Multi-agents path planning for rendezvous using artificial potential fields

This thesis addresses the multi-agent path planning problem for rendezvous, where multiple autonomous agents are required to converge at common meeting points before proceeding together toward a final destination. The work emphasizes the importance of computational efficiency in such complex environments. In real-world scenarios, indeed, traditional optimal approaches based on exhaustive search algorithms (e.g., A*) become computationally prohibitive due to the complexity of the problem and the high dimensionality of the environments, characterized by numerous obstacles and agents. To overcome these limitations, this work proposes a novel heuristic approach based on Artificial Potential Fields (APF). The method proposed is designed to converge rapidly to a rendezvous point by adapting attractive and repulsive forces based on relative agents’ positions and the spatial configuration of obstacles and terrain. This new approach allows the generation of smooth, collision-free trajectories while simultaneously ensuring that the distances traveled by all agents are balanced, to facilitate a synchronized rendezvous. The thesis is structured in two main parts. The first part offers a detailed analysis of the unique challenges posed by rendezvous scenarios. It explores the possible solution for the problem and the related criticality, providing a foundation for understanding how heuristic strategies can be effectively adapted to overcome these challenges. It addresses related issues inherent to the APF method, such as the risk of agents becoming trapped in local minima, and proposes solutions to mitigate them. The second part of the thesis is dedicated to the implementation and analysis of the APF-based method specifically tailored to this problem, focusing on solving the problem while improving also the quality of the results. Experiments conducted to evaluate the performance of the approach show a positive trend, with excellent computational efficiency (on the order of milliseconds) and high path quality. Additionally, the tests demonstrate the algorithm's robustness, with a 99.6$\%$ success rate verifying its suitability for practical use in such environments. These experiments show results that surpass those achieved by traditional optimal methods, suggesting this new approach as the state-of-the-art solution to the problem.

Questa tesi affronta il problema di pianificazione del percorso multi-agente per il rendezvous, dove più agenti autonomi sono tenuti a convergere in punti di incontro comuni prima di procedere insieme verso una destinazione finale. Il lavoro sottolinea l'importanza dell'efficienza computazionale in ambienti così complessi. In scenari reali, infatti, gli approcci ottimali tradizionali basati su algoritmi di ricerca esaustivi (ad esempio, A*), diventano computazionalmente proibitivi a causa della complessità del problema e dell'elevata dimensionalità delle mappe, caratterizzate da numerosi ostacoli e agenti. Per superare queste limitazioni, questo lavoro propone un nuovo approccio euristico basato su campi potenziali artificiali (APF). Il metodo proposto è concepito per convergere rapidamente verso un punto d'incontro adattando le forze attraenti e repulsive in base alla posizione degli agenti relativa e alla configurazione spaziale degli ostacoli e del terreno. Questo nuovo approccio consente di creare traiettorie regolari e prive di collisioni, garantendo nel contempo che le distanze percorse da tutti gli agenti siano bilanciate per facilitare un rendezvous sincronizzato. La tesi è strutturata principalmente in due parti. La prima parte offre un'analisi dettagliata delle sfide uniche poste dagli scenari di rendezvous. Esplora la possibile soluzione per il problema e le relative criticità, fornendo una base per capire come le strategie euristiche possono essere adattate in modo efficace per superare queste sfide. Affronta questioni correlate al metodo APF, come il rischio di agenti intrappolati in minimi locali e propone soluzioni per mitigarli. La seconda parte della tesi è dedicata all'implementazione e all'analisi del metodo basato su APF specificamente adattato a questo problema, concentrandosi sulla risoluzione del problema migliorandone anche la qualità dei risultati. I test condotti per valutare le prestazioni dell'approccio mostrano un trend positivo, con un'eccellente efficienza di calcolo (nell'ordine dei millisecondi) e una ottima qualità del percorso, e inoltre, dimostrano la robustezza dell'algoritmo, con un tasso di successo del 99,6$\%$ che ne verifica l'idoneità all'uso pratico in tali scenari. Questi esperimenti mostrano risultati che superano quelli ottenuti con i metodi ottimali tradizionali, suggerendo questo nuovo approccio come la soluzione più avanzata al problema.