Extensions and applications of the A* algorithm

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Autere, Antti
dc.date.accessioned 2012-02-17T07:25:50Z
dc.date.available 2012-02-17T07:25:50Z
dc.date.issued 2005-12-16
dc.identifier.isbn 951-22-7948-7
dc.identifier.issn 1457-7615
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/2647
dc.description.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. en
dc.format.extent 120
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Helsinki University of Technology en
dc.publisher Teknillinen korkeakoulu fi
dc.relation.ispartofseries Helsinki University of Technology, Laboratory for Theoretical Computer Science. A, Research reports en
dc.relation.ispartofseries Teknillisen korkeakoulun tietojenkäsittelyteorian laboratorion tutkimusraportti. A fi
dc.relation.ispartofseries 98 en
dc.subject.other Computer science en
dc.title Extensions and applications of the A* algorithm en
dc.type G4 Monografiaväitöskirja fi
dc.description.version reviewed en
dc.contributor.department Department of Computer Science and Engineering en
dc.contributor.department Tietotekniikan osasto fi
dc.subject.keyword path finding en
dc.subject.keyword heuristic algorithms en
dc.subject.keyword best-first search en
dc.subject.keyword A* en
dc.subject.keyword resource allocation en
dc.subject.keyword robotics en
dc.subject.keyword motion planning en
dc.subject.keyword message routing en
dc.identifier.urn urn:nbn:fi:tkk-006078
dc.type.dcmitype text en
dc.type.ontasot Väitöskirja (monografia) fi
dc.type.ontasot Doctoral dissertation (monograph) en
dc.contributor.lab Laboratory for Theoretical Computer Science en
dc.contributor.lab Tietojenkäsittelyteorian laboratorio fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account