Ethan Burns

JAIR Journal 2018 Journal Article

Solving Large Problems with Heuristic Search: General-Purpose Parallel External-Memory Search

• Matthew Hatem
• Ethan Burns
• Wheeler Ruml

Classic best-first heuristic search algorithms, like A*, record every unique state they encounter in RAM, making them infeasible for solving large problems. In this paper, we demonstrate how best-first search can be scaled to solve much larger problems by exploiting disk storage and parallel processing and, in some cases, slightly relaxing the strict best-first node expansion order. Some previous disk-based search algorithms abandon best-first search order in an attempt to increase efficiency. We present two case studies showing that A*, when augmented with Delayed Duplicate Detection, can actually be more efficient than these non-best-first search orders. First, we present a straightforward external variant of A*, called PEDAL, that slightly relaxes best-first order in order to be I/O efficient in both theory and practice, even on problems featuring real-valued node costs. Because it is easy to parallelize, PEDAL can be faster than in-memory IDA* even on domains with few duplicate states, such as the sliding-tile puzzle. Second, we present a variant of PEDAL, called PE2A*, that uses partial expansion to handle problems that have large branching factors. When tested on the problem of Multiple Sequence Alignment, PE2A* is the first algorithm capable of solving the entire Reference Set 1 of the standard BAliBASE benchmark using a biologically accurate cost function. This work shows that classic best-first algorithms like A* can be applied to large real-world problems. We also provide a detailed implementation guide with source code both for generic parallel disk-based best-first search and for Multiple Sequence Alignment with a biologically accurate cost function. Given its effectiveness as a general-purpose problem-solving method, we hope that this makes parallel and disk-based search accessible to a wider audience.

JAIR Journal 2015 Journal Article

Achieving Goals Quickly Using Real-time Search: Experimental Results in Video Games

• Scott Kiesel
• Ethan Burns
• Wheeler Ruml

In real-time domains such as video games, planning happens concurrently with execution and the planning algorithm has a strictly bounded amount of time before it must return the next action for the agent to execute. We explore the use of real-time heuristic search in two benchmark domains inspired by video games. Unlike classic benchmarks such as grid pathfinding and the sliding tile puzzle, these new domains feature exogenous change and directed state space graphs. We consider the setting in which planning and acting are concurrent and we use the natural objective of minimizing goal achievement time. Using both the classic benchmarks and the new domains, we investigate several enhancements to a leading real-time search algorithm, LSS-LRTA*. We show experimentally that 1) it is better to plan after each action or to use a dynamically sized lookahead, 2) A*-based lookahead can cause undesirable actions to be selected, and 3) on-line de-biasing of the heuristic can lead to improved performance. We hope this work encourages future research on applying real-time search in dynamic domains.

SoCS Conference 2013 Conference Paper

Experimental Real-Time Heuristic Search Results in a Video Game

• Ethan Burns
• Scott Kiesel
• Wheeler Ruml

In real-time domains such as video games, a planning algo- rithm has a strictly bounded time before it must return the next action for the agent to execute. We introduce a realistic video game benchmark domain that is useful for evaluating real-time heuristic search algorithms. Unlike previous bench- marks such as grid pathfinding and the sliding tile puzzle, this new domain includes dynamics and induces a directed graph. Using both the previous and new domains, we investigate sev- eral enhancements to a leading real-time search algorithm, LSS-LRTA*. We show experimentally that 1) it is not dif- ficult to outperform A* when optimizing goal achievement time, 2) it is better to plan after each action than to commit to multiple actions or to use a dynamically sized lookahead, 3) A*-based lookahead can cause undesirable actions to be selected, and 4) on-line de-biasing of the heuristic can lead to improved performance. We hope that this new domain and results will stimulate further research on applying real-time search to dynamic real-time domains.

SoCS Conference 2012 Conference Paper

Abstraction-Guided Sampling for Motion Planning

• Scott Kiesel
• Ethan Burns
• Wheeler Ruml

Motion planning in continuous space is a fundamentalrobotics problem that has been approached from many per-spectives. Rapidly-exploring Random Trees (RRTs) usesampling to efficiently traverse the continuous and high-dimensional state space. Heuristic graph search methods uselower bounds on solution cost to focus effort on portions ofthe space that are likely to be traversed by low-cost solutions. In this work, we bring these two ideas together in a tech-nique called f -biasing: we use estimates of solution cost, computed as in heuristic search, to guide sparse sampling, as in RRTs. We see this new technique as strengthening theconnections between motion planning in robotics and combi-natorial search in artificial intelligence.

ICAPS Conference 2012 Conference Paper

Anticipatory On-Line Planning

• Ethan Burns
• J. Benton 0001
• Wheeler Ruml
• Sung Wook Yoon
• Minh Binh Do

We consider the problem of on-line continual planning, in whichadditional goals may arrive while plans for previous goals are stillexecuting and plan quality depends on how quickly goals are achieved. This is a challenging problem even in domains with deterministicactions. One common and straightforward approach is reactive planning, in which plans are synthesized when a new goal arrives. In this paper, we adapt the technique of hindsight optimization from on-line schedulingand probabilistic planning to create an anticipatory on-line planningalgorithm. Using an estimate of the goal arrival distribution, wesample possible futures and use a deterministic planner to estimate thevalue of taking possible actions at each time step. Results in twobenchmark domains based on unmanned aerial vehicle planning andmanufacturing suggest that an anticipatory approach yields a superiorplanner that is sensitive not only to which action should be executed, but when.

SoCS Conference 2012 Conference Paper

Implementing Fast Heuristic Search Code

• Ethan Burns
• Matthew Hatem
• Michael J. Leighton
• Wheeler Ruml

Published papers rarely disclose implementation details. In this paper we show how such details can account for speedups of up to a factor of 28 for different implementations of the same algorithm. We perform an in-depth analysis of the most popular benchmark in heuristic search: the 15-puzzle. We study implementation choices in C++ for both IDA* and A* using the Manhattan distance heuristic. Results suggest that several optimizations deemed critical in folklore provide only small improvements while seemingly innocuous choices can play a large role. These results are important for ensuring that the correct conclusions are drawn from empirical comparisons

ICAPS Conference 2012 Conference Paper

Integrating Vehicle Routing and Motion Planning

• Scott Kiesel
• Ethan Burns
• Christopher Makoto Wilt
• Wheeler Ruml

There has been much interest recently in problems that com-bine high-level task planning with low-level motion planning. In this paper, we present a problem of this kind that arises inmulti-vehicle mission planning. It tightly integrates task al-location and scheduling, who will do what when, with pathplanning, how each task will actually be performed. It ex-tends classical vehicle routing in that the cost of executing aset of high-level tasks can vary significantly in time and costaccording to the low-level paths selected. It extends classi-cal motion planning in that each path must minimize costwhile also respecting temporal constraints, including thoseimposed by the agent's other tasks and the tasks assigned toother agents. Furthermore, the problem is a subtask withinan interactive system and therefore must operate within se-vere time constraints. We present an approach to the problembased on a combination of tabu search, linear programming, and heuristic search. We evaluate our planner on represen-tative problem instances and find that its performance meetsthe demanding requirements of our application. These resultsdemonstrate how integrating multiple diverse techniques cansuccessfully solve challenging real-world planning problemsthat are beyond the reach of any single method.

AAAI Conference 2012 Conference Paper

Planning Under Time Pressure

• Ethan Burns

SoCS Conference 2011 Conference Paper

Best-First Search for Bounded-Depth Trees

• Kevin Rose
• Ethan Burns
• Wheeler Ruml

Tree search is a common technique for solving constraint satisfaction and combinatorial optimization problems. The most popular strategies are depth-first search and limited discrepancy search. Aside from pruning or ordering the children of each node, these algorithms do not adapt their search order to take advantage of information that becomes available during search, such as heuristic scores or leaf costs. We present a framework called best-leaf-first search (BLFS) that uses this additional information to estimate the cost of taking discrepancies in the search tree and then attempts to visit leaves in a best-first order. In this way, BLFS brings the idea of best-first search from shortest path problems to the areas of constraint satisfaction and combinatorial optimization. Empirical results demonstrate that this new dynamic approach results in better search performance than previous static search strategies on two very different domains: structured CSPs and the traveling salesman problem.

AAAI Conference 2011 Conference Paper

Heuristic Search for Large Problems With Real Costs

• Matthew Hatem
• Ethan Burns
• Wheeler Ruml

The memory requirements of basic best-first heuristic search algorithms like A* make them infeasible for solving large problems. External disk storage is cheap and plentiful compared to the cost of internal RAM. Unfortunately, state-ofthe-art external memory search algorithms either rely on brute-force search techniques, such as breadth-first search, or they rely on all node values falling in a narrow range of integers, and thus perform poorly on real-world domains with real-valued costs. We present a new general-purpose algorithm, PEDAL, that uses external memory and parallelism to perform a best-first heuristic search capable of solving large problems with real costs. We show theoretically that PEDAL is I/O efficient and empirically that it is both better on a standard unit-cost benchmark, surpassing internal IDA* on the 15-puzzle, and gives far superior performance on problems with real costs.

AAAI Conference 2010 Conference Paper

Searching Without a Heuristic: Efficient Use of Abstraction

• Bradford Larsen
• Ethan Burns
• Wheeler Ruml
• Robert Holte

In problem domains where an informative heuristic evaluation function is not known or not easily computed, abstraction can be used to derive admissible heuristic values. Optimal path lengths in the abstracted problem are consistent heuristic estimates for the original problem. Pattern databases are the traditional method of creating such heuristics, but they exhaustively compute costs for all abstract states and are thus usually appropriate only when all instances share the same single goal state. Hierarchical heuristic search algorithms address these shortcomings by searching for paths in the abstract space on an as-needed basis. However, existing hierarchical algorithms search less efficiently than pattern database constructors: abstract nodes may be expanded many times during the course of a base-level search. We present a novel hierarchical heuristic search algorithm, called Switchback, that uses an alternating direction of search to avoid abstract node re-expansions. This algorithm is simple to implement and demonstrates superior performance to existing hierarchical heuristic search algorithms on several standard benchmarks.

IJCAI Conference 2009 Conference Paper

• Ethan Burns
• Seth Lemons
• Rong Zhou
• Wheeler Ruml

To harness modern multi-core processors, it is imperative to develop parallel versions of fundamental algorithms. In this paper, we present a general approach to best-first heuristic search in a sharedmemory setting. Each thread attempts to expand the most promising open nodes. By using abstraction to partition the state space, we detect duplicate states without requiring frequent locking. We allow speculative expansions when necessary to keep threads busy. We identify and fix potential livelock conditions in our approach, verifying its correctness using temporal logic. In an empirical comparison on STRIPS planning, grid pathfinding, and sliding tile puzzle problems using an 8-core machine, we show that A* implemented in our framework yields faster search than improved versions of previous parallel search proposals. Our approach extends easily to other best-first searches, such as Anytime weighted A*.

ICAPS Conference 2009 Conference Paper

Suboptimal and Anytime Heuristic Search on Multi-Core Machines

• Ethan Burns
• Seth Lemons
• Wheeler Ruml
• Rong Zhou 0001

In order to scale with modern processors, planning algorithms must become multi-threaded. In this paper, we present parallel shared-memory algorithms for two problems that underlie many planning systems: suboptimal and anytime heuristic search. We extend a recently-proposed approach for parallel optimal search to the suboptimal case, providing two new pruning rules for bounded suboptimal search. We also show how this new approach can be used for parallel anytime search. Using temporal logic, we prove the correctness of our framework, and in an empirical comparison on STRIPS planning, grid pathfinding, and sliding tile puzzle problems using an 8-core machine, we show that it yields faster search performance than previous proposals.