Learning to cooperate: Networks of formation agents with switching topologies

Motivated by the prototypical problem of a marching band, this paper studies a class of multi-agent formation problems characterized by two features: (i) the agents attempt to complete a finite duration, coordinated formation task with high precision by repeating the task and (ii) the feedback mechanism by which the agents control their motions is based on relative differences between nearest neighbors, but the underlying graph topology can vary both during a repetition and from one repetition to the next. Adopting the framework of iterative learning control leads to the notion of multi-agent networks with switching topologies along two directions: a finite time axis and an infinite iteration axis. For such systems, we present distributed algorithms using nearest neighbor information whose exponential convergence can be demonstrated. It is shown that as the number of repetition increases, the relative formation between agents approaches the desired formation exponentially fast if and only if at each time step, the union of the interaction graphs has a spanning tree frequently enough along the iteration axis. That is, the agents can “learn to cooperate.” The remarkable point of this result is that it is not necessary to have a spanning tree at any specific time step or iteration in order for the system to converge. Two examples are given to illustrate the ideas, including a general example, where through iteration the agents can form a desired formation, and a special case of it, where an additional agent specifies a reference to regulate the formation shape simultaneously.