优化图中边的方向与权重，让多智能体路径规划更高效可靠
Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding
- 提出混合引导图优化方法，同时调整边的方向和权重
- 新方法使高成本动作变为禁止通行，实现严格路径引导
- 适合长期运行的多智能体系统，提升复杂场景下的规划效率
多智能体路径规划（MAPF）旨在将多个智能体从起点移动到目标点。长期多智能体路径规划（LMAPF）在智能体完成任务后持续分配新目标。现有方法通过引导图优化（GGO）构建有向加权图，其中边代表移动或等待动作，权重表示行动代价。然而，权重仅提供软性引导：高权重仅降低使用概率，不禁止通行。本文提出将边方向优化纳入GGO，引入混合引导图优化（MGGO），设计两种方法：第一种分两阶段分别优化方向与权重；第二种采用质量多样性算法训练神经网络，直接生成方向与权重。同时，将交通模式信息融入引导图，使生成的图具备方向感知能力。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) aims to move agents from their start to goal vertices on a graph. Lifelong MAPF (LMAPF) continuously assigns new goals to agents as they complete current ones. To guide agents' movement in LMAPF, prior works have proposed Guidance Graph Optimization (GGO) methods to optimize a guidance graph, which is a bidirected weighted graph whose directed edges represent moving and waiting actions with edge weights being action costs. Higher edge weights represent higher action costs. However, edge weights only provide soft guidance. An edge with a high weight only discourages agents from using it, instead of prohibiting agents from traversing it. In this paper, we explore the need to incorporate edge directions optimization into GGO, providing strict guidance. We generalize GGO to Mixed Guidance Graph Optimization (MGGO), presenting two MGGO methods capable of optimizing both edge weights and directions. The first optimizes edge directions and edge weights in two phases separately. The second applies Quality Diversity algorithms to optimize a neural network capable of generating edge directions and weights. We also incorporate traffic patterns relevant to edge directions into a GGO method, making it capable of generating edge-direction-aware guidance graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。