Publication Type

Journal Article

Version

publishedVersion

Publication Date

12-2020

Abstract

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.

Keywords

Coverage Path Planning, Integer Programming, Time-Space Network, Unmanned Surface Vehicle

Discipline

Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

International Journal of Operations Research

Volume

17

Issue

4

First Page

101

Last Page

116

ISSN

1813-7148

Publisher

Operations Research Society of Taiwan

Embargo Period

7-12-2021

Copyright Owner and License

Publisher

Additional URL

http://www.orstw.org.tw/ijor/6_volume17_no4.html

Download

Share

COinS