自由構成バイアスサンプリングによるモーションプランニング

サンプリングベースのモーションプランニングアルゴリズムでは、各イテレーションにおける最初のステップは、障害物のない構成空間から新しいサンプルを生成することです。これは通常、拒否サンプリングを介して達成され、すなわち、障害物のない点が見つかるまで全体の空間から点を繰り返し抽出します。この戦略はほとんど疑問視されることはありません。なぜなら、サンプリング（そしてその後の拒否）に関連する追加の作業は、プランニングアルゴリズムの漸近的実行時間の複雑性に対して定数因子を寄与するからです。しかし、実際にはこの定数因子は非常に大きくなり得ます。我々は、障害物のない空間の上で一様分布に収束することが証明された分布からのサンプリングを可能にする代替アプローチを提案します。我々の方法は、障害物のない空間の経験的に観察された推定値を点近接データ構造に格納し、その情報を使用して将来のサンプルを生成します。理論的および実験的な結果は我々のアプローチを検証しています。