Iterative-Deepening Uniform-Cost Heuristic Search

Authors

  • Zhaoxing Bu University of California, Los Angeles
  • Richard E. Korf University of California, Los Angeles

Keywords:

Problem Solving Using Search, Combinatorial Puzzles, Analysis Of Search Algorithms, Time, Memory, And Solution Quality Trade-offs

Abstract

Breadth-first heuristic search (BFHS) is a classic algorithm for optimally solving heuristic search and planning problems. BFHS is slower than A* but requires less memory. However, BFHS only works on unit-cost domains. We propose a new algorithm that extends BFHS to domains with different edge costs, which we call uniform-cost heuristic search (UCHS). Experimental results show that the iterative-deepening version of UCHS, IDUCHS, is slower than A* but requires less memory on a variety of planning domains.

Downloads

Published

2022-07-17