幾何学と情報理論を組み合わせた複数ロボット探索アルゴリズム
Combining Geometric and Information-Theoretic Approaches for Multi-Robot Exploration
情報理論的探索と計算幾何学的探索を融合し、複数ロボットで直交多角形を効率的に探索するアルゴリズムを提案。理論解析とシミュレーション・実機実験で性能を検証した。
著者: Aravind Preshant Premkumar, Kevin Yu, Pratap Tokekar
分類: cs.RO, cs.AI
原文アブストラクト
We present an algorithm to explore an orthogonal polygon using a team of $p$ robots. This algorithm combines ideas from information-theoretic exploration algorithms and computational geometry based exploration algorithms. We show that the exploration time of our algorithm is competitive (as a function of $p$) with respect to the offline optimal exploration algorithm. The algorithm is based on a single-robot polygon exploration algorithm, a tree exploration algorithm for higher level planning and a submodular orienteering algorithm for lower level planning. We discuss how this strategy can be adapted to real-world settings to deal with noisy sensors. In addition to theoretical analysis, we investigate the performance of our algorithm through simulations for multiple robots and experiments with a single robot.
