Distributed Coverage: From Deterministic to Probabilistic Models

For the multi-robot coverage problem determin- istic deliberative as well as probabilistic approaches have been proposed. Whereas deterministic approaches usually provide provable completeness and promise good performance under perfect conditions, probabilistic approaches are more robust to sensor and actuator noise, but completion cannot be guaranteed and performance is sub-optimal in terms of time to completion. In reality, however, almost all deterministic algorithms for robot coordination can be considered probabilistic when considering the unpredictability of real world factors. This paper investigates experimentally and analytically how probabilistic and deterministic algorithms can be combined for maintaining the robustness of probabilistic approaches, and explicitly model the reliability of a robotic platform. Using realistic simulation and data from real robot experiments, we study system performance of a swarm-robotic inspection system at different levels of noise (wheel-slip). The prediction error of a purely deterministic model increases when the assumption of perfect sensors and actuators is violated, whereas a combination of probabilistic and deterministic models provides a better match with experimental data.