Km. Passino et Pj. Antsaklis, A METRIC SPACE APPROACH TO THE SPECIFICATION OF THE HEURISTIC FUNCTION FOR THE A-ASTERISK ALGORITHM, IEEE transactions on systems, man, and cybernetics, 24(1), 1994, pp. 159-166
Citations number
40
Categorie Soggetti
Controlo Theory & Cybernetics","Computer Science Cybernetics","Engineering, Eletrical & Electronic
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.