 Main
FrontToEnd Bidirectional Heuristic Search
 Barker, Joseph Kelly
 Advisor(s): Korf, Richard E
Abstract
Bidirectional heuristic search is a wellknown technique for solving pathfinding problems. The goal in a pathfinding problem is to find pathsoften of lowest costbetween nodes in a graph. Many realworld 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 bruteforce search does simultaneous bruteforce 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 fronttoend bidirectional heuristic search. Previous work has examined this topic, but mine is the first comprehensive explanation for why most fronttoend bidirectional heuristic search algorithms will usually be outperformed by either unidirectional heuristic or bidirectional bruteforce searches. However, I also provide a graph wherein bidirectional heuristic search does outperform both other approaches, as well as realworld 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 commonlyrepeated explanation for the ineffectiveness of bidirectional heuristic searchthat it spends most of its time proving solution optimalityis 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 stateoftheart solvers for the fourpeg Towers of Hanoi with arbitrary initial and goal states, and peg solitaire, using diskbased, bidirectional algorithms. The Towers of Hanoi solver is a bidirectional bruteforce 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 ineffective, the peg solitaire domain demonstrates several caveats to my theory that this algorithm takes advantage of.
Main Content
Enter the password to open this PDF file:













