New heuristic algorithms for efficient hierarchical path planning
- 1 February 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics and Automation
- Vol. 7 (1) , 9-20
- https://doi.org/10.1109/70.68066
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
This publication has 18 references indexed in Scilit:
- Computing metric and topological properties of configuration-space obstaclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Superquadric artificial potentials for obstacle avoidance and approachPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Multiresolution path planning for mobile robotsIEEE Journal on Robotics and Automation, 1986
- Real-Time Obstacle Avoidance for Manipulators and Mobile RobotsThe International Journal of Robotics Research, 1986
- Object level programming of industrial robotsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- A subdivision algorithm in configuration space for findpath with rotationIEEE Transactions on Systems, Man, and Cybernetics, 1985
- Object representation by means of nonminimal division quadtrees and octreesACM Transactions on Graphics, 1985
- Strategies for Solving Collision-free Trajectories Problems for Mobile and Manipulator RobotsThe International Journal of Robotics Research, 1984
- Oct-Tree Algorithms for Solid ModelingPublished by Springer Nature ,1983
- Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysisArtificial Intelligence, 1977