Abstract
The marine multi-robot system, which consists of unmanned surface vehicles (USVs) and unmanned aerial vehicles (UAVs), would provide a promising alternative for conducting complex and hazardous marine missions with reduced costs and human involvement. However, the energy issue of the UAVs substantially limits the practical application of this cooperative multi-robot system in maritime tasks. In order to efficiently guarantee the energy replenishment for the UAVs, this paper presents a dynamic route planning strategy to solve the route planning problem for a USV-UAV multi-robot system, with the USVs traveling as mobile charging stations on the sea with obstacles. Based on the graph theory and receding horizon control (RHC) strategy, we formalize the dynamic route planning problem into a dynamic multiple generalized traveling salesman problem (DMGTSP). A heuristic approach is utilized to solve the optimization problem at each control step in a receding manner. The proposed strategy is compared with the global horizon strategy in different case studies with static and moving obstacles. A lake experiment is conducted to validate the developed dynamic planning strategy. The results indicate that the dynamic route planning approach enables the USV-UAV cooperative system to fulfill the recharging task successfully and efficiently by periodically rendezvousing at varying locations during the long-term mission.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Data Availability
The raw/processed data required to reproduce these findings cannot be shared at this time as the data also forms part of an ongoing study.
References
Liu, C., Zhao, J., Sun, N.: A review of collaborative air-ground robots research. J. Intell. Robot. Syst. 106(3), 1–28 (2022)
Kundu, T., Saha, I.: Mobile recharger path planning and recharge scheduling in a multi-robot environment. In: 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp 3635–3642 (2021)
Ribeiro, R.G., Cota, L.P., Euzébio, T.A., Ramírez, J.A., Guimarães, F G.: Unmanned-aerial-vehicle routing problem with mobile charging stations for assisting search and rescue missions in postdisaster scenarios. IEEE Transactions on Systems Man, and Cybernetics: Systems (2021)
Lin, X., Yazıcıoğlu, Y., Aksaray, D.: Robust planning for persistent surveillance with energy-constrained UAVs and mobile charging stations. IEEE Robot. Autom. Lett. 7(2), 4157–4164 (2022)
Sundar, K., Rathinam, S.: Route planning algorithms for unmanned aerial vehicles with refueling constraints. In: 2012 American Control Conference (ACC), pp 3266–3271 (2012)
Yu, K., Budhiraja, A.K., Tokekar, P.: Algorithms for routing of unmanned aerial vehicles with mobile recharging stations. In: 2018 IEEE International Conference on Robotics and Automation (ICRA), pp 5720–5725 (2018)
Booth, K.E., Piacentini, C., Bernardini, S., Beck, J.C.: Target search on road networks with range-constrained UAVs and ground-based mobile recharging vehicles. IEEE Robot. Autom. Lett. 5(4), 6702–6709 (2020)
Mathew, N., Smith, S.L., Waslander, S.L.: A graph-based approach to multi-robot rendezvous for recharging in persistent tasks. In: 2013 IEEE International Conference on Robotics and Automation, pp 3497–3502 (2013)
Mathew, N., Smith, S.L., Waslander, S.L.: Multirobot rendezvous planning for recharging in persistent tasks. IEEE Trans. Robot. 31(1), 128–142 (2015)
Li, B., Page, B.R., Hoffman, J., Moridian, B., Mahmoudian, N.: Rendezvous planning for multiple AUVs with mobile charging stations in dynamic currents. IEEE Robot. Autom. Lett. 4(2), 1653–1660 (2019)
Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498–516 (1973)
Helsgaun, K.: General k-opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1(2), 119–163 (2009)
Hardgrave, S.W.: Determining the feasibility of replenishing a dispersed carrier battle group. Master’s thesis, Naval Postgraduate School, Monterey, California (1989)
Kannan, B., Marmol, V., Bourne, J., Dias, M.B.: The autonomous recharging problem: Formulation and a market-based solution. In: 2013 IEEE International Conference on Robotics and Automation, pp 3503–3510 (2013)
Flood, M.M.: The traveling-salesman problem. Oper. Res. 4(1), 61–75 (1956)
Bektas, T.: The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega 34(3), 209–219 (2006)
Noon, C.E., Bean, J.C.: An efficient transformation of the generalized traveling salesman problem. INFor: Inform. Syst. Oper. Res. 31(1), 39–44 (1993)
Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498–516 (1973)
Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106–130 (2000)
Cai, M., Peng, H., Li, Z., Gao, H., Kan, Z.: Receding horizon control-based motion planning with partially infeasible LTL constraints. IEEE Control Syst. Lett. 5(4), 1279–1284 (2020)
He, P., Wen, J., Stojanovic, V., Liu, F., Luan, X.: Finite-time control of discrete-time semi-Markov jump linear systems: A self-triggered MPC approach. J. Franklin Inst. 359(13), 6939–6957 (2022)
Meier, L., Tanskanen, P., Heng, L., Lee, G.H., Fraundorfer, F., Pollefeys, M.: PIXHAWK: A micro aerial vehicle design for autonomous flight using onboard computer vision. Auton. Robot. 33(1), 21–39 (2012)
Acknowledgements
This Research is mainly supported by the National Natural Science Foundation of China (62003180). In addition, this paper is partly supported by Hainan Province Science and Technology Special Fund (ZDYF2021GXJS041), Shanghai Scientific and Technological Innovation Program (19510745200), and National Natural Science Foundation of China(U2141234).
Funding
This Research is mainly supported by the National Natural Science Foundation of China (62003180). In addition, this paper is partly supported by Hainan Province Science and Technology Special Fund (ZDYF2021GXJS041), Shanghai Scientific and Technological Innovation Program (19510745200), and National Natural Science Foundation of China(U2141234).
Author information
Authors and Affiliations
Contributions
All authors contributed to the study conception and design. Methodology was designed by Yongqi Li, Haibo Lu, Shengquan Li and Weidong Zhang. Simulation was developed by Yongqi Li. Experiments, data collection and analysis were performed by Yongqi Li and Yumei Zhang. The first draft of the manuscript was written by Yongqi Li and all authors commented on revious versions of the manuscript. All authors read and approved the final manuscript.
Corresponding author
Ethics declarations
Ethics approval
The study does not involve humans and animals.
Consent to participate
The study does not involve human subjects.
Consent for Publication
The study does not involve human subjects.
Conflict of interest/Competing interests
The authors have no relevant financial or non-financial interests to disclose.
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Li, Y., Li, S., Zhang, Y. et al. Dynamic Route Planning for a USV-UAV Multi-Robot System in the Rendezvous Task with Obstacles. J Intell Robot Syst 107, 52 (2023). https://doi.org/10.1007/s10846-023-01830-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-023-01830-5