A self-organizing distributed algorithm to tackle the stochastic coverage problem

Achieving coverage of a mission plane using large-scale rigid drone formations through the use of multi-agent algorithms like linear consensus subsumes a large communication cost. Even though the algorithm itself only requires local communication with neighboring agents, whenever the formation changes, new consensus matrices have to be found in a distributed manner. In this paper, rather than a strict relationship between agents, we assume that the goal is specified as a coverage problem with some known average occupation over time. The proposed solution encompasses three stages: (i) an optimization step that improves the used Markov matrix by doing a distributed ADMM step; (ii) a waypoint generation using the local component of the Markov matrix found in (i); (iii) lastly, a local controller drives the drone to the next waypoint. The aforementioned strategy has some interesting properties, namely: (a) communication is only required for step (i) which can be executed at a much lower frequency; (b) since steps (ii) and (iii) are purely decentralized and based on Markov chains, the method is self-organizing meaning that it copes easily with drones entering and leaving the network; (c) fast convergence to a steady state distribution of the drones in the space that matches the desired stochastic coverage. The method is then tested in simulation and shown to exhibit fast convergence of the drones to the desired formation goal. • Decentralized solution suitable for large-scale systems using Markov Chains. • Probabilistic guidance with optimized convergence rate written as an SDP. • Optimization based on ADMM written for each map partition. • The algorithm is self-healing and adapts to nodes entering and leaving the network.