AN ON-LINE ALGORITHM FOR NAVIGATING IN AN UNKNOWN ENVIRONMENT

Abstract

Suppose that a robot is required to traverse a two-dimensional scene with impenetrable rectangular obstacles. The robot has no information about the obstacles in advance and the size, location, and orientation of each obstacle in the scene are arbitrary, yet the robot can see and move in any direction. In this paper we construct an on-line algorithm for the robot to determine an obstacle-free path to its destination dynamically. The primary concern for such on-line algorithm is the competitiveness coefficient which essentially compares the actual distance traversed to the length of the shortest path. We show that if the aspect ratio of every rectangular obstacle in the scene is bounded by a constant r, then our algorithm achieves the optimal competitiveness coefficient which is r/2+1.