Multi-Ship Cooperative Search Method Based on Dynamic Voronoi Partitioning

JIANG Haijun; ZHANG Yichao; SUN Yaping; CHEN Hongkun

doi:10.11993/j.issn.2096-3920.2025-0123

Volume 34 Issue 1

Feb 2026

Turn off MathJax

Article Contents

Article Navigation > Journal of Unmanned Undersea Systems > 2026 > 34(1): 198-206

JIANG Haijun, ZHANG Yichao, SUN Yaping, CHEN Hongkun. Multi-Ship Cooperative Search Method Based on Dynamic Voronoi Partitioning[J]. Journal of Unmanned Undersea Systems, 2026, 34(1): 198-206. doi: 10.11993/j.issn.2096-3920.2025-0123

Citation:

JIANG Haijun, ZHANG Yichao, SUN Yaping, CHEN Hongkun. Multi-Ship Cooperative Search Method Based on Dynamic Voronoi Partitioning[J]. Journal of Unmanned Undersea Systems, 2026, 34(1): 198-206. doi: 10.11993/j.issn.2096-3920.2025-0123

Citation:

PDF( 1696 KB)

Multi-Ship Cooperative Search Method Based on Dynamic Voronoi Partitioning

doi: 10.11993/j.issn.2096-3920.2025-0123

1.
92899^thUnit, The People’s Liberation Army of China, Ningbo 315200, China
2.
92192^th Unit, The People’s Liberation Army of China, Ningbo 315200, China

Received Date: 2025-09-09
Accepted Date: 2025-10-09
Rev Recd Date: 2025-10-05

Available Online: 2026-01-15

Abstract

Abstract

Traditional multi-ship cooperative inspection search mainly employs fixed partitioning and fails to consider target evasion, resulting in low detection probability and insufficient alignment with actual combat. This paper proposed a multi-ship cooperative search method based on dynamic Voronoi partitioning and multi-source information joint decision-making. Based on a Bayesian probability framework, the method fused a sonar detection model and a target motion diffusion model to construct and dynamically update the probability distribution map of the target’s location. By adaptively dividing the search area using Voronoi diagrams, the method defined responsibility zones for each ship and realized distributed deployment in the task space, which significantly reduced redundant area coverage and eliminated search blind spots. To address the phased adaptation requirements of the “exploration and exploitation” strategy (focusing on exploration in the early stage and exploitation in the later stage), a multi-source information fusion scoring model was designed. This model incorporated target presence probability, degree of unsearched area, and local information entropy into a comprehensive calculation. Furthermore, a mechanism for adjusting weights according to search progress was constructed to dynamically adjust the search strategy with the task process, thereby guiding ships to determine optimal search target points. In adversarial scenarios with active target evasion, the proposed method was compared with the fixed-partition “zigzag”-type area coverage method and the particle swarm maximum probability heading optimization method. Results from 1 000 Monte Carlo simulations indicate that the proposed method significantly shortens the time to discover the target in multi-ship cooperative search tasks and improves the target detection probability in a statistical sense, demonstrating good realism and scalability in adversarial environments.
- multi-ship cooperation,
- search strategy,
- Voronoi partitioning,
- information entropy,
- Bayesian estimation

FullText(HTML)

References(16)

References

[1]	王磊, 吴福初. 基于线列阵声纳的水面舰艇检查搜潜仿真[J]. 火力与指挥控制, 2011, 36(11): 91-95. WANG L, WU F C. Discussion about the efficiency of surface ships checking antisubmarine which using sonar buoy[J]. Fire Control & Command Control, 2011, 36(11): 91-95.
[2]	高永琪, 马威强, 张林森, 等. 分布式AUV协同搜索方法[J]. 系统工程与电子技术, 2022, 44(5): 1674-1675. GAO Y Q, MA W Q, ZHANG L S, et al. Distributed multi-AUVs cooperative search method[J]. Systems Engineering and Electronics, 2022, 44(5): 1674-1675.
[3]	冯西安, 寇思玮, 岳玲. 水下移动平台网络化协同探测技术发展[J]. 应用声学, 2019, 38(4): 1674-1675. doi: 10.11684/j.issn.1000-310X.2019.04.006 FENG X A, KOU S W, YUE L. Development of networked collaborative detection technology for underwater mobile platforms[J]. Journal of Applied Acoustics, 2019, 38(4): 1674-1675. doi: 10.11684/j.issn.1000-310X.2019.04.006
[4]	付乐乐, 陈宏, 巩伟杰. 基于改进蚁群算法的水下机器人路径规划[J]. 自动化与仪表, 2022, 37(4): 46-50. doi: 10.3969/j.issn.1009-0134.2022.12.039 FU L L, CHEN H, GONG W J. Path planning of underwater robots based on improved ant colony algorithm[J]. Automation & Instrumentation, 2022, 37(4): 46-50. doi: 10.3969/j.issn.1009-0134.2022.12.039
[5]	邹佳运, 曲泓玥, 陈志鹏. 大规模水下滑翔机集群区域覆盖探测路径规划[J]. 水下无人系统学报, 2021, 29(1): 23-29. doi: 10.11993/j.issn.2096-3920.2021.01.004 ZOU J Y, QU H Y, CHEN Z P. Path planning of a large-scale underwater glider swarm area coverage detection[J]. Journal of Unmanned Undersea Systems, 2021, 29(1): 23-29. doi: 10.11993/j.issn.2096-3920.2021.01.004
[6]	王飞, 陈芳香. 基于多目标粒子群算法的水面舰艇编队搜潜阵型参数优化方法[J]. 声学与电子工程, 2025, 158(2): 7-11. WANG F, CHEN F X. Optimization method for anti-submarine formation parameters of surface ship formation based on multi-objective particle swarm algorithm[J]. Acoustics and Electronics Engineering, 2025, 158(2): 7-11.
[7]	JIA Q, XU H. Research on cooperative area search of multiple underwater robots based on the prediction of initial target information[J]. Ocean Engineering, 2019, 172: 660-670. doi: 10.1016/j.oceaneng.2018.12.035
[8]	廖燕荣, 姜可宇. 多舰协同分区搜潜动态航路规划[J]. 舰船电子工程, 2022, 42(7): 23-27. doi: 10.3969/j.issn.1672-9730.2022.07.007 LIAO Y R, JIANG K Y. Dynamic route planning of partitioned searching of multiple surface ships[J]. Ship Electronic Engineering, 2022, 42(7): 23-27. doi: 10.3969/j.issn.1672-9730.2022.07.007
[9]	陈捷, 刘海颖, 李志豪, 等. 基于改进Voronoi图的集群无人机区域覆盖方法[J]. 电子设计工程, 2023, 31(6): 31-32. CHEN J, LIU H Y, LI Z H, et al. Multi-UAV area coverage method based on improved Voronoi diagram[J]. Electronic Design Engineering, 2023, 31(6): 31-32.
[10]	彭辉, 沈林成, 霍霄华. 多UAV协同区域覆盖搜索研究[J]. 系统仿真学报, 2007, 19(11): 2472-2476. doi: 10.3969/j.issn.1004-731X.2007.11.022 PENG H, SHEN L C, HUO X H. Research on multiple UAV cooperative area coverage searching[J]. Journal of System Simulation, 2007, 19(11): 2472-2476. doi: 10.3969/j.issn.1004-731X.2007.11.022
[11]	高永琪, 王鹏, 马威强, 等. 改进头脑风暴算法在多AUV协同搜索动态目标中的应用[J]. 国防科技大学学报, 2024, 46(6): 203-209. GAO Y Q, WANG P, MA W Q, et al. Application of improved brain storm optimization algorithm in multi-AUV cooperative search moving targets[J]. Journal of National University of Defense Technology, 2024, 46(6): 203-209.
[12]	赵苗, 高永琪, 吴笛霄, 等. 复杂海战场环境下AUV全局路径规划方法[J]. 国防科技大学学报, 2021, 43(1): 41-48. doi: 10.11887/j.cn.202101006 ZHAO M, GAO Y Q, WU D X, et al. AUV global path planning method in complex sea battle field environment[J]. Journal of National University of Defense Technology, 2021, 43(1): 41-48. doi: 10.11887/j.cn.202101006
[13]	张美燕, 蔡文郁. 基于多AUV间任务协作的水下多目标探测路径规划[J]. 传感技术学报, 2018, 31(7): 1102-1106. ZHANG M Y, CAI W Y. Underwater targets tracking path planning based on task cooperation of multiple AUVs[J]. Chinese Journal of Sensors and Actuators, 2018, 31(7): 1101-1107.
[14]	黄杰, 孙伟, 高渝. 双属性概率图优化的无人机集群协同目标搜索[J]. 系统工程与电子技术, 2020, 42(1): 118-127. doi: 10.3969/j.issn.1001‐506X.2020.01.16 HUANG J, SUN W, GAO Y. Cooperative searching for the multi-UAVs based on dual-attribute probabilistic model optimization[J]. Systems Engineering and Electronics, 2020, 42(1): 118-127. doi: 10.3969/j.issn.1001‐506X.2020.01.16
[15]	张哲璇, 龙腾, 徐广通, 等. 重访机制驱动的多无人机协同动目标搜索方法[J]. 航空学报, 2020, 41(5): 220-232. ZHANG Z X, LONG T, XU G T, et al. Revisit mechanism driven multi-UAV cooperative search planning method for moving target[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(5): 220-232.
[16]	张宁, 寇小明, 李斌, 等. 基于遗传算法的应召搜潜路径优化[J]. 水下无人系统学报, 2023, 31(2): 244-251. doi: 10.11993/j.issn.2096-3920.2022-0002 ZHANG N, KOU X M, LI B, et al. Route optimization of on call submarine search based on genetic algorithm[J]. Journal of Unmanned Undersea Systems, 2023, 31(2): 244-251. doi: 10.11993/j.issn.2096-3920.2022-0002