ロボットナビゲーションのための最小障害物移動計画へのホライズン分割アプローチ
A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation
衝突のない経路が存在しない場合に、可動障害物を移動させて目標地点への経路を計画する問題を扱い、NP困難性を示すとともに、計算負荷を抑えつつ最適解に近い近似解法を提案した。
著者: Antony Thomas, Giulio Ferro, Fulvio Mastrogiovanni, Michela Robba, Marco Baglietto
分類: cs.RO, cs.AI
原文アブストラクト
In this paper, we investigate the Minimum Obstacle Displacement Planning problem from a robot motion planning perspective. The problem involves determining a feasible path to a goal location by displacing movable obstacles when no collision-free path initially exists. We show that this problem is computationally challenging and, in particular, NP-hard when obstacles are modeled as polygons in the plane. Besides an exact formulation of the minimum obstacle displacement problem generalizing other problems in the literature, and the associated optimal solution, this paper proposes an approximate solution that is less intensive from a computational standpoint, and differs from the optimal solution by a fraction of the optimal cost, being able to trade-off between path length and amount of obstacle displacements.