Multi-Agent Pathfinding (MAPF) is the problem of planning paths for multiple agents so that each reaches its target and all paths can be executed concurrently without collisions. Motivating applications include automated warehouses, autonomous vehicles, and robotics. In classical MAPF, time is discrete, agents occupy graph vertices, and each agent performs one move or wait action per time step. Existing papers make different assumptions about motion and conflicts, including whether agents may traverse the same road at the same time, and optimize different objectives such as makespan or the sum of action costs. Because these assumptions and objectives may be implicit or described with inconsistent terminology, it is difficult to understand the literature, select appropriate baselines, or find work matching a concrete application.
The first contribution is a unified terminology and classification for describing common MAPF assumptions, conflicts, objectives, and variants. The classification is intended to help researchers state their problem settings accurately and choose baselines that are appropriate for comparison. It covers classical MAPF as well as extensions that relax classical assumptions about time, actions, or occupancy. The second contribution is a new grid-based benchmark with diverse maps and generated source-target scenarios, together with pointers to other benchmark resources. The paper is positioned as a foundation for definitions and evaluation, not as a comprehensive survey of the state of the art in MAPF algorithms.
The paper first formalizes classical MAPF using an undirected graph, a set of agents, and a source and target for every agent. Time is discretized, and a single-agent plan is defined as a sequence of actions that takes the agent from its source to its target. It then organizes collision concepts involving situations such as shared vertices and agents exchanging positions through an edge, so that joint plans can be judged for concurrent executability. It distinguishes makespan, the time until the last agent reaches its target, from the sum of all agents' action costs. The paper also discusses weighted graphs, where edge weights represent traversal durations, and other settings that relax classical time and occupancy assumptions. For benchmarking, map selection and source-target assignment are treated as separate design choices, and a standard MAPF 提案手順s used to examine the difficulty of the new benchmark.
The benchmark is composed of graph instances and source-target sets associated with those graphs. Its new grid-based component contains diverse maps and generated source and target vertices. The authors run a standard MAPF algorithm and experimentally report that the benchmark is challenging for contemporary MAPF algorithms. This supports the intended role of the benchmark as a future comparison baseline, but the supplied excerpt does not establish the complete names of all algorithms used, runtimes, success rates, solution costs, trial counts, hardware, or detailed numerical comparisons. The paper describes or points to existing resources including Dragon Age Origins maps, grids with randomly selected impassable cells, warehouse-style grids, and ASPRILO. Thus, the evidence supports a claim about benchmark difficulty and evaluation use, not a ranking of methods or a measured performance gap.
A shared vocabulary can improve comparability by making the effects of collision rules, time models, traversal durations, objectives, map structures, and source-target assignments explicit. It can also help practitioners find research that matches application constraints rather than relying on superficially similar terminology. The authors explicitly acknowledge that the proposed benchmarks are not perfect and may contain biases, so the excerpt does not establish that they represent all MAPF workloads without bias. Map families and scenario assignments may favor or disadvantage particular algorithms or applications, and results from one benchmark should not be interpreted as universal superiority. Weighted travel, deadline-based maximization of the number of agents reaching targets, task arrivals, and new agents appearing over time illustrate directions beyond the classical model, but the excerpt does not establish detailed failure analyses or performance characteristics for those extensions.
MAPF has received increasing attention from several research groups and academic communities because of its relevance to automated warehouses, autonomous vehicles, and robotics. Existing papers use different modeling assumptions and objective functions, and related formal settings may be described with different terminology. This fragmentation makes prior work difficult to understand, fair baselines difficult to establish, and application-relevant papers difficult to locate. The authors present this paper as a common reference for definitions, variants, and benchmarks rather than as a state-of-the-art algorithm survey. They also point readers to a website providing MAPF tutorials and other resources.
A classical MAPF instance contains an undirected graph, a set of agents, a source vertex for each agent, and a target vertex for each agent. At every discrete time step, each agent occupies one vertex and can wait or move to an allowed neighboring vertex. Each individual plan must end at its assigned target, while the collection of plans must avoid collisions during concurrent execution. The supplied excerpt contains only part of the formal conflict presentation, so it does not establish every mathematical condition needed to reconstruct the complete definition. The central problem is therefore both to find jointly executable paths and to describe the exact model being solved explicitly.
The paper distinguishes collision concepts involving agents sharing a vertex and agents moving in opposite directions through an edge to exchange positions. It separates makespan from the sum of action costs, while noting that both objective families have been studied by different classes of MAPF algorithms. Classical MAPF assumes that every move or wait takes one time step and that an agent occupies exactly one vertex at every time. Weighted-graph MAPF replaces uniform action duration with edge-specific traversal durations. The paper also mentions maximizing the number of agents reaching targets by a deadline, as well as settings with new tasks after arrival and new agents appearing over time.
The benchmark design combines collections of graphs with source-target scenarios for those graphs. The new grid benchmark provides diverse maps and generated assignments intended to support reusable and organized comparisons of future algorithms. Existing resources described or referenced include Dragon Age Origins game maps, grids with randomly selected impassable cells, warehouse-style grids, and ASPRILO. A standard MAPF 提案手順s used as a baseline demonstration of the benchmark's difficulty. The supplied evidence does not establish all parameter choices, instance counts, time limits, implementation details, or evaluation metrics.
The central reported experimental result is that the new grid-based benchmark presents a challenging problem for contemporary MAPF algorithms. It is offered as a resource for more scientifically organized comparisons in future research. The excerpt does not provide enough numerical evidence to determine runtimes, success percentages, solution-quality gaps, algorithm rankings, or statistical significance. The result should therefore be read as a claim about benchmark difficulty and intended evaluation usefulness, not as evidence that one particular 提案手順s generally superior.
The paper defines common assumptions and objectives for classical MAPF and organizes notable extensions beyond that model. It also introduces a new MAPF benchmark suite and points to another set of benchmark problems. Together, these parts aim to provide common language, terminology, and experimental practice for MAPF research. The authors hope future researchers will use the terminology to describe contributions clearly and the benchmarks to support comparable evaluations. The excerpt establishes this intended role and the reported difficulty, but not a universal standard or a complete account of all MAPF research.
The authors explicitly state that the proposed benchmarks are not perfect and may contain biases. Map families and source-target scenarios can favor particular algorithms or workloads, so one benchmark cannot establish universally representative performance. The supplied excerpt does not establish the full experimental protocol, reproducibility procedure, quantitative results, coverage of every MAPF variant, or treatment of uncertainty in real deployments. It also does not provide detailed failure conditions or robustness evaluations for weighted-graph and task-oriented extensions. Continued use and study are expected to reveal benchmark biases and allow future corrections.
Meaningful MAPF comparisons require explicit statements of the collision model, time and motion model, objective, map distribution, and source-target scenarios. This paper provides a common vocabulary and an organized benchmark starting point for doing that. It can improve the clarity of research reports and help practitioners identify work relevant to their application requirements. Its value is in structuring problem definitions and empirical comparisons, rather than in proving a best algorithm. It is especially useful for separating differences in problem assumptions from differences in solver performance.
This paper is suitable for MAPF researchers who need a framework for describing problem variants, collision assumptions, objectives, and benchmark construction. It is also useful for newcomers learning how classical MAPF differs from weighted-graph and task-oriented extensions. Practitioners can use it as a checklist for matching application requirements with research model assumptions. Readers seeking detailed numerical comparisons of current algorithms or a complete state-of-the-art survey should also consult the full paper and dedicated algorithm surveys, because those conclusions are not established by the supplied excerpt.