Optimal deterministic protocols for mobile robots on a grid

A Multi Robot Grid System consists of m robots that operate in a set of n ≥ m work locations connected by aisles in a √n × √n grid. From time to time the robots need move along the aisles, in order to visit disjoint sets of locations. The movement of the robots must comply with the following constraints: (1) no two robots can collide at a grid node or traverse an 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 an efficient deterministic protocol that allows m=θ (n) robots to visit their target destinations in O (√dn) time, where each robot visits at most d ≤ n targets in any order. We also prove a lower bound that shows 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=O (√n), while for m=O (n) only a randomized suboptimal protocol was known.