Memory-Bounded Bidirectional Search

Previous approaches to bidirectional search require exponential space, and they are either less efficient than unidirectional search for finding optimal solutions, or they cannot even find such solutions for difficult problems. Based on a memory-bounded unidirectional algorithm for trees (SMA*), we developed a graph search extension, and we used it to construct a very efficient memory-bounded bidirectional algorithm. This bidirectional algorithm can be run for difficult problems with bounded memory. In addition, it is much more efficient than the corresponding unidirectional search algorithm also for finding optimal solutions to difficult problems. In summary, bidirectional search appears to be the best approach to solving difficult problems, and this indicates the extreme usefulness of a paradigm that was neglected for long. Notation s, t l-1 (4 ra (4 d d’ d(n) hf (4 il$f h44 F$) c* c L min TREES TREES OPEN; CLOSED~ PC(4 Start node and goal node, respectively. Successors of node n in the problem graph. Parents of node n in the problem graph. Current search direction index; when search is in the forward direction d = 1, and when in the backward direction d = 2. 3 - d; it is the index of the direction opposite to the current search direction. Cost of an optimal path from s to n if i = 1, or from t to n if i = 2. Cost of an optimal path from n to t if i = 1, or from n to s if i = 2. Estimates of g: (n) and hf (n), respectively. Static evaluation function. Revised evaluation after pathmax or backup. Cost of an optimal path from s to t. Cost of a solution path from s to t found. Cost of the best (least costly) complete path found so far from s to t. The forward search tree. The backward search tree. The set of open nodes in TREES. The set of closed nodes in TREE; . Parent of node n in TREES.

Authors

• Hermann Kaindl Aliasghar Khorsand

Keywords

No keywords are indexed for this paper.