Solving the Colored Multi-Agent Path Finding with Waypoints Problem using SAT

The Multi-Agent Path Finding (MAPF) problem is the problem of planning paths for multiple agents without any collisions. There are also many variants such as the waypoint variant, where each agent also has a set of waypoints it must visit before reaching its goal. The colored variant, in which the agents are grouped into teams and each team has...

Solving Multi-Agent Pathfinding with Matching using A*+ID+OD

This paper extends the Multi-Agent Pathfinding (MAPF) algorithm, A*+ID+OD, to be able to solve problems with matching. This extension still keeps the optimal and completeness properties of the original algorithm. Matching is added to the algorithm in both an exhaustive and heuristic manner. Exhaustive matching is further improved by adding a new...

Matching in Multi-Agent Pathfinding using M*

Multi-agent pathfinding (MAPF) is the process of finding collision-free paths for multiple agents. MAPF can be extended by grouping agents into teams. In a team, agents need to be assigned (or matched) to one of the team's goals such that the sum of individual cost} is minimised. This extension is called MAPF with matching (MAPFM). M* is a...

Multi-Agent Pathfinding with Matching using Enhanced Partial Expansion A*

For the Multi-Agent Pathfinding (MAPF) problem, a set of non-colliding paths must be found for multiple agents. In Multi-Agent Pathfinding with Matching (MAPFM), this problem is extended: agents and goals are added to a team and each agent has to navigate to a goal that belongs to the same team. In this paper, two extensions of the EPEA* MAPF...

Adapting CBM to optimize the Sum of Costs

In the Multi-Agent Pathfinding with Matching (MAPFM) problem, agents from a team are matched with and routed towards one of their team's goals without colliding with other agents. The sum of path costs of all agents is minimized. In prior works, Conflict Based Min-Cost-Flow (CBM) has been proposed. This algorithm solves a similar problem that...

Train Unit Shunting Problem, a Multi-Agent Pathfinding approach

The Train Unit Shunting Problem (TUSP) is a well studied problem within the NS (Dutch Railways). TUSP is a problem where trains have to be routed on a shunting yard such that maintenance tasks can be performed and no collisions occur. Furthermore, incoming trains have to be matched to outgoing trains, since trains of the same type can be used...

Extending the Multi-Label A* Algorithm for Multi-Agent Pathfinding with Multiple Waypoints

Multi-Agent Pathfinding (MAPF) is a problem in which the goal is to plan paths for distinct agents while avoiding collisions between agents. We consider a new variation of MAPF, namely MAPF with multiple waypoints (MAPFW), where agents are required to visit a set of intermediary locations before visiting their end goal. MAPFW may have...

A Guide to Solving Pathfinding Problems with Multiple Agents

Currently, literature regarding Multiagent Path Finding (MAPF) does not give a broad enough overview of all the different approaches. Many papers are hard to read and require proper knowledge of MAPF. The goal of this report is to give a global overview of MAPF. To achieve this goal, we provide a detailed explanation of what MAPF problems look...