{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T09:12:03Z","timestamp":1779268323418,"version":"3.51.4"},"reference-count":41,"publisher":"SAGE Publications","issue":"10-11","license":[{"start":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T00:00:00Z","timestamp":1594080000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p>In this work, we propose algorithms to explicitly construct a conservative estimate of the configuration spaces of rigid objects in two and three dimensions. Our approach is able to detect compact path components and narrow passages in configuration space which are important for applications in robotic manipulation and path planning. Moreover, as we demonstrate, they are also applicable to identification of molecular cages in chemistry. Our algorithms are based on a decomposition of the resulting three- and six-dimensional configuration spaces into slices corresponding to a finite sample of fixed orientations in configuration space. We utilize dual diagrams of unions of balls and uniform grids of orientations to approximate the configuration space. Furthermore, we carry out experiments to evaluate the computational efficiency on a set of objects with different geometric features thus demonstrating that our approach is applicable to different object shapes. We investigate the performance of our algorithm by computing increasingly fine-grained approximations of the object\u2019s configuration space. A multithreaded implementation of our approach is shown to result in significant speed improvements.<\/jats:p>","DOI":"10.1177\/0278364920932996","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T05:17:53Z","timestamp":1594099073000},"page":"1049-1067","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":9,"title":["Free space of rigid objects: caging, path non-existence, and narrow passage detection"],"prefix":"10.1177","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0900-1523","authenticated-orcid":false,"given":"Anastasiia","family":"Varava","sequence":"first","affiliation":[{"name":"Robotics, Perception, and Learning, KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8750-0897","authenticated-orcid":false,"given":"J. Frederico","family":"Carvalho","sequence":"additional","affiliation":[{"name":"Robotics, Perception, and Learning, KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danica","family":"Kragic","sequence":"additional","affiliation":[{"name":"Robotics, Perception, and Learning, KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian T.","family":"Pokorny","sequence":"additional","affiliation":[{"name":"Robotics, Perception, and Learning, KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2020,7,7]]},"reference":[{"key":"bibr1-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(84)90064-5"},{"key":"bibr2-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1177\/027836499701600604"},{"key":"bibr3-0278364920932996","first-page":"1765","volume":"2","author":"Basch J","year":"2001","journal-title":"IEEE International Conference on Robotics and Automation"},{"key":"bibr4-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696509"},{"key":"bibr5-0278364920932996","first-page":"356","author":"Dey TK","year":"2012","journal-title":"Proceedings of the seventh ACM symposium on Solid modeling and applications"},{"key":"bibr6-0278364920932996","first-page":"21","author":"Dey TK","year":"2006","journal-title":"International Conference on Foundations of Software Technology and Theoretical Computer Science"},{"key":"bibr7-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009412"},{"key":"bibr8-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1145\/282918.282923"},{"key":"bibr9-0278364920932996","first-page":"584","author":"Kuperberg W","year":"1990","journal-title":"DIMACS Workshop on polytopes"},{"key":"bibr10-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"bibr11-0278364920932996","first-page":"1","author":"Liu J","year":"2018","journal-title":"IEEE International Conference on Robotics and Automation (ICRA)"},{"key":"bibr12-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8997-2_20"},{"key":"bibr13-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2016.2519145"},{"key":"bibr14-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2018.2831724"},{"key":"bibr15-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2008.4650895"},{"key":"bibr16-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1504\/IJMA.2013.058376"},{"key":"bibr17-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1080\/01691864.2017.1371075"},{"key":"bibr18-0278364920932996","first-page":"1574","author":"Makapunyo T","year":"2013","journal-title":"IEEE International Conference on Robotics and Automation"},{"key":"bibr19-0278364920932996","first-page":"2563","author":"McCarthy Z","year":"2012","journal-title":"IEEE International Conference on Robotics and Automation"},{"key":"bibr20-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36279-8_3"},{"key":"bibr21-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1038\/nchem.1550"},{"key":"bibr22-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045477"},{"key":"bibr23-0278364920932996","first-page":"2137","author":"Pipattanasomporn P","year":"2006","journal-title":"Proceedings IEEE International Conference on Robotics and Automation"},{"key":"bibr24-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2010.2103451"},{"key":"bibr25-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630710"},{"key":"bibr26-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1177\/02783649922066222"},{"key":"bibr27-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2012.2201294"},{"key":"bibr28-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912442972"},{"key":"bibr29-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1039\/C6CS00177G"},{"key":"bibr30-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696782"},{"key":"bibr31-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908098485"},{"key":"bibr32-0278364920932996","author":"Varava A","year":"2017","journal-title":"International Symposium on Robotics Research"},{"key":"bibr33-0278364920932996","author":"Varava A","year":"2018","journal-title":"Workshop on Algorithmic Foundations of Robotics"},{"key":"bibr34-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2602374"},{"key":"bibr35-0278364920932996","first-page":"97","volume":"133","author":"Voronoi G","year":"1907","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"bibr36-0278364920932996","first-page":"394","author":"Wang Z","year":"2002","journal-title":"Proceedings IEEE International Conference on Robotics and Automation"},{"key":"bibr37-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1177\/02783640022067157"},{"key":"bibr38-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909352700"},{"key":"bibr39-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908099216"},{"key":"bibr40-0278364920932996","doi-asserted-by":"publisher","DOI":"10.1109\/70.68066"},{"issue":"1","key":"bibr41-0278364920932996","first-page":"143","volume":"12","author":"Zomorodian A","year":"2000","journal-title":"International Journal of Computational Geometry and Applications"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920932996","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364920932996","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920932996","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:41Z","timestamp":1777457801000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364920932996"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,7]]},"references-count":41,"journal-issue":{"issue":"10-11","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["10.1177\/0278364920932996"],"URL":"https:\/\/doi.org\/10.1177\/0278364920932996","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,7]]}}}