The Covering-Assignment Problem for Swarm-powered Ad-hoc Clouds: A Distributed 3D Mapping Use-case

The popularity of drones is rapidly increasing across the different sectors of the economy. Aerial capabilities and relatively low costs make drones the perfect solution to improve the efficiency of those operations that are typically carried out by humans (e.g., building inspection, photo collection). The potential of drone applications can be pushed even further when they are operated in fleets and in a fully autonomous manner, acting de facto as a drone swarm. Besides automating field operations, a drone swarm can serve as an ad-hoc cloud infrastructure built on top of computing and storage resources available across the swarm members and other connected elements. Even in the absence of Internet connectivity, this cloud can serve the workloads generated by the swarm members themselves, as well as by the field agents operating within the area of interest. By considering the practical example of a swarm-powered 3D reconstruction application, we present a new optimization problem for the efficient generation and execution, on top of swarm-powered ad-hoc cloud infrastructure, of multi-node computing workloads subject to data geolocation and clustering constraints. The objective is the minimization of the overall computing times, including both networking delays caused by the inter-drone data transmission and computation delays. We prove that the problem is NP-hard and present two combinatorial formulations to model it. Computational results on the solution of the formulations show that one of them can be used to solve, within the configured time-limit, more than 50% of the considered real-world instances involving up to two hundred images and six drones.


Introduction
An Unmanned Aerial Vehicle (UAV) -otherwise commonly known as drone -is a flying vehicle whose weight can vary, according to the targeted applications, from a few hundreds grams to hundreds of kilos. The popularity of drones is rapidly increasing across the different sectors of the economy. Aerial capabilities and relatively low CAPEX/OPEX costs make UAVs the perfect solution to improve the efficiency of those operations that are typically carried out by humans, e.g., building inspection, photo collection, area surveillance, etc.
In normal operations, drones are remotely controlled by human pilots through wireless remote controls. However, by setting the UAV autopilot in auto off-board mode, a drone can operate in a fully autonomous manner by following the inputs generated by an on-board flight computer directly connected to the autopilot. This capability can be leveraged to create fleets of autonomous UAVs collaborating to fulfill the desired missions. This is achieved by installing a arXiv:2004.11837v1 [eess.SP] 21 Apr 2020 collaborative drone application on each on-board flight computer of the fleet and by connecting these latter on the same wireless network.
The possibility of organizing drones in fleets of autonomous and collaborating entities naturally attracted the attention of swarm robotics scientists [1]. Swarm robotics studies how to reproduce, with the help of artificial agents, those swarming behaviors typically observed in nature -in ant colonies, bee swarms, bird flocks, etc. Swarm behaviors have the potential to revolutionize the world of robotized applications -including UAV applications -because of their promise of jointly achieving maximum performance and maximum resilience through the power of distributed interactions that do not require any form of centralized supervision.
In a complex mission, the UAV swarming component is typically dedicated to data collection duties, e.g., taking pictures, producing video feeds, sniffing wireless signals. Other technologies are then involved in processing the collected data and producing the desired output. For instance, digital photogrammetry algorithms [47,48], can be leveraged to elaborate the images collected by the swarming UAVs, by extracting and displaying the relevant 2D/3D geometric information.
The data-processing phase -3D processing phase in the photogrammetry use-case [49,50,51,52,53,54] -is typically executed in the cloud and in a centralized fashion [55]. However, to mitigate Internet connectivity and network latency issues, the distributed power of the UAV swarm can be leveraged to establish an ad-hoc cloud infrastructure on top of which executing the data processing phases of the considered mission [55,56,57,58]. This approach aims to exploit the power of the many -many embedded microcomputers of limited power are installed on the swarming UAVs -to replace the computer power typically available in a powerful work station reserved in the cloud. This paper addresses the problem of optimizing the exploitation of a swarm-powered ad-hoc cloud, by jointly dealing with two interrelated aspects of the data-processing stage: • the workload generation, i.e., definition of the computing application elements and of the corresponding set of data input.
• the workload scheduling/assignment, i.e., mapping of computing application elements and physical swarm members.
In particular, we consider the generation and placement of workloads whose input data are subject to geolocation/clustering constraints. Practically speaking, the collected data are bound to a location and must be processed in batch of neighboring samples: in the 3D reconstruction use-case, this means that groups of neighboring pictures have to be processed by the same computing element. This additional constraint has a non-negligible impact when dealing with a swarm powered ad-hoc cloud: due to the distributed nature of the swarm-powered data collection stage, the whole input data-set may end up being completely scattered across the UAVs of the swarm. If not properly dealt with during the workload generation/scheduling processes, this aspect may severely deteriorate the whole process performance due to unnecessary data transmission delays (input data must be received by the corresponding computing application element).
For the purpose of illustrating the applicability of our approach to a real-life application, we adjust the proposed solution to a relevant use-case scenario from the emergency response field. Our use-case is a perfect example of a real-life application subject to geolocation constraints that highly benefits from swarm-powered ad-hoc cloud infrastructure [59]. In fact, the drone swarm is able to perform 3D reconstruction of a region of interest -comprising five hundred photos -on top of twenty Raspberry Pis [60] microcomputers [61].
In such context, the 3D map of a given region of interest is used to improve the decision making process and the operator situational awareness through the availability of a 3D digital twin of the operation area, where the elements of interest can be even selectively highlighted, e.g., building or road damages, risky areas, etc. Producing the relevant 3D maps in a timely manner (near real-time), even when the cloud connectivity is not available, is crucial to increase the chances of success of an operation. To this purpose, we introduce a new optimization problem, namely the Covering-Assignment Problem for swarm-powered ad-hoc clouds (CAPsac). Given a set of geo-positioned aerial pictures (data) that are physically distributed across a set of UAVs (stored on the embedded microcomputers on the drones), CAPsac minimizes the 3D mapping (data-processing phase) completion time by jointly computing: • the optimal workload configuration/the optimal covering of photos, i.e., splitting the overall photographed region across multiple convex sub-regions, and • the optimal workload scheduling/the optimal assignment of photographed sub-regions to UAVs, i.e., deciding which drone (its embedded microcomputer) is responsible for the 3D reconstruction of a photographed sub-region.
It is worth pointing out that, differently from the decompose-then-allocate and the allocate-then-decompose paradigms [62] broadly adopted in (both the cloud computing optimization and) the multi-robot task allocation literature, CAPsac is an integrated decision model that handles workload generation (photo covering or sub-region splitting) and workload assignment (sub-region to UAV assignment) at the same time.
The remainder of the paper is organized as follows. The next section formally introduces the CAPsac problem, by clearly highlighting how the general problem designed for swarm-powered ad-hoc clouds is naturally applied to optimize the execution of a distributed 3D mapping application. Once the relationship between the general problem and the specific 3D mapping use-case will have been clearly proved through Section 2, it will be possible to present the remainder of the paper by directly referring to the latter. We believe that this editing approach will allow the reader to better grasp the details and the added value of the proposed solution. Two mathematical programming formulations to solve the CAPsac problem are described in Section 3 while Section 4 presents the NP-hardness proof for the problem. Finally, Section 5 presents and discusses the computational results obtained by experimenting with realistic 3D reconstruction instances, while Section 6 summarizes our concluding remarks.

Covering-Assignment Problem for Swarm-powered Ad-hoc Clouds -CAPsac
A swarm-powered mission can be typically decomposed in two phases: i Data collection: the UAVs of the swarm dynamically collaborate to collect all the necessary information within the area of interest. In a swarm-powered 3D mapping mission, this phase corresponds to the photo-collection process meant to shoot the required aerial photos of the selected area. Note that the set of required pictures is typically computed by a dedicated mapping software and is merely an input of the mapping mission.
ii Data processing: the collected data are collaboratively processed by the ad-hoc cloud built on top of the microcomputers installed on the UAVs to produce the desired output. During this process, thanks to the swarm-powered ad-hoc cloud, the computing workload can be parallelized over the available computing units. Furthermore, the collected data can be transferred over the inter-drone wireless network to satisfy the input requirements of the distributed processing tasks. In a swarm-powered 3D mapping mission, this phase corresponds to the 3D-processing process meant to compute a 3D point cloud and/or a 3D mesh of the selected area.
The proposed CAPsac problem deals with the optimization of the data (3D) processing phase and has no direct control on the data (photo) collection strategy. Given the set of data (aerial pictures) just collected by the UAVs, CAPsac aims at minimizing the overall processing time required to compute the desired output (3D map).
An explanatory CAPsac problem instance involving a swarm of four drones performing a 3D mapping mission is represented in Fig. 1. The full lines delimit the area of interest represented by the set P of aerial pictures just captured by the four drones during the photo collection phase. Each photo p ∈ P was taken by a specific drone (which also stores it in memory). Furthermore, each picture must be processed during the 3D processing phase to guarantee a proper reconstruction. Figure 1: Explanatory instance of CAPsac problem accordingly to the 3D mapping use-case.
In Fig. 1, the positions of the four drones are represented by the large symbols "×", "+", " ", and "•". Not all drones may be equipped with microcomputers powerful enough to support the 3D processing workload. In the example of Fig. 1, only two drones are considered 3D-capable, those represented by the + and the × symbols.
Each photo is characterized by its shooting location, which is denoted by the small versions of the symbols previously used to represent the UAVs: the pictures represented by a small + were shooted by the drone represented by the large +, and so on. Note that, given the dynamic nature of the decentralized decision-making process employed by the swarm of drones [62], it is impossible to know a-priori which UAV will shoot which picture.
A solution of the CAPsac problem describes how to: • Split the processing workload into multiple processing (application) components, each responsible for dealing with a specific subset of the collected data, e.g., of the aerial pictures. Note that in the 3D reconstruction use-case each 3D reconstruction sub-task corresponds to a specific sub-region and requires as input all the aerial pictures that belong to that sub-region.
• Assign each processing component and all its corresponding input data to at least one of the computing elements available within the swarm-powered ad-hoc cloud, i.e., the microcomputers installed on the swarming-UAVs or on any other ground element connected to the swarm itself.
The optimal solution of CAPsac minimizes the latest processing time among all the involved computing elements, which corresponds to minimizing the makespan of the whole 3D reconstruction process. Three main issues cannot be ignored when assigning the photos (and thus the sub-regions) to the optimal 3D processing drones. Note that for sake of simplicity, we consider the case of not more than one computing device available on each drone.
i A feasible region (workload) subdivision is characterized by the creation of a spatial-convex covering: the union of the sub-regions corresponds to the whole region and the photos associated to each sub-region must be a spatial-convex set. Accordingly, a photo can be assigned to a drone if and only if it lies inside the convex hull of all the photos assigned to that drone. Fig. 2 illustrates a set of photos which is not spatial-convex. The assigned photos are represented by colored "•" symbols. The "•" symbols represent photos that do not belong to the set, which are hence assigned to other drones. Spatial-convex sets are crucial to perform the 3D mapping procedure since the presence of non-overlapping photo footprints (represented by the dashed colored rectangles in Fig. 2) makes the 3D reconstruction of the associated region impossible. Fig. 3 shows an example of a photo spatial-convex set assigned to one 3D-capable drone. It is worth pointing out that the creation of a spatial-convex covering is required by any workload operating over geo-located/clustered data to be processed in neighboring batches.  Figure 3: Spatial-convex set and the respective convex hull.
ii As the sub-regions (and their corresponding pictures) are assigned to the 3D-capable drones, a drone may need to require some input pictures (data) from the other swarm members. The CAPsac considers a pre-defined single-tree network topology built by a networking middleware running on the swarming drones [63]. Note that in Fig. 4, the network links are represented by the pointed lines. Besides, in a single-tree network topology, only one routing path exists to connect each pair of UAVs. A drone cannot start the 3D reconstruction of the assigned sub-region until all the required photos are received. The TCP communication protocol is widely applied in engineering to achieve reliable transmissions and flow control, and it is adopted to model the swarm communications in the CAPsac problem. According to [64], a good way to approximate the transmission behavior concerning the TCP protocol is to assume that the transmission rate allocation follows the Max-Min Fairness -MMF paradigm [65]. Thus, minimizing the makespan of the 3D reconstruction requires that all the transmission rates of the network follow the MMF paradigm. iii Finally, a reliability factor should be considered to immunize the CAPsac assignment with respect to drone malfunctions. The reliability factor defines the minimum number of drones (computing elements) that should process each sub-region. Fig. 4 shows a feasible solution to the CAPsac problem optimizing the makespan of a 3D mapping mission and considering a reliability factor equal to one. The dashed and the dashed-and-pointed lines define a feasible spatialconvex covering. The number of sets comprising the covering is equal to the number of 3D-capable drones. For instance, the covering in Fig. 4 has only two sets. The photos lying within the left sub-region are processed by drone +, whereas those in the right sub-region are elaborated by drone ×. Given that the relationship between the general CAPsac and the swarm-powered 3D mission use-case has been clearly established, we will present the remainder of the paper referring directly to the specific use-case. Thus, it will be possible to the reader to better grasp the details and the added value of our proposed optimization problem. Table 1: CAPsac parameters in the context of the 3D mapping use-case. Parameters Description λ p estimated processing time of a photo p µ p amount of data of a photo p in Mb θ dp equal to 1 if drone d has the photo p stored in its memory F set of traffic demands between each pair of drones reliability factor m number of drones (equiv. number of sub-regions) which can perform 3D reconstruction T maximum allowed time for exchanging photos between drones 3 Mathematical programming formulations

Common definitions
Let us consider a swarm of drones D of different types which is responsible for the 3D reconstruction of a region described by the set P of photos. LetD ⊆ D, with |D| = m, be the set of 3D-capable drones that have enough computing power to support the 3D reconstruction workloads. The location of all photos p ∈ P are also known.
Given a photo p ∈ P , let λ p and µ p be the non-negative real parameters representing, respectively, the estimated processing time of p and the storage space occupied by p (expressed in megabytes). Also, for each drone d ∈ D, let θ dp be the binary parameter equal to 1 if photo p ∈ P is stored on drone d. The subset of photos processed by a drone directly corresponds to a specific sub-region. Therefore, note that the number of sub-regions are hence equal to the number of 3D-capable drones available in the swarm.
Some pictures may have to be transferred among different drones to respect the computed sub-region assignment configuration. The picture transmission is supported by an undirected transmission tree T =(N, A), where the nodes of set N correspond to the swarming drones and the arcs of set A represent the device-to-device communication links (e.g., Wi-Fi links) between the drone themselves. Furthermore, let F be the set of traffic demands defined for each pair of drones (h, d) ∈ D ×D, where f hd denotes the demand (possibly null) between drones h and d. For all demands in F , let V hd be the set of links (i, j) ∈ A in the sole routing path between h and d in T . Also for each (i, j) ∈ A, denote c ij the transmission capacity of the link (i, j), and F ij = {F hd ∈ F |(i, j) ∈ V hd }, i.e., the set of demands that use the link (i, j) for transmission purposes. Finally, the maximum allowed time for transmitting the traffic demands through the network is denoted byT .
With the support of the notation just introduced -grouped in Table 1, we present two different Mixed-Integer Linear Programming (MILP) formulations to optimize the 3D-processing phase of 3D mapping missions with UAV swarms: • The Photo-based CAPsac (pCAPsac), where sub-regions are defined by explicitly assigning each picture p ∈ P to the corresponding sub-regions.
• The Region-based CAPsac (rCAPsac), where all the feasible rectangular sub-regions are given; the formulation is responsible for selecting the optimal set of sub-regions among those available.

Photo-based CAPsac
In the pCAPsac formulation, the decision variables will be optimized to compose R = {1, . . . , m} sub-regions (equiv. subsets of photos) to be reconstructed by the set of drones. The formulation aims to jointly perform two assignment operations: • each picture p ∈ P is assigned to one sub-region r ∈ R, • each non-empty sub-region r ∈ R is assigned to one 3D-capable drone d ∈D.
To this purpose, let y r p and x r d be the binary variables equal to 1 when, respectively, photo p ∈ P is assigned to sub-region r ∈ R, and sub-region r ∈ R is assigned to drone d ∈D. Furthermore, let g r dp be the binary variables equal to 1 if drone d ∈D is assigned to a sub-region r ∈ R that contains picture p ∈ P .

Assignment constraints
To obtain a proper 3D-reconstruction, each photo must be processed at least one time, i.e., it must belong to at least one sub-region: Similarly, each sub-region must be assigned to at least σ 3D-capable drones, with σ representing the previously introduced reliability factor meant to immunize the system toward possible drone failures: Finally, let us introduce the group of constraints necessary to correctly compute the g variables without introducing any non-linearity: That is, constraints (3)-(5) are the classical McCormick inequalities [66].

Spatial-convexity constraints
To properly work, state-of-the-art 3D reconstruction algorithms have to deal with convex regions and/or sub-regions, which is also equivalent to work with spatial-convex sets of photos. To this purpose, we approximate the convex hull of the set of photos assigned to a drone by its smallest enclosing hyperrectangle. This is not a bad approximation since 3D mapping missions often considers 50% to 80% of photo overlapping [67].
Since the GPS position of each photo shooting point is known, let C be the set of distinct picture longitudes and let L be the set of distinct photo latitudes. Note that the following relations are always respected: 1 ≤ |C| ≤ |P | and 1 ≤ |L| ≤ |P |. For each sub-region, there exists a finite set of photo latitudes and longitudes that represents the bounding rectangular box, i.e. the approximated boundaries of the sub-region.
The boundary of a sub-region r is defined by its left (α r ), right (β r ), bottom (γ r ), and top (ω r ) borders. Binary variables α r c , β r c , γ r , and ω r are used to designate the latitudes and the longitudes defining these borders: • Binary variable α r c is equal to one if longitude c ∈ C delimits the left border of sub-region r ∈ R, • Binary variable β r c is equal to one if longitude c ∈ C delimits the right border of sub-region r ∈ R, • Binary variable γ r is equal to one if latitude ∈ L delimits the bottom (inferior) border of sub-region r ∈ R, • Binary variable ω r is equal to one if latitude ∈ L delimits the top (superior) border of sub-region r ∈ R.
Each sub-region r ∈ R must be associated to a unique tuple of borders: To respect the sub-region convexity, a photo p ∈ P can be assigned to sub-region r ∈ R if and only if p is contained within the boundary defined for r. Geometrically, such constraint is fulfilled when (i) lng α r ≤ lng p ≤ lng β r and (ii) lat γ r ≤ lat p ≤ lat ω r , where the lat stands for the latitude and lng for longitude. To capture this geometrical pattern, for each photo p, the sets L p α , L p β , L p γ , L p ω are defined as: • L p α = {c ∈ C|lng c ≤ lng p }, i.e., L p α contains the longitudes on the left of lng p , • L p β = {c ∈ C|lng c ≥ lng p }, i.e., L p β contains the longitudes on the right of lng p , i.e., L p ω contains the latitudes above lat p .
Finally, the sub-region convexity is modeled by the Boundary Constraints -BC 1 , expressed as: Constraints (10)  However, a photo p is not assigned to sub-region r if and only if it lies outside the boundary of r, i.e., if lng p < lng α r , or lng p > lng β r , or lat p < lat γ r , or lat p > lat ω r , which may be expressed by either or Given constraints (6)-(9), constraints (14) guarantee that at least one of left-side summations is equal to one when p is not assigned to the sub-region r (i.e., y r p = 0). Consequently, at least one boundary of r makes the photo p to lie outside r. In a complimentary way, constraints (15) force that at most three boundaries are satisfied when the photo p is not assigned to the sub-region r.
Moreover, let us define valid inequalities (namely Ordering inequalities) to preemptively remove the infeasible boundaries in the continuous space for any possible sub-region. For instance, a boundary is infeasible if the the right border is placed on the left side of the left border. Such boundaries are removed through the following set of ordering inequalities:

Photo transmission constraints
For the purpose of minimizing the 3D processing computation time, it cannot be ignored that an additional delay is introduced any time a picture is transmitted by the drone where it is currently stored, to the drone that is responsible for reconstructing the corresponding sub-region. Given a demand f hd ∈ F , letc hd represent the minimum link capacity on routing path V hd and let z hd be the binary variable equal to 1 if traffic demand f hd > 0 is active, i.e., if at least one picture has to be transferred from drone h ∈ D to drone d ∈D. In this case, non-negative real variables φ hd are used to represent the transmission rate achieved by traffic demand f hd on its routing path.
The following two groups of constraints are introduced to, respectively, correctly activate binary variables z, and force flow variables φ to 0 when the corresponding traffic demands are idle and force the upper bound on the transmission rate, otherwise: Given a demand f hd , let w hd ij be the binary variable equal to one if link (i, j) is a bottleneck of f hd , as well as let u ij be the highest transmission rate among all the traffic demands carried by a link (i, j) ∈ A, i.e., u ij = max Thus, the following groups of constraints are used to impose the MMF paradigm for all the swarm communications (the photo transmissions) in pCAPsac [69]: Constraints (22) ensure that all the active demands have at least one bottleneck link on their routing path. The capacity of each link (i, j) ∈ A is respected through inequalities (23). The first condition required to consider a link (i, j) to be a bottleneck is jointly handled by constraints (23) and (24), which ensure that any bottleneck link (for at least one traffic demand) is saturated. The second bottleneck condition is instead fulfilled via constraints (25) and (26). Constraints (25) force u ij to to be greater or equal to the highest transmission rate among the demands that are flowing through link (i, j). Finally, constraints (26) guarantee that φ hd will not be exceeded by any other transmission rate of traffic demands routed over link (i, j) ∈ A when (i, j) is a bottleneck link of traffic demand f hd .
In pCAPsac formulation, a maximum networking/transmission latency ofT seconds is imposed for each activated traffic demand: The summation term r∈R,p∈P g r dp θ hp µ p computes the overall amount of data to be transferred from drone h ∈ D to the drone d ∈D. Limiting the transmission times means to ensure every drone receives all the photos belonging to the assigned sub-region within a maximum prefixed time set by the domain expert. This constraint can be relaxed by settingT to a suitable very high value.

Symmetry breaking constraints
Formulation pCAPsac suffers from symmetry in both photo-to-sub-region (i.e., y r p ) and sub-region-to-drone (i.e., x r d ) assignments. It is possible to partially break the symmetry of the sub-region-to-drone assignments. Each subregion can be assigned to one distinct drone in advance. That is, m variables x r d are fixed where the fixed pairs { (r 1 , d 1 ), . . . , (r m , d m )} ∈ {R ×D} have distinct indexes. Considering Fig. 1, the sub-region 1 could be assigned to the drone "+" and the sub-region 2 to the drone "×" for instance. Note that setting variables x r d does not affect the variables y r p . Consequently, just redundant integer solutions are eliminated.

Complete formulation
Let T max be the 3D mapping completion time, i.e., the makespan, calculated as the maximum processing time obtained from the swarm of drones. The variable T max is computed by the group of constraints where r∈R,p∈P (g r dp λ p ) computes the required time to process all the photos assigned to drone d ∈D. Finally, the pCAPsac formulation is expressed by the following MILP. x r d , y r p , g r dp ∈ {0, 1} ∀r ∈ R, ∀p ∈ P, ∀d ∈D The objective function (29) minimizes the makespan of the whole 3D mapping procedure. The domain constraints are given by (30)- (35). As |R| = |D|, the total number of constraints in the model is O(|P | · |D| 2 ) as well as the number of its variables.

Region-based CAPsac
The CAP sac problem can be addressed by explicitly considering the set S of all feasible rectangular subsets of photos, such that each element of S corresponds to a possible rectangular sub-region to be 3D-reconstructed. It is important to remark that the cardinality of S is polynomial and bounded by O(|C| 2 |L| 2 ), which is O(|P | 4 ) in the worst scenario: Proposition 1. Given a set S comprising all feasible rectangular sub-regions to a CAPsac instance. The |S| is bounded by O(|C| 2 |L| 2 ), which is O(|P | 4 ) in the worst case.
Proof. As in Section 3.2.2, any feasible hyperectangle S ∈ S is defined by a tuple (α S , β S , γ S , ω S ) of latitudes and longitudes corresponding to the left, right, bottom, and top borders of S, respectively, with α S , β S ∈ C and γ S , ω S ∈ L, and such that α S ≤ β S and γ S ≤ ω S . Therefore, S = C × C × L × L. Since 1 ≤ |C| ≤ |P | and 1 ≤ |L| ≤ |P |, |S| is bounded by O(|P | 4 ).
In particular, the photos are commonly spread across the target region in a grid pattern to fulfil photo footprint overlapping constraints [67]. Consequently, |C| and |L| are usually far smaller than |P |, and hence, |C| 2 · |L| 2 is in practice usually significantly smaller than |P | 4 .
Let S p be the collection of rectangular subsets S ∈ S which cover photo p ∈ P . For each set S ∈ S, denote t S the photo processing time of S, and µ hd S the amount of data to transfer from drone h ∈ D to the drone d ∈D if S is selected. Let q S d be the binary variables equal to 1 if S is allocated to drone d ∈D. Finally, let us denote o S the auxiliary binary variable which is equal to 1 if S is selected, and 0 otherwise.
The region-based formulation of the CAP sac is expressed as follows: The objective function (36) minimizes the makespan T max , which is computed by constraints (37). Constraints (38) limit the networking delay for each photo transmission traffic demand. Constraints (39) impose that the selected subsets in S are assigned to σ drones which can do the 3D reconstruction. The set of constraints (40) ensures that each photo p ∈ P is covered at least once, and constraint (41) defines the number of selected subsets to m, i.e., the number of drones which can perform the 3D reconstruction. The transmission rates are defined by (42) and (21)

NP-Hardness of the CAPsac
The proof comes from a reduction of the decision version of the unweighted Geometric Set-Covering Problem -GSCP , whose objective is to assert, for a finite set of points P = {p 1 , p 2 , ..., p n ∈ R d } and a finite collection S of subsets of P , if there exists a covering for the points P composed by at most k < |S | sets of S , i.e., if there exists a C ⊂ S such that ∪ c∈C c = P and |C| ≤ k. The collection S is induced by a fixed polytope T , that is, S is formed by the points covered by the distinct placements of T over the coordinates of the points P . The decision problem is NP-Complete even when T is a fixed square [70] or a fixed circumference [71]. Proposition 2. Given an instance I of the GSCP , there exists a polynomial-time transformation from I to an instance I of the rCAP sac.
Proof. Consider an instance of the GSCP with P points, a collection S of subsets of P induced by a fixed square of length s, and a positive integer k < |S |. The instance of the rCAP sac is created on polynomial-time as follows.
Let the set of photos P and their location be equal to the set of points P (i.e., P = P ), and consider a set of k drones which can do the 3D reconstruction, i.e., |D| = |D| = k. The communication network T = (N, A) is a random tree whose links (i, j) ∈ A have infinite capacity. Therefore, the transmission times, the transmission rates φ hd , and the photos storage location θ dp can be dismissed. Thus, the latest completion time T max is defined only by the photo processing times of the drones. Concerning the reliability factor, it is made equal to 1 (σ = 1). Indeed, the collection S does not have all possible rectangular spatial-convex sets, being the S \ S missing spatial-convex sets obtained in polynomial-time by inspecting the tuples in C × C × L × L. Finally, the photo processing times of the spatial-convex sets will be either 1 or +∞. For S ∈ S , t S = 1, while for the remaining S ∈ S \ S t S = +∞. Proof. Consider rCAP sac(P, D, T, S) a routine which solves the CAP sac by the rCAP sac formulation (Section 3.3). Let its optimal solution be comprised by the optimal set Q * of variables q S d and the optimal completion time T * max . Given a solution of an instance of the CAP sac created from an instance of the GSCP , evaluating T * max is enough to answer the GSCP . If T * max = 1, reply yes. Otherwise, reply no. For an optimal solution whose T * max = 1, the covering C of the P , with |C| ≤ k, can be extracted from Q * .
Proof. Given the propositions 2 and 3, one can state that the GSCP is no harder than the CAP sac. Since the GSCP is NP-complete, the CAP sac is NP-Hard.

Computational experiments
Our experimental analysis assessed (i) the effectiveness of the ordering inequalities and the branching strategies for the pCAPsac formulation; (ii) the performance of formulation pCAPsac; (iii) the sensitivity of the pCAPsac formulation with respect to both reliability factor σ and maximum allowed transmission timeT . We used CPLEX v12.8 as generalpurpose linear programming solver. All experiments were carried exploiting a single core on a machine powered by an Intel E5-2683 v4 Broadwell 2.1GHz with 20Gb of RAM, and running the CentOS Linux 7.5.1804 OS.
We do not present computational experiments for formulation rCAPsac. As demonstrated in Section 3.3, the number of variables of that formulation is bounded by O(|P | 4 ), which can rapidly increase. Column Generation (CG) strategy has been extensively applied to formulations with a massive number of variables [72]. The great advantage of employing CG is to solve the Linear Program (LP) continuous relaxation considering only a relevant subset of variables. Such LP with reduced number of variables is called the restricted master problem (RMP). The subset of relevant variables is iteratively created as needed by solving the so-called pricing subproblem (PS). Usually, a CG iteration comprises: i) solving the current RMP to obtain current primal optimal solution and its associated dual variables, and ii) optimizing the PS to find new variables with negative reduced costs (when considering minimization problems). The CG terminates when the PS does not find any variable with negative reduced cost, i.e., when the optimality of the current RMP has been proved. Preliminary experiments (restricted to σ = 1 andT = +∞) were performed applying a vanilla column generation on the rCAP sac. Unfortunately, rCAP sac has proved highly degenerate requiring several CG iterations to prove optimality. Therefore, its performance for solving CAPsac was largely inferior to that of using the pCAPsac formulation. Finally, note that the above degeneragy is a common CG drawback that leads the resulting algorithms (and codes) to be difficult to tune and somehow delicate, thus incompatible for the applied context we deal with.

Tested instances and computational settings
The instances, which were constructed from realistic data, comprise two scenarios: i Unweighted: all photos require the same amount of processing time λ.
ii Weighted: each photo p ∈ P requires a certain amount of processing time λ p .
The λ p are acquired from the equivalent unweighted case: |P | × 0.1 groups of nine adjacent photos are randomly selected, and then, for each of those groups, a single λ p is drawn from a normal distribution (µ = 26.72 seconds and σ = 5.0) and attributed to all photos of that group. Changing the photo-processing time in that fashion allows to represent the 3D reconstruction of distinct complex objects in the region of interest. The name of the instances follows the notation X-PYYDZ%DWW where "X" is "u" for the unweighted instances and "w" for the weighted instances, "YY" stands for the number of photos in the instance, "Z" specifies the number of drones in the swarm, and "WW" informs the percentage of drones that can do 3D reconstruction. The number of drones able to perform 3D reconstruction, called |D|, is always equal to Z × W W 100 . The characteristics of the tested instances are listed in Table 2.
The tables presented hereafter report the instance employed at each row (column "Instance"), the corresponding formulation (column "Form."), the dual gap (in percentage) wrt the optimal solution found at the root node (column "gap 0 "), the number of cuts added by CPLEX at the root node (column "cuts"), the number of nodes explored by the CPLEX's branch-and-cut method (column "Nodes"), and the dual gap (in percentage) wrt the optimal solution (best known, see below) at the end of the branch-and-cut enumeration (column "gap"). CPU times spent in the solution of the root node and by the branch and cut algorithm are also reported (column "sec.").
Note that dual gaps are computed with respect to the best upper bound solution found whenever the optimal solutions are not obtained by CPLEX within one day of execution. These situations are represented in the tables by the symbol ' * '.

pCAPsac experiments
This section evaluates the performance of the proposed pCAPsac formulation. It investigates the effectiveness of valid inequalities (16)- (19), whose aim is, for any possible sub-region, to clean the search space from all the infeasible boundary configuration. Also, the experiments analyze how different branching priorities can influence the branch-andcut method. All the experiments of this section are for σ = 1 andT =+∞.

pCAPsac performance
The pCAPsac formulation using the BC 0 constraints (14), called "P B:BC 0 ", and the pCAPsac formulation using the BC 0 constraints (15), named "P B:BC 0 ", are compared in Tables 3 and 4. Table 3: CPLEX results when solving unweighted instances for the "P B:BC 0 " and the "P B:BC 0 " formulations.

Instance
Form.
Root Node Branch-and-Cut gap 0 cuts sec. Nodes gap sec.  Table 4: CPLEX results when solving weighted instances for the "P B:BC 0 " and the "P B:BC 0 " formulations.

Instance
Form. Root Node Branch-and-Cut gap 0 cuts sec. Nodes gap sec.
We can observe that the dual gaps at the root node are equal to zero for the unweighted instances whenever the number of photos is divisible by the number of drones that can do the 3D reconstruction. Consequently, the objective function value of the optimum solution coincides with the dual bound already at the root node for instances "u-P200D5%D90", "u-P200D7%D70", "u-P400D5%D90", "u-P400D7%D70", "u-P200D10%D50" and "u-P400D10%D50".

Ordering inequalities effectiveness
The effect of adding all the ordering inequalities (16)- (19) into the "P B:BC 0 " formulation is analyzed in Tables 5 and  6. The inclusion of the ordering inequalities is identified by the "+Ord." in the formulation name. Table 5: CPLEX results when solving unweighted instances for the "P B:BC 0 " and the "P B:BC 0 +Ord." formulations.  Table 6: CPLEX results when solving weighted instances for the "P B:BC 0 " and the "P B:BC 0 +Ord." formulations.

Instance
Form.  The valid inequalities (16)- (19) eliminate infeasible boundaries in the continuous solution space whereas not necessarily excluding the continuous optimum solution. Consequently, these inequalities are not guaranteed to increase the dual bound obtained. In fact, gap 0 was never improved in our experiments after adding the ordering inequalities. Nevertheless, the insertion of (16)- (19) improved the CPU time required to reach the optimum solution of 11 out to 19 instances solved to optimality (considering 2h of execution). In fact, paired t-tests show significant improvements (T= 1.907 p-val= 0.034) by adding them into the "P B:BC 0 " formulation, except for instances "P400D7%D70". However, when limited to weighted cases, there is no significant improvement on reducing the enumeration CPU time. For these cases, 11 seconds of improvement is obtained when comparing the average computing CPU time of non-inserting against inserting constraints (16)- (19). Finally, we observed that the number of cuts added by CPLEX at the root node increased considerably when the ordering inequalities were employed.

Branching priority
Different branching priorities for the selection of the boundary assignment (i.e., α r c , β r c , γ r , and ω r ) and the photo assignment (i.e., y r p ) variables were also explored in formulation "P B:BC 0 +Ord." (simply denoted "P B:BC 0 " at this section) and the results reported in Tables 7 and 8. The distinct branching priorities are denoted as "b>y" and "y>b". The the default option of CPLEX is identified by the absence of those notations. The "b>y" is used when the boundary assignment variables are given higher priority over the photo assignment variables, which still have higher priority over the remaining variables. The "y>b" refers to the opposite case, that is, when photo assignment variables are rather branched over boundary assignment variables. Table 7: CPLEX results when solving unweighted instances for the "P B:BC 0 ", "P B:BC 0 −b>y" and "P B:BC 0 −y>b" branching priority strategies.

Instance
Form.
Branch-and-Cut Nodes gap sec.  Table 8: CPLEX results when solving weighted instances for the "P B:BC 0 ", "P B:BC 0 − b>y" and "P B:BC 0 − y>b" branching priority strategies.

Instance
Form. The adoption of different branching priorities improves the CPU times to solve some instances. In fact, the "y>b" strategy achieves better or equivalent CPU times in 10 out to 11 unweighted instances solved to optimality (within 2h of execution). Regarding weighted cases, the "b>y" strategy results in better or equivalent CPU times in 5 out to 8 instances solved to optimality (considering 2h of execution). However, paired t-tests do not show significant improvement for both "b>y" (T= 0.889 p-val= 0.191) or "y>b" (T=1.295 p-val= 0.103) strategies considering overall cases.

Sensitivity of the pCAPsac formulation
This section evaluates the sensitivity of pCAPsac formulation with respect to both reliability factor σ and to maximum transmission time allowedT .

Reliability factor sensitivity
Tables 9 and 10 report results for various values of σ, ranging from 1 to |D| − 1. The subset of instances used in this experiment consists of those for which CPLEX was able to solve within 2h of execution the associated problem with σ = 1. Besides, the communication constraints concerningT were relaxed, i.e.T =+∞.  Tables 9 and 10 show that initial dual gaps are largely affected by σ. Those large dual gaps result from the increase of the optimum solution values with σ not accompanied by the increase in the dual bounds obtained at the root node. This is illustrated in Fig. 5 and Fig. 6, where the changes in the optimal objective function value (named "T max ") given the increase of σ are presented for unweighted instances "u-P200D7%D70", "u-P200D10%D50", "u-P200D7%D90", and for weighted instances "w-P200D7%D70", "w-P200D10%D50", "w-P200D7%D90". Those instances were selected to include distinct values of |D|.

Maximum transmission time sensitivity
The sensitivity analysis of formulation "P B" to parameterT is performed by decreasing its values progressively (the value of σ is fixed to 1 in this set of experiments). The first value ofT tested corresponds to the allocated communication time between the drones when no time limit is imposed for their communication, i.e.,T =+∞. From that value,T is decreased by 0.5 seconds until formulation "P B" becomes infeasible. Fig. 7 and Fig. 8 present results for instances "u-P200D5%D70" and "w-P200D5%D70". For them, the first value ofT is 48 seconds, being decreased down to 23.5      The decreasing ofT tends to reduce the number of nodes explored in the branch-and-cut enumeration whereas the objective function value increases until the problem becomes infeasible. For example, in Fig. 7, the optimum objective function value increases from 1870.4 to 2939.2 starting atT = 33.5. The problem becomes infeasible forT smaller than 24s.

Conclusion
A swarm of drones (UAVs) can be used to automate a wide range of missions, from surveillance to search and rescue, from 3D mapping to telecommunication enhancement. While UAVs are typically responsible for the mission phases related to data collection -thanks to their flying capabilities and to the availability of embedded sensors -most of the data processing is offloaded to dedicated machines (virtual or bare-metal) placed in the cloud. However, when the communication bandwidth between the swarm and the cloud is limited, an ad-hoc cloud established on top of the UAVs' computing resources (and those of other elements available in the area) can be leveraged to replace the cloud and keep data processing local.
For the purpose of optimizing the use of such ad-hoc cloud infrastructure powered by the swarming UAVs, we introduced a new optimization problem, namely the Covering-Assignment Problem for swarm-powered ad-hoc clouds -CAPsac, based on a real-life use-case in the emergency management field: swarm-powered distributed 3D reconstruction for humanitarian emergency response. After having established the relationship between the general problem and the specific use-case, we presented the NP-Hardness proof of the CAPsac and described two MILP formulations for it.
Given a set of geo-positioned aerial pictures (data) that are subject to geolocation/clustering constraints, CAPsac minimizes the 3D mapping (data-processing phase) completion time by jointly computing: (i) the optimal covering of photos (workload configuration), and (ii) the optimal assignment of photographed sub-regions (workload assignment) to UAVs (computing elements). Besides being a way to provide optimal solutions for the problem, our integrated decision model contrasts with the decompose-then-allocate and the allocate-then-decompose paradigms usually seen in (both the cloud computing optimization and) the multi-robot task allocation literature. Finally, modeling CAPsac in this way is flexible and amendable to take into account any other additional ground computing elements connected to the swarm itself.
In order to assess the proposed formulations, a series of computational experiments was conducted with a set of unweighted and weighted realistic benchmark instances available online (https://github.com/ds4dm/CAPsac). The experiments revealed that the photo-based formulation "P B" was more efficient by using ordering inequalities that remove from the feasible continuous search space those sub-regions whose boundaries are not regular (e.g. left boundary at the right of a right boundary). However, the different branching priority strategies and row generation methods have not proven to yield a performance gain while solving "P B". Column Generation was employed in the region-based formulation "RB", but the presence of highly degenerate optimums led to long execution times.
Finally, the sensitivity analysis of the formulation "P B" showed that it becomes more difficult to solve as the reliability factor σ increases. Tests with varying values for the maximum allowed transmission timeT also presented a slight gain of performance asT approaches a limit when the problem becomes infeasible.