Dec-PPCPP: A Decentralized Predator–Prey-based Approach to Adaptive Coverage Path Planning Amid Moving Obstacles

Abstract

Enabling multiple robots to collaboratively per-form coverage path planning on complex surfaces embedded in {{\mathbb{R}}^3}{{\mathbb{R}}^3} in the presence of moving obstacles is a challenging problem that has not received much attention from researchers. As robots start to be practically deployed, it is becoming important to address this problem. A novel decentralized multi-robot coverage path planning approach is proposed that is adaptive to unexpected stationary and moving obstacles while aiming to achieve complete coverage with minimal cost. The approach is inspired by the predator-prey relation. For a robot (a prey), a virtual stationary predator enforces spatial ordering on the prey, and dynamic predators (other robots) cause the prey to be repelled resulting in better task allocation and collision-avoidance. The approach makes the best use of both worlds: offline global planning for tuning of model parameters based on a prior map of the surface, and real-time local planning for adaptive and swift decision making amid moving obstacles and other robots while preserving global behavior. Comparisons with other approaches and extensive testing and validation using different number of robots, different surfaces and obstacles, and various scenarios are conducted.