Robot mapping: Foot-prints VS tokens

We are interested in the problem of robot exploration from the approach of competitive analysis, where the cost of an online-strategy is compared with the minimum cost carrying out the same task with perfect information. Our world model is restricted to graph maps. Within this model, there are several differences dealing with different robot sensors. Most often robots are assumed to have perfect vision. In this paper, however, we consider two different sensors: tokens and foot-prints. For the former, robots cannot recognize nodes or edges of the unknown graph under exploration but can drop some tokens which can be recognized if it returns to nodes where tokens are dropped. In the latter case, the robot has the power of knowing whether a node or an edge has been visited before, though it may not remember exactly when and where it was visited (similar to a traveler lost in the desert who recognizes its foot-print, or a robot smells its own trace). With competitive analysis, we want to minimize the ratio of the total number of edges traversed for mapping the graph divided by the optimum number of edge traversais for verifying the map. In particular, we call a strategy competitive if this ratio is constant. As a first step, we have developed a competitive strategy to map an unknown embedded planar graph with pure foot-prints. Then we apply this technique to obtain an algorithm using nidentical tokens to competitively map unknown planar embedded graphs. We also give a lower bound of competitive ratio Ω(n) for mapping general embedded graphs with a single token, when robot strategies are slightly restricted. This is tight since there is an algorithm of competitive ratio O(n) [DJMW]. © Springer-Verlag Berlin Heidelberg 1993.