多机器人协同搜索受限视野下的静止与移动入侵者
Multi-robot searching with limited sensing range for static and mobile intruders
- 采用空间填充曲线与随机搜索策略提升覆盖效率
- 证明了搜索问题即使对静止入侵者也属NP难
- 适合在复杂几何区域内部署的多机器人系统参考
本文研究在几何区域内利用多个搜索机器人探测入侵者的问题。搜索区域为简单连通的正交多边形，边与笛卡尔坐标轴平行。每个机器人具有有限感知范围。针对静止和移动入侵者两种情形进行了分析，结果表明该问题即使对于静止入侵者也是NP-hard的。鉴于其计算复杂性，本文提出基于空间填充曲线、随机搜索及协作随机搜索的高效且鲁棒的算法。同时评估了不同算法在机器人数量与搜索时间之间的权衡，并考虑了连通正交区域的几何特性。
原文摘要 · Abstract (English)
We consider the problem of searching for an intruder in a geometric domain by utilizing multiple search robots. The domain is a simply connected orthogonal polygon with edges parallel to the cartesian coordinate axes. Each robot has a limited sensing capability. We study the problem for both static and mobile intruders. It turns out that the problem of finding an intruder is NP-hard, even for a stationary intruder. Given this intractability, we turn our attention towards developing efficient and robust algorithms, namely methods based on space-filling curves, random search, and cooperative random search. Moreover, for each proposed algorithm, we evaluate the trade-off between the number of search robots and the time required for the robots to complete the search process while considering the geometric properties of the connected orthogonal search area.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。