Persistent Schedule Evaluation and Adaptive Re-planning for Maritime Search Tasks
Open Access
- 25 April 2024
- journal article
- research article
- Published by Springer Nature in Journal of Intelligent & Robotic Systems
- Vol. 110 (2) , 1-18
Abstract
Search operations performed by adaptive autonomous maritime vehicles have been a topic of considerable interest for many years. Such operations require carefully scheduled coordination of multiple vehicles performing search tasks across the region of interest. Due to the inherent uncertainty of the maritime environment, however, an initially planned search schedule may not be maintained if the vehicles have significant capability to adapt their tasks to match the environment they detect in real time. We propose a multi-vehicle adaptive algorithm for dynamic evaluation and elastic re-planning of variable-length tasks commonly found in the maritime environments. In adaptive evaluation and re-planning problems, a set of tasks are initially planned for execution by adaptive, autonomous search vehicles. Tasks are allocated to search vehicles under a pre-defined schedule based on prior knowledge and desired outcome. Because of the vehicles’ autonomy and reactivity to in situ conditions such as environment or target pose, the precise duration and actions required by each task are unknown a priori. We develop a hidden Markov model (HMM) for propagating task estimates, coupled with a quadratic-programming-based elastic re-scheduler. The result is an integrated estimate-and-schedule adaptation scheme that quickly and efficiently re-plans the vehicles’ schedules based on in situ observations. The numerical simulation results show that this novel HMM approach decreases avoidable schedule variation by over a factor of two compared to existing methods.Keywords
Funding Information
- Office of Naval Research (N00014-18-WX0-0459, N00014-22-1-2513, N00014-19-1-2144, N00014-22-WX0-1524)
This publication has 42 references indexed in Scilit:
- Maritime patrol tasks assignment optimization of multiple USVs under endurance constraintOcean Engineering, 2023
- Multi-Robot Dynamic Task Allocation for Exploration and DestructionJournal of Intelligent & Robotic Systems, 2019
- Partially-Decoupled Service Agent - Transport Agent Task Allocation and SchedulingJournal of Intelligent & Robotic Systems, 2018
- Composite particle algorithm for sustainable integrated dynamic ship routing and scheduling optimizationComputers & Industrial Engineering, 2016
- A novel genetic algorithm for flexible job shop scheduling problems with machine disruptionsThe International Journal of Advanced Manufacturing Technology, 2013
- Theory and experimental results for the multiple aspect coverage problemOcean Engineering, 2012
- Multiprocessor task scheduling in multistage hybrid flow-shops: A parallel greedy algorithm approachApplied Soft Computing, 2010
- Flexible job shop scheduling with tabu search algorithmsThe International Journal of Advanced Manufacturing Technology, 2006
- Quadratic Optimization1995
- Robust part-of-speech tagging using a hidden Markov modelComputer Speech & Language, 1992