Optimal deterministic protocols for mobile robots on a grid

This paper studies a system of m robots operating in a set of n work locations connected by aisles in a √n×√n grid, wherem ≤ n. From time to time the robots need to move along the aisles, in order to visit disjoint sets of locations. Themovement of the robots must comply with the following constraints: (1) no two robots can collide at a grid node or traverse a grid edge at the same time; (2) a robot’s sensory capability is limited to detecting the presence of another robot at a neighboring node.We present a deterministic protocol that, for any small constant > 0, allows m ≤ (1−)n robots to visit their target locations in O(√dn) time, where each robot visits no more than d ≤ n targets and no target is visited by more than one robot. We also prove a lower bound showing that our protocol is optimal. Prior to this paper, no optimal protocols were known for d > 1. For d = 1, optimal protocols were known only for m ≤ √n, while for generalm ≤ n only a suboptimal randomized protocolwas known.