{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:59:32Z","timestamp":1777715972283,"version":"3.51.4"},"reference-count":29,"publisher":"SAGE Publications","issue":"7","license":[{"start":{"date-parts":[[2009,10,22]],"date-time":"2009-10-22T00:00:00Z","timestamp":1256169600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p>Motion planning problems encountered in manipulation and legged locomotion have a distinctive multi-modal structure, where the space of feasible configurations consists of intersecting submanifolds, often of different dimensionalities. Such a feasible space does not possess expansiveness, a property that characterizes whether planning queries can be solved efficiently with traditional probabilistic roadmap (PRM) planners. In this paper we present a new PRM-based multi-modal planning algorithm for problems where the number of intersecting manifolds is finite. We also analyze the completeness properties of this algorithm. More specifically, we show that the algorithm converges quickly when each submanifold is individually expansive and establish a bound on the expected running time in that case. We also present an incremental variant of the algorithm that has the same convergence properties, but works better for problems with a large number of submanifolds by considering subsets of submanifolds likely to contain a solution path. These algorithms are demonstrated in geometric examples and in a legged locomotion planner.<\/jats:p>","DOI":"10.1177\/0278364909352098","type":"journal-article","created":{"date-parts":[[2009,10,22]],"date-time":"2009-10-22T20:55:34Z","timestamp":1256244934000},"page":"897-915","source":"Crossref","is-referenced-by-count":85,"title":["Multi-modal Motion Planning in Non-expansive Spaces"],"prefix":"10.1177","volume":"29","author":[{"given":"Kris","family":"Hauser","sequence":"first","affiliation":[{"name":"Indiana University Lindley Hall, Room 215, Bloomington, IN 47405-7104, USA,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Claude","family":"Latombe","sequence":"additional","affiliation":[{"name":"Stanford University Clark Center, Room S244 Stanford, CA 94305, USA,"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2009,10,22]]},"reference":[{"key":"atypb1","volume-title":"International Symposium on Robotics Research","author":"Akinc, M."},{"key":"atypb2","unstructured":"Alami, R., Laumond, J.P. and Sim\u00e9on, T. ( 1995). Two manipulation planning algorithms. Algorithmic Foundations of Robotics, Goldberg, K., Halperin, D., Latombe, J.C. and Wilson, R. (eds). Wellesley, MA, A K Peters, pp. 109-125."},{"key":"atypb3","volume-title":"International Conference on Robotics and Automation","author":"Boor, V."},{"key":"atypb4","volume-title":"Workshop on the Algorithmic Foundations of Robotics","author":"Bretl, T."},{"key":"atypb5","volume-title":"Fourth SIAM Conference of Analytic Algorithms and Computational Geometry","author":"Chaudhuri, S."},{"key":"atypb6","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"Choset, H.","year":"2005"},{"key":"atypb7","volume-title":"Workshop on the Algorithmic Foundations of Robotics","author":"Cort\u00e9s, J."},{"key":"atypb8","volume-title":"IEEE International Conference on Robotics and Automation","author":"Hauser, K."},{"key":"atypb9","volume-title":"IEEE International Conference on Humanoid Robots","author":"Hauser, K."},{"issue":"11","key":"atypb10","first-page":"1325","volume":"27","author":"Hauser, K.","year":"2006","journal-title":"The International Journal of Robotics Research"},{"key":"atypb11","volume-title":"International Symposium on Robotics Research","author":"Hauser, K."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"atypb13","volume-title":"Workshop on the Algorithmic Foundations of Robotics","author":"Hsu, D."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556421"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906067174"},{"key":"atypb16","volume-title":"IEEE International Conference on Robotics and Automation","author":"Hsu, D."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000285"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1578"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb20","volume-title":"IEEE International Conference on Robotics and Automation","author":"Koga, Y."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"atypb22","volume-title":"IEEE International Conference on Robotics and Automation","author":"LaValle, S.M."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2000.895219"},{"key":"atypb24","volume-title":"Workshop on the Algorithmic Foundations of Robotics","author":"Nieuwenhuisen, D."},{"key":"atypb25","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Sahbani, A."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556458"},{"key":"atypb27","volume-title":"Navigation Among Movable Obstacles. PhD thesis","author":"Stilman, M.","year":"2007"},{"key":"atypb28","volume-title":"Workshop on the Algorithmic Foundations of Robotics","author":"van den Berg, J."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20193"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364909352098","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364909352098","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:02Z","timestamp":1777457822000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364909352098"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,22]]},"references-count":29,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1177\/0278364909352098"],"URL":"https:\/\/doi.org\/10.1177\/0278364909352098","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,22]]}}}