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

Kai Xue, Zhiqin Huang, Ping Wang, Zumin XuJournal of Marine Science and Engineering 2021 · DOI

TL;DR

This paper introduces a novel exact algorithm for task allocation among multiple Unmanned Surface Vehicles (USVs) that prioritizes minimizing the maximum task completion time across all USVs, while also reducing the total task time. By combining the Hungarian algorithm with a refined cost matrix that includes travel and turning times, the approach offers a more practical solution for real-world USV operations where timely completion by the last vehicle is critical.

What Problem Does This Paper Address?

Coordinating multiple Unmanned Surface Vehicles (USVs) for tasks like environmental monitoring or disaster relief requires efficient task allocation – assigning specific target points to individual USVs. While many existing methods focus on minimizing the total cost (e.g., total travel distance or time) or use heuristic algorithms to find suboptimal solutions for both total and maximum costs, a critical practical concern is minimizing the maximum task completion time. This "makespan" is determined by the time the last USV reaches its assigned target. Existing approaches often fall short in guaranteeing the minimization of this makespan, which is crucial for time-sensitive operations. This paper addresses this gap by proposing an exact algorithm that specifically targets the minimization of the maximum task time, while also considering the reduction of the overall task time.

Methods

The core of the proposed method is an exact algorithm that builds upon the Hungarian algorithm, a well-established technique for solving the assignment problem (minimizing total cost). The key innovation lies in how the cost matrix is constructed and how the Hungarian algorithm is adapted.

  1. Cost Matrix Construction: The cost of assigning USV i to target point j ($C_{ij}$) is not just travel time. It's a composite of:
  2. Travel Time: Calculated using the Fast Marching Square (FMS) method to plan paths that avoid obstacles. This method is applied twice: first to build a safety potential field around obstacles, and then to build a distance potential field from the initial point. The path is then generated on a superimposed potential field. The travel time is derived from the path length and the USV's speed, which can be affected by environmental factors like wind and waves.
  3. Turning Time: This accounts for the time spent adjusting the USV's heading at both the initial departure point and the target destination. It considers the angle between the USV's initial direction and the planned path's initial direction, as well as the angle between the required destination direction and the path's final direction. This turning time is modeled as a function of the angle of direction change, environmental parameters, and the USV's control method.
  4. Algorithm Adaptation for Minimum Max Time: To minimize the maximum task time (makespan) rather than just the total time, the algorithm modifies the standard Hungarian algorithm process:
  5. Cost Matrix Augmentation: Small, random decimals are added to each element in the cost matrix. This is a crucial step to ensure that when the Hungarian algorithm is applied, it can find a full-rank solution and avoid issues where zero elements in the matrix might be misinterpreted as "no cost" rather than "unselected."
    • Iterative Filling and Rank Detection: Elements are filled into a zero matrix in ascending order of their augmented costs. The process stops when the matrix reaches full rank. At this point, the Hungarian algorithm is applied to find the optimal assignment. The element that causes the matrix to become full rank and is the last one added is effectively the maximum cost element.
  6. Constraint Integration: The algorithm aims to minimize the maximum cost ($T_{mc}$) while also reducing the total cost ($T_{tc}$). This is achieved by using the minimization of the maximum cost as the primary objective and incorporating the minimization of the total cost as a constraint.

Datasets

Not discussed in the paper. The experiments were conducted using simulated environments and synthetically generated cost matrices.

Key Insights and Ideas

  • Makespan Minimization is Key for USVs: The paper highlights that for practical USV operations, minimizing the time until the last vehicle completes its task is often more critical than simply minimizing the sum of all task times.
  • Comprehensive Cost Model: Including both travel time (with obstacle avoidance) and turning time at waypoints provides a more realistic cost estimation for USV task allocation.
  • Hungarian Algorithm Adaptation: Cleverly augmenting the cost matrix with small random numbers and using rank detection allows the Hungarian algorithm, typically used for total cost minimization, to effectively find solutions that minimize the maximum cost.
  • Exact vs. Heuristic: The paper emphasizes the benefit of an exact algorithm for this problem, contrasting it with heuristic approaches that might not guarantee optimality for the makespan.

Key Results

The proposed algorithm (referred to as MM) was compared against the Hungarian Algorithm (HA), Auction Algorithm (AA), Genetic Algorithm (GA), and Ant Colony Optimization (ACO).

  • Max Cost (PM): The MM algorithm consistently achieved the lowest percentage of maximum cost (PM) compared to other algorithms, often maintaining a low PM even as the number of USVs increased. GA also performed well in minimizing max cost, but MM was superior. HA and AA performed poorly in this metric as their optimization direction is total cost.
  • Total Cost (PT): HA and AA, being exact algorithms for total cost minimization, achieved the best results for total cost percentage (PT), typically around 100-101%. The MM algorithm's PT was slightly higher than HA and AA (around 101-105%), which is a trade-off for its superior performance in minimizing the maximum cost. ACO and GA also showed higher PT values.
  • Simulation Validation: Visualizations of planned paths showed effective obstacle avoidance. The results indicated that the proposed algorithm successfully minimized the max cost and reduced the total cost.

Limitations and Future Work

  • Computational Complexity: While an exact algorithm, the paper doesn't extensively detail the computational complexity for very large numbers of USVs and tasks. The proof for the Hungarian algorithm's solution relies on the matrix being full rank, which is achieved through the augmentation step, but the efficiency of this process for massive problem instances might be a consideration.
  • Environmental Factors: While environmental parameters are mentioned as influencing speed, the simulation uses simplified models. More complex and dynamic environmental modeling could be explored.
  • Future Work: The authors suggest incorporating formation control into task allocation. USVs could first assemble into formations to travel to target areas and then perform task allocation once near their destinations. This could potentially improve efficiency and coordination further.

Summary updated

Abstract

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.
BibTeX
@article{xue2021exact,
  author = {Kai Xue and Zhiqin Huang and Ping Wang and Zumin Xu},
  title = {{An Exact Algorithm for Task Allocation of Multiple Unmanned Surface Vehicles with Minimum Task Time}},
  journal = {Journal of Marine Science and Engineering},
  year = {2021},
  doi = {10.3390/jmse9080907},
}
Figure