C-Space Tunnel Discovery for Puzzle Path Planning

摘要

Rigid body disentanglement puzzles are challenging for both humans andmotion planning algorithms because their solutions involve tricky twistingand sliding moves that correspond to navigating through narrow tunnels inthe puzzle’s configuration space (C-space). We propose a tunnel-discoveryand planning strategy for solving these puzzles. First, we locate importantfeatures on the pieces using geometric heuristics and machine learning, andthen match pairs of these features to discover collision free states in thepuzzle’s C-space that lie within the narrow tunnels. Second, we proposea Rapidly-exploring Dense Tree (RDT) motion planner variant that buildstunnel escape roadmaps and then connects these roadmaps into a solutionpath connecting start and goal states. We evaluate our approach on a varietyof challenging disentanglement puzzles and provide extensive baselinecomparisons with other motion planning techniques.