A heuristic search algorithm for path determination with learning

We present and analyze an algorithm, adaptive A*(AA*), for finding a least-cost-path from start node to goal node set in a directed graph. Arc costs are assumed to be scalar-valued, and the cost of each path is the sum of the concomitant arc costs. Search is guided by: 1) a collection of real-valued functions on the node set, which is a generalization of the heuristic function associated with A*; 2) a set of predetermined optimal paths; and 3) a set of paths in the graph that are considered desirable but may or may not be optimal. The knowledge representations described in (1) and (3) can be useful in describing knowledge acquired from humans. The knowledge representation described in (2) can be used to automate knowledge acquisition, so that A* exhibits a form of machine learning. Additionally, the collection of real-valued functions on the node set can be useful in describing bounds on the perfect heuristic function, i.e., the solution of the related dynamic program. A numerical analysis, using a specialization of AA* applied to a model of the Cleveland, OH, road network demonstrated significant performance improvement relative to A*