移動ロボットにおける最小制約除去問題の再検討
Revisiting the Minimum Constraint Removal Problem in Mobile Robotics
障害物を最小数だけ除去して始点と終点を結ぶ衝突のない経路を見つける問題について、単連結障害物の場合のNP困難性と、除去数が(n+1)/3未満のときの多項式時間解法を示した。
著者: Antony Thomas, Fulvio Mastrogiovanni, Marco Baglietto
分類: cs.RO
原文アブストラクト
The minimum constraint removal problem seeks to find the minimum number of constraints, i.e., obstacles, that need to be removed to connect a start to a goal location with a collision-free path. This problem is NP-hard and has been studied in robotics, wireless sensing, and computational geometry. This work contributes to the existing literature by presenting and discussing two results. The first result shows that the minimum constraint removal is NP-hard for simply connected obstacles where each obstacle intersects a constant number of other obstacles. The second result demonstrates that for $n$ simply connected obstacles in the plane, instances of the minimum constraint removal problem with minimum removable obstacles lower than $(n+1)/3$ can be solved in polynomial time. This result is also empirically validated using several instances of randomly sampled axis-parallel rectangles.
