Robot Swarms Theory Applicable to Seek and Rescue Operation

Abstract

An important application of cooperative robotics is search and rescue of victims in disaster zones. The cooperation between robots requires multiple factors that need to be taken into consideration such as communication between agents, distributed control, power autonomy, cooperation, navigation strategy, locomotion, among others. This work focuses on navigation strategy with obstacles avoidance and victims localization. The strategy used for navigation is based on swarm theory where each robot is an swarm agent. The calculation of attraction and repulsion forces used to keep the swarm compact is used to avoid obstacles and attract the swarm to the victim zones. Additionally, an agent separation behavior is added, so the swarm can leave behind the agents, who found victims so these can support the victims by transmitting their location to a rescue team. Several experiments were performed to test navigation, obstacle avoidance and victims search. The results show how the swarm theory meets the requirements of navigation and search operations of cooperative robots.

1 Introduction

Unfortunately, Throughout the history of mankind, we have experienced uncountable natural disasters and terrorist attacks, which decimate cities and towns. Evidently, these events end with the lives of many people, and that is the main reason why numerous approaches exist to deal with the before, during and aftermath of a disaster.

When a disaster occurs, the most critical steps that need to be followed in order to save lives are exploration, search, localization and rescue of survivors. Each step is accompanied by a set of challenges for rescue teams, because affected areas are difficult to access and are extremely dangerous, for example they might have uneven grounds, which are prone to landslides, or collapsed buildings, among other possible scenarios. Fortunately, we have seen significant progress in the interaction between rescue workers and robotic platforms used in rescue operations, as shown in the work presented by Casper in [1], which deals with the events presented in the attacks of the World Trade Center. This type of work has allowed the public to see the advantages, disadvantages and applicability of robotics in disaster zones.

One of the recent theories applied to rescue robotics are bio-inspired systems, which are based on animals, specifically insects like ants, termites and bees [2, 3]. These animals show applicable behaviors, such as localization, recognition and are also able to explore large areas, when they are searching for an specific target. Ethology says these animals possess cooperative dynamics, which can be explained in mathematical form. In fact, the implementation and theoretical development of the behavior of swarm agents can open a new path to multi-robots systems, which can provide different kinds of solutions with simple structures to complex challenges. One of the possible approaches of this bio-inspired system, which is the one being covered by this paper, is swarm theory applied to the simulation of robots for rescue applications. These robots can keep a formation, while searching for position targets and can also avoid obstacles.

The use of swarms of robots in exploration of disaster zones facilitates and streamlines rescue tasks, thus making the recognition and mapping of affected areas faster and safer for rescue workers, while providing more information for search-and-rescue of possible survivors.

The other sections that complete this paper are Sect. 2 - Related Work, Sect. 3 - Robotic Swarms, Sect. 4 - Experiment and Results, Sect. 5 - Conclusions.

2 Related Work

Proper search and rescue planning should take into account all of the factors, that can hamper decision-making and lower the performance of duties, such as high stress levels and disorientation that normally affect rescue workers during disaster events. This is critical to safeguard lives and facilitate prompt assistance to those who require it. In disaster events, it is important to have access to a solid contingency procedure, as explained in the work presented by Huder in [4], which discusses the first hours and critical initial days that take place during disaster responses. It is in the first hours and initial days when the robot action can be crucial to save lives. It mentions the precautions and planning that individuals must carry out beforehand and also gives different perspectives on how to manage critical situations presented in diverse types of disasters.

As mentioned in previous section, a possible addition to current search and rescue procedures is the implementation of robotic platforms to locate survivors. As previously mentioned, a benchmark for these type of robotic platforms was displayed during the 911 attacks, where Casper and Murphy in [1] presents the advantages and disadvantages associated with the implementation of this technology and the performance of each robot that deployed. It is also worth mentioning that the robots used by Casper were not conventional, since they were structurally designed to withstand though disaster conditions. In the work presented by Ventura and Lima [5], the need to use heterogeneous robotics teams, such as aerial robots that perform exploration and recognition of the disaster zone, was discussed. In addition to that the author mentioned the need to include powerful robots able to remove debris and rubble, and small agile robots capable of reaching people trapped under ruins.

Regardless of the robotic platform selected, it is clear that they must have a certain level of adjustable autonomy, basic learning capabilities, and object handling abilities, in addition to sufficient human interface options for rescue teams. In this paper, we have outlined the achievements of several search and rescue robots from around the world, in order to shine more light on how these platforms work and to show the increasing level of autonomy that we have witnessed in the last decade. In the contribution made by Seljanko in [6], They proposed a low cost and low maintenance add-on search and rescue robotic system with high reliability and robustness, which includes electronic devices such as microphones, speakers, GPS and integrated camera, thus resembling a smart-phone.

Swarm robotics theory can be best implemented in search and localization of victims in disaster zones, due to the teamwork or cooperation displayed by the swarm, as presented by Tan in [7], who said that the main advantages of using swarms robots is the exploration and recognition of larger areas in less time, specially when compared to the single robot case, thus allowing greater flexibility which is ideal for our application. It is also advantageous for rescue teams to have a swarm of robots, because if some of the agents of the swarm were to fail, the absence of these agents does not seriously affect the overall success of the swarm, which clearly demonstrates the greater robustness of the decentralized control system.

To work with robotic swarms, we must take into consideration factors such as communication, information sharing between agents, the distributed control algorithm, cooperation and navigation, and that is why will explore them in this paper.

Several algorithms designed for the navigation of swarm robots have been tested in the past, one of the more commonly used ones is the swarm intelligence, which was presented by Couceiro et al. in [8]. This paper presents a comparison between the Particle Swarm Optimization (PSO) and an algorithm derived from the PSO called Darwin Particle Swarm Optimization, which is based on the theory of evolution. The results obtained from the PSO algorithm are generally good, but sometimes fail to be trapped in the local optima and can not find the global optimum, on the other hand, the DPSO is a variation, which can perform better, because it divides the swarm into sub-swarms. Dividing the swarm into several sub-swarms is beneficial, because the sub-swarms can share the best solution with the other sub-swarms and if this new team solution is better than the possible solution derived by the swarm as a whole, the sub-swarms are allowed by the complete swarm to go to the new optimal solution, thus avoiding being trapped in the local optima.

3 Robot Swarms

In nature, there are several species that display swarm like behavior, such as bacteria, insects, birds, fish and horses among others. As can be expected, these groups are composed of individuals, who possess specific distinct capabilities and behaviors, but when they all get together as one group, and operate as such, they will behave differently in order to work as a group. One of the more notable examples of this group behavior is a swarm of honey bees choosing a place to build a new honeycomb, this phenomenon was presented by Seeley and Buhrman in [9], whose paper showed that this swarm behavior, which takes place during the spring and summer, is best exemplified when the colony outgrows its honeycomb, and then proceeds to divide itself to find new grounds and then gets back together as a swarm once it finds the correct location to build a bigger hive. To be more specific, The new site selection begins with several hundred scout bees, who leave the colony in search of potential new sites, once the scouts find an appropriate candidate, they return to the hive in order to report with a wiggle dance where the potential new place is located. Once the scouts select the correct location from the pre-selected sites, they will steer the rest of the swarm to the new location by chemical stimulation. After the selection step is completed, the division process of the hive begins, and the old queen with nearly half of the colony leaves the hive to build the new one, while a younger queen stays with the other half of the colony in the old honeycomb.

It is also important to highlight that the ability of the swarm to navigate can be affected by a set of critical factors, such as collisions between themselves, large obstacles in route, pheromone communication errors, erroneous scout indications and even poor sense of direction.

We can represent the swarm of bees with the help of graph theory with the application of the concepts worked by Mesbahi in [10]. One can describe the system by defining N agents representing each member of the bee swarm, or in the case of our application a robot, and a connection representing the communication and transmission of information between the agents, either bees or robots. As mentioned by Mesbahi, we first need to define the agents of the system (V, E), where V is the set of nodes in the system and E stands for the topology of the system, we also need to define N(i) as the neighborhood or adjacent nodes to node i. Regarding the links between the agents, we can be describe them as a dynamic system.

It is advantageous to apply graph theory to control swarm responses, because it allows us to apply concepts such as finding the Laplacian, which represents the system, and assuming that the whole system is a graph fully connected. In addition to that, we can assume that the system has no noise, links are bidirectional, or even digraphs with different hierarchies.

The Algorithm used to simulate the swarm behavior is based on the one proposed by Passino in [11]. This algorithm is explained as follows; We also want to specify to the reader that this algorithm is not focused on a spacial kind of animal swarm, and therefore we are just referring to N number of agents.

Agents: Each agent is described as a point in the space with position and velocity. Initially, the position and velocity are defined randomly. We assumed that each agent can detect the position and velocity of the rest of the swarm agents. The swarm agents interaction is represented by graphs (G, A) where $G= \lbrace 1,2,...,N \rbrace$ is a set of nodes and $A=\lbrace (i,j):i,j \in G,i\ne j \rbrace$ represents the communication and sensing topology between the $i^{th}$ agent and each of the other $j^{th}$ swarm agents. We will now define the terminology and elements used in our algorithm.

Interaction: The interaction of the swarm agents is defined by the attraction and repulsion strategy. This strategy allows the agents to keep a comfortable distance over the other swarm agents. The attraction parameter tries to maintain in close proximity every element of the swarm and thus gives the group a mechanism to remain grouped together. The attraction parameter is defined by (1)

$$\begin{aligned} -k_{a}(x^{i}-x^{j}) \end{aligned}$$

(1)

where $k_{a}$ is the attraction force, this mechanism can be local (having a restriction by the sensing range) or global (Agents can move other agents from the group regardless of how far they are).

The repulsion parameter allows the agent to keep distance from the other members of the swarm. This avoids collision between agents when the swarm is moving. The repulsion mechanism can respond in two different ways. First one, when a comfortable distance is reached and its parameter is expressed by (2)

$$\begin{aligned}{}[-k(\Vert x^{i}-x^{j} \Vert - d)](x^{i}-x^{j}) \end{aligned}$$

(2)

where $\Vert x^{i}-x^{j} \Vert = \root 2 \of {(x^{i}-x^{j})^{T}(x^{i}-x^{j})}$, $k>0$ is the repulsion magnitude and d is the comfortable distance between $i^{th}$ agent and the $j^{th}$ agent. On the other hand, if two agents are two close to each other, the parameter is represented by (3).

$$\begin{aligned} k_{r} exp ( \frac{- \frac{1}{2} \Vert x^{i}-x^{j} \Vert ^{2}}{r^{2}_{s}}) (x^{i}-x^{j}) \end{aligned}$$

(3)

where $k_{r}>0$, represents the repulsion magnitude and $r_{s}>0$, is the repulsion range.

Environment: This is the space where the agents can move and it is composed of good and bad areas. These good and bad areas are analogous to places where agents can find food and to areas that have predators respectively. For this present work, the good areas are defined by the presence of survivors, who need to be rescued and the bad areas are full of ruins, collapsed structures and obstacles that impair the ability of the swarm to navigate freely.

The environment is defined by J(x), where $x \in \mathfrak {R}^{n}$. Its is assumed that J(x) is continuous and that it has a finite slope in every direction. The agents navigate to the negative gradient (4) of the J(x)

$$\begin{aligned} - \nabla J(x)=- \frac{\partial J}{\partial x} \end{aligned}$$

(4)

As mentioned above, the obstacles and victims that must be found by the agents are part of the environment. For the current work, both elements generate forces of repulsion and attraction over the agents. In this way, the interaction between agents with victims and obstacles is modeled using equation (3) with some changes in the meaning of the variables.

Interaction Between Agents and Obstacles: The obstacles produce a repulsion force over the agents. This repulsion is modeled using (3) where $k_{r}>0$, and $r_{s}$ is related to the size of the obstacle.

Interaction Between Agents and Victims: The victims exert an attraction force, where $k_{r}<0$ and $r_{s}$ is proportional to the victims density in the near area.

Left Behind: Every agent is exposed to different attraction and repulsion forces, which help to keep the swarm cohesion and at same time pushes the swarm towards the goal. The victims generate an attraction force over close agents and this force can disturb the normal behavior of the swarm and reduce the velocity of the agents in proximity to the victims. The $k_{r}$ magnitude was put in place so that it can stop at least one of the closest agents near the victims. When agents are navigating close to the victims, at least one agent must stop near the victims. Once one or more agents stop beside to the victims, those agents are left behind by the swarm. They are separated from the swarm, breaking the communication and attraction forces that keep them into the swarm. The agents left behind create a new smaller swarm close to the victims, which changes its status to stationary with the victims and the starts to transmit the localization of the newly found victims.

4 Experiment and Results

In order to perform experiments for swarm navigation, the model previously explained was implemented using Matlab. Four different types of experiments were developed to show and analyze the swarm behavior in search and rescue operations.

Obstacle Avoidance: The first version of this experiment is performed using 10 agents and small obstacle as shown in Fig. (1). This part of the experiment depicts how the swarm goes around the obstacle in order to avoid it. This is possible, because the obstacle is relatively small and the agents are able to tolerate the obstacle between the attraction forces. The second version uses a bigger obstacle as depicted in Fig. (2). In the second case, the agents avoid the obstacle by taking a side path, this occurs because there is not enough space between the attraction forces to allow broad obstacles to stay in between the agents.

Fig. 1.

Navigation with a small obstacle

Fig. 2.

Navigation with a big obstacle

Multiple Obstacles: This part of the experiment depicts how the swarm goes around obstacles in order to avoid them. This is possible, because the obstacles are relatively small and the agents are able to tolerate the obstacles between the attraction forces, as depicted by Fig. 3. This case uses nine obstacles distributed throughout the area between the start point and the goal point. It forces the swarm to navigate through the obstacles. while avoiding them and moving towards to goal point. Figure 3 shows the agents navigating and exploring the zone. At same time, the path described by every agent is drawn and it depicts the explored area.

Fig. 3.

Navigation with several obstacles

Victim Localization: This test uses a flat terrain to show how the swarm localizes victims. This process is accomplished with the use of the “left behind” process. Once an agent has localized a victim, it stops near the potential victim. At the same time, the swarm stops, because of the attraction force between the agents. In that moment the process called “Left behind” detaches the agents found victims. The detached agents create a new swarm surrounding the victims. The original swarm restarts to move towards the target point and leaves behind the swarm agents that are in charge of the victims. Figure (4) shows how the agents stop near the victims and surround them, while the swarm leaves them behind.

Fig. 4.

Search of victims area

Fig. 5.

Victims zone with multiples obstacles

Navigation and Victim Localization: This is a complete case where the swarm navigates through the area full of obstacles and some places with potential victims. This test is divided in two experiments. The first one uses 10 agents and 2 victim places as shown by Fig. 5. The second one has 40 agents and 5 victim places (Fig. 6). Both cases depict how the swarm covered the area navigating through obstacles and localizing victims at the same time. The performance differences between these two cases are the covered area and the number of agents surrounding the victims in independent clusters. With large numbers of agents, the covered area is bigger, because the repulsion force pushes the agents harder to keep the distance between them. These agents use more area, to find an equilibrium point of repulsion and attraction forces. The number of agents around victims is also bigger, because there are more agents in the swarm and therefore rises the probability of finding victims for each agent.

Fig. 6.

Several victim areas with a big swarm

5 Conclusions

An algorithm for search and rescue operations has been proposed using swarm theory. The algorithm is based on concepts of attraction and repulsion forces. These concepts keep the swarm as compact as physically possible and fix a minimum distance between them. It is possible to represent the swarm with graph theory, where the agents are nodes, the attraction and repulsion forces are links between the nodes. The repulsion force is used to avoid obstacles and to keep a minimum distance between the agents. The attraction forces allow the swarm to stay compact and to be attracted by the victims. Additionally, a concept called “left behind” is introduced with the aim of making possible the opportune separation of some agents from the swarm. Agents who find victims are separated from the swarm and they are in charge of the global localization of the victims so they can be rescued. Four different experiments were developed with the objective of showing the performance of the swarm in several cases of navigation. The experiments depicted show how the swarm navigates in areas with multiple obstacles and simultaneously searches for victims. The algorithm shows creation of new small swarms around victims, which can be used to support and facilitate the localization of victims for rescue teams. The swarm algorithm shows redundancy and robustness characteristics when it loses agents, but it regroups with the ones that are left and keeps the navigation process. Future work includes the use of algorithms based on graph theory to improve the relation of the sub swarms and the global swarm. Additionally, the algorithm proposed in the current work will be performed in a robotics simulator with the purpose to check this ideas on aerial and ground robots.