Navigating in unfamiliar geometric terrain
Avrim L. Blum, Prabhakar Raghavan, Baruch Schieber · 1991
Consider a robot that has to travel from a start location s to a target t in an environment with opaque obstacles that lie in its way.The robot always knows its current absolute position and that of the target.It does not, however, know the positions and extents of the obstacles in advance; rather, it finds out about obstacles as it encounters them.We compare the distance walked by the robot in going from .s to t to the length of the shortest path between s and t in the scene.We describe sbar]