Leveraging Machine Learning for UAV trajectory planning and performance estimation

This thesis tackles the problem of Trajectory Planning in the setting of autonomous Unmanned Aerial Vehicles (UAVs) in the context of an industrial project. Given a mission (i.e., a starting point and an end point), the Trajectory Planning problem consists of finding the optimal trajectory with respect to some non-trivial metric in a constrained space, while avoiding collisions with obstacles. As part of the industrial project, our work starts from an existing simulator. We can use it to simulate the dynamics of the UAV along a given trajectory, however its execution is a cumbersome procedure. We model the simulator as a black-box function that we can query by providing a trajectory as input. The goal of this thesis is to produce an AI algorithm capable of automating the procedure of finding a collision-free trajectory in a constrained environment that optimizes a non-trivial goodness metric. Moreover, the algorithm is required to produce results in near-real time. We accomplish this goal by solving three distinct problems: Feasibility Estimation, Trajectory Estimation, and Trajectory Planning. The first problem refers to assessing the feasibility of a candidate solution. The second problem refers to estimating global measurements required for the evaluation of the goodness of a candidate solution. We formulate these two problems as Supervised Machine Learning problems. The third problem consists of exploring the search space of candidate trajectories to find the optimal one with respect to the metrics computed by the evaluation function. We formulate this problem as a Global Optimization problem. We employ a data-driven approach based on synthetic data generated using the simulator in a preparatory phase of the work. As regards the Trajectory Planning problem, we modify state of the art methodologies to adapt them to our particular setting. Finally, we evaluate our proposed solutions by testing them on problem instances separate from those we use in the data generation procedure. The experimental results show that the near-optimal trajectories found by our proposed algorithm are comparable to those that a human expert can produce, while satisfying the timeliness requirements.

Questa tesi affronta il problema della Pianificazione di Traiettoria per velivoli senza pilota (UAV), nel contesto di un progetto industriale. Data una missione (i.e., un punto iniziale e uno finale), il problema consiste nella ricerca della traiettoria ottima rispetto a una metrica non banale in uno spazio vincolato, evitando la collisione con degli ostacoli. Come parte di un progetto industriale, il nostro lavoro parte da un simulatore preesistente. Possiamo utilizzare il simulatore per simulare la dinamica dello UAV lungo una traiettoria data, tuttavia la sua esecuzione richiede un tempo lungo. Modelliamo il simulatore come una funzione black-box, che possiamo interrogare fornendo una traiettoria in input. L’obiettivo di questa tesi è la produzione di un algoritmo di Intelligenza Artificiale in grado di automatizzare la procedura di ricerca di una traiettoria senza collisioni, in uno spazio vincolato, che ottimizza una metrica non banale. In aggiunta, l’algoritmo deve produrre dei risultati in tempo reale. Raggiungiamo questo obiettivo attraverso la risoluzione di tre problemi distinti: Stima di Fattibilità, Stima di Traiettoria e Pianificazione di Traiettoria. Il primo problema si riferisce alla stima di fattibilità di una possibile soluzione. Il secondo problema si riferisce alla stima di valori globali necessari per il calcolo della metrica per una possibile soluzione. Formuliamo questi due problemi come problemi di Machine Learning supervisionato. Il terzo problema consiste nell’esplorazione dello spazio di ricerca delle traiettorie per trovare quella ottima rispetto alle metriche calcolate dalla funzione di valutazione. Formuliamo questo problema come un problema di Ottimizzazione Globale. Utilizziamo delle tecniche basate sui dati, utilizzando dati sintetici generati tramite l’uso del simulatore in una fase preparatoria del lavoro. Per quanto riguarda il problema di Pianificazione di Traiettoria, modifichiamo metodologie di stato dell’arte per adattarle al nostro contesto specifico. Infine, valutiamo le soluzioni da noi proposte testandole su istanze del problema separate da quelle utilizzate nella procedure di generazione dei dati. I risultati sperimentali mostrano che le traiettorie quasi-ottime trovate dall’algoritmo da noi proposto sono comparabili con quelle che un operatore esperto è in grado di produrre manualmente, soddisfacendo anche i requisiti di tempo di esecuzione.