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

Antti Autere, Helsinki University of Technology, Finland

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.