Coverage control for nonholonomic agents

Consider a coverage problem for a team of agents in the plane: target points appear sporadically over time in a bounded environment and must be visited by one of the agents. It is desired to minimize the expected elapsed time between the appearance of a target point, and the instant it is visited. For holonomic agents, this reduces to a continuous facility location problem, well studied in the geometric optimization literature. In this paper, we consider a team of nonholonomic vehicles constrained to move with constant forward speed along paths of bounded curvature. We show that, in this case, the optimal policy depends on the density of vehicles in the environment. In low density scenarios, the optimal policy resembles that of holonomic agents: the environment is partitioned into subregions of dominance, and each vehicle is responsible for targets appearing in its own subregion (territorial behavior). As the density increases, the optimal policy exhibits a transition to a gregarious behavior in which the team loiters in a coordinated pattern, and each vehicle visits targets that appear immediately in front of it.