The BDD-Based Dynamic A* Algorithm for Real-Time Replanning

There are no files associated with this record.

Title The BDD-Based Dynamic A* Algorithm for Real-Time Replanning
Author Xu, Yanyan; Yue, Weiya; Su, Kaile
Publication Title Third International Workshop, FAW 2009, Frontiers in Algorithmics
Editor Xiaotie Deng, John E. Hopcroft , and Jinyun Xue
Year Published 2009
Place of publication United States
Publisher Springer
Abstract Finding optimal path through a graph efficiently is central to many problems, including route planning for a mobile robot. BDD-based incremental heuristic search method uses heuristics to focus their search and reuses BDD-based information from previous searches to find solutions to series of similar search problems much faster than solving each search problem from scratch. In this paper, we apply BDD-based incremental heuristic search to robot navigation in unknown terrain, including goal-directed navigation in unknown terrain and mapping of unknown terrain. The resulting BDD-based dynamic A* (BDDD*) algorithm is capable of planning paths in unknown, partially known and changing environments in an efficient, optimal, and complete manner. We present properties about BDDD* and demonstrate experimentally the advantages of combining BDD-based incremental and heuristic search for the applications studied. We believe that our experimental results will make BDD-based D* like replanning algorithms more popular and enable robotics researchers to adapt them to additional applications.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1007/978-3-642-02270-8_28
ISBN 978-3-642-02269-2
Conference name FAW 2009
Location Hefei, China
Date From 2009-06-20
Date To 2009-06-23
URI http://hdl.handle.net/10072/40044
Date Accessioned 2011-07-21
Language en_AU
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Artificial Intelligence and Image Processing
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1x

Show simple item record

Griffith University copyright notice