将路径规划与执行分离，实现千级智能体高效避障。
Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding
- 先用成本膨胀法在原图上分步规划路径，避免时间建模
- 再用先进先出队列在执行时动态处理冲突，成功率100%
- 适合大规模密集场景，运行时间接近线性增长
多智能体路径寻找（MAPF）需在共享图上为多个智能体生成无碰撞轨迹，常以最小化总代价（SOC）为目标。现有最优与近似最优求解器依赖时间展开模型和集中式冲突解决，难以扩展至大规模或高密度实例。本文提出一种混合优先级框架，将几何规划与执行时冲突解决分离。第一阶段采用几何冲突预判（GCP），在原始图上使用A*算法顺序规划路径，通过膨胀进入已占用顶点的转移代价，促使空间绕行，无需显式时间推理。第二阶段由去中心化局部控制器（DLC）执行几何路径，利用每顶点的先进先出授权队列插入等待动作，避免顶点及边交换冲突。在最多含1000个智能体的标准基准地图上的实验表明，该方法具有近乎线性的运行时间趋势，在满足几何可行性假设的实例中达到100%成功率。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph, often with the objective of minimizing the sum-of-costs (SOC). Many optimal and bounded-suboptimal solvers rely on time-expanded models and centralized conflict resolution, which limits scalability in large or dense instances. We propose a hybrid prioritized framework that separates \emph{geometric planning} from \emph{execution-time conflict resolution}. In the first stage, \emph{Geometric Conflict Preemption (GCP)} plans agents sequentially with A* on the original graph while inflating costs for transitions entering vertices used by higher-priority paths, encouraging spatial detours without explicit time reasoning. In the second stage, a \emph{Decentralized Local Controller (DLC)} executes the geometric paths using per-vertex FIFO authorization queues and inserts wait actions to avoid vertex and edge-swap conflicts. Experiments on standard benchmark maps with up to 1000 agents show that the method scales with an near-linear runtime trend and attains a 100\% success rate on instances satisfying the geometric feasibility assumption. Page of the project: https://sites.google.com/unizar.es/multi-agent-path-finding/home
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。