DocumentCode :
1385517
Title :
New heuristic algorithms for efficient hierarchical path planning
Author :
Zhu, David ; Latombe, Jean-Claude
Author_Institution :
Dept. of Comput. Sci., Stanford Univ., CA, USA
Volume :
7
Issue :
1
fYear :
1991
fDate :
2/1/1991 12:00:00 AM
Firstpage :
9
Lastpage :
20
Abstract :
The authors consider one of the most popular approaches to path planning: hierarchical approximate cell decomposition. This approach consists of constructing successive decompositions of the robot´s configuration space into rectangloid cells and searching the connectivity graph built at each level of decomposition for a path. Despite its conceptual simplicity, an efficient implementation of this approach raises many delicate questions that have not yet been addressed. The major contributions this work are (1) a novel approach to cell decomposition based on constraint reformulation and (2) a new algorithm for hierarchical search with a mechanism for recording failure conditions. These algorithms have been implemented in a path planner, and experiments with this planner have been carried out on various examples. These experiments show that the proposed planner is significantly (approximately 10 times) faster than previous planners based on the same general approach
Keywords :
graph theory; optimisation; planning (artificial intelligence); robots; cell decomposition; connectivity graph; heuristic algorithms; hierarchical path planning; hierarchical search; rectangloid cells; robots; Automatic control; Computational Intelligence Society; Computer science; Heuristic algorithms; Humans; Motion planning; Orbital robotics; Path planning; Robotics and automation; Robots;
fLanguage :
English
Journal_Title :
Robotics and Automation, IEEE Transactions on
Publisher :
ieee
ISSN :
1042-296X
Type :
jour
DOI :
10.1109/70.68066
Filename :
68066
Link To Document :
بازگشت