arXiv:2508.03777cs.MAcs.AI2025-08被引 1

提出动态调整策略,让多智能体在部分失效时仍能高效避障。

When Agents Break Down in Multiagent Path Finding

  • 通过局部协商而非重规划来应对智能体故障
  • 最多增加k个时间步的完成时间,保障整体效率
  • 支持计算能力弱的智能体,适合真实部署

在多智能体路径规划(MAPF)中,目标是为多个智能体在网路中从起点到终点规划出无冲突、高效的路径,以最小化调度的完成时间(makespan)。本文提出一种新范式,正式建模部分智能体因故障导致延迟的情况,这对维持最优调度构成重大挑战。每次故障后重新计算整个调度往往计算开销过大。为此,我们提出一种无需完全重规划的动态调度适应框架。通过设计协议,使智能体能够本地协调并实时调整路径。证明了遵循主要通信协议时,经历k次故障后,完成时间的增加被严格限制在k个时间步以内,有效控制故障影响。此外,考虑到智能体计算能力有限,我们还提出次要协议,将必要计算转移至网络节点,无需提升智能体算力即可保证鲁棒性。结果表明,该方法为应对智能体失效提供了实用且可扩展的解决方案。

原文摘要 · Abstract (English)

In Multiagent Path Finding (MAPF), the goal is to compute efficient, collision-free paths for multiple agents navigating a network from their sources to targets, minimizing the schedule's makespan-the total time until all agents reach their destinations. We introduce a new variant that formally models scenarios where some agents may experience delays due to malfunctions, posing significant challenges for maintaining optimal schedules. Recomputing an entirely new schedule from scratch after each malfunction is often computationally infeasible. To address this, we propose a framework for dynamic schedule adaptation that does not rely on full replanning. Instead, we develop protocols enabling agents to locally coordinate and adjust their paths on the fly. We prove that following our primary communication protocol, the increase in makespan after k malfunctions is bounded by k additional turns, effectively limiting the impact of malfunctions on overall efficiency. Moreover, recognizing that agents may have limited computational capabilities, we also present a secondary protocol that shifts the necessary computations onto the network's nodes, ensuring robustness without requiring enhanced agent processing power. Our results demonstrate that these protocols provide a practical, scalable approach to resilient multiagent navigation in the face of agent failures.

路径规划多智能体容错

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。