research-article

C-Space tunnel discovery for puzzle path planning

Authors:

Etienne VougaAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 39, Issue 4

Article No.: 104, Pages 104:1 - 104:14

https://doi.org/10.1145/3386569.3392468

Published: 12 August 2020 Publication History

Abstract

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.

Supplemental Material

MP4 File

Presentation video

Transcript for: Presentation video

MP4 File

Download
64.41 MB

ZIP File

Supplemental files.

Download
94.16 MB

References

[1]

Nancy M Amato, O Burchan Bayazit, Lucia K Dale, Christopher Jones, and Daniel Vallejo. 1998a. Choosing good distance metrics and local planners for probabilistic roadmap methods. In Robotics and Automation, 1998. Proceedings. 1998 IEEE International Conference on, Vol. 1. IEEE, 630--637.

[2]

Nancy M Amato, O Burchan Bayazit, Lucia K Dale, Christopher Jones, and Daniel Vallejo. 1998b. OBPRM: An obstacle-based PRM for 3D workspaces. In Proc. Int. Workshop on Algorithmic Foundations of Robotics (WAFR). 155--168.

[3]

Taeg Sang Cho, Shai Avidan, and William T Freeman. 2010. A probabilistic image jigsaw puzzle solver. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, 183--190.

[4]

Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013. Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow. ACM Trans. Graph. 32, 5, Article 152 (Oct. 2013), 11 pages.

Digital Library

[5]

J. Denny, E. Greco, S. Thomas, and N. M. Amato. 2014. MARRT: Medial Axis biased rapidly-exploring random trees. In 2014 IEEE International Conference on Robotics and Automation (ICRA). 90--97.

[6]

David Eigen and Rob Fergus. 2015. Predicting depth, surface normals and semantic labels with a common multi-scale convolutional architecture. In Proceedings of the IEEE international conference on computer vision. 2650--2658.

Digital Library

[7]

Chelsea Finn and Sergey Levine. 2017. Deep visual foresight for planning robot motion. In 2017 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2786--2793.

Digital Library

[8]

Jonathan Gammell, Siddhartha Srinivasa, and Timothy Barfoot. 2015. Batch Informed Trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs. Proceedings - IEEE International Conference on Robotics and Automation 2015 (06 2015), 3067--3074.

[9]

Xiang Gao, Sébastien Loriot, and Andrea Tagliasacchi. 2019. Triangulated Surface Mesh Skeletonization. In CGAL User and Reference Manual (4.14 ed.). CGAL Editorial Board. https://doc.cgal.org/4.14/Manual/packages.html#PkgSurfaceMeshSkeletonization

[10]

David Goldberg, Christopher Malon, and Marshall Bern. 2004. A global approach to automatic solution of jigsaw puzzles. Computational Geometry 28, 2 (2004), 165--174.

Digital Library

[11]

Rana Hanocka, Amir Hertz, Noa Fish, Raja Giryes, Shachar Fleishman, and Daniel Cohen-Or. 2019. MeshCNN: a network with an edge. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1--12.

Digital Library

[12]

David Hsu, Jean-Claude Latombe, and Rajeev Motwani. 1999. Path Planning In Expansive Configuration Spaces. International Journal of Computational Geometry & Applications 09, 04n05 (1999), 495--512.

[13]

David Hsu, Gildardo Sánchez-Ante, and Zheng Sun. 2005. Hybrid PRM sampling with a cost-sensitive adaptive strategy. In Proceedings of the 2005 IEEE international conference on robotics and automation. IEEE, 3874--3880.

[14]

Qi-Xing Huang, Simon Flöry, Natasha Gelfand, Michael Hofer, and Helmut Pottmann. 2006. Reassembling Fractured Objects by Geometric Matching. ACM Trans. Graph. 25, 3 (July 2006), 569--578.

Digital Library

[15]

Brian Ichter, James Harrison, and Marco Pavone. 2018. Learning Sampling Distributions for Robot Motion Planning. 7087--7094.

Digital Library

[16]

Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. 2016. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv:1611.05397 (2016).

[17]

Niels Justesen, Philip Bontrager, Julian Togelius, and Sebastian Risi. 2019. Deep learning for video game playing. IEEE Transactions on Games (2019).

[18]

Evangelos Kalogerakis, Aaron Hertzmann, and Karan Singh. 2010. Learning 3D Mesh Segmentation and Labeling. In ACM SIGGRAPH 2010 Papers (Los Angeles, California). Association for Computing Machinery, New York, NY, USA, Article 102, 12 pages.

Digital Library

[19]

S. Karaman, M. R. Walter, A. Perez, E. Frazzoli, and S. Teller. 2011. Anytime Motion Planning using the RRT^*. In 2011 IEEE International Conference on Robotics and Automation. 1478--1483.

[20]

L. E. Kavraki, M. N. Kolountzakis, and J. Latombe. 1998. Analysis of probabilistic roadmaps for path planning. IEEE Transactions on Robotics and Automation 14, 1 (Feb 1998), 166--171.

[21]

L. E. Kavraki, P. Svestka, J. Latombe, and M. H. Overmars. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12, 4 (Aug 1996), 566--580.

[22]

Diederik P Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR). https://arxiv.org/abs/1412.6980

[23]

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems. 1097--1105.

[24]

J. J. Kuffner. 2004. Effective sampling and distance metrics for 3D rigid body path planning. In IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004, Vol. 4. 3993--3998 Vol.4.

[25]

J. J. Kuffner and S. M. LaValle. 2000. RRT-connect: An efficient approach to single-query path planning. In Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation, Vol. 2. 995--1001 vol.2.

[26]

A. M. Ladd and L. E. Kavraki. 2004. Measure theoretic analysis of probabilistic path planning. IEEE Transactions on Robotics and Automation 20, 2 (April 2004), 229--242.

[27]

Steven M. Lavalle. 1998. Rapidly-Exploring Random Trees: A New Tool for Path Planning. Technical Report. Report No. TR 98-11, Computer Science Department, Iowa State University.

[28]

Steven M LaValle. 2006. Planning algorithms. Cambridge university press.

Digital Library

[29]

Sergey Levine, Peter Pastor, Alex Krizhevsky, Julian Ibarz, and Deirdre Quillen. 2018. Learning hand-eye coordination for robotic grasping with deep learning and large-scale data collection. The International Journal of Robotics Research 37, 4-5 (2018), 421--436.

[30]

Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen. 2018. Pointcnn: Convolution on x-transformed points. In Advances in neural information processing systems. 820--830.

[31]

Zhouhui Lian, Afzal Godil, Benjamin Bustos, Mohamed Daoudi, Jeroen Hermans, Shun Kawamura, Yukinori Kurita, Guillaume Lavoué, Hien Van Nguyen, Ryutarou Ohbuchi, et al. 2011. SHREC'11 Track: Shape Retrieval on Non-rigid 3D Watertight Meshes. 3DOR 11 (2011), 79--88.

[32]

Michel J Litzkow, Miron Livny, and Matt W Mutka. 1987. Condor-a hunter of idle workstations. Technical Report. University of Wisconsin-Madison Department of Computer Sciences.

[33]

Kui-Yip Lo, Chi-Wing Fu, and Hongwei Li. 2009. 3D Polyomino Puzzle. ACM Trans. Graph. 28, 5 (Dec. 2009), 1--8.

Digital Library

[34]

Jim Mainprice, E Akin Sisbot, Léonard Jaillet, Juan Cortés, Rachid Alami, and Thierry Siméon. 2011. Planning human-aware motions using a sampling-based costmap planner. In 2011 IEEE International Conference on Robotics and Automation. IEEE, 5012--5017.

[35]

Alejandro Newell, Kaiyu Yang, and Jia Deng. 2016. Stacked hourglass networks for human pose estimation. In European Conference on Computer Vision. Springer, 483--499.

[36]

Jia Pan and Dinesh Manocha. 2016. Fast probabilistic collision checking for sampling-based motion planning using locality-sensitive hashing. The International Journal of Robotics Research 35, 12 (2016), 1477--1496.

Digital Library

[37]

Lerrel Pinto and Abhinav Gupta. 2016. Supersizing self-supervision: Learning to grasp from 50k tries and 700 robot hours. In 2016 IEEE international conference on robotics and automation (ICRA). IEEE, 3406--3413.

Digital Library

[38]

Ruggero Pintus, Kazim Pal, Ying Yang, Tim Weyrich, Enrico Gobbetti, and Holly Rushmeier. 2016. A Survey of Geometric Analysis in Cultural Heritage. Comput. Graph. Forum 35, 1 (Feb. 2016), 4--31.

Digital Library

[39]

Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. 2017. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition. 652--660.

[40]

Charles R Qi, Hao Su, Matthias Nießner, Angela Dai, Mengyuan Yan, and Leonidas J Guibas. 2016. Volumetric and multi-view cnns for object classification on 3d data. In Proceedings of the IEEE conference on computer vision and pattern recognition. 5648--5656.

[41]

J. H. Reif. 1979. Complexity of the mover's problem and generalizations. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979). 421--427.

Digital Library

[42]

Rodriguez, Xinyu Tang, Jyh-Ming Lien, and N. M. Amato. 2006. An obstacle-based rapidly-exploring random tree. In Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. 895--900.

[43]

K. Shi, J. Denny, and N. M. Amato. 2014. Spark PRM: Using RRTs within PRMs to efficiently explore narrow passages. In 2014 IEEE International Conference on Robotics and Automation (ICRA). 4659--4666.

[44]

Richard Socher, Brody Huval, Bharath Bath, Christopher D Manning, and Andrew Y Ng. 2012. Convolutional-recursive deep learning for 3d object classification. In Advances in neural information processing systems. 656--664.

[45]

Peng Song, Chi-Wing Fu, and Daniel Cohen-Or. 2012. Recursive Interlocking Puzzles. ACM Trans. Graph. 31, 6, Article 128 (Nov. 2012), 10 pages.

Digital Library

[46]

M. Strandberg. 2004. Augmenting RRT-planners with local trees. In IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004, Vol. 4. 3258--3262 Vol.4.

[47]

Hang Su, Subhransu Maji, Evangelos Kalogerakis, and Erik Learned-Miller. 2015. Multiview convolutional neural networks for 3d shape recognition. In Proceedings of the IEEE international conference on computer vision. 945--953.

Digital Library

[48]

Ioan A. Şucan, Mark Moll, and Lydia E. Kavraki. 2012. The Open Motion Planning Library. IEEE Robotics & Automation Magazine 19, 4 (December 2012), 72--82. http://ompl.kavrakilab.org.

[49]

Timothy Sun and Changxi Zheng. 2015. Computational Design of Twisty Joints and Puzzles. ACM Trans. Graph. 34, 4, Article 101 (July 2015), 11 pages.

Digital Library

[50]

Andrea Tagliasacchi, Ibraheem Alhashim, Matt Olson, and Hao Zhang. 2012. Mean Curvature Skeletons. Comput. Graph. Forum 31, 5 (Aug. 2012), 1735--1744.

Digital Library

[51]

N. Vahrenkamp, P. Kaiser, T. Asfour, and R. Dillmann. 2011. RDT+: A parameter-free algorithm for exact motion planning. In 2011 IEEE International Conference on Robotics and Automation. 715--722.

[52]

Peng-Shuai Wang, Yang Liu, Yu-Xiao Guo, Chun-Yu Sun, and Xin Tong. 2017. O-cnn: Octree-based convolutional neural networks for 3d shape analysis. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1--11.

Digital Library

[53]

Peng-Shuai Wang, Chun-Yu Sun, Yang Liu, and Xin Tong. 2018. Adaptive O-CNN: A patch-based deep representation of 3D shapes. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1--11.

Digital Library

[54]

Yunhai Wang, Shmulik Asafi, Oliver Van Kaick, Hao Zhang, Daniel Cohen-Or, and Baoquan Chen. 2012. Active co-analysis of a set of shapes. ACM Transactions on Graphics (TOG) 31, 6 (2012), 1--10.

Digital Library

[55]

S. A. Wilmarth, N. M. Amato, and P. F. Stiller. 1999. MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space. In Proceedings 1999 IEEE International Conference on Robotics and Automation, Vol. 2. 1024--1031.

[56]

S. Xin, C. Fu, and Y. He. 2012. Efficiently Computing Exact Geodesic Loops within Finite Steps. IEEE Transactions on Visualization and Computer Graphics 18, 06 (jun 2012), 879--889.

Digital Library

[57]

Shiqing Xin, Chi-Fu Lai, Chi-Wing Fu, Tien-Tsin Wong, Ying He, and Daniel Cohen-Or. 2011. Making Burr Puzzles from 3D Models. ACM Trans. Graph. 30, 4, Article 97 (July 2011), 8 pages.

Digital Library

[58]

Zhenpei Yang, Jeffrey Z Pan, Linjie Luo, Xiaowei Zhou, Kristen Grauman, and Qixing Huang. 2019. Extreme relative pose estimation for RGB-D scans via scene completion. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 4531--4540.

[59]

Fangyi Zhang, Jürgen Leitner, Michael Milford, Ben Upcroft, and Peter Corke. 2015. Towards vision-based deep reinforcement learning for robotic motion control. arXiv preprint arXiv:1511.03791 (2015).

[60]

Liangjun Zhang, Xin Huang, Young J. Kim, and Dinesh Manocha. 2008. D-Plan: Efficient Collision-Free Path Computation for Part Removal and Disassembly. Computer-Aided Design and Applications 5, 6 (2008), 774--786.

[61]

Liangjun Zhang and D. Manocha. 2008. An efficient retraction-based RRT planner. In 2008 IEEE International Conference on Robotics and Automation. 3743--3750.

[62]

Liangjun Zhang and Dinesh Manocha. 2010. Constrained Motion Interpolation with Distance Constraints. Springer Berlin Heidelberg, Berlin, Heidelberg, 367--384.

Cited By

Brandt TFierro RDanielson C(2024)Safe Vehicle Motion Planning Using Constraint Admissible Positive Invariant Sets on SE(3)IEEE Control Systems Letters10.1109/LCSYS.2024.35233858(3255-3260)Online publication date: 2024
https://doi.org/10.1109/LCSYS.2024.3523385
Brandt TFierro RDanielson C(2024)Safe Motion Planning for Serial-Chain Robotic Manipulators via Invariant SetsIEEE Control Systems Letters10.1109/LCSYS.2023.33471768(49-54)Online publication date: 2024
https://doi.org/10.1109/LCSYS.2023.3347176
Livnat DBilevich MHalperin D(2024)Tight Motion Planning by Riemannian Optimization for Sliding and Rolling with Finite Number of Contact Points2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611716(14333-14340)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611716
Show More Cited By

Index Terms

C-Space tunnel discovery for puzzle path planning
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
      1. Motion path planning
  2. Machine learning
    1. Machine learning approaches
      1. Neural networks

Recommendations

Space-filling forest for multi-goal path planning
2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)
In multi-goal path planning, the task is to find a sequence to visit a set of target locations in an environment. The combinatorial part of the problem (finding the sequence) can be solved as an instance of Traveling Salesman Problem, which requires ...
Sampling-based path planning on configuration-space costmaps

This paper addresses path planning to consider a cost function defined over the configuration space. The proposed planner computes low-cost paths that follow valleys and saddle points of the configuration-space costmap. It combines the exploratory ...
K-Order Surrounding Roadmaps Path Planner for Robot Path Planning

Probabilistic roadmaps are commonly used in robot path planning. Most sampling-based path planners often produce poor-quality roadmaps as they focus on improving the speed of constructing roadmaps without paying much attention to the quality. Poor-...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 39, Issue 4

August 2020

1732 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3386569

Editor:
Szymon Rusinkiewicz
Princeton University

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 August 2020

Published in TOG Volume 39, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

sampling strategies

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
428
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Brandt TFierro RDanielson C(2024)Safe Vehicle Motion Planning Using Constraint Admissible Positive Invariant Sets on SE(3)IEEE Control Systems Letters10.1109/LCSYS.2024.35233858(3255-3260)Online publication date: 2024
https://doi.org/10.1109/LCSYS.2024.3523385
Brandt TFierro RDanielson C(2024)Safe Motion Planning for Serial-Chain Robotic Manipulators via Invariant SetsIEEE Control Systems Letters10.1109/LCSYS.2023.33471768(49-54)Online publication date: 2024
https://doi.org/10.1109/LCSYS.2023.3347176
Livnat DBilevich MHalperin D(2024)Tight Motion Planning by Riemannian Optimization for Sliding and Rolling with Finite Number of Contact Points2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611716(14333-14340)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611716
Tian YWillis KAl Omari BLuo JMa PLi YJavid FGu EJacob JSueda SLi HChitta SMatusik W(2024)ASAP: Automated Sequence Planning for Complex Robotic Assembly with Physical Feasibility2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611595(4380-4386)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611595
Cui QRong VChen DMatusik W(2023)Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D ObjectsACM Transactions on Graphics10.1145/359212642:4(1-14)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592126
Danielson C(2023)Invariant Configuration-Space Bubbles for Revolute Serial-Chain RobotsIEEE Control Systems Letters10.1109/LCSYS.2022.32246857(745-750)Online publication date: 2023
https://doi.org/10.1109/LCSYS.2022.3224685
Zhou LDing JFan X(2023)An Adaptive RRT Algorithm Based on Narrow Passage Recognition for Assembly Path Planning2023 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM)10.1109/IEEM58616.2023.10406335(0203-0208)Online publication date: 18-Dec-2023
https://doi.org/10.1109/IEEM58616.2023.10406335
Tian YXu JLi YLuo JSueda SLi HWillis KMatusik W(2022)Assemble Them AllACM Transactions on Graphics10.1145/3550454.355552541:6(1-11)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555525
Hegewald RWolpert NSchömer E(2022)Iterative Mesh Modification Planning: A new Method for Automatic Disassembly Planning of Complex Industrial Components2022 International Conference on Robotics and Automation (ICRA)10.1109/ICRA46639.2022.9812116(336-342)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.1109/ICRA46639.2022.9812116
Song P(2022)Interlocking assemblies: Applications and methodsMaterials Today: Proceedings10.1016/j.matpr.2022.08.54870(78-82)Online publication date: 2022
https://doi.org/10.1016/j.matpr.2022.08.548
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents