Swarm robotics and drone technology have progressed at an increasingly fast pace for the past two decades, extending their capabilities and the kinds of problems they can help tackle. Drones can now be equipped with a range of advanced devices and sensors which enable them to navigate remote areas and to operate in dangerous environments. Given the hazardous nature of the activity, ghting res by means of disposable and relatively inexpensive robots in place of humans is of special interest. In addition, the use of eets of decentralised cooperative and self-organising robots results in a robust and resilient system with collective decision-making which can cope with uncertainty, errors, and the failure or loss of a few non-essential units without jeopardising the mission. This paper comprises an initial proof of concept to demonstrate the feasibility and potential of employing swarm robotics to ght res autonomously. Thus, an e cient yet realistic model of the spread of wild res is developed, which is then coupled with a model of a eet of self-organising drones whose coordination mechanism is based on a forgetful particle swarm algorithm.
Swarm Intelligence (SI) comprises a relatively novel route to Arti cial Intelligence (AI) which stems from decentralised and self-organising behaviour observed in groups of simple social animals in nature such as ant colonies, bee colonies, sh schools, and bird ocks. By way of collaboration, these animals are able to accomplish tasks that are far beyond their individual capabilities, and even beyond the aggregation of all their individual capabilities. That is to say, the whole is more than the sum of its parts. Thus, SI is the branch of AI that deals with the collective behaviour that emerges from decentralised self-organising systems. Self-Organisation occurs with no central control or sense of purpose, as individuals only interact locally with one another and with the environment, inducing the emergence of coherent global patterns. Swarm robotics is a novel approach to the coordination of large numbers of simple and relatively inexpensive robots, which emerged as the application of SI to multi-robot systems. Di erent from other SI studies, swarm robotics puts emphasis on the physical embodiment of individuals [Sah05].
Swarm robotics and drone technology have progressed at an increasingly fast pace for the past two decades, extending their capabilities and the kinds of problems they can help tackle. Drones can now be equipped with a range of advanced cameras, thermal imagers and sensors which enable them to operate in remote areas, dangerous environments, and even through solid smoke while still being able to perform tasks such as surveying, mapping or locating people. Some of their current applications include aerial photography and lming, information gathering for human decision-makers, provision of essential supplies for disaster management, support of search and rescue operations, mapping inaccessible locations, eld surveying, and crop health monitoring. With regards to reghting, drone technology has been applied to forest surveillance, building re risk maps, forest re detection and monitoring [CBM+05], post- re recovery monitoring and forest re measuring [TBC+17], assisting search and rescue operations, and bush re hotspot detection [GW08]. A survey on technologies for automatic forest re monitoring, detection, and ghting using drones can be found in [YZL15].
Robotics and Autonomous Systems (RAS) are predicted to play an increasingly important role in disaster relief by reducing costs and response times and increasing capabilities [UK-17]. Given the hazardous nature of the activity, ghting res by means of disposable and relatively inexpensive robots in place of humans is of special interest. In addition, the use of eets of decentralised cooperative and self-organising robots results in a robust and resilient system with collective decision-making which can cope with uncertainty, errors, and the failure or loss of a few non-essential units without jeopardising the overall mission. However, the use of self-organising swarms of autonomous drones for the actual deed of putting out res has remained notably unexplored.
This paper comprises a proof of concept to demonstrate the feasibility and potential of employing swarm robotics to ght res autonomously. To this end, an e cient yet realistic physics-based model of the spread of wild res is developed, which is coupled with a model of a eet of self-organising drones whose coordination mechanism is based on a forgetful particle swarm algorithm. The aim is to develop algorithms for swarms of drones to self-organise so as to develop the ability to ght the spread of wild res without human intervention.
The remainder of the paper is organised as follows: section 2 presents a short introduction to the modelling of the spread of wild res; section 3 o ers an introduction to Particle Swarm Optimisation (PSO), including adaptations to handle dynamic environments; section 4 presents the proposed model of self-organising reghting drones, where an e cient physics-based model of the spread of re is introduced in section 4.1 and a PSO-based coordination mechanism is developed in section 4.2 for the self-organisation of the swarm; section 5 presents initial simulations; whilst concluding remarks and future work are proposed in section 6. 2
Depending on the features that are taken into account, di erent taxonomies are possible to classify models of the spread of re. Possibly the most general one is to classify them as either phenomenological (black-box) or physics-based (grey and white box) models.
Cellular Automata (CA) is a decentralised spatially extended system consisting of a large number of identical components of simple geometry with local connectivity. Two main components can be identi ed: 1) the cellular space, and 2) the transition rule. The former is a lattice of a certain number of identical nite-state machines whereas the latter returns the new state based on the current state and the states of the neighbouring cells. When used as emulators, they are able to represent complex physics with a very high level of e ciency and robustness. Within the re-spread modelling domain, CA are used as phenomenological models {i.e. as emulators, not derived from rst principles. Thus, they are designed independently from the underlying theories of re dynamics but based on a few leading assumptions. Prominent examples are the Fire Area Simulator (FARSITE ) [Fin04], the Canadian wildland re growth simulator Prometheus [TBW+10], and the Australian Bush re Risk Management Tool Phoenix [TSC+08].
Loosely speaking, there are two approaches that can be followed when deriving a physics-based model [SGM02]: 1) Bottom-up approach, and 2) Top-down approach. The former starts from rudimentary models with numerous simplifying assumptions, then progressively adding complexity by incorporating previously disregarded phenomena. These are usually semi-empirical, based on simple balance laws, and require empirical parameters and a fair amount of experimental data to calibrate them for some particular environmental condition, which are di cult to obtain and not scalable. Examples are the classical Rothermel's model [R+72] and Rio et al.'s model [RJR14] combining Rothermel's and Richard's models [Ric90] into a so-called forward model, and an inverse modelling approach that minimises the di erences between the predictions of the forward model and sensor observations. Conversely, the top-down approach consists of formulating the model from rst principles in its most general form, including as many of the relevant physical phenomena as possible, then progressively simplifying the model as required in order to cope with practical problems such as limited available resources as they arise. They typically solve convection-reaction-di usion equations, with model parameters aimed to be mathematically derived. Prominent examples are [SGM02, MSG02, FAM07, MHM+13]. 3
The Particle Swarm Optimisation (PSO) method was inspired by earlier bird- ock simulations framed within the eld of social psychology. It was also in uenced by experiments and theories in social psychology such as Sherif's experiments, Bandura's no-trial learning, and Latane's Social Impact Theory [KES01]. PSO is a global optimiser in the sense that it is able to escape poor suboptimal attractors thanks to a parallel search carried out by a swarm of cooperative particles. Its overall behaviour results from a combination of each particle's individual behaviour and the social behaviour that emerges from their interactions. The individual behaviour materialises as the trajectory of a particle pulled by an attractor. In most versions of the algorithm, this attractor results from some weighted average of an individual attractor (particle's best experience) and a social attractor (best experience among those of neighbouring particles). The social behaviour is governed by how individually acquired information is propagated throughout the swarm. The individual and social behaviours are linked by the update of the social attractor in the trajectory equation. While the social behaviour is controlled by the neighbourhood structure, the individual behaviour is controlled by the settings of the coe cients in the trajectory equation. 3.1
The original PSO (OPSO ) algorithm proposed in [KE95] is rearranged into a single equation in (1): xi(jt) = xij (t 1) + where xi(jt) is the coordinate j of the position of particle i at time-step t; xbi(jt) is the coordinate j of the best experience of particle i by time-step t; k is the index identifying the particle whose best experience is the best in the neighbourhood at time-step t; iwi(jt) and swi(jt) are the individuality weight and sociality weight, respectively, both originally equal to 2 8i; j; t; and U(0;1) is a random number from a uniform distribution in the range [0,1], resampled anew every time it is referenced.
Eq. (1) is unstable, and particles tend to diverge from the attractor(s). The rst strategy used to control this so-called explosion consisted of bounding the size of each component of a particle's displacement. This restriction helps prevent the explosion but does not ensure convergence or a ne-grain search.
Clerc et al. [CK02] analysed the trajectory of a deterministic particle in OPSO, becoming one of the rst PSO theorists in developing coe cients (constriction factor, ) which ensure convergence. The formulation of the trajectory di erence equation in Eqs. (2) and (3) is referred to here as the Constricted PSO (CoPSO). xi(jt) = xij (t 1) + (t) h ij + swi(jt)U(0;1) xb(ktj 1)
(t 1) i xij (2) (3) 8 > > > > > i(jt) = < awi(jt) > > > > >: (t) ij 2 +
2 i(jt) r awi(jt) 2 4 awi(jt) if awi(jt)
4 if awi(jt) 2 (0; 4) where awi(jt) = iwi(jt) + swi(jt)and ij 2 (0; 1) 8i; j; t:
(t)
Similarly, the formulation here referred to as classical PSO (CPSO) incorporates the inertia weight (!) initially proposed by Shi et al. [SE98], which can be set so as to also ensure convergence and favour ne-grain search: xi(jt) = xij (t 1) (t 1) + !i(jt) xij where !i(jt), iwi(jt), swi(jt) are the jth components of the inertia weight, individuality weight and sociality weight, respectively, of particle i at time-step t. For inertia weight combined with constriction factor, see [IS11]. The neighbourhood structure in the original algorithm is the global topology, where every particle is connected to every other in the swarm, therefore having access to the best solution found so far by any particle. This may lead to a rapid loss of diversity (implosion), which in turn may result in premature convergence to a poor suboptimal solution. While this can be controlled to some extent by the settings of the coe cients in the trajectory equation, numerous neighbourhood topologies have been proposed by reducing connectivity, thus delaying the propagation of information throughout the swarm. A few neighbourhood topologies are shown in Fig. 1.
An alternative to traditional topological neighbourhoods is to de ne the nearest neighbours based on actual Euclidean distance, or using the so-called speciation [Li04, LBB06, PL06] where the local attractor (i.e. neighbourhood best) is chosen as the best within adaptively generated species (clusters). For further studies on neighbourhood structures and inter-particle communication, refer to [GDK+12, CJ10, LAS18, XGZ18]. During the execution of a PSO run, if the optimum locations change, the original algorithm has no means to detect this change as particles are still under the in uence of their outdated memories. Carlisle et al. [CD00] adapted the algorithm to dynamic environments {speci cally for tracking a moving beacon{ by having particles periodically replace their memories with their currently held information, thus e ectively forgetting experiences which are likely to have become obsolete.
Blackwell et al. [BB02] proposed using charged particles in environments where the optimum location changes randomly and with high severity. The use of charged particles aims to maintain diversity, thus enabling it to better respond to such changes. The drawback is that this method requires the calculation of repulsive forces among all charged particles (n), which presents complexity of O(n2). Blackwell et al. [BB06] proposed splitting the population into a set of swarms that interact locally by an exclusion parameter and globally through an anti-convergence operator. Each swarm maintains diversity either by using charged or quantum particles.
Parrot et al. [PL06] proposed a species-based PSO algorithm with a crowding prevention mechanism to locate multiple optima, coupled with the re-evaluation of each particle's memorised best location (xb) to track the changes in the dynamic environment. Yazdani et al. [YNSMM13] proposed a nder-trackers multi-swarm algorithm combined with a mechanism to increase diversity based on a change in velocity vector and particle positions, a test point to detect change, a local search algorithm to enhance exploitation, and a so-called awakening-sleeping mechanism to improve e ciency. Sadeghi et al. [SPR15] incorporated a memory of the locations of previous optima and a diversity mechanism based on k-means clustering to track changing optima.
A comprehensive comparison of di erent techniques to be incorporated to the PSO algorithm to handle dynamic environments can be found in [LY13, YNSMM13], including diversity-maintaining schemes, memorybased schemes, and multi-swarm schemes. For further reading, refer to [RMN11, PMG11, LE12]. 4
In order to demonstrate the feasibility and potential of employing swarms of drones to ght res autonomously, without human intervention, realistic models of the spread of wild res and of the self-organising re- ghting drones need to be developed and coupled for initial simulations. 4.1
An e cient yet realistic physics-based re-spread model was developed, governed by a two-dimensional reactiondi usion equation that describes the combustion of a mono-phase medium composed of pre-mixed gas of fuel and air. This comprises a simpli ed version of the model in [FAM07], where the slope e ect and water vapour pressure are not considered. With this dimensionality reduction, some important phenomena in re dynamics such as buoyancy are disregarded. It is assumed that there is no atmospheric wind, and mass transfer is neglected (no transport). In order to compensate for this, the di usion coe cient is augmented, and two pseudo-3D terms are added into the energy balance equation to account for the energy losses due to convection and radiation in the vertical direction. Horizontal radiation is modelled to a ect only the neighbouring cells, since the cell-size of the discretised domain can be set larger than the optical thickness. The heat capacity at constant pressure of each chemical species is considered to be constant and equal to an average value within the considered temperature range, namely from 293 K to approximately 1,100 K. The mixed gases are con ned in their original location, neither di used nor transported, as if the pyrolysis gasses burned exactly where they had been released.
The irreversible chemical reaction in Eq. (5) represents the combustion of the pyrolysis gasses (e.g. methane) in the air, which is considered to be composed of oxygen, carbon dioxide, water vapour and nitrogen: 1CH4 + 2O2 ! 3CO2 + 4H2O (in air : 5N2)
The re-spread model is represented here by a system of ve partial di erential equations, one for the enthalpy
balance and four for the chemical species formation (CO2 and H2O) or consumption (Fuel and O2):
(5)
(6)
(7)
(8)
(9)
(
Combustion }|M Thermal Di usion }| + k
Vertical Convection + zCa (Ta}m|b T{) fuel Mfuel Vertical Radiation
Ta4m}b| dz
T 4 { r (T; X1; X2) = + (T;X1;2)ArT X10:5X2 exp
Ta T hc =
Hc (T )
M =
i=1 1 X5 iHi (T ) = M
M1 X5 i (Hi;ref + Micpi (Tref i=1
T ))
The system is closed with Eq. (7) for the molar mass of the mixture, Eq. (8) for the heat capacity of the
mixture, Eq. (9) for the combustion rate (Arrhenius equation), and Eq. (
The molar mass of the mixture (M ) in Eq. (7) is the summation of each chemical species molar mass (Mi) multiplied by the respective mass fraction (Xi).
The averaged constant pressure heat capacity of the mixture (cp) in Eq. (8) is obtained by weighted summation of the partial heat capacities (cpi).
The combustion rate (r) in Eq. (9) is the rate of fuel consumption, and follows the continuous exponential Arrhenius law. It is a function of temperature (T ), fuel mass fraction (X1), and oxygen mass fraction (X2). Note that the pre-exponential coe cient (Ar) and the activation temperature (Ta) are empirical parameters. + (T;X1;2) = 1 if 0 else
T > Tp or
X1;2 > X1;2e
The combustion enthalpy in Eq. (
+
The function (T;X1;2) in Eq. (9) is a Kronecker delta as in Eq. (
U(0;1) + swi(jt)
U(0;1) pi(jt) = i(jt)xbi(jt) + i(jt)xb(ktj) (t) ij
Thus, in classical PSO, the randomness incorporated into the coe cients in the trajectory di erence equation a ects both the trajectory of a particle towards the unique attractor (p) on the one hand, and the generation of the unique attractor (p) as a stochastic convex combination of the individual and social attractors on the other. Di erent from classical formulations, these two features of the algorithm are decoupled here. The attractor is generated at every time-step from a uniform distribution within the smallest rectangle that contains the current individual and social attractors. Once the attractor is generated, the trajectory di erence equation is as follows: xi(jt) = xij (t 1) + !i(jt)
The random variable can be realised as in Eq. (
1)2 ; (! + 1)i
While local neighbourhood topologies and other types of sociometries like distance-based nearest neighbours and speciation need to be investigated, only the global neighbourhood topology has been tested here.
As discussed in section 3.3, classical PSO requires some adaptations to be able to cope with dynamic environments. The spread of a wild re carries all di culties of a changing environment, even more so if it is being fought: 1) multiple hotspots continually and severely change location, 2) hotspots continually change intensity, 3) hotspots continually appear and vanish throughout the domain, and 4) drones modify the environment (stigmergy). Furthermore, re-evaluating particles' memories for the current environment is not realistic, as the sensors of physical drones will not be able to acquire data at distant locations. This issue is dealt with here by resetting a given particle's memory if it has not been updated in the last 15 seconds. If the particle belongs to the rst half of the swarm, the reset consists of assigning a random location to the memory with a ctitious temperature equal to the ambient temperature plus 10 degrees. If the particle belongs to the second half of the swarm instead, the memory is simply replaced by the currently held information (both location and temperature).
The search strategy is simple in this rst attempt: particles search for the hotspots, and they drop 40 kg of water as soon as their best experience is improved. After three drops, the drone must go back to the water source to replenish. Although we use water to extinguish the re in this paper, the ultimate goal is to exploit more sophisticated technology with higher extinguishing power and lower payload. Autonomy of each drone is simply measured in terms of distance travelled since re- lling the fuel tank. As soon as the fuel is fully consumed, the drone must go back to the fuel source to re ll the tank.
At this early stage of the research, the swarm of drones has been modelled as 2D massless particles. We are currently working on incorporating-collision avoidance algorithms and ight dynamics in the model of the self-organising drones, and transport {including atmospheric wind{ in the model of the spread of wild res. 5
The domain used in the experiments is a eld of 100x100 m2 with fuel uniformly distributed everywhere except for a small band around it so that combustion does not take place near the boundaries. The remaining settings are as shown in Table 1:
The model is implemented using Finite Di erences with Dirichlet boundary conditions in space, and the fourth order Runge-Kutta method for the integration in time. Implicit methods are computationally too intensive for our needs. Fig. 2 shows an example of the model used for the prediction of the temperature pro le and fuel energy density ve minutes after four sparks have occurred. While very e cient, the simulation of this model using Matlab and a standard PC still runs about ve times slower than real-time (without visualisation).
Once the model of the spread of wild res runs realistically and reasonably fast, the model of the (collision-free) self-organising drones is coupled. In the rst instance, we used a swarm of 50 drones which are launched from the bottom-left corner 20s after the sparks have occurred. The animations are very realistic, showing the drones moving between hotspots, with seemingly controlled ones coming back to life and going out of control while unattended. Snapshots of the temperature pro le and of the fuel energy eld at 100s and at 300s are shown in Fig. 3. As can be observed, the swarm of self-organising drones loses this ght.
Since this re- ghting system is scalable, the re can always be extinguished given su cient time and a su cient number of drones (at least for volume-less drones) {even if this number is unrealistically high. Hence (a) Temperature eld at t = 10s (c) Fuel energy eld at t = 10s (d) Fuel energy eld at t = 300s we simply doubled the size of the swarm and tested the simulation for 100 drones. Snapshots of the temperature pro le and of the fuel energy eld at 100s and at 300s are shown in Fig. 4. As can be observed, the swarm of self-organising drones wins this ght. 6
This work comprises a proof of concept to investigate the feasibility and potential of using swarms of selforganising drones not only to assist human re- ghters and to support decision-makers but also to autonomously and cooperatively strive to extinguish wild res without human intervention. The numerical experiments are not aimed at reaching a conclusion as to whether they are able to put out real res, since the models are still too simple and the settings rather arbitrary. Nonetheless, the experiments show that the self-organising decentralised cooperative behaviour is very powerful and a promising line of research to deal with such complex dynamic problem. The next step in our research is to incorporate collision-avoidance algorithms, to design and test other neighbourhood structures, and to engage more intensively in the development of self-organisation algorithms to achieve more sophisticated emergent re- ghting behaviour than the one that results from simply searching for hotspots. For these studies, the re-spread model needs to remain e cient. More advanced models (c) Fuel energy eld at t = 100s (d) Fuel energy eld at t = 300s of the spread of wild res will be required for later testing of the most promising algorithms.
The authors would like to acknowledge the nancial support of the Institute for Future Transport and Cities. [BB02] Tim M Blackwell and Peter J Bentley. Dynamic search with charged swarms. In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation, pages 19{26. Morgan Kaufmann Publishers Inc., 2002. [BB06] T. Blackwell and J. Branke. Multiswarms, exclusion, and anti-convergence in dynamic environments. IEEE Transactions on Evolutionary Computation, 10(4):459{472, aug 2006. [CBM+05] David W Casbeer, Randal W Beard, Timothy W McLain, Sai-Ming Li, and Raman K Mehra. Forest re monitoring with multiple small uavs. In American Control Conference, 2005. Proceedings of the 2005, pages 3530{3535. IEEE, 2005. (c) Fuel energy eld at t = 100s (d) Fuel energy eld at t = 300s
[CD00] Anthony Carlisle and Gerry Dozier. Adapting particle swarm optimization to dynamic environments. In International conference on arti cial intelligence, volume 1, pages 429{434, 2000. [CJ10] Ying-ping Chen and Pei Jiang. Analysis of particle interaction in particle swarm optimization.
Theoretical Computer Science, 411(21):2101{2115, 2010. Swarm Intelligence Theory: A Snapshot of the State of the Art. [CK02] Maurice Clerc and James Kennedy. The particle swarm { explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1):58{73, feb 2002. [FAM07] L. Ferragut, M.I. Asensio, and S. Monedero. A numerical method for solving convection{reaction{di usion multivalued equations in re spread modelling. Advances in Engineering Software, 38(6):366{371, jun 2007. [Fin04] Mark A. Finney. FARSITE: Fire area simulator - Model development and evaluation. Technical report, U.S. Department of Agriculture, Forest Service, Rocky Mountain Research Station, 2004. [GDK+12] Sayan Ghosh, Swagatam Das, Debarati Kundu, Kaushik Suresh, and Ajith Abraham. Inter-particle communication and search-dynamics of lbest particle swarm optimizers: An analysis. Information Sciences, 182(1):156{168, 2012. Nature-Inspired Collective Intelligence in Theory and Practice. [GW08] Ronald Graml and Grant Wigley. Bush re hotspot detection through uninhabited aerial vehicles and recon gurable computing. In 2008 IEEE Aerospace Conference. IEEE, mar 2008. [IASD15] Mauro Sebastian Innocente, Silvana Maria Bastos Afonso, Johann Sienz, and Helen Margaret Davies. Particle swarm algorithm with adaptive constraint handling and integrated surrogate model for the management of petroleum elds. Applied Soft Computing, 34:463{484, sep 2015.