Framed-quadtree path planning for mobile robots operating in sparse environments
- 27 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (10504729) , 650-655
- https://doi.org/10.1109/robot.1998.677046
Abstract
Mobile robots operating in vast outdoor unstructured environments often only have incomplete maps and must deal with new objects found during traversal. Path planning in such sparsely occupied regions must be incremental to accommodate new information, and, must use efficient representations. In previous work we have developed an optimal method D* to plan paths when the environment is not known ahead of time, but, rather is discovered as the robot moves around. To date, D* has been applied to a uniform grid representation for obstacles and free space. In this paper we propose the use of D* with framed quadtrees to improve the efficiency of planning paths in sparse environments. The new system has been tested in simulation as well on an autonomous jeep, equipped with local obstacle avoidance capabilities. We show how the use of framed quadtrees improves performance in terms of path length, computation speed, and memory requirements.Keywords
This publication has 10 references indexed in Scilit:
- Dynamic mission planning for multiple mobile robotsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimal and efficient path planning for partially-known environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Automatic assembly planning and control via potential functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Planning conditional shortest paths through an unknown environment: a framed-quadtree approachPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Intelligent Unmanned Ground VehiclesPublished by Springer Nature ,1997
- A complete navigation system for goal acquisition in unknown environmentsAutonomous Robots, 1995
- The applications of harmonic functions to roboticsJournal of Robotic Systems, 1993
- Real-time robot motion planning using rasterizing computer graphics hardwarePublished by Association for Computing Machinery (ACM) ,1990
- An Overview of Quadtrees, Octrees, and Related Hierarchical Data StructuresPublished by Springer Nature ,1988
- Neighbor finding techniques for images represented by quadtreesComputer Graphics and Image Processing, 1982