On a bio-inspired hybrid pheromone signalling for efficient map exploration of multiple mobile service robots

Abstract

This paper presents a novel bio-inspired hybrid communication framework that incorporates the repelling behaviour of anti-aphrodisiac pheromones and attractive behaviour of pheromones for efficient map exploration of multiple mobile service robots. The proposed communication framework presents a scheme for robots to efficiently serve large areas of map, while cooperating with each other through proper pheromone deposition. This eliminates the need of explicitly programming each service robot to serve particular areas of the map. The paths taken by robots are represented as nodes across which pheromones are deposited. This reduces the search space for tracking pheromones and reduces data size to be communicated between robots. A novel pheromone deposition model is presented which takes into account the uncertainty in the robot’s position. This eliminates robots to deposit pheromones at wrong places when localization fails. The framework also integrates the pheromone signalling mechanism in landmark-based Extended Kalman Filter (EKF) localization and allows the robots to capture areas or sub-areas of the map, to improve the localization. A scheme to resolve conflicts through local communication is presented. We discuss, through experimental and simulation results, two cases of floor cleaning task, and surveillance task, performed by multiple robots. Results show that the proposed scheme enables multiple service robots to perform cooperative tasks intelligently without any explicit programming.

1 Introduction

Mobile robots are increasingly being employed for tasks like floor cleaning, and surveillance in shopping malls, hospitals, and universities. To serve such large areas, multiple robots are often used for efficiency. However, introducing multiple robots also introduces the problem of programming the robots to efficiently serve the region. For example, if multiple robots are employed for floor cleaning in shopping malls or industries, each robot must explicitly be programmed to serve a specific area. On the other hand, multiple robots serving the same small area will reduce the efficiency. The areas to serve in a map may vary with time. Moreover, the number of the robots available to serve may also be dynamic, in real-world situations, as some of the robots may be charging, while some may be out of order. In case of robots used for surveillance, a robot may want other robot or robots to follow itself while chasing a suspicious person, for backup. This situation is also dynamic in terms of availability of robots, selecting the nearest robot for quick response, and selecting the same path towards a particular area as taken by the previous robot. In both the cases, explicitly programming the robots is cumbersome, and demands for a simpler scheme to accomplish the task.

The proposed work is inspired by biology where insects deposit particular chemicals called as ‘pheromones’ [10] to signal other insects of the same species to either attract or go away from a particular resource. In this paper, we term chemicals which attract other insects as ‘pheromones’, and this signalling mechanism can be found in honeybees, ants, wasps, and termites [11]. Ants use pheromones to attract the population to food source, and bees to attract the population to an empty hive [25]. There are other type of pheromones called anti-aphrodisiac pheromones with opposite behaviour, i.e. they turn away other insects from a resource. They are used to raise alarm and claiming territory. We denote anti-aphrodisiac pheromones as ‘anti-pheromones’ in this paper.

Fig. 1

System architecture

Previous works on pheromone signalling in robotics has been mainly concentrated to mimic the swarm behaviour using attractive pheromones [14] with application in process control [3], communication [6, 7], and to mimic swarm behaviour [17]. Tasks like exploration and surveillance require that multiple robots disperse themselves in the region to cover maximum possible area. A multi-agent exploration algorithm has been proposed in [4] in which a coverage algorithm has been proposed with a pheromone barriers. The larger the pheromone value, stronger is the barrier for other robots. Similar dispersive behaviours which employ repellent virtual pheromones have been proposed in [15, 16] to survey a disaster site. Other works which uses repelling behaviour of pheromones includes [21] which proposes solutions for multi-agent rescue mission, and [1, 2, 18] for robot surveillance. An extensive review of research related to pheromone signalling and swarm robotics can be found in [12, 23, 27].

The proposed work incorporates the advantages of both the ‘repelling anti-pheromone’ signalling mechanism and the ‘attracting pheromone’ mechanism which is presented in a hybrid framework. The novel contributions of the proposed work are:

• Integration of pheromone signalling with EKF Localization: an integrated algorithm is presented in Sect. 5 which allows efficient ‘area capture’ and ‘sub-region capture’ by robots so that they can work efficiently without interruption from other robots (Sect. 4.2). Service robots like cleaning robots or patrolling robots are expected to work in terms of areas of the map like rooms, corridors, and halls, instead of direct spatial coordinates like in [4, 5]. Hence, the proposed ‘area capture’ and ‘sub-region capture’ translates to efficient task distribution in which robots can work without interruption. Once an area has been captured by a robot, it is also efficient in terms of reducing the localization cost as explained in Sect. 5.

• Modelling Robot’s uncertainty in pheromone deposition: localization is very important for mobile robots to ascertain their position in the region. Many previous works like [5, 15] assume a perfect robot localization which is generally not true as the exteroceptive sensors attached on the robots are prone to errors, and this uncertainty needs to be modelled to estimate the state of the robot [19, 20]. The proposed work takes into account the uncertainty in robot’s position for pheromone deposition (Sect. 2). No or less pheromones are deposited if the uncertainty in localization is high. On the other hand, pheromones are deposited with confidence if the localization is good.

• Node representation for reduced search space and efficiency: in previous works like [4] or [5], pheromones are deposited anywhere in the map. Therefore, the search area to find the total pheromones is nearly quadratic ($W \times H$, where W and H are the width and breadth of the map, respectively). However, node representation (described in Sect. 3) drastically reduces the search space as pheromones are deposited only across the (n) nodes of the map, reducing the search space from quadratic ($W \times H$) to linear $2n \times \overrightarrow{m_{dir}}$, where ${\overrightarrow{m_{dir}}}$ is the maximum number of diverging directions across a node. This is also efficient energy-wise as less data needs to be transmitted with node representation. Work by [9] reports that among sensing, computing, and communication, a considerable amount of the energy is consumed during communication than computation. Moreover, conflicts (Sect. 5.1) are resolved and obstacles are avoided using only local communication.

Table 1 Signal notation and behaviour

We tested the proposed framework in real environment with real robots. The results are presented and discussed in Sect. 6. To test the robustness of the method in complex environment and large robots, we developed a simulation software. Both anti-pheromone signalling (Sect. 6.1) and pheromone signalling (Sect. 6.2) experiments in real and simulated environment are described in detail. Finally, Sect. 7 concludes the paper.

Fig. 2

Sub-mapping, node representation, and actual environment. a Map divided into sub-regions to serve with nodes along passages, b Node (green) with four diverging vectors and anti-pheromone values, and a terminal node (red), c Actual environment, d Robots exploring the map (colour figure online)

Fig. 3

Anti-pheromone deposition. a Initial condition with no anti-pheromones on nodes, b Robots $\textit{R}_1$ and $\textit{R}_2$ depositing anti-pheromones on nodes, c A particular node state in future with $-\infty$ values on terminal nodes. d,e Division into sub-regions. d Entire sub-region blocking, e Division of a sub-region further into sub-blocks

2 Pheromone and anti-pheromone representation

The system architecture (Fig. 1) comprises of multiple robots (${\textit{R}}_1, {\textit{R}}_2, \ldots , {\textit{R}}_n$) which are connected to the central server, to each other robot, via. a local network. The proposed system uses numerical values to represent chemicals as virtual pheromones. The entire map of the environment is represented in a ($W_\mathrm{e} \times H_\mathrm{e}$) grid, where $W_\mathrm{e}$ and $H_\mathrm{e}$ represents the width and height of the environment, respectively. A 2D signalling matrix ($M_\mathrm{s}$) of equal dimensions ($W_\mathrm{e} \times H_\mathrm{e}$) which overlaps with the grid map is used as a signalling matrix where virtual pheromones can be deposited by the robot on any place [$(x,y),~0 \ge x > W_\mathrm{e},~0 \ge y > H_\mathrm{e}$] of the map. Practically, this is achieved by setting the value of the appropriate row and column of the matrix ($M_\mathrm{s}[x][y]$) with the signalling value. The 2D signalling matrix is stored in the central server. We represent pheromones and anti-pheromones using the notations shown in Table 1. Pheromones have positive values in the signalling matrix ($M_\mathrm{s}[x][y]$) represents a pheromone ($P_h$) deposited at that location. The strength of the attractive force ($F_\mathrm{a}$) is directly proportional to the pheromone signal value at a location (x, y).

$$\begin{aligned} F_\mathrm{a} \propto f_p(P_h,M_\mathrm{s},x,y) \end{aligned}$$

(1)

Anti-Pheromones ($A_p$) have negative values in the signalling matrix ($M_\mathrm{s}[x][y]$) at a location. The strength of the repulsive force ($F_\mathrm{r}$) is directly proportional to the value of the anti-pheromone signal value ($A_p$).

$$\begin{aligned} F_\mathrm{r} \propto f_a(A_p,M_\mathrm{s},x,y) \end{aligned}$$

(2)

A zero value in signalling matrix represents that the corresponding area has not yet been visited by any of the robots.

We denote the sensor range of the laser range finder used in the experiments by $z_{rng}$. Pheromones can be deposited on the top of already existing pheromones at any position q ($\xi _{q}(t)$). We utilized a modified pheromone model described in [13]. Unlike [13] which uses a fixed number of pheromone deposition by a robot, we incorporate a probabilistic model in which the amount of pheromone deposition depends upon the uncertainty of robot’s state while localizing itself. The amount of pheromones or anti-pheromones deposited by the ith robot $\textit{R}_i$ at location q and time t is given by:

$$\begin{aligned} \Delta _q^{i}(t) = (1 - \xi (t-1)) \Psi _q^{i}(t) \end{aligned}$$

(3)

$$\begin{aligned} \Psi _q^{i}(t) = {\left\{ \begin{array}{ll} \varrho _t e^{\dfrac{(q_{ix} - q_x)^2 + (q_{iy} - q_y)^2}{\lambda ^2}} &{} \text {if} \quad q_{x} \in z_{rng} \\ 0 &{} \text {otherwise} \end{array}\right. }, \end{aligned}$$

where $(q_{ix},q_{iy})$ is the coordinate of the $i$th robot. $\varrho$ is a non-constant probabilistic factor which controls the amount of pheromone deposition at a location based on how good has the localization of the robot been achieved, and $0 \le \varrho _t \le 1$. An integrated pheromone signalling in Extended Kalman Filter (EKF) landmark-based localization is explained in Sect. 5. The algorithm is given in Algorithm 1 which estimates the state $\mu _t$ (i.e. position x, y and orientation $\theta$ ) and the uncertainty associated with this state estimation $\Sigma _t$, at time t for a robot. The factor $\varrho _t$ depends on this uncertainty as,

$$\begin{aligned} \varrho _t \propto \dfrac{1}{\Sigma _t}. \end{aligned}$$

(4)

In other words, if the localization is good, more pheromones are deposited. However, if the robot fails to localize itself, less or no pheromones are deposited. $\lambda$ specifies the dispersion of the pheromones or anti-pheromones. In the presented work, the value of dispersion factor $\lambda$ is chosen to affect only a very limited area around the robot’s current position. Concretely, if the entire area is divided into micro grids of size $\Delta _x \times \Delta _y$, factor $\lambda$ is chosen so that maximum number of pheromones are deposited in the current grid, and only a tiny fraction in the nearby micro-grids which are directly touching the current grid. The total pheromones are given by,

$$\begin{aligned} \Delta _{q} = \Delta _{(qx,\,qy)} =\sum _{i=-1}^{1}\sum _{j=-1}^{1} \Delta _{(qx+j,~qy+i)}(t). \end{aligned}$$

(5)

Pheromones are not fixed and evaporate with time. The rate of evaporation of pheromones is given by $\rho$, and the total amount of pheromones evaporated at position q and time t is given by the function,

$$\begin{aligned} \Phi (t) = \rho \xi _{q}(t) \end{aligned}$$

(6)

Considering the evaporation of pheromones, the total pheromones on position q at time t is,

$$\begin{aligned} \begin{array}{ll} \xi _{q}(t) &{}= (\xi _{q}(t-1) - \Phi _{q}(t-1)) \\ &{}\quad + \sum \limits _{i=-1}^{1}\sum \limits _{j=-1}^{1} \Delta _{(qx+j,~qy+i)}(t) \end{array} \end{aligned}$$

(7)

The pheromones are only deposited on the side of ‘nodes’ which are described in the next section. This is unlike the traditional methods of pheromone deposition in which the pheromones can be deposited anywhere in the map.

3 Node representation of path

The spatial environment is shown in Fig. 2a, and is divided into several sub-regions represented by letters ($A_1, A_2, A_3 \ldots$). The pathways to different sections of the map are represented in the form of a graph with nodes.

A node is shown in Fig. 2b. It comprises one or more vectors (links) diverging from the centre towards the passages of the map. Figure 2b shows four such vectors diverging from the node. A robot deposits anti-pheromones on the diverging vectors while it traverses them. There are two types of nodes: (a) Terminal Nodes: which represent the terminal pathways of the map shown in red colour in Fig. 2b. Robots deposit a negative infinity value on the terminal nodes when it traverses it. (b) Intermediate Nodes: which are not terminal.

4 Anti-pheromone mechanism for map exploration

4.1 Path selection

Initially, the signalling matrix is set to zero, representing no pheromones. The initial position of the robots could be anywhere in the map, and they are not assumed to start from the same location. Figure 3a shows the initial state of the nodes of the map with two robots ${\textit{R}}_1$ and ${\textit{R}}_2$. When robot ${\textit{R}}_1$ encounters node $\text {N}_1$ which has 3 diverging vectors, it calculates from the signalling matrix ($M_\mathrm{s}$) that none of the three diverging paths have been traversed by any of the other robots. Path selection of ${\textit{R}}_1$ is according to the following objective function:

$$\begin{aligned} \begin{array}{ll} \text {path} & = \max _{P_h} (g(N_i)) \\ & = \max _{P_h} (\{\overrightarrow{N_{i}a}:0\},\{\overrightarrow{N_{i}b}:0\},\{\overrightarrow{N_{i}c}:0\}) \end{array} \end{aligned}$$

(8)

The function $g(N_i)$ takes a node value $N_i$ and returns a dictionary containing pairs of the vector path and pheromone values deposited on the diverging vectors of that node, as key-value pairs ($\{key:value\}$). Then, a path representing the maximum pheromone value is chosen. In case of $\text {N}_1$, since there are no pheromones deposited by any of the previous robots, all the three diverging paths have pheromone count of zero. In case of same pheromone count, a random path is selected out of the paths returned by the function g. Hence, robot ${\textit{R}}_1$ takes a random path $\overrightarrow{N_{1}c}$, and deposits an anti-pheromone by decreasing the current value over $\overrightarrow{N_{1}c}$ by 1.

For robot ${\textit{R}}_2$ which initially followed robot ${\textit{R}}_1$, the condition is different at node $\text {N}_1$. Since, path $\overrightarrow{N_{1}c}$ is already taken, a random path $\overrightarrow{N_{1}b}$ is selected between $\overrightarrow{N_{1}b}$ and $\overrightarrow{N_{1}a}$, as both of them have the same maximum pheromone count. ${\textit{R}}_2$ deposits anti-pheromone and proceeds as shown in Fig. 3b. If a robot $\text {R}_i$ takes a path and it encounters a dead-end, it deposits an extremely large value of anti-pheromones ($-\infty$) on that side of the node. The path selection objective function makes sure that paths with larger anti-pheromone values are not prioritized. This mechanism checks that paths leading to terminal points of the map ($\overrightarrow{N_{2}e}$, $\overrightarrow{N_{2}f}$) which have already been selected by other robots as shown in Fig. 3c are not selected by other robots.

Similarly, other robots keep on exploring the map by taking the maximum of the anti-pheromone values deposited across the nodes. Since the anti-pheromones have negative values, the overall result is that the robots take the paths which have not been visited, or which have been least visited. Notice that this is opposite to that of pheromone trailing mechanism in ants and other biological species, in which, ants keeps depositing pheromones and other ants follow them, ultimately optimizing their path towards the food source. However, anti-pheromone mechanism makes sure that robots take as much of diversified paths as possible, and do not just follow each other whenever possible. This is desired for tasks like cleaning and patrolling where robots must explore diverse areas of the map.

4.2 Area capturing and area selection

This section discusses area capturing and area selection by robots.

4.2.1 Sub-region selection and capture

At the start of the job ($M_\mathrm{s} \equiv 0$), each robot $\text {R}_i$ moves to its nearest possible region in the map. The path from the current location of the robot to the nearest region is calculated by $A*$ algorithm [8] or $D*$ algorithm [22]. Multiple robots starting from the same location of the map approach the same nearest area. However, this is controlled via. the node mechanism explained in Sect. 4.1. The first robot to approach the nearest area would deposit an anti-pheromone over the node, which would force other robots to explore different areas of the map. Once a robot enters the nearest sub-block, it deposits an anti-pheromone on the sub-block, which is achieved by altering the values of the signalling matrix to ($-$1) which represents the sub-region. This further prevents obstruction by other robots to enter the same sub-block. The sub-area is, in other words, ‘captured’ by the robot, and robot can perform its task (say cleaning) inside the sub-block. After finishing the job in the sub-block, the robot moves to the next nearest sub-block with the maximum anti-pheromone value, which is given by the following objective function,

$$\begin{aligned} \text {target}= \max _{P_h}~ \Big (h(\text {map, current position})\Big) \end{aligned}$$

(9)

The objective function ensures that the next target of the robot is the nearest sub-area of the map which has not yet been captured by other robots. Such a scheme is depicted in Fig. 3d.

4.2.2 Region blocking and capture

If the sub-area of the maps are large enough, they are further divided into sub-blocks. In this case, the robot does not ‘capture’ the entire sub-region but only a particular block of it. This is achieved in the same way by decreasing the values of the signalling matrix representing that particular block. However, sub-blocking would be inefficient if the area is too small. Sub-blocking is performed by taking the dimensions and capabilities of the robots, and dimensions of the sub-region. A blocked approach is shown in Fig. 3e. The areas in red are the sub-block of the sub-regions which have been captured and anti-pheromones deposited, whereas the blue areas represent the ‘un-captured’ sub-regions and sub-blocks which are yet to be explored.

4.3 Pheromone mechanism

There are scenarios where a robot would like to ‘attract’ other robots in a region for collaborative task completion. In such situations, the robot must relinquish the ‘captured’ sub-region. This is achieved by depositing a pheromone with a large positive value for the respective region of the 2D signalling matrix. Regions with positive values are more attractive to the robots according to Eq. 9. For example, a surveillance robot chasing a target person would like other robots to follow it for backup. In that case, the surveillance robot would keep on depositing positive pheromones across all the traversed nodes. A positive pheromone value would attract other robots to follow the same path, according to Eq. 8.

Thus, a robot traverses nodes and visits regions of map, both of which have pheromones or anti-pheromones (or none) deposited. The net force for a robot to travel from one point to other via nodes to explore the map is given by,

$$\begin{aligned} \max _{P_h}~ \Big (g(N_i)~\cdot ~h(\text {map, current position})\Big ). \end{aligned}$$

(10)

5 Integration of pheromone signalling with landmark-based EKF localization

Service robots must accurately localize themselves in the map which is an integral part of Simultaneous Localization and Mapping (SLAM) [24]. Extended Kalman Filter (EKF) [24] has been a de-facto standard for robot localization technique. EKF is fundamentally based on Bayes filter, in which, the state of the robot ($x_t$) and the environment are expressed through conditional probability distributions. Bayes filter applies two successive rules of prediction and update to determine the system state. With control $u_t$ at time t, the predicted belief $\overline{bel(x_t)}$ is calculated just before, and corrected belief $bel(x_t)$ is calculated just after the sensor observation ($z_t$), respectively, as,

$$\begin{aligned} \begin{array}{ll} (\mathrm{Predict})~~ \overline{\mathrm{bel}(x_t)} &{}= P(x_t | z_{1:t-1},u_{1:t}) \\ (\mathrm{Update})~~ \mathrm{bel}(x_t) &{}= P(x_t | z_{1:t},u_{1:t}). \end{array} \end{aligned}$$

(11)

EKF handles the linearity assumption using Jacobians and Taylor expansion, and assumes a Gaussian noise distribution. As shown in Algorithm 1, $G_t$ and $V_t$ are Jacobians of motion function with respect to state and control, respectively, where $\omega _t$ is the angular velocity of the robot. Control noise and measurement noise are expressed as covariance matrices $M_t$ and $Q_t$, respectively. Similarly, the predicted and corrected robot state, and the covariances associated with them are expressed as $\bar{\mu _t}$, $\mu _t$, $\bar{\Sigma _t}$, and $\Sigma _t$, respectively. In traditional EKF, whenever a robot encounters a landmark, it compares it with all the registered landmarks for localization [24]. However, the proposed algorithm integrates the pheromone mechanism and the maximum likelihood check for an encountered landmark is done only with appropriate landmarks and not all. This is shown between lines 9 and 20 of Algorithm 1. An area $\text {A}_i$ of a map has a set of landmarks represented by $\mathrm{LM}_i$ given by a function $l~(\text {A}_i)$. The total area (A) and the total number of landmarks in the map (LM) are, therefore,

$$\begin{aligned} A = \int _{i}^{~}A_{i}, ~~~~~\mathrm{LM} = \int _{i}^{~}l(A_{i}) \end{aligned}$$

(12)

A robot $\text {R}_i$ which captured the area $\text {A}_i$ with a set of landmarks $\mathrm{LM}_i$, checks only the landmarks give by $l~(A_i)$, and not the entire set of landmarks. The robot can omit comparing the measured landmarks against registered landmarks that belong to other areas which have been captured or not, improving EKF landmark matching by a factor of $\eta _1$ given by Eq. (13).

Similarly, robots which have not yet captured any region may omit comparing the measured landmark against the set of all landmarks which belong to regions which have been captured by other robots. If $\text {A}_c$ represents the set of all areas which have already been captured, improving EKF landmark matching by a factor of $\eta _2$,

$$\begin{aligned} \eta _1 = \frac{\int _{i}^{~}l~(A_{i})}{l~(A_{i})}, ~~~\eta _2 = \frac{\int _{i}^{~}l~(A_{i})}{\int _{i}^{~}l~(A_{i})~ - ~\int _{c}^{~}l~(A_{c})}. \end{aligned}$$

(13)

5.1 Collision avoidance and resolving conflict amongst robots

Region blocking and capture explained in Sect. 4.2, allows a large area to be divided into sub-regions. Different robots can serve each sub-region without interfering with the work of other robots which have other sub-regions to work on. However, if the region is too small, and only a single robot is sufficient enough to serve it, there might arise a situation in which two robots try to capture the same region, and conflict needs to be resolved in such situations. In the proposed work, the conflict is resolved by local communication explained below.

As explained in the system architecture, the robots can communicate with the server and also amongst themselves. At the start of the task, each robot ($R_i$) is given a task-id ($T_{i}$), and priority ($P_{i}$). The robots also keeps a track of the available battery power ($B_i$), total areas captured ($C_i$), and sensor specifications. When two or more robots try to capture an area, they exchange messages in JSON format which comprises of these parameters. A sample JSON message is shown in Listing 1.

The robot with the highest priority gets access to the area. If the priorities are equal, the battery power is considered, and the robot with sufficient power to serve the area gets prioritized. This is followed by checking $C_{i}$ which is an indication of the total number of areas already served by the robot. The robot with lower $C_{i}$ value gets prioritized as it has served lesser areas. After that, robot specifications are checked, and the robot with better specifications get prioritized. In the worst case, if all the values are same, robot with smaller id is prioritized. Notice that, which parameter is prioritized is not a study of this paper and other conflict resolving schemes can also be applied in the proposed framework as robots can communicate with each other.

Table 2 Table showing sub-regions captured by robots at particular times

Fig. 4

Test environment. a Environment’s grid map, b Service regions (green) from A to E, and docking station (orange), along with passage showing nodes. c Comparison of time taken by robots by anti-pheromone signalling and shortest path method with conflict resolve (colour figure online)

Robots rely on attached sensors for local obstacle avoidance. Notice that in many previous works related to virtual pheromones, once a robot has avoided static obstacles like chairs, or boxes, other robots can follow the pheromone trail left out by the previous robot. Thus, robots can save computation related to obstacle avoidance at the cost of frequent communication with the server to keep a track of pheromones. However, in the proposed scheme, since the pheromones are deposited only on the nodes, each robot needs to perform obstacle avoidance using local sensors. However, it is efficient in terms of communication.

6 Results and discussion

This section discusses the results of the experiments performed using the proposed mechanism. We performed experiments in real environment with robots, and simulation with large number of robots to test the robustness of the proposed scheme. Figure 4a shows the map of the environment (Fig. 2d) of the passage around our laboratory used in the experiment. Figure 4b shows the actual 2D grid map of the environment constructed using Lidar sensor. The approximate length of the environment is about 25 m and width is about 5 m. The environment has been overlaid with green and yellow blocks to mark out the target regions for the robot to serve. The green regions have been labelled A, B, C, D, and E. They are the regions where service robots must perform cleaning or patrolling. The yellow region marks the docking point and starting location of all the mobile robots. Figure 4b also shows the nodes along the passage which have been marked as $n_1, n_2, \ldots , n_{14}$. The terminal nodes are shown in red, whereas the non-terminal ones are shown in green, and the links in white.

Two experiments were performed to test the proposed signalling mechanisms of anti-pheromones, and pheromones, in the environment shown in Fig. 4a. The robots (shown in Fig. 2e) used in the experiment were: (1) Pioneer P3-DX equipped with URG 04LX laser range sensor, and (2) Kobuki’s Turtlebot which is equipped with Microsoft Kinect sensor. The robots were programmed and controlled using the Robot Operating System (ROS), and could perform inter-node communication between the robots and the server. The central server comprised of 64 bit Ubuntu 14.04 operating system. The map of the environment (Fig. 4b) was pre-built and was made available to all the robots. Apart from tests in real environment with two real robots, we also performed simulated tests with three, and four robots, to test the robustness of the proposed method. The service regions in ascending order of distance separation from the docking station are: B, C, A, D, E. In other words, service region B is nearest to the docking station, and region E is farthest from the docking station, in that order. All the service regions have approximately the same area, except area A which is twice the size of B. Since, Pioneer 3DX and Turtlebot used in the experiment are not actual cleaning robots, they were programmed to manoeuvre the captured region for a specific work time ($T_\mathrm{w}$).

Fig. 5

Final node configuration. a Final node configuration in anti-pheromone experiment with anti-pheromones shown in red, b Final node configuration in pheromone experiment with pheromones shown in blue (colour figure online)

6.1 Anti-pheromone experiment

Fig. 6

Improvement in landmark matching using proposed method for capture and un-captured area case with and without the proposed method

In case of two robots ($R_1$ and $R_2$), they start from the docking station and $R_1$ proceeds towards the nearest region B, through nodes $n_6$ and $n_5$ depositing anti-pheromones on them. $R_2$ proceeds and encounters node $n_6$, where it finds an anti-pheromone deposited on the left vector, and takes a right turn towards region C, depositing anti-pheromones. Both the robots capture the regions by depositing anti-pheromones. After $T_\mathrm{w}$ time, $R_1$ finishes the task and moves towards the nearest region A which has no pheromones. Similarly, $R_2$ moves towards D. $R_1$ takes twice the time to serve area A. In addition, region E is nearest to $R_2$ and hence $R_2$ moves to serve region E. The movements of the robots in specific times is given in Table 2. Table 2 also shows the area captured by robots in case of three, and four robots. Figure 5a shows the final status of the deposition of anti-pheromones on the nodes.

Fig. 7

Simulation of map exploration using the proposed method with 8 robots. Map is shown with skeleton path, signalling matrix, area capture matrix and robots marked from numbers 1 to 8. a At time = 7 s, b At time = 19 s. Regions A and D are captured by robots $\textit{R}_1$ and $\textit{R}_2$. c At time = 30 s. Regions A, D, and B are captured by robots $\textit{R}_1$, $\textit{R}_2$, and $\textit{R}_3$, respectively. d At time = 49 s. The entire area has been explored and captured

Figure 4c shows the time taken by robots to serve the areas shown in Fig. 4b with varying number of robots using anti-pheromone signalling and shortest path with conflict resolve method. In simulation, the robots were programmed to serve the nearest area through a path which was calculated by $A*$ algorithm [8]. It can be seen that anti-pheromone signalling mechanism takes much less time to complete the task and outperforms the conventional shortest path method. In the conventional shortest paths method, the robots are governed only by the shortest distance mechanism, and multiple robots end up in the same region. Thereafter, conflict needs to be resolved as to which robot will serve (clean) the area and a lot of time is spent in resolving this conflict. Whereas, the anti-pheromone signalling mechanism prevents multiple robots in the same regions (by region capture) and directs the robots to the least traversed paths. It can be seen from Fig. 4c that in case of four robots, time taken to complete the task in conventional shortest path method is almost similar to the time required by two robots with anti-pheromone signalling mechanism. This is because, without region capture, multiple robots end up in the same regions and more time is spent in resolving the conflicts between the robots. Figure 6 shows the improvement in landmark matching using the signalling mechanism with varying number of landmarks for area captured and un-captured case. Figure 6 reflects data with 40 % of total landmarks captured (hence, 60 % un-captured), and 1.65 ms required for matching single landmark.

We build a simulation framework which can load complex maps, and test the proposed method with large number of robots. A snapshot of the simulation is shown in Fig. 7a, which shows the map of the simulation environment, signalling matrix, area capture matrix, skeleton path in red, and eight cleaning robots (marked $\textit{R}_1$ to $\textit{R}_8$). None of the robots is explicitly programmed to explore a particular area. Instead, they explore the environment using the proposed anti-pheromone signalling on nodes. There are eight regions in the loaded map which are same as the number of robots. The skeleton map was generated using the technique of skeletonization proposed in [26]. One robot is sufficient to clean each of the regions except region C which requires two robots. Sub-region division is enabled by setting the value of maximum robots in the region (Max-R) to 2, as shown in Fig. 7a. Initially, none of the regions are captured as shown in Fig. 7a. Figure 7b shows the situation at 19 s of simulation, at which regions A and D have been captured by robots $\textit{R}_1$ and $\textit{R}_2$ as shown in the area capture matrix. The captured marks have been indicated by a triangle $(\blacktriangle )$. The corresponding pheromone values in the signalling matrix are indicated by the letter ‘c’ which is a large value of anti-pheromone, to capture the region. Similarly, ‘-inf’ indicates an infinite value in the signalling matrix, which is an indication of dead-ends in the map. In the loaded map, only four directions across a node (up, down, left, and right) have been considered but can easily be extended. The colours of the anti-pheromones have no significance and are only shown to clearly indicate the respective robot which deposited it. It is assumed that robots can localize well in the environment. Consider Fig. 7c which shows the state of the robots at time 30 s. It can be seen that the robot $\textit{R}_6$ takes a right turn at node n1 by travelling towards a value of lower anti-pheromones (node n1 has $-\infty$ on left, and $-c$ in the up direction as region is captured). Similarly, robot $\textit{R}_5$ moves towards node n6. Figure 7d shows the final configuration of the simulation in which all the robots have captured the areas correctly, and started cleaning. Tables 3 and 4, respectively, show the final configuration of pheromone matrix, and area capture matrix in simulation.

Table 3 Table showing final configuration of pheromone matrix in simulation of Fig. 7

Table 4 Table showing final area capture matrix in simulation of Fig. 7

6.2 Pheromone experiment

To test the (+ve) pheromone mechanism, $\textit{R}_1$ was instructed to go to region E depositing pheromones across nodes. Robot $\textit{R}_2$ was not given any instructions, but just started after $\textit{R}_1$. According to the pheromone mechanism explained in Sect. 4.3, $R_2$ successfully followed $R_1$ sensing pheromones on nodes, without any explicit instructions. This confirmed pheromone signalling for tasks like robot surveillance where a robot may need other robots to follow it for backup. Figure 5b shows the final configuration of nodes with pheromones.

7 Conclusion

This paper proposed a hybrid pheromone and anti-pheromone signalling mechanism for map exploration by multiple service robots. The hybrid mechanism involves anti-pheromones which repel robots across diverse portions of map, whereas pheromones attract robots to particular regions. A novel pheromone deposition scheme which takes the uncertainty of the robot’s localization is proposed. Unlike many previously proposed techniques which use a constant model for pheromone deposition, in this work, the amount of pheromone deposition depends on how well is the robot able to estimate its position from the sensors in the map. This ensures that pheromones are not deposited on unwanted locations if localization fails. The paper proposed a node representation of the map where robots deposit pheromones. This reduces the search space for signalling matrix and is communication efficient. The proposed signalling mechanism is integrated with EKF localization and an algorithm is presented. This integration allows robots to capture areas of sub-areas of the map which enables the robot to work without interference from other robots. The paper also discussed how localization itself improves with the integrated pheromone signalling. Robots rely on local communication to resolve conflicts. The proposed method is presented in both simulated and real environment with variable number of robots. Results with both anti-pheromone and pheromone signalling show that the proposed mechanism can be effectively used to explore the map using multiple robots, for tasks which require diverse map exploration, or collaborative performance, without any explicit programming. In future, we plan to extend the work by incorporating fuzziness of work done by robots, into the system.