Sensor-based terrain acquisition: the `sightseer´ strategy

Concerns a special case of the problem of robot motion planning, in which a mobile robot is required to build a complete map of an unfamiliar scene populated with a finite number of unknown objects (obstacles). The robot has a sort of sensory feedback equivalent to stereo vision or a range finder, and is expected to generate a reasonably short path during the operation. The terrain acquisition problem is formulated as that of continuous motion planning, and an algorithm that allows obstacles to be of arbitrary shape is presented. The upper bound on the algorithm´s performance is estimated in terms of the length of the generated paths and is shown to be linear in the perimeters of the obstacles in the scene