解决高密度仓储中多机器人路径规划难题，确保不阻塞后续操作。
Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms
- 提出新模型PS-MAPF，要求机器人先经中转点再停靠终点。
- 证明在2边连通图上必有解，且给出解存在的精确条件。
- 提出高效算法PPP，比基线快数十倍，适用于仓储物流场景。
自动化高密度存储系统（如仓库、机器人停车场、工厂物流等）需要多智能体在有限关键资源间移动，并最终停靠于无名站点，不得阻碍后续操作。本文提出一种新型多智能体路径规划问题——枢轴-站位多智能体路径规划（PS-MAPF），其中部分任务智能体需依次访问一组可互换的枢轴点（如工作站），随后整个舰队终止于匿名站点，每个站点仅一个智能体。我们完全刻画了该问题的可解性：所有2边连通图上的实例均存在解；在任意连通图上，基于未占用顶点数的结构有效距离度量是解存在的充要条件。我们证明：即使仅有一个枢轴点，最小化站位完成时间或站位流时间也是NP-hard。本文提出三种算法：一个完整基线算法、基于SAT的最优求解器，以及枢轴优先规划（PPP）。PPP算法在基准测试中成功求解74%-89%的实例，其完成时间和流时间比基线低数个数量级。
原文摘要 · Abstract (English)
Automated high-density storage systems (warehouses, robotic parking, plant logistics, etc.) require fleets of agents to move through scarce task-critical resources and then park without obstructing future operations. We introduce Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a MAPF variant in which a subset of tasked agents must each visit one of a set of interchangeable pivots (e.g., workstations) before the entire fleet terminates at anonymous stations, one agent per station. We characterize solvability completely: every instance on a 2-edge-connected graph is solvable, and, on arbitrary connected graphs, a structural effective-distance measure relative to the number of unoccupied vertices gives a necessary and sufficient condition. We prove that minimizing station-makespan or station-flowtime is NP-hard already with a single pivot. We present three algorithms, a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning (PPP), the last solving 74-89% of benchmark instances with makespan and flowtime orders of magnitude below the baseline.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。