{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T13:46:54Z","timestamp":1768916814268,"version":"3.49.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T00:00:00Z","timestamp":1597190400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1910274"],"award-info":[{"award-number":["IIS-1910274"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2018-05665"],"award-info":[{"award-number":["2018-05665"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3386569.3392468","type":"journal-article","created":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T11:44:27Z","timestamp":1597232667000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["C-Space tunnel discovery for puzzle path planning"],"prefix":"10.1145","volume":"39","author":[{"given":"Xinya","family":"Zhang","sequence":"first","affiliation":[{"name":"The University of Texas at Austin"}]},{"given":"Robert","family":"Belfer","sequence":"additional","affiliation":[{"name":"McGill University"}]},{"given":"Paul G.","family":"Kry","sequence":"additional","affiliation":[{"name":"McGill University"}]},{"given":"Etienne","family":"Vouga","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin"}]}],"member":"320","published-online":{"date-parts":[[2020,8,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1998.677043"},{"key":"e_1_2_2_2_1","volume-title":"Proc. Int. Workshop on Algorithmic Foundations of Robotics (WAFR). 155--168","author":"Amato Nancy M","year":"1998","unstructured":"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."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2010.5540212"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516977"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6906594"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2015.304"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989324"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139620"},{"key":"e_1_2_2_9_1","unstructured":"Xiang Gao S\u00e9bastien 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"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.007"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3306346.3322959","article-title":"MeshCNN: a network with an edge","volume":"38","author":"Hanocka Rana","year":"2019","unstructured":"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.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000285"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2005.1570712"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141925"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","unstructured":"Brian Ichter James Harrison and Marco Pavone. 2018. Learning Sampling Distributions for Robot Motion Planning. 7087--7094. 10.1109\/ICRA.2018.8460730","DOI":"10.1109\/ICRA.2018.8460730"},{"key":"e_1_2_2_16_1","volume-title":"Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu.","author":"Jaderberg Max","year":"2016","unstructured":"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)."},{"key":"e_1_2_2_17_1","volume-title":"Deep learning for video game playing","author":"Justesen Niels","year":"2019","unstructured":"Niels Justesen, Philip Bontrager, Julian Togelius, and Sebastian Risi. 2019. Deep learning for video game playing. IEEE Transactions on Games (2019)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1833349.1778839"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980479"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"e_1_2_2_22_1","volume-title":"International Conference on Learning Representations (ICLR). https:\/\/arxiv.org\/abs\/1412","author":"Kingma Diederik P","year":"2015","unstructured":"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"},{"key":"e_1_2_2_23_1","unstructured":"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."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1308895"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824649"},{"key":"e_1_2_2_27_1","unstructured":"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."},{"key":"e_1_2_2_28_1","volume-title":"Planning algorithms","author":"LaValle Steven M","unstructured":"Steven M LaValle. 2006. Planning algorithms. Cambridge university press."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917710318"},{"key":"e_1_2_2_30_1","volume-title":"Pointcnn: Convolution on x-transformed points. In Advances in neural information processing systems. 820--830.","author":"Li Yangyan","year":"2018","unstructured":"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."},{"key":"e_1_2_2_31_1","volume-title":"Ryutarou Ohbuchi, et al.","author":"Lian Zhouhui","year":"2011","unstructured":"Zhouhui Lian, Afzal Godil, Benjamin Bustos, Mohamed Daoudi, Jeroen Hermans, Shun Kawamura, Yukinori Kurita, Guillaume Lavou\u00e9, Hien Van Nguyen, Ryutarou Ohbuchi, et al. 2011. SHREC'11 Track: Shape Retrieval on Non-rigid 3D Watertight Meshes. 3DOR 11 (2011), 79--88."},{"key":"e_1_2_2_32_1","unstructured":"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."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1618452.1618503"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980048"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46484-8_29"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364916640908"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487517"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12668"},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the IEEE conference on computer vision and pattern recognition. 652--660","author":"Qi Charles R","year":"2017","unstructured":"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."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.609"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.10"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2006.1641823"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907540"},{"key":"e_1_2_2_44_1","unstructured":"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."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366147"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1308756"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2015.114"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2012.2205651"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766961"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03178.x"},{"key":"e_1_2_2_51_1","volume-title":"2011 IEEE International Conference on Robotics and Automation. 715--722","author":"Vahrenkamp N.","unstructured":"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."},{"key":"e_1_2_2_52_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3072959.3073608","article-title":"O-cnn: Octree-based convolutional neural networks for 3d shape analysis","volume":"36","author":"Wang Peng-Shuai","year":"2017","unstructured":"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.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_53_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3272127.3275050","article-title":"Adaptive O-CNN: A patch-based deep representation of 3D shapes","volume":"37","author":"Wang Peng-Shuai","year":"2018","unstructured":"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.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366184"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1999.772448"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.119"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964992"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00466"},{"key":"e_1_2_2_59_1","volume-title":"Towards vision-based deep reinforcement learning for robotic motion control. arXiv preprint arXiv:1511.03791","author":"Zhang Fangyi","year":"2015","unstructured":"Fangyi Zhang, J\u00fcrgen 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)."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.3722\/cadaps.2008.774-786"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2008.4543785"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00312-7_23"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386569.3392468","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3386569.3392468","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T05:39:39Z","timestamp":1750829979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386569.3392468"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,12]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3386569.3392468"],"URL":"https:\/\/doi.org\/10.1145\/3386569.3392468","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,12]]},"assertion":[{"value":"2020-08-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}