Cost Adaptation for Robust Decentralized Swarm Behaviour

arXiv:1709.07114v1 [cs.AI] 21 Sep 2017

Peter Henderson1 , Matthew Vertescher2 , David Meger1 , and Mark Coates2
Abstract— The multi-agent swarm system is a robust
paradigm which can drive efficient completion of complex
tasks even under energy limitations and time constraints.
However, coordination of a swarm from a centralized
command center can be difficult, particularly as the swarm
becomes large and spans wide ranges. Here, we leverage
propagation of messages based on mesh-networking protocols for global communication in the swarm and online
cost-optimization through decentralized receding horizon
control to drive decentralized decision-making. Our costbased formulation allows for a wide range of tasks to
be encoded. To ensure this, we implement a method for
adaptation of costs and constraints which ensures effectiveness with novel tasks, network delays, heterogeneous
flight capabilities, and increasingly large swarms. We use
the Unity3D game engine to build a simulator capable of
introducing artificial networking failures and delays in the
swarm. Using the simulator we validate our method using
an example coordinated exploration task. We release our
simulator and code to the community for future work.

I. INTRODUCTION
In recent years, unmanned aerial vehicles (UAVs)
have become commonplace. They have been used most
notably for military purposes [1], aerial photography [2],
and parcel delivery [3]. However, the maximum flight
time of these systems is still limited. This is a challenge for timely completion of tasks such as mapping
and exploration of expansive terrains – a potentially
beneficial goal for the many industries. Systems of
multiple autonomous agents promise to accomplish tasks
at a much faster pace To this end, we pursue a multiagent system which can accomplish cooperative tasks in
a fully decentralized and self-coordinated autonomous
manner. We focus on a cooperative exploration task, as
this has been a widely cited problem with a variety of
applications and goals [4], [5].
We formulate a set of costs and constraints based
on natural flocking behaviour [6] and accomplish local decision making by decentralized receding horizon
control [7] (i.e. finding the next optimal state to be
in at the next timestep). In a complex swarm, it is
difficult to select the correct cost weights a priori, but
agents receive feedback on their local environment and
task performance during execution. We leverage this
experience data through adaptive simulated annealing [8]
1 Department of Computer Science, McGill University, Montreal,
Quebec, Canada peter.henderson@mail.mcgill.ca
2 Department of Electrical, Computer, and Software Engineering,
McGill University, Montreal, Quebec, Canada

to learn a balance between the cost functions and
constraints that allow our agents to perform the present
task optimized for safety and efficiency. This adaptation
further allows for easy replacement of tasks with other
goal-driven objectives and adaptation to a myriad of environmental perturbations (e.g. varying network delays,
heterogeneous mixtures of robot capabilities). For global
coordination, we formulate a mesh network within the
swarm which can propagate messages and beliefs to any
agent connected in the mesh. We implement a bidding
systems to actively divide and assign sub-goals within
the swarm in an entirely decentralized manner. This
allows for large numbers of agents to extend the swarm
and actively partition swarms if this results in more
efficient global coordination.
We construct a 3D simulation capable of mimicking
packet loss and communication delays. Through our
simulator, we show the feasibility of our approach by
accomplishing a cooperative exploration task. We further
demonstrate that the adaptive cost balancing in our system allows for safe and efficient exploration even under
large communication delays. The swarm can actively readapt to keep a safer distance between agents or even
cluster together under negligible communication delays.
Furthermore, our formulation as a mesh network and
consensus bidding solution for global decision making
allows for continuing performance gains under growing
numbers of agents. We release the code for simulation
and implementation to the community1 .
The benefits and applications of our method to any
robotic system are clear. The adaptive nature of our
formulation allows for heterogeneous mixtures of agents
with different capabilities and goals to participate in
the swarm. This has the potential to be used in robot
convoying [9], cooperative exploration [10], or heterogeneous coordination for marine monitoring [11]. The
global consensus bidding model can be expanded to
optimal task completion research as in [12]. This work is
easily expandable and a base for future implementations
of adaptable systems.
II. R ELATED W ORK
Several coordinated swarm systems use centralized
decision-making for coordination of complex tasks
where fine-grained control is needed. In [13], the authors
1 https://github.com/Breakend/SocraticSwarm

form a dense swarm of indoor micro-copters through a
centralized control center and motion capture to track
position. They find that a centralized command center
with motion capture is needed to have the necessary
target tracking error bounds for indoor dense swarms.
In [11], the authors use a command-and-control center
to coordinate a heterogeneous mixture of robots for
coordinated monitoring of marine environments.
Other works focus on decentralized coordination of
UAVs for swarm task completion. In [14], the authors
present the “first decentralized mutlicopter flock that performs stable autonomous outdoor flight“. A differential
update rule for the velocity is derived, based on natural
flocking rules and information belief about neighbouring
swarm members. Other works favour continual cost
optimization to find the next optimal velocity or position
based on the belief of the neighbours states, rather than
differential updates. This is accomplished by setting a
time horizon and computing the optimal predicted parameters at the horizon. The action is taken, information
is then gathered, and the optimization problem solved
again repeatedly. These are called decentralized receding
horizon control (D-RHC) methods [7], [15].
In our work, we aim to move toward decentralized
control through a mesh-network. This allows for extended swarms and dynamic swarm partitioning and
re-joining in locales where it may not be feasible to
establish a central command-and-control center. As such,
we extend the decentralized receding horizon control
scheme posed in [7].
III. BACKGROUND AND P RELIMINARIES
A. Mesh Networking
Mesh networks are composed of multi-hop end-points
which are capable of routing messages between all the
nodes in the mesh. The IEEE 802.11s-2011 is one mesh
network protocol standard which has become increasingly popular and is particularly adept for changing
swarm topologies. The default underlying routing protocol in 802.11s is the Hybrid Wireless Mesh Protocol
(HWMP) [16]. HWMP has both reactive and proactive
routing characteristics. When no root mesh point is
present in the network to initiate proactive tree to root
routing, reactive routing is used by default. In relation
to a dynamic network of autonomous vehicles, the
on-demand path-finding properties of HWMP are well
suited to keep overhead low. Further, frequent multicast
updates in swarms would refresh routes frequently and
the overhead of reactive routing would be minimized.
While our networking simulation can apply to generally
any mesh approach, the 802.11s standard fits well to
facilitate versatile swarm topologies, as such, we base
our communication protocol on this standard for future
expansion using this protocol.

B. RHC and D-RHC
In receding Horizon Control (RHC) control systems,
a constrained optimization problem is used to determine
the next action for a projected time frame, or until the
next receding horizon [17]. RHC systems are used across
many domains, including code generation [17], flight
systems in F-16 fighter jets [1], and decentralized swarm
robotics [18], [15]. A common theme throughout the
RHC literature is its usage in mission critical systems
where fast and reliable decision making is needed. With
an optimized and appropriate set of cost functions, it
has been shown that a system using RHC can “perform
near its physical limits” [17] and, as such, is ideal
for our application. In particular, we focus on D-RHC
as a control scheme. D-RHC models can be generally
formulated as:
minimize
P(xi , Ye )
subject to
c0 (xi , Ye ), . . ., cm (xi , Ye )
Here xi is some variable, or set of variables, (like the
position and velocity of an autonomous agent) that can
be minimized. Ỹ ∼ {e
y0 , . . . , yen } are the predicted states
of input data analogous to the predicted position and
velocity states of the neighbour nodes in swarm at the
next horizon. P is the optimization problem which the
D-RHC controller is trying to solve, comprising the
internal costs of the system. {c0 , . . . , cm } is the set of
constraints the optimization problem must obey.
The D-RHC controller first predicts state information
of its neighbouring nodes and any other variable data inputs at the next time horizon. To make these predictions
it uses any model information it may have about the
optimization functions of the other controllers or simply
current state information like velocity. The system then
runs a cost minimization algorithm to determine the
optimal solution at the next time horizon for a variable
it can control, such as the velocity of the agent.
C. Boids Flocking
The “boids” model presented by Reynolds [6] is
based on natural flocking patterns in birds. Three core
rules make up natural flocking. According to this work,
each agent in a flock aims only to: “steer to avoid
crowding local flockmates” (separation), “steer towards
the average heading of local flockmates” (alignment),
and “steer to move toward the average position of local
flockmates” (cohesion). By following these fundamental laws, simulated agents can mimic natural flocking
behaviour often seen in birds.
IV. M ETHOD
We formulate decentralized task completion as a
mixture of global coordination and local action decisionmaking. Global coordination involves task decomposition and assignment through decentralized consensus

bidding. Local action decisions are made using D-RHC.
We frame our work in the context of a coordinated
exploration task where the state space is easily divisible
by an area grid. In this formulation, the mesh-networked
decision-making process can be viewed in three parts:
(1) knowledge distribution and gathering; (2) global goal
assignment through bidding within agents connected
through the mesh; (3) local action choice through costoptimization. In the first part, agents must propagate
information about each other through the network such
that efficient coordination can be accomplished. In the
second, divisible parts of the task are assigned to agents
through a decentralized bidding process. In the last, the
information gained through propagation and bidding is
used to optimize the local action choice used by lowlevel controllers. A general outline of this can be seen
in Algorithm 1.
Algorithm 1: Agent Decision Process
1

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Divide task into a set possible goals Gi associated
with a cost Ci .
while True do
while not WonBid do
bid = CalculateNextBid()
Broadcast(bid)
WonBid = CompleteBidding()
if WonBid then
AddCost(bid.SubGoalCost)
end
end
while not Completed(bid.SubGoal) do
belief=predictBeliefAt(ti+1 )
nextPos = optimize(costs, belief)
applyVelocityToward(nextPos)
broadcast(currentPosition)
updates = ListenForPositionUpdates()
updateBeliefState(updates)
end
end

A. Knowledge Propagation and Mesh Networking
We assume a fluid mesh network for our swarm. That
is, agents can drop in and out of the network if that
is the most optimal action to take. Because of this,
the swarm must propagate information about its fellow
agents to ensure the efficient completion of tasks. Each
agent has the ability to send information about itself, the
environment, or bidding results. Before an agent makes
a decision, it must process all new messages and directly
update its knowledge base. Each agent keeps a record
of its current belief about a neighbour’s position, goal,
and the information about the world.

At the start of the decision loop, agents broadcast
their position to its immediate neighbours in the mesh.
Incoming updates are processed and placed into the
knowledge base. Similar to D-RHC, agents will try and
predict their neighbours positions at the next horizon
using any position, velocity, and acceleration information in addition to the time elapsed since the message
was sent (via timestamp on the information packet). For
bidding, messages are propagated throughout the mesh
and agents are made aware if new swarm members join.
B. Bidding
For global coordination, a task must be divided into
smaller parts, which we will denote as sub-goals. In an
exploration task, the sub-goals are to search an area
subsection, or tile. To coordinate the distribution of
these sub-goals, we formulate a decentralized consensus
bidding mechanism wherein agents: calculate their next
desired sub-goal to complete, broadcast a bid, and enter
an auction process until they claim a sub-goal. All
receiving agents keep a belief state of the state of all
sub-goals (e.g. in bidding, claimed, completed). Bids
are re-broadcast through the mesh, unlike current agent
positions which are only broadcast locally.
If an agent does not have a sub-goal assigned to it or a
candidate sub-goal (where a bid has been submitted) it
will generate a new bid. A bid is calculated as gj =
wdist Dj + wnear λij based on [19] and the largest bid
from all unclaimed sub-goals is chosen. In the context
of exploration, here Dj is the distance to the centre of
the tile and λij is the cohesion factor from other agents
to the tile. This bid formulation encourages a choice of
sub-goals that are close the current position, with some
spread-out factor from other agents. This helps to reduce
contention for tiles, which increases search efficiency.
If an agent has the highest bid within some auction
timeout, it claims the sub-goal. If there is a higher bid,
it marks its own belief of the sub-goal as claimed by
another agent and re-bids. Once an agent reaches and
completes a sub-goal, it broadcasts this update through
the mesh. With larger communication delays, race conditions can occur during bidding. If an agent receives
information contrary to its own beliefs, it attempts to
correct its current belief state or send out corrective
messages to the swarm. Some of these scenarios are
described in Figure 1.
V. L OCAL ACTION C HOICE THROUGH D-RHC
For decisions on what trajectory to follow we use DRHC. This optimizes for the best possible position to be
at the next time horizon.
A. Constrained Optimization Problem
We define our decision cost function as a mixture of
three costs: cohesion, safety, and goal. These are based

Agent 1

Agent 2

Agent 1

Agent 1

Agent 2

Agent 1

Agent 2

Timeout
Timeout
Claimed

Bid on ti
Bid on ti

Agent 2
Bid on ti

Bid on ti

Claimed
Searched

Higher Bid on ti

Higher Bid on ti
Higher Bid on ti

Gives up

Drops claim

Timeout
Claimed ti

Timeout

Timeout

Claimed ti

Searched ti

Claimed ti
Drops claim

(a) a

(c) c

(b) b

(d) d

Fig. 1. Illustrations of several bidding scenarios. (1) shows the common no contention bid. (b) shows two agents bidding over the same tile
where a winner is achieved without race conditions. (c) illustrates an agent bidding on an already claimed tile. The agent with the lower bid
drops its claim. (d) shows an agent claiming a searched tile. The agent that searched the tile corrects its neighbours’ knowledge.

on the formulations seen in [14], [7]. While we initially
considered the rote boids formulation (i.e. alignment,
separation, and cohesion), we empirically found that we
could combine separation and cohesion into one term
and remove the alignment penalty for efficiency.
1) Cohesion: Our combined cohesion cost is:
(

(2dj /rc ) − 1 if dj < 0.75rc
Cpenalty
otherwise
!
P|N | j
j=1 α f (dj , rc )
cη = min 1,
|N |

f (dj , rc ) =

(1)

2) Safety Cost: While the safety cost can adapt to
many contexts, here we simply formulate it as keeping
a safe altitude off of the ground. Note, that we explicitly
model collision with other agents as a constraint, while
altitude is a cost. This is by design, as in the case of
landing, the altitude safety cost can be decreased.
((yi /ymin ) − 1)2
cy = min 1,
((yi − ymin )/ymax )2

if ymin > yi
otherwise

(4)

Where pi is the agent’s position to be tested and pgoal
is the position of the centre of the goal tile which the
agent intends to search. Cdiet is a centroid point which
determines the slope of the cost according to arctan.
4) Full Optimization Problem: Thus our action
swarm action decision process can be viewed as an
optimization problem:

(2)

Where d1 ≤ d2 · · · ≤ d|N | (i.e. the distance are sorted
in order) and dj = dist(pj , pi ). Here |N | designates the
local neighbour space (i.e. the closest z neighbours),
and for most purposes we set z = 7 to simplify
the system). dj is the distance to the neighbour; rc
is the communication range; α ∈ [0, 1] is a fading factor.

(




dist(pi , pgoal )
2
cg = min 1, arctan
π
Cdist

!

(3)
Here, yi is the altitude to be tested and ymin , ymax are
the bounds for the altitude.
3) Goal Cost: Lastly, we must formulate a goal cost
associated with the completion of a sub-goal. Once a
sub-goal has been claimed, this goal cost is added to the
D-RHC optimization problem, driving task completion
in local actions. This is formulated as:

min
s.t.

(wη cη + wy cy + wg cg )
pt+1
< pti + (vit + ati ∗ δt) ∗ δt
i
∀j∈neighbours distance(pt+1
, pt+1
i
j ) > ∆min

(5)

Here, wη , wy , wg are the cost weights. vit is the current
velocity, ati is the current acceleration, δt is the time
until the next horizon, pt+1
is the next position with
i
cost to be minimized, pti is the current position, pt+1
is
j
a neighbour’s predicted position at the next horizon, and
∆min is some minimum distance kept between an agent
and any neighbour.
Figure 2 shows the functions modelled by these costs.
We explicitly bound the output of each cost function
between 0 and 1. This makes cost adaptation much more
intuitive and easy to optimize. Note, that we formulate
collision as a constraint, bounding the next optimal
position such that it is not within some sphere of radius
∆min surrounding an agent. For higher communication
delays, this ∆min can be adapted to prevent agents
from risking collision with an uncertain agents position.
Furthermore, we bound the search space to only points
that are reachable by the agent by the next horizon based
on the agent’s current velocity and acceleration.
5) Solving the Optimization Problem: To minimize
our optimization problem, we attempted several different
techniques. We investigated Particle Swarm Optimization with constraints and Differential Evolution with

1
Cp
0

1

0

rc /2
(a)

Fig. 2.

0

rc

1

0

cη

ymin
(b)

cy

ymax

0

0

1
(c)

cg

Visualizations of each of the three cost functions. cη , cy and cg describe the cohesion, safety and goal cost respectively.

constraints2 . Both PSO and DE performed well, but DE
with constraints proved to be the least computationally
intensive approach with acceptable solutions. As such,
we simply use this method as a black box for constrained
optimization of D-RHC problem.
VI. A DAPTING C OSTS AND C ONSTRAINTS
Since our D-RHC model relies heavily on the cost
minimization of weighted functions, it is important to
find an ideal balance between the weights and the correct
constraint values. As such, we need to search for the
best balance which achieves the safest and most efficient
performance even under adverse conditions. As such, we
use a guided search method to find the best optimum
weight balance across iterative trials.
First, we constrain our weights w ∈ W such that
w = [Wmin , Wmax ]. For consistency and reduction of
the search space, we set Wmin = 0, Wmax = 1. We
evaluate each trial using a set of weights according to a
heuristic function, Ec .

turned to Adaptive Simulated Annealing (ASA) [8],
[21]. We found poor convergence properties with the
rote version of ASA, as such, we modify it for our own
purposes. This selection algorithm in our formulation is
shown in Algorithm 2.
Algorithm 2: Adapting Costs and Constraints
Input : w ∈ W for all weights assigned to costs
and constraints. wmin , wmax , ∀w ∈ W
Output: w̄ ∈ W̄
−MAX TRIALS
1 Set a temperature TC = T0 = .95
2 Initialize w
ˆ0 = w̄ = w; ∀w ∈ W, ŵ ∈ Ŵ , w̄ ∈ W̄
3 Set Emin = ∞
4 for i = 0, 1, 2, . . . ,MAX TRIALS do
5
Sample ŵi+1 ∈ Ŵi+1 with the random variable
Yi ∼ U [(w̄min − w̄) TTC0 , (w̄max − w̄i ) TTC0 ]
according to:
ŵi+1 = wi + yi ; wi+1 ∈ Wi+1 , wi ∈ Wi
Run trial with Ŵ Eand evaluate heuristic Ec .

Ec = ctime + 2cnsrh + 4cclsn
ttrial
ctime =
tmax

(6)
(7)
2

cclsn

ccompleteness = 1 − (pcomplete )
(
clsn
0.25 + 0.75 nnagents
, nclsn > 0
=
0
, otherwise

(8)

cprev −Ec

6

7
8
9

(9)

Here, pcomplete is the fraction of the task completed
(for the coordinated exploration task this is the percentage of tiles searched); nclsn is the number of agent
collisions with the total number of agents being: nagents ;
ttrial is the time it took to complete a trial and tmax is
the maximum allowed trial time.
This heuristic is used in successive trials to optimize
the cost balance under the current system dynamics
(such as conditions with heavy packet loss). While we
initially formulated the cost re-balancing problem with
simulated annealing [20], we found this to be a sample
inefficient search method. Since the desire is to reweight the costs in as few simulations as possible, we
2 Both PSO and DE from C# framework found at: http://www.
hvass-labs.org/projects/swarmops/cs/

10
11
12
13
14
15

TC
if Ec < Emin or e
> v ∼ U [0, 1]
then
Emin = Ec
Set w̄ = ŵi ; ∀ŵi ∈ Ŵi , w̄ ∈ W̄
end
if i mod 25 = 0 then
Re-anneal, by setting TC = T0
end
else
Set TC = T0 (.95)i
end
end

VII. E XPERIMENTS
To validate our methods, we use an example coordinated exploration problem. Here, the task is to search a
given a 600m×400m area. This area can be divided into
384 (25m×25m) tiles. To search a tile properly, an agent
must be a distance of 5 meters or less from the centre of
the tile and 40 meters above the ground. This is to simulate taking an aerial photograph. The goal is to search
the entire space in a decentralized manner in the least

Sensors

Altimeter

Flight
Controller

Communication
Goal Bids

Safety Cost

Cohesion Cost

GPS

Cost Manager

Decision
Manager

Agent

Knowledge
Base

World
State

Comm
Manager

Bidding
Knowledge

Possible
Goals

Goal Cost
Tile

RectZone

Trial
Runner

Fig. 3. Simplified class diagram of the simulation structure. The colours green, blue and orange represent the Learning, World State and
Agent modules respectively. The Learning module consists of the trial runner, responsible for conducting a single trial. The World State module
facilitates inter-agent communication and maintains the true state of the task. It also serves as the communication manager. The Agent module
consists of several sub modules designed to support each of the required functionality from movement to decision making. Agents communicate
with each other through the world module.

amount of time possible without collisions. The timeout
for tiles after the first bid (auction time, tauction ) was 0.5
seconds. Agents update their next desired location every
tupdate = 0.05s and send agent update message every
tbroadcast = 0.25s. The communication range was set
to 200 meters based on several known 802.11s capable
chipsets [22]. The maximum velocity of an agent was
set to 40ms−1 in any direction. With maximum vertical
acceleration at 6 ms−2 and horizontal acceleration at
3 ms−2 . These settings allow for a balance between
realistic dynamics and speed of simulation.
A. Simulator
Several promising 3D multi-agent robotics simulators
exist, including Stage [23] and Argos [24]. However,
we found that existing simulators provided a large
amount of overhead in fast implementation of meshnetworked agents or were poorly maintained. Instead, we
built our simulation on the actively maintained Unity3D
game engine3 . Unity supports basic physics simulations,
networking, and all other necessary components for our
swarm simulation including the ability to add visual cues
which indicate algorithm performance.
B. Overall Architecture
The overall architecture of the simulator encompasses
three main modules: Learning, World State, and Agent.
The Learning module facilitates the execution of multiple trials for weight optimization and cost adaptation.
The World State module is in charge of running a single
trial, simulated communication, and keeping track of the
overall world state. Finally, the Agent module consists
of several sub modules designed to simulate a swarm
agent and decision making algorithms. A simplified class
diagram of the framework can be seen in Figure 3.
Each agent has a simulated GPS sensor for position
and altitude as well as an IMU for heading, velocity,
3 https://unity3d.com

acceleration. To simulate the real world inaccuracy of
sensors, random noise of up to two meters is added to
the agents’ position. We also add an simulated altimeter based on ray-casting to the “sea-level”. A simple
flight controller is implemented which calculates the
necessary pitch, roll, yaw velocities to move toward
the next desired position. The maximum velocity and
acceleration are scaled in the positive and negative y
directions representing the agility of the quad copter
to gain or drop altitude quickly. Agents send either
position updates or bidding related messages through the
WorldStateManager, which represents the mesh network
protocol’s lower communication layers. Figure 4 shows
an example of five agents in simulation4 .
VIII. R ESULTS
A. Adaptation to Network Delays
Tables I compare the control versus increasing communication delay with five agents. The average completion time (µt ) and variance (σt2 ) across 100 simulated
trials – along with the percent of area searched in
the restricted time frame (300 seconds) and number
of collisions between agents in that time frame. Communication delay was variable with the average delay
as shown in the table. The control scenario consists
of the each agent having a pre-calculated flight plan
which avoids all other agents. As the communication
delay increases past the auction time of 0.5 seconds,
collisions and slower search times appear when the cost
and nearness constraint is not properly tuned to account
for uncertainty in neighbouring position.
In the second half of Table I, costs were adapted with
ASA for 50 iterations, then 100 trials were run with
the optimal adaptation. As can be seen, performance
drastically improves as distance constraints and cost
penalties are re-weighted to complete tasks in the safest
4 Video

demo: https://youtu.be/2TUSXMo493I

Fig. 4. Five agents searching 384, 25 × 25m2 tiles. Agent start in the bottom left corner and search clockwise around the grid as illustrated
by the spread of the green tiles. Black lines show an agents position to where it believes each of the other agents to be. Agents tend to search
tiles at a comfortable distance to swarm. Red, blue, yellow, green are the states of the tiles (not claimed, in auction, claimed, searched).

Tdelay (s)
Control
0
0.2
0.4
0.8
1.6
3.2
0
0.2
0.4
0.8
1.6
3.2

µt (s)
σt2 (s)
µ% Searched
Without Adaptation
107.08
0.47
100
175.15
48.26
100
177.30
42.79
100
174.68
53.80
100
171.60
49.73
100
198.86
370.13
100
221.56
449.73
98
With Adaptation
164.44
53.86
100
162.22
45.12
100
168.15
56.72
100
171.34
33.14
100
195.93
67.26
100
191.07
77.45
100

µcollisions

σmaxV elocity

0
0
0
0
0
0.12
2.25

10
20
30

0
0
0
0
0
0

TABLE I
C OMMUNICATION DELAY TRIALS

and most efficient manner possible. While we note that
performance of the control in this scenario is obviously
faster, it is not robust to changing goals and conditions
(such as destruction of members of the swarm). In
our approach, the swarm recovers and picks up other
workers’ tasks if they are not completed.
B. Adaptation to Heterogenous Capabilities
To further expand on our analysis of the system’s
ability to adapt to new conditions, we investigate using
heterogeneous mixtures of agents. For these purposes,
we spawn 10 agents and limit trials to 100 seconds such
that goal is to complete as many tiles as possible in
this time with hetergeneous dynamics. We use the same
384 tile grid and run 100 trials. We vary the maximum
velocity of the agents by adding a fixed Gaussian noise
of the form ∼ N (0, σmaxVel ) to the maximum velocity
of each agent at the start of the experiment such that
every agent has different flight dynamics.
First, we use the original parameters with results seen
Table II and then we perform 50 iterations of adaptive
simulated annealing to re-adapt our cost balance before
our 100 trial iterations. We similarly add a fixed Gaussian noise of the form ∼ N (0, σacc ) to the acceleration
of each agent in another set of experiments. We find that
in nearly every case, adaptation significantly improves
performance and the agents are able to adapt to heterogeneous neighbours successfully simply by adapting the

10
20
30

2
µ% Searched
σ%
Searched
Without Adaptation
51.4 %
3.9 %
30.7 %
7.4%
40.1 %
5.7%
With Adaptation
63.2 %
3.4 %
53.2 %
7.9%
70.1 %
13.5%

µcollisions
0
0
0
0
0
0

TABLE II
A DAPTATION TO VELOCITY G AUSSIAN NOISE
σacceleration
.5
1.0
2.0
2.5
.5
1.0
2.0
2.5

2
µ% Searched
σ%
Searched
Without Adaptation
51.4 %
1.8%
61.1%
3.3%
67.2%
2.4%
51%
12.15%
With Adaptation
63.3%
0.2%
70.1%
0.8&
73.6%
3.6%
77.9%
6.7%

µcollisions
0
0
0
0
0
0
0
0

TABLE III
A DAPTATION TO ACCELERATION G AUSSIAN NOISE

balance of cost functions and constraints using adaptive
simulated annealing. We note that at higher dynamics
noise, we found that part of the non-adaptive swarm
was sometimes stuck trying to stick with a slower agent
and end up not searching very many tiles. In these cases,
the adaptive swarm found that the best parameters left
behind lagging members by lowering the cohesion cost.
C. Scalability
A benefit of using mesh networking and global bidding is the ability to scale to large numbers of agents.
Agents
5
10
15
20
25
30

µt (s)
175.15
97.73
95.00
70.66
51.60
49.37

σt2 (s)
48.26
23.84
25.00
4.80
3.30
2.32

µcollisions
0
0
0
0
0
0

TABLE IV
T RIALS ON SCALABILITY TO NUMBER OF AGENTS .

Table IV shows the evaluations of the algorithms performance using varying number of agents. The communication delay was fixed at zero and trials were
simulated 100 times each. As more agents are added,
we see search times decrease as expected, without any
collisions. However, at around 30 agents, we find that for
our particular grid test case, there is too much contention
for space and performance gains begin to level off.
D. Other Properties
Furthermore, we made note of several key features
of our system. If we change bidding from propagating
messages through the mesh to the simple broadcasting
of messages to immediate neighbours, we find that the
swarm is still able to complete tasks. This is because,
belief states are inherently updated through correction
during the bidding process as we discuss earlier. We
find that these corrections cascade through the network,
effectively accomplishing selective propagation. This
effect is further seen when new members join a swarm
or multiple swarms join together.
IX. D ISCUSSION
Overall, we develop a system for decentralized coordination of generic tasks through mesh networking,
consensus bidding and D-RHC. We demonstrate that
this system can leverage cost adaptation through heuristic optimization to successfully conform to new environment conditions. We build a simulator on top of
Unity3D, evaluate our system on a coordinated exploration task, and release all code to the public.
The robust framework we introduce here has vast
potential for reuse in a myriad of settings. In particular,
the heuristic-based cost adaptation methods here can
leverage reinforcement learning in the future for more
efficient online learning. The robustness of the methods
we present here are building blocks for future advances
in swarm behaviour and robotic control systems.
R EFERENCES
[1] T. Keviczky and G. J. Balas, “Receding Horizon Control of
an F-16 Aircraft: A Comparative Study,” Control Engineering
Practice, vol. 14, no. 9, pp. 1023–1033, 2006.
[2] H. Xiang and L. Tian, “Development of a low-cost agricultural
remote sensing system based on an autonomous unmanned aerial
vehicle (uav),” Biosystems engineering, vol. 108, no. 2, pp. 174–
190, 2011.
[3] E. T. Bokeno, T. M. Bort, S. S. Burns, M. Rucidlo, W. Wei, D. L.
Wires et al., “Package delivery by means of an automated multicopter uas/uav dispatched from a conventional delivery vehicle,”
Jan. 7 2016, uS Patent App. 14/989,870.
[4] J. Banfi, A. Q. Li, I. Rekleitis, F. Amigoni, and N. Basilico,
“Strategies for coordinated multirobot exploration with recurrent
connectivity constraints,” Autonomous Robots, pp. 1–20, 2017.
[5] I. Rekleitis, V. Lee-Shue, A. P. New, and H. Choset, “Limited
communication, multi-robot team based coverage,” in Robotics
and Automation, 2004. Proceedings. ICRA’04. 2004 IEEE International Conference on, vol. 4. IEEE, 2004, pp. 3462–3468.

[6] C. W. Reynolds, “Flocks, Herds and Schools: A Distributed
Behavioral Model,” SIGGRAPH Comput. Graph., vol. 21,
no. 4, pp. 25–34, Aug. 1987. [Online]. Available: http:
//doi.acm.org/10.1145/37402.37406
[7] T. Keviczky, F. Borrelli, K. Fregene, D. Godbole, and G. J. Balas,
“Decentralized receding horizon control and coordination of
autonomous vehicle formations,” IEEE Transactions on Control
Systems Technology, vol. 16, no. 1, pp. 19–33, 2008.
[8] L. Ingber., “Adaptive Simulated Annealing (ASA): Lessons
Learned,” Control and Cybernetics, vol. 25, pp. 33–54, 1996.
[9] F. Shkurti, W.-D. Chang, P. Henderson, M. J. Islam, J. Camilo
Gamboa Higuera, J. Li, T. Manderson, A. Xu, G. Dudek, and
J. Sattar, “Underwater multi-robot convoying using visual tracking by detection,” in Proc. of The IEEE International Conference
on Intelligent Robots and Systems (IROS), 2017.
[10] C. Trevai, Y. Fukazawa, J. Ota, H. Yuasa, T. Arai, and
H. Asama, “Cooperative exploration of mobile robots using
reaction-diffusion equation on a graph,” in Robotics and Automation, 2003. Proceedings. ICRA’03. IEEE International Conference on, vol. 2. IEEE, 2003, pp. 2269–2274.
[11] F. Shkurti, A. Xu, M. Meghjani, J. C. G. Higuera, Y. Girdhar, P. Giguere, B. B. Dey, J. Li, A. Kalmbach, C. Prahacs
et al., “Multi-domain monitoring of marine environments using
a heterogeneous robot team,” in Intelligent Robots and Systems
(IROS), 2012 IEEE/RSJ International Conference on. IEEE,
2012, pp. 1747–1753.
[12] A. Xu, C. Viriyasuthee, and I. Rekleitis, “Optimal complete
terrain coverage using an unmanned aerial vehicle,” in Robotics
and automation (ICRA), 2011 IEEE international conference on.
IEEE, 2011, pp. 2513–2519.
[13] J. A. Preiss, W. Honig, G. S. Sukhatme, and N. Ayanian,
“Crazyswarm: A large nano-quadcopter swarm,” in Robotics and
Automation (ICRA), 2017 IEEE International Conference on.
IEEE, 2017, pp. 3299–3304.
[14] G. Vásárhelyi, C. Virágh, G. Somorjai, N. Tarcai, T. Szörényi,
T. Nepusz, and T. Vicsek, “Outdoor Flocking and Formation Flight with Autonomous Aerial Robots,” arXiv preprint
arXiv:1402.3588, 2014.
[15] T. Keviczky, F. Borrelli, and G. J. Balas, “Decentralized Receding Horizon Control for Large Scale Dynamically Decoupled
Systems,” Automatica, vol. 42, no. 12, pp. 2105–2115, 2006.
[16] G. R. Hiertz, S. Max, R. Zhao, D. Denteneer, and L. Berlemann,
“Principles of IEEE 802.11s,” in Proc. Computer Communications and Networks, 2007, pp. 1002–1007.
[17] J. Mattingley, Y. Wang, and S. Boyd, “Receding Horizon Control,” Control Systems, IEEE, vol. 31, no. 3, pp. 52–65, 2011.
[18] T. Keviczky, K. Fregene, F. Borrelli, G. J. Balas, and D. Godbole,
“Coordinated Autonomous Vehicle Formations: Decentralization,
Control Synthesis and Optimization,” in American Control Conference, 2006, 2006, pp. 6–pp.
[19] W. Sheng, Q. Yang, J. Tan, and N. Xi, “Distributed Multi-Robot
Coordination in Area Exploration,” Robotics and Autonomous
Systems, vol. 54, no. 12, pp. 945–955, 2006.
[20] P. J. Van Laarhoven and E. H. Aarts, Simulated Annealing.
Springer, 1987.
[21] L. Ingber, A. Petraglia, M. R. Petraglia, and M. A. S. Machado,
“Adaptive Simulated Annealing,” in Stochastic Global optimization and Its Applications with Fuzzy Adaptive Simulated
Annealing. Springer, 2012, pp. 33–62.
[22] L. Li, X. Hu, and B. Zhang, “A routing algorithm for wifi-based
wireless sensor network and the application in automatic meter
reading,” Mathematical Problems in Engineering, vol. 2013,
2013.
[23] R. Vaughan, “Massively Multi-Robot Simulation in Stage,”
Swarm Intelligence, vol. 2, no. 2-4, pp. 189–208, 2008.
[24] C. Pinciroli, V. Trianni, R. O’Grady, G. Pini, A. Brutschy,
M. Brambilla, N. Mathews, E. Ferrante, G. Di Caro, and
F. Ducatelle, “ARGoS: A Modular, Parallel, Multi-Engine Simulator for Multi-Robot Systems,” Swarm Intelligence, vol. 6, no. 4,
pp. 271–295, 2012.

