Heterogeneous multi-vehicle task assignment in a time-invariant drift field with obstacles

This paper studies the multi-vehicle task assignment problem where several dispersed vehicles need to visit a set of target locations in a time-invariant drift field with obstacles while trying to minimize the total travel time. The vehicles have different capabilities, and each kind of vehicles needs to visit a certain type of target locations; each target location might have the demand to be visited more than once by different kinds of vehicles. To find approximate solutions for such a challenging problem, we first design a path planning algorithm to minimize the time for a single vehicle to travel between two given locations through the drift field while avoiding obstacles. The path planning algorithm provides the travel cost matrix for the target assignment, and generates routes once the target locations are assigned to the vehicles. Then, we propose an auction-based distributed task assignment algorithm to assign the target locations to the vehicles using only local communication. Finally, numerical simulations show that the algorithm can lead to solutions close to the optimal.