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). This problem is an NP-hard problem, and current algorithms cannot always determine whether an instance is feasible. We analyze a simplified variant of the TUSP, leaving out details from the real-world scenario to study the theoretical conditions for basic scenarios to be feasible. To this extent, we identify essential elements of the TUSP and include these in a modification of the Pebble Motion problem. Based on this Pebble Motion variant, we establish new problems that can be studied to analyze the feasibility of the TUSP. For each of these problems, we examine the complexity and look into different solution approaches.

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 of algorithms based on the Increasing Cost Tree Search (ICTS) algorithm for multi-agent pathfinding are presented that can optimally solve this joint problem: exhaustive algorithms that reduce the problem to solving many multi-agent pathfinding problems using regular ICTS, and algorithms that search a generalized increasing cost tree. These are compared to each other experimentally on a set of grid maps, and it is shown that exhaustive methods typically outperform the generalized ICTS. Lastly, an exhaustive ICTS algorithm is compared to alternative algorithms based on other multi-agent pathfinding approaches to put its performance into the broader context of algorithms for multi-agent pathfinding with matching.

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 solver will be discussed that enable it to solve MAPFM problems. The first extension modifies the EPEA* algorithm to directly allow it to solve MAPFM problem instances. The second extension generates all possible goal assignments for each agent and runs EPEA* on these assignments. This last extension is shown to have a superior performance in most cases. The second extension is also compared to extensions of other MAPF algorithms.

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 layer of Independence Detection (ID) to reduce the number of matchings. Besides this, the pruning efficiency is increased by sorting the matchings based on the initial heuristic. The exhaustive matching method has been found to perform better than the heuristic matching method. The exhaustive version of A*+ID+OD is finally compared to other extended MAPF algorithms which shows that on small maps, Conflict Based Min-Cost Flow (CBM) performs best as it is the only algorithm that does not use exhaustive matching. A*+ID+OD and Enhanced Partial Expansion A* (EPEA*) also perform well on open maps with multiple teams when compared to other exhaustive matching algorithms due to the addition of matching ID.

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 that have been extended to incorporate waypoints. It also analyzes which influence map characteristics like corridors, chokepoints, overlapping waypoints and the average degree have on the performance of these algorithms. It concludes that EMLA and WM* perform best overall with some variations per characteristic.

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-agent pathfinding with waypoints (MAPFW) problem is a variation on the classical MAPF problem. MAPFW can be useful for e.g. navigating warehouses and scheduling trains. However, little to no research exists on MAPFW. This research proposes two extensions to the BCP-MAPF algorithm to incorporate waypoints and reviews their performance.

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 game artificial intelligence. In this paper an extension to Conflict Based Search (CBS), an algorithm that solves Multi-Agent Path Finding problems without waypoints, is proposed to solve MAPFW problems, named CBSW.
The effect of extending the Bypass optimization and the Prioritizing conflicts optimization for CBS to CBSW is investigated and a new optimization that improves the performance of CBSW in corridors is proposed.
CBSW is compared with other MAPFW solvers that have been developed made simultaneously, and experimental result show a large speed up using CBSW on benchmarks with large maps or many 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 interesting applications, such as in the field of train scheduling and routing. To solve MAPFW problems we present the new algorithm Extended Multi-Label A* (EMLA*), which is based of the existing MLA* algorithm. Experimental evaluation shows that Heuristic-Based EMLA* (HB-EMLA*) for unordered MAPFW outperforms other algorithms when it comes to the number of agents and waypoints it is able to handle. However, HB-EMLA* struggles to find solutions to instances which are \textit{not well-formed}, as resting agents may block planning agents preventing a valid plan from being found. HB-EMLA* generally outperforms other algorithms when it comes to run time of larger instances. This comes at the cost of solution quality, where the solutions provided by EMLA* are 30\% worse than the best solution of the compared algorithms. Lastly, set benchmarks show that a simple \textit{Nearest Waypoint} heuristic generally outperforms other tested heuristics for HB-EMLA*.

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 like, as well as giving a clear overview of the strength and weaknesses of different solutions. Besides this theoretical analysis, we also analyse and critique benchmarking performed by other researchers. Following all this, we conclude that the field of MAPF lacks agreement on terminology. Furthermore, performance analysis is limited to researchers choice, skewing research in their own favour.