{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T09:08:29Z","timestamp":1774602509772,"version":"3.50.1"},"reference-count":56,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T00:00:00Z","timestamp":1728604800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62173314"],"award-info":[{"award-number":["62173314"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U2013601"],"award-info":[{"award-number":["U2013601"]}],"id":[{"id":"10.13039\/501100001809","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":[[2025,4]]},"abstract":"<jats:p>Existing methods for the task allocation and planning (TAP) of multi-robot systems with temporal logic specifications mainly rely on optimization-based approaches or graph search techniques applied to the product automaton. However, these methods suffer from high computational cost and scale poorly with the number of robots and the complexity of temporal logic tasks, thus limiting the applicability in real-time implementation, especially for large multi-robot systems. To address these challenges, this work develops a novel TAP framework that can solve reactive temporal logic planning problems for large-scale heterogeneous multi-robot systems (HMRS) in real time. Specifically, we develop a planning decision tree (PDT) to represent the task progression and task allocation specialized for HMRS with temporal logic specifications. Based on the PDT, we develop two key search algorithms\u2014the planning decision tree search (PDTS) and the interactive planning decision tree search (IPDTS)\u2014where PDTS generates an offline plan which will be modified online by PDTS and IPDTS jointly to enable fast reactive planning if environmental changes or temporary tasks occur. Such a design can generate satisfying plan for HMRS with multiple orders of magnitude more robots than those that existing methods can manipulate. Rigorous analysis shows that the PDT-based planning is feasible (i.e., the generated plan is applicable) and complete (i.e., a feasible plan, if exits, is guaranteed to be found). The algorithm complexity further indicates that the solution time is only linearly proportional to the robot numbers and types. Simulation and experiment results demonstrate that reactive plan can be generated for large HMRS in real-time, which outperforms the state-of-the-art methods.<\/jats:p>","DOI":"10.1177\/02783649241278372","type":"journal-article","created":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T23:46:46Z","timestamp":1728690406000},"page":"640-664","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":15,"title":["Real-time reactive task allocation and planning of large heterogeneous multi-robot systems with temporal logic specifications"],"prefix":"10.1177","volume":"44","author":[{"given":"Ziyang","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Automation, University of Science and Technology of China, Hefei, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2069-9544","authenticated-orcid":false,"given":"Zhen","family":"Kan","sequence":"additional","affiliation":[{"name":"Department of Automation, University of Science and Technology of China, Hefei, China"}]}],"member":"179","published-online":{"date-parts":[[2024,10,11]]},"reference":[{"key":"e_1_3_4_2_1","volume-title":"Principles of Model Checking","author":"Baier C","year":"2008","unstructured":"Baier C, Katoen JP (2008) Principles of Model Checking. Cambridge, MA: MIT Press."},{"key":"e_1_3_4_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA40945.2020.9197066"},{"key":"e_1_3_4_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2007.339624"},{"key":"e_1_3_4_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCSYS.2020.3032845"},{"key":"e_1_3_4_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3101544"},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2020.3006967"},{"key":"e_1_3_4_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2021.3138704"},{"key":"e_1_3_4_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2024.3401166"},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2727514"},{"key":"e_1_3_4_11_1","volume-title":"Model Checking","author":"Clarke EM","year":"1999","unstructured":"Clarke EM, Grumberg O, Peled D (1999) Model Checking. Cambridge, MA: MIT Press."},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2018.8594404"},{"key":"e_1_3_4_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-88885-5_11"},{"key":"e_1_3_4_14_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-091420-084139"},{"key":"e_1_3_4_15_1","first-page":"53","volume-title":"Computer Aided Verification. CAV 2001. Lecture Notes in Computer Science","author":"Gastin P","year":"2001","unstructured":"Gastin P, Oddoux D (2001) Fast LTL to B\u00fcchi automata translation. Computer Aided Verification. CAV 2001. Lecture Notes in Computer Science. Berlin: Springer, 53\u201365."},{"key":"e_1_3_4_16_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914546174"},{"key":"e_1_3_4_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2016.2628389"},{"key":"e_1_3_4_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2016.2555581"},{"key":"e_1_3_4_19_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364920983353"},{"key":"e_1_3_4_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2017.8206426"},{"key":"e_1_3_4_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2020.3013916"},{"key":"e_1_3_4_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC49753.2023.10383968"},{"key":"e_1_3_4_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2015.10.035"},{"key":"e_1_3_4_24_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364920913922"},{"key":"e_1_3_4_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA40945.2020.9197570"},{"key":"e_1_3_4_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA46639.2022.9811980"},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2035776"},{"key":"e_1_3_4_28_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011254632723"},{"key":"e_1_3_4_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2019.103289"},{"key":"e_1_3_4_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942756"},{"key":"e_1_3_4_31_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364919856695"},{"key":"e_1_3_4_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2021.3130794"},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3143304"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.23919\/ACC55779.2023.10156237"},{"key":"e_1_3_4_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2022.3181948"},{"key":"e_1_3_4_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2021.3061983"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783649211052066"},{"key":"e_1_3_4_38_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915594679"},{"key":"e_1_3_4_39_1","doi-asserted-by":"publisher","DOI":"10.23919\/ACC.2018.8431866"},{"key":"e_1_3_4_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2020.3039484"},{"key":"e_1_3_4_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2019.2957669"},{"key":"e_1_3_4_42_1","article-title":"Hybrid feedback for autonomous navigation in environments with arbitrary non-convex obstacles","author":"Sawant M","year":"2023","unstructured":"Sawant M, Tayebi A, Polushin I (2023) Hybrid feedback for autonomous navigation in environments with arbitrary non-convex obstacles. arXiv preprint arXiv:2304.10598.","journal-title":"arXiv preprint arXiv:2304.10598"},{"key":"e_1_3_4_43_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918774135"},{"key":"e_1_3_4_44_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918774135"},{"key":"e_1_3_4_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/CASE48305.2020.9216991"},{"key":"e_1_3_4_46_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783649231204659"},{"key":"e_1_3_4_47_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911417911"},{"key":"e_1_3_4_48_1","article-title":"Ltlf synthesis under partial observability: from theory to practice","author":"Tabajara LM","year":"2020","unstructured":"Tabajara LM, Vardi MY (2020) Ltlf synthesis under partial observability: from theory to practice. arXiv preprint arXiv:2009.10875.","journal-title":"arXiv preprint arXiv:2009.10875"},{"key":"e_1_3_4_49_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914537008"},{"key":"e_1_3_4_50_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913487931"},{"key":"e_1_3_4_51_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913519000"},{"key":"e_1_3_4_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989177"},{"key":"e_1_3_4_53_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364920918919"},{"key":"e_1_3_4_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9561958"},{"key":"e_1_3_4_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2021.3088764"},{"key":"e_1_3_4_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2023.10.959"},{"key":"e_1_3_4_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/CASE49997.2022.9926658"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241278372","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649241278372","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241278372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T10:43:17Z","timestamp":1747737797000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649241278372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,11]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["10.1177\/02783649241278372"],"URL":"https:\/\/doi.org\/10.1177\/02783649241278372","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,11]]}}}