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
this https URL

该研究提出了一种通过图论技术和本地环境特征来识别关键状态的方法，并通过分层图中的全局连接有效利用这些关键状态来提高采样规划效率的 “Critical Probabilistic Roadmaps” 的算法，达到比均匀采样高三个数量级的效率提升。