Distributed coordination of a formation of heterogeneous agents with individual regrets and asynchronous communications

We consider a flotilla composed of N autonomous mobile agents. Each agent ignores its absolute position but collects noisy measurements of the relative position of other agents. It has a convex utility function which depends on its control variables and on some global variables, typically, the average motion of all agents during a unit of time. The utility function of an agent is unknown by other agents. The aim is to determine the control variables which minimize the sum of all utility functions. The minimization is subject to constraints: speed limitations, collision avoidance and maintenance of the flock. We provide sufficient convex and separable conditions which guarantee that constraints are satisfied. These conditions allow to search for a minimizer of the aggregate utility function in a distributed fashion. The proposed algorithm simultaneously involves a gradient descent locally performed by the agents and a random gossip step which allows to find an agreement on the global motion strategy. In the case when there is a large number of transmissions during each unit of time, the algorithm is proved to converge almost surely to the desired minimizer, under mild conditions on the gossip protocol. When transmissions become less frequent, the minimization problem is no longer likely to be solved exactly. However, we propose an adaptive algorithm capable of tracking the minimizer. Its behavior is characterized through detailed simulations.