1. Matthew Hatem, Roni Stern and Wheeler Ruml, Bounded Suboptimal Heuristic Search in Linear Space, Proceedings of the Sixth Annual Symposium on Combinatorial Search (in press), 2013. PDF

  1. 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.


  1. Matthew Hatem and Wheeler Ruml, External Memory Best-First Search for Multiple Sequence Alignment, Proceedings of the Twenty-seventh AAAI Conference on Artificial Intelligence (in press), 2013. PDF

  1. 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 space complexity 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.


  1. Ethan Burns, Matthew Hatem, Michael J. Leighton, and Wheeler Ruml, Implementing Fast Heuristic Search Code, Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS-12), 2012. PDF

  1. 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.


  1. Matthew Hatem, Ethan Burns and Wheeler Ruml, Heuristic Search for Large Problems With Real Costs, Proceedings of the Twenty-fifth AAAI Conference on Artificial Intelligence (AAAI-11), 2011. PDF


  1. 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.

About    Papers    CV    Contact