{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:48Z","timestamp":1750221288990,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,31]],"date-time":"2018-03-31T00:00:00Z","timestamp":1522454400000},"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 (NSERC) Discovery","award":["228104-2015(TW)"],"award-info":[{"award-number":["228104-2015(TW)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>A central problem in swarm robotics is to design a controller that will allow the member robots of the swarm to collectively perform a given task. Of particular interest in massively distributed applications are reactive controllers with severely limited computational and sensory abilities. In this article, we give the results of the first computational complexity analysis of the reactive swarm design problem. Our core results are derived relative to a generalization of what is arguably the simplest possible type of reactive controller, the so-called computation-free controller proposed by Gauci et al., which operates in grid-based environments in a noncontinuous manner. We show that the design of a generalized computation-free swarm for an arbitrary given task in an arbitrary given environment is not polynomial-time solvable either in general or by the most desirable types of approximation algorithms (including evolutionary algorithms with high probabilities of producing correct solutions) but is solvable in effectively polynomial time relative to several types of restrictions on swarms, environments, and tasks. All of our results hold for the design of several more complex types of generalized computation-free swarms. Moreover, all of our intractability and inapproximability results hold for the design of any type of reactive swarm (including those based on the popular feed-forward neural network and Brooks-style subsumption controllers) operating in grid-based environments in a noncontinuous manner whose member robots satisfy two simple conditions. As such, our results give the first theoretical survey of the types of efficient exact and approximate solution algorithms that are and are not possible for designing several types of reactive swarms.<\/jats:p>","DOI":"10.1145\/3157087","type":"journal-article","created":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T12:27:57Z","timestamp":1523881677000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Viable Algorithmic Options for Designing Reactive Robot Swarms"],"prefix":"10.1145","volume":"13","author":[{"given":"Todd","family":"Wareham","sequence":"first","affiliation":[{"name":"Memorial University of Newfoundland, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Vardy","sequence":"additional","affiliation":[{"name":"Memorial University of Newfoundland, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,4,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1052796.1052804"},{"volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"Ausiello Giorgio","key":"e_1_2_1_2_1","unstructured":"Giorgio Ausiello , Pierluigi Crescenzi , Giorgio Gambosi , Viggo Kann , Alberto Marchetti-Spaccamela , and Marco Protasi . 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties . Springer . Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, and Marco Protasi. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2015.05.116"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-012-0075-2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1986.1087032"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-013-9398-1"},{"key":"e_1_2_1_8_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer , Berlin Germany. Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer, Berlin Germany."},{"key":"e_1_2_1_9_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer , Berlin, Germany. Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer, Berlin, Germany."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562164.1562186"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.3389\/frobt.2016.00029"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-014-0092-4"},{"key":"e_1_2_1_13_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability. W. H. Freeman."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914525244"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 13th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201914)","author":"Gauci Melvin","year":"2014","unstructured":"Melvin Gauci , Jianing Chen , Wei Li , Tony J. Dodd , and Roderich Gro\u00df . 2014 b. Clustering objects with robots that do not compute . In Proceedings of the 13th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201914) . 421--428. Melvin Gauci, Jianing Chen, Wei Li, Tony J. Dodd, and Roderich Gro\u00df. 2014b. Clustering objects with robots that do not compute. In Proceedings of the 13th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201914). 421--428."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2421119.2421135"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4108\/eai.3-12-2015.2262390"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_1_20_1","volume-title":"ADAPTIVE 2016: The 8th International Conference on Adaptive and Self-Adaptive Systems and Applications. 34--39","author":"Khaluf Yara","year":"2016","unstructured":"Yara Khaluf . 2016 . Adaptive construction behavior in robot swarms . In ADAPTIVE 2016: The 8th International Conference on Adaptive and Self-Adaptive Systems and Applications. 34--39 . Yara Khaluf. 2016. Adaptive construction behavior in robot swarms. In ADAPTIVE 2016: The 8th International Conference on Adaptive and Self-Adaptive Systems and Applications. 34--39."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9660-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2831071.2831086"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-016-0119-0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"volume-title":"Randomized Algorithms","author":"Motwani Rajeev","key":"e_1_2_1_26_1","unstructured":"Rajeev Motwani and Prabhakar Raghavan . 2010. Randomized Algorithms . Chapman 8 Hall\/CRC. Rajeev Motwani and Prabhakar Raghavan. 2010. Randomized Algorithms. Chapman 8 Hall\/CRC."},{"volume-title":"Introduction to AI Robotics","author":"Murphy Robin","key":"e_1_2_1_27_1","unstructured":"Robin Murphy . 2000. Introduction to AI Robotics . MIT Press , Cambridge, MA . Robin Murphy. 2000. Introduction to AI Robotics. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30552-1_2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2015.07.018"},{"volume-title":"Evolutionary Swarm Robotics: Evolving Self-Organising Behaviours in Groups of Autonomous Robots. Studies in Computational Intelligence","author":"Trianni Vito","key":"e_1_2_1_30_1","unstructured":"Vito Trianni . 2008. Evolutionary Swarm Robotics: Evolving Self-Organising Behaviours in Groups of Autonomous Robots. Studies in Computational Intelligence , Vol. 108 . Springer . Vito Trianni. 2008. Evolutionary Swarm Robotics: Evolving Self-Organising Behaviours in Groups of Autonomous Robots. Studies in Computational Intelligence, Vol. 108. Springer."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4108\/eai.3-12-2015.2262395"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Todd Wareham and Andrew Vardy. 2017. Putting it together: The computational complexity of designing robot controllers and environments for distributed construction. Swarm Intelligence.  Todd Wareham and Andrew Vardy. 2017. Putting it together: The computational complexity of designing robot controllers and environments for distributed construction. Swarm Intelligence.","DOI":"10.1007\/s11721-017-0152-7"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1245842"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4171\/022-1\/25"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3157087","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3157087","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:29Z","timestamp":1750212689000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3157087"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,31]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3157087"],"URL":"https:\/\/doi.org\/10.1145\/3157087","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2018,3,31]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}