UCLA

Heuristic search and planning model real-world problems as graphs, where each node represents a unique state or configuration of the problem, and each edge represents an operator that changes one state to another state. The task is to find a shortest or lowest-cost path between the initial state and a goal state in such a graph, which corresponds to a sequence of operators to solve the given problem instance with minimum cost.

A* is the standard algorithm for a single-agent heuristic search or planning problem. However, A* stores all nodes generated during the search and can run out of the available memory on common heuristic search and planning domains in a few minutes. Therefore, A* usually cannot solve hard problems. On the other hand, the memory requirement of iterative-deepening-A* (IDA*) is only linear in the search depth. However, on a domain where many distinct paths exist between the same pair of nodes, IDA* may generate too many duplicate nodes and hence run for a prohibitively long time.

In this dissertation, we provide three new algorithms, A*+IDA*, A*+BFHS, and IDUCHS, for solving problems that cannot be solved by A* due to memory limitations, nor IDA* due to the existence of many distinct paths between the same pair of nodes. We show that A*+IDA* is the state-of-the-art algorithm on the classic benchmark 24-Puzzle, while A*+BFHS and IDUCHS can generate significantly fewer nodes than A*, hence solving more problems than A* given the same memory limitations.