# Intelligent UAV Map Generation and Discrete Path Planning for Search and Rescue Operations

Authors: Víctor San Juan; Matilde Santos; José Manuel Andújar
Journal: Complexity
 (2018)

---

## Abstract

Search and Rescue Operations (SAR) take place in any emergency situation where people are involved and their lives are at risk. These operations are nowadays carried out with the help of advanced technology, such as Unmanned Aerial Vehicles (UAVs). In this work, several methods are proposed to calculate the UAV discrete path planning. Previously, an intelligent characterization of the searching area is performed to estimate a potential risk/occupancy degree of the gridding map. This estimation is mainly based on fuzzy logic, considering different factors. Then, four methods are applied to calculate the path planning: an original proposal called attraction, fuzzy logic, ANFIS, and a PSO algorithm. All of them calculate the location of the waypoints to be followed by the UAVs to minimize the distance and the risk the people is exposed to. Then, these strategies are adapted to the possibility of having more than one UAV searching at the same time, and the swarm formation is discussed. Finally, these four solutions for path planning, including different number of UAVs, are tested in a real simulation scenario, and then the performance of each method is analyzed and compared with the others.


---

## Body

## 1. Introduction

Unfortunately, every year there are some news of natural disasters, like fires or earthquakes which affect cities, towns, and natural environment. Besides, we also see human tragedies as maritime accidents or people who get lost in hazardous places. All these situations, and many others, have one important aspect in common. They subject the life of many people involved in these situations in one way or another to danger and a direct risk.The most critical aspect in these cases, even before starting to mitigate the risk (i.e., extinguishing a fire), is the search and rescue (SAR) of potential survivors. The SAR process is carried out by specialized teams that even risk their own lives to save others.Fortunately, these SAR teams are, in most of the cases, well equipped with advanced technology, which nowadays includes Unmanned Aerial Vehicles (UAVs) to improve people searching and also to prevent rescue team from going through risky places with no real evidences of finding survivors [1].These autonomous vehicles have experienced a huge development during the last ten years. UAVs are nowadays used in many different applications such as defence, surveillance, or package delivery, among others [2]. But the unmanned aerial vehicle path planning problem is an important issue in the UAV mission planning [3].Many of these applications use automatically controlled aerial vehicles, which are able to flight through a preplanned trajectory or even to make a real-time decision on the trajectories. Nevertheless, most of the commercial UAVs still use an off-board pilot and a fixed preplanned trajectory [4].The final motivation of this work is to find people at risk as fast as possible in SAR operations, using fully automatic UAVs equipped with on-board cameras. Therefore, we proposed some strategies to optimize this searching. The path planning takes into account the hazard of a particular scenario, where there will be some places with higher risk than others. To do this, we have first developed a methodology based on fuzzy logic to characterize the surface to be explored and to estimate the degree of potential risk and the probability of people to be at that spot.Then, we have developed a discrete path planner to find people as fast as possible using the map generated by the previous analysis. Four intelligent discrete path planning strategies have been implemented and tested on a real scenario. Finally, we will show how the number of UAVs in swarm formation affects the speed and effectiveness of people searching.The following topics are not included in the scope of this work: UAV on-board control and obstacle avoidance and UAV path following and image processing. In fact, we are not working with a model of the dynamics of the UAV. The path planning is calculated as a trajectory along some discrete points, corresponding to different cells in which the map of the searching area is divided. The UAV moves from one cell to another (the adjacent one) with a constant speed. The number of cells visited gives the length of the trajectory and therefore the time spent.The paper is organized as follows: Section2 summarizes the related works. Section 3 describes the generation of the fuzzy occupancy/risk map. In Section 4, four approaches for the intelligent discrete path planning are proposed and results on a real simulation scenario are presented and analyzed. The outcome of using several UAVs in the search and rescue mission is discussed in Section 5. Section 6 shows a case studied and Section 7 summarizes and discusses the global results. The paper ends with the conclusions and future work.


## 2. Background

Search and Rescue (SAR) operations must be carried out by the competent authorities in case of emergency that involves people in danger. The nature of these emergencies can be very different; therefore, the hazards will vary depending on the kind of emergency and consequently the SAR mission has also to be adapted to the scenario. Some emergency situations are, for instance, people lost in uninhabitable places, fires, aircraft or vessel accidents, natural disasters like landslides, floods, and earthquakes [5].Autonomous robots and vehicles have been used to carry out missions in hazardous environments, such as operations in nuclear power plants, exploration of Mars, and surveillance of enemy forces in the battle field [6]. Indeed, UAVs are often used in SAR operations. The common operation of these UAVs is to be commanded remotely by a SAR team member [7]. The UAV is moved by its pilot to the desired areas in order to collect the relevant information for the SAR mission [8]. The payload of the UAV may be of different nature, usually cameras to record video or to take pictures, but it is also possible to find other sensors such as gas analyzers to detect smoke composition.But still planning a SAR mission in terms of obtaining the path or trajectory is a challenging issue that requires careful consideration. The autonomous UAVs flight can be based on a preplanned path or can even be calculated online [9]. The level of autonomy achieved by the UAVs depends on the methodology used to control the vehicle and to generate its routes [10]. Therefore, autonomous UAVs must have an auto path planning calculation functionality to be really autonomous.Discrete search is an interesting topic nowadays, with many applications. For example, in built infrastructure monitoring, an efficient path planning algorithm is essential for robotic inspection of large surfaces using computer vision [11, 12] or for controlling autonomous agents in interactive virtual worlds, given the growing demands on the size and complexity of these virtual scenarios, even for areas of crowd animation and whole-body motion planning for virtual characters [13].Discrete path planning has different approaches. The book by Kallmann and Kapadia [13] reviews the evolution of several related techniques for achieving intelligent navigation in discrete spaces, starting from classical planning and computational geometry techniques and then gradually moving towards more advanced topics, although being applied to interactive virtual worlds, to address shortest paths and limited time budgets. Some of the path following algorithms more often used for UAVs are presented in [14], including a comparison between them in order to help in the selection of one or another. Geometrical methods such as spline interpolation are used in order to get smoother curves through a number of waypoints [15, 16]. In [7], path planning is defined using a Monte Carlo searching of the best path using online detected parameters.The optimization of the path between waypoints is also addressed by several authors. Many of them use genetic algorithms (GA) [17–20]. Other proposals apply estimation of distribution algorithms [21] or A∗ searching [22]. Generally, in these cases, the UAV needs to move in a known environment, and the optimal path is obtained to avoid obstacles, radar zones, buildings, battery run out, and so on.


## 3. Generation of the Risk/Occupancy Map

In this process of searching and rescue, it is desirable to exploit the increasing availability of data about a disaster that come from different sources. In particular, such information can be a valuable resource to drive the planning of UAV flight paths over a space in order to discover people who are in danger [8]. Therefore, the first step will be to estimate and define the searching area, including all the available data, and define the desired area coverage level, in order to generate the map that will be used for the discrete UAVs path planning.This area characterization involves the analysis of the surface where the search will take place and the quantification of some characteristics. The input is a map of the area to be covered. This map is divided into a grid of cells. Each of these cells will have an assigned value of potential risk and occupancy that will be used to calculate the waypoints that the UAV will follow.To make the grid partition, it is assumed that the UAV will be able to track the whole cell when located at the geometrical centre of it. That is, the size of the cells will not be bigger than the area covered by the on-board camera of the UAV. But this is difficult to be estimated since it depends on two main factors: the altitude of the UAV and the opening angle of the camera lens. At the same time, the altitude of the UAV, in case of visual tracking, will be limited for the camera characteristics. In fact, if the altitude is too high, the camera will not be able to focus correctly, and therefore the tracking will not work. Taking this into account and considering that we are working with a discrete scenario in a theoretical way, a limit of 100 × 100 m cell size has been established. This value can be scaled according to the technical specifications of the sensors used.Once the size of the grid is determined, the number of cells is calculated straightforward for the particular zone we are exploring.The application scenario of this work is a real case. In August 2016, a forest fire was declared in the island of La Palma, in the Canary Islands (Spain). The fire lasted several days affecting over 4000 hectares, that is, 6.8% of the island surface (Figure1(a)). Fortunately, there were no civil victims, but sadly one person died during the extinguishing phase. More than 2500 people needed to be evacuated from their homes during the fire.Figure 1
La Palma fire map (a) and gridding searching area (b).
(a) (b)In Figure1(a), we can see how the fire grew throughout the days. The simulation scenario corresponds to the third day of the fire (dotted red line). Three days is a reasonable time to search for a person. A rectangular area, larger than the fire area, was selected to be tracked and partitioned. The grid partition has 24 × 24 cells (Figure 1(b)).Once the region to be covered is defined and the grid partition obtained, the potential risk/occupancy value for each cell is going to be estimated.


### 3.1. Potential Risk/Occupancy Estimation

The potential risk/occupancy map aims to give a value of the possibility of each cell to be occupied by people and, in that case, the potential hazard for the life of that person.To calculate this value some information from different sources is necessary. To obtain the potential occupancy we need to know, for example, how often the area is visited by people. The potential risk can be given by the types of emergencies. This information can be obtained from an analysis of the area by experts and/or from historical data. We will consider two main components to define the map, called terrain and emergency factors. They are defined by fuzzy inference systems (FIS).The terrain FIS has as inputs the variables namedstaying,hazard, andtransit (Table 1). The output isPterrain, which is the contribution of this factor to the map.Table 1
Terrain factor inputs.
Staying It describes whether the area is often visited by people or not. High values increase potential occupancy. This information can be obtained from an analysis of the area and/or from historical data. Hazard It quantifies the hazards inherent to the area, affected by wild animals, weather conditions, terrain access, etc. Higher values increase potential risk. Transit It expresses whether the area is usually transited by people, meaning people could be more easily found by other people. The potential occupancy and the risk of these areas decrease.Two of these input variables have been defined as fuzzy (staying andhazard), and the third one(transit) will be considered as a crisp weight to be applied to the output. Both thestaying and thehazard linguistic variables are normalized between 0 and 1. The fuzzy sets are given by triangular and trapezoidal membership functions. The labels are Low, Mid, and High forstaying (Figure 2(a)) and Low and High forhazard (Figure 2(b)).Figure 2
Staying (a) andhazard (b) fuzzy variables.
(a) (b)The output is defined by three triangular fuzzy sets (Low, Mid, and High). The fuzzy rules, obtained by applying expert knowledge, are as follows:RuleStayingHazardOutput1highhighhigh2highlowlow3mediumhighhigh4mediumlowmedium5lowhighmedium6lowlowlowThe output of this fuzzy system is finally weighted by thetransit variable. That is, the terrain FIS result is multiplied by it to obtain the finalPterrain value. Thetransit variable will be low, in general, in places where the access is easy and it is difficult that people get lost and stay there (low occupancy); if something happened, they will have been already found and evacuated. Besides, the risk will be also low as there will be help to solve that situation. Therefore, the transit value will lower the value ofPterrain in this case. And vice versa.ThisPterrain factor is part of the contribution to the final value that will be assigned to each cell in order to rank them to be visited (see equation (1)).Table3 shows an example of the values that these variables may have. The values given to thestaying factor are estimated according to the terrain accessibility and orography. Inaccessible areas or areas with difficult access have smaller staying factor than others like roads or plains. Thehazard has been estimated according to the terrain nature as well. The transit value depends on the presence of roads or buildings on that area.To give an example, if the staying input is high, the contribution of the terrain factor to the risk/occupancy value of a cell should be high (there will be people there) but at the same time this value will be balanced for two other factors, transit and hazard. Anyway, if the staying is high it is very likely that the hazard of that place is low (no dangers) and in addition the transit factor will be low (roads, accessible places), decreasing the final contribution to the risk.The same reasoning has been applied to determine the emergency FIS. The fuzzy input variables areaffected andinjuries, whereaffected is defined by three fuzzy sets with triangular membership functions andinjuries has two trapezoidal ones. The third input, theSAR team position, is a binary variable with value equal to one except in the case the rescue team is already on the spot, in which case is 0. The definition of these variables is shown in Table 2. The output of this FIS is calledPemergency (see equation (1)).Table 2
Emergency factor inputs.
Affected It represents how the area is affected by an emergency. High values increase potential risk and low values the opposite. Injuries It describes the possibility of people being injured. High values increase potential risk. SAR team position It describes the location of the SAR team, e.g., how close to the emergency area they are. Indeed if the spot is already covered, the necessity of going to that point is cancelled.Table 3
Terrain input values.
Description Transit Staying Hazard Main roads 0.2 0.8 0.1 Sec roads 1 0.4 0.6 0.2 Sec roads 2 0.6 0.4 0.2 Forest nearby 0.4 0.4 0.3 Plain 0.3 0.7 0.2 Forest type 1 0.6 0.4 0.4 Forest type 2 0.8 0.3 0.5 Forest type 3 0.9 0.1 0.7 Hills 0.5 0.5 0.3 Desert 0.9 0.2 0.6For example, if a particular zone is strongly affected, and the type of accidents is dangerous for people lives, the value of this FIS will be high. It will be pondered by whether the SAR team is near or even already there, decreasing the risk and the occupancy.Finally, regarding the importance ofPterrain andPemergency factors on the final decision about the path planning, the meaning of them is as follows. The first one is more important since it represents the zones that have to be visited because is very likely that people are there. Besides, they can also be hazardous areas. However,Pemergency represents the zones that should be visited because they are potentially dangerous for people due to some kind of emergency, in case people are there.


### 3.2. Potential Risk/Occupancy Map

We estimate the result of these fuzzy inference systems,Terrain andEmergency, for each cell of the map of the searching area of La Palma. A map is generated for both of them (Figure 3).Figure 3
La Palma terrain (a) and emergency (b) maps.
(a) (b)The colour represents the value of the corresponding factor for that cell, from dark blue (value 0) to yellow (value 1). Figure3(a) shows the terrain contribution. A high staying factor can be observed in the middle of the map, and the secondary roads are clearly marked in blue. The emergency contribution is shown in Figure 3(b). There are three differentiated zones: the not affected one, the one in the middle that has been seriously affected by the fire and a pale green one.Then both contributions are combined according to the relation given by (1) to obtain the potential risk/occupancy value of the zone caught on fire of La Palma (Figure 4), which will be the input for the discrete path planning:(1)P=0.5·PTERRAIN+0.4·PEMERGENCY+0.1·PHISTORICAL.Figure 4
La Palma potential risk/occupancy map.The third term of (1), the historical contribution, quantifies the possibility of an event to happen again in the same place. It will be 1 in the positive case and 0 otherwise.It is possible to see the different elements of the area; for example, some roads can be clearly identified and the yellow areas correspond to the forest, with higher risk values and where the fire started.


## 3.1. Potential Risk/Occupancy Estimation

The potential risk/occupancy map aims to give a value of the possibility of each cell to be occupied by people and, in that case, the potential hazard for the life of that person.To calculate this value some information from different sources is necessary. To obtain the potential occupancy we need to know, for example, how often the area is visited by people. The potential risk can be given by the types of emergencies. This information can be obtained from an analysis of the area by experts and/or from historical data. We will consider two main components to define the map, called terrain and emergency factors. They are defined by fuzzy inference systems (FIS).The terrain FIS has as inputs the variables namedstaying,hazard, andtransit (Table 1). The output isPterrain, which is the contribution of this factor to the map.Table 1
Terrain factor inputs.
Staying It describes whether the area is often visited by people or not. High values increase potential occupancy. This information can be obtained from an analysis of the area and/or from historical data. Hazard It quantifies the hazards inherent to the area, affected by wild animals, weather conditions, terrain access, etc. Higher values increase potential risk. Transit It expresses whether the area is usually transited by people, meaning people could be more easily found by other people. The potential occupancy and the risk of these areas decrease.Two of these input variables have been defined as fuzzy (staying andhazard), and the third one(transit) will be considered as a crisp weight to be applied to the output. Both thestaying and thehazard linguistic variables are normalized between 0 and 1. The fuzzy sets are given by triangular and trapezoidal membership functions. The labels are Low, Mid, and High forstaying (Figure 2(a)) and Low and High forhazard (Figure 2(b)).Figure 2
Staying (a) andhazard (b) fuzzy variables.
(a) (b)The output is defined by three triangular fuzzy sets (Low, Mid, and High). The fuzzy rules, obtained by applying expert knowledge, are as follows:RuleStayingHazardOutput1highhighhigh2highlowlow3mediumhighhigh4mediumlowmedium5lowhighmedium6lowlowlowThe output of this fuzzy system is finally weighted by thetransit variable. That is, the terrain FIS result is multiplied by it to obtain the finalPterrain value. Thetransit variable will be low, in general, in places where the access is easy and it is difficult that people get lost and stay there (low occupancy); if something happened, they will have been already found and evacuated. Besides, the risk will be also low as there will be help to solve that situation. Therefore, the transit value will lower the value ofPterrain in this case. And vice versa.ThisPterrain factor is part of the contribution to the final value that will be assigned to each cell in order to rank them to be visited (see equation (1)).Table3 shows an example of the values that these variables may have. The values given to thestaying factor are estimated according to the terrain accessibility and orography. Inaccessible areas or areas with difficult access have smaller staying factor than others like roads or plains. Thehazard has been estimated according to the terrain nature as well. The transit value depends on the presence of roads or buildings on that area.To give an example, if the staying input is high, the contribution of the terrain factor to the risk/occupancy value of a cell should be high (there will be people there) but at the same time this value will be balanced for two other factors, transit and hazard. Anyway, if the staying is high it is very likely that the hazard of that place is low (no dangers) and in addition the transit factor will be low (roads, accessible places), decreasing the final contribution to the risk.The same reasoning has been applied to determine the emergency FIS. The fuzzy input variables areaffected andinjuries, whereaffected is defined by three fuzzy sets with triangular membership functions andinjuries has two trapezoidal ones. The third input, theSAR team position, is a binary variable with value equal to one except in the case the rescue team is already on the spot, in which case is 0. The definition of these variables is shown in Table 2. The output of this FIS is calledPemergency (see equation (1)).Table 2
Emergency factor inputs.
Affected It represents how the area is affected by an emergency. High values increase potential risk and low values the opposite. Injuries It describes the possibility of people being injured. High values increase potential risk. SAR team position It describes the location of the SAR team, e.g., how close to the emergency area they are. Indeed if the spot is already covered, the necessity of going to that point is cancelled.Table 3
Terrain input values.
Description Transit Staying Hazard Main roads 0.2 0.8 0.1 Sec roads 1 0.4 0.6 0.2 Sec roads 2 0.6 0.4 0.2 Forest nearby 0.4 0.4 0.3 Plain 0.3 0.7 0.2 Forest type 1 0.6 0.4 0.4 Forest type 2 0.8 0.3 0.5 Forest type 3 0.9 0.1 0.7 Hills 0.5 0.5 0.3 Desert 0.9 0.2 0.6For example, if a particular zone is strongly affected, and the type of accidents is dangerous for people lives, the value of this FIS will be high. It will be pondered by whether the SAR team is near or even already there, decreasing the risk and the occupancy.Finally, regarding the importance ofPterrain andPemergency factors on the final decision about the path planning, the meaning of them is as follows. The first one is more important since it represents the zones that have to be visited because is very likely that people are there. Besides, they can also be hazardous areas. However,Pemergency represents the zones that should be visited because they are potentially dangerous for people due to some kind of emergency, in case people are there.


## 3.2. Potential Risk/Occupancy Map

We estimate the result of these fuzzy inference systems,Terrain andEmergency, for each cell of the map of the searching area of La Palma. A map is generated for both of them (Figure 3).Figure 3
La Palma terrain (a) and emergency (b) maps.
(a) (b)The colour represents the value of the corresponding factor for that cell, from dark blue (value 0) to yellow (value 1). Figure3(a) shows the terrain contribution. A high staying factor can be observed in the middle of the map, and the secondary roads are clearly marked in blue. The emergency contribution is shown in Figure 3(b). There are three differentiated zones: the not affected one, the one in the middle that has been seriously affected by the fire and a pale green one.Then both contributions are combined according to the relation given by (1) to obtain the potential risk/occupancy value of the zone caught on fire of La Palma (Figure 4), which will be the input for the discrete path planning:(1)P=0.5·PTERRAIN+0.4·PEMERGENCY+0.1·PHISTORICAL.Figure 4
La Palma potential risk/occupancy map.The third term of (1), the historical contribution, quantifies the possibility of an event to happen again in the same place. It will be 1 in the positive case and 0 otherwise.It is possible to see the different elements of the area; for example, some roads can be clearly identified and the yellow areas correspond to the forest, with higher risk values and where the fire started.


## 4. Discrete Path Planning

Four approaches for discrete path planning have been develop and applied, three of them using techniques that come from the artificial intelligence field. The final aim is to define the waypoints the UAV must follow, in order to find as quickly as possible the people involved in a SAR operation and to minimize the risk of their lives.To find people in the fastest way, it is necessary to explore the whole area minimizing the travelled distance. Moreover, not only the time but also the risk has to be minimized, so the UAVs should first go to those zones which are riskier or more hazardous. As it is difficult to solve both problems at the same time, firstly the areas with higher potential risk/occupancy will be visited and then the distance will be minimized as well, looking for a good trade-off between both aims.As it has been said, the on-board camera is supposed to be able to track a whole cell of the grid partition and the waypoints will be located at the centre of these cells. The path planning consists then in setting the order the cells should be gone through.To check the quality of the solution, the results are quantified by two figures:(i)
Distance(d) is the total distance travelled by the UAV.(ii)
Weight(w) is a factor that is calculated as(2)w=∑in∑jmorderi,j·Pi,j,where order is the correlative position of the cell (i,j) that is tracked and P is the potential risk/occupancy value of that cell. The meaning of this weight value is to quantify whether the most important cells, those with high P values, are tracked earlier than the other ones, so it is interesting to minimize it.The scenario for the four approaches is the 24 × 24 cell map shown in Figure4 that corresponds to the fire affected area in La Palma.


### 4.1. First Proposal: Attraction Approach

This so-calledattraction approach is based on the potential fields’ theory. In general, potential fields are used when the final point is known. A vector is calculated and its direction and magnitude depend on the distance to this final point, taking into account the obstacles or forbidden zones that could affect the trajectory.In our case, the final point is unknown. To define it, an attraction value is estimated for each cell so that the cell with the highest attraction value will be the next waypoint. The attraction value depends directly on the potential risk/occupancy of the cell and the distance to the current position (3). In this expression (3), Ai,j represents the ijth cell of the attraction matrix A and Pi,j the potential risk/occupancy associated with that cell. Covered matrix contains the historical information about whether the cell has been already tracked. That is, covered is a matrix with the same dimension as P and A, with value 1 for nontracked cells and 0 for traced ones. The denominator is the Euclidean distance from the ijth cell to the current position(3)Ai,j=Pi,j·Coveredi,jxij-x2+yij-y2.The algorithm tries to go to the points with highP values but near the current position, so further cells with high P values have less attraction than nearer points. Therefore, the trajectory is consistent and the UAV tracks low and high P cells minimizing the distance, but always being more attracted by higher P cells. If the distance was not taken into account, only P values would decide the waypoints, so the trajectory could have jumps from one waypoint to another and it may be bumpy.Nevertheless, according to this proposal, the attraction by the distance is bigger than by the potential risk/occupancy value. So, in fact, the trajectory tries to first minimize the distance and then the potential risk/occupancy. While minimizing the distance is interesting, to minimize the weight is even more important because it is crucial to go first to the cells where the probability of finding someone is higher. Thus, (3) is changed to (4) in order to have a more balanced relation between those factors:(4)Ai,j=Pi,j·Coveredi,jexp⁡xij-x2+yij-y2.In (4), the exponential function of the distance has been chosen because of its asymptotic behaviour. The very close cells will take advantage of the distance, but in a short term all the cells will be similarly affected, in opposition to previous linear relationship, where further cells had less chance to be explored than nearer ones.Two more improvements are made in order to get a better solution. The first one is about the continuity of the trajectory. To avoid jumps between consecutive cells a sequence of conditional rules is implemented. According to this, if two consecutive waypoints are located on the same vertical or horizontal line, all cells between these two points become automatically waypoints. This way these cells are considered already tracked and the UAV will not have to go backwards to explore them.The second enhancement of the algorithm is about the waypoint selection. The cell with the maximum attraction is chosen as waypoint, but sometimes more than one cell has the same maximum value. Initially the first maximum found was selected, so the path depended on the starting point. A control strategy has been applied to avoid this bias. The first waypoint will be the cell that, having the maximum attraction value, is surrounded by cells with higherP values than the other candidates; that is, it is located in areas with more P density. A matrix with this density, Pg, is generated, according to the following formula:(5)Pgi,j=∑n=i-2i+2∑m=j-2j+2Pm,nxij-xnm2+yij-ynm2,∀n≠i,m≠j.Then, after finding the maximum values of attraction of matrixA (4), a searching for the maximum Pg values (5) is carried out. The cell with highest density among the maximum attractions cells is selected as the next waypoint.With all these modifications, a simulation is run on La Palma map to show this approach (Figure5).Figure 5
La Palmaattraction path planning.The trajectory starts at the top left corner and covers the entire surface. It seems to be consistent, with good continuity. The value of the distance is 680 units and the weight is 37392. As expected, the trajectory starts going across the light blue cells to the green ones, to quickly cover the yellow part of the map (higherP values). When the UAV gets near yellow cells, it goes directly to it and then covers all the nearer low P cells, without wasting time exploring low P cells that are automatically considered visited. Then it goes to the other yellow zones and so on.To summarize, this original proposal works well and it is quite simple, but still the behaviour could be improved because there are some loops and paths cross each other. Other strategies will be tested.


### 4.2. Fuzzy Logic Approach

A different approach using fuzzy logic has been also implemented. A Mamdani Fuzzy Inference System (FIS) is designed with two inputs,P (potential risk/occupancy) and d (distance), and one output, attraction matrix (A). This way the contribution of the potential risk/occupancy value and the distance to the current position are separated and a nonlinear relationship between them is generated. For each input, three triangular and trapezoidal fuzzy sets have been assigned (high, medium, and low) and two for the output (high and low). The nine fuzzy rules are given in Table 4.Table 4
Rules of the fuzzy approach.
Rule P D A 1 High High High 2 Medium High Low 3 Low High Low 4 High Medium High 5 Medium Medium Low 6 Low Medium Low 7 High Low High 8 Medium Low High 9 Low Low HighSimulations were carried out on different scenarios to test this initial fuzzy approach. The results were worse than with the previous solution. When analyzing the evolution of the trajectory, we found that the UAV prefers to go to an adjacent cell with a lowerP value instead of going to further cells with high P values. In fact, the yellow cells are first surrounded by the UAV but not tracked until later.Although a FIS is usually designed and adjusted by an expert who knows the behaviour of the system, in this case the knowledge was quite poor. So, as the target is to minimize distance and risk, an optimization method can be used to tune the membership functions. That is, an evolutionary FIS is implemented, which consists of the same FIS proposed above but adjusted with genetic algorithms.The configuration of the GA must include the 32 parameters of the trapezoidal membership functions of the FIS. Each trapezoidal membership functions is defined by 4 points:x1, x2, x3, and x4. The value of these parameters must be correlative; that is, x1 must be smaller than x2, x2 than x3, and so on. These restrictions are defined by the linear constraints Ax<b, being b=0.001 in our case.The fitness criterion is a function of the weight and the distance, both normalized in the range[0,1] and to be minimized as follows:(6)f=1-∑i=1max⁡i∑j=1max⁡jPi,jw+1-max⁡i·max⁡jd.The rest of the GA parameters are shown in Table5.Table 5
GA parameters.
Generations 300 Initial population 200 Stall generations limit 100 Average relative change limit (TolFun) 10−10 Crossover fraction 0.8 Mutation distribution Gaussian, scale, and shrink equal to 1Initially, the process was so computationally slow that makes the problem unaffordable for this work. In order to reduce the computational time, we consider a smallerP map, and once the membership functions have been adjusted, it is scaled to a bigger one to see how it fits. Therefore, the GA is executed with the same configuration described but for a 5 × 5 P matrix.As an example, Figure6 shows the membership functions of the input variable distance (a) and the output surface (b) after the GA adjustment. In the surface it is possible to see high output values for short distances and also for high P values in long distances.Figure 6
Membership function of inputdistance (a) and fuzzy outputsurface (b).
(a) (b)A test is now carried out with the 25 × 25P map of La Palma (Figure 7), using the membership functions calculated for the 5 × 5 map.Figure 7
La Palma fuzzy logic path planning.The results ared=1497 and w=35951. Although the distance is much longer than in the attraction solution, weight is lower. Therefore we can say this solution also meets the target but with a stronger tendency to minimize risk/occupancy versus distance. However, the small angles that represent the transitions between two consecutive waypoints are not realistic and make the trajectory unaffordable for a UAV.The strength of this approach is the fast convergence to the highP value cells, visiting later the lower P cells. This means that, even covering all the cells in a longer time, since the weight is lower and it also quantifies the occupancy, the probability of finding people in a short time is higher.


### 4.3. ANFIS Approach

Another solution is implemented using an Adaptive-Network-based Fuzzy Inference System (ANFIS) [23]. The FIS is the same as the previous one but the membership functions are now modified by the ANFIS algorithm.Besides, a new input variable is included, the density matrixPg (5). Now the system is able to give higher attraction values to higher density areas, instead of only using this factor for the selection of the maximum.Therefore, the inputs areP, d, and Pg. The first two are normalized and the range of Pg is [0.5,5]. Three Gaussian membership functions are calculated for each variable. The output is again attraction matrix A. But ANFIS requires samples for training. Hence, we have generated 80 synthetic data sets manually. The training is performed during 50 epochs (Figure 8(a)). An example of the membership functions generated for the new variable Pg is shown in Figure 8(b).Figure 8
ANFIS training (a) andPg membership functions (b).
(a) (b)The new generated control surfaces are shown in Figure9. It is possible to observe the difference with the one shown in Figure 6(b). In this case they are smoother although clearly nonlinear.Figure 9
ANFIS fuzzy output surfaces:P-d, P-Pg, and Pg-d, respectively, from (a)–(c).
(a) (b) (c)Once the ANFIS has been generated, simulations are run on the real scenario of La Palma. The trajectory is shown in Figure10. The results obtained are d=808 and w=36284.Figure 10
La Palma ANFIS path planning.In this case, compared with the fuzzy logic solution (d=1497 and w=35951), the weight is higher but distance is much shorter, so it is not so easy to say which is better. However, what it is really interesting of this approach is how the UAV goes over the highest P cells first, finishing the searching on low P cells.


### 4.4. Using Particle Swarm Optimization (PSO)

Although the previous solutions seem to meet the main goal, they can be improved. In this case, an evolutive approach, a Particle Swarm Optimization (PSO) based solution is now proposed.The GA was used to obtain the order of the cells that should be visited. GA worked well in small size maps but, when scaled to the 25 × 25 map, some problems raised. In addition, in all the previous solutions, the waypoint calculation was very static, all the cells being tracked from its central point. Despite the assumptions made at the beginning regarding this way of tracking each cell, with this PSO solution, we try to find a continuous strategy.The approach is quite different. We start from the sameP map (24 × 24 cells), but every cell is divided by 10 to obtain a better discretization. Each new smaller cell has the same P value than the bigger cell that contains it. Once the map is so divided, the waypoints are searched applying the PSO algorithm.The variables of the PSO fitness function are the coordinates of the waypoints. The calculation is structured in groups of 10 waypoints, so there will be 20 variables: 10 “x” coordinates and 10 “y” coordinates. Then, the distance, the weight, and the number of tracked cells are calculated. It is clear that the distance has to be minimized, and the tracked cells need to be maximized, what implies that the UAV is travelling over the maximum number of new cells, since the tracked ones will not be taken into account more than once.To obtain the tracked cells, a straight path will be traced between two consecutive waypoints, and all the cells inside a square of 10 × 10 along the trajectory will be considered as tracked. That means that the UAV is continually taking images using the same area as in previous solutions. This is the first relevant modification.Another important modification is that in this case the weight will be maximized. In the previous approaches, a minimization of the weight was interesting because it meant that the UAV first went to the areas with highP cells. However, with this approach, it is more interesting the opposite because, as said, the calculation is made in bunches of ten waypoints. So, if the weight is maximized for the first ten points, the weight of the second ten points will be lower. That is, the UAV is going over the high P cells first.The relation between these factors is shown in the following:(7)f=1∑i=1max⁡i∑j=1max⁡jcoveredi,j0.1+1w0.1+1-1d.The rest of the configuration of the PSO algorithm is shown in Table6.Table 6
PSO configuration parameters.
Creation distribution Uniform Maximum iterations 4000 Stall Iterations limit 20 Average relative change limit (TolFun) 10−6 Swarm size 100 Inertia range [ 0.1,1.1 ]Once the setup is finished, the PSO algorithm is applied. The trajectory is shown in Figure11.Figure 11
La Palma PSO path planning.The values ofd and w are not now calculated because they are not relevant since the nature of the approach is totally different from the previous solutions. But it is worth seeing (Figure 11) how the trajectory has many straight lines covering all the possible space, especially between high P areas. Many more iterations could have been performed in order to cover the 100% of the map. However, we can also notice that the UAV goes forward and backwards to the same points, which means that this is not such an optimal solution.


## 4.1. First Proposal: Attraction Approach

This so-calledattraction approach is based on the potential fields’ theory. In general, potential fields are used when the final point is known. A vector is calculated and its direction and magnitude depend on the distance to this final point, taking into account the obstacles or forbidden zones that could affect the trajectory.In our case, the final point is unknown. To define it, an attraction value is estimated for each cell so that the cell with the highest attraction value will be the next waypoint. The attraction value depends directly on the potential risk/occupancy of the cell and the distance to the current position (3). In this expression (3), Ai,j represents the ijth cell of the attraction matrix A and Pi,j the potential risk/occupancy associated with that cell. Covered matrix contains the historical information about whether the cell has been already tracked. That is, covered is a matrix with the same dimension as P and A, with value 1 for nontracked cells and 0 for traced ones. The denominator is the Euclidean distance from the ijth cell to the current position(3)Ai,j=Pi,j·Coveredi,jxij-x2+yij-y2.The algorithm tries to go to the points with highP values but near the current position, so further cells with high P values have less attraction than nearer points. Therefore, the trajectory is consistent and the UAV tracks low and high P cells minimizing the distance, but always being more attracted by higher P cells. If the distance was not taken into account, only P values would decide the waypoints, so the trajectory could have jumps from one waypoint to another and it may be bumpy.Nevertheless, according to this proposal, the attraction by the distance is bigger than by the potential risk/occupancy value. So, in fact, the trajectory tries to first minimize the distance and then the potential risk/occupancy. While minimizing the distance is interesting, to minimize the weight is even more important because it is crucial to go first to the cells where the probability of finding someone is higher. Thus, (3) is changed to (4) in order to have a more balanced relation between those factors:(4)Ai,j=Pi,j·Coveredi,jexp⁡xij-x2+yij-y2.In (4), the exponential function of the distance has been chosen because of its asymptotic behaviour. The very close cells will take advantage of the distance, but in a short term all the cells will be similarly affected, in opposition to previous linear relationship, where further cells had less chance to be explored than nearer ones.Two more improvements are made in order to get a better solution. The first one is about the continuity of the trajectory. To avoid jumps between consecutive cells a sequence of conditional rules is implemented. According to this, if two consecutive waypoints are located on the same vertical or horizontal line, all cells between these two points become automatically waypoints. This way these cells are considered already tracked and the UAV will not have to go backwards to explore them.The second enhancement of the algorithm is about the waypoint selection. The cell with the maximum attraction is chosen as waypoint, but sometimes more than one cell has the same maximum value. Initially the first maximum found was selected, so the path depended on the starting point. A control strategy has been applied to avoid this bias. The first waypoint will be the cell that, having the maximum attraction value, is surrounded by cells with higherP values than the other candidates; that is, it is located in areas with more P density. A matrix with this density, Pg, is generated, according to the following formula:(5)Pgi,j=∑n=i-2i+2∑m=j-2j+2Pm,nxij-xnm2+yij-ynm2,∀n≠i,m≠j.Then, after finding the maximum values of attraction of matrixA (4), a searching for the maximum Pg values (5) is carried out. The cell with highest density among the maximum attractions cells is selected as the next waypoint.With all these modifications, a simulation is run on La Palma map to show this approach (Figure5).Figure 5
La Palmaattraction path planning.The trajectory starts at the top left corner and covers the entire surface. It seems to be consistent, with good continuity. The value of the distance is 680 units and the weight is 37392. As expected, the trajectory starts going across the light blue cells to the green ones, to quickly cover the yellow part of the map (higherP values). When the UAV gets near yellow cells, it goes directly to it and then covers all the nearer low P cells, without wasting time exploring low P cells that are automatically considered visited. Then it goes to the other yellow zones and so on.To summarize, this original proposal works well and it is quite simple, but still the behaviour could be improved because there are some loops and paths cross each other. Other strategies will be tested.


## 4.2. Fuzzy Logic Approach

A different approach using fuzzy logic has been also implemented. A Mamdani Fuzzy Inference System (FIS) is designed with two inputs,P (potential risk/occupancy) and d (distance), and one output, attraction matrix (A). This way the contribution of the potential risk/occupancy value and the distance to the current position are separated and a nonlinear relationship between them is generated. For each input, three triangular and trapezoidal fuzzy sets have been assigned (high, medium, and low) and two for the output (high and low). The nine fuzzy rules are given in Table 4.Table 4
Rules of the fuzzy approach.
Rule P D A 1 High High High 2 Medium High Low 3 Low High Low 4 High Medium High 5 Medium Medium Low 6 Low Medium Low 7 High Low High 8 Medium Low High 9 Low Low HighSimulations were carried out on different scenarios to test this initial fuzzy approach. The results were worse than with the previous solution. When analyzing the evolution of the trajectory, we found that the UAV prefers to go to an adjacent cell with a lowerP value instead of going to further cells with high P values. In fact, the yellow cells are first surrounded by the UAV but not tracked until later.Although a FIS is usually designed and adjusted by an expert who knows the behaviour of the system, in this case the knowledge was quite poor. So, as the target is to minimize distance and risk, an optimization method can be used to tune the membership functions. That is, an evolutionary FIS is implemented, which consists of the same FIS proposed above but adjusted with genetic algorithms.The configuration of the GA must include the 32 parameters of the trapezoidal membership functions of the FIS. Each trapezoidal membership functions is defined by 4 points:x1, x2, x3, and x4. The value of these parameters must be correlative; that is, x1 must be smaller than x2, x2 than x3, and so on. These restrictions are defined by the linear constraints Ax<b, being b=0.001 in our case.The fitness criterion is a function of the weight and the distance, both normalized in the range[0,1] and to be minimized as follows:(6)f=1-∑i=1max⁡i∑j=1max⁡jPi,jw+1-max⁡i·max⁡jd.The rest of the GA parameters are shown in Table5.Table 5
GA parameters.
Generations 300 Initial population 200 Stall generations limit 100 Average relative change limit (TolFun) 10−10 Crossover fraction 0.8 Mutation distribution Gaussian, scale, and shrink equal to 1Initially, the process was so computationally slow that makes the problem unaffordable for this work. In order to reduce the computational time, we consider a smallerP map, and once the membership functions have been adjusted, it is scaled to a bigger one to see how it fits. Therefore, the GA is executed with the same configuration described but for a 5 × 5 P matrix.As an example, Figure6 shows the membership functions of the input variable distance (a) and the output surface (b) after the GA adjustment. In the surface it is possible to see high output values for short distances and also for high P values in long distances.Figure 6
Membership function of inputdistance (a) and fuzzy outputsurface (b).
(a) (b)A test is now carried out with the 25 × 25P map of La Palma (Figure 7), using the membership functions calculated for the 5 × 5 map.Figure 7
La Palma fuzzy logic path planning.The results ared=1497 and w=35951. Although the distance is much longer than in the attraction solution, weight is lower. Therefore we can say this solution also meets the target but with a stronger tendency to minimize risk/occupancy versus distance. However, the small angles that represent the transitions between two consecutive waypoints are not realistic and make the trajectory unaffordable for a UAV.The strength of this approach is the fast convergence to the highP value cells, visiting later the lower P cells. This means that, even covering all the cells in a longer time, since the weight is lower and it also quantifies the occupancy, the probability of finding people in a short time is higher.


## 4.3. ANFIS Approach

Another solution is implemented using an Adaptive-Network-based Fuzzy Inference System (ANFIS) [23]. The FIS is the same as the previous one but the membership functions are now modified by the ANFIS algorithm.Besides, a new input variable is included, the density matrixPg (5). Now the system is able to give higher attraction values to higher density areas, instead of only using this factor for the selection of the maximum.Therefore, the inputs areP, d, and Pg. The first two are normalized and the range of Pg is [0.5,5]. Three Gaussian membership functions are calculated for each variable. The output is again attraction matrix A. But ANFIS requires samples for training. Hence, we have generated 80 synthetic data sets manually. The training is performed during 50 epochs (Figure 8(a)). An example of the membership functions generated for the new variable Pg is shown in Figure 8(b).Figure 8
ANFIS training (a) andPg membership functions (b).
(a) (b)The new generated control surfaces are shown in Figure9. It is possible to observe the difference with the one shown in Figure 6(b). In this case they are smoother although clearly nonlinear.Figure 9
ANFIS fuzzy output surfaces:P-d, P-Pg, and Pg-d, respectively, from (a)–(c).
(a) (b) (c)Once the ANFIS has been generated, simulations are run on the real scenario of La Palma. The trajectory is shown in Figure10. The results obtained are d=808 and w=36284.Figure 10
La Palma ANFIS path planning.In this case, compared with the fuzzy logic solution (d=1497 and w=35951), the weight is higher but distance is much shorter, so it is not so easy to say which is better. However, what it is really interesting of this approach is how the UAV goes over the highest P cells first, finishing the searching on low P cells.


## 4.4. Using Particle Swarm Optimization (PSO)

Although the previous solutions seem to meet the main goal, they can be improved. In this case, an evolutive approach, a Particle Swarm Optimization (PSO) based solution is now proposed.The GA was used to obtain the order of the cells that should be visited. GA worked well in small size maps but, when scaled to the 25 × 25 map, some problems raised. In addition, in all the previous solutions, the waypoint calculation was very static, all the cells being tracked from its central point. Despite the assumptions made at the beginning regarding this way of tracking each cell, with this PSO solution, we try to find a continuous strategy.The approach is quite different. We start from the sameP map (24 × 24 cells), but every cell is divided by 10 to obtain a better discretization. Each new smaller cell has the same P value than the bigger cell that contains it. Once the map is so divided, the waypoints are searched applying the PSO algorithm.The variables of the PSO fitness function are the coordinates of the waypoints. The calculation is structured in groups of 10 waypoints, so there will be 20 variables: 10 “x” coordinates and 10 “y” coordinates. Then, the distance, the weight, and the number of tracked cells are calculated. It is clear that the distance has to be minimized, and the tracked cells need to be maximized, what implies that the UAV is travelling over the maximum number of new cells, since the tracked ones will not be taken into account more than once.To obtain the tracked cells, a straight path will be traced between two consecutive waypoints, and all the cells inside a square of 10 × 10 along the trajectory will be considered as tracked. That means that the UAV is continually taking images using the same area as in previous solutions. This is the first relevant modification.Another important modification is that in this case the weight will be maximized. In the previous approaches, a minimization of the weight was interesting because it meant that the UAV first went to the areas with highP cells. However, with this approach, it is more interesting the opposite because, as said, the calculation is made in bunches of ten waypoints. So, if the weight is maximized for the first ten points, the weight of the second ten points will be lower. That is, the UAV is going over the high P cells first.The relation between these factors is shown in the following:(7)f=1∑i=1max⁡i∑j=1max⁡jcoveredi,j0.1+1w0.1+1-1d.The rest of the configuration of the PSO algorithm is shown in Table6.Table 6
PSO configuration parameters.
Creation distribution Uniform Maximum iterations 4000 Stall Iterations limit 20 Average relative change limit (TolFun) 10−6 Swarm size 100 Inertia range [ 0.1,1.1 ]Once the setup is finished, the PSO algorithm is applied. The trajectory is shown in Figure11.Figure 11
La Palma PSO path planning.The values ofd and w are not now calculated because they are not relevant since the nature of the approach is totally different from the previous solutions. But it is worth seeing (Figure 11) how the trajectory has many straight lines covering all the possible space, especially between high P areas. Many more iterations could have been performed in order to cover the 100% of the map. However, we can also notice that the UAV goes forward and backwards to the same points, which means that this is not such an optimal solution.


## 5. Multiple UAVs Approach

In SAR operations, more than one UAV is usually used. Swarm systems take advantage of simple local behaviours to collectively solve complex problems, where the capability of the group is greater than the sum of its parts [24, 25]. In this work, two different swarm formations of UAVs for discrete path planning are studied: free and distributed. The UAVs are identical but start from different positions at the map and among them they track all the desired area.The discrete path planning for several UAVs has been obtained by the attraction, fuzzy logic, and ANFIS approaches. The strategy is the same as the ones presented before for one UAV but now, for every iteration, the number of waypoints calculated is the same as the number of available vehicles. For simplicity, only 1, 2, or 3 UAVs are considered, but the solution could be extended to as many as needed.In the gridding map of La Palma, the starting point for a 2-UAV configuration is (13, 1) and (18, 1) for 3 UAVs.


### 5.1. Free Formation

Free swarm formation consists of running the path planning algorithm for two or more UAVs at the same time in parallel; that is, each UAV follows an independent path along the coverage area. When calculating new waypoints, the information about the cells tracked by other UAVs is supposedly available, so the rest of the UAVs do not have to visit any already tracked cell.As an example, Figure12 shows the trajectories for 2 and 3 UAVs (a and b, resp.), when the attraction approach is used to obtain the discrete path planning.Figure 12
La Palma attraction path planning with 2 UAVs (a) and 3 UAVs (b), free formation.
(a) (b)The results obtained with the attraction path planning approach ared=680, w=37393 for 1 UAV; d = 713, w = 19638 for 2 UAVs; and d = 720, w = 12812 for 3 UAVs in free formation. The distance is quite similar in all the cases, but the weight is much lower with more than one UAV.This effect on the weight is due to the parallel searching. As explained for a single UAV, the weight is calculated multiplying the order each cell is tracked by itsP value, and getting the sum for all cells. In this case, there are two cells with order 1, two with order 2 and so on, until the UAVs reach half of the number of cells.The searching time is supposed to be reduced because although the distance is similar, it is shared by several UAVs, so the maximum distance travelled is now about a half or even a third of the distance travelled by only one UAV.Regarding the path, it is interesting to see how the two UAVs (Figure12(a)) converge to the green area in the middle of the map at the beginning. Then they separate each other and search in different high P value areas. At the end, they converge again in low P value areas. With 3 UAVs, the convergence is not as evident as in this case, meaning a more distributed tracking of every zone.In all the cases, the trajectories of the different UAVs cross each other. This does not mean collision because the UAVs are not at the same point at the same time. However, the path planning must be completed with a collision avoidance algorithm, which is out of the scope of this work.The free formation cannot be implemented with the PSO approach due to the nature of the solution, as explained before. For the ANFIS approach, the results are similar, the worst case being the fuzzy one.


### 5.2. Distributed Swarm Formation

A distributed swarm formation of UAVs means that the map is divided into several parts, as many as vehicles, and each UAV is assigned an area which it must track.The path planning for 2 and 3 UAVs in a distributed swarm formation with the attraction path planning is shown in Figure13. It is possible to see how each UAV tracks an independent zone and their paths do not cross. The distances are now d = 673 for 2 UAVs and d = 678 for 3 UAVs, and the weights w = 20411 and w= 13712, respectively. The distance is similar but slightly longer than with only one UAV (680) and slightly better than the travelled distance obtained with UAVs in free formation (713 and 720). Regarding the weight, it is much smaller than the case of one UAV (37392) and much better for 3 UAVs than with 2 UAVs.Figure 13
La Palma attraction path planning with 2 UAVs (a) and 3 UAVs (b), distributed formation.
(a) (b)The same experiments have been carried out with different number of UAVs for the different approaches proposed (fuzzy logic and ANFIS).


### 5.3. Comparison of the Approaches with Different Number of UAVs

Finally, Table7 summarizes the results of the different approaches for the two configurations. As expected, the results improve when the number of UAVs is increased. This is mainly due to the way the weight is calculated and proves the validity of the proposed strategies.Table 7
Comparison between the different approaches.
Formation 1 UAV 2 UAV 3 UAV Free Distributed Free Distributed w d w d w d w d w d Attraction 37393 680 19638 713 20411 673 12812 720 13712 678 Fuzzy logic 35951 1497 17931 1550 19219 1212 12137 1596 13119 1155 ANFIS 36284 808 18579 827 19474 716 12520 876 13386 732In general terms, it can be seen how the different methods have strong and weak points. The attraction method is the one with shortest paths, followed by the ANFIS one. However its weights are slightly higher than the other methods. Indeed, the fuzzy logic one has the lowest weight values although the difference is not big, but with much longer distances that the other two methods. In that sense, the ANFIS method has the most balanced results, with medium weights and low distance values.To summarize, it is difficult to say which is better. It depends on the priority of the goals. The quickest is the attraction strategy, but the fuzzy approach is the best one finding people, at least visiting the areas where it is most probable to find someone. We will check these results on a real case in the next section.


## 5.1. Free Formation

Free swarm formation consists of running the path planning algorithm for two or more UAVs at the same time in parallel; that is, each UAV follows an independent path along the coverage area. When calculating new waypoints, the information about the cells tracked by other UAVs is supposedly available, so the rest of the UAVs do not have to visit any already tracked cell.As an example, Figure12 shows the trajectories for 2 and 3 UAVs (a and b, resp.), when the attraction approach is used to obtain the discrete path planning.Figure 12
La Palma attraction path planning with 2 UAVs (a) and 3 UAVs (b), free formation.
(a) (b)The results obtained with the attraction path planning approach ared=680, w=37393 for 1 UAV; d = 713, w = 19638 for 2 UAVs; and d = 720, w = 12812 for 3 UAVs in free formation. The distance is quite similar in all the cases, but the weight is much lower with more than one UAV.This effect on the weight is due to the parallel searching. As explained for a single UAV, the weight is calculated multiplying the order each cell is tracked by itsP value, and getting the sum for all cells. In this case, there are two cells with order 1, two with order 2 and so on, until the UAVs reach half of the number of cells.The searching time is supposed to be reduced because although the distance is similar, it is shared by several UAVs, so the maximum distance travelled is now about a half or even a third of the distance travelled by only one UAV.Regarding the path, it is interesting to see how the two UAVs (Figure12(a)) converge to the green area in the middle of the map at the beginning. Then they separate each other and search in different high P value areas. At the end, they converge again in low P value areas. With 3 UAVs, the convergence is not as evident as in this case, meaning a more distributed tracking of every zone.In all the cases, the trajectories of the different UAVs cross each other. This does not mean collision because the UAVs are not at the same point at the same time. However, the path planning must be completed with a collision avoidance algorithm, which is out of the scope of this work.The free formation cannot be implemented with the PSO approach due to the nature of the solution, as explained before. For the ANFIS approach, the results are similar, the worst case being the fuzzy one.


## 5.2. Distributed Swarm Formation

A distributed swarm formation of UAVs means that the map is divided into several parts, as many as vehicles, and each UAV is assigned an area which it must track.The path planning for 2 and 3 UAVs in a distributed swarm formation with the attraction path planning is shown in Figure13. It is possible to see how each UAV tracks an independent zone and their paths do not cross. The distances are now d = 673 for 2 UAVs and d = 678 for 3 UAVs, and the weights w = 20411 and w= 13712, respectively. The distance is similar but slightly longer than with only one UAV (680) and slightly better than the travelled distance obtained with UAVs in free formation (713 and 720). Regarding the weight, it is much smaller than the case of one UAV (37392) and much better for 3 UAVs than with 2 UAVs.Figure 13
La Palma attraction path planning with 2 UAVs (a) and 3 UAVs (b), distributed formation.
(a) (b)The same experiments have been carried out with different number of UAVs for the different approaches proposed (fuzzy logic and ANFIS).


## 5.3. Comparison of the Approaches with Different Number of UAVs

Finally, Table7 summarizes the results of the different approaches for the two configurations. As expected, the results improve when the number of UAVs is increased. This is mainly due to the way the weight is calculated and proves the validity of the proposed strategies.Table 7
Comparison between the different approaches.
Formation 1 UAV 2 UAV 3 UAV Free Distributed Free Distributed w d w d w d w d w d Attraction 37393 680 19638 713 20411 673 12812 720 13712 678 Fuzzy logic 35951 1497 17931 1550 19219 1212 12137 1596 13119 1155 ANFIS 36284 808 18579 827 19474 716 12520 876 13386 732In general terms, it can be seen how the different methods have strong and weak points. The attraction method is the one with shortest paths, followed by the ANFIS one. However its weights are slightly higher than the other methods. Indeed, the fuzzy logic one has the lowest weight values although the difference is not big, but with much longer distances that the other two methods. In that sense, the ANFIS method has the most balanced results, with medium weights and low distance values.To summarize, it is difficult to say which is better. It depends on the priority of the goals. The quickest is the attraction strategy, but the fuzzy approach is the best one finding people, at least visiting the areas where it is most probable to find someone. We will check these results on a real case in the next section.


## 6. A Case Studied

To analyze and prove the validity and utility of the discrete path planning proposals presented in this paper, they are going to be compared on a SAR real scenario.Thirty missing people have been randomly located on the potential risk/occupancy map of La Palma. A uniformly distributed random generator gives a value that is associated with each cell of the map. Then, this value is multiplied by half of the potential risk/occupancy value of that cell. The resulting 25 positions with the highest value are selected. In this way we obtain a random distribution but weighted towards areas with highP values. The remaining 5 cases are manually distributed on areas with low P values (Figure 14). These last ones are set as the first five cases to be found so that they can be easily located in the graphs showing the time results of the searching.Figure 14
La Palma missing people.The main criterion used to test the strategies is the time the UAV needs to find each of the 30 people individually. It is supposed to be proportional to the distance. All the UAVs are considered to have the same technical characteristics and to fly at the same speed (set to 3). Another assumption has been considered to make the simulation more realistic. When the UAV is tracking a cell, its speed is lower than when it is moving between different areas (tracking speed = 1).Each case (finding someone) is evaluated estimating the time it takes the UAV to get there from the initial position with a particular configuration (strategy and formation).When the cases are evaluated, the time that each method and its training require is calculated. For each case there is a method with a particular formation that has been the fastest, it is a winner; and there has been another one that has been the slowest, that is, a loose one. There should be a total of 30 wins and 30 loses adding all the possible configurations and strategies results, but there are some more because since the space and the speed are discretized, in some cases, there are ties.In this way, we can compare the different methods, to see which are the best one exploring lowP zones or high P cells and so on.


### 6.1. Finding People with the Attraction Strategy

The time results for attraction path planning are shown in Table8. The number of wins represents the number of times that a specific configuration was the best one among the others. The number of losses represents when it was the worst one.Table 8
Time results with attraction strategy.
1 UAV 2 UAVs 3 UAVs Free Distributed Free Distributed Mean 217.62 113.88 115.60 88.84 87.60 Wins 1.00 2.00 2.00 3.00 1.00 Losses 6.00 0.00 5.00 0.00 0.00  Total wins 9.00  Total losses 11.00Figures15 and 16 show the comparison between different number of UAV for this strategy. Time unit is represented in the vertical axis and the case in the horizontal one.Figure 15
La Palma attraction path planning results for free swarm.Figure 16
La Palma attraction path planning results for distributed swarm.As expected, the time is reduced when the number of UAVs increases. Besides, the first five points need more time because they have lowP values, so the UAV goes there after going to the higher P ones.A comparison between the two swarm configurations with the same number of UAVs is shown in Figure17 (free, f1; distributed, f2). We can observe that with two UAVs the difference is not significant. Nevertheless, with three UAVs, even having a similar tendency, there are big differences in some of the cases, which indicates that the searching is done with a very different philosophy.Figure 17
La Palma attraction path planning results for 2 UAVs (a) and 3 UAVs (b).
(a) (b)


### 6.2. Fuzzy Logic Path Planning

The results obtained with the fuzzy logic path planning are shown in Table9.Table 9
Time results with fuzzy logic path planning.
1 UAV 2 UAVs 3 UAVs Free Distributed Free Distributed Mean 257.90 120.02 109.71 84.95 59.05 Wins 0.00 0.00 2.00 3.00 9.00 Losses 11.00 0.00 1.00 0.00 0.00  Total wins 14.00  Total losses 12.00In this case, there are more winning configurations. The worst ones are almost exclusively associated with the use of only one UAV. That means that this method is inefficient for one UAV, but its efficiency is highly improved when increasing the number of UAVs, especially in distributed formation.


### 6.3. ANFIS Path Planning Results

The results obtained for the ANFIS path planning are shown in Table10.Table 10
Time results with ANFIS path planning.
1 UAV 2 UAVs 3 UAVs Free Distributed Free Distributed Mean 212.70 117.33 107.94 74.99 86.23 Wins 0.00 3.00 2.00 8.00 3.00 Losses 8.00 0.00 0.00 0.00 0.00  Total wins 16.00  Total losses 8.00Although this method seems to be the best one in terms of finding people, it has the same problem as the fuzzy logic approach. That is, better results are obtained with free swarm formation than with the distributed one; the worst case is again with an only UAV. Anyway, this strategy gives the best average values for this scenario.


### 6.4. PSO Path Planning Results in a SAR Mission

PSO path planning obtains the worst results of all. This method does not work well because the UAV travels long distances between waypoints in order to cover the surface with a distance/speed relation of one. Due to the continuous tracking, the UAV is very slow in comparison to the other methods. All results obtained are worse than with the other solutions, with many losses, meaning that the UAV did not find that people (Figure18).Figure 18
La Palma PSO path planning results.In view of these results, PSO is not taken into account for the global comparison between the different methods.


## 6.1. Finding People with the Attraction Strategy

The time results for attraction path planning are shown in Table8. The number of wins represents the number of times that a specific configuration was the best one among the others. The number of losses represents when it was the worst one.Table 8
Time results with attraction strategy.
1 UAV 2 UAVs 3 UAVs Free Distributed Free Distributed Mean 217.62 113.88 115.60 88.84 87.60 Wins 1.00 2.00 2.00 3.00 1.00 Losses 6.00 0.00 5.00 0.00 0.00  Total wins 9.00  Total losses 11.00Figures15 and 16 show the comparison between different number of UAV for this strategy. Time unit is represented in the vertical axis and the case in the horizontal one.Figure 15
La Palma attraction path planning results for free swarm.Figure 16
La Palma attraction path planning results for distributed swarm.As expected, the time is reduced when the number of UAVs increases. Besides, the first five points need more time because they have lowP values, so the UAV goes there after going to the higher P ones.A comparison between the two swarm configurations with the same number of UAVs is shown in Figure17 (free, f1; distributed, f2). We can observe that with two UAVs the difference is not significant. Nevertheless, with three UAVs, even having a similar tendency, there are big differences in some of the cases, which indicates that the searching is done with a very different philosophy.Figure 17
La Palma attraction path planning results for 2 UAVs (a) and 3 UAVs (b).
(a) (b)


## 6.2. Fuzzy Logic Path Planning

The results obtained with the fuzzy logic path planning are shown in Table9.Table 9
Time results with fuzzy logic path planning.
1 UAV 2 UAVs 3 UAVs Free Distributed Free Distributed Mean 257.90 120.02 109.71 84.95 59.05 Wins 0.00 0.00 2.00 3.00 9.00 Losses 11.00 0.00 1.00 0.00 0.00  Total wins 14.00  Total losses 12.00In this case, there are more winning configurations. The worst ones are almost exclusively associated with the use of only one UAV. That means that this method is inefficient for one UAV, but its efficiency is highly improved when increasing the number of UAVs, especially in distributed formation.


## 6.3. ANFIS Path Planning Results

The results obtained for the ANFIS path planning are shown in Table10.Table 10
Time results with ANFIS path planning.
1 UAV 2 UAVs 3 UAVs Free Distributed Free Distributed Mean 212.70 117.33 107.94 74.99 86.23 Wins 0.00 3.00 2.00 8.00 3.00 Losses 8.00 0.00 0.00 0.00 0.00  Total wins 16.00  Total losses 8.00Although this method seems to be the best one in terms of finding people, it has the same problem as the fuzzy logic approach. That is, better results are obtained with free swarm formation than with the distributed one; the worst case is again with an only UAV. Anyway, this strategy gives the best average values for this scenario.


## 6.4. PSO Path Planning Results in a SAR Mission

PSO path planning obtains the worst results of all. This method does not work well because the UAV travels long distances between waypoints in order to cover the surface with a distance/speed relation of one. Due to the continuous tracking, the UAV is very slow in comparison to the other methods. All results obtained are worse than with the other solutions, with many losses, meaning that the UAV did not find that people (Figure18).Figure 18
La Palma PSO path planning results.In view of these results, PSO is not taken into account for the global comparison between the different methods.


## 7. Discussion of the Global Results

A comparison between the different methods and configurations is carried out and the global results are discussed. To have a good overview, every strategy has been applied to the same 30 cases, with the two possible formations when more than one UAV is used in the searching.First, Figure19 shows the three different searching strategies with one UAV. The time results are very similar but, in general, ANFIS path planning is slightly better. The three methods work well with low P cells, but attraction gets shorter time than the others finding those worse cases.Figure 19
La Palma path planning results comparison for 1 UAV.In Figures20 and 21, the path planning results for two and three UAVs, respectively, in free swarm formation are shown. Results are again quite similar. Fuzzy logic path planning seems to be somewhat worse than the others.Figure 20
La Palma results comparison for 2 UAVs in free formation.Figure 21
La Palma results comparison for 3 UAVs in free formation.For distributed swarm configuration, Figures22 and 23 show the results for 2 and 3 UAVs, respectively. The results for 2 UAVs are once again similar for all methods, having the ANFIS approach a slightly better performance.Figure 22
La Palma results comparison for 2 UAVs in distributed formation.Figure 23
La Palma results comparison for 3 UAVs in distributed formation.However, in Figure23, it is possible to see that there is a big difference between the fuzzy logic approach and the others. This method works better in distributed swarm maybe because it was designed for smaller maps, so when the searching area is smaller, the performance of this approach improves.Finally, Figure24 shows the average time of each configuration for every approach. According to these results, the fastest configuration for searching is to have 3 UAVs in distributed swarm formation (f2), as expected, and fuzzy logic approach gives the best results for this particular configuration, having ANFIS and attraction similar searching time.Figure 24
La Palma path planning mean time for all the configurations and every approach.Nevertheless, regarding the number of losses and wins (Figure25), which is a critical factor, the ANFIS method is in general the best one. The fuzzy logic has also a very good performance, especially for distributed configurations, as it has been said. However, even having less number of wins, attraction method is the most consistent due to its small number of losses, which indicates that its results are quite balanced.Figure 25
La Palma wins (a) and losses (b) cases.
(a) (b)As a summary, we can say that the attraction method gets medium positions regarding efficiency. It performs a regular and extensive search, which implies that it does not take it a lot of time finding people in lowP areas, but it does not go as fast as other methods to high P values zones. This method works very well for homogenous P maps.Fuzzy logic presents a quite fast convergence but it is very irregular. However, it works well in maps with large highP areas due to its type of searching, which performs like a random search in all dangerous areas.The ANFIS approach has been proven to be the best one in general terms. It has a fast convergence to highP values and also performs a quite regular searching on the rest of the cells. It works worse on low P areas that are far from high P ones, where other methods have obtained better results.


## 8. Conclusions and Future Work

In this work, two main contributions are presented. The first one is a fuzzy map generation of a searching area according to a risk/occupancy factor that aims at search and rescue (SAR) missions. The second one is the application of different intelligent strategies for discrete path planning to cover a gridding searching area.Regarding the map characterization, the conclusion is that it helps to focus the path planning on promising zones. The path planner finds trajectories that minimize the risk the people are exposed to. Indeed, in the simulations results, a fast tracking of the higher probability risk/occupied areas can be observed that results in a quicker finding of the people involved in a dangerous situation.Four intelligent strategies have been applied to the discrete path planning, namely, attraction, an original one, and fuzzy, ANFIS, and PSO. Except this last one, the rest have obtained good results in terms of searching time and distance. Another conclusion is that the performance of the method strongly depends on the associated probability map. This remarks the importance of the generation of this map, taking into account all the possible variables and factors that can influence the searching.Using multiple UAVs in swarm formation for the searching, a dependence on the type of path planning method has been observed. In general, distributed formation works better, but it should be chosen in association with theP map and the path planning method.Future works related to several aspects of this work could be the following:(i)
Studying other factors for the map characterization and their influence on the potential risk/occupancy value, which has been proved important for the SAR mission(ii)
Working with a more realistic model of the UAVs, including the dynamics [26], and also avoidance and visual tracking algorithms [27](iii)
Testing the most successful proposals on real systems.



---

*Source: 6879419-2018-04-23.xml*