C-Space Tunnel Discovery for Puzzle Path Planning

Xinya Zhang, Robert Belfer, Paul G. Kry, Etienne Vouga

Accepted by SIGGRAPH 2020

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.

  1. [Paper (TOG)]
  2. [Supplementary Material], contains:
    • A few hand picked key configurations;
    • Samples of training images;
    • All puzzles used in our paper (for additional ones see “Puzzle Repository” below);
    • A blender-based visualizer to show the solution path found by our planner.
  3. [Vimeo Video] [Youtube Video]
  4. [Main Source Code]
  5. [Puzzle Repository]

Videos

Solution Video

Visualizations

Authors

Xinya Zhang

The University of Texas at Austin

Robert Belfer

McGill University

Paul G. Kry

McGill University

Etienne Vouga

The University of Texas at Austin

BibTex

@article{zhang2020cspace,
  title={{C-Space Tunnel Discovery for Puzzle Path Planning}},
  author={Zhang, Xinya and Belfer, Robert and Kry, Paul G and Vouga, Etienne},
  journal={ACM Transactions on Graphics (TOG)},
  volume={39},
  number={4},
  pages={1--14},
  articleno = {104},
  year={2020},
  publisher={ACM New York, NY, USA}
}