Necessary and Sufficient Graphical Conditions for Affine Formation Control

Abstract

This paper introduces a new multi-agent control problem, called an affine formation control problem, with the objective of asymptotically reaching a configuration that preserves collinearity and ratios of distances with respect to a target configuration. Suppose each agent updates its own state using a weighted sum of its neighbor's relative states with possibly negative weights. Then the affine control problem can be solved for either undirected or directed interaction graphs. It is shown in this paper that an affine formation is stabilizable over an undirected graph if and only if the undirected graph is universally rigid, while an affine formation is stabilizable over a directed graph in the d-dimensional space if and only if the directed graph is (d + 1)-rooted. Rigorous analysis is provided, mainly relying on Laplacian associated with the interaction graph, which contain both positive and negative weights.