Near-Optimal Covering Solution for USV Coastal Monitoring using PAES
Abstract
This paper addresses a multi-objective optimization problem for marine monitoring using USV. The objectives are to 1) cover the maximum area with 2) the lowest energy cost while avoiding collisions. To solve this problem, we use two optimization approaches: The first one is an exact method based on a Mixed Integer Programming model of the Covering Salesman Problem (CSP) and Travelling Salesman Problem with Profit (TSPP). The second one is a heuristic method based on a multi-objective evolutionary algorithm known as Pareto Archived Evolution Strategy (PAES). Then, a customized PAES (C-PAES) is proposed where the optimal chromosome size is calculated to enhance both performance and solutions quality. To validate the proposed heuristic solution, C-PAES is compared with the exact method. The results show that if the monitored area is represented with a graph containing less than 74 vertices, C-PAES is able to provide optimal solution within a much lower execution time. Beyond the limit of 74 vertices, the exact solver is not able to provide any solution within 24 hours delay while C-PAES can converge to a solution which consumes only 7% additional energy as comped to the optimal one.
Origin | Files produced by the author(s) |
---|