2次元環境における移動ロボットのセンサカバレッジ:効率限界を伴う最適化アプローチ
Mobile Robot Sensory Coverage in 2-D Environments: An Optimization Approach with Efficiency Bounds
障害物の有無やマルチターゲット視野を考慮した移動ロボットのセンサカバレッジ計画問題をMINLPで定式化し、多項式時間近似アルゴリズムと厳密解とのギャップを制限する限界を導出した論文。
著者: E. Fourney, J. W. Burdick, E. D. Rimon
分類: cs.RO
原文アブストラクト
This paper considers three related mobile robot multi-target sensory coverage and inspection planning problems in 2-D environments. In the first problem, a mobile robot must find the shortest path to observe multiple targets with a limited range sensor in an obstacle free environment. In the second problem, the mobile robot must efficiently observe multiple targets while taking advantage of multi-target views in an obstacle free environment. The third problem considers multi-target sensory coverage in the presence of obstacles that obstruct sensor views of the targets. We show how all three problems can be formulated in a MINLP optimization framework. Because exact solutions to these problems are NP-hard, we introduce polynomial time approximation algorithms for each problem. These algorithms combine polynomial-time methods to approximate the optimal target sensing order, combined with efficient convex optimization methods that incorporate the constraints posed by the robot sensor footprint and obstacles in the environment. Importantly, we develop bounds that limit the gap between the exact and approximate solutions. Algorithms for all problems are fully implemented and illustrated with examples. Beyond the utility of our algorithms, the bounds derived in the paper contribute to the theory of optimal coverage planning algorithms.
