Network Controllability & Network Topology

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.


Original video: YouTube

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)

main 

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).

main 

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.

main 

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

main 

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. N is the network size and U is a bound on the control effort at each site.

Fractal Networks

main 

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.

Related Papers

Related Talks