解决部分智能体无目标的多智能体路径规划问题
Unassigned Agents in Compilation-based Multi-agent Path Finding
- 将未分配目标的智能体纳入编译式路径规划框架
- 基于SMT-CBS与NRF-SAT实现高效求解
- 适合处理有动态或临时智能体的场景
编译式方法因其模块化和对非标准变体的适应性，是多智能体路径规划（MAPF）的重要求解手段。标准MAPF要求所有智能体从初始位置到达指定目标位置且不发生碰撞，但存在一种变体——未分配智能体的MAPF（UA-MAPF），其中部分智能体具有初始位置和目标位置，而其余智能体仅有初始位置且无目标。这些未分配智能体虽无需到达特定位置，但在路径规划中仍需避让其他智能体，带来独特挑战。本文证明，该问题可被纳入基于布尔可满足性的最新编译式方法中，具体通过适配基于反例引导抽象精化的SMT-CBS和非精炼抽象的NRF-SAT求解器实现。
原文摘要 · Abstract (English)
Compilation-based techniques represent an important stream of solvers for multi-agent path finding (MAPF) due to their modularity and adaptability for non-standard variants of the problem. While in the standard MAPF the task is to navigate all agents from their initial positions to given individual goal positions without any collision, variants where a different requirement for agents is used are also relevant. Such a variant is MAPF with unassigned agents (UA-MAPF) where some agents have the same setting as in the standard MAPF with initial positions and goals while the remaining agents have the initial position but have no goal - unassigned agents. Despite unassigned agent do not need to reach any goal position they have to be moved out of the way of the standard agents if needed which represent a specific challenge. We show in this paper that UA-MAPF can be expressed in recent compilation-based techniques for MAPF based on formulating the problem as Boolean satisfiability, namely we adapt SMT-CBS and NRF-SAT, the recent solvers based on counterexample guided abstraction refinement and non-refined abstractions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。