Multi-RRT* : a sample-based algorithm for multi-agent planning

This thesis addresses the problem of trajectory planning for multiple agents movingin the same region. Agents need to be at some safety distance one from the otherand to avoid collisions with obstacles. The resulting multi-agent planning problemis addressed via a cooperative decentralized scheme where agents exchange informa-tion on their planned trajectories, which are then possibly modified if if some conflictis detected The resolution scheme is iterative, and at the first iteration, all agentsreplan to avoid conflicts, and the trajectory of the agent with minimal performancedegradation is chosen. If there is still a conflict, then, at each iteration the sameprocedure is repeated by all agents except the ones that already changed their tra-jectory. Given that the number of conflicts is reduced at each iteration, convergenceis guaranteed in a finite number of iterations. Furthermore, the obtained solution isPareto optimal. Trajectory planning for each single agent is performed via the rapidlyexploring random tree star (RRT?) algorithm, which is able to handle cost functionsand constraints, and is thus extended here to a multi-agent setting. The resultingmulti-RRT?algorithm is tested in different scenarios and shows promising results.

Questa tesi affronta il problema della pianificazione delle traiettorie nel caso di pi`uagenti che condividono la stessa regione dello spazio e devono mantenere una certadistanza di sicurezza l’uno dall’altro ed evitare eventuali ostacoli. Il problema vieneaffrontato secondo uno schema decentralizzato coperativo, in cui gli agenti comunicanotra di loro le informazioni relative alla traiettoria prescelta, che viene eventualmentemodificata se vengono rilevate situazioni di conflitto. L’idea `e di far risolvere il con-flitto all’agente per il quale il peggioramento della funzione di costo `e pi`u limitato.Iterazioni multiple sono richieste nel caso in cui la modifica di traiettoria da parte delsingolo agente prescelto non sia risolutiva per l’intero sistema. La convergenza ad unasoluzione senza conflitti `e garantita in un numero finito di iterazioni per costruzione,dato che ad ogni iterazione il numero di conflitti viene diminuito. Tale soluzione `e perconstruzione Pareto ottima. La pianificazione di ogni singola traiettoria viene effet-tuata attraverso un metodo randomizzato noto in letteratura come rapidly exploringrandom tree star (RRT?) che `e in grado di gestire cifre di merito e vincoli, e vienequindi esteso in questa tesi al caso multi-agente. L’algoritmo multi-RRT?proposto `estato testato in alcuni scenari e ha mostrato risultati promettenti.