{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T06:16:43Z","timestamp":1783059403948,"version":"3.54.6"},"reference-count":49,"publisher":"SAGE Publications","issue":"8","license":[{"start":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T00:00:00Z","timestamp":1760572800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100020950","name":"National Science and Technology Council","doi-asserted-by":"publisher","award":["112-2221-E-008-075"],"award-info":[{"award-number":["112-2221-E-008-075"]}],"id":[{"id":"10.13039\/501100020950","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020950","name":"National Science and Technology Council","doi-asserted-by":"publisher","award":["113-2221-E-008-101-MY2"],"award-info":[{"award-number":["113-2221-E-008-101-MY2"]}],"id":[{"id":"10.13039\/501100020950","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":[[2026,7]]},"abstract":"<jats:p>\n                    The multi-robot search problem is challenging since it involves task allocation, minimal routing, and maximal coverage problems, which are NP-hard. To solve this problem with theoretical guarantees, it is reformulated as a maximal coverage problem subject to the intersection of matroid constraints. The coverage problem is solved by utilizing its submodularity. Additionally, the workload balance is considered to enhance search efficiency. The intersection matroid is composed of a routing constraint and a clustering constraint. The proposed algorithm, Multi-Robot Search with Matroid constraints (MRSM), achieves\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" overflow=\"scroll\">\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>3<\/mml:mn>\n                        <mml:mrow>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                        <mml:mover accent=\"true\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mi>P<\/mml:mi>\n                            <mml:mi>T<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:mo>\u02dc<\/mml:mo>\n                        <\/mml:mover>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" overflow=\"scroll\">\n                        <mml:mrow>\n                          <mml:mover accent=\"true\">\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                              <mml:mi>P<\/mml:mi>\n                              <mml:mi>T<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u02dc<\/mml:mo>\n                          <\/mml:mover>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    is the optimal performance under spanning-tree structures. Furthermore, Dynamic MRSM (D-MRSM) and MRSM with Hexagonal Packing (MRSM-Hex) are proposed for unknown and large-scale environments, respectively. The experiment results show that the MRSM approaches outperform state-of-the-art methods in terms of expected time to detection in multi-robot search problems and scale effectively for large search spaces.\n                  <\/jats:p>","DOI":"10.1177\/02783649251379517","type":"journal-article","created":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T09:54:58Z","timestamp":1760608498000},"page":"1145-1164","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["Multi-robot search in 3D environments using submodularity with matroid intersection constraints"],"prefix":"10.1177","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5467-2254","authenticated-orcid":false,"given":"Yan-Shuo","family":"Li","sequence":"first","affiliation":[{"name":"National Central University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7818-5821","authenticated-orcid":false,"given":"Kuo-Shih","family":"Tseng","sequence":"additional","affiliation":[{"name":"National Central University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2025,10,16]]},"reference":[{"key":"e_1_3_6_2_1","doi-asserted-by":"crossref","unstructured":"Aironi C Cornell S Squartini S (2022) Tackling the linear sum assignment problem with graph neural networks. In: International Conference on Applied Intelligence and Informatics Reggio Calabria Italy 1-3 September 90\u2013101.","DOI":"10.1007\/978-3-031-24801-6_7"},{"key":"e_1_3_6_3_1","first-page":"1134","volume-title":"International Conference on Machine Learning","author":"Breuer A","year":"2020","unstructured":"Breuer A, Balkanski E, Singer Y (2020) The fast algorithm for submodular maximization. In: International Conference on Machine Learning, IEEE, 1134\u20131143."},{"key":"e_1_3_6_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-018-9778-6"},{"key":"e_1_3_6_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2008.931633"},{"key":"e_1_3_6_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_3_6_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2024.3371254"},{"key":"e_1_3_6_8_1","first-page":"427","article-title":"Adaptive submodularity: theory and applications in active learning and stochastic optimization","volume":"42","author":"Golovin D","year":"2011","unstructured":"Golovin D, Krause A (2011) Adaptive submodularity: theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research 42: 427\u2013486.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"e_1_3_6_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.04.059"},{"key":"e_1_3_6_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAR.1997.620182"},{"key":"e_1_3_6_11_1","doi-asserted-by":"publisher","unstructured":"Jocher G Chaurasia A Stoken A et al (2022) ultralytics\/yolov5: v7.0 - yolov5 sota realtime instance segmentation. DOI:10.5281\/ZENODO.7347926.\u00e8.","DOI":"10.5281\/ZENODO.7347926.\u00e8"},{"key":"e_1_3_6_12_1","first-page":"5622","volume-title":"The Matroid Team Surviving Orienteers Problem: Constrained Routing of Heterogeneous Teams with Risky Traversal","author":"Jorgensen S","year":"2017","unstructured":"Jorgensen S, Chen RH, Milam MB, et al. (2017a) The Matroid Team Surviving Orienteers Problem: Constrained Routing of Heterogeneous Teams with Risky Traversal. IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), 5622\u20135629."},{"key":"e_1_3_6_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/IRC.2017.49"},{"key":"e_1_3_6_14_1","unstructured":"Kaempfer Y Wolf L (2018) Learning the multiple traveling salesmen problem with permutation invariant pooling networks. arXiv preprint arXiv:1803.09621."},{"key":"e_1_3_6_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_3_6_16_1","unstructured":"Kool W van Hoof H Welling M (2019) Attention learn to solve routing problems. International Conference on Learning Representations May 6-May 9 2019 New Orleans LA USA."},{"key":"e_1_3_6_17_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913496484"},{"key":"e_1_3_6_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70322-4"},{"key":"e_1_3_6_19_1","first-page":"1650","article-title":"Near-optimal observation selection using submodular functions","volume":"7","author":"Krause A","year":"2007","unstructured":"Krause A, Guestrin C (2007) Near-optimal observation selection using submodular functions. Association for the Advancement of Artificial Intelligence (AAAI) 7: 1650\u20131654.","journal-title":"Association for the Advancement of Artificial Intelligence (AAAI)"},{"key":"e_1_3_6_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_3_6_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.3007445"},{"key":"e_1_3_6_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/LWC.2018.2843359"},{"key":"e_1_3_6_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA57147.2024.10610393"},{"key":"e_1_3_6_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2023.3243792"},{"key":"e_1_3_6_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2018.8460215"},{"key":"e_1_3_6_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2019.2925301"},{"key":"e_1_3_6_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.107"},{"key":"e_1_3_6_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICUAS48674.2020.9213891"},{"key":"e_1_3_6_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73238-9"},{"key":"e_1_3_6_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2014.10.004"},{"key":"e_1_3_6_31_1","first-page":"575","article-title":"Vision-based autonomous uav navigation and landing for urban search and rescue","author":"Mittal M","year":"2019","unstructured":"Mittal M, Mohan R, Burgard W, et al. (2019) Vision-based autonomous uav navigation and landing for urban search and rescue. The International Symposium of Robotics Research 575\u2013592.","journal-title":"The International Symposium of Robotics Research"},{"key":"e_1_3_6_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2019.2928774"},{"key":"e_1_3_6_33_1","first-page":"1","volume-title":"IEEE Transactions on Cybernetics","author":"Mohamed SC","year":"2022","unstructured":"Mohamed SC, Fung A, Nejat G (2022) A multirobot person search system for finding multiple dynamic users in human-centered environments. IEEE Transactions on Cybernetics. IEEE, 1\u201313."},{"key":"e_1_3_6_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_6_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA46639.2022.9812370"},{"key":"e_1_3_6_36_1","first-page":"652","volume-title":"IEEE Conference on Computer Vision and Pattern Recognition","author":"Qi CR","year":"2017","unstructured":"Qi CR, Su H, Mo K, et al. (2017) Pointnet: deep learning on point sets for 3d classification and segmentation. In: IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 652\u2013660."},{"key":"e_1_3_6_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0323-0"},{"key":"e_1_3_6_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2018.2794608"},{"key":"e_1_3_6_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3188904"},{"key":"e_1_3_6_40_1","first-page":"2204","volume-title":"International Joint Conference on Artifical Intelligence (IJCAI)","author":"Singh A","year":"2007","unstructured":"Singh A, Krause A, Guestrin C, et al. (2007) Efficient planning of informative paths for multiple robots. International Joint Conference on Artifical Intelligence (IJCAI). 2204\u20132211."},{"key":"e_1_3_6_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS51168.2021.9636675"},{"key":"e_1_3_6_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSRR.2019.8848962"},{"key":"e_1_3_6_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989038"},{"key":"e_1_3_6_44_1","doi-asserted-by":"crossref","unstructured":"Zhang H Vorobeychik Y (2016) Submodular optimization with routing constraints. In: Association for the Advancement of Artificial Intelligence Phoenix Arizona February 12-17 2016 Vol. 30.","DOI":"10.1609\/aaai.v30i1.10066"},{"key":"e_1_3_6_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3146912"},{"key":"e_1_3_6_46_1","first-page":"3","article-title":"Nonmonotone submodular maximization under routing constraints","author":"Zhang H","year":"2023","unstructured":"Zhang H, Li R, Wu Z, et al. (2023) Nonmonotone submodular maximization under routing constraints. National Conference of Theoretical Computer Science 3\u201317.","journal-title":"National Conference of Theoretical Computer Science"},{"key":"e_1_3_6_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS51168.2021.9636737"},{"key":"e_1_3_6_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3051563"},{"key":"e_1_3_6_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2023.3236945"},{"key":"e_1_3_6_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICUAS48674.2020.9214062"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649251379517","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649251379517","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649251379517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T05:24:22Z","timestamp":1783056262000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649251379517"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,16]]},"references-count":49,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["10.1177\/02783649251379517"],"URL":"https:\/\/doi.org\/10.1177\/02783649251379517","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,16]]}}}