TY - GEN

T1 - Navigating in Unfamiliar Geometric Terrain

AU - Blum, Avrim

AU - Raghavan, Prabhakar

AU - Schieber, Baruch

N1 - Publisher Copyright:
© 1991 ACM.

PY - 1991/1/3

Y1 - 1991/1/3

N2 - 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 and analyze robot strategies that minimize this ratio for different kinds of scenes. In particular, we consider the cases of rectangular obstacles aligned with the axes, rectangular obstacles in more general orientations, and wider classes of convex bodies both in two and three dimensions. We study scenes with non-convex obstacles, which are related to the study of maze-Traversal. We also show scenes where randomized algorithms.

AB - 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 and analyze robot strategies that minimize this ratio for different kinds of scenes. In particular, we consider the cases of rectangular obstacles aligned with the axes, rectangular obstacles in more general orientations, and wider classes of convex bodies both in two and three dimensions. We study scenes with non-convex obstacles, which are related to the study of maze-Traversal. We also show scenes where randomized algorithms.

UR - http://www.scopus.com/inward/record.url?scp=84981460967&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84981460967&partnerID=8YFLogxK

U2 - 10.1145/103418.103419

DO - 10.1145/103418.103419

M3 - Conference contribution

AN - SCOPUS:84981460967

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 494

EP - 504

BT - Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991

PB - Association for Computing Machinery

T2 - 23rd Annual ACM Symposium on Theory of Computing, STOC 1991

Y2 - 5 May 1991 through 8 May 1991

ER -