{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:06:24Z","timestamp":1758823584362,"version":"3.38.0"},"reference-count":44,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2011,12,21]],"date-time":"2011-12-21T00:00:00Z","timestamp":1324425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p> Many problems in robot motion planning involve collision testing a set of local paths. In this paper we propose a novel solution to this problem by exploiting the structure of paths and the outcome of previous collision tests. Our approach circumvents expensive collision tests on a given path by detecting that the entire geometry of the path has effectively already been tested on a combination of other paths. We define a homotopy-like equivalence relation among local paths to detect this condition, and we provide algorithms that (1) classify paths based on equivalence, and (2) circumvent collision testing on up to 90% of them. We then prove both correctness and completeness of these algorithms and provide experimental results demonstrating a performance increase up to 300% in the rate of path tests. Additionally, we apply our equivalence relation to the navigation problem in a planning algorithm that takes advantage of information gained from equivalence relationships among collision-free paths. Finally, we explore applications of path equivalence to several other mechanisms, including kinematic chains and medical steerable needles. <\/jats:p>","DOI":"10.1177\/0278364911430418","type":"journal-article","created":{"date-parts":[[2011,12,22]],"date-time":"2011-12-22T01:54:40Z","timestamp":1324518880000},"page":"167-186","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":26,"title":["Toward a deeper understanding of motion alternatives via an equivalence relation on local paths"],"prefix":"10.1177","volume":"31","author":[{"given":"Ross A","family":"Knepper","sequence":"first","affiliation":[{"name":"Computer Science and Artificial Intelligence Lab, Massachusetts Institute of Technology, Cambridge, USA"}]},{"given":"Siddhartha S","family":"Srinivasa","sequence":"additional","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsurgh, USA"}]},{"given":"Matthew T","family":"Mason","sequence":"additional","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsurgh, USA"}]}],"member":"179","published-online":{"date-parts":[[2011,12,21]]},"reference":[{"volume-title":"Proceedings of the Australasian Conference on Robotics and Automation","year":"2007","author":"Allen T","key":"bibr1-0278364911430418"},{"key":"bibr2-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908097661"},{"key":"bibr3-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891837"},{"volume-title":"Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence","year":"2010","author":"Bhattacharya S","key":"bibr4-0278364911430418"},{"key":"bibr5-0278364911430418","first-page":"362","volume-title":"Proceedings of the Symposium on Models for the Perception of Speech and Visual Form","author":"Blum H","year":"1967"},{"key":"bibr6-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/70.88137"},{"key":"bibr7-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1177\/0278364902021012002"},{"key":"bibr8-0278364911430418","first-page":"31","volume":"16","author":"Buhmann J","year":"1995","journal-title":"AI Magazine"},{"key":"bibr9-0278364911430418","first-page":"1649","volume-title":"Proceedings of the International Conference on Robotics and Automation","author":"Choset H","year":"1995"},{"key":"bibr10-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1007\/11008941_10"},{"key":"bibr11-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-0760-9"},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence","year":"2007","author":"Gardiol NH","key":"bibr12-0278364911430418"},{"volume-title":"Proceedings of the Thirteenth International Symposium of Robotics Research","year":"2007","author":"Green C","key":"bibr13-0278364911430418"},{"key":"bibr14-0278364911430418","volume":"1","author":"Henrikson J","year":"1999","journal-title":"MIT Undergraduate Journal of Mathematics"},{"key":"bibr15-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908098411"},{"key":"bibr16-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.509171"},{"key":"bibr17-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906065543"},{"key":"bibr18-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1985.1087247"},{"volume-title":"Proceedings of the International Symposium on Experimental Robotics","year":"2008","author":"Knepper RA","key":"bibr19-0278364911430418"},{"key":"bibr20-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2009.5152696"},{"key":"bibr21-0278364911430418","unstructured":"Knepper RA, Srinivasa SS, Mason MT (2010a) Curvature bounds on the weighted Voronoi diagram of two proximal paths with shape constraints. Technical Report CMU-RI-TR-10-25. Robotics Institute, Carnegie Mellon University."},{"key":"bibr22-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509669"},{"key":"bibr23-0278364911430418","first-page":"346","volume-title":"Proceedings of the International Conference on Intelligent Autonomous Systems","author":"Laumond JP","year":"1986"},{"key":"bibr24-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045481"},{"key":"bibr25-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"bibr26-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840369"},{"key":"bibr27-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509725"},{"key":"bibr28-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/IEMBS.2007.4352899"},{"volume-title":"Topology","year":"2000","author":"Munkres JR","key":"bibr29-0278364911430418"},{"key":"bibr30-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970081"},{"key":"bibr31-0278364911430418","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1990.145.367"},{"key":"bibr32-0278364911430418","first-page":"49","volume-title":"Third International Workshop on Algorithmic Foundations of Robotics","author":"Reif J","year":"1998"},{"key":"bibr33-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1007\/s003660170004"},{"key":"bibr34-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556458"},{"key":"bibr35-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/IRDS.2002.1041613"},{"key":"bibr36-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45058-0_3"},{"key":"bibr37-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.511023"},{"key":"bibr38-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.1991.261477"},{"key":"bibr39-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/OCEANS.1984.1152243"},{"key":"bibr40-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17452-0_22"},{"key":"bibr41-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1109\/70.781973"},{"key":"bibr42-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906065388"},{"key":"bibr43-0278364911430418","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187890"},{"key":"bibr44-0278364911430418","first-page":"306","volume-title":"Proceedings of the International Symposium on Robotics","author":"Yu Y","year":"2000"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364911430418","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364911430418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T11:11:17Z","timestamp":1740827477000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364911430418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,21]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1177\/0278364911430418"],"URL":"https:\/\/doi.org\/10.1177\/0278364911430418","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[2011,12,21]]}}}