Constrained Multi-objective Task Assignment for UUVs using Multiple Ant Colonies System

摘要

The purpose of this research is to develop an effective task assignment algorithm for multiple Unmanned Underwater Vehicles (UUVs) to reacquaint multiple targets. This algorithm is specifically designed for the underwater environment where vehicles typically have dissimilar starting and ending locations. Besides the objective of minimizing the total distance of multiple vehicles, the objectives of minimizing the total turning angle and the constraint of balancing the targets number visited by each vehicle are also considered. This problem is modeled as a constrained multi-objective MTSP. The different measurement units and order of magnitudes of multiple objectives significantly increase the difficulty to generate an effective solution. The proposed algorithm consists of two phases: task number assignment and task assignment using Multiple Ant Colony System (MACS) which is extended from the classical Ant Colony System (ACS). In the first phase, the target number is assigned to each vehicle. Afterwards, MACS is used to solve constrained multi-objective MTSP, in which multiple ant colonies work separately to optimize dissimilar objectives, the ideal solution is generated according to the result of each colony, and the output is the best solution which has the smallest deviation from the ideal solution in the set of Pareto optimal solutions. The computational results show that the output of the proposed algorithm can satisfy the constrained multi-objective requirement and can be applied to underwater application scenario.