## Abstract

The problem is autonomous coordinated search by an interconnected group of moving robots for the purpose of finding and localising a source of hazardous emissions (e.g., gas and particles). Dispersion of the emitted substance is assumed to be affected by turbulence, resulting in the absence of concentration gradients. The chapter proposes a search strategy that operates in a completely decentralised manner, as long as the communication network of the moving robots forms a connected graph. By decentralised operation, we mean that each moving robot is reasoning (i.e., estimating the source location and making decisions on robot motion) locally. Coordination of the group is achieved by consensus via communication with the neighbours only, in a manner which does not require global knowledge of the communication network topology.

### Keywords

- autonomous search
- machine intelligence
- sequential Monte Carlo estimation
- infotaxis

## 1. Introduction

Searching strategies for finding targets using appropriate sensing modalities are of great importance in many aspects of life. In the context of national security, there could be a need to find a source of hazardous emissions [1, 2, 3]. Similarly, rescue and recovery missions may be tasked with localising a lost piece of equipment that is emitting weak signals [4]. Biological applications include, for example, protein searching for its specific target site on DNA [5], or foraging behaviour of animals in their search for food or a mate [6, 7]. The objective of search research [8] is to develop optimal strategies for localising a target in the shortest time (on average), for a given search volume and sensing characteristics.

The use of autonomous vehicles in dangerous missions, such as finding a source of hazardous emissions, has become widespread [9, 10, 11]. Existing approaches to the search and localisation in the context of atmospheric releases can be loosely divided into three categories: up-flow motion methods, concentration gradient-based methods and information gain-based methods, also known as * infotaxis*. Both the up-flow motion methods and the concentration gradient methods are simple, in the sense that they require only a limited level of spatial perception [12]. Their limitations manifest in the presence of turbulent flows, due to the absence of concentration gradients, when the plume typically consists of time-varying disconnected patches. The information gain-based methods [13] have been developed specifically for searching in turbulent flows. In the absence of a smooth distribution of concentration (e.g., due to turbulence), this strategy directs the searching robot(s) towards the highest information gain. As a theoretically principled approach, where the source-parameter estimation is carried out in the Bayesian framework and the searching platform motion control is based on the information-theoretic principles, the infotaxic (or cognitive) search strategies have attracted a great deal of interest [3, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23].

This chapter summarizes our recent results in development of an autonomous infotaxic coordinated search strategy for a group of robots, searching for an emitting hazardous source in open terrain under turbulent conditions. The assumption is that the search platforms can move and sense. Two types of sensor measurements are collected sequentially: (a) the concentration of the hazardous substance; (b) the platform location within the search domain. Due to the turbulent transport of the emitted substance, the concentration measurements are typically sporadic and fluctuating. The searching platforms form a moving sensor network, thus enabling the exchange of data and a cooperative behaviour. The multi-robot infotaxis have already been studied in [16, 17, 20, 24]. However, all mentioned references assumed * all-to-all* (i.e., fully connected) communication network with

*of the searching group.*centralised fusion and control

We develop an approach where the group of searching robots operate in a fully decentralised coordinated manner. Decentralised operation means that each searching robot performs the computations (i.e., source estimation and path planning) locally and independently of other platforms. Having a common task, however the robotic platforms must perform in a coordinated manner. This coordination is achieved by exchanging the data with immediate neighbours only, in a manner which does not require the global knowledge of the communication network topology. For this reason, the proposed approach is scalable in the sense that the complexities for sensing, communication, and computing per sensor platform are independent of the sensor network size. In addition, because all sensor platforms are treated equally (no leader-follower hierarchy), this approach is robust to the failure of any of the searching agents. The only requirement for avoiding the break-up of the searching formation is that the communication graph of the sensor network remains * connected* at all times. Source-parameter estimation is carried out sequentially, and on each platform independently, using a Rao-Blackwellised particle filter. Platform path planning, in the spirit of

*, is based on entropy-reduction and is also carried out independently on every platform.*infotaxis

## 2. Mathematical models

First, we describe the measurement model. The concentration measurements are modelled using a Lagrange encounters model developed in [13], based on an open field assumption and a two-dimensional geometry. Let * average* wind characteristics be the speed

^{1}

where

The probability that a sensor at location

Parameter

The motion model of a coordinated group of robots is described next. Let the pose vector of the

For each platform

The measurements of concentration are taken at time instants * travel time*) for the

Motion of the

where vector

Here,

A robotic platform can communicate with another platform of the formation, if their mutual distance is smaller than a certain range

## 3. Decentralised sequential estimation

Estimation and robot motion control are carried out using the measurement dissemination-based decentralised fusion architecture [25]. Measurement locations^{2} and the corresponding measured concentration values, i.e., the triple

Suppose the posterior density function of the source at discrete-time

where

where

is independent of

where the posterior of source strength

Since the conjugate prior of the Poisson distribution is the Gamma distribution [28], the posterior

The parameters of the prior for source strength,

Next, we turn our attention to the posterior of source position

where

The Rao-Blackwellised particle filter (RBPF) fully describes the posterior

Here,

## 4. Decentralised formation control

In decentralised multi-robot search, each platform autonomously makes a decision at time

### 4.1 Selection of individual control vectors

A robot platform

where

Previous studies of search strategies [3, 20] found that the reward function defined as the * reduction of entropy*, results in the most efficient search. Hence, we adopt the expected reward defined as

where

while

where

Given that

In order to compute

where the product

Thus, (17) is approximated with

Pseudo-code of the routine for the computation of control vector on platform

Algorithm 1 Computation of

1:

2: Compute

3: Create admissible set

4: ** for** every

do

5: Compute the future platform location

6: Compute

7: Determine

8: Compute

9: Calculate the expected reward

10:

11: Find

12:

### 4.2 Cooperative control through consensus

So far, we have explained how platform

We apply decentralised cooperative control based on the average consensus [30, 31]. In a network of collaborating agents, consensus is an iterative protocol designed to reach an agreement regarding a certain quantity of interest. Suppose that every platform, as a node in the communication network, initially has an individual scalar value. The goal of average consensus is for every node in the network to compute the average of initial scalar values, in a completely decentralised manner: by communicating only with the neighbours in the communication graph (without knowing the topology of the communication graph).

In the problem we consider, there is not only a single individual scalar value, but six of them. They include three motion control parameters, i.e., for platform

Let us denote the scalar value of interest by

Ideally, we want every platform in the formation to compute the mean value

Average consensus is an iterative algorithm. At iteration

where * maximum degree weights* [32]. Other weights can be also used. It can be shown that if the communication graph is connected, the values

The search continues until the global stopping criterion is satisfied. The local stopping criterion is calculated on each platform independently based on the spread of the local positional particles

The global stopping criterion is computed on each platform using the average consensus algorithm, using (21), but with

We point out that both estimation and control are based on the consensus algorithm. While the cooperative control is using the * average* consensus (21), the decentralised measurement dissemination of Section 3 achieves the consensus on the set of measurements at time

*. Furthermore, assuming bidirectional communication between the robots in formation, the network topology can be represented by an undirected graph. The convergence of the consensus algorithm for a time-invariant undirected communication topology is guaranteed if the graph is connected [31, 32, 33]. Note that this theoretical result is valid for an infinite number of iterations. In practice, if the communication graph at some point of time is not connected, or if an insufficient number of consensus iterations are performed, it may happen that one or more robots are lost (they could re-join the formation only by coincidence). This event, however, does not mean that the search mission has failed: the emitting source will be found eventually, albeit by a smaller formation in possibly longer interval of time.*time-invariant

## 5. Numerical results

The proposed search algorithm has been applied to an experimental dataset, collected by COANDA Research & Development Corporation using their large recirculating water channel. The emitting source was releasing fluorescent dye at a constant rate from a narrow tube. The dataset comprises a sequence of 340 frames of instantaneous concentration field measurements in the vertical plane and is sampled at every 10/23 s. The size of a frame is

An example of the search algorithm running on the experimental data is shown in Figure 2. All physical quantities are in arbitrary units (a.u.). The following environmental/sensing parameters were used:

Figure 2 displays the top-down view of the search progress at step indices ** (a)–(c)** of Figure 2 show the particles before resampling: the particles are placed on a regular grid, thus mimicking a grid-based approach, with the value of particle weights indicated by the grey-scale intensity plot (white means a zero weight). This provides a good visual representation of the posterior

**shows the situation after a non-zero concentration measurement was collected by the search team. The positional particles have been resampled at this point of time and moved closer to the true source location.**(d)

Using 200 Monte Carlo simulations, the mean search time for the algorithm was 2525 a.u., with a 5th and 95th quantile of 1840 and 3445 a.u., respectively. Note that in all simulations the formation started from the bottom right hand corner indicated in Figure 2(a).

## 6. Conclusions

The chapter presented a decentralised infotaxic search algorithm for a group of autonomous robotic platforms. The algorithm allows the platforms to search and locate a source of hazardous emissions in a coordinated manner without the need for a centralised fusion and control system. More precisely, this distributed coordination is achieved only by local exchange of measurement data between neighbouring platforms. Similarly, the movement decisions taken by the platforms were reached using a distributed average consensus algorithm over the whole formation. The key aspect is that individual platforms only require knowledge of their neighbours; the global knowledge of the communication network topology is unnecessary. An advantage of adopted distributed framework is that all platforms are treated equally, making the proposed search algorithm scalable and robust to the failure of a single platform. Numerical results using experimental data confirmed the robust performance of the algorithm. The main limitation of the algorithm is that the environmental parameters (such as diffusivity, the average direction and speed of the wind, particle lifetime), must be known. Future work will explore sensitivity to parametrisation and will aim to develop a team of “search and rescue” robots for further experimentation in realistic environments.

## Acknowledgments

This research was supported in part by the Defence Science and Technology Group through its Strategic Research Initiative on Trusted Autonomous Systems.

## References

- 1.
Hutchinson M, Liu C, Chen W-H. Information-based search for an atmospheric release using a mobile robot: Algorithm and experiments. IEEE Transactions on Control Systems Technology. 2018; 99 :1-15 - 2.
Ristic B, Morelande M, Gunatilaka A. Information driven search for point sources of gamma radiation. Signal Processing. 2010; 90 :1225-1239 - 3.
Ristic B, Skvortsov A, Gunatilaka A. A study of cognitive strategies for an autonomous search. Information Fusion. 2016; 28 :1-9 - 4.
Haley KB, Stone LD, editors. Search Theory and Applications. Nato Conference Series. New York: Plenum Press; 1980 - 5.
Halford SE. How do site-specific DNA-binding proteins find their targets? Nucleic Acids Research. 2004; 32 (10):3040-3052 - 6.
Fauchald P, Tveraa T. Using first-passage time in the analysis of area-restricted search and habitat selection. Ecology. 2003; 84 (2):282-288 - 7.
Viswanathan GM, Afanasyev V, Buldyrev SV, Murphy EJ, Prince PA, Satnley HE. Levy flight search patterns of wandering albatrosses. Nature. 1996; 381 :413-415 - 8.
Shlesinger MF. Mathematical physics: Search research. Nature. 2006; 443 (7109):281-282 - 9.
Bayat B, Crasta N, Crespi A, Pascoal AM, Ijspeert A. Environmental monitoring using autonomous vehicles: A survey of recent searching techniques. Current Opinion in Biotechnology. 2017; 45 :76-84 - 10.
Dunbabin M, Marques L. Robots for environmental monitoring: Significant advancements and applications. IEEE Robotics and Automation Magazine. 2012; 19 (1):24-39 - 11.
Ishida H, Wada Y, Matsukura H. Chemical sensing in robotic applications: A review. IEEE Sensors Journal. 2012; 12 (11):3163-3173 - 12.
Masson J-B, Bailly-Bachet M, Vergassola M. Chasing information to search in random environments. Journal of Physics A: Mathematical and Theoretical. 2009; 42 :434009 - 13.
Vergassola M, Villermaux E, Shraiman BI. ‘Infotaxis’ as a strategy for searching without gradients. Nature. 2007; 445 (25):406-409 - 14.
Barbieri C, Cocco S, Monasson R. On the trajectories and performance of infotaxis, an information-based greedy search algorithm. Europhysics Letters. 2011; 94 (2):20005 - 15.
Fatès N. Collective infotaxis with reactive amoebae: A note on a simple bio-inspired mechanism. In: International Conference on Cellular Automata; 2016. pp. 157-165 - 16.
Hajieghrary H, Ani Hsieh M, Schwartz IB. Multi-agent search for source localization in a turbulent medium. Physics Letters A. 2016; 380 (20):1698-1705 - 17.
Hajieghrary H, Tomas AF, Hsieh MA. An information theoretic source seeking strategy for plume tracking in 3D turbulent fields. In: Proceedings of the IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR); 2015. pp. 1-8 - 18.
Hein AM, McKinley SA. Sensing and decision-making in random search. Proceedings of the National Academy of Sciences of the United States of America. 2012; 109 :12070-12074 - 19.
Hutchinson M, Oh H, Chen W-H. Entrotaxis as a strategy for autonomous search and source reconstruction in turbulent conditions. Information Fusion. 2018; 42 :179-189 - 20.
Masson J-B. Olfactory searches with limited space perception. Proceedings of the National Academy of Sciences of the United States of America. 2013; 110 (28):11261-11266 - 21.
Moraud EM, Martinez D. Effectiveness and robustness of robot infotaxis for searching in dilute conditions. Frontiers in Neurorobotics. 2010; 4 :1-8 - 22.
Ristic B, Skvortsov A, Walker A. Autonomous search for a diffusive source in an unknown structured environment. Entropy. 2014; 16 (2):789-813 - 23.
Voges N, Chaffiol A, Lucas P, Martinez D. Reactive searching and infotaxis in odor source localization. PLoS Computational Biology. 2014; 10 (10):e1003861 - 24.
Ristic B, Angley D, Moran B, Palmer JL. Autonomous multi-robot search for a hazardous source in a turbulent environment. Sensors. 2017; 17 (4):918 - 25.
Hlinka O, Hlawatsch F, Djuric PM. Distributed particle filtering in agent networks: A survey, classification, and comparison. IEEE Signal Processing Magazine. 2013; 30 (1):61-81 - 26.
Doucet A, De Freitas N, Murphy K, Russell S. Rao-Blackwellised particle filtering for dynamic Bayesian networks. In: Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence; 2000. pp. 176-183 - 27.
Ristic B, Gunatilaka A, Wang Y. Rao–Blackwell dimension reduction applied to hazardous source parameter estimation. Signal Processing. 2017; 132 :177-182 - 28.
Gelman A, Carlin JB, Stern HS, Rubin DB. Bayesian Data Analysis. 2nd ed. Boca Raton FL: CRC Press; 2004 - 29.
Chong EKP, Kreucher C, Hero AO. Chapter 8. POMDP approximation using simulation and heuristics. In: Hero AO, Castanon D, Cochran D, Kastella K, editors. Foundations and Applications of Sensor Management. New York: Springer; 2008 - 30.
Xiao L, Boyd S. Fast linear iterations for distributed averaging. Systems & Control Letters. 2004; 53 (1):65-78 - 31.
Ren W, Beard RW, Atkins EM. Information consensus in multivehicle cooperative control. IEEE Control Systems. 2007; 27 (2):71-82 - 32.
Xiao L, Boyd S, Lall S. A scheme for robust distributed sensor fusion based on average consensus. In: Proceedings of the 4th International Symposium on Information Processing in Sensor Networks; 2005. p. 9 - 33.
Olfati-Saber R, Fax JA, Murray RM. Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE. 2007; 95 (1):215-233

## Notes

- Robot locations are assumed to be non-coincidental with the source location r0.
- Because the measurement locations are assumed to be known exactly, they will not be treated as random variables.