Counting Critical Formations on a Line

Abstract

Formation shape control for a collection of point agents is concerned with devising decentralized control laws which ensure that the formation will move so that certain interagent distances approximate prescribed values as closely as possible. Such laws are often derived using steepest descent of a potential function which is invariant under translation and rotation, and then critical formations are those that are fixed under the evolution of the decentralized control dynamics, i.e., those corresponding to equilibrium points of the control dynamics. Using a specific and frequently used potential function for formation control, this paper introduces tools from Morse theory and complex algebraic geometry to estimate the number of critical formations of N agents on a line. We show that there are at least 2N - 1 equilibrium points and at most 3 N-1 isolated equilibria. Moreover, bounds on the number of equilibrium points with a k-dimensional stable manifold (the socalled Morse-index) are established. We show that generically there are exactly five critical formations for three agents on a line, and exactly 27 complex critical formations for four agents on a line, where a complex critical formation is defined as an equilibrium point of the gradient flow with complex, not necessarily real, coordinates. Except for a single critical formation, no two or more of the agents in the other 26 critical formations are collocated.