Andrea Di Nezza
A multi-agent path finding instance: the Matrix Problem.
Rel. Fabio Fagnani. Politecnico di Torino, Master of science program in Mathematical Engineering, 2025
|
Preview |
PDF (Tesi_di_laurea)
- Thesis
Licence: 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
Relators
Academic year
Publication type
Number of Pages
Course of studies
Classe di laurea
URI
![]() |
Modify record (reserved for operators) |
