Adele E. Howe

SoCS Conference 2016 Conference Paper

Stochastic Local Search over Minterms on Structured SAT Instances

• Wenxiang Chen
• L. Darrell Whitley
• Adele E. Howe
• Brian W. Goldman

We observed that Conjunctive Normal Form (CNF) encodings of structured SAT instances often have a set of consecutive clauses defined over a small number of Boolean variables. To exploit the pattern, we propose a transformation of CNF to an alternative representation, Conjunctive Minterm Canonical Form (CMCF). The transformation is a two-step process: CNF clauses are first partitioned into disjoint subsets such that each subset contains CNF clauses with shared Boolean variables. CNF clauses in each subset are then replaced by Minterm Canonical Form (i. e. , partial solutions), which is found by enumeration. We show empirically that a simple Stochastic Local Search (SLS) solver based on CMCF can consistently achieve a higher success rate using fewer evaluations than the SLS solver WalkSAT on two representative classes of structured SAT problems.

ICAPS Conference 2014 Conference Paper

Evaluating Diversity in Classical Planning

• Mark Roberts
• Adele E. Howe
• Indrajit Ray

Applications that require alternative plans challenge the single solution, single quality metric assumptions upon which many classical planners are designed and evaluated. To evaluate the distinctness of alternative plans (i. e. , plan sets), researchers have created diversity metrics that often measure the set difference between the actions of plans. Many approaches for generating plan sets embed the same diversity metric in a weighted evaluation function to guide the search mechanism, thus confounding the search process with its evaluation. We discover that two diversity metrics fail to distinguish similar plans from each other or to identify plans with extraneous actions, so we introduce two new diversity metrics, \emph{uniqueness} and \emph{overlap}, to capture these cases. We then examine the tradeoffs of producing diverse plans while we control for plan length and metric interaction and confirm that metric interaction can significantly impact search performance. We show that planners searching for plan sets must consider a third metric, \emph{parsimony}, that prefers shorter plans while maximizing diversity. We evaluate three existing approaches for generating diverse plans and two new algorithms that are designed to explicitly manage diversity and interaction between the diversity and quality metrics. Our findings synthesize and extend recent results in plan diversity.

TCS Journal 2012 Journal Article

Computing the moments of k -bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time

• Andrew M. Sutton
• L. Darrell Whitley
• Adele E. Howe

We show that given a k -bounded pseudo-Boolean function f, one can always compute the c th moment of f over regions of arbitrary radius in Hamming space in polynomial time using algebraic information from the adjacency structure (where k and c are constants). This result has implications for evolutionary algorithms and local search algorithms because information about promising regions of the search space can be efficiently retrieved, even if the cardinality of the region is exponential in the problem size. Finally, we use our results to introduce a method of efficiently calculating the expected fitness of mutations for evolutionary algorithms.

SoCS Conference 2010 Conference Paper

Directed Plateau Search for MAX-k-SAT

• Andrew M. Sutton
• Adele E. Howe
• L. Darrell Whitley

Local search algorithms for MAX-k-SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau "gradient" function using a Walsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space. This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks. We show that embedding the gradient computation into a hill-climbing local search for MAX-k-SAT improves its convergence profile.

ICAPS Conference 2008 Conference Paper

What Makes Planners Predictable?

• Mark Roberts
• Adele E. Howe
• Brandon Wilson
• Marie desJardins

In recent work we showed that models constructed from planner performance data over a large suite of benchmark problems are surprisingly accurate; 91-99% accuracy for success and 3-496 seconds RMSE for runtime. In this paper, we examine the underlying causes of these accurate models. We deconstruct the learned models to assess how the features, the planners, the search space topology and the amount of training data facilitate predicting planner performance. We find that the models can be learned from relatively little training data (e. g., performance on 10% of the problems in some cases). Generally, having more features improves accuracy. However, the effect is often planner-dependent: in some cases, adding features degrades performance. We identify that the most prominent features in the models are domain features, though we find that the runtime models still have a need for better features. In the last part of the paper, we examine explanatory models to refine the planner dependencies and to identify linkages between problem structure and specific planners' performance.

ICAPS Conference 2007 Conference Paper

Using Adaptive Priority Weighting to Direct Search in Probabilistic Scheduling

• Andrew M. Sutton
• Adele E. Howe
• L. Darrell Whitley

Many scheduling problems reside in uncertain and dynamic environments -- tasks have a nonzero probability of failure and may need to be rescheduled. In these cases, an optimized solution for a short-term time horizon may have a detrimental impact over a broader time scale. We examine a scheduling domain in which time and energy on a phased array radar system is allocated to track objects in orbit around the earth. This domain requires probabilistic modeling to optimize the expected number of successful tasks on a particular day. Failed tasks must be attempted again on subsequent days. Given a set of task requests, we study two long-term objectives: percentage of requests initially successful, and the average time between successful request updates. We investigate adaptive priority weighting strategies that directly influence the short-term objective function and thus indirectly influence the long-term goals. We find that adapting priority weights based on when individual tasks succeed or fail allows a catalog of requests to be filled more quickly. Furthermore, with adaptive priorities, we observe a Pareto-front effect between the two long-term objectives as we modify how priorities are weighted, but an inverse effect of weighting when the priorities are not adapted.

ICAPS Conference 2006 Conference Paper

Looking for Shortcuts: Infeasible Search Analysis for Oversubscribed Scheduling Problems

• Mark F. Rogers
• Adele E. Howe
• L. Darrell Whitley

Searches that include both feasible and infeasible solutions have proved to be ef cient algorithms for solving some scheduling problems. Researchers conjecture that these algorithms yield two primary benefits: 1) they tend to focus on solutions close to the boundary between feasible and infeasible solutions, where active constraints are likely to yield optimal values, and 2) moves that include infeasible solutions may uncover short-cuts in a search space. Researchers have published empirical studies that confirm the value of searching along the feasible-infeasible boundary, but until now there has been little direct evidence that infeasible search yields short-cuts. We present empirical results in two oversubscribed scheduling domains for which boundary region search in infeasible space appears to offer advantages over search in strictly feasible space. Our results confirm that infeasible search finds shortcuts that may improve search efficiency more than boundary region search alone. However, our results also reveal that ineffi- cient infeasible paths which we call detours may degrade search performance, potentially offsetting efficiency shortcuts may provide.

ICAPS Conference 2006 Conference Paper

Spacetrack: Trading off Quality and Utilization in Oversubscribed Schedules

• Andrew M. Sutton
• Adele E. Howe
• L. Darrell Whitley

Many scheduling problems are posed as optimization problems where the goal is to find a feasible schedule that maximizes the utilization of some resource. In some domains it is also necessary to consider the quality of the resulting schedule. In most research these two quantities are independent. This paper introduces a real world problem in which radar tasks must be allocated to track objects in space. We explore the trade-off between off-line task resource utilization and a measure of task quality that correlates to whether tasks are actually successfully executed. We develop two general types of algorithms that differ in the way they reason about quality and explore the trade-off between high quality solutions and solutions with high resource utilization.

ICAPS Conference 2004 Conference Paper

Trading Places: How to Schedule More in a Multi-Resource Oversubscribed Scheduling Problem

• Laura Barbulescu
• Adele E. Howe
• L. Darrell Whitley
• Mark Roberts

Oversubscribed scheduling problems require removing tasks when enough resources are not available. Prior AI approaches have mostly been constructive or repairbased heuristic search. In contrast, we have found a genetic algorithm (GA) to be the best approach to the overconstrained problem of Air Force Satellite Control Network scheduling. We present empirical results that elucidate sources of difficulty in the application and partially explain why the GA is well suited to this problem. We show that the task interaction compels changes involving many tasks simultaneously and the GA appears to be learning domain specific patterns in the data.

AIJ Journal 2003 Journal Article

Problem difficulty for tabu search in job-shop scheduling

• Jean-Paul Watson
• J.Christopher Beck
• Adele E. Howe
• L.Darrell Whitley

Tabu search algorithms are among the most effective approaches for solving the job-shop scheduling problem (JSP). Yet, we have little understanding of why these algorithms work so well, and under what conditions. We develop a model of problem difficulty for tabu search in the JSP, borrowing from similar models developed for SAT and other NP-complete problems. We show that the mean distance between random local optima and the nearest optimal solution is highly correlated with the cost of locating optimal solutions to typical, random JSPs. Additionally, this model accounts for the cost of locating sub-optimal solutions, and provides an explanation for differences in the relative difficulty of square versus rectangular JSPs. We also identify two important limitations of our model. First, model accuracy is inversely correlated with problem difficulty, and is exceptionally poor for rare, very high-cost problem instances. Second, the model is significantly less accurate for structured, non-random JSPs. Our results are also likely to be useful in future research on difficulty models of local search in SAT, as local search cost in both SAT and the JSP is largely dictated by the same search space features. Similarly, our research represents the first attempt to quantitatively model the cost of tabu search for any NP-complete problem, and may possibly be leveraged in an effort to understand tabu search in problems other than job-shop scheduling.

AAMAS Conference 2003 Conference Paper

Using Web Helper Agent Profiles in Query Generation

• Gabriel L. Somlo
• Adele E. Howe

AAAI Conference 1999 Conference Paper

Algorithms Performance and Problem Structure for Flow-Shop Scheduling

• Jean-Paul Watson
• Laura Barbulescu
• Adele E. Howe
• L. Darrell Whitley
• Colorado State University Search

Test suites for many domains often fail to model features present in real-world problems. For the permutation flow-shop sequencing problem (PFSP), the most popular test suite consists of problems whose features are generated from a single uniform random distribution. Synthetic generation of problems with characteristics present in real-world problems is a viable alternative. We compare the performance of several competitive algorithms on problems produced with such a generator. We find that, as more realistic characteristics are introduced, the performance of a stateof-the-art algorithm degrades rapidly: faster and less complex stochastic algorithms provide superior performance. Our empirical results show that small changes in problem structure or problem size can influence algorithm performance. We hypothesize that these performance differences may be partially due to differences in search space topologies; we show that structured problems produce topologies with performance plateaus. Algorithm sensitivity to problem characteristics suggests the need to construct test suites more representative of real-world applications.

ICAPS Conference 1996 Conference Paper

Comparing Heuristic, Evolutionary and Local Search Approaches to Scheduling

• Soraya B. Rana
• Adele E. Howe
• L. Darrell Whitley
• Keith E. Mathias

The choice of search algorithm can play a vital role in the success of a scheduling application. In this paper, we investigate the contribution of search algorithms in solving a real-world warehouse scheduling problem. We compare performance of three types of scheduling algorithms: heuristic, genetic algorithms and local search. Additionally, we assess the in uence of heuristics on search performance and check for bias induced by using a fast objective function to evaluate intermediate search results.

AIJ Journal 1995 Journal Article

Understanding planner behavior

• Adele E. Howe
• Paul R. Cohen

As planners and their environments become increasingly complex, planner behavior becomes increasingly difficult to understand. We often do not understand what causes them to fail, so that we can debug their failures, and we may not understand what allows them to succeed, so that we can design the next generation. This paper describes a partially automated methodology for understanding planner behavior over long periods of time. The methodology, called Dependency Interpretation, uses statistical dependency detection to identify interesting patterns of behavior in execution traces and interprets the patterns using a weak model of the planner's interaction with its environment to explain how the patterns might be caused by the planner. Dependency Interpretation has been applied to identify possible causes of plan failures in the Phoenix planner. By analyzing four sets of execution traces gathered from about 400 runs of the Phoenix planner, we showed that the statistical dependencies describe patterns of behavior that are sensitive to the version of the planner and to increasing temporal separation between events, and that dependency detection degrades predictably as the number of available execution traces decreases and as noise is introduced in the execution traces. Dependency Interpretation is appropriate when a complete and correct model of the planner and environment is not available, but execution traces are available.

AAAI Conference 1992 Conference Paper

Analyzing Failure Recovery to Improve Planner Design

• Adele E. Howe

Plans fail for many reasons. During planner development, failure can often be traced to actions of the planner itself. Failure recovery analysis is a procedure for analyzing execution traces of failure recovery to discover how the planner’s actions may be causing failures. The four step procedure involves statistically analyzing execution data for dependencies between actions and failures, mapping those dependencies to plan structures, explaining how the structures might produce the observed dependencies, and recommending modifications. The procedure is demonstrated by applying it to explain how a particular recovery action may lead to a particular failure in the Phoenix planner. The planner is modified based on the recommendations of the analysis, and the modifications are shown to improve the planner’s performance by removing a source of failure and so reducing the overall incidence of failure.

AAAI Conference 1991 Conference Paper

Failure Recovery: A Model and Experiments

• Adele E. Howe