logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-05152016-010256


Tipo di tesi
Tesi di laurea magistrale
Autore
DENARO, ANGELICA
URN
etd-05152016-010256
Titolo
Multi robot coordination in time-space on semantic roadmaps
Dipartimento
INGEGNERIA DELL'INFORMAZIONE
Corso di studi
INGEGNERIA ROBOTICA E DELL'AUTOMAZIONE
Relatori
relatore Prof.ssa Pallottino, Lucia
Parole chiave
  • A star.
  • multi-agents planning
  • Push and Swap
  • Voronoi Diagram
Data inizio appello
21/07/2016
Consultabilità
Completa
Riassunto
The object of this work is finding an efficient solution for multiple agents. Given a start and a goal state for each agent, the aim is to find minimal paths for every agent avoiding collisions.
The multi-agent path finding (MAPF) problem is a generalization of the single path finding problem for k > 1 agents.
The approch is centralized: the agents can communicate their own position to the other agents without any limits. The robots move on the graph obtained from the Voronoi diagram of the environment map, which allows me to focus on avoiding the collision between the agents rather than on the collision with the obstacles.
The algorithms are decoupled approaches that break down the problem into a series of single-agent searches. The problem is divided in two levels: in the first level the path for each individual agent is obtained from optimal algorithm A star. In the second level a main algorithm checks if there are any collisions between the robots. If there are collisions, it will avoid them with different approches at each time (from start time of the paths until the last time) and until the last robot arrives to last goal.
This method of avoiding the collision is an improvement of the procedure Push and Swap realized by the Ryan Luna and Kostas E. Bekris in "Efficient and Complete Centralized Multi-Robot Path Planning".
With this method collisions are handled by changing the speed of the robots and updating the time line every avoided collision.
File