Andrea Di Nezza
A multi-agent path finding instance: the Matrix Problem.
Rel. Fabio Fagnani. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2025
|
Preview |
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (6MB) | Preview |
Abstract
This thesis studies a special multi-agent path finding problem known as the “Matrix Problem”. In the Matrix Problem, a set of agents, initially at rest in specific positions, must sequentially reach a common target without colliding. In this thesis, we model this as a set of synchronized collective motions which take place on the edges of a given graph, where the target is a particular vertex in such graph. Agents are of two types: the tasked ones that need their motion to pass through the target, and the untasked ones that can be moved to ease the motions of the tasked agents.
For this setup, I define all kinds of motions and set necessary and sufficient topological requirements on the graph for the existence of feasible solutions
Tipo di pubblicazione
URI
![]() |
Modifica (riservato agli operatori) |
