Joint Task and Path Planning for Unmanned Surface Vehicle Surveillance Based on Beetle Antenna Search and Minimal Construct Visibility Graph

Task and path planning are critical to unmanned surface vehicles before sending off to commit surveillance tasks. In this paper, a hierarchical framework is proposed to resolve the problem where the lower-level path planner provides cost information to the upper-level task planner. Minimal construct visibility graph, a novel path planning algorithm that obsolete traditional grid-map, is introduced to plan the path between tasks as well as the depot. As only relative obstacles are involved, the path planning can achieve (near) optimal solutions within reasonable computational time. With regard to the upper-level task planner, a modified beetle antenna search algorithm with single-agent searching is proposed, showing competitive performance compared with the classical meta-heuristic algorithms like genetic algorithm and ant colony optimization algorithm. Simulation of joint task and path planning scenario demonstrates the high performance of our proposed methods, the solution quality is satisfactory and the computational load is at a low level.