Systems Engineering and Electronics ›› 2025, Vol. 47 ›› Issue (11): 3708-3720.doi: 10.12305/j.issn.1001-506X.2025.11.19
• Systems Engineering • Previous Articles
Multi-USV cooperative task planning based on clustering optimization algorithm
Wenzhao YU1,2,3,4, Jingchao QIAO1,2, Zhe DU1,2,*(
), Zhukai XING5, Xinyuan WAN2
- 1. Key Laboratory of High Performance Ship Technology of Ministry of Education，Wuhan University of Technology，Wuhan 430062，China
2. School of Naval Architecture，Ocean and Energy Power Engineering，Wuhan University of Technology，Wuhan 430062，China
3. Centre of Excellence in Modelling and Simulation for Next Generation Ports，Department of Industrial Systems Engineering and Management，National University of Singapore，Singapore City 119077，Singapore
4. Sanya Science and Education Innovation Park，Wuhan University of Technology，Sanya 572000，China
5. School of Ship Engineering，Dalian University of Technology，Dalian 116024，China
-
Received:2025-04-30Online:2025-11-25Published:2025-12-08 -
Contact:Zhe DU E-mail:duzhe@whut.edu.cn
CLC Number:
Cite this article
Wenzhao YU, Jingchao QIAO, Zhe DU, Zhukai XING, Xinyuan WAN. Multi-USV cooperative task planning based on clustering optimization algorithm[J]. Systems Engineering and Electronics, 2025, 47(11): 3708-3720.
share this article
Fig.1
Schematic diagram of multi-task allocation and path planning for isomorphic unmanned surface vessels cluster"
Fig.1
Fig.2
Technical route of improved ACO allocation algorithm based on DBSCAN"
Fig.2
Fig.3
Division method of artificial ant plans"
Fig.3
Fig.4
Schematic diagram of virtual potential field force on unmanned surface vessel in improved APF method"
Fig.4
Table 1
Parameters of task allocation algorithm"
| 参数 | 取值 | 参数 | 取值 | |
| 56 | 0.15 | |||
| 2 | 18 | |||
| 2 | 1 | |||
| 5 | 200 | |||
| 1 | — | — |
Table 1
Table 2
Parameters of path planning algorithm"
| 参数 | 取值 | 参数 | 取值 | |
| 1 000 | 20 | |||
| 10 | 2 | |||
| 0.5 | 0.002 5 | |||
| 0.275 | 6 | |||
| 0.000 3 | 0.038 2 | |||
| 5.116 | — | — |
Table 2
Table 3
Setting of initial position of tasks"
| 任务 | 对应坐标/m | 任务 | 对应坐标/m | |
| T1 | （81,113） | T15 | （462,167） | |
| T2 | （136,55） | T16 | （260,263） | |
| T3 | （221,78） | T17 | （244,322） | |
| T4 | （290,54） | T18 | （263,321） | |
| T5 | （146,135） | T19 | （348,243） | |
| T6 | （172,204） | T20 | （467,261） | |
| T7 | （208,139） | T21 | （463,229） | |
| T8 | （242,157） | T22 | （427,264） | |
| T9 | （321,209） | T23 | （458,335） | |
| T10 | （146,351） | T24 | （203,430） | |
| T11 | （126,394） | T25 | （242,402） | |
| T12 | （413,78） | T26 | （360,364） | |
| T13 | （363,156） | T27 | （385,383） | |
| T14 | （395,184） | — | — |
Table 3
Table 4
Setting of obstacles"
| 障碍物 | 圆心坐标/m | 障碍物半径/m |
| O1 | （185,90） | 25 |
| O2 | （110,150） | 25 |
| O3 | （195,275） | 45 |
| O4 | （350,100） | 40 |
| O5 | （360,300） | 15 |
Table 4
Fig.5
Setting of simulation scenario"
Fig.5
Fig.6
Schematic diagram of clustering results for task points"
Fig.6
Fig.7
Schematic diagram of division result of task point clusters"
Fig.7
Fig.8
Schematic diagram of task allocation result without search angle constraint"
Fig.8
Fig.9
Schematic diagram of task allocation result with search angle constraint"
Fig.9
Fig.10
Diagram of voyage cost variation of each unmanned surface vessel with search angle constraint"
Fig.10
Table 5
Comparison of task allocation sequences with and without search angle constraint"
| 无人艇 | 有/无搜索角约束 | 任务分配计划 | 转角值/rad |
| V1 | 无 | 1→4→8→9→19→20→21→28→27→14→13 | 10.355 |
| 有 | 1→4→8→9→19→21→28→27→14→13→20 | 7.427 | |
| V2 | 无 | 2→5→6→10→11→12→22→29→30 | 4.824 |
| 有 | 2→5→6→10→11→12→22→29→30 | 4.824 | |
| V3 | 无 | 3→7→15→16→17→18→24→23→25→26 | 9.849 |
| 有 | 3→7→15→16→17→18→24→23→26→25 | 9.176 |
Table 5
Table 6
Performance comparison of two algorithms"
| 任务分配算法 | 完成任务数量 | 交叉点个数 | 预设路径长度/m |
| 改进ACO[ | 30 | 3 | 810.1 |
| 本文算法 | 30 | 0 | 817.6 |
Table 6
Fig.11
Path planned by APF method"
Fig.11
Fig.12
Path planned after smoothed by cubic Hermite curve"
Fig.12
Fig.13
Comparison chart of enlarged area 1"
Fig.13
Fig.14
Comparison chart of enlarged area 2"
Fig.14
Fig.15
Comparison chart of enlarged area 3"
Fig.15
Fig.16
Comparison chart of enlarged area 4"
Fig.16
Table 7
Comparison between path curvature radius and minimum turning radius"
| 参数 | 放大区域 | |||
| 1 | 2 | 3 | 4 | |
| 回转角度/（°） | 89.89 | 32.79 | 82.72 | 149.48 |
| 纵向速度/（m/s） | 0.55 | 0.84 | 0.59 | 0.55 |
| 最小回转半径 | 4.31 | 6.54 | 4.59 | 4.30 |
| APF法的曲率半径 | 0 | 0 | 0 | 0 |
| 本文方法的曲率半径 | 5.45 | 10.53 | 5.71 | 7.17 |
Table 7
| 1 | 孔维玮, 冯伟强, 诸葛文章, 等. 美军大中型水面无人艇发展现状及启示[J]. 指挥控制与仿真, 2022, 44 (5): 14- 18. |
| KONG W W, FENG W Q, ZHUGE W Z, et al. Development and enlightenment of large and medium-sized unmanned surface vehicles of the US navy[J]. Command Control and Simulation, 2022, 44 (5): 14- 18. | |
| 2 | 齐小刚, 李博, 范英盛, 等. 多约束下多无人机的任务规划研究综述[J]. 智能系统学报, 2020, 15 (2): 204- 217. |
| QI X G, LI B, FAN Y S, et al. A survey of mission planning on UAVs systems based on multiple constraints[J]. CAAI Transactions on Intelligent Systems, 2020, 15 (2): 204- 217. | |
| 3 | 毕文豪, 张梦琦, 高飞, 等. 无人机集群任务分配技术研究综述[J]. 系统工程与电子技术, 2024, 46 (3): 922- 934. |
| BI W H, ZHANG M Q, GAO F, et al. Review on UAV swarm task allocation technology[J]. Systems Engineering and Electronics, 2024, 46 (3): 922- 934. | |
| 4 |
ZHUANG J Y, LONG L Y, ZHANG L, et al. Research on task allocation for multi-type task of unmanned surface vehicles[J]. Ocean Engineering, 2024, 308, 118321.
doi: 10.1016/j.oceaneng.2024.118321 |
| 5 |
BI W H, ZHANG M Q, CHEN H, et al. Cooperative task allocation method for air-sea heterogeneous unmanned system with an application to ocean environment information monitoring[J]. Ocean Engineering, 2024, 309, 118496.
doi: 10.1016/j.oceaneng.2024.118496 |
| 6 | ZHANG Y N, TIAN X, LI Y N, et al. Ant colony algorithm based unmanned surface vehicles task allocation design and implementation[C]//Proc.of the IEEE 4th International Conference on Computer Engineering and Intelligent Control, 2023: 274−277. |
| 7 | YI N, XU J J, YAN L M, et al. Task optimization and scheduling of distributed cyber-physical system based on improved ant colony algorithm[J]. Future Generation Computer Systems, 2020, 109 (1): 134- 148. |
| 8 | LIU Y, WU X, GUO Y K, et al. The multiple unmanned surface vehicles cooperative defense based on PM-PSO and GA-PSO in the sophisticated sea environment[C]//Proc. of the International Conference on New Trends in Intelligent Software Methodologies, Tools and Techniques, 2018: 801−809. |
| 9 |
ZHANG J, REN J, CUI Y N, et al. Multi-USV task planning method based on improved deep reinforcement learning[J]. IEEE Internet of Things Journal, 2024, 11 (10): 18549- 18567.
doi: 10.1109/JIOT.2024.3363044 |
| 10 | TANG Y N, DOU L Q, ZHANG X Y, et al. Improved CNP-based task allocation for large-scale UAVs with timing constraints[J]. Journal of Aerospace Engineering, 2025, 38 (4): 4025029. |
| 11 |
DU B, LU Y, CHENG X T, et al. The object-oriented dynamic task assignment for unmanned surface vessels[J]. Engineering Applications of Artificial Intelligence, 2021, 106, 104476.
doi: 10.1016/j.engappai.2021.104476 |
| 12 |
MIYOMBO M E, LIU Y, MULENGA C M, et al. Optimal path planning in a real-world radioactive environment: a comparative study of A-star and Dijkstra algorithms[J]. Nuclear Engineering and Design, 2024, 420, 113039.
doi: 10.1016/j.nucengdes.2024.113039 |
| 13 |
SANG T T, XIAO J C, XIONG J F, et al. Path planning method of unmanned surface vehicles formation based on improved A* algorithm[J]. Journal of Marine Science and Engineering, 2023, 11 (1): 176.
doi: 10.3390/jmse11010176 |
| 14 |
ZHANG B, LU S L, LI Q, et al. Escape path planning for unmanned surface vehicle based on blind navigation rapidly exploring random tree* fusion algorithm[J]. Sensors, 2024, 24 (23): 7596.
doi: 10.3390/s24237596 |
| 15 |
ZHOU X J, TANG Z H, WANG N, et al. A novel state transition algorithm with adaptive fuzzy penalty for multi-constraint UAV path planning[J]. Expert Systems with Applications, 2024, 248, 123481.
doi: 10.1016/j.eswa.2024.123481 |
| 16 | LIANG X Y, JIANG P, ZHU H. Path planning for unmanned surface vehicle with dubins curve based on GA[C]//Proc. of the IEEE Chinese Automation Congress, 2020: 5149−5154. |
| 17 |
CHEN Y L, BAI G Q, ZHAN Y, et al. Path planning and obstacle avoiding of the USV based on improved ACO-APF hybrid algorithm with adaptive early-warning[J]. IEEE Access, 2021, 9, 40728- 40742.
doi: 10.1109/ACCESS.2021.3062375 |
| 18 | ZHAI H R, WANG W H, ZHANG W, et al. Path planning algorithms for USVs via deep reinforcement learning[C]//Proc. of the IEEE China Automation Congress, 2021: 4281−4286. |
| 19 | LI X W, SONG H S, HAN Z J, et al. An improved artificial potential field algorithm with swerving force for USV path planning[C]//Proc. of the IEEE International Conference on Unmanned Systems, 2021: 1019−1024. |
| 20 | 徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40 (12): 3508- 3512. |
| XU X Q, WANG M Y, MAO Y. Path planning of mobile robot based on improved artificial potential field method[J]. Journal of Computer Applications, 2020, 40 (12): 3508- 3512. | |
| 21 | ZHANG L Y, HAN Y, JIANG B. Research on path planning method of unmanned boat based on improved artificial potential field method[C]//Proc. of the IEEE 6th Asian Conference on Artificial Intelligence Technology, 2022. |
| 22 | 时维国, 宁宁, 宋存利, 等. 基于蚁群算法与人工势场法的移动机器人路径规划[J]. 农业机械学报, 2023, 54 (12): 407- 416. |
| SHI W G, NING N, SONG C L, et al. Path planning of mobile robots based on ant colony algorithm and artificial potential field algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2023, 54 (12): 407- 416. | |
| 23 |
韩尧, 李少华. 基于改进人工势场法的无人机航迹规划[J]. 系统工程与电子技术, 2021, 43 (11): 3305- 3311.
doi: 10.12305/j.issn.1001-506X.2021.11.31 |
|
HAN Y, LI S H. UAV path planning based on improved artificial potential field[J]. Systems Engineering and Electronics, 2021, 43 (11): 3305- 3311.
doi: 10.12305/j.issn.1001-506X.2021.11.31 |
|
| 24 | WANG D, CHEN H M, WU C C. A path planning and obstacle avoidance method for USV based on dynamic-target APF algorithm in edge[C]//Proc. of the International Conference on Algorithms and Architectures for Parallel Processing, 2023: 21−39. |
| 25 | 王庆禄, 吴冯国, 郑成辰, 等. 基于优化人工势场法的无人机航迹规划[J]. 系统工程与电子技术, 2023, 45 (5): 1461- 1468. |
| WANG Q L, WU F G, ZHENG C C, et al. UAV path planning based on optimized artificial potential field method[J]. Systems Engineering and Electronics, 2023, 45 (5): 1461- 1468. | |
| 26 | ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proc. of the 2nd International Conference on Knowledge Discovery and Data Mining, 1996: 226−231. |
| 27 | 苏菲, 陈岩, 沈林成. 基于蚁群算法的无人机协同多任务分配[J]. 航空学报, 2008, (S1): 184- 191. |
| SU F, CHEN Y, SHEN L C. UAV cooperative multi-task assignment based on ant colony algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2008, (S1): 184- 191. | |
| 28 | 宋佳瑞. 基于人工势场法的机器人避障问题研究[D]. 沈阳: 沈阳工业大学, 2017. |
| SONG J R. Obstacle avoidance problem study of robot based on artificial potential field method[D]. Shenyang: Shenyang University of Technology, 2017. | |
| 29 | 谢朔. 基于多新息辨识理论的USV运动模型参数辨识[D]. 武汉: 武汉理工大学, 2017. |
| XIE S. Motion model parameters identification of USV based on multi-innovation theory[D]. Wuhan: Wuhan University of Technology, 2017. | |
| 30 | 贾胜伟. 基于运动模型的水面无人艇路径规划[D]. 大连: 大连理工大学, 2022. |
| JIA S W. Path planning of unmanned surface vehicle based on motion model[D]. Dalian: Dalian University of Technology, 2022. |
| [1] | Zhao YANG, Jinbiao HU, Yan WANG, Hongbiao QI. UAV coverage path planning for mountain patrol considering different takeoff and landing nests [J]. Systems Engineering and Electronics, 2025, 47(8): 2622-2631. |
| [2] | Xiaozhen YAN, Xinyue ZHOU, Qinghua LUO. Improved A-star algorithm for dynamic path planning of unmanned ships [J]. Systems Engineering and Electronics, 2025, 47(7): 2314-2328. |
| [3] | Junchao TANG, Chunhe HU. Complete coverage path planning for UAVs in 3D terrain and wind field environment [J]. Systems Engineering and Electronics, 2025, 47(7): 2349-2356. |
| [4] | Yijie LIU, Bin JIANG, Yajie MA, Wenbo LI, Chengrui LIU. Collision avoidance path planning and re-planning for USV formation [J]. Systems Engineering and Electronics, 2025, 47(6): 1964-1974. |
| [5] | Wei CHEN, Congqing WANG, Qiang ZENG, Zhan LI. UAV coverage path planning for aircraft surface visual inspection [J]. Systems Engineering and Electronics, 2025, 47(4): 1206-1213. |
| [6] | Ze GENG, Yanyan HUANG, Han ZHANG. UAV swarm anti-artillery search path planning based on artillery transfer path prediction [J]. Systems Engineering and Electronics, 2025, 47(4): 1222-1234. |
| [7] | Yuqi XIA, Yanyan HUANG, Qia CHEN. Path planning for unmanned vehicle reconnaissance based on deep Q-network [J]. Systems Engineering and Electronics, 2024, 46(9): 3070-3081. |
| [8] | Bowen FEI, Weidong BAO, Daqian LIU, Xiaomin ZHU. Air-ground cooperative autonomous task allocation method for dynamic target search and strike [J]. Systems Engineering and Electronics, 2024, 46(7): 2346-2358. |
| [9] | Jie LI, Yuejin TAN. Operation loop recommendation method based on integrated improved ant colony algorithm [J]. Systems Engineering and Electronics, 2024, 46(6): 2002-2012. |
| [10] | Jiawei SUN, Minghui YU, Dapeng YANG, Haoquan TANG, Dapeng BIAN. Path planning of carrier aircraft traction system based on CL-RRT and MPC [J]. Systems Engineering and Electronics, 2024, 46(5): 1745-1755. |
| [11] | Dong SUI, Zhenyu YANG, Songbin DING, Tingting ZHOU. Three-dimensional path planning of UAV based on EMSDBO algorithm [J]. Systems Engineering and Electronics, 2024, 46(5): 1756-1766. |
| [12] | Jing YU, Xiaojun WU, Anlin JIANG, Enmi YONG. Research on UAV path planning method based on the multi-precision planning windows [J]. Systems Engineering and Electronics, 2024, 46(5): 1767-1776. |
| [13] | Gang LIU, Zhibiao AN, Maojun ZHANG, Yu LIU, Wu LI. Subject objective path planning algorithm based on continuous road network environment [J]. Systems Engineering and Electronics, 2024, 46(4): 1346-1356. |
| [14] | Guixiang ZHAO, Jian ZHOU, Yunmiao LI, Chenxu WANG. Improved bi-directional rapidly-exploring random tree path planning for USV [J]. Systems Engineering and Electronics, 2024, 46(4): 1364-1371. |
| [15] | Ping YANG, Bing XIAO, Xin CHEN, Luqi TANG. 3D path planning problem for fighter aircraft with multiple constraints [J]. Systems Engineering and Electronics, 2024, 46(12): 4213-4221. |
| Viewed | ||||||
|
Full text |
|
|||||
|
Abstract |
|
|||||