Graphics enhanced version of this site

Framed-Quadtree Path Planning for Mobile Robots Operating in Sparse Environments
A. Yahja, A. Stentz, S. Singh, and B. Brummit
In Proceedings, IEEE Conference on Robotics and Automation, (ICRA), Leuven, Belgium, May, 1998.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [170 KB]
Compressed postscript (ps.gz) [359 KB]

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.

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

Associated centers: SRI and FRC
Associated project: Mars Autonomy

A. Yahja, A. Stentz, S. Singh, and B. Brummit, "Framed-Quadtree Path Planning for Mobile Robots Operating in Sparse Environments," In Proceedings, IEEE Conference on Robotics and Automation, (ICRA), Leuven, Belgium, May, 1998.

@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)",
   month = "May",
   year = "1998",
   address = "Leuven, Belgium"
}