Sensor-Based Planning with the Freespace Assumption

Sven Koenig and Y. Smirnov
Proceedings of the International Conference on Robotics and Automation (ICRA '97), 1997.


Download
  • Adobe portable document format (pdf) (212KB)
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(s) / Group(s): Reliable Autonomous Systems Lab
Associated Project(s): 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
Sven 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",
   Notes = "Leonard Schulman noticed that one of the examples in the original paper was buggy. This problem has been corrected in the on-line version."
}