Note: this project has been discontinued and superceded by the Multi-agent Coordination Simulator project.

Flocks, Mobs, Pins, and Figure Eights: Implementations of Popular Swarming Strategies (v.3.0)

This project implements several of the most popular swarming strategies.

Version 3.0 includes the following updates since previous version:

now includes pinning control
cleaned up file structure
added init.py for modules
adjusted some Saber flocking hyperparameters
improved lattice formation in animation module

Reynolds Flocking

Here we implement Reynolds Rules of Flocking (or Boids), which is based on a balance between three steering forces:

Cohesion: the tendency to steer towards the center of mass of neighbouring agents.
Alignment: the tendency to steer in the same direction as neighbouring agents.
Separation: the tendency to steer away from neighbouring agents.

Below is a demonstration of the technique, including an additional Navigation term to facilitate target tracking:

Source: Craig Reynolds, "Flocks, Herds, and Schools:A Distributed Behavioral Model", Computer Graphics, 21(4) (SIGGRAPH '87 Conference Proceedings), pages 25-34, 1987.

Olfati-Saber Flocking

Here we implement the 3-part distributed Olfati-Saber flocking formulation that involves the following terms:

Alpha-Alpha Interaction (alignment) - encourages the agents to align in a lattice formation. The function represents other vehicles as "alpha" agents.
Alpha-Beta Interaction (obstacle avoidance) - discourages the agents from colliding with obstacles. The function represents obstacles as "beta" agents.
Gamma Feedback (navigation) - encourages motion towards a static or dynamic target. The function represents the target as a "gamma" agent.

When compared to the Reynolds implementation above, this results in a more structured flock with many convenient mathematical properties:

Source: Reza Olfati-Saber, "Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory", IEEE Transactions on Automatic Control, Vol. 51 (3), 2006.

Starling Flocking

For more natural behavior, we model the roosting behaviour of starlings as follows:

Cohesion, Alignment, and Separation rules of Reynolds above.
Horizontal Roosting, which encourages all agents to steer towards a central location as a function of their heading and distance away.
Vertical Roosting, which encourages all agents to hover over a nest.

Below is a demonstration of this roosting:

Source: H. Hildenbrandt, C. Carere, and C.K. Hemelrijk,"Self-organized aerial displays of thousands of starlings: a model", Behavioral Ecology, Volume 21, Issue 6, pages 1349–1359, 2010.

Encirclement

Here we formulate overlapping planes of encirclement (using quaternions) to achieve dynamic encirclement:

Source: P. T. Jardine and S. N. Givigi, "Bimodal Dynamic Swarms", IEEE Access, vol. 10, pp. 94487-94495, 2022.

Dynamic Lemniscate

Inspired by the natural mobbing behavior of birds, here we present a quasi-distributed swarming strategy called the Dynamic Lemniscatic Arch. It resolves the problem of producing globally-stable, evenly-spaced lemniscate (or, figure-eight) trajectories while relying on local interactions only.

Source: P. T. Jardine and S. N. Givigi, "Flocks, Mobs, and Figure Eights: Swarming as a Lemniscatic Arch", IEEE Transactions on Network Science and Engineering, 2022.

Pinning Control

Here we implement adaptive pinning control on a network of dynamic agents. Energy efficient pins are automatically selected using the Network Controlability Gramian. We consider the network as a Graph, $G=${ $V$, $E$ } such that:

Vertices ( $V$ ) are the agents (nodes)
Edges ( $E$ ) are a set of links in the form of ordered pairs
Edges are defined by the Cartesian Product $V \times V$, $E=$ {( $a$ , $b$ ) such that $a \in V$ and $b \in V$}
$G$ is simple, or ( $a$ , $a$) $\notin E~\forall~a \in V$
$G$ is undirected, or ( $a$ , $b$ ) $\in E <=>$ ( $b$ , $a$) $\in E$
Nodes $i$ and $j$ are neighbours if they share an edge
Adjacency matrix $A=$ { $a_{ij}$ } with dimensions $N \times N$ describes the connections between nodes where $a_{ij}$ is $1$ if $i$ and $j$ are neighbours or $0$ otherwise
Component set of the graph is a set with no neighbours outside itself

We define a pin for each component such that it consumes the minimal amount of energy to control its respective component. Here, we achieve this by computing the Network Controlability Gramian:

$W_j=$ $\sum\limits_{h=0}^{H-1}$ $A_d^hb_jb_j^T\left(A_d^T\right)^h$

where:

$A_d = AD^{-1}$
$D$ is the diagonal augmented in-degree matrix of $A$, composed by the sum of the columns of $A$ on its diagonal (or a $1$ when this sum is $0$)
$b_j$ is a column vector with all terms equal to $0$ except at the pin location $j$
$H$ is the control horizon

The trace of $W_j$ is inversely proportional to the average energy required to control the graph component when $j$ is selected as the pin. Therefore, we compute the trace of $W_j$ for each candidate pin (within a given component set) and select the one with the lowest value in order to minimize the control energy.

The graph is built using Olfati-Saber flocking (Reference 4, below) such that the agents are considered to be connected when they are within radius $r$ of eachother. These connections are what define the component sets of the graph. The pins share a common target, which draws the separate components together. As the components meet, they combine to form a larger component. New pins are computed in real-time, until all agents form part of a single component representing the entire graph. This convergence is guaranteed, so long as the components are observable, controlable, stable, and share the same target.

Below are plots with adaptive pins, selected to conserve energy using the Network Controlability Gramian:

Example using Betweenness centrality:

Example using Degree centrality (with obstacles)

Source: Kléber M. Cabral, Sidney N. Givigi, and Peter T. Jardine, Autonomous assembly of structures using pinning control and formation algorithms in 2020 IEEE International Systems Conference (SysCon), 07 Dec 2020

Citing

The code is opensource but, if you reference this work in your own reserach, please cite me. I have provided an example bibtex citation below:

@techreport{Jardine-2022, title={Flocks, Mobs, Pins, and Figure Eights: Implementations of Popular Swarming Strategies}, author={Jardine, P.T.}, year={2022}, institution={Royal Military College of Canada, Kingston, Ontario}, type={GitHub Repository}, }

Alternatively, you can cite any of my related papers, which are listed in Google Scholar.

tjards/swarming_sim