Formation Control of Multi-Agent Systems via Voronoi Tessellation and Kullback-Leiber Divergence

Abstract

Recent advancements in communication technology, computational power, and control theory have led to the adoption of multi-agent systems in various engineering applications. By utilizing multiple agents, these systems can accomplish complex cooperative tasks that are difficult for a single agent to achieve, such as coordinated patrolling, surveillance, post-disaster search and rescue, and transportation logistics. Moreover, multi-agent systems have been employed to model and analyze flocking behaviour in both social and natural phenomena, including pedestrian flow, animal migration and hunting.

This thesis presents an algorithm to control the spatial distribution of kinematic multi-agent systems in two-dimensional workspaces. Leveraging on the coverage control framework, the problem is formulated as a multi-objective optimization with performance index composed of the area coverage metric and of the Kullback–Leibler (KL) divergence. The KL term drives the statistical spatial distribution of the agents to a desired, user-defined density in the workspace, whereas the coverage term drives the agents to a centroidal Voronoi configuration. The connection is the target distribution in the KL term, which is also the risk density in the area coverage term.

Since the system is non-autonomous due to the drift introduced by the evolving target density, the asymptotic stability is established by using Barbalat's lemma. The agents are proven to asymptotically converge to the trajectories of the time-varying stationary points of the multi-objective performance index, which monotonically minimizes the index, and drives the agents to evolve in a special centroidal Voronoi configuration of the same statistics as the target density. The collision avoidance of the agents between each other is guaranteed based on the inherent properties of the centroidal Voronoi tessellation. Furthermore, by designing the target density via its elliptical contour, the converged KL term drives the agents in a specified range, which allows the agents to accurately pass through confined environments, such as tunnels or pipelines. Theoretical predictions are illustrated in simulations.