Research Seminar - March 11, 1998

Abstract

We consider the navigation problem of a robot from a starting point S to a target point T inside an unknown rectilinear polygon. We measure the performance of the robot by comparing the path-length generated by the robot (RP) to the length of the shortest path (SP). If RP <= c * SP, for some c, we say that the corresponding strategy achieves a competitive ratio of c. In our model, the robot does not know its coordinates, but it knows the directions of the points S and T. In addition to this, the robot has tactile sensors to determine its proximity to the walls of the polygonal environment. The robot does not have any global knowledge of the environment. We present a strategy with a competitive ratio f(d), where d is the distance between S and T and f(d) is an exponential function of d.

I will discuss the model, previous results in on-line (algorithmic) robot navigation and the significance of this strategy. I will not discuss any detailed proof. This is an unfinished work and the practical significance of the model is yet to be justified.