用几何抽象解决未知环境中的移动代理覆盖与连通问题
On Mobile Ad Hoc Networks for Coverage of Partially Observable Worlds
- 将覆盖问题建模为部分可观测的协作守卫画廊问题，设计新算法
- 在1500次仿真中均实现空间覆盖与网络连通，成功率高
- 去中心化方案效果接近集中式，适合大规模移动网络部署
本文研究在初始未知环境中，如何通过移动代理的运动与部署建立通信网络。将覆盖问题与视距约束纳入计算几何框架，提出部分可观测协作守卫画廊问题（POCGAGP）的变体。设计两种求解算法：CADENCE为集中式规划器，逐步选择270度拐角部署代理；DADENCE为去中心化方案，仅依赖局部信息与轻量级通信。两者均在部分可观测条件下实现同步覆盖与连通。在1500个不同规模与结构的测试案例中进行仿真评估，结果表明两类方法均能稳定构建连通网络并探索未知空间。研究验证了几何抽象在通信驱动探索中的有效性，并显示去中心化策略可媲美集中式性能，同时具备良好可扩展性。
原文摘要 · Abstract (English)
This paper addresses the movement and placement of mobile agents to establish a communication network in initially unknown environments. We cast the problem in a computational-geometric framework by relating the coverage problem and line-of-sight constraints to the Cooperative Guard Art Gallery Problem, and introduce its partially observable variant, the Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP). We then present two algorithms that solve POCGAGP: CADENCE, a centralized planner that incrementally selects 270 degree corners at which to deploy agents, and DADENCE, a decentralized scheme that coordinates agents using local information and lightweight messaging. Both approaches operate under partial observability and target simultaneous coverage and connectivity. We evaluate the methods in simulation across 1,500 test cases of varied size and structure, demonstrating consistent success in forming connected networks while covering and exploring unknown space. These results highlight the value of geometric abstractions for communication-driven exploration and show that decentralized policies are competitive with centralized performance while retaining scalability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。