Extensions and Applications of the Algorithm

Reference:

Antti Autere. Extensions and applications of the algorithm. Research Report A98, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, November 2005. Doctoral dissertation.

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 algorithm.

We begin by proving new theorems comparing the performance of to other (generalized) path finding algorithms. In some cases, is an optimal method in a large class of algorithms. This means, roughly speaking, that 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 dynamically, during search. A heuristic controls the search of so that unnecessary branches of the tree of nodes that 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 as a higher level method to allocate resources among several path finding algorithms. In some cases, the 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 , 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 algorithm.

Keywords:

path finding, heuristic algorithms, best-first search, , resource allocation, robotics, motion planning, message routing

Suggested BibTeX entry:

@techreport{HUT-TCS-A98,
    address = {Espoo, Finland},
    author = {Antti Autere},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {November},
    note = {Doctoral dissertation},
    number = {A98},
    pages = {130},
    title = {Extensions and Applications of the {$A^*$} Algorithm},
    type = {Research Report},
    year = {2005},
}