Abstract
Over the last several decades advancement in UAV technology has formed an important part of recent research. Nowadays, these flying robots are a great aid and even replace humans in many types of critical activities such as surveillance, fire protection, search & rescue (SAR), etc. In this paper, we study the design of SAR system using autonomous quadrotors UAVs. The developed system attempts to maximize the probability of target detection and minimize the expected search time while also minimizing the number of UAVs required. It is also adapted to counter UAV failures by re-configuring the UAVs to optimally continue the mission. Furthermore the SAR system algorithms are designed to accomplish the mission with a minimum amount of control information to be passed between UAVs. Finally a case study of survivor search and rescue operations is provided along with the obtained results which confirm the efficiency of the designed system.
Introduction
After and even during a disaster, infrastructure and services like communication links are interrupted, roads are blocked and buildings collapse. Under this situation roads are covered with debris leading the disaster struck region to be completely unreachable. Subsequently, the need for immediate support to the survivors is necessary, due to the fact that the probability to remain alive is reduced as time advances. Transporting humans and material to disaster locations can take too much time, and rescuers often risk their own safety during such operations in their attempt to rescue any victim. Consequently, the need for robot systems in crisis management to complete tasks a human could not is generated.
SAR operations are considered as critical missions, a considerable organizational capability to aid as fast as possible the disaster victims is required. An overview for the use of UAVs for SAR applications could be found in [1]. The growing recognition of the potential use of UAVs is supported by an increasing number of utilities spanning in many areas, including human detection and localization [2], mission planning [3], networking and data processing [4], collaborative SAR missions [5], assisted UAV task allocation and trajectory planning [6, 7], etc. Many types of SAR missions are defined depending on the environment and the situation of the targets. Survivors could be on mountain in an avalanche events [8], in marine [9], facing a fire [10], or even in a closed building [11]. The reference [12] describes the design a robotic Autonomous Unmanned Aerial System (AUAS), namely the ROLFER (Robotic Lifeguard for Emergency Rescue) system, which aim to immediately provide rescue and lifesaving services.
International civil authorities and emergency services start to give an important part to SAR operation using UAVs due to the difficulties in adequately managing crises, The European Union ICARUS project on this subject is introduced in [13]. The ICARUS project proposes to equip first responders with a comprehensive and integrated set of unmanned search and rescue tools, to increase the situational awareness of human crisis managers, such that more work can be done in a shorter amount of time.However the previous cited works describe the different parts of a SAR system, but no one has presented a full designed autonomous system that takes into consideration all the contributed parts (i.e. mission planning, autopilot system, search strategy and targets geo-localization).
Various algorithms and techniques have been proposed for searching targets: Reference [14] studies different search strategies based on greedy heuristics, potential-based algorithms and partially observable Markov decision, while [15] proposes a bio-inspired self-organized search strategy. In reference [16] search strategies provided by the international maritime organization and international civil aviation organization, and published annually in IAMSAR (International Aeronautical and Maritime Search and Rescue) manual are used. Despite the development of many heuristics and probabilistic problem-solving techniques for SAR search problem, published procedures still deliver approximate solution and mostly fail to cover the integrity of searching area and include the probability of detection/observation model, questioning their real expected relative efficiency.
Due to the limited flight time of such UAVs (a few ten minutes) and the fact that search and rescue missions are time critical, the use of multiple UAVs rather than one UAV plays an important role. Many works were published in the field of SAR operation using Multi-UAVs such as [17] where a SAR system using quadrotors with an embedded camera is presented. Paper [18] proposes the use of multi-agents flooding algorithm for the SAR operations in an Unknown terrain. For path planning of the agents swarm, the reader can refer to [3] for a multi-target approach of a multi-agents SAR drones. SAR operation can also be executed by a team of heterogeneous robots; an online collaborative mission planning is explained in [19].
On the other hand coordination and cooperation strategies between the different agents can be found in [20, 21, 22], several subject were treated such as cooperative path finding, task allocation and distributed decision and control systems. References [23, 21, 24] focus over search strategies and collaborative searching within multi-agents system. For this propose an optimal hybrid PSO-GA algorithms for swarm control is given in [25].
The objective of this work is to develop an efficient search and rescue methodology for employing a UAV swarm in order to efficiently locate Survivor targets within the search region. To summarize, here are some contributions and the corresponding features that distinguish our work from others:
In this work low cost, small scaled UAVs with a maximum payload are used, which impose them to respect the UAVs load limitations. To address these challenges, we have divided the UAVs into two teams: Search team and rescue team. The UAVs of the search team are equipped with high quality sensors and communication devices, to perform the detection mission and coordinate their actions. On the other hand, the rescues UAVs have no detection sensors on board, so they can carry a first aid kit, water or food for the survivors. For a multi-UAV system robustness is a critical parameter thus, fault tolerance is included in such way that the failure of one UAV does not make the mission unsuccessful. For search and rescue scenarios, time is critical and we need also to satisfy some requirements in terms of mission time and energy optimization.
This paper is organized as follow: Section 2 introduces a presentation of the designed SAR system. Section 3 presents the different SAR strategies using multi-UAV and their path patterns. Section 4 discusses the sensor coverage, target detection and task allocation algorithms used for the navigation system. Simulations and SAR strategies comparison are in Section 5. Finally, Section 6 presents a conclusion and the future recommendations are provided.
For the proposed SAR application, a system of homogeneous quadrotor UAVs is designed. All the UAVs can coordinate and cooperate their actions in order to complete a desired mission. The human interaction is supposed to be minimized since all the UAVs are considered to work in a decentralized/distributed architecture, and failure of one UAV will not affect the whole mission. Each UAV is capable of performing its mission independently due to the embedded sensors. During the SAR operation, all the UAVs are able to share their collected data (e.g., locations, states, and images) with direct communication amongst themselves and the control station. The architecture of the designed system is shown in Fig. 1.
SAR scenario.
SAR operation description and challenges.
SAR operations are executed using a small group of pre-defined swarm flying patterns. The flying patterns are based on IAMSAR standard search strategies that guarantees a successful completion of the mission. The initial number of UAVs in the pattern is decided (by ground control station) prior to the launch, and each UAV is given the pattern, its position in the pattern, and the dictionary of allowable alternative patterns. The communication link between the UAVs is assured via keeping a limited distance in order to keep all agents within the communication range. Information about the UAV status and the collected data must be exchanged between UAVs and the control station. Task re-allocation is used to modify the search in the event of a UAV loss, this allows an efficient and automatic reconfiguration of the UAVs array, in the case of a UAV malfunction.
Each UAV has the capability to detect and avoid the obstacles in its environment. The swarm is also robust over the external disturbances and the bad weather conditions, in the case of a failure to track the search pattern due to wind, the mission is then cancelled and the base control station is informed.
For a complete mission, the UAVs are divided into two teams depending on the allocate mission, one for search and the second for rescue as shown in Fig. 2 Each UAV is equipped with inboard sensors that are adequate with the mission requirements. The goal of the mission is to track the search strategy pre-defined pattern and locate the survivors using on board sensors. Once the target is identified, the survivor’s geographic position is sent to the other swarm agents and to the ground control station, using a direct communication link or via the team leader which play the role of a relay, transmitting the information to the control ground station. Once the survivors are positioned, the rescue team starts its mission to feed the survivors with firs aid, water and food.
Rescue operation represents the second leg of the SAR operation. Depending on the number of the UAVs used, the rescue can start after completing the search operation (all the survivors positions are known, they are then gathered in form of collections), or it can be real time operation, where a rescue UAV is dedicated to every detected survivor, which requires a lot number of rescue UAVs.
Having distributed architecture ensures that the UAVs can coordinate with each other directly and not necessarily all the traffic refer to the base station. An autonomous control of navigation and detection with distributed control for collision avoidance of the UAVs is also introduced. Though, if a centralized structure is not applicable or it does not improve the system performance (e.g., pre-planning), decisions are made in a distributed manner. SAR missions are summarized into the following phases:
As illustrated in Fig. 3, during a typical scenario the quadrotors UAVs will be used to deploy an area of interest, perform sensory operations to collect evidence of the presence of a victim, and report their collected information to a remote ground station or rescue team.
SAR system architecture.
This section explains the context of the designed system and presents the different search strategies for Multi-UAV swarms. The proposed mission is that the SAR UAVs scan the desired area, search for any possible Survivors, and then rescue them just after a disaster (tsunami, earthquake, hurricane, explosion, …).
There are two main strategies to scan the disaster area using Multi agents UAVs: A centralized/decentralized squadron search strategy by creating a squadron of drones that fly in formation, or a distributed independent search strategy that is based on dividing the area into rectangular sub-areas, each sub-area being assigned to a drone. Both strategies are investigated in the next sections.
The advantage of the Squadron search is that the drones fly close to each other (see Fig. 4) in a centralized or decentralized architecture. Thus, all drones can easily converge to a detected event when one of the drones detects one. However, the drawback of this solution is that the provided substitution network does not cover the whole area to explore: as the drones fly close to each other, they can easily communicate with each other, but the squadron is concentrated in a small area and is isolated from the remainder of the network.
Figure 4 shows the exploration search using 6 UAVs (2 rows of 3 drones each). The red path shows the trajectory for drone 1. Depending on the shape of squadron, the separation distance c squadron is estimated in accordance with the width W of the area and the number of UAVs (by assuming that the length of the trajectory is the same for all the drones).
Squadron searching strategy.
Multi-ships IAMSAR standard searching strategy.
The IAMSAR proposes the following searching pattern for the multi-ship searching (Fig. 5):
Parallel sweep: for use by two ships. Parallel sweep: for use by three ships. Parallel sweep: for use by four ships. Parallel sweep: for use by five or more ships.
This strategy is based on dividing the area into rectangular sub-areas, with each sub-area being assigned to a drone (or a swarm of drones). The advantage of the independent search is that the substitution network provided by the drones covers a wider surface. Moreover, as for the squadron exploration, this network is very stable (the distances between the drones remain constant). However, the drones are farther from each other, and this implies a larger delay when they need to gather at a given location.
Searching and detection
Sensor coverage
The sensors ability to detect a victim in the prevalent conditions will significantly affect the maximum altitude at which the UAVs can operate.
Sensor coverage.
Lets consider that the sensing areas on the ground cover surface
Lets we consider a sensing model accounting for false positive and false negative:
The probability of sensing a target at height The probability of not sensing a target at height The probability of not sensing a target at height The probability of sensing a target at height
With
Observation model
For this work a fixed searching high of 100 m above the earth is used in order to maintain an acceptable values of
Target detection presents the searching algorithm used depending on the searching strategy, where the UAV scan the hall area and report any target detection to the base station. The mission is completed whenever all the targets are detected (if the number is limited) or the hall area is scanned, it also can be canceled if any fault is occurred, for all the cases the base station is reported about the mission situation.
Target Detection Initialization
Tasks allocation
When a failure occurs in one of the swarm agents it stops its mission and executes an emergency landing. The neighbored agents in the communication range are then informed. Depending on the agent health, the task of the failed agent is allocated to the other agents. A re-planning of the task of every allocated agent is occurred and the new path is designed. Switching the scanning strategy is necessary to scan all the remained area.
Tasks AllocationInputInput KwToto KwByby Beginnbeginnende
Two 2 agents decentralized searching strategy.
Five 5 agents decentralized searching strategy.
Ten 10 agents searching strategy.
Five 5 agents centralized searching strategy.
Two 10 agents centralized searching strategy.
This section is concerned to test the ability of the quadrotors swarm to track the desired generated trajectory of the different SAR strategies patterns, while the second part presents a full case study of a SAR operation using multi-UAV swarm.
Several scenarios for the different multi-agents architectures are simulated to demonstrate the quadrotors swarm ability of scanning different shapes, detect any possible Survivors, and then report their position to the base station or support team to start the rescue operation.
The supposed search area is supposed to be with a total surface of 1000 m
Centralized vs decentralized searching strategy.
Five 5 agents searching strategy with one agent failure.
Ten 10 agents searching strategy with one agent failure.
Five 5 agents distributed searching strategy.
Rescue agents UAVs.
This function gives altitude of the given coordinate (
Squadron search
This section investigates the effects of using multi agents quadrotors in SAR operation. As mentioned before the quadrotors swarm mission is to scan the desired area using a parallel (sweeping) motion strategy. Figures 7–8 show the results of the simulated scenario using 2, 5 and 10 quadrotors UAVs with centralized architecture.
Simulation results of the decentralized architecture with 2 and 5 UAVs are shown in Figs 10 and 11.
From the obtained results it is clear that the desired area was scanned completely in all the cases. The target pattern was also tracked with high accuracy; the collusion between the agents was avoided since the separation distance is maintained.
A comparison between the searching time for the centralized and decentralized architecture using 2, 5 and 10 UAV agents is shown in Fig. 12.
Figure 12 shows that the searching time is decreasing whenever the number of agents is increasing, since the scanned area is divided between the different agents, the searching time is decreasing from 817 sec when using 2 agents to 330 sec with 5 agents and finally to 165 with 10 agents, which means that all the 10 Survivors were detected in less than 3 min with 10 quadrotors agents.
It is also important to mention that the number of agents is related to many factors, such as the number of the available agents, the possible starting points, the communication links, the scanned area surface division, and the sensor coverage area. Saturation is reached whenever a limitation over the previous factors exists.
Distributed independent search
A simulated scenario of an agent failure and task allocation using 5 and 10 agents is shown in Figs 13 and 14.
From Figs 13 and 14 it can be noticed that a failure occurred to the agent 2 at Y
In the case of 10 agents the only the agent number 1 is allocated because of the agent 3 bad health, the allocated agent switches its strategy and successfully complete the mission.
SAR case study
In this section a full scenario of search and rescue operation is presented. The mission is then divided into two legs, one for search and Survivor detection and the second for rescue operation. The same environment is maintained as in the previous scenario but with new methodology.
Search operation
For search and detection mission a decentralized distributed method is used. With 5 UAVs (One leader and four followers), the swarm is scanning the area with a hybrid expanding/contour searching strategy is used. As shown in Fig. 15 the swarm agents start from points
UAV 5 is considered as the leader of the swarm since its mission is to coordinate, assist and direct the mission. Only the leader can have the communication with the base station, all the others UAV are supposed to be within the communication range of the leader.
By the end of the mission the swarm has a meeting point to exchange the information about the searching operation. The meeting points are as follow:
Rescue operation
After receiving the Survivors position from the leader of the swarm, an estimation of the Survivors collection is done in order to minimize the number of the rescue UAVs. In our case six rescue UAVs denoted R1R6 are used to rescue six collections of Survivors (see Fig. 16). The collection is defined by the Survivors in a range of a circle with a radius of 100 m.
Each rescue UAV is equipped by a first aid kit, and it starts from the base station and go directly at the desired collection. All the UAV are flying at a flight level that is situated at 120 m, which means that they are above the mountains, and bellow the searching team, no collisions can occurs!
Table 2 presents the rescue time for each collection. All the Survivors are rescued in less than 3 minutes, which reflect the efficiency of the operation.
Rescue operation time
Rescue operation time
This chapter studied the application of search and rescue operations using multi-agents quadrotors drones. SAR strategies were developed in accordance to many possible UAVs. All the obtained results for the different strategies were judged to be satisfactory, since the quadrotors swarm has successfully followed the desired generated path, coordinated their movements and collaborated to finish the mission, even in the case of any agent failure.
Both decentralized and distributed search strategies were applied and compared in order to obtain the most adequate method. A conclusion about the factors that affect the search operation and the different requirement is then given.
Finally a full study case of search and rescue operation is presented using five quadrotors UAVs organized in a decentralized distributed method with a hybrid expanding/contour searching strategy. The searching and rescuing time is evaluated to be very promising compared to the other strategies.
