{'fraction_non_alphanumeric': 0.02775319480335587, 'fraction_numerical': 0.007186095083011788, 'mean_word_length': 4.704765751211632, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cost Adaptation for Robust Decentralized Swarm Behaviour

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 cost-based 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] 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 community 1 .
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. RELATED WORK
Several coordinated swarm systems use centralized decision-making for coordination of complex tasks where fine-grained control is needed. In [13], the authors 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].

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: Here x i is some variable, or set of variables, (like the position and velocity of an autonomous agent) that can be minimized.Ỹ ∼ { y 0 , . . . , y n } 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. {c 0 , . . . , c m } 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. METHOD
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.

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 g j = w dist D j + w near λ ij based on [19] and the largest bid from all unclaimed sub-goals is chosen. In the context of exploration, here D j 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. LOCAL ACTION CHOICE THROUGH D-RHC
For decisions on what trajectory to follow we use D-RHC. 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 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: Where d 1 ≤ d 2 · · · ≤ d |N | (i.e. the distance are sorted in order) and d j = dist(p j , p i ). 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). d j is the distance to the neighbour; r c is the communication range; α ∈ [0, 1] is a fading factor.
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.
Here, y i is the altitude to be tested and y min , y max 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: Where p i is the agent's position to be tested and p goal is the position of the centre of the goal tile which the agent intends to search. C diet 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: Here, w η , w y , w g are the cost weights. v t i is the current velocity, a t i is the current acceleration, δt is the time until the next horizon, p t+1 i is the next position with cost to be minimized, p t i is the current position, p t+1 j is 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 Fig. 2. Visualizations of each of the three cost functions. cη, cy and cg describe the cohesion, safety and goal cost respectively. constraints 2 . 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. ADAPTING COSTS AND CONSTRAINTS
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 = [W min , W max ]. For consistency and reduction of the search space, we set W min = 0, W max = 1. We evaluate each trial using a set of weights according to a heuristic function, E c .
Here, p complete is the fraction of the task completed (for the coordinated exploration task this is the percentage of tiles searched); n clsn is the number of agent collisions with the total number of agents being: n agents ; t trial is the time it took to complete a trial and t max 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 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. w min , w max , ∀w ∈ W Output:w ∈W 1 Set a temperature Run trial withŴ and evaluate heuristic E c .

VII. EXPERIMENTS
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  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, t auction ) was 0.5 seconds. Agents update their next desired location every t update = 0.05s and send agent update message every t broadcast = 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 engine 3 . 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 simulation 4 .

A. Adaptation to Network Delays
Tables I compare the control versus increasing communication delay with five agents. The average completion time (µ t ) and variance (σ 2 t ) 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 Fig. 4. Five agents searching 384, 25 × 25m 2 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). 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 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.  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. DISCUSSION
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.