重要状態を学習するクリティカル確率的ロードマップ
Learned Critical Probabilistic Roadmaps for Robotic Motion Planning
グラフ理論の媒介中心性で経路計画に重要な状態を特定し、局所環境特徴からその重要度を学習して階層グラフで活用する手法を提案。一様サンプリング比で最大3桁の効率改善を達成した。
著者: Brian Ichter, Edward Schmerling, Tsang-Wei Edward Lee, Aleksandra Faust
分類: cs.RO, cs.LG
原文アブストラクト
Sampling-based motion planning techniques have emerged as an efficient algorithmic paradigm for solving complex motion planning problems. These approaches use a set of probing samples to construct an implicit graph representation of the robot's state space, allowing arbitrarily accurate representations as the number of samples increases to infinity. In practice, however, solution trajectories only rely on a few critical states, often defined by structure in the state space (e.g., doorways). In this work we propose a general method to identify these critical states via graph-theoretic techniques (betweenness centrality) and learn to predict criticality from only local environment features. These states are then leveraged more heavily via global connections within a hierarchical graph, termed Critical Probabilistic Roadmaps. Critical PRMs are demonstrated to achieve up to three orders of magnitude improvement over uniform sampling, while preserving the guarantees and complexity of sampling-based motion planning. A video is available at https://youtu.be/AYoD-pGd9ms.
