Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios
---
paper_title: Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem

paper_content:

The task in the multi-agent path finding problem (MAPF) is to find paths for multiple agents, each with a different start and goal position, such that agents do not collide. A successful optimal MAPF solver is the conflict-based search (CBS) algorithm. CBS is a two level algorithm where special conditions ensure it returns the optimal solution. Solving MAPF optimally is proven to be NP-hard, hence CBS and all other optimal solvers do not scale up. We propose several ways to relax the optimality conditions of CBS trading solution quality for runtime as well as bounded-suboptimal variants, where the returned solution is guaranteed to be within a constant factor from optimal solution cost. Experimental results show the benefits of our new approach; a massive reduction in running time is presented while sacrificing a minor loss in solution quality. Our new algorithms outperform other existing algorithms in most of the cases.
---
paper_title: Multi-agent path finding with payload transfers and the package-exchange robot-routing problem

paper_content:

We study transportation problems where robots have to deliver packages and can transfer the packages among each other. Specifically, we study the package-exchange robot-routing problem (PERR), where each robot carries one package, any two robots in adjacent locations can exchange their packages, and each package needs to be delivered to a given destination. We prove that exchange operations make all PERR instances solvable. Yet, we also show that PERR is NP-hard to approximate within any factor less than 4/3 for makespan minimization and is NP-hard to solve for flowtime minimization, even when there are only two types of packages. Our proof techniques also generate new insights into other transportation problems, for example, into the hardness of approximating optimal solutions to the standard multi-agent path-finding problem (MAPF). Finally, we present optimal and suboptimal PERR solvers that are inspired by MAPF solvers, namely a flow-based ILP formulation and an adaptation of conflict-based search. Our empirical results demonstrate that these solvers scale well and that PERR instances often have smaller makespans and flowtimes than the corresponding MAPF instances.
---
paper_title: Planning optimal paths for multiple robots on graphs

paper_content:

In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that compute minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.
---
paper_title: Reduced time-expansion graphs and goal decomposition for solving cooperative path finding sub-optimally

paper_content:

Solving cooperative path finding (CPF) by translating it to propositional satisfiability represents a viable option in highly constrained situations. The task in CPF is to relocate agents from their initial positions to given goals in a collision free manner. In this paper, we propose a reduced time expansion that is focused on makespan sub-optimal solving. The suggested reduced time expansion is especially beneficial in conjunction with a goal decomposition where agents are relocated one by one.
---
paper_title: Reduced time-expansion graphs and goal decomposition for solving cooperative path finding sub-optimally

paper_content:

Solving cooperative path finding (CPF) by translating it to propositional satisfiability represents a viable option in highly constrained situations. The task in CPF is to relocate agents from their initial positions to given goals in a collision free manner. In this paper, we propose a reduced time expansion that is focused on makespan sub-optimal solving. The suggested reduced time expansion is especially beneficial in conjunction with a goal decomposition where agents are relocated one by one.
---
paper_title: Multi-agent path finding with payload transfers and the package-exchange robot-routing problem

paper_content:

We study transportation problems where robots have to deliver packages and can transfer the packages among each other. Specifically, we study the package-exchange robot-routing problem (PERR), where each robot carries one package, any two robots in adjacent locations can exchange their packages, and each package needs to be delivered to a given destination. We prove that exchange operations make all PERR instances solvable. Yet, we also show that PERR is NP-hard to approximate within any factor less than 4/3 for makespan minimization and is NP-hard to solve for flowtime minimization, even when there are only two types of packages. Our proof techniques also generate new insights into other transportation problems, for example, into the hardness of approximating optimal solutions to the standard multi-agent path-finding problem (MAPF). Finally, we present optimal and suboptimal PERR solvers that are inspired by MAPF solvers, namely a flow-based ILP formulation and an adaptation of conflict-based search. Our empirical results demonstrate that these solvers scale well and that PERR instances often have smaller makespans and flowtimes than the corresponding MAPF instances.
---

Title: Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios
Section 1: Introduction
Description 1: Provide an overview of the standard Multi-Agent Path Finding (MAPF) problem and highlight the need for generalizations to real-world scenarios.

Section 2: Combined Target Assignment and Path Finding (TAPF) for Teams of Agents
Description 2: Discuss the TAPF problem where targets are assigned to teams of agents, and detail the methods developed to solve this problem.

Section 3: Package-Exchange Robot Routing (PERR) for Anonymous Agents
Description 3: Describe the PERR problem which allows for payload transfers among anonymous agents and emphasize the complexity and solutions.

Section 4: Exploitation of Problem Structure and Predictability of Motions
Description 4: Explain the importance of predictability in agent motions, especially in shared human-agent environments, and describe the use of highways to achieve consistency and predictability.

Section 5: Dealing with Imperfect Plan-Execution Capabilities
Description 5: Address the challenges of imperfect plan execution by proposing a framework that postprocesses MAPF solutions to create executable schedules for real-world robots.

Section 6: Conclusions
Description 6: Summarize the research directions and emphasize the significance of addressing real-world generalizations of MAPF.