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 instead minimizes the maximum path length. In this paper, an extension upon CBM is presented, called CBMxSOC. It consists of several changes to CBM that allow it to minimize the sum of path costs. CBMxSOC is experimentally compared to other MAPFM solvers and is shown to be able to scale to many agents when there are few conflicts between different teams.

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 complete and optimal algorithm to solve MAPF problems. In this paper, two strategies are proposed which allow M* to solve MAPFM problems. These strategies are called inmatching and prematching. It is shown that prematching is generally preferable to inmatching, the benefits of different optimisations for M* are compared, and it is shown that the performance of M* performs very comparably to other A*-derived algorithms.