Controllability of Formations over Time-varying Graphs

Xudong Chen, Mohamed-Ali Belabbas, Tamer Başar

Abstract

In this paper, we investigate the controllability of a class of formation control systems. Given a directed graph, we assign an agent to each of its vertices and let the edges of the graph describe the information flow in the system. We relate the strongly connected components of this graph to the reachable set of the formation control system. Moreover, we show that the formation control model is approximately path-controllable over a path-connected, open dense subset as long as the graph is weakly connected and satisfies some mild assumption on the numbers of vertices of the strongly connected components.

Introduction

Formation control is a fundamental problem in multi-agent systems, where a group of agents must maintain specific geometric relationships while moving. While much of the existing literature focuses on undirected communication graphs, real-world applications often involve directed and time-varying links due to sensor limitations or environmental changes. This paper addresses the controllability of such systems, establishing topological requirements for a group of agents to reach any desired formation under directed, switching communication topologies.

Methodology

The study employs a combination of graph theory and differential geometry to analyze the system's dynamics. A central technique is the Strong Component Decomposition, where complex directed graphs are broken down into Strongly Connected Components (SCCs). These are clusters where every agent can eventually influence every other agent. The overall network is then simplified into a skeleton digraph, which illustrates the hierarchy of influence between these clusters.

Decomposition of a directed graph into strongly connected components and its corresponding skeleton digraph.

To prove controllability for these non-linear systems, the authors utilize the Lie Algebra Rank Condition (LARC). They demonstrate that the Lie algebra of zero row-sum matrices, which represents the formation dynamics, is directly linked to the transitive closure of the communication graph. This allows the complex control problem to be mapped onto a graph-topological problem.

Theoretical Insights

A key finding is that controllability is primarily dictated by the "maximal elements" of the skeleton digraph—the clusters with no outgoing edges to other clusters. These "leader" groups effectively drive the rest of the network. Furthermore, the authors identify the $n+1$ rule: for agents in $n$-dimensional space, each maximal SCC must contain more than $n+1$ agents to provide sufficient degrees of freedom for controllability.

Illustration of a directed graph and its transitive closure, representing the reachable movements in the formation control system.

The relationship between the reachable movements and the transitive closure of the graph (as shown above) provides a powerful tool for analyzing formation dynamics. This link ensures that the system remains controllable even as the graph topology switches over time, provided the connectivity requirements are met at each interval.

Key Results

The primary result is summarized in Theorem 1, which states that a formation is approximately path-controllable over an open dense subset of the configuration space if the graph is weakly connected and all maximal SCCs satisfy $|G_i| > n+1$. The "open dense subset" implies that the system is controllable almost everywhere, failing only in rare, degenerate configurations. This result is extended to switching graphs, confirming robustness under time-varying topologies.

Conclusion and Future Work

While the proposed model provides a robust framework for formation control, it inherently preserves the formation's centroid, meaning the group cannot move its center of mass without external signals. Future research will focus on developing explicit control laws for real-time implementation and optimizing the number of active edges to minimize communication overhead in large-scale swarms.

Summary updated

Abstract

In this paper, we investigate the controllability of a class of formation control systems. Given a directed graph, we assign an agent to each of its vertices and let the edges of the graph describe the information flow in the system. We relate the strongly connected components of this graph to the reachable set of the formation control system. Moreover, we show that the formation control model is approximately path-controllable over a path-connected, open dense subset as long as the graph is weakly connected and satisfies some mild assumption on the numbers of vertices of the strongly connected components.
BibTeX
@article{chen2017controllability,
  author = {Xudong Chen and Mohamed-Ali Belabbas and Tamer Başar},
  title = {{Controllability of Formations over Time-varying Graphs}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2017},
  doi = {10.1109/tcns.2015.2504034},
}
Figure