TR018: New Heuristic Algorithms for Efficient Hierarchical Path Planning
Abstract/Contents
- Abstract
- One of the ultimate goals of robotics research is to create autonomous robots. Progress toward this goal requires advances in many domains, including automatic motion planning. The "basic problem" in motion planning is to construct a collision-free path for a moving object among fixed obstacles. Several approaches have been proposed, including cell decomposition, retraction, and potential field. Nevertheless, most existing planners still lack efficiency, or reliability, or both. In this paper, we consider one of the most popular approaches to path planning: hierarchical approximate cell decomposition. We propose a set of new algorithms for constructing more efficient and reliable path planners based on this general approach. These algorithms concern the hierarchical decomposition of the robot's configuration space into rectangloid cells, and the search of the connectivity graphs built at each level of decomposition. We have implemented these algorithms in a path planner and experimented with this planner on various examples. Some are described in the paper. These experiments show that our planner is significantly faster than previous planners based on the same general approach.
Description
| Type of resource | text |
|---|---|
| Date created | August 1989 |
Creators/Contributors
| Author | Zhu, David |
|---|---|
| Author | Latombe, Jean-Claude |
Subjects
| Subject | CIFE |
|---|---|
| Subject | Center for Integrated Facility Engineering |
| Subject | Stanford University |
| Subject | Artificial Intelligence |
| Subject | Path Planning |
| Subject | Robot Motion Planning |
| Genre | Technical report |
Bibliographic information
| Related item | |
|---|---|
| Location | https://purl.stanford.edu/rt697vp3106 |
Access conditions
- Use and reproduction
- User agrees that, where applicable, content will not be used to identify or to otherwise infringe the privacy or confidentiality rights of individuals. Content distributed via the Stanford Digital Repository may be subject to additional license and use restrictions applied by the depositor.
Preferred citation
- Preferred Citation
- Zhu, David and Latombe, Jean-Claude. (1989). TR018: New Heuristic Algorithms for Efficient Hierarchical Path Planning. Stanford Digital Repository. Available at: http://purl.stanford.edu/rt697vp3106
Collection
CIFE Publications
Contact information
- Contact
- cife-email@stanford.edu
Loading usage metrics...