{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T10:04:56Z","timestamp":1785924296433,"version":"3.56.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001961","name":"AXA Research Fund","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001961","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001961","name":"AXA Research Fund","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001961","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/R030073\/1"],"award-info":[{"award-number":["EP\/R030073\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The<jats:italic>Coalition Formation with Spatial and Temporal constraints Problem<\/jats:italic>(CFSTP) is a multi-agent task allocation problem where the tasks are spatially distributed, with deadlines and workloads, and the number of agents is typically much smaller than the number of tasks. To maximise the number of completed tasks, the agents may have to schedule coalitions. The state-of-the-art CFSTP solver, the<jats:italic>Coalition Formation with Look-Ahead<\/jats:italic>(CFLA) algorithm, has two main limitations. First, its time complexity is exponential with the number of agents. Second, as we show, its look-ahead technique is not effective in real-world scenarios, such as open multi-agent systems, where new tasks can appear at any time. In this work, we study its design and define a variant, called<jats:italic>Coalition Formation with Improved Look-Ahead<\/jats:italic>(<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\text {CFLA}2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mtext>CFLA<\/mml:mtext><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>), which achieves better performance. Since we cannot eliminate the limitations of CFLA in<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\text {CFLA}2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mtext>CFLA<\/mml:mtext><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we also develop a novel algorithm to solve the CFSTP, the first to be simultaneously anytime, efficient and with convergence guarantee, called<jats:italic>Cluster-based Task Scheduling<\/jats:italic>(CTS). In tests where the look-ahead technique is highly effective, CTS completes up to<jats:inline-formula><jats:alternatives><jats:tex-math>$$30\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>30<\/mml:mn><mml:mo>%<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(resp.<jats:inline-formula><jats:alternatives><jats:tex-math>$$10\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>10<\/mml:mn><mml:mo>%<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) more tasks than CFLA (resp.<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\text {CFLA}2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mtext>CFLA<\/mml:mtext><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) while being up to 4 orders of magnitude faster. We also propose S-CTS, a simplified but parallel variant of CTS with even lower time complexity. Using scenarios generated by the RoboCup Rescue Simulation, we show that S-CTS is at most<jats:inline-formula><jats:alternatives><jats:tex-math>$$10\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>10<\/mml:mn><mml:mo>%<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>less performing than high-performance algorithms such as Binary Max-Sum and DSA, but up to 2 orders of magnitude faster. Our results affirm CTS as the new state-of-the-art algorithm to solve the CFSTP.<\/jats:p>","DOI":"10.1007\/s42979-021-00523-w","type":"journal-article","created":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T16:06:50Z","timestamp":1616515610000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Anytime and Efficient Multi-agent Coordination for Disaster Response"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4404-0998","authenticated-orcid":false,"given":"Luca","family":"Capezzuto","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3226-6861","authenticated-orcid":false,"given":"Danesh","family":"Tarapore","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9686-4302","authenticated-orcid":false,"given":"Sarvapali D.","family":"Ramchurn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"523_CR1","volume-title":"Principles of emergency planning and management","author":"ED Alexander","year":"2002","unstructured":"Alexander ED. Principles of emergency planning and management. Oxford University Press; 2002."},{"issue":"16","key":"523_CR2","doi-asserted-by":"publisher","first-page":"5522","DOI":"10.1080\/00207543.2018.1470695","volume":"56","author":"K Bogner","year":"2018","unstructured":"Bogner K, Pferschy U, Unterberger R, Zeiner H. Optimised scheduling in human\u2013robot collaboration\u2014a use case in the assembly of printed circuit boards. Int J Prod Res. 2018;56(16):5522\u201340.","journal-title":"Int J Prod Res"},{"issue":"6","key":"523_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00355ED1V01Y201107AIM016","volume":"5","author":"G Chalkiadakis","year":"2011","unstructured":"Chalkiadakis G, Elkind E, Wooldridge M. Computational aspects of cooperative game theory. Synth Lect Artif Intell Mach Learn. 2011;5(6):1\u2013168.","journal-title":"Synth Lect Artif Intell Mach Learn"},{"issue":"3","key":"523_CR4","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1016\/0377-2217(94)00289-4","volume":"88","author":"IM Chao","year":"1996","unstructured":"Chao IM, Golden BL, Wasil EA. The team orienteering problem. Eur J Oper Res. 1996;88(3):464\u201374.","journal-title":"Eur J Oper Res"},{"key":"523_CR5","volume-title":"Introduction to international disaster management","author":"DP Coppola","year":"2006","unstructured":"Coppola DP. Introduction to international disaster management. Elsevier; 2006."},{"key":"523_CR6","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithms. 3rd ed. MIT Press; 2009.","edition":"3"},{"key":"523_CR7","unstructured":"Donald, K.E.: The art of computer programming, volume 4, fascicle 2: generating all tuples and permutations. Pearson Education; 2005."},{"issue":"3","key":"523_CR8","first-page":"465","volume":"22","author":"F Dos Santos","year":"2011","unstructured":"Dos Santos F, Bazzan ALC. Towards efficient multiagent task allocation in the robocup rescue: a biologically-inspired approach. AAMAS. 2011;22(3):465\u201386.","journal-title":"AAMAS"},{"key":"523_CR9","unstructured":"Farinelli A., Rogers A., Petcu A., Jennings N.R.: Decentralised coordination of low-power embedded devices using the max-sum algorithm. In: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - (AAMAS '08). International Foundation for Autonomous Agents and Multiagent Systems, Richland; vol.\u00a02. 2008. p. 639\u2013646."},{"key":"523_CR10","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1613\/jair.5565","volume":"61","author":"F Fioretto","year":"2018","unstructured":"Fioretto F, Pontelli E, Yeoh W. Distributed constraint optimization problems and applications: a survey. JAIR. 2018;61:623\u201398.","journal-title":"JAIR"},{"issue":"5","key":"523_CR11","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1002\/sys.21433","volume":"21","author":"X Gallud","year":"2018","unstructured":"Gallud X, Selva D. Agent-based simulation framework and consensus algorithm for observing systems with adaptive modularity. Syst Eng. 2018;21(5):432\u201354.","journal-title":"Syst Eng"},{"key":"523_CR12","doi-asserted-by":"crossref","unstructured":"Godoy J, Gini M. Task allocation for spatially and temporally distributed tasks. In: Proceedings of the 12th international conference on intelligent autonomous systems. Springer, Berlin; 2013. p. 603\u201312.","DOI":"10.1007\/978-3-642-33932-5_56"},{"key":"523_CR13","first-page":"383","volume-title":"The challenge of open systems","author":"C Hewitt","year":"1990","unstructured":"Hewitt C. The challenge of open systems. Cambridge University Press; 1990. p. 383\u201395."},{"issue":"4","key":"523_CR14","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1017\/S0269888905000317","volume":"19","author":"B Horling","year":"2005","unstructured":"Horling B, Lesser V. A survey of multi-organizational paradigms. Knowl Eng Rev. 2005;19(4):281\u2013316.","journal-title":"Knowl Eng Rev"},{"key":"523_CR15","unstructured":"Kitano H, Tadokoro S. Robocup rescue: a grand challenge for multiagent and intelligent systems. AI Mag. 2001;22(1):39. https:\/\/rescuesim.robocup.org."},{"key":"523_CR16","doi-asserted-by":"publisher","unstructured":"Kitano H et al., RoboCup Rescue: search and rescue in large-scale disasters as a domain for autonomous agents research, IEEE SMC'99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No.99CH37028), Tokyo, vol.6, 1999. p. 739\u201343. https:\/\/doi.org\/10.1109\/ICSMC.1999.816643.","DOI":"10.1109\/ICSMC.1999.816643"},{"key":"523_CR17","unstructured":"Kleiner A, Farinelli A, Ramchurn S, Shi B, Maffioletti F, Reffato R. Rmasbench: benchmarking dynamic multi-agent coordination in urban search and rescue. In: Proc. of the 12th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2013), The international foundation for autonomous agents and multiagent systems (IFAAMAS); 2013. p. 1195\u20136."},{"key":"523_CR18","first-page":"1292","volume":"5","author":"M Koes","year":"2005","unstructured":"Koes M, Nourbakhsh I, Sycara K. Heterogeneous multirobot coordination with spatial and temporal constraints. AAAI. 2005;5:1292\u20137.","journal-title":"AAAI"},{"key":"523_CR19","unstructured":"Korsah GA. Exploring bounded optimal coordination for heterogeneous teams with cross-schedule dependencies. Ph.D. thesis, Carnegie Mellon University; 2011."},{"issue":"12","key":"523_CR20","doi-asserted-by":"publisher","first-page":"1495","DOI":"10.1177\/0278364913496484","volume":"32","author":"GA Korsah","year":"2013","unstructured":"Korsah GA, Stentz A, Dias MB. A comprehensive taxonomy for multi-robot task allocation. Int J Robot Res. 2013;32(12):1495\u2013512.","journal-title":"Int J Robot Res"},{"key":"523_CR21","doi-asserted-by":"publisher","unstructured":"Krizmancic M, Arbanas B, Petrovic T, Petric F, Bogdan S. Cooperative aerial-ground multi-robot system for automated construction tasks. IEEE Robot Autom Lett. 2020;5(2):798\u2013805. https:\/\/doi.org\/10.1109\/LRA.2020.2965855.","DOI":"10.1109\/LRA.2020.2965855"},{"issue":"3","key":"523_CR22","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/s00500-014-1274-0","volume":"19","author":"C Liu","year":"2015","unstructured":"Liu C, Kroll A. Memetic algorithms for optimal task allocation in multi-robot systems for inspection problems with cooperative tasks. Soft Comput. 2015;19(3):567\u201384.","journal-title":"Soft Comput"},{"key":"523_CR23","doi-asserted-by":"crossref","unstructured":"Mataric MJ. Designing emergent behaviors: from local interactions to collective intelligence. In: Proceedings of the second international conference on from animals to animats 2: simulation of adaptive behavior: simulation of adaptive behavior. MIT Press, Cambridge; 1993. p. 432\u201341.","DOI":"10.7551\/mitpress\/3116.003.0059"},{"key":"523_CR24","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.robot.2016.10.008","volume":"90","author":"E Nunes","year":"2017","unstructured":"Nunes E, Manner M, Mitiche H, Gini M. A taxonomy for task allocation problems with temporal and ordering constraints. Robot Auton Syst. 2017;90:55\u201370.","journal-title":"Robot Auton Syst"},{"key":"523_CR25","volume-title":"Computational complexity","author":"CH Papadimitriou","year":"1993","unstructured":"Computational complexity. Pearson; 1993."},{"key":"523_CR26","doi-asserted-by":"publisher","unstructured":"Ponda SS, Johnson LB, Geramifard A, How JP. Cooperative mission planning for multi-UAV teams, chap.\u00a060. Springer; 2015. p. 1447\u201390. https:\/\/doi.org\/10.1007\/978-90-481-9707-1.","DOI":"10.1007\/978-90-481-9707-1"},{"key":"523_CR27","unstructured":"Pujol-Gonzalez M, Cerquides J, Farinelli A, Meseguer P, Rodriguez-Aguilar JA. Efficient Inter-team task allocation in robocup rescue. In: Proceedings of the 2015 international conference on autonomous agents and multiagent systems (AAMAS '15). International foundation for autonomous agents and multiagent systems; 2015. p. 413\u201321."},{"issue":"8","key":"523_CR28","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1109\/12.30866","volume":"38","author":"K Ramamritham","year":"1989","unstructured":"Ramamritham K, Stankovic JA, Zhao W. Distributed scheduling of tasks with deadlines and resource requirements. IEEE Trans Comput. 1989;38(8):1110\u201323.","journal-title":"IEEE Trans Comput"},{"issue":"9","key":"523_CR29","doi-asserted-by":"publisher","first-page":"1447","DOI":"10.1093\/comjnl\/bxq022","volume":"53","author":"SD Ramchurn","year":"2010","unstructured":"Ramchurn SD, Farinelli A, Macarthur KS, Jennings NR. Decentralized coordination in robocup rescue. Comput J. 2010;53(9):1447\u201361.","journal-title":"Comput J"},{"key":"523_CR30","unstructured":"Ramchurn SD, Polukarov M, Farinelli A, Truong C, Jennings NR. Coalition formation with spatial and temporal constraints. In: Proceedings of the 9th international conference on autonomous agents and multiagent systems: (AAMAS '10). International Foundation for Autonomous Agents and Multiagent Systems, Richland, vol.\u00a03; 2010. p. 1181\u20138."},{"key":"523_CR31","unstructured":"RoboCup Rescue Simulator Manual. RoboCup rescue simulation team. Version 1.3. https:\/\/rescuesim.robocup.org\/resources\/documentation. 2020"},{"issue":"1\u20132","key":"523_CR32","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0004-3702(98)00045-9","volume":"101","author":"O Shehory","year":"1998","unstructured":"Shehory O, Kraus S. Methods for task allocation via agent coalition formation. Artif Intell. 1998;101(1\u20132):165\u2013200.","journal-title":"Artif Intell"},{"key":"523_CR33","doi-asserted-by":"crossref","unstructured":"Stankovic JA, Spuri M, Ramamritham K, Buttazzo GC. Deadline scheduling for real-time systems: EDF and related algorithms, vol. 460. Springer Science & Business Media; 2013. Reprint of the original 1998 edition.","DOI":"10.1007\/978-1-4615-5535-3"},{"key":"523_CR34","doi-asserted-by":"publisher","first-page":"83","DOI":"10.3389\/frobt.2020.00083","volume":"7","author":"D Tarapore","year":"2020","unstructured":"Tarapore D, Gro\u00df R, Zauner KP. Sparse robot swarms: moving swarms to real-world applications. Front Robot AI. 2020;7:83. https:\/\/doi.org\/10.3389\/frobt.2020.00083.","journal-title":"Front Robot AI"},{"key":"523_CR35","unstructured":"Taylor ME, Jain M, Jin Y, Yokoo M, Tambe M. When should there be a \"Me\" in \"Team\"? distributed multi-agent optimization under uncertainty. In: Proceedings of the 9th international conference on autonomous agents and multiagent systems: (AAMAS '10). International Foundation for Autonomous Agents and Multiagent Systems, Richland; 2010. p. 109\u201316"},{"issue":"03","key":"523_CR36","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1142\/S0219525911003104","volume":"14","author":"ME Taylor","year":"2011","unstructured":"Taylor ME, Jain M, Tandon P, Yokoo M, Tambe M. Distributed on-line multi-agent optimization under uncertainty: balancing exploration and exploitation. Adv Complex Syst. 2011;14(03):471\u2013528.","journal-title":"Adv Complex Syst"},{"issue":"9","key":"523_CR37","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1057\/jors.1984.162","volume":"35","author":"T Tsiligirides","year":"1984","unstructured":"Tsiligirides T. Heuristic methods applied to orienteering. J Oper Res Soc. 1984;35(9):797\u2013809.","journal-title":"J Oper Res Soc"},{"key":"523_CR38","volume-title":"Multiagent systems","year":"2013","unstructured":"Weiss G, editor. Multiagent systems. 2nd ed. MIT Press; 2013.","edition":"2"},{"issue":"5","key":"523_CR39","doi-asserted-by":"publisher","first-page":"1042","DOI":"10.1109\/TPDS.2012.213","volume":"24","author":"D Ye","year":"2013","unstructured":"Ye D, Zhang M, Sutanto D. Self-adaptation-based dynamic coalition formation in a distributed agent network: a mechanism and a brief survey. IEEE Trans Parallel Distrib Syst. 2013;24(5):1042\u201351.","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"1\u20132","key":"523_CR40","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.artint.2004.10.004","volume":"161","author":"W Zhang","year":"2005","unstructured":"Zhang W, Wang G, Xing Z, Wittenburg L. Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks. Artif Intell. 2005;161(1\u20132):55\u201387.","journal-title":"Artif Intell"},{"key":"523_CR41","doi-asserted-by":"publisher","unstructured":"Zhou J, Zhao X, Zhang X, Zhao D, Li H. Task allocation for multi-agent systems based on distributed many-objective evolutionary algorithm and greedy algorithm. IEEE Access. 2020;8:19306\u201319318. https:\/\/doi.org\/10.1109\/ACCESS.2020.2967061.","DOI":"10.1109\/ACCESS.2020.2967061"},{"issue":"3","key":"523_CR42","first-page":"73","volume":"17","author":"S Zilberstein","year":"1996","unstructured":"Zilberstein S. Using anytime algorithms in intelligent systems. AI Mag. 1996;17(3):73.","journal-title":"AI Mag"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00523-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-021-00523-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00523-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T17:27:26Z","timestamp":1724693246000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-021-00523-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,23]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["523"],"URL":"https:\/\/doi.org\/10.1007\/s42979-021-00523-w","relation":{},"ISSN":["2662-995X","2661-8907"],"issn-type":[{"value":"2662-995X","type":"print"},{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,23]]},"assertion":[{"value":"22 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The source code of the tests reported in \u201c\u201d to \u201c\u201d and the numerical data used to generate Figs.\u00a0and\u00a0are available at the following URLs:,..","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code and Data Availability"}},{"value":"The authors declare that they have no conflict of interest.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"165"}}