{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T06:10:01Z","timestamp":1751091001468,"version":"3.41.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T00:00:00Z","timestamp":1746662400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T00:00:00Z","timestamp":1746662400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006302","name":"Universidad de Alcal\u00e1","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006302","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Robot"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study the problem of determining minimum-length coordinated motions for two axis-aligned square robots translating in an obstacle-free plane: Given feasible start and goal configurations (feasible in the sense that the two squares are interior disjoint), find a continuous motion for the two squares from start to goal, comprising only robot-robot collision-free configurations, such that the total Euclidean distance traveled by the two squares is minimal among all possible such motions. In this paper we present an adaptation of the tools developed for the case of disks to the case of squares. We show that in certain aspects the case of squares is more complicated, requiring additional and more involved arguments over the case of disks.\n<\/jats:p>","DOI":"10.1007\/s10514-025-10198-4","type":"journal-article","created":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T13:40:37Z","timestamp":1746711637000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Shortest coordinated motions for square robots"],"prefix":"10.1007","volume":"49","author":[{"given":"Guillermo","family":"Esteban","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodrigo I.","family":"Silveira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,8]]},"reference":[{"key":"10198_CR1","first-page":"1","volume-title":"Algorithmic foundations of robotics XI","author":"A Adler","year":"2015","unstructured":"Adler, A., de Berg, M., Halperin, D., & Solovey, K. (2015). Efficient multi-robot motion planning for unlabeled discs in simple polygons. In H. L. Akin, N. M. Amato, V. Isler, & A. F. van der Stappen (Eds.), Algorithmic foundations of robotics XI (pp. 1\u201317). Springer."},{"key":"10198_CR2","doi-asserted-by":"publisher","first-page":"102019","DOI":"10.1016\/j.comgeo.2023.102019","volume":"114","author":"PK Agarwal","year":"2023","unstructured":"Agarwal, P. K., Geft, T., Halperin, D., & Taylor, E. (2023). Multi-robot motion planning for unit discs with revolving areas. Computational Geometry, 114, 102019.","journal-title":"Computational Geometry"},{"key":"10198_CR3","doi-asserted-by":"crossref","unstructured":"Agarwal, P. K., Halperin, D., Sharir, M., & Steiger, A. (2024). Near-optimal min-sum motion planning for two square robots in a polygonal environment. In Proceedings of the 2024 annual ACM-SIAM symposium on discrete algorithms (pp. 4942\u20134962).","DOI":"10.1137\/1.9781611977912.176"},{"key":"10198_CR4","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/BF02574371","volume":"12","author":"B Aronov","year":"1994","unstructured":"Aronov, B., & Sharir, M. (1994). Castles in the air revisited. Discrete Computational Geometry, 12, 119\u2013150.","journal-title":"Discrete Computational Geometry"},{"key":"10198_CR5","unstructured":"Banyassady, B., de\u00a0Berg, M., Bringmann, K., Buchin, K., Fernau, H., Halperin, D., Kostitsyna, I., Okamoto, Y., & Slot, S. (2022). Unlabeled multi-robot motion planning with tighter separation bounds. In X.\u00a0Goaoc and M.\u00a0Kerber (Eds.), 38th International Symposium on Computational Geometry, volume 224 of LIPIcs (pp. 12:1\u201312:16). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik."},{"key":"10198_CR6","doi-asserted-by":"crossref","unstructured":"Canny, J. F., & Reif, J. H. (1987). New lower bound techniques for robot motion planning problems. In 28th Annual symposium on foundations of computer science (pp. 49\u201360). IEEE Computer Society.","DOI":"10.1109\/SFCS.1987.42"},{"key":"10198_CR7","volume-title":"Principles of robot motion: Theory, algorithms, and implementation","author":"H Choset","year":"2005","unstructured":"Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., & Thrun, S. (2005). Principles of robot motion: Theory, algorithms, and implementation. MIT Press."},{"key":"10198_CR8","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/2372560","volume":"79","author":"LE Dubins","year":"1957","unstructured":"Dubins, L. E. (1957). On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 79, 497\u2013516.","journal-title":"American Journal of Mathematics"},{"key":"10198_CR9","doi-asserted-by":"crossref","unstructured":"Eggleston, H. G. (1966). Convexity.","DOI":"10.1112\/jlms\/s1-41.1.183b"},{"key":"10198_CR10","doi-asserted-by":"crossref","unstructured":"Esteban, G., Halperin, D., Ru\u00edz, V., Sacrist\u00e1n, V., & Silveira, R. I. (2023). Shortest coordinated motion for square robots. In Algorithms and data structures symposium (pp. 430\u2013443). Springer.","DOI":"10.1007\/978-3-031-38906-1_28"},{"key":"10198_CR11","first-page":"1343","volume-title":"Handbook of discrete and computational geometry, chapter 51","author":"D Halperin","year":"2018","unstructured":"Halperin, D., Kavraki, L., & Solovey, K. (2018). Robotics. In J. E. Goodman, J. O\u2019Rourke, & C. T\u00f3th (Eds.), Handbook of discrete and computational geometry, chapter 51 (3rd ed., pp. 1343\u20131376). Chapman & Hall\/CRC.","edition":"3"},{"key":"10198_CR12","first-page":"1311","volume-title":"Handbook of discrete and computational geometry, chapter\u00a050","author":"D Halperin","year":"2018","unstructured":"Halperin, D., Slazman, O., & Sharir, M. (2018). Algorithmic motion planning. In J. E. Goodman, J. O\u2019Rourke, & C. T\u00f3th (Eds.), Handbook of discrete and computational geometry, chapter\u00a050 (3rd ed., pp. 1311\u20131342). Chapman & Hall\/CRC.","edition":"3"},{"issue":"2","key":"10198_CR13","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/BF01891839","volume":"10","author":"C Icking","year":"1993","unstructured":"Icking, C., Rote, G., Welzl, E., & Yap, C. (1993). Shortest paths for line segments. Algorithmica, 10(2), 182\u2013200.","journal-title":"Algorithmica"},{"issue":"7","key":"10198_CR14","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1177\/0278364911406761","volume":"30","author":"S Karaman","year":"2011","unstructured":"Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research, 30(7), 846\u2013894.","journal-title":"International Journal of Robotics Research"},{"key":"10198_CR15","doi-asserted-by":"crossref","unstructured":"Kavraki, L. E., Kolountzakis, M. N., & Latombe, J. (1996). Analysis of probabilistic roadmaps for path planning. In Proceedings of the 1996 IEEE international conference on robotics and automation (pp. 3020\u20133025). IEEE.","DOI":"10.1109\/ROBOT.1996.509171"},{"key":"10198_CR16","unstructured":"Kirkpatrick, D. G., & Liu, P. (2016). Characterizing minimum-length coordinated motions for two discs. CoRR, arxiv:1607.04005"},{"key":"10198_CR17","unstructured":"Kirkpatrick, D. G., & Liu, P. (2016). Characterizing minimum-length coordinated motions for two discs. In Proceedings of the 28th Canadian conference on computational geometry (pp. 252\u2013259)."},{"issue":"2","key":"10198_CR18","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1109\/LRA.2018.2888947","volume":"4","author":"M Kleinbort","year":"2019","unstructured":"Kleinbort, M., Solovey, K., Littlefield, Z., Bekris, K. E., & Halperin, D. (2019). Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation. IEEE Robotics and Automation Letters, 4(2), 277\u2013283.","journal-title":"IEEE Robotics and Automation Letters"},{"key":"10198_CR19","doi-asserted-by":"crossref","unstructured":"Kleinbort, M., Solovey, K., Littlefield, Z., Bekris, K. E., & Halperin, D. (2023). Corrections to Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation\u2019. IEEE Robotics and Automation Letters, 8(2), 1149\u20131150.","DOI":"10.1109\/LRA.2023.3236496"},{"key":"10198_CR20","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. (1991). Robot motion planning. Kluwer."},{"issue":"11","key":"10198_CR21","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1177\/02783649922067753","volume":"18","author":"J-C Latombe","year":"1999","unstructured":"Latombe, J.-C. (1999). Motion planning: A journey of robots, molecules, digital actors, and other artifacts. International Journal of Robotics Research, 18(11), 1119\u20131128.","journal-title":"International Journal of Robotics Research"},{"key":"10198_CR22","doi-asserted-by":"crossref","unstructured":"LaValle, S. M. (2006). Planning algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511546877"},{"key":"10198_CR23","volume-title":"Lectures on discrete geometry","author":"J Matousek","year":"2013","unstructured":"Matousek, J. (2013). Lectures on discrete geometry (Vol. 212). Springer Science & Business Media."},{"key":"10198_CR24","first-page":"811","volume-title":"Handbook of discrete and computational geometry, chapter\u00a031","author":"JSB Mitchell","year":"2018","unstructured":"Mitchell, J. S. B. (2018). Shortest paths and networks. In J. E. Goodman, J. O\u2019Rourke, & C. T\u00f3th (Eds.), Handbook of discrete and computational geometry, chapter\u00a031 (3rd ed., pp. 811\u2013848). Chapman & Hall\/CRC.","edition":"3"},{"key":"10198_CR25","doi-asserted-by":"crossref","unstructured":"Orthey, A., Chamzas, C., & Kavraki, L. E. (2023). Sampling-based motion planning: A comparative review.","DOI":"10.1146\/annurev-control-061623-094742"},{"issue":"2","key":"10198_CR26","doi-asserted-by":"publisher","first-page":"367","DOI":"10.2140\/pjm.1990.145.367","volume":"145","author":"JA Reeds","year":"1990","unstructured":"Reeds, J. A., & Shepp, L. A. (1990). Optimal paths for a car that goes both forwards and backwards. Pacific Journal of Mathematics, 145(2), 367\u2013393.","journal-title":"Pacific Journal of Mathematics"},{"issue":"10","key":"10198_CR27","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1145\/3318164","volume":"62","author":"O Salzman","year":"2019","unstructured":"Salzman, O. (2019). Sampling-based robot motion planning. Communications of the ACM, 62(10), 54\u201363.","journal-title":"Communications of the ACM"},{"issue":"1","key":"10198_CR28","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF01530889","volume":"3","author":"M Sharir","year":"1991","unstructured":"Sharir, M., & Sifrony, S. (1991). Coordinated motion planning for two independent robots. Annals of Mathematics and Artificial Intelligence, 3(1), 107\u2013130.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"14","key":"10198_CR29","doi-asserted-by":"publisher","first-page":"1750","DOI":"10.1177\/0278364916672311","volume":"35","author":"K Solovey","year":"2016","unstructured":"Solovey, K., & Halperin, D. (2016). On the hardness of unlabeled multi-robot motion planning. International Journal of Robotics Research, 35(14), 1750\u20131759.","journal-title":"International Journal of Robotics Research"},{"key":"10198_CR30","doi-asserted-by":"crossref","unstructured":"Solovey, K., Janson, L., Schmerling, E., Frazzoli, E., & Pavone, M. (2020). Revisiting the asymptotic optimality of RRT. In 2020 IEEE international conference on robotics and automation (pp. 2189\u20132195). IEEE.","DOI":"10.1109\/ICRA40945.2020.9196553"},{"key":"10198_CR31","volume-title":"Robotics: Science and systems XI","author":"K Solovey","year":"2015","unstructured":"Solovey, K., Yu, J., Zamir, O., & Halperin, D. (2015). Motion planning for unlabeled discs with optimality guarantees. In L. E. Kavraki, D. Hsu, & J. Buchli (Eds.), Robotics: Science and systems XI. MIT Press."}],"container-title":["Autonomous Robots"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-025-10198-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10514-025-10198-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-025-10198-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T05:31:44Z","timestamp":1751088704000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10514-025-10198-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,8]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10198"],"URL":"https:\/\/doi.org\/10.1007\/s10514-025-10198-4","relation":{},"ISSN":["0929-5593","1573-7527"],"issn-type":[{"type":"print","value":"0929-5593"},{"type":"electronic","value":"1573-7527"}],"subject":[],"published":{"date-parts":[[2025,5,8]]},"assertion":[{"value":"25 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Non applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical statements"}}],"article-number":"14"}}