通信距离约束下的无人船集群覆盖搜索方法

针对通信距离受限时水面无人船(unmanned surface vessel, USV)集群对未知水域的覆盖搜索问题, 提出一种竞拍协同边界探索算法。首先根据边界探索的思想提取地图探测边界, 然后以基于层次聚类思想进行改进的K-means++聚类算法划分任务区间, 消除不安全或低收益的目标搜索点, 再以分布式竞拍算法为USV集群动态分配搜索任务, 使集群搜索效率最大化, 各艇经过多轮分配、执行搜索任务直至覆盖全水域。仿真实验表明，在相同集群规模下, 相较于无协作的几种边界探索算法, 该算法任务用时和集群航行总路程更少; 在相同任务地图下, 覆盖搜索效率随USV集群规模增大而提高。

USV cluster coverage search method with communication distance constraint

Aiming at the coverage search problem of unmanned surface vessel (USV) cluster in unknown environment, an auction collaborate frontier algorithm is proposed. Firstly, the map detection boundary is extracted according to the idea of boundary exploration. Secondly, the task interval is divided by the improved K-means++ clustering algorithm based on the idea of hierarchical clustering to eliminate unsafe or low-yielding target search points. Finally, the search task is dynamically assigned to the USV cluster by the distributed bidding algorithm to maximize the cluster search efficiency, and each boat goes through multiple rounds of assignment and executes the search task until the whole water is covered. Simulation results show that the algorithm takes less time for the task and the total distance travelled by the cluster compared to several boundary exploration algorithms without collaboration at the same cluster size, and the coverage search efficiency improves with increasing USV cluster size at the same task map.