Strategies for parallel unaware cleaners

We investigate the parallel traversal of a graph with multiple robots unaware of each other. All robots traverse the graph in parallel forever and the goal is to minimize the time needed until the last node is visited (first visit time) and the time between revisits of a node (revisit time). We also want to minimize the visit time, i.e. the maximum of the first visit time and the time between revisits of a node. We present randomized algorithms for uncoordinated robots, which can compete with the optimal coordinated traversal by a small factor, the so-called competitive ratio.For any number of robots ring and path graph simple traversal strategies allow constant competitive factors even in the worst case. For grid and torus graphs with n   nodes and any number of robots there is an O(log⁡n)O(log⁡n)-competitive algorithm for both visit problems succeeding with high probability, i.e. with probability 1−n−O(1)1−n−O(1). For general graphs we present an O(log2⁡n)O(log2⁡n)-competitive algorithm for the first visit problem, while for the visit problem we show an O(log3⁡n)O(log3⁡n)-competitive algorithm both succeeding with high probability.