COMPETITIVE ROBOT MAPPING WITH HOMOGENEOUS MARKERS

We consider the robot exploration problem of graph maps with homogeneo us markers, following the graph world model introduced by Dudek et al. [10], The environment Is a graph consisting of nodes and edges, where the robot can navigate from one node to another through an edge conne cting these two nodes, However, the robot may not distinguish one node (or edge) from another in this unknown graph, All the nodes (edges) l ook the same, However, at each node, the robot can observe a consisten t local relative orientation of its incident edges, that is, a cyclic order of edges incident to the node, To assist the robot's task of map ping the environment, it can put homogeneous (i.e., identical) marks o n nodes or edges which can be recognized later. The total number of ed ges traversed when constructing a map of the graph is often used as a performance measure for robot strategies, However, since the graph is unknown, a strategy may be efficient in one situation but not in other s. Thus, there is a conceptual question about what is an optimal strat egy, In this paper, we apply the competitive analysis method [5], [23] , [25] for robot explorations, In particular, we compare the cost for constructing a map with the cost for verifying the same map and call t heir ratio by competitive ratio, an approach initially applied to a si milar mapping problem by Deng and Papadimitriou [12], That is, we call a strategy optimal if it minimizes the worst-case ratio (over all all owable embedded graphs) of the total number of edges traversed when co nstructing a map of the graph to the optimum number of edges traversed in verifying the correctness of a given map of the same graph, If thi s competitive ratio is bounded above by a constant, we say the strateg y is competitive, One of the main results of this paper is to show tha t a competitive strategy exists for mapping planar embedded graphs whe n the robot has n homogeneous markers at its disposal (throughout the paper n denotes the number of vertices and m denotes the number of edg es of the unknown graph), We also show that in some alternative situat ions no competitive strategy exists.