Competitive robot mapping with homogeneous markers

We consider the robot exploration problem of graph maps with homogeneous markers. The graph consists of nodes and edges, where the robot can navigate from one node to another through an edge connecting these two nodes. However, the robot may not distinguish one node (or edge) from another in the unknown graph. All the nodes (edges) look the same. However, at each node, the robot can observe a consistent 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 mapping the environment, it can put homogeneous marks on nodes or edges which can be recognized later. The total number of edges 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 others. Thus, there is a conceptual question about what is an optimal strategy. In this paper, we apply the competitive analysis method for robot explorations. In particular, we compare the cost for constructing a map with the cost for verifying the same map; their ratio is the competitive ratio. A strategy is optimal if it minimizes the worst-case ratio of the total number of edges traversed when constructing 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 this competitive ratio is bounded above by a constant, we say the strategy is competitive