PhD Dissertation

Bidirectional Heuristic Search

Abstract

Bidirectional heuristic search is a well-known technique for solving pathfinding problems. The goal in a pathfinding problem is to find paths—often of lowest cost—between nodes in a graph. Many real-world problems, such as finding the quickest route between two points in a map or measuring the similarity of DNA sequences, can be modeled as pathfinding problems.

Bidirectional brute-force search does simultaneous brute-force searches forward from the initial state and backward from the goal states, finding solutions when both intersect. The idea of adding a heuristic to guide search is an old one, but has not seen widespread use and is generally believed to be ineffective.

I present an intuitive explanation for the ineffectiveness of front-to-end bidi- rectional heuristic search. Previous work has examined this topic, but mine is the first comprehensive explanation for why most front-to-end bidirectional heuristic search algorithms will usually be outperformed by either unidirectional heuris- tic or bidirectional brute-force searches. However, I also provide a graph wherein bidirectional heuristic search does outperform both other approaches, as well as real-world problem instances from the road navigation domain. These demonstrate that there can be no general, formal proof of the technique’s ineffectiveness.

I tested my theory in a large number of popular search domains, confirming its predictions. One of my experiments demonstrates that a commonly-repeated explanation for the ineffectiveness of bidirectional heuristic search—that it spends most of its time proving solution optimality—is in fact wrong, and that with a strong heuristic a bidirectional heuristic search tends to find optimal solutions very late in a search.

Finally, I introduce state-of-the-art solvers for the four-peg Towers of Hanoi with arbitrary initial and goal states, and peg solitaire, using disk-based, bidirec- tional algorithms. The Towers of Hanoi solver is a bidirectional brute-force solver which, as my theory predicts, outperforms a unidirectional heuristic solver. The peg solitaire solver is a bidirectional heuristic algorithm with novel heuristics. While my theory demonstrates that bidirectional heuristic search is generally in- effective, the peg solitaire domain demonstrates several caveats to my theory that this algorithm takes advantage of. 

 

AAAI 2015

Limitations Of Front-To-End Bidirectional Heuristic Search

[Video of AAAI 2015 Presentation | Slides Used]

Abstract

We present an intuitive explanation for the limited effectiveness of front-to-end bidirectional heuristic search, supported with extensive evidence from many commonly-studied domains. While previous work has proved the limitations of specific algorithms, we show that any front-to-end bidirectional heuristic search algorithm will likely be dominated by unidirectional heuristic search or bidirectional brute-force search. We also demonstrate a pathological case where bidirectional heuristic search is the dominant algorithm, so a stronger claim cannot be made. Finally, we show that on the four-peg Towers Of Hanoi with arbitrary start and goal states, bidirectional brute-force search outperforms unidirectional heuristic search using pattern-database heuristics.

 

AAAI 2012

Solving Peg Solitaire with Bidirectional BFIDA*

Abstract

We present a novel approach to bidirectional breadth-first IDA* (BFIDA*) and demonstrate its effectiveness in the domain of peg solitaire, a simple puzzle. Our approach improves upon unidirectional BFIDA* by usually avoiding the last iteration of search entirely, greatly speeding up search. In addition, we provide a number of improvements specific to peg solitaire. We have improved duplicate-detection in the context of BFIDA*. We have strengthened the heuristic used in the previous state-of-the-art solver. Finally, we use bidirectional search frontiers to provide a stronger technique for pruning unsolvable states. The combination of these approaches allows us to improve over the previous state-of-the-art, often by a two-orders-of-magnitude reduction in search time. 

 

AAAI 2012

Solving Dots-And-Boxes

Abstract

Dots-And-Boxes is a well-known and widely-played combinatorial game. While the rules of play are very simple, the state space for even very small games is extremely large, and finding the outcome under optimal play is correspondingly hard. In this paper we introduce a Dots-And-Boxes solver which is significantly faster than the current state-of-the-art: over an order-of-magnitude faster on several large problems. Our approach uses Alpha-Beta search and applies a number of techniques—both problem-specific and general—that reduce the search space to a manageable size. Using these techniques, we have determined for the first time that Dots-And-Boxes on a board of 4 × 5 boxes is a tie given optimal play; this is the largest game solved to date.