Extensions and applications of the A* algorithm

Abstract

In this thesis we investigate path finding problems, that is, planning 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 minimum cost path using the A* algorithm.

We begin by proving new theorems comparing the performance of A* to other (generalized) path finding algorithms. In some cases, A* is an optimal method 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 that unnecessary branches of the tree of nodes that A* visits are pruned. The new method also finds an optimal path to any node it visits for the first time so that every node will be visited only once. The latter is an important property considering the efficiency of the search.

We examine the use of A* as a higher level method to allocate resources among several path finding algorithms. In some cases, the A* is an optimal resource allocation method, which means that the number of the nodes the path finding algorithms together visit is minimized.

As applications of A*, we have developed new hierarchical algorithms for robot point-to-point path planning tasks, and new algorithms for power-aware routing of messages in large communication networks. The new algorithms are more robust than some older ones to which we compare. Moreover, one of the message routing algorithms produces higher average lifetimes of the network than those of the widely quoted max-min zPmin algorithm.