Research On Cooperative Coverage Path Planning For Multi-USMVs

With the deepening of China’s ‘Sea Power Nation Strategy’ and the Yangtze River Economic Belt,waterway transport plays an increasingly important role in economic and social development.Underwater topography exploration is the basic condition to ensure the safety of waterway transportation,and its demand is increasingly strong.The traditional water surveying operations are mainly realized by manned mapping vessels reciprocating in the operating waters.With the development of artificial intelligence technology and the shipbuilding industry,unmanned surface vessel（USV）is gradually used in water exploration tasks,which benefits from the advantages of shallow draft,low energy consumption,flexible operation and no need to carry people.To further improve the accuracy and efficiency of the water depth sounding operation,this paper intends to use the cooperative mode of multiple Unmanned Surface Mapping Vehicles（USMV）to achieve water area measurement work,and carry out in-depth research on cooperative coverage path planning algorithms.The quality of USMV’s underwater topographic exploration mainly depends on its ability of coverage path planning.Currently,the research of coverage path planning mainly focuses on mobile robots.The traditional coverage path planning algorithm has the problems of discontinuous path planning and low efficiency of cooperative coverage.Therefore,to carry out underwater topographic survey work based on USMV,it is necessary to analyze the water coverage requirements,establish a water area environment model,and design a reasonable and efficient cooperative coverage path planning algorithm to significantly improve the quality,efficiency and safety of cooperative coverage paths.This paper mainly carried out the following research:Firstly,the paper summarizes the map decomposition methods such as decomposition algorithm,trapezoid decomposition method,Boustrophedon decomposition method and BA * coverage path planning algorithm,and analyzes the applicability of traditional coverage path planning algorithm.Secondly,the coverage path planning algorithm of a single unmanned survey vessel is developed.Using grid method to carry out water environment information modeling.Combined with the known characteristics of sea chart and river map information in the operating water area,the static environment information is imported to provide information support for subsequent route optimization.The BA * algorithm is improved in terms of cell decomposition method and map update method,and the IBA *（Improved BA *）algorithm is designed to solve the problem of insufficient continuity caused by too many cells and meet the high-precision requirements of environmental modeling.The shortcomings of local optimum of BA * algorithm are effectively overcome.Numerical examples confirm that the IBA * algorithm is superior to the Boustrophedon algorithm and the BA * algorithm in terms of coverage ratio,path length,and number of turns,and has lower time complexity.Subsequently,the research on cooperative coverage path planning of multiple unmanned surface mapping vehicles is carried out.Based on the IBA * algorithm,a multi-USMV cooperative coverage path planning algorithm CCIBA *（Cooperative Coverage IBA *）is designed and implemented.The CCIBA * algorithm consists of two phases: cooperative coverage offline planning and cooperative coverage online planning.In the off-line planning stage of cooperative coverage,considering the factors such as predicted path and its own performance,the sub task area is divided,and four typical cooperative behavior strategies such as region segmentation,backtracking transfer,region exchange and obstacle joint identification are proposed to improve the optimization decision-making level in complex scenes;in the cooperative coverage online planning stage,based on the single USMV coverage path planning IBA *algorithm,reflects the multi-USMV cooperative operation of the dynamic allocation of sub-regions in the coverage requirements,design online coverage scanning process to achieve CCIBA * algorithm.Finally,a series of simulational experiments of cooperative coverage of multiple unmanned measurement vessels in a complex environment was carried out.Based on the analysis of sub-area division,dynamic update,and cooperative scanning algorithm flow,the advantages of CCIBA * algorithm are summarized,and cooperative coverage simulation experiments in a variety of complex operating environments are carried out.The analysis and calculations confirm that the coverage ratio of the CCIBA * algorithm designed in this paper is improved by about 7.6% over the BA * algorithm,the number of turns is reduced by about 16.5% over the BA * algorithm,and the number of units is reduced by about 44.4% over the BA *.Under the premise of ensuring complete coverage,the path length of IBA * does not increase significantly compared with the BA * algorithm,which is about 10.76% less than the Boustrophedon algorithm that achieves complete coverage.The cooperative coverage path planning algorithm proposed in this thesis improves the coverage ratio and coverage effect under the complex operation environment of USMV.Our study can do great deeds for the construction of national waterway information,and can provide excellent theoretical guidance and technical support correspondingly.