A METRIC SPACE APPROACH TO THE SPECIFICATION OF THE HEURISTIC FUNCTION FOR THE A-ASTERISK ALGORITHM

Given a graph with area that have costs, the A algorithm is designed to find the shortest path from a single node to a set of nodes. While the A algorithm is well understood, it is somewhat limited in its app lication due to the fact that it is often difficult to specify the ''h euristic function'' so that A exhibits desirable computational proper ties. In this paper a metric space approach to the specification of th e heuristic function is introduced. It is shown how to specify an admi ssible and monotone heuristic function for a wide class of problem dom ains. In addition, when the cost structure for the underlying graph is specified via a metric, it is shown that admissible and monotone heur istic functions are easy to specify and further computational advantag es can be obtained. Applications to an optimal parts distribution prob lem in flexible manufacturing systems and artificial intelligence plan ning problems are provided.