Extensions and applications of the A* algorithm

Thumbnail Image

Files

isbn9512279487.pdf (1.09 MB)

URL

Journal Title

Journal ISSN

Volume Title

Doctoral thesis (monograph)
Checking the digitized thesis and permission for publishing
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2005-12-16

Department

Department of Computer Science and Engineering
Tietotekniikan osasto

Major/Subject

Mcode

Degree programme

Language

en

Pages

120

Series

Helsinki University of Technology, Laboratory for Theoretical Computer Science. A, Research reports, Teknillisen korkeakoulun tietojenkäsittelyteorian laboratorion tutkimusraportti. A, 98

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.

Description

Keywords

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

Other note

Citation

Permanent link to this item

https://urn.fi/urn:nbn:fi:tkk-006078

Collections

[diss] Perustieteiden korkeakoulu / SCI