{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:33:38Z","timestamp":1764174818546},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030440503"},{"type":"electronic","value":"9783030440510"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-44051-0_2","type":"book-chapter","created":{"date-parts":[[2020,5,7]],"date-time":"2020-05-07T20:02:40Z","timestamp":1588881760000},"page":"19-35","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Free Space of Rigid Objects: Caging, Path Non-existence, and Narrow Passage Detection"],"prefix":"10.1007","author":[{"given":"Anastasiia","family":"Varava","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Frederico","family":"Carvalho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian T.","family":"Pokorny","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danica","family":"Kragic","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,8]]},"reference":[{"issue":"6","key":"2_CR1","first-page":"759","volume":"16","author":"J Barraquand","year":"1997","unstructured":"Barraquand, J., Kavraki, L., Latombe, J.-C., Motwani, R., Li, T.-Y., Raghavan, P.: A random sampling scheme for path planning. IJRR 16(6), 759\u2013774 (1997)","journal-title":"IJRR"},{"key":"2_CR2","unstructured":"Basch, J., Guibas, L.J., Hsu, D., Nguyen, A.T.: Disconnection proofs for motion planning. In: IEEE ICRA, pp. 1765\u20131772 (2001)"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Behar, E., Lien, J.-M.: Mapping the configuration space of polygons using reduced convolution. In: IEEE\/RSJ Intelligent Robots and Systems, pp. 1242\u20131248 (2013)","DOI":"10.1109\/IROS.2013.6696509"},{"issue":"1","key":"2_CR4","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/PL00009412","volume":"21","author":"H Edelsbrunner","year":"1999","unstructured":"Edelsbrunner, H.: Deformable smooth surface design. Discrete Comput. Geom. 21(1), 87\u2013115 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"2_CR5","unstructured":"Kuperberg, W.: Problems on polytopes and convex sets. In: DIMACS Workshop on Polytopes, pp. 584\u2013589 (1990)"},{"key":"2_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9","volume-title":"Robot Motion Planning","author":"J-C Latombe","year":"1991","unstructured":"Latombe, J.-C.: Robot Motion Planning. Kluwer Academic Publishers, Norwell (1991)"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1109\/TC.1983.1676196","volume":"2","author":"T Lozano-Perez","year":"1983","unstructured":"Lozano-Perez, T.: Spatial planning: a configuration space approach. IEEE Trans. Comput. 2, 108\u2013120 (1983)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"2_CR8","first-page":"508","volume":"1","author":"J Mahler","year":"2016","unstructured":"Mahler, J., Pokorny, F.T., McCarthy, Z., van der Stappen, A.F., Goldberg, K.: Energy-bounded caging: formal definition and 2-D energy lower bound algorithm based on weighted alpha shapes. IEEE RA-L 1(1), 508\u2013515 (2016)","journal-title":"IEEE RA-L"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Makita, S., Maeda, Y.: 3D multifingered caging: basic formulation and planning. In: IEEE IROS, pp. 2697\u20132702 (2008)","DOI":"10.1109\/IROS.2008.4650895"},{"issue":"4","key":"2_CR10","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1504\/IJMA.2013.058376","volume":"3","author":"S Makita","year":"2013","unstructured":"Makita, S., Okita, K., Maeda, Y.: 3D two-fingered caging for two types of objects: sufficient conditions and planning. Int. J. Mechatron. Autom. 3(4), 263\u2013277 (2013)","journal-title":"Int. J. Mechatron. Autom."},{"issue":"19\u201320","key":"2_CR11","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.1080\/01691864.2017.1371075","volume":"31","author":"S Makita","year":"2017","unstructured":"Makita, S., Wan, W.: A survey of robotic caging and its applications. Adv. Robot. 31(19\u201320), 1071\u20131085 (2017)","journal-title":"Adv. Robot."},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Makapunyo, T., Phoka, T., Pipattanasomporn, P., Niparnan, N., Sudsang, A.: Measurement framework of partial cage quality based on probabilistic motion planning. In: IEEE ICRA, pp. 1574\u20131579 (2013)","DOI":"10.1109\/ICRA.2013.6630780"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"McCarthy, Z., Bretl, T., Hutchinson, S.: Proving path non-existence using sampling and alpha shapes. In: IEEE ICRA, pp. 2563\u20132569 (2012)","DOI":"10.1109\/ICRA.2012.6225300"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1038\/nchem.1550","volume":"5","author":"T Mitra","year":"2013","unstructured":"Mitra, T., Jelfs, K.E., Schmidtmann, M., Ahmed, A., Chong, S.Y., Adams, D.J., Cooper, A.I.: Molecular shape sorting using molecular organic cages. Nat. Chem. 5, 276 (2013)","journal-title":"Nat. Chem."},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-36279-8_3","volume-title":"Algorithmic Foundations of Robotics X","author":"V Milenkovic","year":"2013","unstructured":"Milenkovic, V., Sacks, E., Trac, S.: Robust complete path planning in the plane. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds.) Algorithmic Foundations of Robotics X, pp. 37\u201352. Springer, Heidelberg (2013)"},{"key":"2_CR16","unstructured":"Pipattanasomporn, P., Sudsang, A.: Two-finger caging of concave polygon. In: IEEE ICRA, pp. 2137\u20132142 (2006)"},{"issue":"2","key":"2_CR17","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1109\/TRO.2010.2103451","volume":"27","author":"P Pipattanasomporn","year":"2011","unstructured":"Pipattanasomporn, P., Sudsang, A.: Two-finger caging of nonconvex polytopes. IEEE T-RO 27(2), 324\u2013333 (2011)","journal-title":"IEEE T-RO"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Pokorny, F.T., Stork, J.A., Kragic, D.: Grasping objects with holes: a topological approach. In: IEEE ICRA, pp. 1100\u20131107 (2013)","DOI":"10.1109\/ICRA.2013.6630710"},{"issue":"3","key":"2_CR19","first-page":"299","volume":"18","author":"E Rimon","year":"1999","unstructured":"Rimon, E., Blake, A.: Caging planar bodies by one-parameter two-fingered gripping systems. IJRR 18(3), 299\u2013318 (1999)","journal-title":"IJRR"},{"issue":"5","key":"2_CR20","doi-asserted-by":"publisher","first-page":"1177","DOI":"10.1109\/TRO.2012.2201294","volume":"28","author":"A Rodriguez","year":"2012","unstructured":"Rodriguez, A., Mason, M.T.: Path connectivity of the free space. IEEE T-RO 28(5), 1177\u20131180 (2012)","journal-title":"IEEE T-RO"},{"issue":"7","key":"2_CR21","first-page":"886","volume":"31","author":"A Rodriguez","year":"2012","unstructured":"Rodriguez, A., Mason, M.T., Ferry, S.: From caging to grasping. IJRR 31(7), 886\u2013900 (2012)","journal-title":"IJRR"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"6213","DOI":"10.1039\/C6CS00177G","volume":"45","author":"M Rother","year":"2016","unstructured":"Rother, M., Nussbaumer, M.G., Rengglic, K., Bruns, N.: Protein cages and synthetic polymers: a fruitful symbiosis for drug delivery applications, bionanotechnology and materials science. Chem. Soc. Rev. 45, 6213 (2016)","journal-title":"Chem. Soc. Rev."},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Stork, J.A., Pokorny, F.T., Kragic, D.: Integrated motion and clasp planning with virtual linking. In: IEEE\/RSJ IROS, pp. 3007\u20133014 (2013)","DOI":"10.1109\/IROS.2013.6696782"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Stork, J.A., Pokorny, F.T., Kragic, D.: A topology-based object representation for clasping, latching and hooking. In: IEEE-RAS International Conference on Humanoid Robots, pp. 138\u2013145 (2013)","DOI":"10.1109\/HUMANOIDS.2013.7029968"},{"issue":"7\u20138","key":"2_CR25","first-page":"783","volume":"23","author":"GAS Pereira","year":"2004","unstructured":"Pereira, G.A.S., Campos, M.F.M., Kumar, V.: Decentralized algorithms for multi-robot manipulation via caging. IJRR 23(7\u20138), 783\u2013795 (2004)","journal-title":"IJRR"},{"issue":"6","key":"2_CR26","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1109\/TRO.2016.2602374","volume":"32","author":"A Varava","year":"2016","unstructured":"Varava, A., Kragic, D., Pokorny, F.T.: Caging grasps of rigid and partially deformable 3-d objects with double fork and neck features. IEEE T-RO 32(6), 1479\u20131497 (2016)","journal-title":"IEEE T-RO"},{"key":"2_CR27","unstructured":"Varava, A., Carvalho, J.F., Pokorny, F.T., Kragic, D.: Caging and path non-existence: a deterministic sampling-based verification algorithm. In: ISRR (2017). Preprint: \nhttps:\/\/www.csc.kth.se\/~jfpbdc\/path_non_ex.pdf"},{"issue":"11\u201312","key":"2_CR28","first-page":"1308","volume":"27","author":"M Vahedi","year":"2008","unstructured":"Vahedi, M., van der Stappen, A.F.: Caging polygons with two and three fingers. IJRR 27(11\u201312), 1308\u20131324 (2008)","journal-title":"IJRR"},{"key":"2_CR29","unstructured":"Wang, Z., Kumar, V.: Object closure and manipulation by multiple cooperating mobile robots. In: IEEE ICRA, pp. 394\u2013399 (2002)"},{"issue":"8","key":"2_CR30","first-page":"762","volume":"19","author":"K Wise","year":"2000","unstructured":"Wise, K., Bowyer, A.: A survey of global configuration-space mapping techniques for a single robot in a static environment. IJRR 19(8), 762\u2013779 (2000)","journal-title":"IJRR"},{"issue":"11\u201312","key":"2_CR31","first-page":"1246","volume":"27","author":"L Zhang","year":"2008","unstructured":"Zhang, L., Young, J.K., Manocha, D.: Efficient cell labelling and path non-existence computation using C-obstacle query. IJRR 27(11\u201312), 1246\u20131257 (2008)","journal-title":"IJRR"},{"issue":"1","key":"2_CR32","first-page":"9","volume":"7","author":"D Zhu","year":"1991","unstructured":"Zhu, D., Latombe, J.: New heuristic algorithms for efficient hierarchical path planning. IEEE T-RO 7(1), 9\u201320 (1991)","journal-title":"IEEE T-RO"},{"key":"2_CR33","first-page":"801","volume":"29","author":"A Yershova","year":"2009","unstructured":"Yershova, A., Jain, S., LaValle, S.M., Mitchell, J.C.: Generating uniform incremental grids on SO(3) using the Hopf fibration. IJRR 29, 801\u2013812 (2009)","journal-title":"IJRR"},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"Zomorodian, A., Edelsbrunner, H.: Fast software for box intersections. In: Proceedings of the 16th Annual Symposium on Computational Geometry, pp. 129\u2013138 (2000)","DOI":"10.1145\/336154.336192"},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"Liu, J., Xin, S., Gao, Z., Xu, K., Tu, C., Chen, B.: Caging loops in shape embedding space: theory and computation. In: ICRA (2018)","DOI":"10.1109\/ICRA.2018.8461206"}],"container-title":["Springer Proceedings in Advanced Robotics","Algorithmic Foundations of Robotics XIII"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-44051-0_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,7]],"date-time":"2020-05-07T20:02:49Z","timestamp":1588881769000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-44051-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030440503","9783030440510"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-44051-0_2","relation":{},"ISSN":["2511-1256","2511-1264"],"issn-type":[{"type":"print","value":"2511-1256"},{"type":"electronic","value":"2511-1264"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"8 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAFR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on the Algorithmic Foundations of Robotics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Merida","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wafr2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/parasol.tamu.edu\/wafr\/wafr2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}