Frontier search

ABSTRACT

The critical resource that limits the application of best-first search is memory. We present a new class of best-first search algorithms that reduce the space complexity. The key idea is to store only the Open list of generated nodes, but not the Closed list of expanded nodes. The solution path can be recovered by a divide-and-conquer technique, either as a bidirectional or unidirectional search. For many problems, frontier search dramatically reduces the memory required by best-first search. We apply frontier search to breadth-first search of sliding-tile puzzles and the 4-peg Towers of Hanoi problem, Dijkstra's algorithm on a grid with random edge costs, and the A* algorithm on the Fifteen Puzzle, the four-peg Towers of Hanoi Problem, and optimal sequence alignment in computational biology.

REFERENCES

• 1: Araki, S., Goshima, M., Mori, S., Nakashima, H., and Tomita, S. 1999. Application of parallelized DP and A* algorithm to multiple sequence alignment. In Proceedings of the Genome Informatics Workshop IV, 94--102.
• 2: Bode, J.-P., and Hinz, A. 1999. Results and open problems on the Tower of Hanoi. In Proceedings of the 30th Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL). Congressus Numerantium, Vol. 139. 112--122.
• 3: Brungger, A., Marzetta, A., Fukuda, K., and Nievergelt, J. 1999. The parallel search bench ZRAM and its applications. Ann. Oper. Res. 90, 45--63.
• 4: P. P. Chakrabarti , S. Ghose , A. Acharya , S. C. de Sarkar, Heuristic search in restricted memory (research note), Artificial Intelligence, v.41 n.2, p.197-222, Dec. 1989 [doi>10.1016/0004-3702(89)90010-6]
• 5: Culberson, J., and Schaeffer, J. 1998. Pattern databases. Computat. Intell. 14, 3, 318--334.
• 6: Dijkstra, E. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269--271.
• 7: Dudeney, H. 1908. The Canterbury Puzzles (and Other Curious Problems). E.P. Dutton, New York.
• 8: Dunkel, O. 1941. Editorial note concerning advanced problem 3918. Amer. Math. Month. 48, 219.
• 9: Felner, A., Korf, R., and Hanan, S. 2004. Additive pattern database heuristics. J. Artif. Intell. Res. 22, 279--318.
• 10: Felner, A., Meshulam, R., Holte, R., and Korf, R. 2004. Compressing pattern databases. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-04) (San Jose, CA). 638--643.
• 11: Frame, J. 1941. Solution to advanced problem 3918. Amer. Math. Month. 48, 216--217.
• 12: Subrata Ghosh , Ambuj Mahanti , Dana S. Nau, ITS: an efficient limited-memory heuristic tree search algorithm, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.1353-1358, October 1994, Seattle, Washington, United States
• 13: Hart, P., Nilsson, N., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cyber. SSC-4, 2 (July), 100--107.
• 14: D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
• 15: Daniel S. Hirschberg, Serial computations of Levenshtein distances, Pattern matching algorithms, Oxford University Press, Oxford, 1997
• 16: Hohwald, H., Thayer, I., and Korf, R. 2003. Comparing best-first search and dynamic programming for optimal multiple sequence alignment. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03) (Acapulco, Mexico). 1239--1245.
• 17: Takahiro Ikeda , Hiroshi Imai, Enhanced A algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases, Theoretical Computer Science, v.210 n.2, p.341-374, Jan. 17, 1999 [doi>10.1016/S0304-3975(98)00093-0]
• 18: Johnson, W., and Storey, W. 1879. Notes on the 15 Puzzle. Amer. J. Math. 2, 397--404.
• 19: Kaindl, H., and Kainz, G. 1997. Bidirectional heuristic search reconsidered. J. Artif. Intell. Res. 7, 283--317.
• 20: Klavzar, S., and Milutinovic, U. 2002. Simple explicit formulas for the Frame- Stewart numbers. Ann. Combinat. 6, 157--167.
• 21: Richard E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, v.27 n.1, p.97-109, Sept. 1985 [doi>10.1016/0004-3702(85)90084-0]
• 22: Richard E. Korf, Linear-space best-first search, Artificial Intelligence, v.62 n.1, p.41-78, July 1993 [doi>10.1016/0004-3702(93)90045-D]
• 23: Richard E. Korf, A Divide and Conquer Bidirectional Search: First Results, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1184-1191, July 31-August 06, 1999
• 24: Korf, R. 2003. Delayed duplicate detection: Extended abstract. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03) (Acapulco, Mexico). 1539--1541.
• 25: Korf, R. 2004. Best-first frontier search with delayed duplicate detection. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-2004) (San Jose, CA). 650--657.
• 26: Korf, R. 2005. Large-scale parallel breadth-first search. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI-2005) (Pittsburgh, PA), 1380--1385.
• 27: Richard E. Korf , David Maxwell Chickering, Best-first minimax search, Artificial Intelligence, v.84 n.1-2, p.299-337, July 1996 [doi>10.1016/0004-3702(95)00096-8]
• 28: Richard E. Korf , Michael Reid , Stefan Edelkamp, Time complexity of iterative-deepening-A, Artificial Intelligence, v.129 n.1-2, p.199-218, June 2001 [doi>10.1016/S0004-3702(01)00094-7]
• 29: Richard E. Korf , Weixiong Zhang, Divide-and-Conquer Frontier Search Applied to Optimal Sequence Alignment, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.910-916, July 30-August 03, 2000
• 30: Lermen, M., and Reinert, K. 2000. The practical use of the A* algorithm for exact multiple sequence alignment. J. Computat. Biol. 7, 5, 655--671.
• 31: Needleman, S., and Wunsch, C. 1970. A general method applicable to the search for similarities in the amino acid sequences of two proteins. J. Molec. Biol. 48, 443--453.
• 32: Pearl, J. 1984. Heuristics. Addison-Wesley, Reading, MA.
• 33: Pohl, I. 1970. Heuristic search viewed as path finding in a graph. Artif. Intell. 1, 193--204.
• 34: Pohl, I. 1971. Bi-directional search. In Machine Intelligence 6, B. Meltzer and D. Michie, Eds. American Elsevier, New York, 127--140.
• 35: Reinefeld, A. 1993. Complete solution of the Eight Puzzle and the benefit of node ordering in IDA*. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93) (Chambery, France). 248--253.
• 36: Rudin, H. 1987. Network protocols and tools to help produce them. In Annual Review of Computer Science, J. Traub, B. Grosz, B. Lampson, and N. Nilsson, Eds. Annual Reviews Inc., Palo Alto, CA, 291--316.
• 37: Stuart Russell, Efficient memory-bounded search methods, Proceedings of the 10th European conference on Artificial intelligence, p.1-5, August 1992, Vienna, Austria
• 38: Schofield, P. 1967. Complete solution of the Eight Puzzle. In Machine Intelligence 3, B. Meltzer and D. Michie, Eds. American Elsevier, New York, 125--133.
• 39: Sen, A., and Bagchi, A. 1989. Fast recursive formulations for best-first search that allow controlled use of memory. In Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI-89) (Detroit, MI). 297--302.
• 40: Setubal, J., and Meidanis, J. 1997. Introduction to Computational Molecular Biology. PWS Publishing, Boston, MA.
• 41: J. L. Spouge, Speeding up dynamic programming algorithms for finding optimal lattice paths, SIAM Journal on Applied Mathematics, v.49 n.5, p.1552-1566, Oct. 1989 [doi>10.1137/0149094]
• 42: Stewart, B. 1941. Solution to advanced problem 3918. Amer. Math. Monthly 48, 217--219.
• 43: Taylor, L., and Korf, R. 1993. Pruning duplicate nodes in depth-first search. In Proceedings of the 11th National Conference on Artificial Intelligence (AAAI-93) (Washington, DC). 756--761.
• 44: Thayer, I. 2003. Methods for optimal multiple sequence alignment. M.S. dissertation. Computer Science Department, University of California, Los Angeles, CA.
• 45: Thomson, J., Plewniak, F., and Poch, O. 1999. BAli BASE: A benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics 15, 1, 87--88.
• 46: Esko Ukkonen, Algorithms for approximate string matching, Information and Control, v.64 n.1-3, p.100-118, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80046-2]
• 47: Takayuki Yoshizumi , Teruhisa Miura , Toru Ishida, A* with Partial Expansion for Large Branching Factor Problems, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.923-929, July 30-August 03, 2000
• 48: Rong Zhou , Eric A. Hansen, Multiple sequence alignment using anytime A*, Eighteenth national conference on Artificial intelligence, p.975-976, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 49: Zhou, R., and Hansen, E. 2003a. Sparse-memory graph search. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03) (Acapulco, Mexico). 1259--1266.
• 50: Rong Zhou , Eric A. Hansen, Sweep A*: Space-Efficient Heuristic Search in Partially Ordered Graphs, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.427, November 03-05, 2003
• 51: Zhou, R., and Hansen, E. 2004. Breadth-first heuristic search. In Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS-04) (Whistler, British Columbia, Canada). 92--100.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Keywords:
A* algorithm, Dijkstra's algorithm, Towers of Hanoi, best-first search, bidirectional search, breadth-first search, heuristic search, sequence alignment, sliding-tile puzzles