Source-linked AI summary
Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks
Roni Stern, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Eli Boyarski, Roman Bartak
TL;DR
MAPF research uses varied assumptions, objectives, and terminology, making comparison and application-focused paper discovery difficult. This paper unifies MAPF terminology and evaluation practice, introduces benchmarks, and reports a grid benchmark that challenges contemporary solvers.
Problem
Inconsistent MAPF assumptions, objectives, and terminology make literature navigation, baseline establishment, and application-relevant paper discovery difficult.
Method
The paper develops unified MAPF terminology, common benchmarks and evaluation measures, and introduces a grid benchmark with diverse maps and generated source-target vertices.
Results
The new grid benchmark contains problems that are complex enough to challenge contemporary MAPF solvers, with standard-algorithm performance reported as a comparison baseline.
Takeaways & Limitations
The terminology and benchmark suite are intended to provide a common language and experimental setting for more scientifically rigorous MAPF comparisons.
Takeaways & Limitations
The paper notes that weighted-graph variants use more complex motion models with different action durations, while target behavior remains an explicit modeling assumption.
Abstract
from arXiv · showhide
The MAPF problem is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses and autonomous vehicles. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers make different assumptions, e.g., whether agents can traverse the same road at the same time, and have different objective functions, e.g., minimize makespan or sum of agents' actions costs. These assumptions and objectives are sometimes implicitly assumed or described informally. This makes it difficult to establish appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application. This paper aims to fill this gap and support researchers and practitioners by providing a unifying terminology for describing common MAPF assumptions and objectives. In addition, we also provide pointers to two MAPF benchmarks. In particular, we introduce a new grid-based benchmark for MAPF, and demonstrate experimentally that it poses a challenge to contemporary MAPF algorithms.
1 Introduction
MAPF plans concurrent, collision-free paths for multiple agents and supports applications such as automated warehouses, autonomous vehicles, and robotics. The paper addresses inconsistent terminology by proposing unified descriptions, benchmarks, and evaluation measures.
- MAPF plans paths for multiple agents that can be followed concurrently without collisions.
- MAPF is relevant to automated warehouses, autonomous vehicles, and robotics.
- Different assumptions, objectives, and terminology make MAPF literature difficult to understand and complicate baseline selection and application-focused paper discovery.
- The paper introduces unified terminology for describing MAPF problems and establishes common benchmarks and evaluation measures.
- A new grid MAPF benchmark includes diverse maps and generated source-target vertices, and standard-algorithm results provide a baseline for future comparisons.
2 Classical MAPF
Classical MAPF defines graph-based, discrete-time plans for agents moving from sources to targets, with validity determined by specified conflicts. Its variants also differ in target behavior and objectives such as makespan and sum of costs.
- A classical MAPF instance is a tuple ⟨G, s, t⟩ with an undirected graph, source mapping, and target mapping for k agents.
- Agents use wait or adjacent-vertex move actions, and a solution contains one single-agent plan per agent that reaches its target.
- A MAPF solution is valid when its single-agent plans can be executed without conflicts, whose definitions depend on the environment.
- Common conflicts include vertex, edge, following, cycle, and swapping conflicts, with dominance relations among several restrictions.
- Classical MAPF must specify whether agents stay at targets or disappear, because agents can reach targets at different times.
- The two common objectives are makespan, the time until all agents reach targets, and sum of costs, the total individual arrival times.
- Other objectives are possible, but prior classical MAPF work mainly uses makespan or sum of costs, with their use varying across algorithmic approaches.
3 Beyond Classical MAPF
Beyond classical MAPF, research relaxes discrete-time, unit-duration, single-vertex assumptions and extends the task to richer assignments, online settings, weighted graphs, feasibility rules, and motion-planning constraints.
- Classical MAPF assumes discretized time, one-time-step actions, and one occupied vertex per agent at each time step.
- MAPF variants relax these assumptions through different action durations, weighted graphs, and more complex motion models.
- In 2^k-neighbor grids, agents move among 2^k neighboring cells, with Euclidean costs producing different move costs when k > 2.
- Euclidean-space MAPF represents graph nodes as points and edges as allowed moves, including roadmaps for continuous environments.
- Additional feasibility rules address execution delays through robustness requirements and impose formation or communication-link constraints.
- Large-agent MAPF models geometric volume, while kinematic variants make actions depend on state parameters such as velocity and orientation.
- Anonymous, colored, and online MAPF extend assignment structure or repeatedly solve problems on the same graph.
4 Benchmarks
The paper organizes MAPF benchmarks around map types, source-target assignment methods, and publicly available benchmark suites. Its new grid benchmark spans diverse maps and scenarios, and ICBS results show substantial difficulty variation and challenging instances.
- Benchmark design: MAPF benchmarks combine graphs with sets of agent source and target vertices.
- Sources and targets: Source-target assignments may be random, clustered within radius r, or designated from specified source and target sets.Designated assignments have been used to model warehouse and intersection applications.
- Maps: Common map types include DAO, open, obstacle-filled, warehouse, city, maze-like, and room-like grids.The grid-based benchmark contains 24 maps from cities, games, open grids, mazes, and room-like environments.
- Grid-based MAPF benchmark: The benchmark provides 25 scenarios per map, with randomly paired source-target vertices from each map’s largest reachable region.Each scenario contains up to 1000 source-target pairs, from which MAPF problems can be formed by selecting subsets.
- Evaluation: The proposed evaluation increases the agent count consecutively for a selected algorithm, map type, and scenario until the solver fails or exceeds the time limit.The ICBS baseline used a 30-second timeout under a classical MAPF setting with sum of costs and specified conflict rules.
- Results: ICBS solved many benchmark problems, but many remained unsolved within 30 seconds, while scenario difficulty varied substantially within maps.For brc202d, the maximum solved agent count ranged from 2 in one scenario to 22 in another.
5 Conclusion
The paper proposes common terminology and experimental settings for MAPF research. It defines classical MAPF assumptions and extensions, introduces a new benchmark suite, and points to Asprilo as another benchmark resource.
- The paper defines common assumptions for classical MAPF and discusses their relationships.
- It introduces a new suite of MAPF benchmark problems and points to another publicly available benchmark set.
- Together, the terminology and benchmarks are intended to provide a common language and experimental setting for MAPF research.