高次元状態空間におけるサンプリングベース運動計画のための貪欲ヒューリスティクス
Greedy Heuristics for Sampling-Based Motion Planning in High-Dimensional State Spaces
現在の解経路に沿った最大ヒューリスティックコストに基づいてサンプリング領域を縮小する「貪欲情報集合」を導入し、RRT*の双方向 anytime 変種である G-RRT* を提案した。これにより、初期解を迅速に見つけつつ漸近的最適性を達成し、最先端のサンプリングベース計画法を上回る性能を示した。
著者: Phone Thiha Kyaw, Anh Vu Le, Rajesh Elara Mohan, Jonathan Kelly
分類: cs.RO
原文アブストラクト
Informed sampling techniques accelerate the convergence of sampling-based motion planners by biasing sampling toward regions of the state space that are most likely to yield better solutions. However, when the current solution path contains redundant or tortuous segments, the resulting informed subset may remain unnecessarily large, slowing convergence. Our prior work addressed this issue by introducing the greedy informed set, which reduces the sampling region based on the maximum heuristic cost along the current solution path. In this article, we formally characterize the behavior of the greedy informed set within Rapidly-exploring Random Tree (RRT*)-like planners and analyze how greedy sampling affects exploration and asymptotic optimality. We then present Greedy RRT* (G-RRT*), a bi-directional anytime variant of RRT* that leverages the greedy informed set to focus sampling in the most promising regions of the search space. Experiments on abstract planning benchmarks, manipulation tasks from the MotionBenchMaker dataset, and a dual-arm Barrett WAM problem demonstrate that G-RRT* rapidly finds initial solutions and converges asymptotically to optimal paths, outperforming state-of-the-art sampling-based planners.
