An adaptive bi-level task planning strategy for multi-USVs target visitation

This paper considers a task planning problem, which dispatches multiple unmanned surface vehicles (USVs) to visit a set of targets located in ocean environments. The problem is modeled as a bi-level optimization to reduce the total and the individual navigation costs simultaneously. The upper-level allocates targets and schedules target visitation sequences, while the lower-level plans safe and economical paths between two targets under the current influence. Subsequently, a novel nested strategy is proposed to solve the bi-level problem, which modifies each level initialization process and can adaptively give the lower-level function evaluation number according to the problem complexity. Besides, the proposed strategy can adopt general metaheuristics as optimizers. Thus, two upper-level and five lower-level algorithms are employed in combination, which covers most kinds of metaheuristics. Finally, the ten combinations of algorithms are tested on three large-scale and complex cases, and the results verify the effectiveness of the proposed model and strategy.