<  Back to the Polytechnique Montréal portal

The covering-assignment problem for swarm-powered ad-hoc clouds : a distributed 3D mapping use-case

Leandro R. Costa, Daniel Aloise, Luca G. Gianoli and Andrea Lodi

Technical Report (2020)

An external link is available for this item
Show abstract
Hide abstract


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.

Uncontrolled Keywords

3D reconstruction; cloud computing; swarm; workload optimization

Department: Department of Computer Engineering and Software Engineering
Department of Mathematics and Industrial Engineering
Research Center: GERAD - Research Group in Decision Analysis
Funders: GRSNG / NSERC
PolyPublie URL: https://publications.polymtl.ca/48681/
Report number: 2020-28
Official URL: https://www.gerad.ca/en/papers/G-2020-28
Date Deposited: 18 Apr 2023 15:00
Last Modified: 05 Apr 2024 11:50
Cite in APA 7: Costa, L. R., Aloise, D., Gianoli, L. G., & Lodi, A. (2020). The covering-assignment problem for swarm-powered ad-hoc clouds : a distributed 3D mapping use-case. (Technical Report n° 2020-28). https://www.gerad.ca/en/papers/G-2020-28


Stats are not available on this system.

Repository Staff Only

View Item View Item