Time-optimal path planning for dynamical systems using the level set method

The aim of this work is to employ the level set method to generate time-optimal paths, with or without external flow fields. The goal is to predict the sequence of steering directions and the corresponding trajectory so that the vehicle reaches the goal in the minimum time. At first, the vehicle is considered as a purely kinematic agent, so it behaves like a point mass. The partial differential equation that predicts the time-optimal path is described in detail and, then, applied in presence of numerically simulated space- and time-dependent flow fields. The numerical solutions are compared with the analytical ones when available. Next, the level set method is applied to vehicles subject to the dynamic constraint and the influence of external flow fields. The partial differential equation that predicts the time-optimal path is derived and, then, applied to five different dynamical systems, increasing complexity in terms of number of state variables and control inputs. In some cases, analytical solutions are employed to verify the correctness of the numerical results.

Lo scopo di questa tesi è utilizzare il metodo level set per generare traiettorie tempo-ottime, con o senza la presenza di campi di flusso esterni. L’obiettivo è predire la sequenza di direzioni di sterzata affinché il veicolo raggiunga il punto finale nel minor tempo possibile. Inizialmente il veicolo è considerato come un agente puramente cinematico, ovvero controllato attraverso velocità e angolo di sterzo. L’equazione differenziale alle derivate parziali che predice la traiettoria tempo-ottima viene descritta dettagliatamente e, successivamente, applicata in presenza di campi di flusso numericamente simulati. Le soluzioni ottenute numericamente sono confrontate con quelle analitiche, quando possibile. Successivamente il metodo level set viene applicato a veicoli soggetti al vincolo della dinamica, in presenza o assenza di flussi esterni. L’equazione alle derivate parziali che predice la traiettoria tempo-ottima viene derivata. Successivamente, differenti sistemi dinamici vengono analizzati, aumentando la complessità in termini di numero di variabili di stato e azioni di controllo. In alcuni casi, soluzioni analitiche sono presenti in letteratura e utilizzate per verificare la correttezza dei risultati numerici.