多智能体在未知迷宫中通过局部通信协作导航，效率接近最优。
Scalable Multi-Agent Maze Traversal with Local Communication
- 采用领导者-追随者机制与动态换领，仅一个智能体实时探索
- 625个智能体实验显示，总能耗随数量增加而下降
- 适合大规模分布式导航场景，尤其通信受限的复杂环境
洞穴网络、管道系统等类似迷宫的环境，在通信受限且未知的情况下对多智能体导航构成重大挑战。我们提出一种分布式算法，使智能体能够共同遍历一个未知的、可能含环的图结构。智能体按序从指定起点进入，任务是定位并抵达未公开的目标点，同时避免碰撞。它们通过局部通信建立领导者-追随者关系并实现领导权切换。在任意时刻，仅一个智能体执行单智能体迷宫求解器进行探索。我们证明该算法具有完备性，其完成时间（makespan）在智能体数量上渐近等价于最优全知策略，并推导出其时间和空间复杂度。模拟实验最多使用625个智能体，结果显示随着智能体数量增加，平均总燃料消耗持续下降，且显著优于所有智能体独立运行单智能体求解器的基线方法。
原文摘要 · Abstract (English)
Cave networks, pipe systems, and similar maze-like environments pose significant challenges for multi-agent navigation in unknown settings with limited communication. We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph. Agents enter sequentially at a designated start node and are tasked to localize and reach an undisclosed goal while avoiding collisions. They coordinate via local communication using leader-follower relationships and leader switching. At any moment in time, exploration is performed by only one of the agents, which runs a single-agent maze solver. We prove that the algorithm is complete, that its makespan is asymptotically equivalent (in the number of agents) to that of an optimal full-knowledge strategy, and derive its time and space complexity. Simulations with up to $625$ agents show a decreasing average sum-of-fuels as the number of agents increases and demonstrate that the proposed approach outperforms a naïve baseline in which all agents independently execute the single-agent solver.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。