A black-box optimization approach to the UAV coverage problem using N+1 drones

Unmanned aerial vehicles (UAVs) have established themselves as a versatile solution in multiple fields such as surveillance and monitoring, among others. Of particular interest is the application of UAVs serving as aerial base stations (ABS). Several studies have shown that, in scenarios where there is no fixed telecommunications infrastructure, using UAVs can provide fast and reliable wireless connectivity. This strategy can be especially useful in situations such as providing services in remote areas without access to traditional networks, or in urban areas facing service disruptions and limitations. This thesis introduces a black-box optimization approach to maximize the Quality of Service (QoS) provided by a fleet of N+1 UAVs appropriately deployed in a two-dimensional search space. This method is particularly suitable in cases where system evaluations rely on complex tests or real-world environments that do not permit the use of direct analytical modelling. To address this limitation, an optimization strategy based on the Set Membership Global Optimization (SMGO) paradigm is used. Building upon previous work where the SMGO was employed using N UAVs to maximize user service coverage, i.e. to provide the maximum QoS, this study explores the benefits of incorporating an additional drone (N+1). In each iteration, N candidate positions are generated, and only N drones are deployed at a time, leaving one inactive. This enables the evaluation of N+1 unique deployment combinations of N UAVs, effectively providing N+1 parallel samples per iteration. This strategy enriches the optimization process with more data per step, significantly accelerating convergence toward the optimal deployment. In order to assign the newly generated positions by the SMGO to the N+1 available UAVs, the Hungarian Algorithm has been employed. Based on this framework, several functional variants have been developed, each incorporating different position assignment and sampling strategies. The performance of the proposed method is assessed based on experimental results. The outcomes obtained confirm that the use of one additional UAV in the algorithm substantially improves the convergence speed, highlighting the method's potential for enhancing UAV-based network deployment.

I velivoli senza pilota (UAV) si sono affermati come una soluzione versatile in molteplici campi, tra cui la sorveglianza, il monitoraggio e la fornitura di connettività in situazioni critiche. Di particolare interesse è l'applicazione degli UAV come stazioni base aeree (ABS), in grado di garantire connettività wireless veloce e affidabile in scenari privi di infrastrutture fisse, come aree remote o ambienti urbani soggetti a disservizi. Questa tesi introduce un approccio di ottimizzazione black-box per massimizzare la Quality of Service (QoS) fornita da una flotta di N+1 UAV distribuiti in uno spazio di ricerca bidimensionale. Tale strategia si basa sul paradigma Set Membership Global Optimization (SMGO), particolarmente adatto a problemi in cui la funzione obiettivo non è nota in forma analitica e le valutazioni si basano su simulazioni complesse. A partire da lavori precedenti basati su N droni, questo studio propone l’integrazione di un UAV aggiuntivo, consentendo di valutare N+1 combinazioni di dispiegamento in ogni iterazione. Questo approccio fornisce più campioni per passo, accelerando significativamente la convergenza verso soluzioni ottimali. Per assegnare le posizioni generate dall’SMGO agli UAV disponibili, è stato impiegato l’algoritmo ungherese. A partire da questo schema sono state sviluppate diverse varianti funzionali, ognuna caratterizzata da differenti strategie di assegnazione e raccolta delle valutazioni. I risultati sperimentali ottenuti confermano che l’introduzione dell’UAV aggiuntivo e l’impiego di tecniche avanzate di campionamento migliorano sensibilmente l’efficienza del processo di ottimizzazione, riducendo il tempo di convergenza e aumentando la copertura, con potenziale applicabilità a scenari reali basati su reti di UAV.