Collective search and decision-making for target localization

Abstract

In this article we investigate the properties of collective search and decision-making in robotic swarm, inspired by a phenomena witnessed in bio-societies. The task of the proposed robotic swarm, comprising scouts and labourers, is to find the most hazardous target in a predefined area. Since in the proposed scenario the time interval for decision-making is predefined, robotic scouts have to detect targets within a particular amount of time. Hence, in the first part of the article, we define a model of scout movement that enhances the explored area. As we want to keep the searching process as simple as possible, and at the same time to mimic social insect behaviour, a particular type of correlated random walk is used for exploration. The second part of the article deals with modelling of the decision-making process in the robotic swarm. Using random walk theory we determine under which circumstances all agents (or a particular number of them) would be committed to the most hazardous target at the moment when the predefined time interval for decision-making expires.

Keywords:

• swarm robotics
• correlated random walk
• decision-making process

1. Introduction

In nature, we often notice a complex behaviour of biological systems which have a large number of individuals. They usually lack sophisticated communication capabilities as well as sensor information. In spite of that, those biological systems perform extremely complex tasks. In contrast to traditional multi-robot systems control, the swarm robotic approach provides a decentralized control that relies only on local interactions between robots and their environment [1]. Those systems are robust and fault tolerant and therefore applicable to detection and confrontation of hazardous events such as fires and oil spills [2,3]. Generally, the swarm concept is very efficient in environmental monitoring since decentralized control requires minimal inter-agent communication. In [4], we proposed bio-inspired algorithms for target localization and swarm distribution (decision-making) over localized targets. Both algorithms were inspired by the behaviour of social insects, especially ants and honey bees. To continue our research, herein we aim to model complex swarm behaviour, target searching and decision-making processes.

Moving patterns demonstrated by predators while searching for prey have been investigated for several decades. Researchers' objective was to describe foraging behaviour in a formal, mathematical, way. Although it was believed that most animals and insects perform Brownian motion while searching for food, in [5] it has been proposed, for the first time, that the so-called Levy flights could be an appropriate mathematical tool for describing foraging phenomena. The first account on practical usage of Levy flight appeared in [6] where authors detected a power-law distribution of the flight intervals of albatrosses. The same authors implemented Levy flight on deer and bumblebee movement patterns with the same results – foraging appeared to have power-law distribution [7]. Following this article other authors have reported that the foraging and hunting behaviour of many animals, such as seals [8], monkeys [9], honeybees [10] and others, can be described with heavy-tail power-law distribution. As a consequence, it has been generally agreed that Levy flight with power exponent represents an optimal search pattern.

However, recent results oppose to those asserts. First, it has been shown that the methods used for fitting of data measured on foraging animals to the power-law distribution were inappropriate [11–13 13], that is, by using proposed methods it was difficult to distinguish between the Brownian and the Levy models on the basis of observed data, and second, it has been noticed that some animals combine various strategies, depending on the environment and distribution of the targets (food source), the largest dependence being in the revisitable/nonrevisitable character of the targets [14–16 16]. It has been shown in [17] that in the case of non-revisitable targets, that we are interested in, the so-called composite Brownian motion (CBM – Brownian motion comprising two random walks with different exponential distributions) gives better search results than Levy flights. This outcome has been confirmed in [18] in the case of ants locating their nest – CBM results in two phases of motion: an intensive phase with low correlation that results in highly sinuous paths with lots of turning and an extensive phase with high correlation resulting in highly correlated straight movements with no turning.

Even though through the last 30 years significant progress has been made in understanding and modelling of animals' foraging behaviour, the main drawback of most of the past and current results is that an animal trajectory has been represented by a set of distinct, independent and randomly oriented shifts. Hopefully, there have been some attempts to overcome this problem by the incorporation of continuous time correlated random walk in the model [19]. Even more important is that the most recent reports strive to continue along this line [20]. In this article we use a form of continuous time correlated random walk in discrete time framework, such that the previous positions of a scout influence the standard deviation of turning angles, while keeping the scout's velocity at maximum.

Another issue addressed in this article is modelling of the decision-making process in swarms of robots. The algorithm for decision-making draws inspiration from honeybee nest site selection process. It is important to emphasize that our aim is not to mimic honeybee behaviour completely or to investigate certain behaviour phenomena of honeybees on robots. Our aim is to only implement energy efficient behaviours (e.g. revisiting previously visited sites by scouts is considered as energy-consuming behaviour in robotic swarm). According to [21], only scout bees leave the hive and explore unknown environment. When they find a target, they return to the nest and perform a waggle dance for that site [22]. Other uncommitted scout bees decode their dances, randomly choose a dance to follow, visit the site to check its quality and finally perform waggle dance in the hive for that site. Scout bees dance for a certain site for a limited time interval. The length of the time interval depends on site quality: the higher the quality of the site, the longer is the dance time interval. The collective decision in a honeybee swarm is reached when quorum among scouts is reached [23]. Scouts are involved in the decision-making process; workers are idle agents resting in the hive and waiting for the scout's piping signal to initiate take-off to the selected nest [24]. The duration of the decision-making process in honey bees usually lasts 2–3 days [25] and duration cannot be controlled. In our robotic swarm, agents are able to assess the targets' quality accurately since they possess sophisticated sensors for certain applications (e.g. they can accurately determine the thickness of oil spill). Therefore, there exists an accurate measure of the targets' quality factor, so agents that become committed to a certain target do not have to revisit that target in order to assess its quality factor by themselves. Agents can store the information about a target's position and quality factor in their memory. Agents become committed to another target only if it has higher quality factor in contrast to honeybees who become uncommitted when their dance interval expires. There is no need for an internally triggered switching between committed and uncommitted states among robotic agents, since the communication between agents is more reliable, they possess memory and more sophisticated sensors specialized for certain applications. Furthermore, our robotic agents have an internal clock which is set to a predefined interval which can be tuned and changed and is a design parameter. When this interval expires, the decision-making process is finished and agents decide about a target they are committed to. Scouts know the exact position, and labourers follow them. In Section 4, there is a detailed mathematical analysis of the relation between the duration of decision process and parameters of information propagation in the hive.

The concept of decision-making process in swarms of robots was presented in [26], where authors presented the S-BOT project, a group of several physically connected robots which perform complex tasks. They showed that the complex decision-making abilities can emerge from simple individual behaviours. Besides the individual-based model [27], in [28,29], authors presented probabilistic macroscopic models of the task allocation process in swarms and their results provide a good prediction of the expected number of robots in certain states. Those models do not involve spatial characteristics of the search space. Switching probabilities between robot's states depends only on basic geometrical properties of the search arena. In order to provide better mapping between the mathematical model and the real process parameters, our goal was to model the nest as a discrete grid, investigate properties of random walk on a square lattice and determine agent parameters that enable stable decision-making in the swarm of robots.

The article is organized as follows: In Section 2, we describe the system and introduce basic agent behaviours that provide a complex behaviour of the swarm. In Section 3, the behavioural model that defines the agent's searching process, based on correlated random walk, is presented. In Section 4, we propose a model of information propagation and decision-making process based on standard random walk theory. In Section 5, we give conclusion and plans for future work.

2. System description

The search area is a space with dimensions D × D, containing a uniformly distributed set of targets and a nest. The target is modelled as a circle with radius . Each target has its hazard factor , i = 1, 2, … , M, where M is the number of targets in the search area. Targets do not have attractive or repulsive properties [30]. Our goal is to determine a bio-inspired model of a multi-agent system (swarm) capable to single out the most hazardous target. Hence, we consider N agents divided into two groups: scouts () and labourers (). Scouts are agents whose motion is influenced by components of a reference velocity vector, described in more detail in Section 3. Their task is to find the targets and to inform other agents in the swarm about the targets' hazard factor and location. Scouts can send messages to other scouts and labourers. Those messages contain only information about the targets' hazard factor and location. On the other hand, labourers are idle agents that basically rest in the nest and wait for the scouts' information regarding targets. Agents have the following properties:

•	scouts can distinguish targets, nest and other agents within their radius of perception ,
•	agent's locomotion is assumed to be non-holonomic, having three degrees of freedom and only two controllable variables, orientation and velocity,
•	scouts can communicate with other agents within their radius of communication ,
•	scouts have the information about global position.

2.1. Swarm behaviour

The decision-making process in the proposed multi-agent system is induced by simple behaviours of agents. Agents can be committed or uncommitted. Agents are committed if they carry information about certain target. Otherwise they are uncommitted. A scout becomes committed if it finds a target, while a labourer becomes committed if it receives a message about a target found by a scout. Scout behaviour is based on three simple modes of operation:

•	Search: The scout is searching the surroundings; It has no prior information about targets so it is uncommitted.
•	Move to target/nest: The scout moves to the nest if a potential target is found. The scout is committed to the target. If decision is reached, the scout moves to the selected target.
•	Spread information: When a scout is committed to a target, it sends messages to other agents within its radius of communication containing information about the targets' hazard factor and location. In case two scouts meet, the one committed to the target with higher hazard factor will pass its information.

Labourer behaviour is even less complex – it simply moves randomly in the nest while waiting for information about targets. Labourers cannot communicate with each other and they cannot send messages in the nest, they can only receive messages from scouts.

In the proposed system structure, an agent does not have the advanced ability of monitoring the behaviour of other agents; hence, upon the expiration of a particular time interval, which begins after the first scout leaves the nest, the agent decides on a target that it is currently committed to. This scenario is in line with two natural assumptions: (i) agents have a limited amount of energy and (ii) potentially hazardous target becomes a real threat after some time. Hence, one has to resolve under which circumstances all agents (or a particular number of them) would be committed to the most hazardous target at the moment when the predefined time interval expires. This problem is investigated in Section 4.

The second issue, addressed in Section 3, is related to the search process. Namely, due to the limited time interval for decision-making, scouts have to detect targets within a particular amount of time (which corresponds with fixing the total path length that a scout travels upon leaving the nest). The question is how to define a scout's movement in order to maximize an explored area. As we want to keep the search process as simple as possible, and at the same time to mimic social insect behaviour, a particular form of random walk is used for exploration.

3. Searching for a target

As we have already mentioned, the first problem addressed in the article is related to searching for a target. This task is performed by scouts who leave the nest and move in a search area containing one or more potential targets. In this section, we present a behaviour model that defines the scout reference vector.

3.1. Components of the reference vector

A reference vector for scout i at moment k, , is composed of two components – stochastic and heuristic:

(1)

The stochastic component controls the random walk of an agent, while the heuristic component is a bias to random movement, added to increase the scout's area coverage. In order to minimize the search time, one has to keep the scout's velocity at maximum, that is,

(2)

where is the maximum linear velocity of the scout (for the sake of simplicity we omit the scout index i in remaining text).

This type of search method, composed of stochastic and heuristic velocity components, can be seen as a form of correlated random walk [31]. Unlike in standard random walk, current position of the scout is influenced by previous positions (not Markovian process) due to the fact that reference velocities are correlated. As demonstrated in [31], one way to model velocity correlation is by using Ornstien–Uhlenbeck process which leads to autoregressive equation for each velocity component in . Depending on the autoregressive equation parameters the model would describe velocities as standard random walk or velocities with directional persistence, in which case revisits are reduced, thus increasing the scout's coverage area. Since in our approach scout should keep maximum speed while searching for targets, instead of using Ornstien–Uhlenbeck process, we propose the model with similar properties composed of two velocity components.

3.2. Heuristic component

The heuristic component, , of the reference vector, for a scout residing at position , defined as

(3)

is based on short-term memory implemented in a form of a FIFO buffer assigned to each scout. A buffer of length contains previous scout positions (see Figure 1). The influence that the buffered position j has on the final form of reference vector is calculated as

(4)

(5)

Figure 1. Short-term memory buffer and its influence on the reference vector.

The heuristic component vector attains its maximum amplitude when all heuristic vectors are colinear. In that case

(6)

Due to Equation (2)(2), one has to keep . This, according to Equation (1)(1), means that for , scout movement is driven by the heuristic component, that is, previous positions play the main role in direction of search, while in case scout movement attains the form of the random walk. Function is shown in Figure 2. It can be seen that increase of length of the short-term memory buffer, , has neglectable influence on (the behaviour of the scout) for . This fact has two important consequences: (i) the memory capacity of scouts can be kept low and (ii) the computational time, required for calculation of sum in Equation (3)(3), is reduced.

Figure 2. Influence that parameters and have on heuristic component.

Once the length of the short-term memory buffer, , and the maximum linear velocity of a scout, , are defined, remains as the design parameter that directly influences the search area covered by a scout.

3.3. Stochastic component

Stochastic component, , of reference vector is determined as

(7)

(8)

The change in argument of stochastic component, , is a stochastic variable with uniform distribution:

(9)

The amplitude of stochastic component vector is calculated as a solution of the quadratic Equation (8)(8).

3.4. Search area coverage

The scout is driven by the following procedure executed at the step k:

i.	calculate heuristic component according to Equation (3)(3);
ii.	calculate argument of stochastic component according to Equation (7)(7);
iii.	calculate amplitude of stochastic component according to Equation (8)(8);
iv.	calculate new reference vector by using Equation (1)(1); and
v.	move to new position.

While moving in the search area, a scout gathers knowledge about the space covered by its perception radius. In case a target is detected, the scout returns to the nest and spreads the obtained information. As the probability to detect a target depends on the trajectory executed by the scout, the goal is to determine the parameter such that it maximizes the covered area. A closer look into equations that determine the reference vector reveals that actually shrinks the domain of – as increases, the domain of becomes narrower. The consequence is that the scout's trajectory is becoming similar to a straight line, thus reducing the covered area and probability of target detection. On the other hand, for small values of the domain becomes and the scout performs a random walk trajectory – repeatedly moves in areas already visited, which, again, reduces the probability of target detection.

In order to determine that maximizes the area covered by a scout's trajectory, we used computer simulations of the proposed search model. Results, shown in Figure 3, confirm the assumptions that for and the covered area is small. Maximal coverage is obtained for . Evolutions of two experiments, for (left) and (right), are depicted in Figure 4.

Figure 3. Area covered by a scout as a function of design parameter .

Figure 4. Area covered by a scout for different values of : (a) , ; (b) , ; (c) , ; (d) , ; (e) , ; (f) , ; (g) , ; and (h) , .

4. Information propagation and decision-making

When a scout localizes a target, it returns to the nest and spreads information among labourers and other scouts. Based on potentially conflicting information disseminated by several scouts, the whole collective has to make a decision on which target to commit to. Similar decision-making scenarios have been observed in various biological systems [32]. However, unlike biological systems, the decision of our multi-agent group is based purely on the expiration of a predetermined time interval. Upon the expiration of this time interval each robot moves to the target that it is committed to at that moment. This decision-making scheme ensures a guaranteed response time, which is an absolute requirement in the time-critical scenarios that we are considering, such as search and rescue or environmental hazard containment. Depending on how the information propagation process was carried out, at the time of decision all robots could be committed to the same target, or to several different targets, that is, the group splits. The parameters of the information propagation process affect the decision of individual units and group cohesion at the time of decision. This link between information propagation and group cohesion is in the focus of our interest.

In this section, we present a formal method for determining the expectation that a particular number of agents (labourers and scouts) would receive information carried by a scout in a particular amount of time. Furthermore, as two (or more) scouts could move within the nest with different information, we investigate the influence that such a situation has on the final decision made by the swarm. We consider the nest in space with dimensions d × d, . When in the nest, scout reference vector contains only stochastic component, hence, it performs random walk which has been reported in [15] as an optimal behaviour in case of searching an area with large number of targets (in our case large number of labourers in limited area of the nest). In order to make random walk analysis feasible, it is assumed that a scout, although moving continuously, executes discrete steps on a 2D-grid with M nodes, where

(10)

This assumption is in line with potential search and rescue and environmental hazard containment scenarios. While the scouts are outside searching for victims or hazardous areas, all the other agents are idle in the nest, waiting to be deployed. It makes sense for the agents in the nest to be arranged in an orderly pattern, to facilitate the movement of scouts through the nest and information propagation. As we demonstrate later, analytical results gained under this assumption fit very well with results obtained by computer simulation of the proposed swarm system.

4.1. Single scout in the nest

The mathematical expectation of , which represents the number of different nodes visited by the scout after k iterations, is calculated as [33,34]

(11)

where

(12)

While moving, a scout communicates its information within the area defined by its communication radius. Depending on the scout's trajectory, consecutive communication areas might overlap, that is, a particular number of labourers receive the same information more than once. Due to the random walk the exact trajectory is not known, thus, we can only calculate a boundary value of the expected number of labourers that receive the information, , achieved in the worst case scenario, that is, a random walk with maximum overlapping (Figure 5):

(13)

where is the overlapping area of two consecutive steps.

Figure 5. Random walk in the nest with maximum communication overlapping ( – communication radius; – communication area; – overlapping area).

The boundary value in case of and 500 labourers in the nest, together with results obtained by computer simulation of the swarm, is presented in Figure 6. In the simulation, scouts were moving through the nest continuously, driven by the pure stochastic component of the reference vector, given by Equations (7)(7) and (8). Relevant system parameters, scaled relatively to robot size, are listed in Table 1. It can be seen that simulation results fit with precalculated boundary, thus confirming the efficiency of Equation (13)(13) in predicting information spread among labourers in the nest.

Table 1. Relevant system parameters for the information propagation simulations, scaled relatively to robot size (the diameter of the physical robot )

Parameter	Value
Nest dimensions	50 × 50
Communication radius	6
Evasion radius	1
Scout speed	1
Number of labourers N	500

Figure 6. Expected number of visited labourers by one scout (, ).

4.2. Several scouts in the nest

In [35] it has been proven that the cover time of a 2D-grid is reduced by at least the order of for m being the number of parallel random walks. In Table 2 we show the results for . It can be seen that the number of steps for obtained by simulation () decreases faster than the theoretical value (). This confirms that the spread of information within the nest would speed up at least by order of if more scouts with the same information move among labourers.

Table 2. Simulated and values of cover time speed up in the nest

m
1	–	225
2	157	110
3	117	70
4	89	50
5	68	41
6	50	33

However, as agents might enter the nest carrying different information, the speed-up process depends on phenomena related to rendezvous of two scouts in the nest. We are interested in the number of steps executed by the scout prior to its meeting with another scout (scouts meet when their communication areas overlap). Again, we consider the worst case situation – two scouts enter the nest on opposite corners and perform a random walk with maximum overlapping. It is well known that the distance travelled from the origin, while performing a random walk, increases with [36]. In order to derive an equation for the expected number of steps until the first rendezvous, we approximate the nest by a graph with nodes. It is important to emphasize that this graph representation is used for analytical purposes only, and that simulations have been performed with continous scout motion. In this case, the distance between two opposite corner nodes is . If we anticipate that the highest probability for two scouts to meet for the first time is when each of them is at distance of corner node, and having in mind that each node has four overlapping nodes, then the most probable number of steps required for the first randevous of two scouts is

(14)

To verify the applicability of the Equation (14)(14), we have conducted numerous simulations under the same conditions as described in Section 4.1, with two scouts moving through the nest. From Figure 7 it can be seen that calculated values of for different nest size agree with results obtained by computer simulations.

Figure 7. Number of steps required for the first rendezvous of two scouts for different nest sizes.

Now, let us assume that two scouts enter a target by carrying different information: scout localized the target with hazardous factor and scout localized the target with hazardous factor. Let us assume that all labourers are uncommitted and scout gets in the nest steps after scout . That is, information on target with lower hazardous factor is communicated within the nest for steps. The question is for which values of one can guarantee that the final swarm decision (i.e. predetermined percentage of agents) would be towards , that is, the target with higher hazardous factor?

The expected number of nodes, visited by scout , until its rendezvous with can be calculated from Equation (11)(11) as

(15)

Once scouts meet, receives information from and both scouts continue to communicate information . The expected number of nodes visited by both scouts in the interval , where is the required number of steps for the swarm to make decision, is calculated as

(16)

where, in the worst case of speed up by order of , . A value that better fits computer simulation results (see Table 1) is defined as . Now, from Equations (15)(15) and (16), by using result in Equation (13)(13), one can obtain a lower bound of the expected number of agents that are committed to a higher hazardous factor target, with respect to . Calculated lower bound, together with simulation results, is shown in Figure 8. It can be seen that, for example, if the second scout enters the nest after 70% of the time for decision-making has expired (), only 80% of the agents are committed to the optimal target.

Figure 8. Number of agents committed to optimal target for different .

5. Conclusion

Two problems related to the analysis of multi-agent systems inspired by biological swarms have been addressed in the article. One of them is concerned with conditions required for the successful detection of targets that reside within a predefined search area investigated by agents (scouts). In this article we proposed the addition of a so-called heuristic component as part of agent's reference vector defined by stochastic component derived from random walk, thus forming movement of a scout driven by correlated random walk. This change, as demonstrated in the article, increases the area covered by the scout performing target search thus decreasing the time needed for target localization. The second problem is concerned with decision-making in a multi-agent system. The properties of information propagation within the nest area, occupied by the so-called labourers, have been investigated. A lower bound for the expected number of committed labourers has been defined, as well as the influence of several scouts in the nest on its value. These results have been confirmed by computer simulation of the proposed swarm system. A short simulation video clip can be viewed at: http://larics.rasip.fer.hr/movies/swarmsearch.avi. Our current work on this topic is concerned with open issues related to influence that boundaries of a search area and the nest have on obtained results. Namely, in research presented in this article we used theoretical results on random walk on toroidal graphs. Although simulation results with relatively small search area and nest with predefined boundaries comply with theory to a large extent, question is for which dimensions derived relations remain valid. Second issue that is currently investigated is related to the formalization of analytic relations between amount of explored area and parameters of correlated random walk.