EXTENSIONS AND APPLICATIONS OF THE A * ALGORITHM Antti Autere

ABSTRACT: In this thesis we investigate path finding problems, that is, plan-ning routes from a start node to some goal nodes in a graph. Such problems arise in many fields of technology, for example, production planning,energy-aware message routing in large networks, resource allocation, and vehicle navigation systems. We concentrate mostly on planning a minimumcost path using the A * algorithm.We begin by proving new theorems comparing the performance of A * toother (generalized) path finding algorithms. In some cases, A * is an optimalmethod in a large class of algorithms. This means, roughly speaking, that A*explores a smaller region of the search space than the other algorithms in the given class.We develop a new method of improving a given (static) heuristic for A*dynamically, during search. A heuristic controls the search of A * so thatunnecessary branches of the tree of nodes that A * visits are pruned. The newmethod also finds an optimal path to any node it visits for the first time s