Declarative vs Rule-based Control for Flocking Dynamics
Usama Mehmood

Department of Computer Science,
Stony Brook University, USA

Radu Grosu

arXiv:1710.10013v1 [cs.MA] 27 Oct 2017

Cyber-Physical Systems Group,
Technische Universitat Wien, Austria

Ashish Tiwari

SRI International, USA

Nicola Paoletti

Department of Computer Science,
Stony Brook University, USA

Shan Lin

Department of Electrical and
Computer Engineering, Stony Brook
University, USA

Junxing Yang

Department of Computer Science,
Stony Brook University, USA

ABSTRACT
The popularity of rule-based flocking models, such as Reynolds’
classic flocking model, raises the question of whether more declarative flocking models are possible. This question is motivated by
the observation that declarative models are generally simpler and
easier to design, understand, and analyze than operational models.
We introduce a very simple control law for flocking based on a
cost function capturing cohesion (agents want to stay together) and
separation (agents do not want to get too close). We refer to it as
declarative flocking (DF). We use model-predictive control (MPC)
to define controllers for DF in centralized and distributed settings. A
thorough performance comparison of our declarative flocking with
Reynolds’ classic flocking model, and with more recent flocking
models that use MPC with a cost function based on lattice structures, demonstrate that DF-MPC yields the best cohesion and least
fragmentation, and maintains a surprisingly good level of geometric regularity while still producing natural flock shapes similar to
those produced by Reynolds’ model. We also show that DF-MPC
has high resilience to sensor noise.
ACM Reference Format:
Usama Mehmood, Nicola Paoletti, Dung Phan, Radu Grosu, Shan Lin, Scott
D. Stoller, Ashish Tiwari, Junxing Yang, and Scott A. Smolka. 2018. Declarative vs Rule-based Control for Flocking Dynamics. In Proceedings of ACM/SIGAPP
Symposium On Applied Computing (SAC 2018). ACM, New York, NY, USA,
8 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

1

INTRODUCTION

Flocking is a collective behavior exhibited by a large number of
interacting agents possessing a common group objective [7]. The
term is most commonly associated with birds, and more recently,
drones. Examples include foraging for food, executing a predatoravoidance maneuver, and engaging in migratory behavior.
Permission to make digital or hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. Copyrights for third-party components of this work must be honored.
For all other uses, contact the owner/author(s).
SAC 2018, April 9-13, 2018, Pau, France
© 2018 Copyright held by the owner/author(s).
ACM ISBN 978-x-xxxx-xxxx-x/YY/MM.
https://doi.org/10.1145/nnnnnnn.nnnnnnn

Dung Phan

Department of Computer Science,
Stony Brook University, USA

Scott D. Stoller

Department of Computer Science,
Stony Brook University, USA

Scott A. Smolka

Department of Computer Science,
Stony Brook University, USA

With the introduction of Reynolds’ model [12, 13], rule-based
control became the norm in the flocking community. Specifically,
in this model, at each time-step, each agent executes a control law
given in terms of the weighted sum of three competing forces to
determine its next acceleration. Each of these forces has its own rule:
separation (keep a safe distance away from your neighbors), cohesion
(move towards the centroid of your neighbors), and alignment (steer
toward the average heading of your neighbors). As the descriptions
suggest, these rules are executed by each agent in a distributed
environment with limited-range sensing and no communication.
The popularity of Reynolds’ model and its many variants raises
the question: Is there a more abstract declarative form of control for
flocking? This question is important because declarative models
are generally simpler and easier to design, understand, and analyze
than operational models. This is analogous to declarative programs
(e.g., functional programs and logic programs) being easier to write
and verify than imperative programs.
We show that the answer to this question is indeed positive by
providing a very simple control law for flocking based on a cost
function comprising two main terms: cohesion (the average squared
distance between all pairs of agents) and separation (a sum of inverse squared distances, except this time between pairs of agents
within each other’s sensing range). That is it. For example, no term
representing velocity alignment is needed. The cost function specifies what we want as the goal, and is hence declarative. In contrast,
the update rules in Reynolds’ model aim to achieve an implicit goal
and hence are operational. Executing declarative control amounts
to finding the right balance between attracting and repelling forces
between agents. We refer to this approach as Declarative Flocking
(DF). We use MPC (model-predictive control) to define controllers
for DF, and refer to this approach as DF-MPC. We define a centralized version of DF-MPC, which requires communication, and a
distributed version, which does not.
Previous MPCs for flocking exist, e.g., [16–18]. Most of these
MPCs are designed to conform to the α-lattice model of flocking
proposed in [7]. α-lattices impose a highly regular structure on
flocks: all neighboring agents are distance d apart, for a specified
constant d. This kind of structure is seen in some settings, such as
beehives, but is not expected in many other natural and engineered
settings, and it is not imposed by Reynolds’ model.

SAC 2018, April 9-13, 2018, Pau, France

U. Mehmood et al.

In this paper, we show, via a thorough performance evaluation,
how centralized and distributed DF-MPC compare to Reynolds’ rulebased approach [12, 13], Olfati-Saber’s potential-based approach
[7], a variant of Zhan and Li’s centralized lattice-based MPC approach [15, 16], and Zhang et al.’s distributed lattice-based MPC
approach [17]. We consider performance measures that capture multiple dimensions of flocking behavior: number of sub-flocks (flock
fragmentation), maximum sub-flock diameter (cohesion), velocity
convergence, and a new parameter-free measure of the geometric
regularity of the formation.
Our experimental results demonstrate that DF-MPC yields the
best cohesion and least fragmentation, and produces natural flock
shapes like those produced by Reynolds’ model. Also, distributed
DF-MPC maintains a surprisingly good level of geometric regularity.
We also analyze the resiliency of DF-MPC and the lattice-based
MPC approaches by considering the impact of sensor noise. Our
results demonstrate a remarkably high level of resiliency on the
part of DF-MPC in comparison with these other approaches.
The rest of the paper is organized as follows. Section 2 presents
the rule-based, potential-based, and lattice-based MPC approaches
mentioned above. Section 3 defines our declarative flocking approach. Section 4 defines our performance measures for flocking
models. Section 5 presents our experimental results and performance evaluation. Section 6 discusses related work. Finally, Section 7 offers our concluding remarks and directions for future work.

2

MODELS OF FLOCKING BEHAVIOR

We consider a set of dynamic agents B = {1, . . . , n} that move
according to the following discrete-time equation of motion:
x i (k + 1) = x i (k) + dT · vi (k), vi (k) ∈ V

vi (k + 1) = vi (k) + dT · ai (k), ai (k) ∈ A,

(1)
(2)

where x i (k), vi (k), ai (k) ∈ Rm are respectively position, velocity
and acceleration of agent i ∈ B in the m-dimensional space at
step k, and dT ∈ R+ is the time step. We consider physical constraints on velocities and accelerations, described by the sets V
and A, respectively, which are defined by V = {v | |v | ≤ v̄} and
A = {a | |a| ≤ ā}, where v̄ and ā limit the allowed magnitude of
the velocity and acceleration vectors, respectively.
In most flocking models, agents update their motion by changing
their acceleration. In this sense, ai (k) represents the control input
for agent i.
The configuration of all agents is described by the vector x(k) =
[x 1T (k) . . . x nT (k)]T ∈ Rm ·n . Let v(k) = [vT1 (k) . . . vnT (k)]T ∈
Rm ·n , and a(k) = [aT1 (k) . . . aTn (k)]T ∈ Rm ·n . Then the equation
of motion for all agents can be expressed as
x(k + 1) = x(k) + dT · v(k),

v(k + 1) = v(k) + dT · a(k),

(3)
(4)

The local neighborhood of agent i is defined by the set of other
agents, called neighbors, within a given distance from i, mimicking
the agent’s visibility sphere. For an interaction radius r > 0 and
configuration x, the set of spatial neighbors of agent i, Ni (x) ⊆ B,
is given by:

Ni (x) = j ∈ B | j , i ∧ ∥x i − x j ∥ < r ,
(5)

where ∥ · ∥ denotes the Euclidean norm.

a)

b)

Figure 1: Examples of α-lattice a) and quasi α-lattice b). Solid
lines connect agents in the same neighborhood that have distance d. Dashed lines connect those with have distance d ± ϵ
for ϵ ≤ δ (the tolerance).
For configuration x ∈ Rm ·n , we define the associated proximity
net G(x) = (B, E(x)) as the graph that connects agents within their
interaction radius:

E(x) = (i, j) ∈ B × B | ∥x i − x j ∥ < r , i , j ,
(6)

To capture the regular geometry of flocks, Olfati-Saber introduced the notions of α-lattices, i.e. configurations where each agent
is equally distant from its neighbors, and quasi α-lattices, i.e. configurations that are α-lattices modulo a small error in the distances
[7]. The scale parameter d defines the ideal inter-agent distance.
Definition 2.1 (α-lattice [7]). A configuration x ∈ Rm ·n is called
α-lattice if for all i ∈ B and all j ∈ Ni (x), ∥x i − x j ∥ = d, where d ∈
R+ is the scale of the α-lattice. For tolerance δ ∈ R+ , a configuration
x ∈ Rm ·n is called a quasi α-lattice if for all i ∈ B and all j ∈ Ni (x),
|∥x i − x j ∥ − d | ≤ δ .

2.1

Sensing noise

We extend the classical equations of motion, Eqs. (1)–(2), with sensing noise affecting how each agent perceives positions and velocities
of its neighbors. Existing work has put little focus on flocking dynamics subject to noise, which is unfortunately unavoidable in
realistic natural and engineered flocks.
For actual positions x(k) and velocities v(k) at step k, let x̃(k)
and ṽ(k) denote their noisy counterparts sensed by a generic agent,
defined by:
x̃(k) = x(k) + nx(k) and ṽ(k) = v(k) + nv(k),

(7)

where nx(k) and nv(k) in
are vectors of independent and
identically distributed (i.i.d.) random variables. The position noise
nx(k) and velocity noise nv(k) are distributed according to Gaussian distributions with mean 0 and standard deviation σx and σv ,
respectively. We stress the dependency on k because noise variables
are independent across time steps.
In centralized flocking algorithms, where agent decisions are
computed by a single controller with information about the whole
population, we use Eq. 7 to define noisy measurements. In distributed algorithms, sensing noise is independent for each agent.
We denote the noisy measurement of agent i by x̃▷i (k) and ṽ▷i (k),
where positions and velocities are noisy for all agents except agent
i
Rm ·n

x̃▷i (k) =[x̃ 1T (k) . . . x iT (k) . . . x̃ nT (k)]T and

ṽ▷i (k) =[ṽT1 (k) . . . viT (k) . . . ṽnT (k)]T ,

(8)
(9)

Declarative vs Rule-based Control for Flocking Dynamics

SAC 2018, April 9-13, 2018, Pau, France

with x̃ 1 (k), . . . , x̃ n (k) and ṽ 1 (k), . . . , ṽn (k) defined as per (7); implicitly, for each agent i and each other agent j, the noise distribution is
sampled independently to compute the x̃ Tj (k) component of x̃▷i (k).

2.2 Reynolds’ rule-based model
In Reynolds’ rule-based distributed model [12, 13], agents follow
simple rules to compute their accelerations from the positions and
velocities of their neighbors. The rules are illustrated in Figure 2.
They do not explicitly specify the desired flocking formation as an
objective; rather, flocking emerges from the interaction rules.
Specifically, each agent i ∈ B updates its acceleration ai (k) at
step k by considering the following three components (adapted to
include sensing noise):
(1) Alignment: agents match their velocities with the average
velocity of nearby agents.
Õ

©©
ª
ª
= w al · ­­
·
ṽ j (k)® − vi (k)® (10)
|Ni (x̃▷i (k))|
▷i
j ∈N i (x̃ (k ))
««
¬
¬
(2) Cohesion: agents move towards the centroid of the agents in
the local neighborhood.
1

aial (k)

Õ
1
©©
ª
ª
aci (k) = wc · ­­
·
x̃ j (k)® − x i (k)® (11)
▷i
|Ni (x̃ (k))|
j ∈N i (x̃▷i (k ))
««
¬
¬
(3) Separation: agents move away from nearby neighbors.

Õ
x i (k) − x̃ j (k) ª
©
·­
® (12)
|Ni
∥x i (k) − x̃ j (k)∥ 2
«j ∈Ni (x̃▷i (k ))
¬
The cohesion and alignment rules help form and maintain a closely
packed, flock-like formation. The separation rule prevents agents
from coming too close to each other, thus reducing crowding and
collisions.
Non-negative constants w al , wc and w s are the weights for each
acceleration component. Typically, a smaller interaction radius
(hence a smaller neighborhood) is used for the separation rule,
because it is significant only when agents are very close to each
other. The overall acceleration in Reynolds’ model is given by:
asi (k) = w s ·

1

2.4

MPC-based models

Model predictive control (MPC) [2] is a well-established control
technique that works as follows: at each time step k, it computes
the optimal control sequence (agents’ accelerations in our case)
that minimizes a given cost function with respect to a predictive
model of the controlled system and a finite prediction horizon of
length T , i.e., from step k + 1 to k + T . Then, the first control input
of the optimal sequence is applied (the remainder of the sequence
is unused), and the algorithm proceeds with a new iteration.
Two main kinds of MPC-based flocking models exist, centralized
and distributed. Centralized models assume that information about
positions and velocities of all agents is available to compute their
optimal accelerations. Formally, at each time step k, it solves the
following optimization problem:
min

a(k |k ), ...,a(k +T −1|k )∈A

(13)

2.3 Olfati-Saber’s potential-based model
In potential-based flocking models, the interaction between a pair
of agents is modeled by a potential field. It is assumed that an agent
is a point source, and it has a potential field around it, which exerts a force, equal to its gradient, on other agents in its range of
influence. The potential field has circular symmetry and hence is a
function of distance from the source. In the work of Olfati-Saber [7],
the potential function ψ α for a pair of agents has its minimum at
the desired inter-agent distance d of the desired α-lattice. Outside
the interaction radius r , the potential function is constant, so the
potential field exerts no force. The exact definition of ψ α is complicated: it is the definite integral of an “action function” ϕ α that
is the product of a “bump function” ρh and an uneven sigmoidal
function ϕ. The control law computes an agent’s acceleration based
on the sum of the forces from all other agents in its neighborhood
and a velocity alignment term.

TÕ
−1
t =0

∥a(k + t | k)∥ 2

(14)

where a(k + t | k) is the control input (accelerations) for all agents
at predicted time step k + t starting from step k. The first term J (k)
is the primary model-specific cost function that the controller seeks
to optimize within the prediction horizon; it is implicitly a function
of the predicted configurations during the prediction horizon for
time step k. The second term is standard for MPC problems and
penalizes large control inputs, with weight λ > 0.
In distributed flocking models, each agent computes its optimal
acceleration based only on information about its neighbors. Each
agent i solves an optimization problem of the form:

(x̃▷i (k))|

ai (k) = aial (k) + aci (k) + asi (k).

J (k) + λ ·

min

a i (k |k ), ...,a i (k +T −1|k )∈A

Ji (k) + λ ·

TÕ
−1
t =0

∥ai (k + t | k)∥ 2

(15)

where ai (k + t | k) is the acceleration for agent i at predicted time
step k + t starting from step k, and Ji (k) is the model-specific cost
function for agent i. In distributed MPC, an agent has no way to
know current or future control decisions of its neighbors, which
are needed to make accurate predictions about their behavior. To
address this problem, some approaches allow agents to communicate their local control decisions or future positions (e.g. [16, 18]),
or assume that neighbors follow some default motion law, e.g.,
they move with constant velocities. We adopt the second strategy,
because it does not require any communication.
The majority of existing MPC-based approaches to flocking are
designed to optimize the regularity of the flock, by penalizing configurations where neighboring agents are not exactly distance d
apart, i.e., configurations that differ from an α-lattice [15–18]. We
call these approaches lattice-based MPC. Next we describe representative centralized and distributed lattice-based MPC flocking
models, which we extend to account for sensing noise. The centralized model is a variant of a model by Zhan and Li [15, 16]. The
distributed model is by Zhang et al. [17].
2.4.1 Centralized lattice-based MPC flocking. The centralized
lattice-based MPC problem is defined as:
min

a(k |k ), ...,a(k+T −1|k )∈A

T
Õ
t =1

TÕ
−1

∥д (x(k + t | k)) ∥ 2 +λ·

t =0

∥a(k+t | k)∥ 2
(16)

SAC 2018, April 9-13, 2018, Pau, France

U. Mehmood et al.

(a) Alignment

(b) Cohesion

(c) Separation

Figure 2: Interaction rules for flocking behavior in Reynolds Model.
where x(k + t | k) is the configuration of the system at predicted
time step k + t starting from step k, following the dynamics:
x i (k | k) = x̃ i (k) vi (k | k) = ṽi (k)
x i (k + t + 1 | k) = x i (k + t | k) + dT · vi (k + t | k)
vi (k + t + 1 | k) = vi (k + t | k) + dT · ai (k + t | k),

where the initial state of the prediction window is given by noisy
measurements. For configuration x, д(x) captures the α-lattice irregularity as the total deviation between agent distances and d:
Õ
d · x ji 2
∥д(x)∥ 2 =
x ji −
, with x ji = x j − x i . (17)
∥x ji ∥
(i, j)∈ E(x)

This model is inspired by [15] and [16] but differs from both:
in [15] the cost function also contains a velocity alignment term,
which the same authors removed in their subsequent work, while
in [16], “impulsive MPC” is used, which means that agents directly
control their velocities (instead of accelerations), an abstraction
that allows physically unrealizable accelerations.

2.4.2 Distributed lattice-based MPC flocking. In the distributed
MPC flocking model of Zhang et al. [17], each agent i controls its
acceleration based on position and velocity measurements of the
neighbors and assumes they have constant velocity (zero acceleration) during the prediction horizon. Similarly, the set of neighbors
of i is assumed invariant during the prediction horizon, and we
denote it by Ni (k) = Ni (x(k)). The control law for agent i is:
min

a i (k |k ), ...,a i (k +T −1|k )∈A

T
Õ
t =1

2

∥дi (x(k + t | k)) ∥ +
λ·

TÕ
−1
t =0

∥ai (k + t | k)∥ 2 .

(18)

where the predicted future dynamics of i is determined by:
x i (k | k) = x̃ i (k) vi (k | k) = ṽi (k)
x i (k + t + 1 | k) = x i (k + t | k) + dT · vi (k + t | k)
x i (k + t + 1 | k) = x i (k + t | k) + dT · ai (k + t | k),

while i’s neighbors j ∈ Ni (k) have constant velocity:

x j (k | k) = x̃ j (k) x j (k + t + 1 | k) = x j (k + t | k) + dT · ṽ j (k).

For configuration x, дi (x) is defined in a similar way to Eq. (17)
and quantifies how much i’s neighborhood Ni (k) deviates from an
α-lattice:
Õ
d · x ji 2
∥дi (x)∥ 2 =
x ji −
.
(19)
∥x ji ∥
j ∈N i (k )

3

DECLARATIVE FLOCKING

This section introduces centralized and distributed versions of our
Declarative Flocking (DF) model, and presents a flocking algorithm
based on MPC. Our formulation is declarative in that it consists of
just two simple terms: (1) a cohesion term based on the average
squared distance between pairs of agents, to keep the flock together,
and (2) a separation term based on the inverse squared distances
between pairs of agents, to avoid crowding. These two terms represent opposing forces on agents, causing agents to move towards
positions in which these forces are balanced. Unlike the majority
of existing MPC-based approaches that are designed to optimize
conformance to an α-lattice, our design does not impose a specific
geometric structure.

3.1

Centralized DF model

The cost function J for our centralized DF model contains the two
terms described above, with the cohesion term considering all pairs
of agents, and the separation term considering only pairs of agents
that are neighbors. The weight ω of the separation term provides
control over the density of the flock.
Õ
Õ Õ
1
2
∥x i j ∥ 2 + ω ·
J C (x) =
·
2
|B| · (|B| − 1)
∥x
ij ∥
i ∈B j ∈B,i <j
The control law is Eq. (14) with J (k) equal to

3.2

Distributed DF model

ÍT

(i, j)∈E(x)

t =1

J C (x(k + t | k)).

The cost function J for our distributed DF model is similar to the
centralized one, except that both terms are limited to consider pairs
of agents that are neighbors.
Õ
Õ
1
1
·
∥x i j ∥ 2 + ω ·
(20)
JiD (x) =
|Ni (k)|
∥x i j ∥ 2
j ∈N i (k )

j ∈N i (k )

The control law for agent i is Eq. (15) with Ji (k) equal to
ÍT
D
t =1 Ji (x(k + t | k)).

4

MEASURES OF FLOCKING PERFORMANCE

We introduce four key measures of flocking performance. A single
measure is insufficient, because flocking is indeed characterized by
multiple desirable properties, such as aligned velocities and cohesion. Olfati-Saber introduces four main properties for flocking [7],
informally described as:
(1) the group of agents stays connected in a unique flock, i.e., no
sub-flocks and fragmentation should emerge;
(2) the group remains cohesive, in a close-knit formation;

Declarative vs Rule-based Control for Flocking Dynamics

SAC 2018, April 9-13, 2018, Pau, France

(3) the group moves in a coherent way as if it was a unique body,
i.e., agents’ velocities are aligned; and
(4) the group maintains a regular geometry (in the α-lattice
sense).
We introduce the following four measures to capture these four
requirements. An important concept in these definitions is a subflock, which is a set of interacting agents that is too far apart from
other agents to interact with them. Formally, a sub-flock in a configuration x corresponds to a connected component of the proximity
net G(x). Let CC(x) ⊆ 2 B be the set of connected components of
the proximity net G(x).
(1) The number of connected components of the proximity net
quantifies connectedness—or, equivalently, fragmentation—of the
flock. There is no fragmentation when |CC(x)| = 1. Fragmentation
exists when |CC(x)| > 1. Fragmentation may be temporary or, if
sub-flocks move in different directions, permanent.
(2) The maximum component diameter, denoted D(x), quantifies
cohesion. It is defined by
D(x) =

max

B ′ ∈CC(x)

(21)

D(x, B ′ )

where D(x, B ′ ) is the diameter of connected component B ′ :
max

D(x, B ′ ) =

(i, j)∈B ′ ×B ′
i,j

∥xi j ∥.

(22)

Ð
Note that when all agents are isolated, i.e., CC(x) = i ∈B {{i}},
D(x) = −∞ because the domain of the max function in Equation 22
is empty when B ′ is a singleton. Note that we consider the maximum diameter of a sub-flock in order to make this measure more
independent of connectedness. If we instead considered the overall
diameter of the entire (possibly fragmented) flock, any flocking
model that did poorly on connectedness would also do very poorly
on this measure.
(3) The velocity convergence measure, adopted from [17], quantifies the average discrepancy between each agent’s velocity and the
average velocity of the flock. In particular, we extend the measure
of [17] to average velocity convergence values across sub-flocks:

VC(x, v) =

Í

B ′ ∈CC(x)

Í

i ∈B ′ vi

−

Í

|CC(x)|

j ∈B ′ v j
| B′ |

 2

|B ′ |

(23)

(4) To measure the regularity of the geometric structure of a flock,
as reflected in the inter-agent spacing, we introduce a parameterfree and model-independent irregularity measure I (x). For a connected component (sub-flock) B ′ , it is defined as the sample standard deviation of the distances between each agent in B ′ and its
closest neighbor. Thus, the measure penalizes configurations where
there is dispersion in inter-agent distances, while not imposing any
fixed distance between them (unlike α-lattices).
Ð
Let CC ′ (x) = CC(x) \ i ∈B {{i}} be the set of connected components where isolated agents are excluded. For |CC ′ (x)| = 0 (or
equivalently, |CC(x)| = |B|), i.e., all agents are isolated, we set the
irregularity I (x) = 0, which is the optimal value. This reflects the
fact that a single point is a regular structure on its own. Moreover,

such a configuration is already highly penalized by |CC(x)| and
VC(v). For |CC ′ (x)| > 0, the measure is defined by:

Í
Ò
B ′ ∈CC ′ σ
i ∈B ′ min j,i ∥x i j ∥
.
(24)
I (x) =
|CC ′ |

where σ (S) is the standard deviation of the multiset of samples S
Ò
and is the sum operator (or disjoint union) for multisets.
An α-lattice (see Def. 2.1) has the optimal value of I (x), i.e.,
I (x) = 0, since all neighboring agents are located at the same
distance d from each other, leading to zero standard deviation for the
term σ ({d, d, . . . , d }). This shows that I (x) captures the regularity
underlying the concept of α-lattice.
We introduce this measure because previous measures of regularity or irregularity, such as those in [7, 16, 17], measure deviations
from an α-lattice with a specified inter-agent distance d and are
therefore inapplicable to flocking models, such as Reynolds’ model
and our DF models, that are not based on α-lattices and do not
have a specified target inter-agent distance. Also, our irregularity
measure is more flexible than those based on α-lattices, because it
gives an optimal score to some configurations that are geometrically
regular but not α-lattices. For example, consider a configuration x
in which the agents are on the vertices of a grid with edge length e,
and the interaction radius is equal to the length of the diagonal of
a box in the grid. This configuration has an optimal value for our
irregularity measure, i.e., I (x) = 0, because the distance from every
agent to its nearest neighbor is e. This configuration is not an αlattice and hence does not nave an optimal value for the irregularity
measures used in prior work.

5

PERFORMANCE EVALUATION

We compare the performance of the models of Section 2 with the
newly introduced DF flocking models in the 2-dimensional setting.
In the first set of experiments (Section 5.1), we evaluate the performance measures illustrated in Section 4. In the second set of
experiments (Section 5.2), we analyze the resilience of the algorithms to sensor noise.
For consistency with the experimental settings of [17], the latticebased MPC problems are solved using the interior point method implemented in MATLAB’s fmincon function. Our DF-MPC problems
are solved using gradient descent optimization. Unless otherwise
specified, the population size is n = 30, the simulation length is
100, dT = 0.3, v̄ = 8, ā = 1, r = 8.4, d = 7, T = 3, and λ = 1.
These parameter values are the same ones reported in [17]. Following the settings in the OpenSteer project [11], the parameters for
Reynolds’ model are rc = 9, r s = 5, r al = 7.5, wc = 8, w s = 12,
and w al = 8. The weight of the separation term in our centralized
and distributed DF-MPC is ω = 50. As in [17], initial positions and
initial velocities of agents are uniformly sampled from [−15, 15]2
and [0, 2]2 , respectively.

5.1

Performance Comparison of Flocking
Algorithms

Fig. 3 shows examples of final formations for all flocking models.
In particular, we chose configurations where fragmentation did
not occur. We observe that the formations for lattice-based MPC
algorithms have spread-out, rigid structures, consistent with the

SAC 2018, April 9-13, 2018, Pau, France
design objective of maximizing the α-lattice regularity. On the other
hand, Reynolds and our DF MPC models result in more natural
flock shapes.
In Fig. 4, we compare the performance measures averaged over
100 runs for each flocking model. Regarding the number of connected components (sub-flocks), our centralized DF-MPC registers
the best behavior, rapidly stabilizing to an average of 1 component
(see plot a). Our distributed DF-MPC and Reynolds’ model have
comparable performance, reaching an average number of sub-flocks
below 1.4. The lattice-based MPCs and Olfati-Saber instead lead
to constant fragmentation, with more than 2 sub-flocks for the
distributed lattice-based MPC, 6 for the centralized lattice-based
MPC, and more than 8 for Olfati-Saber’s model.
This ranking is confirmed by the diameter measure (plot b),
where our centralized and distributed DF-MPC and Reynolds’ model
show the best cohesion, outperforming the lattice-based approaches.
Recall that this measure indicates the maximum diameter over all
sub-flocks, not the diameter of the entire population. As a consequence, fragmentation tends to improve diameter values since it
produces sub-flocks with fewer individuals. This explains why our
distributed DF-MPC performs better on this measure than the centralized version, and similarly why Olfati-Saber’s model has smaller
diameter measure than centralized lattice-based MPC, which in turn
has smaller diameter measure than the distributed variant.
As expected, Olfati-Saber’s model and the lattice-based MPCs
have very good performance for irregularity (plot c), since they are
designed to achieve the regular geometric formation of α-lattice.
Surprisingly, our distributed DF-MPC performs almost as well as
them on this measure. Centralized DF-MPC and Reynolds’ model
have the least regular formations.
For velocity convergence (plot d), we find that all models perform
comparably well and are able to achieve flocks with consistent
velocities fairly quickly after an initial spike.

5.2

Robustness to Sensing Noise

To evaluate the resiliency of the models to sensor noise, we performed 20 runs for each model at 10 noise levels. The noise levels
are numbered from 1 to 10, and noise level i has σx = 0.2i and
σv = 0.1i. For each performance metric, we averaged its final values over 20 runs for each noise level. The results are plotted in Fig. 5.
Of the six models, Olfati-Saber’s model is the most vulnerable to
sensing noise: the number of sub-flocks |CC | in Olfati-Saber’s model
quickly increases to nearly 30, rendering other metrics irrelevant.
The lattice-based MPC models also exhibit high fragmentation, leading to nominally good but largely irrelevant values for the other
performance metrics. Our distributed DF-MPC and Reynolds’ model
have the best resiliency to sensing noise, with both models exhibiting similar profiles in all metrics. While the irregularity and velocity
convergence measures increase with noise level, as expected, both
models remarkably maintain almost a single connected component
with a nearly constant component diameter for all 10 noise levels,
with DF-MPC achieving a smaller diameter than Reynolds’ model.

6

RELATED WORK

Reynolds [12] introduced the first rule-based approach for simulation of flocking behavior. With only three simple rules, his model is

U. Mehmood et al.
able to capture complex flocking behaviors of animals. Additional
rules can be added to the model to simulate specific behaviors, such
as leader following and predator avoidance. Pearce et al. [8] present
a rule-based strategy for flocking, where agents move to maximize
their view out of the flock. Cucker and Dong [3] present a rulebased flocking approach with proofs of convergence and collision
avoidance.
Cucker and Smale [4] introduced another popular rule-based
flocking model. The Cucker-Smale model is parameterized by a
constant β such that if β < 1/2, velocity convergence is guaranteed.
If β ≥ 1/2, velocity convergence can also be achieved under some
conditions on the initial positions and initial velocities of the agents.
Ahn and Ha [1] investigated the effects of multiplicative noise on
the long term dynamics of the Cucker-Smale model. Erban et al. [5]
extend the Cucker-Smale model to take into account stochasticity
(imperfections) of agent behavior and delay in agents’ responses to
changes in their environment.
Flocking models based on potential fields have been proposed
in several papers. Tanner et al. [14] propose a potential function
Ui j , given in Equation 25, where ||r i j || 2 is the distance between
agents i and j. For distances greater than R, the potential is set to a
constant value, C, indicating a zero force. In their control law, the
acceleration of agent i is based on the sum over all neighbors j of
the gradient of the potential function Ui j .
(
1
+ loд||r i j || 2 , ||r i j || 2 < R
| |r i j | | 2
(25)
Ui j =
C,
||r i j || 2 ≥ R
A similar potential function is also proposed by [10]. Furthermore,
potential-based solutions have been extended with additional behaviors such as obstacle avoidance and leader following. For example,
Ogren et.al. [9] use the motion of the leader to guide the motion of
the flock; the leader’s motion is independent, i.e., is not influenced
by other agents.
La and Sheng [6] propose an extension of Olfati-Saber’s model
designed for noisy environments. In addition to the terms found in
Olfati-Saber’s model, their control law contains feedback terms for
position and velocity, to make agents tend to stay close to the centroid of their neighborhood and minimizing the velocity mismatch
with their neighbors. They show that adding these feedback terms
to the control law helps bound the error dynamics of the system.

7

CONCLUSIONS

This paper presents an abstract declarative form of control for
flocking behavior and the results of a thorough comparison of
centralized and distributed versions of our MPC-based declarative
flocking with four other flocking models. Our simulation results
demonstrate that DF-MPC yields the best cohesion and least fragmentation, and produces natural flock shapes like those produced
by Reynolds’ rule-based model. Our resiliency analysis shows that
the distributed version of our DF-MPC is highly robust to sensor
noise.
As future work, we plan to study resilience of the flocking models
with respect to additional noisy scenarios such as actuation noise
(i.e., noise affecting acceleration) and faulty agents with deviant
behavior. We also plan to investigate smoothing techniques to
increase resilience to sensor noise.

Declarative vs Rule-based Control for Flocking Dynamics

75

SAC 2018, April 9-13, 2018, Pau, France

135

140

80

70

125

65

120
125

120

120

110
20

55
50
190

200

210

105

0

20

40

0

110

90
-20

(a) Reynolds

20

110
115

100

0

40
115

40

60

60

130

130

60

100

60

100

120

140

(b) Lattice-based central- (c)
Lattice-based
ized MPC
tributed MPC

dis-

90

100

-20

110

80

(d) DF centralized MPC

90

100

0

(e) DF distributed MPC

20

40

60

80

(f) Olfati-Saber

Figure 3: Examples of final formations for different flocking models. The red dots are the agent positions. The blue lines
denote the agent velocities; the line lengths are proportional to the speeds.
Lattice Distributed

Reynolds

DF Centralized

60

10

20

40

3
2

4

10
80

1

0.5

20
60

1.5
1

I

D
0

O-S
4

30

6

0

Lattice Centralized

40

5

|CC|

|CC|

50

8

DF Distributed
2

VC

10

0

0
0

20

40

Time

60

80

0

20

40

Time

2
(a) Number of connected components
|CC |
0
0
10

30

0

80

20

40

(c) Irregularity I

40

50

60

60

80

Time

Time

(b) Max component diameter D

20

60

(d) Velocity convergence V C

70

80

90

Figure 4: Comparison of performance measures obtained
with 100 runs for each flocking algorithm.
Time
Lattice Distributed

10
30

DF Centralized

DF Distributed

Lattice Centralized

O-S

1.5

1.5

1

1

40

8

30

I

VC

20

D

|CC|

Reynolds

50

20

|CC|

10
0
2

4

6

0.5

0.5

6
10

4

0
8

10

Noise Level

2
(a) Number of connected components
|CC |
0
0
10

0

0
2

4

6

8

10

2

4

Noise Level

30

8

2

10

40

(c) Irregularity I

50

60

70

4

6

8

10

Noise Level

Noise Level

(b) Max component diameter D

20

6

(d) Velocity convergence V C

80

90

Figure 5: Comparison of the final values of the performance measures
obtained with 20 runs for each flocking algorithm and
Time
for each noise level.

REFERENCES

[1] Shin Mi Ahn and Seung-Yeal Ha. 2010.
Stochastic flocking dynamics of the CuckerâĂŞSmale model with multiplicative white noises. J.
Math. Phys. 51, 10 (2010), 103301.
https://doi.org/10.1063/1.3496895
arXiv:http://dx.doi.org/10.1063/1.3496895
[2] E.F Camacho and C. Bordons. 2007. Model predictive control. Springer.
[3] Felipe Cucker and Jiu-Gang Dong. 2011. A general collision-avoiding flocking
framework. IEEE Trans. Automat. Control 56, 5 (2011), 1124–1129.
[4] F. Cucker and S. Smale. 2007. Emergent Behavior in Flocks. IEEE Trans. Automat.
Control 52, 5 (May 2007), 852–862. https://doi.org/10.1109/TAC.2007.895842
[5] Radek Erban, Jan Hasźkovec, and Yongzheng Sun. 2016. A Cucker–Smale Model
with Noise and Delay. SIAM J. Appl. Math. 76, 4 (July 2016), 1535–1557. https:
//doi.org/10.1137/15M1030467
[6] H. M. La and W. Sheng. 2010. Flocking control of multiple agents in noisy
environments. In 2010 IEEE International Conference on Robotics and Automation.
4964–4969. https://doi.org/10.1109/ROBOT.2010.5509668
[7] Reza Olfati-Saber. 2006. Flocking for multi-agent dynamic systems: Algorithms
and theory. IEEE Transactions on automatic control 51, 3 (2006), 401–420.

[8] Daniel J. G. Pearce, Adam M. Miller, George Rowlands, and Matthew S. Turner.
2014. Role of projection in the control of bird flocks. Proceedings of the National
Academy of Sciences 111, 29 (2014), 10422–10426. https://doi.org/10.1073/pnas.
1402202111 arXiv:http://www.pnas.org/content/111/29/10422.full.pdf
[9] Naomi Ehrich Leonard Peter Ogren. 2004. Cooperative control of mobile sensor networks:Adaptive gradient climbing in a distributed environment. IEEE
transactions on Automatic Control 49, 8 (2004).
[10] John H. Reif and Hongyan Wang. 1999. Social potential fields: A distributed
behavioral control for autonomous robots. Robotics and Autonomous Systems 27,
3 (1999), 171 – 194. https://doi.org/10.1016/S0921-8890(99)00004-4
[11] Craig Reynolds. 2004. OpenSteer, steering behaviors for autonomous characters.
(2004). http://opensteer.sourceforge.net/
[12] Craig W. Reynolds. 1987. Flocks, Herds and Schools: A Distributed Behavioral
Model. SIGGRAPH Comput. Graph. 21, 4 (Aug. 1987), 25–34. https://doi.org/10.
1145/37402.37406
[13] Craig W. Reynolds. 1999. Steering Behaviors For Autonomous Characters. In
Proceedings of Game Developers Conference 1999. 763–782.

SAC 2018, April 9-13, 2018, Pau, France
[14] H. G. Tanner, A. Jadbabaie, and G. J. Pappas. 2003. Stable flocking of mobile
agents part I: dynamic topology. In 42nd IEEE International Conference on Decision
and Control (IEEE Cat. No.03CH37475), Vol. 2. 2016–2021 Vol.2.
[15] Jingyuan Zhan and Xiang Li. 2011. Flocking of discrete-time multi-agent systems
with predictive mechanisms. IFAC Proceedings Volumes 44, 1 (2011), 5669–5674.
[16] Jingyuan Zhan and Xiang Li. 2013. Flocking of multi-agent systems via model
predictive control based on position-only measurements. IEEE Transactions on
Industrial Informatics 9, 1 (2013), 377–385.
[17] Hai-Tao Zhang, Zhaomeng Cheng, Guanrong Chen, and Chunguang Li. 2015.
Model predictive flocking control for second-order multi-agent systems with
input constraints. IEEE Transactions on Circuits and Systems I: Regular Papers 62,
6 (2015), 1599–1606.
[18] Lifeng Zhou and Shaoyuan Li. 2017. Distributed model predictive control for
multi-agent flocking via neighbor screening optimization. International Journal
of Robust and Nonlinear Control 27, 9 (2017), 1690–1705.

U. Mehmood et al.

