The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
|
|
|
Extensions and Applications of the A* Algorithm
Antti Autere
Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Department of Computer Science and Engineering for public examination and debate in Auditorium T2 at Helsinki University of Technology (Espoo, Finland) on the 16th of December, 2005, at 12 o'clock noon.
Dissertation in PDF format (ISBN 951-22-7948-7) [1142 KB]
Dissertation is also available in print (ISBN 951-22-7947-9)
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.
Keywords: path finding, heuristic algorithms, best-first search, A*, resource allocation, robotics, motion planning, message routing
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
© 2005 Helsinki University of Technology
Last update 2011-05-26