{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:16:11Z","timestamp":1740122171770,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T00:00:00Z","timestamp":1722988800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T00:00:00Z","timestamp":1722988800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FE 407\/22-1","SCHE 1931\/4-1"],"award-info":[{"award-number":["FE 407\/22-1","SCHE 1931\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004871","name":"Technische Universit\u00e4t Braunschweig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004871","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>When considering motion planning for a swarm of <jats:italic>n<\/jats:italic> labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, collision-free moves. The objective is to reach the new configuration in a minimum amount of time. Problems of this type have been considered before, with recent notable results achieving <jats:italic>constant stretch<\/jats:italic> for parallel reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of <jats:italic>d<\/jats:italic>, the total duration of an overall schedule can be bounded to\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(d)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is optimal up to constant factors. An important constraint for coordinated reconfiguration is to keep the swarm connected after each time step. In previous work, constant stretch could only be achieved if <jats:italic>disconnected<\/jats:italic> reconfiguration is allowed, or for scaled configurations of <jats:italic>unlabeled<\/jats:italic> robots; on the other hand, the existence of non-constant lower bounds on the stretch factor was unknown. We resolve these major open problems by (1)\u00a0establishing a lower bound of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega (\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected, labeled reconfiguration can be achieved. In addition, we show that (3) it is -complete to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a schedule of makespan 1 exists.<\/jats:p>","DOI":"10.1007\/s10458-024-09668-3","type":"journal-article","created":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:02:27Z","timestamp":1723014147000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficiently reconfiguring a connected swarm of labeled robots"],"prefix":"10.1007","volume":"38","author":[{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Kramer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Rieck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheffer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arne","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,7]]},"reference":[{"issue":"4","key":"9668_CR1","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1109\/TASE.2015.2470096","volume":"12","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. IEEE Transactions on Automation Science and Engineering, 12(4), 1309\u20131317. https:\/\/doi.org\/10.1109\/TASE.2015.2470096","journal-title":"IEEE Transactions on Automation Science and Engineering"},{"key":"9668_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: Theory & Applications, 114, 102019. https:\/\/doi.org\/10.1016\/J.COMGEO.2023.102019","journal-title":"Computational Geometry: Theory & Applications"},{"issue":"5","key":"9668_CR3","doi-asserted-by":"publisher","first-page":"1316","DOI":"10.1007\/s00453-020-00784-6","volume":"83","author":"HA Akitaya","year":"2021","unstructured":"Akitaya, H. A., Arkin, E. M., Damian, M., Demaine, E. D., Dujmovic, V., Flatland, R. Y., Korman, M., Palop, B., Parada, I., van Renssen, A., & Sacrist\u00e1n, V. (2021). Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers. Algorithmica, 83(5), 1316\u20131351. https:\/\/doi.org\/10.1007\/s00453-020-00784-6","journal-title":"Algorithmica"},{"key":"9668_CR4","doi-asserted-by":"publisher","unstructured":"Akitaya, H.\u00a0A., Demaine, E.\u00a0D., Korman, M., Kostitsyna, I., Parada, I., Sonke, W., Speckmann, B., Uehara, R., & Wulms, J. (2022). Compacting squares: Input-sensitive in-place reconfiguration of sliding squares. In Scandinavian symposium and workshops on algorithm theory (SWAT) (pp. 1\u201319). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2022.4","DOI":"10.4230\/LIPIcs.SWAT.2022.4"},{"key":"9668_CR5","doi-asserted-by":"publisher","unstructured":"Becker, A.\u00a0T., Fekete, S.\u00a0P., Keldenich, P., Konitzny, M., Lin, L., & Scheffer, C. (2018). Coordinated motion planning: The video. In Symposium on computational geometry (SoCG) (pp. 1\u20136). Video at https:\/\/www.ibr.cs.tu-bs.de\/users\/fekete\/Videos\/CoordinatedMotionPlanning.mp4. https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.74","DOI":"10.4230\/LIPIcs.SoCG.2018.74"},{"key":"9668_CR6","doi-asserted-by":"publisher","unstructured":"Bourgeois, J., Fekete, S.\u00a0P., Kosfeld, R., Kramer, P., Piranda, B., Rieck, C., & Scheffer, C. (2022). Space ants: Episode II\u2014Coordinating connected Catoms. In Symposium on computational geometry (SoCG) (pp. 1\u20136). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2022.65","DOI":"10.4230\/LIPIcs.SoCG.2022.65"},{"issue":"1","key":"9668_CR7","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1137\/060652063","volume":"22","author":"G C\u0103linescu","year":"2008","unstructured":"C\u0103linescu, G., Dumitrescu, A., & Pach, J. (2008). Reconfigurations in graphs and grids. SIAM Journal on Discrete Mathematics, 22(1), 124\u2013138. https:\/\/doi.org\/10.1137\/060652063","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9668_CR8","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1117\/12.360345","volume":"II","author":"A Casal","year":"1999","unstructured":"Casal, A., & Yim, M. H. (1999). Self-reconfiguration planning for a class of modular robots. Sensor Fusion and Decentralized Control in Robotic Systems, II, 246\u2013257. https:\/\/doi.org\/10.1117\/12.360345","journal-title":"Sensor Fusion and Decentralized Control in Robotic Systems"},{"key":"9668_CR9","doi-asserted-by":"publisher","unstructured":"Charrier, T., Queffelec, A., Sankur, O., & Schwarzentruber, F. (2019). Reachability and coverage planning for connected agents. In International joint conference on artificial intelligence (IJCAI) (pp. 144\u2013150). https:\/\/doi.org\/10.24963\/ijcai.2019\/21","DOI":"10.24963\/ijcai.2019\/21"},{"key":"9668_CR10","doi-asserted-by":"publisher","unstructured":"Charrier, T., Queffelec, A., Sankur, O., & Schwarzentruber, F. (2019). Reachability and coverage planning for connected agents. In International conference on autonomous agents and multiagent systems (AAMAS) (pp. 1874\u20131876). https:\/\/doi.org\/10.5555\/3306127.3331948","DOI":"10.5555\/3306127.3331948"},{"issue":"2","key":"9668_CR11","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/s10458-020-09468-5","volume":"34","author":"T Charrier","year":"2020","unstructured":"Charrier, T., Queffelec, A., Sankur, O., & Schwarzentruber, F. (2020). Complexity of planning for connected agents. Autonomous Agents Multi Agent Systems, 34(2), 44. https:\/\/doi.org\/10.1007\/s10458-020-09468-5","journal-title":"Autonomous Agents Multi Agent Systems"},{"issue":"4","key":"9668_CR12","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1109\/TRO.2018.2857475","volume":"34","author":"S-J Chung","year":"2018","unstructured":"Chung, S.-J., Paranjape, A. A., Dames, P., Shen, S., & Kumar, V. (2018). A survey on aerial swarm robotics. IEEE Transactions on Robotics, 34(4), 837\u2013855. https:\/\/doi.org\/10.1109\/TRO.2018.2857475","journal-title":"IEEE Transactions on Robotics"},{"key":"9668_CR13","doi-asserted-by":"publisher","unstructured":"Crombez, L., da\u00a0Fonseca, G.\u00a0D., Gerard, Y., Gonzalez-Lorenzo, A., Lafourcade, P., & Libralesso, L. (2021). Shadoks approach to low-makespan coordinated motion planning. In Symposium on computational geometry (SoCG) (pp. 1\u20139). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2021.63","DOI":"10.4230\/LIPIcs.SoCG.2021.63"},{"issue":"3","key":"9668_CR14","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0218195912500045","volume":"22","author":"M de Berg","year":"2012","unstructured":"de Berg, M., & Khosravi, A. (2012). Optimal binary space partitions for segments in the plane. International Journal on Computational Geometry and Applications, 22(3), 187\u2013206. https:\/\/doi.org\/10.1142\/S0218195912500045","journal-title":"International Journal on Computational Geometry and Applications"},{"key":"9668_CR15","doi-asserted-by":"publisher","unstructured":"Delahaye, D., Puechmorel, S., Tsiotras, P., & F\u00e9ron, E. (2014). Mathematical models for aircraft trajectory design: A survey. In Air traffic management and systems (pp. 205\u2013247). https:\/\/doi.org\/10.1007\/978-4-431-54475-3_12","DOI":"10.1007\/978-4-431-54475-3_12"},{"issue":"3","key":"9668_CR16","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s11047-008-9073-0","volume":"7","author":"ED Demaine","year":"2008","unstructured":"Demaine, E. D., Demaine, M. L., Fekete, S. P., Ishaque, M., Rafalin, E., Schweller, R. T., & Souvaine, D. (2008). Staged self-assembly: Nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing, 7(3), 347\u2013370. https:\/\/doi.org\/10.1007\/s11047-008-9073-0","journal-title":"Natural Computing"},{"issue":"6","key":"9668_CR17","doi-asserted-by":"publisher","first-page":"1727","DOI":"10.1137\/18M1194341","volume":"48","author":"ED Demaine","year":"2019","unstructured":"Demaine, E. D., Fekete, S. P., Keldenich, P., Scheffer, C., & Meijer, H. (2019). Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch. SIAM Journal on Computing, 48(6), 1727\u20131762. https:\/\/doi.org\/10.1137\/18M1194341","journal-title":"SIAM Journal on Computing"},{"key":"9668_CR18","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.tcs.2016.11.020","volume":"671","author":"ED Demaine","year":"2017","unstructured":"Demaine, E. D., Fekete, S. P., Scheffer, C., & Schmidt, A. (2017). New geometric algorithms for fully connected staged self-assembly. Theoretical Computer Science, 671, 4\u201318. https:\/\/doi.org\/10.1016\/j.tcs.2016.11.020","journal-title":"Theoretical Computer Science"},{"key":"9668_CR19","doi-asserted-by":"publisher","unstructured":"Demaine, E.\u00a0D., Patitz, M.\u00a0J., Schweller, R.\u00a0T., & Summers, S.\u00a0M. (2011). Self-assembly of arbitrary shapes using RNAse enzymes: Meeting the Kolmogorov bound with small scale factor. In Symposium on theoretical aspects of computer science (STACS) (pp. 201\u2013212). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2011.201","DOI":"10.4230\/LIPIcs.STACS.2011.201"},{"issue":"1","key":"9668_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00373-005-0640-1","volume":"22","author":"A Dumitrescu","year":"2006","unstructured":"Dumitrescu, A., & Pach, J. (2006). Pushing squares around. Graphs and Combinatorics, 22(1), 37\u201350. https:\/\/doi.org\/10.1007\/s00373-005-0640-1","journal-title":"Graphs and Combinatorics"},{"issue":"6","key":"9668_CR21","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1177\/0278364904039652","volume":"23","author":"A Dumitrescu","year":"2004","unstructured":"Dumitrescu, A., Suzuki, I., & Yamashita, M. (2004). Formations for fast locomotion of metamorphic robotic systems. International Journal of Robotics Research, 23(6), 583\u2013593. https:\/\/doi.org\/10.1177\/0278364904039652","journal-title":"International Journal of Robotics Research"},{"issue":"3","key":"9668_CR22","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1109\/TRA.2004.824936","volume":"20","author":"A Dumitrescu","year":"2004","unstructured":"Dumitrescu, A., Suzuki, I., & Yamashita, M. (2004). Motion planning for metamorphic systems: Feasibility, decidability, and distributed reconfiguration. IEEE Transactions on Robotics, 20(3), 409\u2013418. https:\/\/doi.org\/10.1109\/TRA.2004.824936","journal-title":"IEEE Transactions on Robotics"},{"key":"9668_CR23","doi-asserted-by":"publisher","unstructured":"Fekete, S.\u00a0P., Hendriks, B., Tessars, C., Wegener, A., Hellbr\u00fcck, H., Fischer, S., & Ebers, S. (2011). Methods for improving the flow of traffic. In Organic computing\u2014A paradigm shift for complex systems (pp. 447\u2013460). https:\/\/doi.org\/10.1007\/978-3-0348-0130-0_29","DOI":"10.1007\/978-3-0348-0130-0_29"},{"key":"9668_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-023-09626-5","author":"SP Fekete","year":"2023","unstructured":"Fekete, S. P., Keldenich, P., Kosfeld, R., Rieck, C., & Scheffer, C. (2023). Connected coordinated motion planning with bounded stretch. Autonomous Agents and Multi-Agent Systems. https:\/\/doi.org\/10.1007\/s10458-023-09626-5","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"9668_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3532773","volume":"27","author":"SP Fekete","year":"2022","unstructured":"Fekete, S. P., Keldenich, P., Krupke, D., & Mitchell, J. S. B. (2022). Computing coordinated motion plans for robot swarms: The CG:SHOP challenge 2021. ACM Journal of Experimental Algorithmics, 27, 1\u201312. https:\/\/doi.org\/10.1145\/3532773","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"9668_CR26","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184","volume-title":"Flows in networks","author":"LR Ford","year":"1962","unstructured":"Ford, L. R., & Fulkerson, D. R. (1962). Flows in networks. Princeton University Press. https:\/\/doi.org\/10.1515\/9781400875184"},{"key":"9668_CR27","doi-asserted-by":"publisher","unstructured":"Geft, T., & Halperin, D. (2022). Refined hardness of distance-optimal multi-agent path finding. In International conference on autonomous agents and multiagent systems (AAMAS) (pp. 481\u2013488). https:\/\/doi.org\/10.5555\/3535850.3535905","DOI":"10.5555\/3535850.3535905"},{"key":"9668_CR28","unstructured":"Goldstein, S.\u00a0C., & Mowry, T.\u00a0C. (2004). Claytronics: A scalable basis for future robots. http:\/\/www.cs.cmu.edu\/~claytronics\/papers\/goldstein-robosphere04.pdf"},{"issue":"2","key":"9668_CR29","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/JCSS.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., & Paturi, R. (2001). On the complexity of k-sat. J. Comput. Syst. Sci., 62(2), 367\u2013375. https:\/\/doi.org\/10.1006\/JCSS.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"key":"9668_CR30","unstructured":"Jiang, Z., Hu, X., & Gao, S. (2013). A parallel Ford\u2013Fulkerson algorithm for maximum flow problem. In International conference on parallel and distributed processing techniques and applications (PDPTA) (pp. 71\u201374)."},{"issue":"4","key":"9668_CR31","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1109\/TRO.2006.878952","volume":"22","author":"S Kloder","year":"2006","unstructured":"Kloder, S., & Hutchinson, S. (2006). Path planning for permutation-invariant multi-robot formations. IEEE Transactions on Robotics and Automation, 22(4), 650\u2013665. https:\/\/doi.org\/10.1109\/TRO.2006.878952","journal-title":"IEEE Transactions on Robotics and Automation"},{"key":"9668_CR32","doi-asserted-by":"publisher","unstructured":"Kornhauser, D., Miller, G.\u00a0L., & Spirakis, P.\u00a0G. (1984). Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In Foundations of computer science (FOCS) (pp. 241\u2013250). https:\/\/doi.org\/10.1109\/SFCS.1984.715921","DOI":"10.1109\/SFCS.1984.715921"},{"key":"9668_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-56039-6","volume-title":"Combinatorial optimization","author":"BH Korte","year":"2011","unstructured":"Korte, B. H., & Vygen, J. (2011). Combinatorial optimization. Springer. https:\/\/doi.org\/10.1007\/978-3-662-56039-6"},{"key":"9668_CR34","doi-asserted-by":"publisher","unstructured":"Liu, P., Spalding-Jamieson, J., Zhang, B., & Da Zheng, W. (2021). Coordinated motion planning through randomized $$k$$-opt. In Symposium on computational geometry (SoCG) (pp. 1\u201364). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2021.64","DOI":"10.4230\/LIPIcs.SoCG.2021.64"},{"issue":"1","key":"9668_CR35","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s11047-018-9707-9","volume":"18","author":"A Luchsinger","year":"2019","unstructured":"Luchsinger, A., Schweller, R. T., & Wylie, T. (2019). Self-assembly of shapes at constant scale using repulsive forces. Natural Computing, 18(1), 93\u2013105. https:\/\/doi.org\/10.1007\/s11047-018-9707-9","journal-title":"Natural Computing"},{"key":"9668_CR36","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/j.tcs.2022.11.015","volume":"941","author":"A Queffelec","year":"2023","unstructured":"Queffelec, A., Sankur, O., & Schwarzentruber, F. (2023). Complexity of planning for connected agents in a partially known environment. Theoretical Computer Science, 941, 202\u2013220. https:\/\/doi.org\/10.1016\/j.tcs.2022.11.015","journal-title":"Theoretical Computer Science"},{"key":"9668_CR37","doi-asserted-by":"publisher","unstructured":"Reif, J.\u00a0H. (1979). Complexity of the mover\u2019s problem and generalizations. In Foundations of computer science (FOCS) (pp. 421\u2013427). https:\/\/doi.org\/10.1109\/SFCS.1979.10.","DOI":"10.1109\/SFCS.1979.10"},{"issue":"6198","key":"9668_CR38","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1126\/science.1254295","volume":"345","author":"M Rubenstein","year":"2014","unstructured":"Rubenstein, M., Cornejo, A., & Nagpal, R. (2014). Programmable self-assembly in a thousand-robot swarm. Science, 345(6198), 795\u2013799. https:\/\/doi.org\/10.1126\/science.1254295","journal-title":"Science"},{"issue":"2\u20134","key":"9668_CR39","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s11721-008-0020-6","volume":"2","author":"E \u015eahin","year":"2008","unstructured":"\u015eahin, E., & Winfield, A. F. T. (2008). Special issue on swarm robotics. Swarm Intelligence, 2(2\u20134), 69\u201372. https:\/\/doi.org\/10.1007\/s11721-008-0020-6","journal-title":"Swarm Intelligence"},{"key":"9668_CR40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07809-9","volume-title":"Human behaviour and traffic networks","author":"M Schreckenberg","year":"2013","unstructured":"Schreckenberg, M., & Selten, R. (2013). Human behaviour and traffic networks. Springer. https:\/\/doi.org\/10.1007\/978-3-662-07809-9"},{"issue":"3","key":"9668_CR41","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1177\/027836498300200304","volume":"2","author":"JT Schwartz","year":"1983","unstructured":"Schwartz, J. T., & Sharir, M. (1983). On the piano movers\u2019 problem: III. Coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal barriers. International Journal of Robotics Research, 2(3), 46\u201375. https:\/\/doi.org\/10.1177\/027836498300200304","journal-title":"International Journal of Robotics Research"},{"issue":"6","key":"9668_CR42","doi-asserted-by":"publisher","first-page":"1544","DOI":"10.1137\/S0097539704446712","volume":"36","author":"D Soloveichik","year":"2007","unstructured":"Soloveichik, D., & Winfree, E. (2007). Complexity of self-assembled shapes. SIAM Journal on Computing, 36(6), 1544\u20131569. https:\/\/doi.org\/10.1137\/S0097539704446712","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"9668_CR43","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1177\/0278364913506268","volume":"33","author":"K Solovey","year":"2014","unstructured":"Solovey, K., & Halperin, D. (2014). $$k$$-color multi-robot motion planning. International Journal of Robotics Research, 33(1), 82\u201397. https:\/\/doi.org\/10.1177\/0278364913506268","journal-title":"International Journal of Robotics Research"},{"issue":"14","key":"9668_CR44","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. https:\/\/doi.org\/10.1177\/0278364916672311","journal-title":"International Journal of Robotics Research"},{"key":"9668_CR45","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2015.XI.011","author":"K Solovey","year":"2015","unstructured":"Solovey, K., Yu, J., Zamir, O., & Halperin, D. (2015). Motion planning for unlabeled discs with optimality guarantees. Robotics: Science and Systems. https:\/\/doi.org\/10.15607\/RSS.2015.XI.011","journal-title":"Robotics: Science and Systems"},{"key":"9668_CR46","doi-asserted-by":"publisher","unstructured":"Stern, R., Sturtevant, N.\u00a0R., Felner, A., Koenig, S., Ma, H., Walker, T.\u00a0T., Li, J., Atzmon, D., Cohen, L., Kumar, T.\u00a0K.\u00a0S., Bart\u00e1k, R., & Boyarski, E. (2019). Multi-agent pathfinding: Definitions, variants, and benchmarks. In Symposium on combinatorial search (SOCS) (pp. 151\u2013159). https:\/\/doi.org\/10.1609\/socs.v10i1.18510","DOI":"10.1609\/socs.v10i1.18510"},{"issue":"3","key":"9668_CR47","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0921-8890(97)00033-X","volume":"23","author":"P \u0160vestka","year":"1998","unstructured":"\u0160vestka, P., & Overmars, M. H. (1998). Coordinated path planning for multiple robots. Robotics and Autonomous Systems, 23(3), 125\u2013152. https:\/\/doi.org\/10.1016\/S0921-8890(97)00033-X","journal-title":"Robotics and Autonomous Systems"},{"key":"9668_CR48","doi-asserted-by":"publisher","unstructured":"Turpin, M., Michael, N., & Kumar, V.. (2013). Trajectory planning and assignment in multirobot systems. In Algorithmic foundations of robotics X\u2014Workshop on the algorithmic foundations of robotics (WAFR) (pp. 175\u2013190). https:\/\/doi.org\/10.1007\/978-3-642-36279-8_11","DOI":"10.1007\/978-3-642-36279-8_11"},{"issue":"4","key":"9668_CR49","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s10514-014-9412-1","volume":"37","author":"M Turpin","year":"2014","unstructured":"Turpin, M., Mohta, K., Michael, N., & Kumar, V. (2014). Goal assignment and trajectory planning for large teams of interchangeable robots. Autonomous Robots, 37(4), 401\u2013415. https:\/\/doi.org\/10.1007\/s10514-014-9412-1","journal-title":"Autonomous Robots"},{"key":"9668_CR50","doi-asserted-by":"publisher","unstructured":"Yang, H., & Vigneron, A. (2021). A simulated annealing approach to coordinated motion planning. In Symposium on computational geometry (SoCG) (pp. 1\u20139). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2021.65","DOI":"10.4230\/LIPIcs.SoCG.2021.65"},{"key":"9668_CR51","doi-asserted-by":"publisher","unstructured":"Yu, J., & LaValle, S.\u00a0M. (2012). Multi-agent path planning and network flow. In Workshop on the algorithmic foundations of robotics (WAFR) (pp. 157\u2013173). https:\/\/doi.org\/10.1007\/978-3-642-36279-8_10","DOI":"10.1007\/978-3-642-36279-8_10"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09668-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-024-09668-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09668-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T15:24:08Z","timestamp":1731511448000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-024-09668-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,7]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9668"],"URL":"https:\/\/doi.org\/10.1007\/s10458-024-09668-3","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2024,8,7]]},"assertion":[{"value":"11 July 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"39"}}