• Push and Swap
• multi-agents planning
• A star.
• Voronoi Diagram

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.