Optimal collaborative path planning for unmanned surface vehicles carried by a parent boat along a planned route

• Main Authors: PRASETIA, Ari Carisza Graha, WANG, I-Lin, GUNAWAN, Aldy
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: Coverage Path Planning; Integer Programming; Time-Space Network; Unmanned Surface Vehicle; Numerical Analysis and Scientific Computing; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/6042; https://ink.library.smu.edu.sg/context/sis_research/article/7045/viewcontent/OptimalCollaborativePathPlanningforUnmannedSurfaceVehiclesCarriedbyaParentBoatAlongaPlannedRoute20__1_.pdf
• Institution: Singapore Management University

In this paper, an effective mechanism using a fleet of unmanned surface vehicles (USVs) carried by a parent boat (PB) is proposed to complete search or scientific tasks over multiple target water areas within a shorter time . Specifically, multiple USVs can be launched from the PB to conduct such operations simultaneously, and each USV can return to the PB for battery recharging or swapping and data collection in order to continue missions in a more extended range. The PB itself follows a planned route with a flexible schedule taking into consideration locational constraints or collision avoidance in a real-world situation. Assuming that each target has a value, this research investigates how to route these USVs, including their schedules to rendezvous with the PB, so that they can maximize the total collected target values from the operation in a limited amount of time. We use a multi-layered time-space network to describe the USVs and PB movement over time and give an integer programming (IP) formulation for the coverage path planning problem. To further shorten the computational time, we propose the Iterative Clustering Heuristic (ICH) to firstly cluster the workspace, calculate the path for each USV to visit targets and meet with the PB for range extension. To evaluate the performance of the proposed IP model and ICH, test cases are designed based on a real-world scenario, as well as families of simulated grid-like networks. Based on the computational analysis of different USV area sizes, targets covered, and operation time-bound increments, the proposed heuristic ICH can solve larger sized cases faster than the IP commercial solver with higher quality results.