Optimization based unmanned aerial vehicles trajectory generation

Unmanned Aerial Vehicles (UAVs) have received significant attention in recent years due to their diverse applications in civil and military do- mains. Furthermore, in many of these applications, the coordination of multiple UAVs, or swarms, offers the potential for enhanced efficiency, reduced mission times, and increased system resilience. One of the key challenges in UAV operations lies in generating optimal trajectories that ensure safe and efficient flight. This dissertation investigates the use of convex optimization to ad- dress UAV trajectory generation challenges. Convex optimization, with its robust theoretical foundation and efficient solvers, offers a promising framework for tackling trajectory planning problems. When problems are non-convex, convex approximations can be constructed to leverage these advantages. The thesis is divided into two main parts. The first part focuses on computing globally optimal solutions to the obstacle avoidance prob- lem by developing tight convex outer approximations of the problem. Specifically, a convex approximation framework based on polynomial optimization is applied, resulting in a hierarchy of Semidefinite Pro- gramming (SDP) problems of increasing size. The solutions to these problems progressively converge to the global solution of the original problem. To improve computational efficiency, a novel sparse hierarchy is introduced, exploiting the problem’s inherent chain structure. The second part addresses multi-UAV trajectory generation with a focus on real-time, decentralized algorithms. The proposed approach III tackles the problem by constructing local inner convex approximations of the collision avoidance constraints to ensure computational efficiency. By leveraging a cooperative framework, an anytime algorithm is devel- oped and experimentally validated.

Una delle principali sfide nelle operazioni con velivoli senza pilota è la pianificazione di traiettorie ottimali che garantiscano un volo sicuro ed efficiente. Inoltre, in molte applicazioni di interesse, il coordinamento di più droni può migliorare l’efficienza, ridurre i tempi di missione e aumentare la resilienza del sistema. Questa tesi esplora l’uso dell’ottimizzazione convessa per affrontare le difficoltà legate alla generazione di traiettorie per droni. La ricerca è articolata in due parti principali. La prima parte si concentra sulla determinazione di soluzioni globalmente ottimali per il problema dell’evitamento degli ostacoli, sviluppando approssimazioni convesse globali. Viene illustrata la costruzione di una gerarchia di problemi di Programmazione Semidefinita (SDP) di complessità crescente, le cui soluzioni convergono progressivamente alla soluzione globale del problema originale. Per migliorare l’efficienza computazionale, è stata introdotta una nuova gerarchia sparsa che sfrutta la struttura a catena intrinseca del problema. La seconda parte della tesi si focalizza sulla generazione di traiettorie per sciami di droni, con un’attenzione particolare a algoritmi decentralizzati capaci di operare in tempo reale. L’approccio adottato prevede la costruzione di approssimazioni convesse locali per garantire la generazione di traiettorie di traiettorie localmente ottime in tempo reale. L’algoritmo sviluppato è stato testato e validato sperimentalmente in un ambiente reale.