Sensor-Based Planning with the Freespace Assumption

Sven Koenig and Yury Smirnov

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 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 optimal in
general. For situations in which its performance guarantee is not
sufficient, 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 factor.