Matthew Hatem

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.

AAAI Conference 2015 Conference Paper

Recursive Best-First Search with Bounded Overhead

• Matthew Hatem
• Scott Kiesel
• Wheeler Ruml

There are two major paradigms for linear-space heuristic search: iterative deepening (IDA*) and recursive best-first search (RBFS). While the node regeneration overhead of IDA* is easily characterized in terms of the heuristic branching factor, the overhead of RBFS depends on how widely the promising nodes are separated in the search tree, and is harder to anticipate. In this paper, we present two simple techniques for improving the performance of RBFS while maintaining its advantages over IDA*. While these techniques work well in practice, they do not provide any theoretical bounds on the amount of regeneration overhead. To this end, we introduce RBFSCR, the first method for provably bounding the regeneration overhead of RBFS. We show empirically that this improves its performance in several domains, both for optimal and suboptimal search, and also yields a better linear-space anytime heuristic search. RBFSCR is the first linear space best-first search robust enough to solve a variety of domains with varying operator costs.

SoCS Conference 2014 Conference Paper

Bounded Suboptimal Search in Linear Space: New Results

• Matthew Hatem
• Wheeler Ruml

Bounded suboptimal search algorithms are usually faster than optimal ones, but they can still run out of memory on large problems. This paper makes three contributions. First, we show how solution length estimates, used by the current state-of-the-art linear-space bounded suboptimal search algorithm Iterative Deepening EES, can be used to improve unbounded-space suboptimal search. Second, we convert one of these improved algorithms into a linear-space variant called Iterative Deepening A* epsilon, resulting in a new state of the art in linear-space bounded suboptimal search. Third, we show how Recursive Best-First Search can be used to create additional linear-space variants that have more stable performance. Taken together, these results significantly expand our armamentarium of bounded suboptimal search algorithms.

AAAI Conference 2014 Conference Paper

Simpler Bounded Suboptimal Search

• Matthew Hatem
• Wheeler Ruml

It is commonly appreciated that solving search problems optimally can take too long. Bounded suboptimal search algorithms trade increased solution cost in a principled way for reduced solving time. Explicit Estimation Search (EES) is a recent state-of-the-art algorithm for bounded suboptimal search. Although it tends to expand fewer nodes than alternative algorithms, its per-node expansion overhead is much higher, causing it to sometimes take longer. In this paper, we present simplified variants of EES (SEES) and an earlier algorithm, A∗ (SA∗ ), that use different implementations of the same motivating ideas to significantly reduce search overhead and implementation complexity. In an empirical evaluation, we find that SEES matches or outperforms classic bounded suboptimal search algorithms, such as WA∗, on all domains tested. We also confirm that, while SEES and SA∗ expand roughly the same number of nodes as their progenitors, they solve problems significantly faster and are much easier to implement. This work widens the applicability of state-ofthe-art bounded suboptimal search by making it easier to deploy.

SoCS Conference 2013 Conference Paper

Bounded Suboptimal Heuristic Search in Linear Space

• Matthew Hatem
• Roni Stern
• Wheeler Ruml

It is commonly appreciated that solving search problems optimally can overrun time and memory constraints. Bounded suboptimal search algorithms trade increased solution cost for reduced solving time and memory consumption. However, even suboptimal search can overrun memory on large problems. The conventional approach to this problem is to combine a weighted admissible heuristic with an optimal linear space algorithm, resulting in algorithms such as Weighted IDA* (wIDA*). However, wIDA* does not exploit distance-to-go estimates or inadmissible heuristics, which have recently been shown to be helpful for suboptimal search. In this paper, we present a linear space analogue of Explicit Estimation Search (EES), a recent algorithm specifically designed for bounded suboptimal search. We call our method Iterative Deepening EES (IDEES). In an empirical evaluation, we show that IDEES dramatically outperforms wIDA* on domains with non-uniform edge costs and can scale to problems that are out of reach for the original EES.

AAAI Conference 2013 Conference Paper

External Memory Best-First Search for Multiple Sequence Alignment

• Matthew Hatem
• Wheeler Ruml

Multiple sequence alignment (MSA) is a central problem in computational biology. It is well known that MSA can be formulated as a shortest path problem and solved using heuristic search, but the memory requirement of A* makes it impractical for all but the smallest problems. Partial Expansion A* (PEA*) reduces the memory requirement of A* by generating only the most promising successor nodes. However, even PEA* exhausts available memory on many problems. Another alternative is Iterative Deepening Dynamic Programming, which uses an uninformed search order but stores only the nodes along the search frontier. However, it too cannot scale to the largest problems. In this paper, we propose storing nodes on cheap and plentiful secondary storage. We present a new general-purpose algorithm, Parallel External PEA* (PE2A*), that combines PEA* with Delayed Duplicate Detection to take advantage of external memory and multiple processors to solve large MSA problems. In our experiments, 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 suggests that external best-first search can effectively use heuristic information to surpass methods that rely on uninformed search orders.

AAAI Conference 2013 Conference Paper

Heuristic Search for Large Problems with Real Costs

• Matthew Hatem

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

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.