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 × 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(√logn). 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 Ω(n log n), even if it uses visual information.