A novel approach for path planning with goal position uncertainty

This thesis addresses the problem of path planning in the context of search and rescue missions employing drones. Given a starting and an ending point, a generic path planning problem consists of finding the optimal path with respect to some metric in a constrained space, while avoiding collisions with obstacles. Traditional algorithms solve this kind of problem relying on the assumption of precise knowledge regarding the goal position. However, in search and rescue scenarios, it often happens that the exact location of targets may remain unknown at planning time, to be discovered only later (e.g., when the agent senses the true rescue position). To the best of our knowledge, there are no existing studies in the literature that analyze or attempt to solve this kind of problems with uncertainty regarding the goal position from a mathematical perspective. For this reason, the goal of this thesis is to investigate this gap by formalizing this problem and studying aiming to find new methods to address it. Specifically, we firstly formalize a model representing a possible search and rescue scenario, formulating it as a Global Optimization problem. This step involves the introduction of new definitions of optimality, specifically designed for scenarios with incomplete information regarding the final destination. Then, we present a novel heuristic algorithm, called Meta Algorithm, built upon A*-like algorithms, tailored to tackle the newly formulated problem. In addition, we illustrate its main properties, such as completeness, optimality and efficiency, proving them from a theoretical point of view. Next, we show a set of emblematic experiments in order to illustrate the potential of the algorithm and its flexibility. Specifically, we apply it to different scenarios and compare it with the available alternative, namely the Complete Search Approach. The experimental results not only confirm the algorithm’s capability to successfully solve the problem, but also provide valuable insights for future research.

Questa tesi affronta il problema della Pianificazione di Percorso nel contesto delle missioni di ricerca e soccorso che coinvolgono l’uso di droni. Dato un punto di partenza e uno di arrivo, un problema generico di Pianificazione di Percorso consiste nel trovare il percorso ottimale rispetto a una metrica in uno spazio vincolato, evitando collisioni con ostacoli. Gli algoritmi tradizionali risolvono questo tipo di problema basandosi sull’assunzione di una conoscenza precisa della posizione dell’obiettivo. Tuttavia, nei casi di ricerca e soccorso, accade spesso che la posizione esatta degli obiettivi possa rimanere sconosciuta al momento della pianificazione, per essere scoperta solo in seguito (ad esempio, quando l’agente rileva la vera posizione del soccorso). A quanto ci risulta, non esistono studi in letteratura che analizzino o tentino di risolvere questo tipo di problemi con incertezza riguardo la posizione dell’obiettivo, da un punto di vista matematico. Per questo motivo, l’obiettivo di questa tesi è di indagare su questa lacuna, formalizzando il problema e studiando nuovi metodi per affrontarlo. In particolare, formalizziamo in primo luogo un modello che rappresenti uno scenario possibile di ricerca e soccorso, formulandolo come un problema di Ottimizzazione Globale. Questo passo implica l’introduzione di nuove definizioni di ottimalità, specificamente progettate per scenari con informazione incompleta riguardante la destinazione finale. Successivamente, presentiamo un nuovo algoritmo euristico, chiamato Meta Algoritmo, fondato su algoritmi come A* e progettato appositamente per affrontare il problema appena formulato. Inoltre, illustriamo le sue principali proprietà, come ottimalità, completezza ed efficienza, dimostrandole da un punto di vista teorico. In seguito, mostriamo una serie di esperimenti emblematici per mettere in luce il potenziale dell’algoritmo e la sua flessibilità. In particolare, lo applichiamo a diversi scenari e lo confrontiamo con l’unica alternativa disponibile, ovvero un Approccio di Ricerca Completa. I risultati sperimentali non solo confermano la capacità dell’algoritmo di risolvere con successo il problema, ma forniscono anche preziose intuizioni per la ricerca futura.