{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T02:06:15Z","timestamp":1787018775824,"version":"3.56.0"},"reference-count":86,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T00:00:00Z","timestamp":1667952000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/100006754","name":"Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF-17-2-0181"],"award-info":[{"award-number":["W911NF-17-2-0181"]}],"id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:p>Effective deployment of multi-robot teams requires solving several interdependent problems at varying levels of abstraction. Specifically, heterogeneous multi-robot systems must answer four important questions: what (task planning), how (motion planning), who (task allocation), and when (scheduling). Although there are rich bodies of work dedicated to various combinations of these questions, a fully integrated treatment of all four questions lies beyond the scope of the current literature, which lacks even a formal description of the complete problem. In this article, we address this absence, first by formalizing this class of multi-robot problems under the banner Simultaneous Task Allocation and Planning with Spatiotemporal Constraints (STAP-STC), and then by proposing a solution that we call Graphically Recursive Simultaneous Task Allocation, Planning, and Scheduling (GRSTAPS). GRSTAPS interleaves task planning, task allocation, scheduling, and motion planning, performing a multi-layer search while effectively sharing information among system modules. In addition to providing a unified solution to STAP-STC problems, GRSTAPS includes individual innovations both in task planning and task allocation. At the task planning level, our interleaved approach allows the planner to abstract away which agents will perform a task using an approach that we refer to as agent-agnostic planning. At the task allocation level, we contribute a search-based algorithm that can simultaneously satisfy planning constraints and task requirements while optimizing the associated schedule. We demonstrate the efficacy of GRSTAPS using detailed ablative and comparative experiments in a simulated emergency-response domain. Results of these experiments conclusively demonstrate that GRSTAPS outperforms both ablative baselines and state-of-the-art temporal planners in terms of computation time, solution quality, and problem coverage.<\/jats:p>","DOI":"10.1177\/02783649211052066","type":"journal-article","created":{"date-parts":[[2021,11,9]],"date-time":"2021-11-09T23:38:53Z","timestamp":1636501133000},"page":"232-256","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":33,"title":["GRSTAPS: Graphically Recursive Simultaneous Task Allocation, Planning, and Scheduling"],"prefix":"10.1177","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0874-0690","authenticated-orcid":false,"given":"Andrew","family":"Messing","sequence":"first","affiliation":[{"name":"Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Glen","family":"Neville","sequence":"additional","affiliation":[{"name":"Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sonia","family":"Chernova","sequence":"additional","affiliation":[{"name":"Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Hutchinson","sequence":"additional","affiliation":[{"name":"Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6635-2637","authenticated-orcid":false,"given":"Harish","family":"Ravichandar","sequence":"additional","affiliation":[{"name":"Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2021,11,9]]},"reference":[{"key":"bibr1-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-018-9817-3"},{"key":"bibr2-02783649211052066","author":"Akbari A","year":"2016","journal-title":"International Conference on Emerging Technologies and Factory Automation"},{"key":"bibr3-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1145\/182.358434"},{"key":"bibr4-02783649211052066","first-page":"39","author":"Andreychuk A","year":"2019","journal-title":"International Joint Conference on Artificial Intelligence"},{"key":"bibr5-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/PACET48583.2019.8956244"},{"key":"bibr6-02783649211052066","author":"Barry J","year":"2013","journal-title":"International Conference on Robotics and Automation"},{"key":"bibr7-02783649211052066","first-page":"51","author":"Bechon P","year":"2014","journal-title":"STAIRS 2014: Proceedings of the 7th European Starting AI Researcher Symposium"},{"key":"bibr8-02783649211052066","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1609\/icaps.v22i1.13509","author":"Benton J","year":"2012","journal-title":"22nd International Conference on Automated Planning and Scheduling"},{"key":"bibr9-02783649211052066","author":"Bohlin R","year":"2000","journal-title":"International Conference on Robotics and Automation (ICRA)"},{"key":"bibr10-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1613\/jair.740"},{"key":"bibr11-02783649211052066","author":"Brafman R","year":"2014","journal-title":"ICAPS DMAP"},{"key":"bibr12-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.07.033"},{"key":"bibr13-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2163434"},{"key":"bibr14-02783649211052066","volume-title":"Principles of Robot Motion","author":"Choset H","year":"2005"},{"key":"bibr15-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-017-0938-8"},{"key":"bibr16-02783649211052066","first-page":"44","author":"Cohen L","year":"2019","journal-title":"Proceedings of the 12th International Symposium on Combinatorial Search, SoCS 2019"},{"key":"bibr17-02783649211052066","author":"Coles A","year":"2018","journal-title":"International Planning Competition 2018 Temporal Track"},{"key":"bibr18-02783649211052066","author":"Crosby M","year":"2013","journal-title":"International Conference on Automated Planning and Scheduling"},{"key":"bibr19-02783649211052066","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2016.XII.002"},{"key":"bibr20-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90006-6"},{"key":"bibr21-02783649211052066","author":"Dornhege C","year":"2009","journal-title":"International Conference on Automated Planning and Scheduling Semantic"},{"key":"bibr22-02783649211052066","author":"Driess D","year":"2019","journal-title":"RSS Workshop on Robust Task and Motion Planning"},{"key":"bibr23-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980160"},{"key":"bibr24-02783649211052066","author":"Faruq F","year":"2018","journal-title":"International Conference on Intelligent Robots and Systems (IROS)"},{"key":"bibr25-02783649211052066","first-page":"396","author":"Flushing E","year":"2014","journal-title":"International Conference on Intelligent Robots and Systems"},{"issue":"9","key":"bibr26-02783649211052066","first-page":"1","volume":"32","author":"Garrett C","year":"2020","journal-title":"The International Journal of Robotics Research"},{"key":"bibr27-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917739114"},{"key":"bibr28-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045564"},{"key":"bibr29-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139583923"},{"key":"bibr30-02783649211052066","first-page":"4863","author":"Gini M","year":"2017","journal-title":"Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)"},{"key":"bibr31-02783649211052066","doi-asserted-by":"publisher","DOI":"10.4114\/ia.v7i19.714"},{"key":"bibr32-02783649211052066","unstructured":"Gomaa M, Prof S, Lakemeyer G (2019) Centralized goal reasoning and scheduling using mixed integer programming for RoboCup Logistics League. Master\u2019s Thesis, Knowledge-based Systems Group, Rheinisch-Westf\u00e4lische Technische Hochschule Aachen."},{"key":"bibr33-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14743-2_26"},{"key":"bibr34-02783649211052066","first-page":"253","volume":"14","author":"Hoffman J","year":"2001","journal-title":"Journal of Artificial Intelligence"},{"key":"bibr35-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973594.ch1"},{"key":"bibr36-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-010-9202-3"},{"key":"bibr37-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980391"},{"key":"bibr38-02783649211052066","first-page":"739","volume":"6","author":"Kitano H","year":"1999","journal-title":"Proceedings of the IEEE International Conference on Systems, Man and Cybernetics"},{"key":"bibr39-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913496484"},{"key":"bibr40-02783649211052066","first-page":"115","author":"Korsah GA","year":"2012","journal-title":"International Conference on Robotics and Automation"},{"key":"bibr41-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2018.2856701"},{"key":"bibr42-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914545811"},{"key":"bibr43-02783649211052066","first-page":"957","author":"Lagriffoul F","year":"2012","journal-title":"IEEE International Conference on Intelligent Robots and Systems"},{"key":"bibr44-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/CCTA41146.2020.9206322"},{"key":"bibr45-02783649211052066","first-page":"220","volume":"1","author":"Lo SY","year":"2018","journal-title":"Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS"},{"key":"bibr46-02783649211052066","first-page":"3684","author":"Lozano-P\u00e9rez T","year":"2014","journal-title":"International Conference on Intelligent Robots and Systems"},{"key":"bibr47-02783649211052066","first-page":"1144","author":"Ma H","year":"2016","journal-title":"Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS"},{"key":"bibr48-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1017\/S0263574718000735"},{"issue":"4","key":"bibr49-02783649211052066","first-page":"13","volume":"20","author":"Marie E","year":"1999","journal-title":"AI Magazine"},{"key":"bibr50-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/SSST.2007.352311"},{"key":"bibr51-02783649211052066","author":"Messing A","year":"2020","journal-title":"The Workshop on the Algorithmic Foundations of Robotics (WAFR)"},{"key":"bibr52-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.2976329"},{"key":"bibr53-02783649211052066","first-page":"1","author":"Neville G","year":"2021","journal-title":"IROS 2021"},{"key":"bibr54-02783649211052066","first-page":"7978","author":"Neville G","year":"2020","journal-title":"IEEE International Conference on Intelligent Robots and Systems"},{"key":"bibr55-02783649211052066","first-page":"1847","author":"Nikou A","year":"2017","journal-title":"Proceedings of the American Control Conference"},{"key":"bibr56-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4295"},{"key":"bibr57-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2631593"},{"key":"bibr58-02783649211052066","volume":"2","author":"Ramchurn SD","year":"2010","journal-title":"International Joint Conference on Autonomous Agents and Multiagent Systems"},{"key":"bibr59-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-020-09461-y"},{"key":"bibr60-02783649211052066","doi-asserted-by":"publisher","DOI":"10.3390\/s16071018"},{"key":"bibr61-02783649211052066","author":"Sapena O","year":"2018","journal-title":"International Planning Competition 2018 Temporal Track"},{"key":"bibr62-02783649211052066","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-140613"},{"key":"bibr63-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-73008-0_18"},{"key":"bibr64-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918774135"},{"key":"bibr65-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.2974695"},{"key":"bibr66-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.11.006"},{"key":"bibr67-02783649211052066","author":"Shekhar S","year":"2020","journal-title":"Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018)"},{"key":"bibr68-02783649211052066","author":"Shome R","year":"2019","journal-title":"International Symposium on Multi-Robot and Multi-Agent Systems"},{"key":"bibr69-02783649211052066","first-page":"639","author":"Srivastava S","year":"2014","journal-title":"International Conference on Robotics and Automation"},{"key":"bibr70-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.08.007"},{"key":"bibr71-02783649211052066","first-page":"625","volume":"603","author":"Stroupe AW","year":"2005","journal-title":"European Space Agency Special Publication"},{"key":"bibr72-02783649211052066","author":"Sucan I","year":"2010","journal-title":"IEEE Robotics and Automation Magazine"},{"key":"bibr73-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-014-0540-2"},{"key":"bibr74-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1145\/3128584"},{"key":"bibr75-02783649211052066","first-page":"1930","author":"Toussaint M","year":"2015","journal-title":"International Joint Conference on Artificial Intelligence"},{"key":"bibr76-02783649211052066","author":"Toussaint M","year":"2017","journal-title":"International Conference on Robotics and Automation"},{"key":"bibr77-02783649211052066","first-page":"29","author":"To\u017ei\u010dka J","year":"2015","journal-title":"Competition of Distributed and Multi-Agent Planners"},{"key":"bibr78-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913487931"},{"key":"bibr79-02783649211052066","first-page":"9","author":"Umay I","year":"2019","journal-title":"International Symposium on Robotic and Sensors Environments"},{"key":"bibr80-02783649211052066","first-page":"528","volume":"12","author":"Vega-Brown W","year":"2016","journal-title":"Algorithmic Foundations of Robotics"},{"key":"bibr81-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2019.10.010"},{"key":"bibr82-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2019.03.005"},{"issue":"4","key":"bibr83-02783649211052066","first-page":"27","volume":"15","author":"Weld DS","year":"1994","journal-title":"AI magazine"},{"key":"bibr84-02783649211052066","first-page":"6451","author":"Whitbrook A","year":"2015","journal-title":"IEEE International Conference on Intelligent Robots and Systems"},{"key":"bibr85-02783649211052066","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1609\/icaps.v30i1.6677","volume":"30","author":"Zhang H","year":"2020","journal-title":"Proceedings International Conference on Automated Planning and Scheduling, ICAPS"},{"key":"bibr86-02783649211052066","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2015.2418052"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211052066","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649211052066","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211052066","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211052066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:53Z","timestamp":1777457813000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649211052066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,9]]},"references-count":86,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10.1177\/02783649211052066"],"URL":"https:\/\/doi.org\/10.1177\/02783649211052066","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,9]]}}}