<  Retour au portail Polytechnique Montréal

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

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

Rapport technique (2020)

Un lien externe est disponible pour ce document
Afficher le résumé
Cacher le résumé

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.

Mots clés

3D reconstruction; cloud computing; swarm; workload optimization

Département: Département de génie informatique et génie logiciel
Département de mathématiques et de génie industriel
Centre de recherche: GERAD - Groupe d'études et de recherche en analyse des décisions
Organismes subventionnaires: GRSNG / NSERC
URL de PolyPublie: https://publications.polymtl.ca/48681/
Numéro du rapport: 2020-28
URL officielle: https://www.gerad.ca/en/papers/G-2020-28
Date du dépôt: 18 avr. 2023 15:00
Dernière modification: 03 nov. 2023 09:46
Citer en 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. (Rapport technique n° 2020-28). https://www.gerad.ca/en/papers/G-2020-28

Statistiques

Aucune statistique n'est disponible.

Actions réservées au personnel

Afficher document Afficher document