効率的な階層的経路計画のための新しいヒューリスティックアルゴリズム

著者は、経路計画の最も一般的なアプローチの一つである階層的近似セル分解を考察します。このアプローチは、ロボットの構成空間を直方体セルに逐次的に分解し、各分解レベルで構築された接続性グラフを検索して経路を見つけることから成り立っています。その概念的な単純さにもかかわらず、このアプローチの効率的な実装は、まだ対処されていない多くの微妙な問題を提起します。この研究の主要な貢献は、(1) 制約の再定式化に基づくセル分解の新しいアプローチと、(2) 失敗条件を記録するメカニズムを持つ階層的検索の新しいアルゴリズムです。これらのアルゴリズムは経路プランナーに実装され、このプランナーを使用した様々な例で実験が行われました。これらの実験は、提案されたプランナーが同じ一般的なアプローチに基づく以前のプランナーよりも大幅に（約10倍）速いことを示しています。