When natural disasters, such as earthquakes, occur, rapid deployment of rescue operations is extremely important, in order to avoid an increase in loss of lives. Moreover, we cannot even count on the presence of public communications networks and infrastructures such as internet or mobile communication, that could be disrupted. In this context, Unmanned Aerial Vehicles (UAVs) can make the di erence, contributing to reduce the costs, resources, and human risks in support of more e cient Search & Rescue operations.
It is reasonable to assume that civil defense constantly possesses an updated map of every town and village considered at risk and, for every relevant building, it has the information about the necessary time to over y it entirely and the level of importance. Civil defense can have in very few minutes a clear idea of the boundary of the a ected area and set the level of importance of the buildings and sites that have been subjected to some damages based on emergency calls and on the moment when the earthquake happened: just to make a single example, if it was during the night or in summer, schools are assigned a very low priority; vice-versa, if it happened in the morning of the school year, schools will receive the highest priority. Civil Defense usually has a \National Plan for seismic risk prevention" in which each region of the country is analyzed, to assess the risk, that is, to identify the areas that, in the event of a seismic wave, may be subject to ampli cation phenomena and provide useful indications for urban planning and rescue operation.
Then, we consider that on hand of civil defense is a eet of q homogeneous
asynchronous UAVs u1; : : : ; uq taking o from the operations center v0. Each
UAV has a battery that corresponds to B 2 R+ units of ying time; when it
is run-down, it takes R 2 R+ (with R B: current estimate is, for example,
1:5B R 2B [
We consider the emergency situation after a natural disaster (e.g., an
earthquake) and the main issue of over ying the whole zone employing the eet of
UAVs, acquiring information as soon as possible by sensors and/or cameras
mounted on UAVs, to have a clear idea about the places where rescue teams are
more necessary. So, the aim of our problem consists of assigning to every UAV
an ordered set of sites to over y so that the whole eet can inspect all the areas
of interest as soon as possible giving precedence to the sites with higher
priority. Since our situation is time-critical, we allow having a certain number b 0
of batteries that can be separately recharged while UAVs are in ight. These
batteries can be quickly swapped out in seconds with those exhausted without
causing any delay using methods such as those proposed in [
We consider two di erent scenarios, according to the devices civil defense can count on and the assumptions we are able to do on the environment.
In the rst scenario, each UAV is equipped with an RGB commercial camera, it has neither computational power nor communication devices. In this case, the only thing UAVs can do is to follow an assigned route through some sensible targets, record a video and bring it back to the operations center; there, an image detection/recognition tool will be able to detect in parallel on all videos possible survivors needing help in real-time. The fact that the videos must be brought back to the base before being processed can cause a waste of time. However, the positive side of this scenario is that the eet can be easily constituted by a large number of UAVs because they are very cheap.
In the second scenario, we considered high-cost UAVs, so they have a processing unit with good computational power, and can be equipped with a device allowing them to communicate with the base at every time (e.g., a radio); so we can assume they are able to scan in real-time the videos while recording them and immediately detect and recognize whether there is an emergency; in case some people requesting help are detected, they promptly decrease their altitude, closer to the possible survivors, acquire additional information concerning detected people possibly in di culty and send to the base a radio message, so that a rescue team is sent. Note that the radio onboard is also exploited to inform the base in real-time about the battery status and the capability to over y a further site.
In order to model the described context, we consider a complete node- and edge-weighted graph G = (V; E; dist; ; p), where: { V = fv0; v1; : : : ; vng: v1; : : : ; vn are the sites representing the points of interest inside the area, i.e., buildings (or areas) that need to be explored, while v0 represents the operations centre. { Each node is associated with two di erent values, a function p that represents the priority and a function , that represents the time needed to explore a site. In the rst scenario, (v) represents the only ( xed) time to y over each site. In the second scenario, it may be necessary to add to (v) a second contribution due to the time that the UAV needs to take more precise information concerning detected people and send a message to the base. { Every (undirected) edge e = (vi; vj ) 2 E, with i 6= j, is associated with a distance function dist that represents the symmetric traveling distance between two nodes.
The aim of our problem consists of assigning to every UAV an ordered set of sites to over y so that the whole eet can inspect all the areas of interest as soon as possible giving precedence to the sites with higher priority. Since UAVs are prone to their battery constrain, they could be not able to visit all sites assigned to them in a unique ight, but need to perform more than one ight, after each of them returning to the base for either recharging or substituting its battery. Thus, we have to assign to each UAV an ordered set of cycles all passing through v0, whose weights are bounded by B, such that all nodes of the graph are over own, giving precedence to those with higher priority, and in such a way an opportune optimization function is minimized. Of course, in the two scenarios, the situation is di erent and hence also the solution is. In particular, it is worth to be noticed that, while in the rst scenario the times needed to explore each site are exact, in the second one they are not.
Let us de ne a sequence Sui as a set of cycles that are assigned to UAV ui. Then, a solution set SOL is set of sequences for each UAV that covers V , i.e., if for every v 2 V there exists a cycle in SOL containing v.
We informally de ne the completion time of a site as the time necessary to know whether there are people needing help in it. Given a node, in the rst scenario, this occurs only after that the video of the cycle including it has been delivered to the base and the portion corresponding to it has been analyzed In the second scenario, instead, this occurs as soon as the node has been completely over ight. In this extended abstract, we omit the formalization of the de nition of completion time of site v, cost(i)(v; SOL), where i = I; II and refer to, respectively, to the rst and second scenario described above.
We now de ne two functions that exploit the concept of completion time of a site and are useful to evaluate the goodness of a solution: The weighted latency, wL and the completion time ct. Formally,
v2V wL(i)(SOL) = 1 X p(v)cost(i)(v; SOL) where i = I; II: n (1) and ct(i)(SOL) = max cost(i)(v; SOL) where i = I; II:
v2V
Observe that, while ct(i) does not take into account the priority of nodes, not only in wL(i) priorities are taken into account, but sites with the highest priority should be served rst to have a smaller value of wL(i), in order to associate a larger multiplicative factor (corresponding to priority) to a smaller sum of costs. We call HPSF (Higher Priority Sites First) this implicit problem requirement.
Clearly better solutions for our scenario will have smaller values of ct and wL, from which it follows the formal de nition of our problem:
Given a complete node- and edge-weighted graph G = (V; E; dist; ; p) and a set of q homogeneous UAVs u1; : : : ; uq, the problem Cover by Multitrips with Priorities (CMP) consists in nding a set SOL of q sequences such that ct(i)(SOL), where i = I; II, is minimized and Requirement HPSF is addressed.
It is easy to see that CMP is a generalization of the well known m-TSP [
We propose four di erent heuristics, each one based on a di erent consideration but all based on a meta-algorithm that is run at the operations center; it consists of a number of iterations going on until all sites have been over ight; at each iteration, a cycle for each UAV is produced as output and its length is guaranteed to be bounded by B. The meta-algorithm (and hence all the heuristics) provably terminate in a nite time whose an upper bound can be analytically determined in both scenarios.
This meta-algorithm can be run also as a preprocessing algorithm in order to do some preliminary estimates on the necessary completion time and the best number of necessary additional batteries and of UAVs.
We evaluate and compare the performance of the proposed heuristics running extended experimentation on two types of randomly generated graphs: we position n points, varying n between 50 and 200, placed either uniformly at random or with a Poisson point process in a unit square. This latter distribution is intended to simulate building collapses in some speci c zones.
We remand to the full version of the paper the interested reader for a detailed description of the graphics out-coming from the experimental results.