Heuristic search with limited resources
Subrata Kumar Ghosh · 1994
Heuristic Search is a fundamental problem solving method with applications in many areas of artificial intelligence and operations research. A variety of heuristic search algorithms have been developed with various computational tradeoffs. For example, the IDA$\sp\*$ algorithm overcomes the exponential memory requirement of A$\sp\*$, but at the expense of doing more node generations. This thesis investigates two kinds of tradeoffs in heuristic search: (1) space versus time for admissible search algorithms, and (2) space and time versus solution quality for inadmissible search algorithms. The main results are summarized below. In general, no limited-memory best-first admissible search algorithm can do the same number of node generations as best-first search algorithm like A$\sp\*$, even in the asymptotic sense. However, for a restricted class of trees, it is possible to guarantee asymptotic optimality. Analysis of IDA$\sp\*$ on acyclic graphs shows that IDA$\sp\*$ can perform exponentially worse than A$\sp\*$ on graphs. This thesis also presents a new limited-memory admissible tree search algorithm called Iterative Threshold Search (ITS). ITS improves IDA$\sp\*$ as follows: (1) unlike IDA$\sp\*$ it can use any amount of memory given to it as input, and (2) it dominates IDA$\sp\*$, i.e., given the same amount of memory, ITS never expands more nodes than IDA$\sp\*$ and there are trees on which it expands far fewer nodes. ITS is a space-efficient search algorithm. However, like IDA$\sp\*$, it is an admissible algorithm and therefore does not scale up to large problems. For large problems and for real time search, this thesis presents two unidirectional algorithms, namely Breadth-Depth-A$\sp\*$ (BDA$\sp\*$) and Controlled-A$\sp\*$ (CA$\sp\*$), and a bidirectional algorithm called Bidirectional Heuristic Front-to-Front Stage Search (BHFFSS). These algorithms trade solution quality for exponential time. Experimental results on the 15-puzzle and 24-puzzle problems and the 3-machine scheduling problem show that these algorithms are useful for finding near-optimal solutions quickly. Finally, the thesis presents a new search technique called Block Depth-First Search (BDFS). BDFS can be used both for finding near-optimal solutions as well as for finding optimal solutions. BDFS starts with a near-optimal solution in linear time and then improves its solution until it converges to the optimal solution.