ONLINE NAVIGATION IN A ROOM

We consider the problem of navigating through an unknown environment in which the obstacles are disjoint oriented rectangles enclosed in an n x n square room. The task of a navigating algorithm is to reach the center of the room starting from one of the corners. While there always exists a path of length n, the best previously known navigating algorithm finds paths of length n2(o)(square-root log n). We give an efficient deterministic algorithm which finds a path of length O(n log n); this algorithm uses tactile information only. Moreover, we prove that any deterministic algorithm can be forced to traverse a distance of OMEGA(n log n), even if it uses visual information. (C) 1994 Academic Press, Inc.