A Cellular Automata Model with Repulsive Pheromone for Swarm Robotics in Surveillance

Abstract

This study proposes an inverted ant cellular automata (IACA) model for swarm robots performing the surveillance task. A new distributed coordination strategy is described here, which was designed with a cellular automata-based modeling and using a repulsive pheromone-based search. The environmental structure is well-known to all robots and their current positions are shared by the team. Besides, they communicate indirectly through the repulsive pheromone, which is available to each robot as an information about its neighborhood. The pheromone is deposited at each time step by each robot, over its current position and neighborhood cells. The pheromone is also evaporated as the time goes by. All next movement decisions are stochastic giving a non-deterministic characteristic to the model. Simulation results are presented, by applying the proposed model to different environmental conditions.

1 Introduction

Each member of a multi-agent system must be capable to achieve its objectives autonomously adapting it-self to environmental changes. An intelligent global behavior is desirable, which can be generated by modeling each individual agent of the system and the interactions among them [1]. It is well-known that a distributed and coordinated behavior can emerge from individual interactions in complex systems. In this context, there are several works that have investigated the application of cellular automata-based models to swarm robotics [2, 3]. Swarm systems are characterized by a global dynamics reflecting some synergy among the swarm members [4]. Swarm robotics models that mimic the natural collective behavior have being recently investigated, such as the pheromone interaction employed by ants colonies (ACO) [1] and the communication between glows-worms lights [5]. In this context, some works use a combination of cellular automata (CA) and ACO [6] and others use IAS (Inverted Ant System) [7]. The IAS [7] is a technique based on the biological ants behavior that uses the indirect global communication denominated stigmergy. Unlike ACO [8], that provides a chemical attraction between agents through the pheromone interaction, an opposite behavior emerges in IAS since it employs a repulsive pheromone type. This kind of pheromone is also observed in natural ants and it is used to indicate risk or danger. Stigmergy is considered one of the factors that decisively contributes to enlarge the capabilities of a single ant. Colonies use the stigmergy to coordinate their activities in a distributed way [9]. There are many coordinating tasks being investigated in swarm robotics, such as, foraging [10], search and rescue [11]. Another relevant task in robotics is surveillance [12], which consists in monitoring the behavior, the activities, or other environmental changing information, protecting people or objects [7, 13, 14]. Surveillance involves environmental exploration and the area must be covered by the robots. Therefore, the swarm uses cooperation and communication strategies to cover the environment, in a reasonable period of time.

In the present work, a navigation model called IACA based on cellular automata modeling and inverted ant pheromone communication was proposed for robots performing the surveillance task. The environment is modeled by a lattice of square cells composed by two layers. Simulations were carried out to evaluate the model in different situations and environments. They were made to (i) measure the time taken by the robots team to perform the surveillance task; (ii) analyze the evaporation process; (iii) analyze the coverage and exploration. By simulation results it was possible to observe that the resultant behavior returns an efficient task execution and the inverted pheromone employment causes scattered paths with low or none collisions.

2 Model Description

Initially, a two-dimensional map representing the environment is constructed. It is divided in square cells and the resultant lattice has two layers. The first layer is the pheromone lattice where the cell’s pheromone amount is stored. A continues state is assigned to each cell of the pheromone lattice. The state value is between 0 and $\tau _{max}$ for the non-wall cells cells. Additionally, a value representing $\infty$ is assigned for all wall cells. The second layer is the physical lattice, in which the current robots’ positions and the walls cells are represented. A discrete state is assigned to each cell of the physical grid. There are three possible values: free, wall and robot. Figures 1(a) and (b) show two examples of physical grids, where the walls cells are represented in gray, the free cells are represented in white and the cells with red circles represent the current robots’ positions. One robot in the grid cannot overlaps another or a wall cell. The pheromone layer relative to the environment $E_2$ is shown in Fig. 1(c).

Fig. 1.

Rooms $20 \times 30$ size. (a) Environment $E_1$ with 7 rooms. (b) Environment $E_2$ with 6 rooms. Four robots are represented in red in each environment and they are performing the surveillance task. (c) Pheromone grid. (Color figure online)

The IACA model is divided in two levels: one is related to the individual robot’s behavior and the other is related to the team’s global behavior. The team’s behavior is related to robot-robot and environment-robot interactions.

2.1 Individual Behavior

The behavior model of each robot can be described by a four finite state machine (FSM), as shown in Fig. 2. In IACA model, the robots start their movements at time step 0 and the task is finished (when the robots stop their movements) after a predefined number of time steps (T).

Fig. 2.

Individual behavior represented by a finite state machine adapted from [7].

The pheromone detection state in the FSM represents the robot’s pheromone reading process. The current amount of pheromone in each cell $x_{ij}$ is a resultant from the previous pheromone deposition due to robots’ steps followed by an evaporation process. This reading comprises the Moore neighborhood cells considering the robot’s vision radius $r_v$. The robot access all the neighborhood pheromone values $x_{ij}$, which size is defined as $m=(2r_v+1)^2$. The robot access the $x_{ij}$ values from its neighborhood cells to make the next movement decision.

The decision process is represented by the next cell choice, which will drive the next robot’s movement. This choice is based on the amount of the repulsive pheromone deposited in the neighborhood cells. The amount of pheromone in a determined cell $x_{ij}$ will define the probability $P(x_{ij})$ of this cell to be chosen in the next time step. If the pheromone amount is big, then the probability is low. On the other hand, if the cell has a small amount of pheromone, it has a high probability to be chosen. The total pheromone deposited in the neighborhood cells as a whole is given by $\rho _{\max }^t=\sum ^m_{k=1} x_{ij}^t$. Equation 1 shows the function used to determine the probability of each cell $x_{ij}$ of the current neighborhood to be the next robot position in the time step $t+1$. Using this equation, a stochastic choice is made to decide the next position.

$$\begin{aligned} P(x_{ij})^{t+1} = \frac{\rho _{\max }^t- x_{ij}^t}{\sum ^m_{k=1} \rho _{\max }^t- x_{ij}^t} \end{aligned}$$

(1)

Each robot deposits pheromone over its current and neighborhood cells, to signalize its presence to the other members of the swarm. The pheromone deposition state in the FSM represents the process in which the robot increases the amount of pheromone over its current position $x_{ij}$ and in the corresponding neighborhood cells $x_{(i+a)(j+b)}$, where $-r_v \le a <2 \times r_v$ and $-r_v \le b < 2 \times r_v$. If a neighborhood cell is a wall, then the pheromone is not deposited. There is a maximum amount of pheromone $\tau _{\max }$ that each cell can receive, avoiding an uncontrolled growth of pheromone. Equation 2 represents the amount of pheromone deposited in one time step. The constants $\delta$ and $\sigma$ represents, respectively, the pheromone rate and the dispersion rate.

$$\begin{aligned} \rho _{ij}^{t+1} = \delta \times e^{ - \frac{x_{ij}-x_{(i+a)(j+b)}}{{\sigma r_v}^2}} \end{aligned}$$

(2)

The pheromone updating is computed by Eq. 3:

$$\begin{aligned} x_{ij}^{t+1} = x_{ij}^{t} + (\tau _{\max } - x_{ij}^{t}) \times \rho _{ij}^{t+1} \end{aligned}$$

(3)

By analyzing Eqs. 2 and 3, one can observe that in a first visit to a cell with no pheromone the robot deposits the maximum amount of pheromone $\tau _{\max }$ multiplied by the $\delta$ constant before its departure. However, in the next time steps, this value will be continuously evaporated until a robot crosses the cell’s neighborhood again. On the other hand, the robot deposits an attenuated amount of pheromone ($<< \tau _{\max }$ and given by $\sigma$ parameter) over its neighborhood, which will be also submitted to an evaporation process in the next time.

The movement state is the FSM is the final step that represents the robot’s transition from one cell $x_{ij}$ to another $x_{(i+a)(j+b)}$ in the robot neighborhood. This action will be accomplished by the robots’ individual control, which is responsible to decide how to control robot’s components to make the desired step.

The CA model investigated here is not standard since the transition rule changes the state of two cells of the neighborhood. This transition starts with a stochastic local rule which taking in account the pheromone amount in each cell of the robot neighborhood. Each robot movement corresponds to change its current position to an adjacent cell. Besides that, the CA modifies the neighborhood cells updating the pheromone amount. Finally, the cell occupied by the robot becomes free, and the free neighborhood’s cell chosen by the stochastic rule as its next position, becomes the new robot’s position.

2.2 Global Behavior

The global behavior comprehends two processes: the first is the evaporation process and the second represents the interaction between the robots and the environment. The pheromone evaporation is a global process performed in all the cells of the environment (except the wall cells) at the end of each time step t according to a constant $\beta$. The evaporation process is represented by Eq. 4. In the first time step ($t=0$), each cell $x_{ij}$ receives a pheromone amount equal to 0. In the subsequent time steps, each cell visited by a robot or in its neighborhood has its pheromone increased according to Eqs. 2 and 3. Besides, all the non-wall cells in the environment having a pheromone different from zero have their values decreased by a $\beta$ constant as in Eq. 4.

$$\begin{aligned} x_{ij}^{t+1} = x_{ij}^t - (\beta \times x_{ij}^t) \end{aligned}$$

(4)

Each robot tries to move to a cell of its neighborhood defined by its vision radius $r_v$. The employment of the inverted pheromone - and its inherit repulsive force [15] - to guide robot’s movements returns trajectories almost-free of conflicts due to the robots spreading effect. However, specific conflict cases are solved by a random decision process: if two robots try to move into the same cell, a random choice decides which robot that will perform the movement, while the loser has to wait until the next time step. The conflicts avoidance between a robot and a wall is solved using a high value of pheromone, in this case, $\rho = \infty$.

From these interactions between the robots and the environment (pheromone dynamics), and between the robots themselves (collision avoidance), emerges a complex behavior that makes the swarm of robots able to efficiently solve the surveillance task. These interactions produce a robot-robot repulsion and prevent collisions, improving the exploration and increasing the covered area.

3 Experiments

The experiments presented in this section were carried out using virtual environments implemented in C language aiming to: (i) evaluate different evaporation rates, (ii) evaluate different team size N to perform the task, (iii) evaluate the team performance related to the environment coverage, (iv) evaluate the team performance in the surveillance task. All the simulation experiments were conducted in $20 \times 30$ cells lattice environments, each cell was defined as a $14 \times 14$ cm square. This size is sufficiently large to accommodate a robot inside the cell, since the robot size was adopted according to a real e-puck dimension: a circular robot with 7 cm of diameter. This configuration results in a $2.8 \times 4.2$ m environment, which is adequate to analyze the performance of a e-pucks’ team performing surveillance. Figure 1 presents the two lattice environments used to conduct the experiments. All the simulations were carried out using the following parameters: $T=1000$ steps, $\sigma =0.43$, $r_v=1$, $\delta =0.7$ and $\tau _{max}=50$, values were defined by preliminar experiments with the model and they were adjusted based on the adaptation of the values proposed for a continuous model in [13].

The first experiment was conducted to refine the evaporation rate corresponding to the $\beta$ constant in Eq. 4, which was varied using six different values: $\{0.001$, 0.005, 0.01, 0.05, 0.1, $0.2\}$. It was accomplished using the $E_1$ environment. The number of iterations was $T=1000$ and $N=3$ robots were used. The amount of pheromone from each cell $x_{ij}$ was captured in the step $T=1000$ for each $\beta$ variation. Figure 3 shows the temperature graphics for the six $\beta$ variations. The red cells have high pheromone levels, while the dark blue cells have low or null pheromone levels. It is important to note that each graphic has a different color scale, because the highest temperature (dark red color) depends on the maximum pheromone level ($\theta _{max}$) found at the end of the simulation. It is possible to observe in Fig. 3(a) that final lattice does not have a significant variation on $x_{ij}$ value, because all the cells have high pheromone levels (red and orange cells), except for the blue cells corresponding to the environment walls. This situation is not adequate for a good coverage strategy because it turns the movement choice a random process, since the cells have almost the same probability to be chosen, not taking account the cells previously visited by the swarm. The best evaporation rates were those used in the simulations related to Fig. 3(b) and (c) ($\beta =0.005$ and $\beta =0.01$), because the cells have a good variability in the color scales. It represents that the robot can choose a cell in its neighborhood using the pheromone information. The higher evaporation rates were used in Fig. 3(d), (e) and (f). It is possible to conclude that they are not appropriate, because of the large number of dark blue regions. This absence of pheromone information affects the task conclusion and the robot decision movement is a random choice.

Fig. 3.

Maps of amount of pheromone according to different evaporation rates (a) $\beta =0.001$ and $\theta _{max} = 50$. (b) $\beta =0.005$ and $\theta _{max} = 46$. (c) $\beta =0.01$ and $\theta _{max} = 45$. (d) $\beta =0.05$ and $\theta _{max} = 40$. (e) $\beta =0.1$ and $\theta _{max} = 35$. (f) $\beta =0.2$ and $\theta _{max} = 35$. (Color figure online)

A second analysis was conducted using $N=3$ robots to verify the environment coverage employing the same $\beta$ variation used in the first experiment. The number of times each cell $x_{ij}$ have been visited during 1000 time steps was computed in each simulation. These values were used to construct temperature graphics, in which a high number of dark blues cells represents a simulation with low coverage, indicating a poor surveillance performance. Figure 4 shows that robots made good environmental coverage for almost all $\beta$ values. The simulation $\beta =0.2$ returned the worst performance, due to one room was overloaded with robots visits, while other rooms were missing visits. It is also possible to observe in $\beta =0.05$ and $\beta =0.1$ simulations that there are several blue points inside some individual rooms, indicating that some positions were never or few times visited by the robots. Therefore, considering both pheromone (Fig. 3) and coverage (Fig. 4) analyses we conclude that $\beta =0.005$ and $\beta =0.01$ evaporation rates leads the team to the best behaviors.

Fig. 4.

Maps of cell steps according to different evaporation rates (a) $\beta =0.001$ and $s_{max}= 12$. (b) $\beta =0.005$ and $s_{max} = 16$. (c) $\beta =0.01$ and $s_{max} = 16$. (d) $\beta =0.05$ and $s_{max} = 14$. (e) $\beta =0.1$ and $s_{max} = 14$. (f) $\beta =0.2$ and $s_{max} = 20$, using $N=3$, $T=1000$ and $\sigma =0.43r_v$. (Color figure online)

The appropriate team size N to perform the task is an important feature to be considered in a swarm of robots for an specific environment. In order to analyze this characteristic, the team size was varied using four different values $N = \{1$, 2, 3, $4\}$ and they were used to perform the surveillance for $E_2$ environment. Since there are 7 rooms in this environment, the task could be solved putting one robot in each room. Therefore, the goal is to identify the minimum number of robots in the team to solve this task with a reasonable performance, that is, each room needs to be checked by at least one robot after a short interval of time. The experiment was conducted using $T=1000$ steps and $\beta =0.01$. By inspecting Eqs. 2, 3 and 4 using $\delta =0.7$, $\sigma =0.43$, $\tau _{max}=50$ and $\beta =0.01$, it was possible to conclude that after a cell is visited and a pheromone is deposited on it, and it takes at least 100 time steps to be almost evaporated (considering the case that no robot returns to this position to reinforce the pheromone trace). Therefore, if a dark blue cell is found at time $T=1000$, it means that this position has not been visited by any robot for at least 100 time units. Figure 5 shows the pheromone in each cell $x_{ij}$ after $T=1000$ steps. Figure 5(a) shows the result of the first experiment performed with just one robot ($N=1$). It was possible to note that 4 rooms were not recently visited, since they just have dark blue cells. It represents that a unique robot is not able to perform this task alone. Figure 5(b) shows the resultant pheromone temperature graphic using 2 robots in the team. Although it was possible to observe at least one cell in each room with a different color, it is still possible to observe a lot of dark blue cells in each room, meaning that a large portion of these rooms were not recently visited, embarrassing the surveillance task. Therefore, 2 robots is still not enough to complete the task. Starting from 3 robots (Fig. 5(c) and (d)), it is possible to notice that the team performance is good. Although we have 1 room in Fig. 5(c) with a great number of dark blue cells, this same room has a hot region indicating that a robot was inside it at time $T=1000$ and this region was started to be coverage again. Figure 5(d) indicates that all rooms received a good recent exploration but as the previous analysis suggested we can considered a waste of resources to use 4 robots. Finally, we conclude that the appropriate team size for this environment configuration uses 3 robots.

Fig. 5.

Maps of pheromone amount according to the number of robots (a) $N=1$ and $\theta _{max} = 46$. (b) $N=2$ and $\theta _{max} = 45$. (c) $N=3$ and $\theta _{max} = 45$. (d) $N=4$ and $\theta _{max} = 46$. (Color figure online)

Fig. 6.

The IACA performance according to different evaporation rates (a) $\beta =0.001$. (b) $\beta = 0.01$. (c) $\beta =0.1$. (Color figure online)

A final experiment was carried out to deeper analyze the team performance by registering the number of visits in each room during the 1000 time steps. Figure 6 exhibits three graphics summarizing the simulation conducted using room $E_2$, each one corresponding to a different evaporation rate $\beta = \{0.001, 0.01, 0.1\}$. The graphics were elaborated registering the current localization of each robot at each time step. The y-axis represents the rooms and the x-axis represents iterations. Each red vertical line indicates that one cycle of the surveillance was completed, that is, the iteration when the robots cooperatively visited all the 6 rooms. Each robot is initialized in a different room. The graphics show that IACA system with $\beta = 0.001$ is able to conclude the first cycle of surveillance at the iteration 219. In the simulations using $\beta = 0.01$ and $\beta = 0.1$ the IACA system executes more efficiently the task concluding the first cycle at the iterations 145 and 152, respectively. Moreover, IACA system with $\beta = 0.001$ concludes 5 cycles of the surveillance task, considering all the 1000 steps of simulation. On the other hand, using $\beta = 0.01$ and $\beta = 0.1$, the number of cycles concluded is increased to 7 and 6, respectively. This result corroborates that the pheromone evaporation rate is an important parameter of the model to induce a better swarm performance. Considering the $\beta$ values evaluated and using 3 robots to explore the environment $E_2$, the best performance was achieved using $\beta =0.01$.

4 Conclusions and Further Comments

This work proposes and investigates a new control model for swarms of robots based on two-dimensional cellular automata and inverted pheromone dynamics called IACA. Our model is dedicated to the surveillance task, which is very relevant to collective robotics due to [14] (i) it is included in a broad class of robotics problems; (ii) surveillance is largely used for the study of robot-robot cooperation, (iii) many real-world applications for robotics are samples of surveillance robots.

The major characteristics of IACA model are: (i) the environment is modeled as a cellular automata lattice formed by identical square cells; (ii) each robot is controlled by an individual finite state machine that switches over a 4-state cycle; (iii) each time a robot passes a cell while exploring, it leaves a trace in the environment, being that the repulsive pheromone is deposited in the current cell but also in the adjacent ones (in a attenuated value); (iv) the pheromone is submitted to an evaporation process aiming to enable visited cells to be checked again after some time delay, (v) the vision ability is considered in a such way that the robot is able to identify a pheromone trace inside its vision radius; (vi) the next step choice is stochastic and based on a probability which is inversely proportional to the pheromone amount of the neighborhood cells; (vii) the pheromone dynamics allows almost-free collisions trajectories; (viii) the robot-robot conflict avoidance are treated in a non-deterministic way.

Using simulations on virtual environments it was possible to evaluate the IACA model in terms of coverage performance, exploration analysis and the best evaporation rate. It was possible to conclude that the proposed model is adequate to control a team of robots for surveillance returning an efficient performance in this task. For a better utilization of this model, it is possible to refine its parameters according to robots and environment’s specifications.

A forthcoming work is about the implementation of this model using simulation platforms with real-world robotic architectures, allowing a more realistic analysis of the model. We have already started this investigation and some new relevant issues have appeared related to the need of synchronization and the model dependency on the accuracy of the localization and orientation of robots. In a future investigation we intend to identify the common behavior returned by the proposed model, independently from the parameters values adopted.