C-Space tunnel discovery for puzzle path planning
C-Space tunnel discovery for puzzle path planning
复制标题
DOI：
10.1145/3386569.3392468
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Xinya Zhang;Robert Belfer;P. Kry;E. Vouga
中科院分区：
文献类型：
--
作者：
Xinya Zhang;Robert Belfer;P. Kry;E. Vouga
刚体解缠谜题对人类和运动规划算法都是具有挑战性的，因为它们的解决方案涉及到棘手的扭曲和滑动移动，这些移动对应于在谜题的配置空间(C空间)中导航通过狭窄的隧道。我们提出了一种隧道发现和规划策略来解决这些难题。首先，我们使用几何启发式和机器学习来定位棋子上的重要特征，然后匹配这些特征对，以发现位于狭窄隧道内的拼图的C空间中的无碰撞状态。其次，我们提出了一种快速探索密集树(RDT)运动规划器变体，它构建隧道逃生路线图，然后将这些路线图连接到连接开始状态和目标状态的解决路径。我们评估了我们在各种具有挑战性的解开谜题上的方法，并提供了与其他运动规划技术的广泛基线比较。
Rigid body disentanglement puzzles are challenging for both humans and motion planning algorithms because their solutions involve tricky twisting and sliding moves that correspond to navigating through narrow tunnels in the puzzle's configuration space (C-space). We propose a tunnel-discovery and planning strategy for solving these puzzles. First, we locate important features on the pieces using geometric heuristics and machine learning, and then match pairs of these features to discover collision free states in the puzzle's C-space that lie within the narrow tunnels. Second, we propose a Rapidly-exploring Dense Tree (RDT) motion planner variant that builds tunnel escape roadmaps and then connects these roadmaps into a solution path connecting start and goal states. We evaluate our approach on a variety of challenging disentanglement puzzles and provide extensive baseline comparisons with other motion planning techniques.