Optimal Collaborative Path Planning for Area Coverage Tasks by a Parent Boat Carrying Unmanned Surface Vehicles

Abstract

Due to improvements in sensing and wireless communication technology a fleet of unmanned surface vehicles (USVs) can now be used to search water areas for the purpose of carrying out multiple targeted operations Specifically multiple USVs can conduct search tasks simultaneously However due to its limited battery or fuel capacity a USV requires recharging (or refueling) or battery swapping to continue longer range missions Thus we propose a mechanism in which USVs can depart from and return to a parent boat (PB) for recharging and data collection Assuming each target has a value of importance this thesis investigates how to calculate optimal routes for both PB and USVs so that USVs can cover all the target areas with the total target values as the objective for operating in a limited amount of time We propose an integer programming formulation on a time-space network for cases of a given PB path (C1) and the case where the PB path is not yet known (C2) based on techniques similar to the coverage path planning (CPP) the orienteering problem and the two-echelon routing problem in the literature Although mathematical formulations can be used to solve the problem this is quite time-consuming We thus designed three methods to solve the problems related to calculating good routings in a shorter time The first method is the Iterative Clustering Heuristic (ICH) based on the clustering technique which was intended to limit the workspace for each USV The second method is the Iterative Local Search (ILS) algorithm based on multiple local search procedures which was intended to further shorten the computational results The third method is the Sequential Segmentation Heuristic (SSH) which is based on the segmentation process and was intended to limit the time-bound in each segment The results of our preliminary computational experiments for both cases and a real-world scenario problem setting indicate that the proposed solution methods can calculate good search plans faster than the proposed integer programming model

Date of Award	2020
Original language	English
Supervisor	I-Lin Wang (Supervisor)