A* as an Optimal Resource Allocation Policy in Path Finding Problems

May 2001

Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2001)

Volume

Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2001)

All Papers

Consider a problem of finding a path from a start to a goal node on a graph. Suppose that we have divided the problem into smaller subproblems by dividing the search graph into subgraphs. Nodes and edges in a subgraph form subsets of the nodes and the edges in the original search graph. Assume that we have either specialized algorithms for searching the subgraphs or only a single algorithm expanding nodes in every subgraph. Usually it is impossible to know a priori which algorithm finds solution paths fastest or which subproblem is the easiest to solve. In this paper, we will examine how A* can be used as a resource allocation policy for node expansions among the subgraphs. Moreover, we will discuss when A* is the optimal algorithm for that purpose.