Simulated Annealing-Based Optimization for the Coverage Path Planning of Multiple Unmanned Surface Vehicles in ECDIS

This paper addresses the coverage path planning of multiple unmanned surface vehicles (USVs) based on electronic chart display and information system. An optimized coverage path planning method is proposed to improve the coverage percentages, and the coverage area of each USV leaves an additional degree of freedom for the operator to adjust further. Specifically, a grid representation method is proposed to fully cover the polygonal work area where three kinds of grids, namely, “Free”, “Obstacle”, and “Initial USV Position” are obtained. Next, a simulated annealing-based optimization method is proposed to optimize the placement of the grid by moving and rotating such that more “Free” grid can be obtained. Then, an improved divide area based on robots' initial positions method is proposed to achieve proportional area division. Finally, the coverage paths are generated using a spanning tree coverage method. Simulation results verify the effectiveness of the pro-posed simulated annealing-based optimization for the coverage path planning of multiple USVs.