Control of Multi-Agent Systems Using Time-Varying Density Functions

In this project, optimal coverage ideas are used to control a multi-agent system. In optimal coverage, we are concerned with finding the algorithm that will drive the agents to position themselves in ‘best’ locations, when given a certain density function that represents spatial ‘importance’. For example, this density function may be a probability density function of an event of interest over a domain. Under the algorithm, the agents are to place themselves at locations that are close to area with high probabilities.

A density function and multiple agents (in colored dots).

We use this idea of agents covering the density function to control a system of multiple agents. More specifically, we specify a time-varying density function as an input to multi-agent system. This time-varying density function can represent some time-evolving phenomenon. It may be the probability of a lost person being present in a region over time, or it can be a description of oil spill over time. Otherwise, it may just represent where we want the agents to be at each time. The agents are guided by the time-varying density function to be where we want them to be at each time. To enable this idea, we developed an optimal coverage algorithm for general time-varying density functions. Other algorithms for optimal coverage with time-varying density functions existed before, but relied on assumptions that do not hold in general. We proposed an algorithm that guarantees optimal coverage of the density function provided that the agents start from a favorable initial setup. This can be easily achieved by holding the density function constant in the beginning and running well-known algorithms for time-invariant algorithms (such as Lloyd’s algorithm). Simulations and robot experiments were conducted to verify the approach.

Three robots performing optimal coverage of a specified time-varying density function (shown in red). The robots have a colored arrow associated that marks its position and orientation.


Sung G. Lee Magnus Egerstedt



S.G. Lee and M. Egerstedt, Controlled Coverage Using Time-Varying Density FunctionsIFAC Workshop on Estimation and Control of Networked Systems, Koblenz, Germany, Sept. 2013.

Comments are closed.