Imagine large vehicular formations that need to travel in unison, something that resembles a
rigid lattice or grid of objects. In nature, such formations are found in e.g. birds flying
in formation or fish schooling together. One can also think of swarms of autonomous artificial vehicles
attempting to form a rigid grid-like formation.
The Geese shown above in effect form a 1-dimensional “string formation”. The picture in the middle
is a caricature of a 2-dimensional artificial vehicle formation. Schools of fish appear to be 3-dimensional
formations. If you've seen videos of such formations on something like the Discovery Channel,
you probably
have observed that fish schools appear to swim in much tighter formations than the somewhat
meandering string
formations of Geese. In other words, fish schools are more “coherent” than Geese formations, and
it turns out
that this is a fundamental pattern. 3-dimensional formations are more coherent than 1-dimensional
ones when
agents can only use local feedback to control their relative motion.
It is also intuitively clear that the larger
the formation is, the less likely it is to be coherent.
These observations raise several
questions:
How does one quantify “coherence”, i.e. how closely does a formation resemble a rigid lattice?
This is a sort of macroscopic performance measures.
How does one capture the local behavior of vehicles, such as the tendency to run into each other?
This is a sort of microscopic performance measures.
How do these measures scale with formation size, and how do they depend on the network topology?
How does all this depend on whether vehicles have local feedback versus global feedback of things
like position errors and velocity errors?
The answers to these questions are provided in the paper below. It turns out that
a common
phenomenon appears where a higher spatial dimension implies a more favorable
scaling of coherence measures, with a dimensions of 3 being necessary to achieve
coherence in consensus and vehicular formations under certain conditions.
One way to think about these results is in terms of network controllability. Certain network topologies (like the one dimensional platoon formation discussed below) are inherently difficult to control. This is quantified using bounds on the best achievable closed-loop performance under topological constraints on the network feedback laws.
Worst-case Topology: Vehicular Strings (Platoons)
The situation is worst in one dimension, e.g. in the so-called Vehicular Platoons problem. It turns out
that it is
impossible to have large coherent 1-dimensional vehicular platoons with only local feedback.
Consider a simple
control scheme for a toy platooning problem as shown to the left.
The red arrows indicated stochastic forcing disturbances buffeting each vehicle. A simple control scheme
based on look-ahead and look-behind policies can be easily designed to stabilize the entire formation
(and avoid the so-called string instability problem, which incidentally is unrelated to the phenomenon
we discuss here).
However, if you simulate the system, here's what you observe. The graph on the right
shows the position trajectories of a 100
vehicle formation (relative to leader). It exhibits what can be
described as an accordion-like motion in which large shape features in the formation fluctuate.
We call this phenomenon a lack of formation coherence.
It is only
discernible when one “zooms out” to view the entire formation.
The length of the formation
fluctuates stochastically, but with a distinct slow temporal and long spatial wavelength signature.
In contrast,
the zoomed-in view here shows a relatively well regulated vehicle-to-vehicle
spacing. In general, it appears that small scale (both temporally and spatially) disturbances are
well regulated, while large scale disturbances are not. An intuitive interpretation of
this phenomenon
is that local feedback strategies are unable to regulate against large scale disturbances
in this one
dimensional formation. This is an example of the lack of coherence in this formation.
Higher-dimensional Topologies
Lattices and Tori
What is perhaps surprising is that in higher spatial dimensions, it is indeed possible to have
coherent formations
with only local feedback. This table summarizes the asymptotic upper and lower bounds of
microscopic error measures,
and macroscopic measures of formation cohesion under various types of feedback controls.
is the network size and is a bound on
the control effort at each site.
Fractal Networks
For more general networks, a natural question is whether there is a purely topological quantity that captures the scalings of coherence measures. A natural candidate is the Hausdorff dimension, which for example is well defined for fractal networks. The table above shows calculations for some special cases. The Peano Basin fractal network case shows that the Hausdorff dimension does not capture the asymptotics. The Peano Basin has same dimension as the 2d lattice, but coherence scales differently! Finding a purely topological quantifier for coherence scalings is still an open question.