HOW TO LEARN AN UNKNOWN ENVIRONMENT I - THE RECTILINEAR CASE

We consider the problem faced by a robot that must explore and learn a n unknown room with obstacles in it. We seek algorithms that achieve a bounded ratio of the worst-case distance traversed in order to see al l visible points of the environment (thus creating a map), divided by the optimum distance needed to verify the map, if we had it in the beg inning. The situation is complicated by the fact that the latter off-l ine problem (the problem of optimally verifying a map) is NP-hard. Alt hough we show that there is no such ''competitive'' algorithm for gene ral obstacle courses, we give a competitive algorithm for the case of a polygonal room with a bounded number of obstacles in it. We restrict ourselves to the rectilinear case, where each side of the obstacles a nd the room is parallel to one of the coordinates, and the robot must also move either parallel or perpendicular to the sides. (In a subsequ ent paper, we will discuss the extension to polygons of general shapes .) We also discuss the off-line problem for simple rectilinear polygon s and find an optimal solution (in the L-1 metric) in polynomial time, in the case where the entry and the exit are different points.