Keywords

1 Introduction

Recent years have seen a rapidly growing interest in multi-robot systems for automatically surveilling environments of different size, type and complexity. Multi-robot systems (MRS) consist of multiple interacting robots, each executing an application-specific control strategy, which is not centrally steered. The interest in MRS for surveillance is largely motivated by the wide range of application areas including the protection of safety-critical technical infrastructures and buildings, search and rescue scenarios, the monitoring of danger zones which cannot be entered by humans, for instance, in the case of a nuclear incident, a bio-hazard, etc. As such automated surveillance has become a well studied topic in multi-robot research with a strong practical relevance.

A key advantage of robot-based surveillance lies in its flexibility achieved through possible positional changes of the robots, which makes this form also suited for surveillance applications in unknown or complex environments. In contrast to stationary wireless sensor-based surveillance systems or networks, however, robot-based surveillance systems have not yet found their way to real-world applications on a broader scale. Two interrelated key components of every multi-robot surveillance system are exploration and coverage of a potentially unknown environments. The term exploration refers to the discovery of all traversable regions of the environment through one or several robots [30]. The term coverage refers to the maximisation of (or the process of maximising) the total area covered by the sensors of the involved robot(s) [30].

Previously, we have investigated three different biological inspirations: the stigmergy principle of ants, the foraging behaviour of honey bee colonies and the pheromone signalling procedure of honey bees. StiCo, the stigmergy principle, is based on the observations of ant colonies, and is used as a coordination mechanism for coverage by multi-robot systems [30]. The foraging behaviour of honey bee colonies [24] are inspected and used to solve robot coordination, navigation and path planning issues in multi-robot platforms. PS [7], a honey bee inspired pheromone signalling procedure, is used to address load balancing and redundancy control issues in wireless sensor networks.

In this paper we are concerned with coverage issues of multi-robot systems. Specifically we explore the performance outcomes of the bees pheromone signalling procedure, which we call BeePCo, when applied to the coverage problem in multi-robot systems. The proposed BeePCo mechanism is inspired by biological processes: how social insects (bees) control and orchestrate with other members of a hive [1, 2]. As abstract agents, individual bees have many similarities with robots (as do bee colonies with MRSs). The required similarities are in terms of individual wellbeing (bee/robot) and collective welfare (colony/MRS). With our approach, we enable group coordination among robots, where the individual movement-related decisions of each robot is based on its local information. The proposed approach is evaluated in simulation against the well-known ant algorithm, StiCo [30].

The remainder of this paper is structured as follows. Section 2 reviews the related work in the areas of multi-agent coverage and bio-inspired techniques in networked distributed systems. Section 3 covers pheromone signalling based coverage algorithms for MRSs together with the required biological background. The paper continues with the experimental setup and results in Sect. 4. We conclude in Sect. 5.

2 Related Work

This section gives an overview of relevant literature that has attempted to describe, analyse, or efficiently exploit bio-inspired techniques for addressing the multi-agent coverage problem. This section is split into two main parts of the problem targeted in this research: Sect. 2.1 provides examples of existence work in the fields of multi-agent coverage in MRSs, whereas Sect. 2.2 shows the significant bio-inspired research work in the field of networked distributed systems in general.

2.1 Multi Robot Coverage

The concept of coverage as a metric for evaluating robotic systems which was first introduced by Gage [13]. Gage defines three basic types of coverage: blanket coverage, where its objective is to achieve a node formation which maximises the total detection area; barrier coverage, which aims to minimise the probability of undetected intrusion through the barrier; and sweep- or repetitive-coverage with the goal to cover all accessible interest points in a given environment over time, while maximising the rate of visits over all points and minimising the total distance travelled by all robots.

Blanket coverage is most common for the deployment of mobile sensor networks in an unknown environment; the sensor nodes are initially placed in a compact configuration, and the nodes try to spread out to maximise the area covered by the network. One example for such a use case is a hazardous material leak in a damaged structure. Mobile sensor nodes equipped with chemical sensors spread out from a initial position to gather information about location and concentration of the hazard. Due to the fact that the communication infrastructure could be damaged, the nodes have to ensure their own network structure even if single nodes get lost or destroyed. Many approaches in this field are based on the potential field technique first introduced by Khatib [22].

Barrier and repetitive-coverage problems originate from the computational geometry Art Gallery Problem [10] and its variant for mobile guard for mobile guards, the Watchman Route Problem [25]. Barrier coverage is the problem of placing sensors (of robots) to act as guards to protect a region from being entered by an intruder and often used in randomly deployed military applications [23]. In robotics, repetitive-coverage can be described as a problem where a team of robots has to visit multiple points of interests (POI) in a known environment frequently, to perform certain tasks. The goal of such algorithms is to keep the average visit frequency over all POIs high, while achieving a minimal total travelled distance and a balanced workload over all robots. Typical real world use cases for such problems are patrolling, lawn mowing and cleaning up chemical spills. Many approaches concerning multi-robot patrol partition the area into sub-areas divided between the robots. Inside such a sub-area, each robot applies a single robot patrol algorithm. Ahmadi and Stone [1] describe a negotiation-based approach for distributing the area between the robots and dealing with events such as addition or removal of robots to the environment. Jung and Sukhatme [19] introduce a region based approach for tracking targets in a system with mobile robots and stationary sensors.

Another important form of multi-robot coverage is terrain coverage or multi-robot exploration. It can be defined as a problem where a robot tries to visit each and every location in a continuous bounded unknown environment by avoiding obstacles and perform defined tasks [8, 12, 26]. A terrain coverage algorithm must generate a coverage path, which is a chain of motion steps for a robot, the optimal coverage path takes minimal time and guarantee to cover the entire terrain and perform the task efficiently.

Many approaches divide the environment into grid cells and explore one cell at the time until the whole area is covered. One of the first approaches was Spanning Tree Coverage (STC) which solves single robot coverage optimistically [11]. The same idea was applied by Hazon and Kaminka on a multi-robot system [17].

Batalin et al. propose a multi-robot algorithm, which spread the robots in the terrain and makes them avoid each others sensing area [3].

Several authors propose marked based approaches in multi-robot exploration, in which robots make bids on a sub-task of an exploration attempted [35, 38]. These bids are based on values such as expected information gain and travelled cost to a particular location. This approach seems to minimise the costs while maximising the benefit.

2.2 Bio-inspired Solutions

Bio-inspired solutions are often used to solve complex problems (e.g. MAC level routing, load balancing, task allocation and resource scheduling, network coverage, and emergence) in the broad research area of distributed systems with a particular interest on wireless sensor networks, many and multicore systems, swarm intelligence and multi-robot systems to make systems more reliable, efficient and self-organised. Ant colony optimisation, bee colony optimisation and artificial immune systems are three of the most commonly used biological inspirations.

Based on the observation of the collective foraging behaviour of ants, many research studies are held on Ant Colony Optimisation (ACO) on the ability of ants to converge on the shortest path from their nest to a food source to improve energy efficiency and QoS in routing. ARA [15], AntHocNet [9], ARO [37] and StiCo [30] can be listed as some of the key research in ACO.

Conforming to this swarm metaphor, Bee Colony Optimisation (BCO) was introduced by Karaboga et al. [20, 21]. Scientists are inspired by variety of different behaviours of bees: foraging behaviour in Lemmens et al. [24], Beehive protocol [36], BeeSensor [31]; bees mating procedure in [29, 34]; pheromone signalling mechanism in PS [7].

Artificial Immune Systems (AIS) are inspired by the human/ mammalian immune system. Sensitivity to detecting environmental change, and identifying the foreign/infectious agents is used, particularly for security purposes in anomaly detections. SASHA [4], DSR [32, 33], DNRS [2] are some of the significant research in the field of autonomous distributed systems inspired by AIS.

BTMS [16] uses zygote differentiation to extend the network lifetime whilst speeding up task mapping and scheduling. Homogeneous nodes begin in a default state and within time nodes differentiate themselves dynamically to perform distinct tasks according to their location.

In our previous work, pheromone signalling based load-balancing, PS [5, 7], we present a dynamic technique for Wireless Sensor Networks (WSNs) that is applied at run time at the application layer. PS is inspired from the pheromone signalling mechanism found in bees and provides distributed WSN control that uses local information only. PS is unique; unlike many load balancing approaches are applied at link or network layer [14, 18, 36] and balance only communication load, PS is an application-layer protocol and manages both computation and communication load. In [6], we extend our initial PS technique by introducing additional network elements in the form of robotic vehicles for Wireless Sensor and Robot Networks (WSRNs). We merge different subclasses of cyber-physical systems (sensors and robots) together to increase the area coverage effectively, which directly increases the service availability and extends the network lifetime by benefiting from their heterogeneity. Effective area coverage in this research is defined as achieving the highest service availability while minimising movement to conserve energy. To achieve the desired effective area coverage, we have extended our PS technique to guide robots towards the areas of the sensor field where the sensor nodes have run out of battery and are unable to provide service. The same pheromone signalling process is applied into multi-robot systems in this research and explained in detail in the next section.

3 Pheromone Signalling Based Coverage Technique

We describe our previous work on a pheromone signalling algorithm which is applied to the WSN domain. Unlike our previous work on WSNs, this paper focuses on applying the pheromone signalling technique to MRSs. WSNs and MRSs have different application requirements, and in order to indicate the application domain we change the name of the pheromone signalling technique (from PS for WSNs) to BeePCo for MRSs. The bee-inspired coverage algorithm, BeePCo, described in this section is a completely decentralised approach that has low computational overhead and direct local communication.

Changes in pheromone levels are used by many social animals to orchestrate the colony by assigning responsibilities to each individual. Roberts [28] explains the process of larvae differentiation in beehives as an example of such orchestration. Bees have developed a special hormonal system to ensure every beehive has a queen, which maintains the stability of the colony and orchestrates the behaviour of all other bees. Throughout its life, a queen bee stimulates a pheromone called Queen Mandibular Pheromone (QMP), which makes the worker bees aware of its presence as queen. This hormonal mechanism works as follows: the worker bees lick the queen bee and pass the pheromone to the others. If there is no pheromone passed through the worker bees, they will then consider the queen as dead. In that case, workers will select a larva to be fed with large amounts of the royalactin protein. That protein induces the differentiation of honey bee larvae into a queen. If worker bees keep receiving the pheromone, they will be aware that there is a queen bee to orchestrate the colony and will take no action towards building a new queen.

The proposed coverage technique is inspired by the behaviour described above. The role of a queen bee denotes a robot that is responsible for managing the execution of all service requests it receives. Throughout this paper we will refer these robots as Queen Robots (QR) and their responsibility (service) is to patrol an unknown area. The basic strategy of the algorithm is based on the periodic transmission of pheromone by QRs, and its retransmission by recipients to their neighbours. The pheromone level of each robot decays with time and with distance to the source. All robots accumulate pheromone received from other QRs and if at a particular time the pheromone level of a robot is below a given threshold this robot will differentiate itself into a QR. To make it clear, the threshold we used for this work is 10,000 for this paper - a very high value, which means all the robots are assigned to be QRs and they remain as QRs until they run out of energy. Although we do not particularly benefit from robot differentiation for this work, we still describe the differentiation process for the completeness of this work and to provide a base for our future work. In the BeePCo technique, the level of pheromone indicates how well a certain area is covered. Areas in the robotic arena that have lower level of pheromone, at a given time, demonstrate a lower robot density as opposed to other parts. This means, areas with low pheromone level have either low coverage or are not covered at all.

The proposed BeePCo algorithm consists of four parts which are executed on every robot of the MRS: two of them are time-triggered (differentiation cycle and decay of pheromone), whereas the other two (propagation of received pheromone and robotic move) occur together in a single event-triggered process. The first time-triggered part, referred to as the differentiation cycle (Algorithm 1), is executed by every robot of the MRS every \(T_{QR}\) time units. On each execution, each robot checks its current pheromone level \(h_i\) against a predefined level \(threshold_{QR}\). We set the \(threshold_{QR}\) to 10,000 for this paper - a level unreachable in practice - which means all of the differentiate into QRs and remain as QRs until they run out of energy. QRs transmits pheromone to its network neighbourhood to make its presence felt. Each pheromone dose hd is represented as a two-position vector. The first element of the vector denotes the distance in hops to the QR that has produced it (and therefore is initialised as 0 in line 4 of Algorithm 1). The second element is the actual dosage of the pheromone that will be absorbed by the neighbours.

figure a

The event-triggered part of BeePCo deals with the propagation of the pheromone released by QRs (as described above in the differentiation cycle) and received at neighbouring robots. The purpose of propagation is to extend the influence of QRs to their surroundings (neighbouring robots in the communication range). Propagation is not a periodic activity, and happens every time a robot receives a pheromone dose. The pseudocode given in Algorithm 2. Upon receiving a pheromone dose, a robot checks whether the transmitting QR is located sufficiently near for the pheromone to be effective. It does that by comparing the first element of hd with a predefined \(threshold_{hopcount}\). If the hd has travelled more hops than the \(threshold_{hopcount}\), the robot simply discards it. If not, it adds the received dosage of the pheromone to its own pheromone level \(h_i\) and propagates the pheromone to its neighbourhood. Before forwarding it, the robot updates the hd vector element by incrementing the hop count, and by multiplying the dosage by a decay factor \(0 < K_{HOP DECAY} < 1\). This represents pheromone transmission decaying with distance from the source. Once the pheromones are propagated, a move cycle is triggered. As well as the propagation cycle, move cycle also occurs when a robot receives pheromones. The move cycle illustrates the general movement behaviour of a robot as given in Algorithm 3.

figure b
figure c

If a robot receives pheromone it makes the decision of where to move by selecting a target destination in the opposite direction of the received pheromone, based on BeePCo. The moving decision of robots are based on vector addition and its pseudo code appears in Algorithm 4. Given the robot’s movement behaviour and assuming that all robots know their location, we calculate the angle of the received pheromone with the use of the sender’s x and y coordinates. To do this, we resolve the horizontal and vertical components based on the amount of received pheromone level, \(h_i\), and the coordinates of the QRs. In order to find the magnitude, we sum up all the horizontal and vertical components. In order to determine the direction of the magnitude, we take the arctangent of the magnitude and resolve x and y coordinates. This process happens on-demand as the robotic agents receive pheromone from as part of propagation cycle.

figure d

If a robot does not receive any pheromone at its destination location, it surveils this position provided it does not receive any new pheromone. This happens when robots are not in each others’ communication ranges (when they cannot receive pheromones from each other) and allows them to spread out in the area.

The second time-triggered part of the algorithm, shown in Algorithm 5 is a simple periodic decay of the pheromone level of each robot. Every \(T_{DECAY}\) time units, \(h_i\) is multiplied by a decay factor \(0 < K_{TIME DECAY} < 1\) to indicate reduced pheromone levels due to elapsed time.

figure e

Although decay and differentiation cycles have zero effect on the coverage presented in this paper, we have explicitly formalised and explained them to establish a ground for our future work and for the completeness of this research. In our future work, we will build up on these cycles and use our approach to control redundant processing and task executions as well as coverage issues in MRSs.

4 Evaluation Environment and Experimental Results

To evaluate the effectiveness of BeePCo at providing network coverage, and to establish a valid comparison between StiCo and BeePCo, we apply both algorithms on the simulation platform that StiCo is developed on. For further details about the simulation framework, we refer to [27].

The experimental work presented in this section aims to show the area coverage of the BeePCo and StiCo techniques. Area coverage in this study is defined as maximising the total area covered by the sensors of the robot(s), as defined in [30]. The algorithms are applied on a MSR of 20, 30 and 40 robots, each having a sensing and communication radius of 25 cm (simulating E-puck robots). The application arena size is set to 300 cm \(\times \) 300 cm, and the robots are initially deployed randomly in the centre of the arena, in a square 5 cm \(\times \) 5 cm region. We evaluate the three following scenarios:

  • BeePCo represents a case where a wide spread of the robots in the arena is based on bees pheromone signalling mechanism. Parameters for the algorithm is \(T_{DECAY} = 0.5\) sec, \(T_{QR} = 0.066\) sec, and \(threshold_{QR} = 10,000\).

  • StiCo represents a case where the wide spread of the robots in the arena is based on ants stigmergy principle [27].

  • MaxCo represents the optimal case where the robots’ transmission range does not intersect with each other. This scenario is a benchmark for the maximum possible coverage of deployed robots with zero surveillance area overlap within a 300 cm \(\times \) 300 cm arena. This can also be referred to as potential coverage.

Fig. 1.
figure 1

The distribution of robots in the arena using a MRS of 20 robots on StiCo and BeePCo techniques.

Full size image
Fig. 2.
figure 2

The distribution of robots in the arena using a MRS of 30 robots on StiCo and BeePCo techniques.

Full size image
Fig. 3.
figure 3

The distribution of robots in the arena using a MRS of 40 robots on StiCo and BeePCo techniques.

Full size image
Fig. 4.
figure 4

The percentage of area coverage using MRSs with 20 robots: StiCo and BeePCo.

Full size image

Figures 1, 2 and 3 illustrate how evenly the area is covered over time, using 20, 30 and 40 robots on a single run. The colour scale used for Figs. 1, 2, and 3 is from dark to light: uncovered areas are represented in black and the lighter the colour of an area, the higher the percentage of the area being covered over the total time of the experiment. The more evenly the total area is coloured, the more uniform is the distribution of the robots positions over time. These three figures do not only show the performance of the StiCo and BeePCo approaches, but also illustrates the effects of the number of the robots on the eventual coverage, i.e., more robots improve the performance. The improvement on area coverage using StiCo can clearly be seen in Figs. 1a, 2a, and 3a incrementally. Although it is slightly more difficult to see the same effect on BeePCo, Figs. 1b, 2b and 3b exhibit the same behaviour. The continuous rotation of StiCo enables an uniform distributed coverage in all three figures. On the other hand, the area coverage of BeePCo is non-uniform and mainly cluttered in the middle of the arena. This is due to the disconnected communication links. As the robots send pheromone in BeePCo, they push each other away until they are no longer connected to the network. Therefore, BeePCo is applied on a single robot as long as it possesses communication links to other robots. Once the communication links are no longer available, robots do not move in the BeePCo until they establish new connections, otherwise, they remain on their positions until they run out of battery.

Figures 4, 5, 6 and 7 are averaged over 30 independent runs to ensure statistical significance of the results on area coverage. Figure 4 illustrates the experimental results of a MRS with 20 robots comparing the performance of the StiCo, BeePCo and MaxCo approaches against each other in terms of the percentage of area coverage. As shown in Fig. 4, the StiCo approach initially spreads the robots faster than BeePCo and converges faster. In the BeePCo approach, the robots stop spreading after communication links with the other robots are broken because they are outside of the inter-robot transmission range.

Fig. 5.
figure 5

The percentage of area coverage using MRSs with 30 robots: StiCo and BeePCo.

Full size image

Similarly, Fig. 5 illustrates the experimental results on a MRS with 30 robots and compares the performance of the StiCo, BeePCo and MaxCo approaches against each in terms of the percentage of area coverage. Results show that BeePCo achieves better area coverage than StiCo technique whilst encouraging not moving once the communication network is lost. This feature of BeePCo prevents the algorithm from achieving a more evenly covered area as we explained previously in Fig. 2.

Fig. 6.
figure 6

The percentage of area coverage using MRSs with 40 robots: StiCo and BeePCo.

Full size image

Figure 6 exhibits the experimental results on a MRS with 40 robots and compares the performance of the StiCo, BeePCo and MaxCo approaches against each in terms of the percentage of area coverage as well as previous figures. In this set of experiments with 40 robots, we also observe the same behaviour: BeePCo achieves higher area coverage than the StiCo technique through out the simulation time although it does not allow robots to move once the communication network is lost.

Fig. 7.
figure 7

The percentage of area coverage using MRSs with 20, 30 and 40 robots: StiCo versus BeePCo

Full size image

In Fig. 7, the StiCo and BeePCo algorithms are compared against each other with respect to area coverage using 20, 30 and 40 robots. MaxCo illustrates the maximum possible area coverage that can be achieved using 20, 30 or 40 robots. These are plotted to show the effectiveness of the StiCo and BeePCo algorithms in comparison to the maximum possible coverage.

For both StiCo and BeePCo, we observe that the percentage of area covered increases as the number of robots increases as expected based on comparison on Figs. 4, 5 and 6. The difference in the percentage area coverage between StiCo and BeePCo considerably increases as the number of robots increases. This indicates that the pheromone signalling approach forces robots to explore more of the arena where other robots are not active and as a result, BeePCo achieves higher performance in terms of percentage of covered area in denser systems. We believe this is mainly due to the direct communication exchange as it allows the robots to more quickly spread in the environment rather than indirect communication that StiCo applies.

On the other hand, in Figs. 4, 5, 6 and 7 the percentage of area coverage starts improving faster between \(10^0\) to \(10^1\) time period in StiCo. This is due to the propagation cycle period, \(T_{QR}\), which is set as 0.06 seconds. BeePCo does not allow robots to move before the period occurs and as a result area coverage in this time period is lower than StiCo. Although BeePCo performs lower in this time period, it closes the difference in the percentage of area coverage quickly. This steep hill between \(10^1\) to \(10^2\) time period indicates that BeePCo scatters around the arena faster than StiCo. BeePCo achieves a stable period between \(10^2\) to \(10^3\) time period where robots do not move any more. Minor changes on the percentage of the coverage area in StiCo indicates that once the robots are scattered around they keep being scattered around and not getting cluttered after a certain time, which indicates a high stability in this approach too.

5 Conclusions

This paper had two major goals: providing a novel bee-inspired algorithm to address the coverage problem in MRSs (BeePCo), and evaluating the different performances and properties of BeePCo and StiCo in different scenarios. In this paper, we have described a bee-inspired robot guidance technique, BeePCo in an attempt to address multi-robot coverage problem. The multi-robot coordination and coverage is a complicated problem in itself, especially when the capacity of robots are limited. As all communications between the robots are through the wireless medium, it is essential to manage the robot coordination with a computationally lightweight algorithm that consumes less energy. Therefore, we propose to improve multi-robot coverage by guiding the robots towards the areas where the robot density is low with the use of bees pheromone signalling algorithm. Simulated experimental results on three different scales of such systems demonstrate that our proposed BeePCo technique encourages robots to spread apart from each other using the pheromone signalling process.

Moreover, we have compared our proposed bee-inspired pheromone signalling algorithm (BeePCo) against an ant-inspired stigmergic principle (StiCo) to show how these bio-inspired behaviours affect coverage on MRSs. Experimental results show that the StiCo approach starts spreading the robots as soon as they are deployed. On the other hand, in BeePCo, robots start spreading once the periodic cycles occur and therefore takes longer than StiCo. In BeePCo robots continue expanding the coverage until the robots have moved apart from each other that the communication links are no longer exist, whereas in StiCo robots keep moving until they run out of energy. The current BeePCo approach fails to improve coverage and remains static when the robots are further apart from each other as this approach requires direct packet exchange based on the local network. This results in uncovered areas in the arena as marked with black in Figs. 1, 2 and 3. The StiCo move strategy is based on the indirect pheromone communication and allows robots to explore the arena excessively.

Based on the simulated experiments in this paper, BeePCo needs to be improved to decrease the uncovered areas of the arena. We believe merging the advantages of BeePCo and StiCo may solve the MRS coverage problem which for now remains as future work. In the future, we would also like to consider the resource limitations of the robots, examining the trade off between the total distance taken by a robot and the total service availability of the MRS. From our experience in pheromone signalling algorithm on WSNs, the BeePCo algorithm can be applied to MRSs for redundancy control on top of the current coverage and connectivity procedure in a multi-objective manner. It can be easily inferred from the BeePCo differentiation cycle that each robot makes its own decision on whether and when it becomes a QR by referring to local information only: its own pheromone level \(h_i\). Although, for this paper we have allowed all robots to be QRs by setting the predefined \(threshold_{QR}\) to 10000, that is done only to focus the single objective: to tackle multi-robot coverage problem. In future, we would like to inspect the MRSs behaviour when \(threshold_{QR}\) is set to a lower and more appropriate number to actually enable robot differentiation. This should allow for highly self-organised behaviour which fits the requirements for high-density networked MRSs.