{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T05:46:58Z","timestamp":1767764818666,"version":"3.48.0"},"reference-count":18,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T00:00:00Z","timestamp":1767571200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["42401512"],"award-info":[{"award-number":["42401512"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotics"],"abstract":"<jats:p>For multi-robot cooperative coverage, an effective spatial division strategy is essential to ensure balanced and spatially continuous task regions for each robot. Traditional grid-based partitioning approaches like DARP (Divide Areas based on Robots\u2019 Positions) and TASR (Task Allocation based on Spatial Regions) often generate discontinuous sub-regions and imbalanced workloads, particularly in irregular or fragmented task spaces. To mitigate these issues, this paper introduces HGTA (Hexagonal Grid-based Task Allocation), a novel method that employs hexagonal tessellation for environmental representation. The hexagonal grid structure provides uniform neighbor connectivity and minimizes boundary fragmentation, yielding smoother partitions. HGTA integrates a multi-stage wavefront expansion algorithm with an iterative region-correction mechanism, jointly ensuring spatial contiguity and load equilibrium across robots. Extensive evaluations in 2D environments with varying obstacle densities and robot distributions show that HGTA enhances spatial continuity\u2014achieving improvements of 18.2% in connectivity and 17.8% in boundary smoothness over DARP, and 7.5% and 9.5% over TASR, respectively\u2014while also improving workload balance (variance reduction up to 18.5%) without compromising computational efficiency. The core contribution lies in the synergistic coupling of hexagonal tessellation, wavefront expansion, and dynamic correction, a design that fundamentally advances partition smoothness and convergence speed. HGTA thus offers a robust foundation for multi-robot cooperative coverage, area surveillance, and underwater search applications where connected and balanced partitions are critical.<\/jats:p>","DOI":"10.3390\/robotics15010015","type":"journal-article","created":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T10:03:48Z","timestamp":1767607428000},"page":"15","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["HGTA: A Hexagonal Grid-Based Task Allocation Method for Multi-Robot Coverage in Known 2D Environments"],"prefix":"10.3390","volume":"15","author":[{"given":"Weixing","family":"Xia","sequence":"first","affiliation":[{"name":"Naval Submarine Academy, Qingdao 266199, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shihui","family":"Shen","sequence":"additional","affiliation":[{"name":"Naval Submarine Academy, Qingdao 266199, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ping","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Intelligent Systems Science and Engineering, Harbin Engineering University, Harbin 150001, China"},{"name":"Qingdao Innovation and Development Center, Harbin Engineering University, Qingdao 266404, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3140-3462","authenticated-orcid":false,"given":"Jinjin","family":"Yan","sequence":"additional","affiliation":[{"name":"College of Intelligent Systems Science and Engineering, Harbin Engineering University, Harbin 150001, China"},{"name":"Qingdao Innovation and Development Center, Harbin Engineering University, Qingdao 266404, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2026,1,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Arjun, K., Parlevliet, D., Wang, H., and Yazdani, A. (2025). Optimizing Coalition Formation Strategies for Scalable Multi-Robot Task Allocation: A Comprehensive Survey of Methods and Mechanisms. Robotics, 14.","DOI":"10.20944\/preprints202505.0606.v1"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Fikri, A.A., and Matsunaga, N. (2025, January 17\u201319). B-FAME: An Adaptive Area Division Algorithm for Multi-Robot Exploration and Mapping. Proceedings of the 2025 IEEE International Conference on Advanced Robotics and its Social Impacts (ARSO), Osaka, Japan.","DOI":"10.1109\/ARSO64737.2025.11124985"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Espina, M.V., Grech, R., De Jager, D., Remagnino, P., Iocchi, L., Marchetti, L., Nardi, D., Monekosso, D., Nicolescu, M., and King, C. (2011). Multi-robot teams for environmental monitoring. Innovations in Defence Support Systems\u20133: Intelligent Paradigms in Security, Springer.","DOI":"10.1007\/978-3-642-18278-5_8"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Cai, C., Chen, J., Yan, Q., and Liu, F. (2022). A multi-robot coverage path planning method for maritime search and rescue using multiple AUVs. Remote Sens., 15.","DOI":"10.3390\/rs15010093"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Zhang, F., Liu, J., and Wang, H. (2025, January 17\u201319). Research on Multi-Robot Regional Search Planning Method Based on Voronoi Diagram. Proceedings of the 2025 40th Youth Academic Annual Conference of Chinese Association of Automation (YAC), Zhengzhou, China.","DOI":"10.1109\/YAC66630.2025.11149758"},{"key":"ref_6","first-page":"4261","article-title":"From simulations to reality: Enhancing multi-robot exploration for urban search and rescue","volume":"17","author":"Kashyap","year":"2025","journal-title":"Int. J. Inf. Technol."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"111474","DOI":"10.1016\/j.knosys.2024.111474","article-title":"An effective collaboration evolutionary algorithm for multi-robot task allocation and scheduling in a smart farm","volume":"289","author":"Guo","year":"2024","journal-title":"Knowl.-Based Syst."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1301","DOI":"10.1108\/EC-09-2023-0612","article-title":"Balanced task allocation and motion planning of a multi-robot system under fuzzy time windows","volume":"41","author":"Xidias","year":"2024","journal-title":"Eng. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chen, Y., Zeng, Z., Lai, Z., Jiang, W., Lu, H., Zhang, H., and Wang, Y. (2025). Dynamic Task-Priority Coverage Planning for Efficient Multi-Robot Collaboration. IEEE Trans. Ind. Electron., 1\u201312.","DOI":"10.1109\/TIE.2025.3594447"},{"key":"ref_10","unstructured":"Yan, J., Wang, P., Han, H., and Huang, R. (2024, January 5\u20138). TASR: A Task Allocation Approach for a Swarm of Robots in 2D Known Environments. Proceedings of the 2024 14th Asian Control Conference (ASCC), Dalian, China."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Yang, T., Du, X., Zhang, B., Wang, X., Zhang, Z., and Wu, C. (2025). Coverage Path Planning Based on Region Segmentation and Path Orientation Optimization. Agriculture, 15.","DOI":"10.3390\/agriculture15141479"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Xu, J., and Mo, L. (2025, January 16\u201319). A Multi-Robot Indoor Coverage Path Planning Method Based on the Improved BCD Segmentation. Proceedings of the 2025 37th Chinese Control and Decision Conference (CCDC), Xiamen, China.","DOI":"10.1109\/CCDC65474.2025.11091206"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Wang, Y., Gu, N., Kang, T., Wang, H., Wang, D., and Peng, Z. (2024, January 18\u201320). Distributed Auction-Based Target Assignment for Formation Reconfiguration of Unmanned Surface Vehicles Subject to Kinematic Constraints. Proceedings of the 2024 9th International Conference on Automation, Control and Robotics Engineering (CACRE), Jeju Island, Republic of Korea.","DOI":"10.1109\/CACRE62362.2024.10635051"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1109\/TASE.2024.3367237","article-title":"An end-to-end deep reinforcement learning based modular task allocation framework for autonomous mobile systems","volume":"22","author":"Ma","year":"2024","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"4464","DOI":"10.1109\/LRA.2022.3148489","article-title":"Hierarchical planning for heterogeneous multi-robot routing problems via learned subteam performance","volume":"7","author":"Banfi","year":"2022","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_16","first-page":"1","article-title":"A Systematic Literature Review on Multi-Robot Task Allocation","volume":"57","author":"Athira","year":"2024","journal-title":"Acm Comput. Surv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1007\/s10846-016-0461-x","article-title":"DARP: Divide areas algorithm for optimal multi-robot coverage path planning","volume":"86","author":"Kapoutsis","year":"2017","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"4404","DOI":"10.1109\/LRA.2025.3551078","article-title":"MAC-Planner: A Novel Task Allocation and Path Planning Framework for Multi-Robot Online Coverage Processes","volume":"10","author":"Wang","year":"2025","journal-title":"IEEE Robot. Autom. Lett."}],"container-title":["Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2218-6581\/15\/1\/15\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T05:14:32Z","timestamp":1767762872000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2218-6581\/15\/1\/15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,5]]},"references-count":18,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,1]]}},"alternative-id":["robotics15010015"],"URL":"https:\/\/doi.org\/10.3390\/robotics15010015","relation":{},"ISSN":["2218-6581"],"issn-type":[{"type":"electronic","value":"2218-6581"}],"subject":[],"published":{"date-parts":[[2026,1,5]]}}}