An Effective Task allocation Algorithm for Unmanned Surface Vehicle System
Qinghua Luo, Liqi Zhang, Xiaozhen Yan, Di Wu · 2023
Task allocation plays a crucial role in enabling unmanned surface vehicles (USV) to operate autonomously and intelligently. However, in recent years, with the increasing scale of USVs and the growing complexity of task environments, existing algorithms have gradually become inadequate for current application scenarios, exhibiting deficiencies in both real-time performance and effectiveness. Traditional heuristic algorithms are often prone to local convergence and yield suboptimal solutions. Optimization methods are better suited for environments with simple constraints and small task scales, but their real-time performance deteriorates rapidly as task scales increase. To address these issues, this paper proposes an improved genetic algorithm based on the K-means clustering algorithm (K-means Based Genetic Algorithm, KBGA). First, we need to establish an USVs task allocation model that meets the requirements of the marine environment. Subsequently, we employ the K-means clustering algorithm to preprocess the environmental information, enhancing the effectiveness of initial task allocation in USV systems. Lastly, we enhance the optimization capabilities of the genetic algorithm by improving the genetic computational steps, thereby improving the effectiveness and stability of final task allocation in USVs systems. We comprehensively evaluate the improved genetic algorithm based on the K-means clustering algorithm under capability-limited environments and multi-task scenarios. Through comparative analysis using simulations, our algorithm demonstrates higher effectiveness and stability compared to relevant algorithms.