{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:42Z","timestamp":1750219842329,"version":"3.41.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T00:00:00Z","timestamp":1676419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science and Engineering Research Council","award":["228105-2015"],"award-info":[{"award-number":["228105-2015"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Hum.-Robot Interact."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>Over the last 20 years, human interaction with robot swarms has been investigated as a means to mitigate problems associated with the control and coordination of such swarms by either human teleoperation or completely autonomous swarms. Ongoing research seeks to characterize those situations in which such interaction is both viable and preferable. In this article, we contribute to this effort by giving the first computational complexity analyses of problems associated with algorithm, environmental influence, and leader selection methods for the control of swarms performing distributed construction tasks. These analyses are done relative to a simple model in which swarms of deterministic finite-state robots operate in a synchronous error-free manner in 2D grid-based environments. We show that all three of our problems are polynomial-time intractable in general and remain intractable under a number of plausible restrictions (both individually and in many combinations) on robot controllers, environments, target structures, and sequences of swarm control commands. We also give the first restrictions relative to which these problems are tractable, as well as discussions of the implications of our results for both the design and deployment of swarm control assistance software tools and the human control of swarms.<\/jats:p>","DOI":"10.1145\/3555078","type":"journal-article","created":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T11:57:50Z","timestamp":1659700670000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Swarm Control for Distributed Construction: A Computational Complexity Perspective"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2410-7991","authenticated-orcid":false,"given":"Todd","family":"Wareham","sequence":"first","affiliation":[{"name":"Memorial University of Newfoundland, NL, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2023-0586","authenticated-orcid":false,"given":"Ronald","family":"de Haan","sequence":"additional","affiliation":[{"name":"Universiteit van Amsterdam, Amsterdam, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7278-5378","authenticated-orcid":false,"given":"Andrew","family":"Vardy","sequence":"additional","affiliation":[{"name":"Memorial University of Newfoundland, NL, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6520-4635","authenticated-orcid":false,"given":"Iris","family":"van Rooij","sequence":"additional","affiliation":[{"name":"Radboud Universiteit, Nijmegen, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2023,2,15]]},"reference":[{"key":"e_1_3_5_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509913"},{"key":"e_1_3_5_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICAR.2017.8023623"},{"issue":"3","key":"e_1_3_5_4_2","first-page":"10","article-title":"Are autonomous mobile robots able to take over construction? A review","volume":"4","author":"Ardiny Hadi","year":"2015","unstructured":"Hadi Ardiny, Stefan Witwicki, and Francesco Mondada. 2015. Are autonomous mobile robots able to take over construction? A review. International Journal of Robotics: Theory and Applications 4, 3 (2015), 10\u201321.","journal-title":"International Journal of Robotics: Theory and Applications"},{"key":"e_1_3_5_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/328320"},{"key":"e_1_3_5_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-012-0075-2"},{"key":"e_1_3_5_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_3_5_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_3_5_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2650247"},{"key":"e_1_3_5_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-10801-4_15"},{"key":"e_1_3_5_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/2464827"},{"key":"e_1_3_5_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"1","key":"e_1_3_5_13_2","first-page":"19","article-title":"Complexity results for agent design","volume":"1","author":"Dunne Philip E.","year":"2003","unstructured":"Philip E. Dunne, Michael Laurence, and Michael Wooldridge. 2003. Complexity results for agent design. Annals of Mathematics, Computing and Teleinformatics 1, 1 (2003), 19\u201336.","journal-title":"Annals of Mathematics, Computing and Teleinformatics"},{"key":"e_1_3_5_14_2","first-page":"6","volume-title":"Proceedings of the 15th Canadian Conference on Computational Geometry","author":"Fernau Henning","year":"2003","unstructured":"Henning Fernau, Torben Hagerup, Naomi Nishimura, Prabhakar Ragde, and Klaus Reinhardt. 2003. On the parameterized complexity of the generalized rush hour puzzle. In Proceedings of the 15th Canadian Conference on Computational Geometry. 6\u20139."},{"key":"e_1_3_5_15_2","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","year":"2006","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer, Berlin."},{"key":"e_1_3_5_16_2","volume-title":"Kernalization: Theory of Parameterized Prepreocessing","author":"Fomin Fedor V.","year":"2019","unstructured":"Fedor V. Fomin, Daniel Lokshantov, Saket Saurabh, and Meirav Zehavi. 2019. Kernalization: Theory of Parameterized Prepreocessing. Cambridge University Press, Cambridge, UK."},{"key":"e_1_3_5_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1562164.1562186"},{"key":"e_1_3_5_18_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017503201702"},{"key":"e_1_3_5_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_3_5_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FAS-W.2016.45"},{"key":"e_1_3_5_21_2","doi-asserted-by":"publisher","DOI":"10.1177\/14780771211025153"},{"key":"e_1_3_5_22_2","volume-title":"The Moon is a Harsh Mistress","author":"Heinlein Robert A.","year":"1966","unstructured":"Robert A. Heinlein. 1966. The Moon is a Harsh Mistress. G. P. Putnam\u2019s Sons, New York."},{"key":"e_1_3_5_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2421119.2421135"},{"key":"e_1_3_5_24_2","volume-title":"Introduction to Automata Theory, Languages, and Computation (2nd ed.)","author":"Hopcroft John E.","year":"2001","unstructured":"John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2001. Introduction to Automata Theory, Languages, and Computation (2nd ed.). Addison-Wesley."},{"key":"e_1_3_5_25_2","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300405"},{"key":"e_1_3_5_26_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_5_27_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_5_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2157689.2157704"},{"key":"e_1_3_5_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/THMS.2015.2480801"},{"key":"e_1_3_5_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_2"},{"key":"e_1_3_5_31_2","doi-asserted-by":"publisher","DOI":"10.1177\/1557234X13506688"},{"key":"e_1_3_5_32_2","first-page":"1","volume-title":"Proceedings of the NATO Symposium on Human Factors of Uninhabited Military Vehicles as Force Multipliers","author":"Lewis Michael","year":"2006","unstructured":"Michael Lewis, Jijun Wang, and Paul Scerri. 2006. Teamwork coordination for realistically complex multi robot systems. In Proceedings of the NATO Symposium on Human Factors of Uninhabited Military Vehicles as Force Multipliers. 1\u201312."},{"key":"e_1_3_5_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/SMC.2018.00644"},{"key":"e_1_3_5_34_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"e_1_3_5_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9381-0"},{"key":"e_1_3_5_36_2","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","year":"2010","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 2010. Randomized Algorithms. Chapman & Hall\/CRC."},{"key":"e_1_3_5_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989312"},{"key":"e_1_3_5_38_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_3_5_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/2821575"},{"key":"e_1_3_5_40_2","doi-asserted-by":"publisher","DOI":"10.1126\/scirobotics.aau8479"},{"key":"e_1_3_5_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11229-019-02431-2"},{"key":"e_1_3_5_42_2","doi-asserted-by":"publisher","DOI":"10.1111\/tops.12506"},{"key":"e_1_3_5_43_2","volume-title":"The Language Complexity Game","author":"Ristad Eric S.","year":"1993","unstructured":"Eric S. Ristad. 1993. The Language Complexity Game. MIT Press."},{"key":"e_1_3_5_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32552-1_57"},{"key":"e_1_3_5_45_2","doi-asserted-by":"publisher","DOI":"10.21236\/ADA057655"},{"key":"e_1_3_5_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2015.07.018"},{"key":"e_1_3_5_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(03)00014-6"},{"key":"e_1_3_5_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-006-5943-4"},{"key":"e_1_3_5_49_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.269.5224.686"},{"issue":"4","key":"e_1_3_5_50_2","first-page":"1","article-title":"Special issue: Autonomous assembly: Designing for a new era of collective construction","volume":"87","author":"Tibbits Skylar","year":"2017","unstructured":"Skylar Tibbits (Ed.). 2017. Special issue: Autonomous assembly: Designing for a new era of collective construction. Architectural Design 87, 4 (2017), 1\u2013136.","journal-title":"Architectural Design"},{"key":"e_1_3_5_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-05816-6_4"},{"key":"e_1_3_5_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2018.2812906"},{"key":"e_1_3_5_53_2","doi-asserted-by":"publisher","DOI":"10.1080\/03640210801897856"},{"key":"e_1_3_5_54_2","doi-asserted-by":"publisher","DOI":"10.1177\/1745691620970604"},{"key":"e_1_3_5_55_2","volume-title":"Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis","author":"Rooij Iris van","year":"2019","unstructured":"Iris van Rooij, Mark Blokpoel, Johan Kwisthout, and Todd Wareham. 2019. Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis. Cambridge University Press, Cambridge, UK."},{"key":"e_1_3_5_56_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm034"},{"key":"e_1_3_5_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmp.2012.05.002"},{"key":"e_1_3_5_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11229-010-9847-7"},{"key":"e_1_3_5_59_2","volume-title":"Systematic Parameterized Complexity Analysis in Computational Phonology","author":"Wareham Todd","year":"1999","unstructured":"Todd Wareham. 1999. Systematic Parameterized Complexity Analysis in Computational Phonology. Ph.D. Dissertation. University of Victoria, Canada."},{"key":"e_1_3_5_60_2","first-page":"295","volume-title":"Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communication Technologies","author":"Wareham Todd","year":"2015","unstructured":"Todd Wareham. 2015. Exploring algorithmic options for the efficient design and reconfiguration of reactive robot swarms. In Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communication Technologies. ICST, Brussels, 295\u2013302."},{"key":"e_1_3_5_61_2","first-page":"2:1\u20132:29","article-title":"Designing robot teams for distributed construction, repair, and maintenance","volume":"14","author":"Wareham Todd","year":"2019","unstructured":"Todd Wareham. 2019. Designing robot teams for distributed construction, repair, and maintenance. ACM Transactions on Autonomous and Adaptive Systems 14, 1 (2019), 2:1\u20132:29.","journal-title":"ACM Transactions on Autonomous and Adaptive Systems"},{"key":"e_1_3_5_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/DEVLRN.2011.6037337"},{"key":"e_1_3_5_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-017-0152-7"},{"key":"e_1_3_5_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3157087"},{"key":"e_1_3_5_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACSOS-C52956.2021.00059"},{"key":"e_1_3_5_66_2","unstructured":"Eric W. Weisstein. 2020. Von neumann neighborhood. Retrieved July 31 2020 from https:\/\/mathworld.wolfram.com\/vonNeumannNeighborhood.html. From MathWorld \u2013 A Wolfram Web Resource."},{"key":"e_1_3_5_67_2","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2006.25"},{"key":"e_1_3_5_68_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1245842"},{"key":"e_1_3_5_69_2","doi-asserted-by":"publisher","DOI":"10.4171\/022-1\/25"},{"key":"e_1_3_5_70_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45448-9_9"}],"container-title":["ACM Transactions on Human-Robot Interaction"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555078","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3555078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:51Z","timestamp":1750178811000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555078"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,15]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3555078"],"URL":"https:\/\/doi.org\/10.1145\/3555078","relation":{},"ISSN":["2573-9522","2573-9522"],"issn-type":[{"type":"print","value":"2573-9522"},{"type":"electronic","value":"2573-9522"}],"subject":[],"published":{"date-parts":[[2023,2,15]]},"assertion":[{"value":"2020-10-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-28","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}