Voronoi Based Deployment for Multi-Agent Systems
Abstract
This thesis investigates convergence in the framework of Voronoi-based deployment of a multi-agent system to a convex polytopic multi-dimensional environment. The deployment objective is to drive the system into a stable static configuration which exhibits optimal coverage of the target environment. To this end, the system is subjected to a collection of decentralized control laws steering each agent towards a Chebyshev center of its associated time-varying polytopic Voronoi-neighborhood. In non-degenerate cases, so-called Chebyshev configurations of the multi-agent system achieves the above objective. In these configurations, all agents are at a Chebyshev center of their Voronoi-neighborhood. Proving convergence to the set of Chebyshev configurations is an open research question. This is the most pertinent issue with regards to the framework viability. While such a property is supported by simulations, neither complete formal convergence proofs nor formal characterizations of the equilibria to be achieved exist. This thesis is oriented towards strengthening the theoretical convergence results. For the special case of deployment to one-dimensional environments, we prove convergence to an unique static Chebyshev configuration. Moreover, we highlight connections to discrete time averaging systems and show how the system converges to consensus on the Chebyshev radii. The remaining results apply in the general case of multi-dimensional environments. We introduce a novel undirected interaction graph as a theoretical tool for a deeper understanding of the multi-agent system's functioning. Exploiting this graph, we prove that the set of static configurations are Chebyshev configurations in which all subsets of agents within the same connected component of the interaction graph are in consensus on their Chebyshev radii. Finally we prove convergence to a Chebyshev configuration, with consensus on the Chebyshev radii, provided the interaction graph is connected along the trajectories of the multi-agent system. Throughout the presentation, the theoretical results are motivated and supported by simulations.