跳转至

文章背景与核心概要

自动化高密度存储系统（如智能仓储机器人、自动化立体车库以及工业厂房物流）通常需要调度大批自主智能体在稀缺的任务关键资源中进行导航，并安全停放以免阻碍后续的作业。为了解决这一挑战，本文引入了“轴心与站点多智能体路径规划”（Pivot-and-Station Multi-Agent Path Finding, 简称 PS-MAPF），这是标准多智能体路径规划（MAPF）问题的一种全新变体。在该问题中，部分执行任务的智能体在转换之前必须先访问至少一个可互换的“轴心”（例如工作站），最终整个智能体机群需在匿名的“站点”停泊（每个站点恰好停放一个智能体）。

本文作者针对这一路径规划难题，建立了一系列基础理论洞见与高性能算法：1. 可解性表征：证明了在任意 2-边连通图上的每个实例都是可解的。对于任意连通图，结合相对于空闲顶点数量的结构化有效距离测度，给出了一个精确的充要条件。2. 计算复杂性：证明了最小化站点完工时间（makespan）或站点流经时间（flowtime）是 NP 难问题，即使将场景限制在单个轴心时也是如此。3. 算法设计：介绍了三种不同的方法，包括一个完备的基准算法、一个基于 SAT 的最优求解器，以及轴心优先级规划（Pivot-Prioritized Planning, 简称 PPP）。值得注意的是，PPP 成功解决了 74%–89% 的基准测试实例，其完工时间和流经时间指标比基准算法低了几个数量级。

轴心与站点多智能体路径规划：可解性、复杂性与算法 (Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms)

作者： Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini
主要学科： 人工智能 (cs.AI)
arXiv 标识符： arXiv:2608.24585 [cs.AI]
提交时间： 2026年8月25日

📋 摘要 (Summary)

自动化高密度存储系统（如机器人仓库、自动化停车场和工业厂房物流）频繁要求由自主智能体组成的机群在稀缺且对任务至关重要的资源中导航，并安全停放而不妨碍未来的操作。

Automated high-density storage systems—such as robotic warehouses, automated parking garages, and industrial plant logistics—frequently require fleets of autonomous agents to navigate scarce, task-critical resources and securely park without impeding future operations.

本文引入了轴心与站点多智能体路径规划（Pivot-and-Station Multi-Agent Path Finding, 简称 PS-MAPF），这是标准 MAPF 问题的一种新颖变体。在 PS-MAPF 中： * 任务智能体的一个子集在转换前必须各自访问至少一个可互换的轴心（例如工作站）。 * 整个机群最终终止于匿名的站点（每个站点恰好有一个智能体）。

This paper introduces Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a novel variant of the standard MAPF problem. In PS-MAPF: * A subset of tasked agents must each visit at least one interchangeable pivot (e.g., a workstation) before transitioning. * The entire fleet eventually terminates at anonymous stations (exactly one agent per station).

作者针对这一路径规划挑战建立了基础的理论见解和高性能算法： 1. 可解性表征：证明了 2-边连通图上的每个实例都是可解的。对于任意连通图，相对于未占用顶点数量的结构化有效距离度量提供了精确的必要和充分条件。 2. 计算复杂性：证明了最小化站点完工时间（makespan）或站点流经时间（flowtime）是 NP 难的，即使限制在单个轴心时也是如此。 3. 算法：介绍了三种不同的方法，包括一个完备的基准方法、一个基于 SAT 的最优求解器以及轴心优先级规划（PPP）。值得注意的是，PPP 成功解决了 74–89% 的基准测试实例，其完工时间和流经时间指标比基准低了几个数量级。

The authors establish foundational theoretical insights and high-performing algorithms to address this routing challenge: 1. Solvability Characterization: Proves that every instance on a 2-edge-connected graph is solvable. For arbitrary connected graphs, a structural effective-distance measure relative to the number of unoccupied vertices provides a precise necessary and sufficient condition. 2. Computational Complexity: Demonstrates that minimizing station-makespan or station-flowtime is NP-hard, even when restricted to a single pivot. 3. Algorithms: Introduces three distinct approaches, including a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning (PPP). Notably, PPP successfully resolves 74–89% of benchmark instances with makespan and flowtime metrics orders of magnitude lower than the baseline.