An Exact Algorithm for Task Allocation of Multiple Unmanned Surface Vehicles with Minimum Task Time

Task allocation of unmanned surface vehicles (USVs) with low task cost is an important research area which assigns USVs from starting points to different target points to complete tasks. Most of the research lines of task allocation are using heuristic algorithms to obtain suboptimal solutions to reduce both the max task cost and total task cost. In practice, reducing the maximum is more important to task time, which is from the departure of USVs to the last USV arriving at the designated position. In this paper, an exact algorithm is proposed to minimize the max task time and reduce the total task time based on the Hungarian algorithm. In this algorithm, task time is composed of the travel time along the planned path and the turning time at initial and target points. The fast marching square method (FMS) is used to plan the travel path with obstacle avoidance. The effectiveness and practicability of the proposed algorithm are verified by comparing it with the Hungarian algorithm (HA), the auction algorithm (AA), the genetic algorithm (GA) and the ant colony optimization algorithm (ACO). The results of path planning and task allocation are displayed in the simulation