{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T20:26:11Z","timestamp":1747254371306,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T00:00:00Z","timestamp":1608681600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T00:00:00Z","timestamp":1608681600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 degli Studi di Roma La Sapienza"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Robot"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Consider the problem of planning collision-free motion of <jats:italic>n<\/jats:italic> objects movable through contact with a robot that can autonomously translate in the plane and that can move a maximum of <jats:inline-formula><jats:alternatives><jats:tex-math>$$m \\le n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> objects simultaneously. This represents the abstract formulation of a general class of manipulation planning problems that are proven to be decidable in this paper. The tools used for proving decidability of this simplified manipulation planning problem are, in fact, general enough to handle the decidability problem for the wider class of systems characterized by a stratified configuration space. These include, e.g., problems of legged and multi-contact locomotion, bi-manual manipulation. In addition, the approach described does not restrict the dynamics of the manipulation system modeled.\n<\/jats:p>","DOI":"10.1007\/s10514-020-09957-2","type":"journal-article","created":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T13:03:26Z","timestamp":1608728606000},"page":"679-692","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Decidability in robot manipulation planning"],"prefix":"10.1007","volume":"45","author":[{"given":"Marilena","family":"Vendittelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0757-2912","authenticated-orcid":false,"given":"Andrea","family":"Cristofaro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Paul","family":"Laumond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bud","family":"Mishra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,12,23]]},"reference":[{"key":"9957_CR1","unstructured":"Alami, R., Simeon, T., & Laumond, J. P. (1989). A geometrical approach to planning manipulation tasks. The case of discrete placements and grasps. In The fifth international symposium on robotics research, Tokyo, JPN."},{"key":"9957_CR2","doi-asserted-by":"crossref","unstructured":"Berg, J., Stilman, M., Kuffner, J., Lin, M., & Manocha, D. (2010). Path planning among movable obstacles: A probabilistically complete approach. In G. Chirikjian, H. Choset, M. Morales, & T. Murphey (Eds.), Algorithmic foundation of robotics VIII, Springer tracts in advanced robotics (Vol. 57, pp. 599\u2013614). Berlin: Springer.","DOI":"10.1007\/978-3-642-00312-7_37"},{"issue":"1","key":"9957_CR3","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1109\/9.553690","volume":"42","author":"S Celikovsky","year":"1997","unstructured":"Celikovsky, S., & Nijmeijer, H. (1997). On the relation between local controllability and stabilizability for a class of nonlinear systems. IEEE Transactions on Automatic Control, 42(1), 90\u201394.","journal-title":"IEEE Transactions on Automatic Control"},{"key":"9957_CR4","doi-asserted-by":"crossref","unstructured":"Dacre-Wright, B., Laumond, J. P., & Alami, R. (1992). Motion planning for a robot and a movable object amidst polygonal obstacles. In 1992 IEEE international conference on robotics and automation (pp. 2475\u20132480).","DOI":"10.1109\/ROBOT.1992.220094"},{"key":"9957_CR5","doi-asserted-by":"crossref","unstructured":"Deshpande, A., Kaelbling, L.P., & Lozano-Perez, T. (2016). Decidability of semi-holonomic prehensile task and motion planning. In Algorithmic foundations of robotics XII (pp. 544\u2013559). Berlin: Springer.","DOI":"10.1007\/978-3-030-43089-4_35"},{"issue":"3","key":"9957_CR6","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1109\/9.911414","volume":"46","author":"B Goodwine","year":"2001","unstructured":"Goodwine, B., & Burdick, J. W. (2001). Controllability of kinematic control systems on stratified configuration spaces. IEEE Transactions on Automatic Control, 46(3), 358\u2013368.","journal-title":"IEEE Transactions on Automatic Control"},{"issue":"4","key":"9957_CR7","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/0308033","volume":"8","author":"GW Haynes","year":"1970","unstructured":"Haynes, G. W., & Hermes, H. (1970). Nonlinear controllability via lie theory. SIAM Journal on Control, 8(4), 450\u20130460.","journal-title":"SIAM Journal on Control"},{"issue":"6","key":"9957_CR8","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1109\/TRO.2004.829503","volume":"20","author":"C Karagoz","year":"2004","unstructured":"Karagoz, C., Bozma, H., & Koditschek, D. (2004). Feedback-based event-driven parts moving. IEEE Transactions on Robotics, 20(6), 1012\u20131018.","journal-title":"IEEE Transactions on Robotics"},{"key":"9957_CR9","doi-asserted-by":"crossref","unstructured":"Latombe, J. C. (1991). Robot motion planning. The Springer international series in engineering and computer science. Springer.","DOI":"10.1007\/978-1-4615-4022-9"},{"issue":"5","key":"9957_CR10","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1109\/70.326564","volume":"10","author":"J Laumond","year":"1994","unstructured":"Laumond, J., Jacobs, P. E., Taix, M., & Murray, R. M. (1994). A motion planner for nonholonomic mobile robots. IEEE Transactions on Robotics and Automation, 10(5), 577\u2013593.","journal-title":"IEEE Transactions on Robotics and Automation"},{"issue":"3","key":"9957_CR11","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0196-8858(83)90014-3","volume":"4","author":"JT Schwartz","year":"1983","unstructured":"Schwartz, J. T. (1983). On the \u201cpiano movers\u201d problem: II. General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4(3), 298\u2013351.","journal-title":"Advances in Applied Mathematics"},{"issue":"7\u20138","key":"9957_CR12","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1177\/0278364904045471","volume":"23","author":"T Sim\u00e9on","year":"2004","unstructured":"Sim\u00e9on, T., Laumond, J. P., Cort\u00e8s, J., & Sahbani, A. (2004). Manipulation planning with probabilistic roadmaps. The International Journal of Robotics Research, 23(7\u20138), 729\u2013746.","journal-title":"The International Journal of Robotics Research"},{"key":"9957_CR13","doi-asserted-by":"crossref","unstructured":"Vendittelli, M., Laumond, J. P., & Mishra, B. (2015). Decidability of robot manipulation planning: three disks in the plane. In Algorithmic foundations of robotics XI (pp. 641\u2013657). Springer Tracts in Advanced Robotics.","DOI":"10.1007\/978-3-319-16595-0_37"},{"issue":"1","key":"9957_CR14","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BF01530890","volume":"3","author":"G Wilfong","year":"1991","unstructured":"Wilfong, G. (1991). Motion planning in the presence of movable obstacles. Annals of Mathematics and Artificial Intelligence, 3(1), 131\u2013150.","journal-title":"Annals of Mathematics and Artificial Intelligence"}],"container-title":["Autonomous Robots"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-020-09957-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10514-020-09957-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-020-09957-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T08:17:44Z","timestamp":1626855464000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10514-020-09957-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,23]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["9957"],"URL":"https:\/\/doi.org\/10.1007\/s10514-020-09957-2","relation":{},"ISSN":["0929-5593","1573-7527"],"issn-type":[{"type":"print","value":"0929-5593"},{"type":"electronic","value":"1573-7527"}],"subject":[],"published":{"date-parts":[[2020,12,23]]},"assertion":[{"value":"15 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}