The multi-agent pathfinding environment is part of the multi-agent toolbox and has been developed in the context of the AI Flanders Research Program. The environment is made using the Unity game engine. The software can be found in this Gitlab project.
This environment is a grid based world containing walls and tiles. Given are a number of robots/agents that all have an initial location and a goal location. The problem consist of planning a path for each agent.
Since we are using the ML-agents toolkit to connect Unity with algorithms written in Python, a distinction has to be made between centralized and decentralized: in the centralized setting actions are created for and given to each agent at once, in the decentralized setting each agent does this separately. In this Unity project we have thus two different scenes: a centralized and a decentralized version of the problem.
In this environment every agent has a position (2-d coordinate) but also a rotation. The idea behind this is that the time it takes to move one tile forward equals the time it takes to rotate over one unit of rotation. This unit of rotation is one of many configurable settings of the environment. All parameters can be set providing a configuration file: the layout of the warehouse, the unit of rotation, the time it takes for an agent to move one tile forward, the number of agents, their initial and goal nodes (coordinate and rotation) and whether agents can move backwards. By default initial and goal nodes are set and known for each agent, optionally you can also give the goal nodes and have your algorithm assign goal nodes to agents.
Standardly some metrics are saved whenever an algorithm runs:
An algorithm is called optimal when it returns a solution for which the makespan and sum of costs are both minimal and it is called complete if it returns a solution whenever one exists.
These metrics are written to a file in JSON format when all agents have arrived at their goal locations. You can easily add other metrics. We have also added a Python project where you can find examples and inspiration on how to visualize these metrics.
Visualization in this project is done in Unity. Algorithms are connected to the visualization via ML-agents. Several algorithms based on conflict based search have been added to the project by AI lab students. A short overview can be found below. There are also toy examples provided that explain how to use the ML-agents toolkit. A comprehensive readme is also provided.
If you do not want to use the Unity editor, you can also use the builds that can be downloaded from our website. Do check the readme in the Gitlab project how you have to connect your algorithm and the Unity build via ML-agents.
Questions and remarks can be send to marjon.blondeel@vub.be.
Conflict-based search (CBS) is a centralized algorithm which is both complete and optimal. Its main idea is to decompose the problem into multiple constrained single-agent pathfinding problems. A low level process finds shortest paths for each agent given constraints imposed on the agent and a high level process searches a constraint tree: a binary tree in which nodes consist of a set of constraints, a solution (shortest paths consistent with these constraints) and a cost for that solution. Whenever the search process finds a conflict, two new child nodes are created and constraints solving that conflict are added. Once a nodes without conflicts has been found, the solution is returned.
Despite outperforming other multi-agent pathfinding algorithms such as EPEA* and ICTS on certain scenarios, when using CBS the constraint tree will grow exponentially in the number of conflicts found and the algorithm will behave poorly when the agents collide often.
A direct link to the algorithm can be found here and is based on Sharon et al. (2015) .
Meta-agent conflict-based search (MA-CBS) is centralized algorithm based on CBS, it is not complete and optimal. MA-CBS tries to tackle to problem of a constraint tree that grows exponentially when agents have a high internal collision rate. The main idea is to divide the set of agents into multiple sets of strongly coupled agent; each of such sets will be merged into a single agent, a so-called meta-agent. As CBS, it consists of a high and lower level process. In the high level process, meta-agents are treated as if they were single agents. The lower level uses a multi-agent pathfinding solver such as EPEA* to find paths without conflicts for all the single agents in the meta-agent. Basic CBS cannot be used here since it could be stuck when dealing with unsolvable multi-agent pathfinding problems.
A direct link to the algorithm can be found here and is based on Sharon et al. (2015) .
Improved conflict-based search (ICBS) is a centralized algorithm which is both optimal and complete and adds two improvements to MA-CBS. A first improvement is to restart the search in the constraint tree after two agents are merged. In practice the overhead of restarting the search is smaller than having the lower level MAFP solver do redundant work. A second improvement is to prioritize conflicts. The idea is to first resolve the conflicts in which the new child nodes both have a higher cost. This avoids the search being stuck in subtrees where the cost remains the same. To do this we store all possible paths of a particular cost for each agent. The overhead of storing and checking this information is worth in situations with a lot of bottlenecks.
A direct link to the algorithm can be found here and is based on Sharon et al. (2015) and Boyarski et al. (2015).
Greedy conflict-based search (Greedy CBS) is a centralized algorithm and is a suboptimal variant of CBS. Greedy CBS uses the same framework of CBS but allows a more flexible search in both the high and the lower level. It prefers expanding nodes that are more likely to produce a valid solution fast. In return, the solution might be suboptimal.
A direct link to the algorithm can be found here and is based on Barer et al. (2014).
Enhanced conflict-based search (ECBS) is a centralized algorithm and is a bounded suboptimal variant of CBS. In ECBS both high and low level share a joint suboptimality bound and use focal search.
A direct link to the algorithm can be found here and is based on Barer et al. (2014).