増分サンプリングとセグメンテーションによる運動計画の実行不可能性判定
An Incremental Sampling and Segmentation-Based Approach for Motion Planning Infeasibility
ロボットの運動計画において、障害物領域をサンプリングして構成空間を徐々に構築し、始点と終点が同じ連結領域にあるかを判定することで、計画が実行不可能であることを検出する簡便なアルゴリズムを提案した。
著者: Antony Thomas, Fulvio Mastrogiovanni, Marco Baglietto
分類: cs.RO
原文アブストラクト
We present a simple and easy-to-implement algorithm to detect plan infeasibility in kinematic motion planning. Our method involves approximating the robot's configuration space to a discrete space, where each degree of freedom has a finite set of values. The obstacle region separates the free configuration space into different connected regions. For a path to exist between the start and goal configurations, they must lie in the same connected region of the free space. Thus, to ascertain plan infeasibility, we merely need to sample adequate points from the obstacle region that isolate start and goal. Accordingly, we progressively construct the configuration space (initially assumed to be entirely free) by sampling from the discretized space and updating the bitmap cells representing obstacle regions. Subsequently, we partition this partially built configuration space to identify different connected components within it and assess the connectivity of the start and goal cells. We illustrate this methodology on five different scenarios with configuration spaces having up to 5 degrees-of-freedom (DOF). Additionally, we discuss further optimizations designed to significantly accelerate the proposed algorithm. The scalability of our approach to higher-dimensional configuration spaces is also examined, with experimental demonstrations involving 6-DOF and 7-DOF robots.
