Extending CBS to efficiently solve MAPFW

Multi-Agent Path Finding with Way-points (MAPFW) is the problem of routing agents through a graph past a set of waypoint to a goal location, without agents colliding, with the shortest combined path length. This problem has to the authors knowledge not been investigated yet even though it has implications in train scheduling problems and video...

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 Increasing Cost Tree Search

Both the assignment problem and the multi-agent pathfinding problem are common problems in the fields of robotics and transportation. The joint problem of multi-agent pathfinding extended with the assignment of goals to agents, matching, is something that has not been studied much; few methods exist today that solve it. In this work, two types...

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...

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...

Multi-agent pathfinding with waypoints using Branch-Price-and-Cut

In the multi-agent pathfinding (MAPF) problem, agents have to traverse a graph to a goal location without running into each other. Currently, the Branch-and-Cut-and-Price-MAPF (BCP-MAPF) algorithm is the state-of-the-art algorithm for solving MAPF problems, which uses Branch-Price-and-Cut (BPC) to solve a linear minimization problem. The multi...

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...

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...

Analysis of the influence of graph characteristics on MAPFW algorithm performance

The Multi-Agent Path Finding (MAPF) problem is a problem in which a route must be found for multiple agents such that they do not collide. The Multi-Agent PathFinding with Waypoints problem extends this problem by adding waypoints that the agents must visit before travelling to their end location. This paper compares five algorithms for MAPF...

Applying the Pebble Motion problem: studying the feasibility of the Train Unit Shunting Problem

Shunting yards are the locations where trains, which are not included in the train schedule at a certain time, are parked until they are required again. Managing the parking of the trains such that all trains can leave at the desired time is a complicated task, and results in the problem formally known as the Train Unit Shunting Problem (TUSP)....