Planning Multi-Agent Inspection Tours With Energy Constraints and Separation Requirements

Abstract

We present a tractable approach to grid-based multi-agent path planning for inspection tasks that minimizes task completion time. We require all agents to collectively inspect all targets while (i) maintaining a user-defined separation distance, (ii) returning to charging stations as needed, and (iii) avoiding obstacles. We decompose the constraints into per-agent constraints and team-level constraints, and propose a tour-based formulation where each tour satisfies per-agent constraints. We also introduce a notion of separation boxes which allows enforcing inter-agent separation constraints without costly pairwise distance evaluation. Numerical experiments show that the proposed algorithm can efficiently solve the grid-based planning problem compared with a baseline MILP formulation. Drone-based physical experiments further demonstrate integration of the resulting high-level discrete plans with off-the-shelf controllers via waypoint tracking.