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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Data Availability
No experimental data or large data sets were used in this paper.
References
Baylog, J.G., Wettergren, T.A.: Online determination of the potential benefit of path adaptation in undersea search. IEEE J. Ocean. Eng. (2014)
Bennett, A.A., Leonard, J.J.: A behavior-based approach to adaptive feature detection and following with autonomous underwater vehicles. IEEE J. Ocean. Eng. 25(2), 213–226 (2000)
Apker, T., Liu, S.-Y., Sofge, D., Hedrick, J.K.: Application of grazing-inspired guidance laws to autononomous information gathering. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, (2014)
Kriminger, E., Cobb, J.T., Príncipe, J.C.: Online active learning for automatic target recognition. IEEE J. Ocean. Eng. 40(3), 583–591 (2014)
Sledge, I.J., Bryner, D.W., Príncipe, J.C.: Annotating motion primitives for simplifying action search in reinforcement learning. IEEE Trans. Emerg. Top. Comput. Intell. 6(5), 1137–1156 (2022)
Sledge, I.J., Emigh, M.S., King, J.L., Woods, D.L., Cobb, J.T., Principe, J.C.: Target detection and segmentation in circular-scan synthetic aperture sonar images using semisupervised convolutional encoder-decoders. IEEE J. Ocean. Eng. 47(4), 1099–1128 (2022)
Zhu, T., Xiao, Y., Zhang, H.: Maritime patrol tasks assignment optimization of multiple usvs under endurance constraint. Ocean Eng. 285, 115445 (2023)
Koes, M., Nourbakhsh, I., Sycara, K.: Constraint optimization coordination architecture for search and rescue robotics. In: International Conference on Robotics and Automation, (2006)
Gombolay, M.C., Wilcox, R.J., Shah, J.A.: Fast scheduling of multi-robot teams with temporospatial constraints. In: Robotics: Science and Systems, (2013)
Bays, M.J., Wettergren, T.A.: Service agent-transport agent task planning incorporating robust scheduling techniques. Robot. Auton. Syst. 89, 15–26 (2017)
Molineaux, M., Auslander, B., Moore, P.G., Gupta, K.M.: Minimally disruptive schedule repair for mcm missions. In: Proc. SPIE 9454, Detection and Sensing of Mines, Explosive Objects, and Obscured Targets XX, (2015)
Sidoti, D., Avvari, G.V., Mishra, M., Zhang, L., Nadella, B.K., Peak, J.E., Hansen, J.A., Pattipati, K.R.: A multiobjective path-planning algorithm with time windows for asset routing in a dynamic weather-impacted environment. IEEE Trans. Syst. Man Cybern. Syst. 47(12), 3256–3271 (2017)
Sidoti, D., Han, X., Zhang, L., Avvari, G.V., Ayala, D.F.M., Mishra, M., Sankavaram, M.S., Kellmeyer, D.L., Hansen, J.A., Pattipati, K.R.: Context-aware dynamic asset allocation for maritime interdiction operations. IEEE Trans. Syst. Man Cybern. Syst. 50(3), 1055–1073 (2020)
De, A., Mamanduru, V.K.R., Gunasekaran, A., Subramanian, N., Tiwari, M.K.: Composite particle algorithm for sustainable integrated dynamic ship routing and scheduling optimization. Comput. Ind. Eng. 96, 201–215 (2016)
Saidi-Mehrabad, M., Fattahi, P.: Flexible job shop scheduling with tabu search algorithms. Int. J. Adv. Manuf. Tech. 32, 563–570 (2007)
Arif, M.U., Haider, S.: A flexible framework for diverse multi-robot task allocation scenarios including multi-tasking. ACM Trans. Auton. Adapt. Syst. (TAAS) 16(1), 1–23 (2022)
Yan, B., Bragin, M.A., Luh, P.B.: Novel formulation and resolution of job-shop scheduling problems. IEEE Robot. Autom. Lett. 3(4), 3387–3393 (2018)
Chakraa, H., Guérin, F., Leclercq, E., Lefebvre, D.: Optimization techniques for multi-robot task allocation problems: Review on the state-of-the-art. Robot. Auton. Syst. 104492 (2023)
Dai, W., Lu, H., Xiao, J., Zeng, Z., Zheng, Z.: Multi-robot dynamic task allocation for exploration and destruction. J. Intell. Robot. Syst. 98, 455–479 (2020)
Lippi, M., Marino, A.: A mixed-integer linear programming formulation for human multi-robot task allocation. In: 2021 30th IEEE International Conference on Robot & Human Interactive Communication (RO-MAN), pp. 1017–1023. IEEE, (2021)
Turner, J., Meng, Q., Schaefer, G., Whitbrook, A., Soltoggio, A.: Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system. IEEE Trans. Cybern. 48(9), 2583–2597 (2018)
Wang, Y.M., Yin, H.L., Qin, K.D.: A novel genetic algorithm for flexible job shop scheduling problems with machine disruptions. Int. J. Adv. Manuf. Tech. 68, 1317–1326 (2013)
Kupiec, J.: Robust part-of-speech tagging using a hidden markov model. Comput. Speech Lang. 6(3), 225–242 (1992)
Zhang, H.-P., Liu, Q., Cheng, X.-Q., Zhang, H., Yu, H.-K.: Chinese lexical analysis using hierarchical hidden markov model. In: Proceedings of the second SIGHAN workshop on Chinese language processing-Volume 17. Association for Computational Linguistics, pp. 63–70 (2003)
Juang, B.H., Rabiner, L.R.: Hidden markov models for speech recognition. Technometrics 33(3), 251–272 (1991)
Lee, K.-F., Hon, H.-W.: Speaker-independent phone recognition using hidden markov models. IEEE Trans. Acoust. Speech Signal. Process. 37(11), 1641–1648 (1989)
Evans, J., Krishnamurthy, V.: Optimal sensor scheduling for hidden markov model state estimation. Int. J. Control. 74(18), 1737–1742 (2001)
Ertunc, H.M., Loparo, K.A., Ocak, H.: Tool wear condition monitoring in drilling operations using hidden markov models (hmms). Int. J. Mach. Tools Manuf. 41(9), 1363–1384 (2001)
Gabel, T., Riedmiller, M.: Adaptive reactive job-shop scheduling with reinforcement learning agents. Int. J. Inf. Technol. Intell. Comput. 24(4), (2008)
Buttazzo, G.C., Lipari, G., Caccamo, M., Abeni, L.: Elastic scheduling for flexible workload management. IEEE Trans. Comput. 51(3), 289–302 (2002)
Yang, L., Li, J., Hackney, P., Chao, F., Flanagan, M.: Manual task completion time estimation for job shop scheduling using a fuzzy inference system. In: 2017 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), pp. 139–146. IEEE, (2017)
Barcelö, J., Montero, L., Marqués, L., Carmona, C.: Travel time forecasting and dynamic origin-destination estimation for freeways based on bluetooth traffic monitoring. Transp. Res. Rec. 2175(1), 19–27 (2010)
Hadachi, A., Lecomte, C., Mousset, S., Bensrhair, A.: An application of the sequential monte carlo to increase the accuracy of travel time estimation in urban areas. In: 2011 14th International IEEE Conference on Intelligent Transportation Systems (ITSC), pp. 157–162. IEEE, (2011)
Ding, K., Lei, J., Chan, F.T., Hui, J., Zhang, F., Wang, Y.: Hidden markov model-based autonomous manufacturing task orchestration in smart shop floors. Robot. Comput. Integr. Manuf. 61, 101845 (2020)
Bays, M.J., Wettergren, T.A.: A solution to the service agent transport problem. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), September pp. 6443–6450 (2015)
Ghahramani, Z.: An introduction to hidden Markov models and Bayesian networks. Int. J. Pattern Recognit. Artif. Intell. 15, 9–42 (2001)
Casella, G., Berger, R.L.: Statistical inference. Crockett, C. (ed.) Duxbury, (2002)
Reynolds, J.F.: Some theorems on the transient covariance of Markov chains. J. Appl. Probab. (1972)
Shah, D.C., Campbell, M.A.: A robust qualitative planner for mobile robot navigation. In: IEEE International Conference on Robotics and Automation, (2011)
Floudas, C.A., Visweswaran, V.: Quadratic optimization. In: Handbook of global optimization, pp. 217–269. Springer, (1995)
Chang, S., Isaacs, J., Fu, B., Shin, J., Zhu, P., Ferrari, S.: Confidence level estimation in multi-target classification problems. In: Detection and Sensing of Mines, Explosive Objects, and Obscured Targets XXIII, vol. 10628. International Society for Optics and Photonics, p. 1062818 (2018)
Bays, M.J., Shende, A., Stilwell, D.J., Redfield, S.A.: Theory and experimental results for the multiple-aspect coverage problem. Ocean Eng. 54, (2012)
Bays, M.J., Wettergren, A.: Partially-decoupled service agent - transport agent task allocation & scheduling. J. Intell. Robot. Syst. 94(2), 423–437 (2019)
Kahraman, C., Engin, O., Kaya, A., Ozturk, R.E.: Multiprocessor task scheduling in multistage hybrid flow-shops: A parallel greedy algorithm approach. Appl. Soft. Comput. 10(4), 1293 – 1300 (2010) optimisation Methods and Applications in Decision-Making Processes
Acknowledgements
This work was funded by the Office of Naval Research, Code 32.
Funding
This work was funding under Office of Naval Research grants N0014-18-WX0-0459, N00014-22-1-2513, N00014-19-1-2144, and N00014-22-WX0-1524.
Author information
Authors and Affiliations
Contributions
Matthew J. Bays contributed to the theoretical development and software implementation of the HMM algorithm and elastic scheduler. Thomas A. Wettergren contributed to the theoretical development of the HMM algorithm and elastic scheduler as well as general refinement of the manuscript. Jane Shin and Shi Chang contributed to the theoretical development and software implementation of the AMAC algorithm. Silvia Ferrari contributed to the theoretical development of the AMAC algorithm and general refinement of the manuscript.
Corresponding author
Ethics declarations
Conflict of Interest
The authors are not aware of any conflicts of interest.
Ethics and Consent
This work did not involve human subjects and thus ethical considerations, consent to participate, and consent by subjects to publish do not apply. This manuscript has been designated Distribution Statement A: Approved for public release; distribution is unlimited.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Bays, M.J., Wettergren, T.A., Shin, J. et al. Persistent Schedule Evaluation and Adaptive Re-planning for Maritime Search Tasks. J Intell Robot Syst 110, 65 (2024). https://doi.org/10.1007/s10846-024-02094-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-024-02094-3