Framed-Quadtree Path Planning for Mobile Robots Operating in Sparse Environments

Alex Yahja, Anthony (Tony) Stentz, Sanjiv Singh, and Barry Brummit
In Proceedings, IEEE Conference on Robotics and Automation, (ICRA), May, 1998.


Download
  • Adobe portable document format (pdf) (170KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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. advantage of discretization is that the computational com-plexity

Notes
Associated Center(s) / Consortia: Space Robotics Initiative and Field Robotics Center
Associated Project(s): Mars Autonomy

Text Reference
Alex Yahja, Anthony (Tony) Stentz, Sanjiv Singh, and Barry Brummit, "Framed-Quadtree Path Planning for Mobile Robots Operating in Sparse Environments," In Proceedings, IEEE Conference on Robotics and Automation, (ICRA), May, 1998.

BibTeX Reference
@inproceedings{Yahja_1998_2100,
   author = "Alex Yahja and Anthony (Tony) Stentz and Sanjiv Singh and Barry Brummit",
   title = "Framed-Quadtree Path Planning for Mobile Robots Operating in Sparse Environments",
   booktitle = "In Proceedings, IEEE Conference on Robotics and Automation, (ICRA)",
   address = "Leuven, Belgium",
   month = "May",
   year = "1998",
}