RI | Publications | Sensor-Based Planning with the Freespace Assumption

Text only version of this site

Sensor-Based Planning with the Freespace Assumption
S. Koenig and Y. Smirnov
Proceedings of the International Conference on Robotics and Automation (ICRA '97), 1997.

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

Download [Help]

Adobe portable document format (pdf) [211 KB]
Compressed postscript (ps.gz) [74 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.

Abstract

A popular technique for getting to a goal location in unknown terrain is planning with the freespace assumption. The robot assumes that the terrain is clear unless it knows otherwise. It always plans a shortest path to the goal location and re-plans whenever it detects an obstacle that blocks its path or, more generally, when it detects that its current path is no longer optimal. It has been unknown whether this sensor-based planning approach is worst-case optimal, given the lack of initial knowledge about the terrain. We demonstrate that planning with the freespace assumption can make good performance guarantees on some restricted graph topologies (such as grids) but is not worst-case optimal in general. For situations in which its performance guarantee is insufficient, we also describe an algorithm, called Basic-VECA, that exhibits good average-case performance and provides performance guarantees that are optimal up to a constant (user-defined) factor.

Notes

Associated lab/group: Reliable Autonomous Systems Lab
Associated project: Xavier

Note: Leonard Schulman noticed that one of the examples in the original paper was buggy. This problem has been corrected in the on-line version.

Text Reference

S. Koenig and Y. Smirnov, "Sensor-Based Planning with the Freespace Assumption," Proceedings of the International Conference on Robotics and Automation (ICRA '97), 1997.

BibTeX Reference

@inproceedings{Koenig_1997_3860,
   author = "Sven Koenig and Y. Smirnov",
   title = "Sensor-Based Planning with the Freespace Assumption",
   booktitle = "Proceedings of the International Conference on Robotics and Automation (ICRA '97)",
   year = "1997",
   note = "Leonard Schulman noticed that one of the examples in the original paper was buggy. This problem has been corrected in the on-line version."
}