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

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.