Abstract
This paper presents elite group-based evolutionary algorithms (EGEA) for adaptive ocean sampling using multiple unmanned marine vehicles (UMVs). The EGEA integrate a group-based framework and elitist selection methods into evolutionary path planner, which combine main advantages of these two techniques.The group-based framework allows each offspring individual of evolutionary algorithm to generate its own group of new solutions with a certain probability. Two elitist selection methods, herein referred to as group individual elitist selection (GIES) and whole population elitist selection (WPES), are proposed to facilitate selecting preferable solutions to be passed on to the next generation in the procedure of evolutionary algorithms. The EGEA path planners based on simulated annealing algorithm (SA) and particle swarm optimization (PSO) are tested to find trajectories for multiple UMVs to collect maximum interested ocean information from regions under investigation. The mixed integer linear programming (MILP) is also described and evaluated with the proposed EGEA for solving the adaptive sampling problem. Simulation results show that the whole elite group-based simulated annealing algorithm (WEGSA) is able to generate trajectories with more information gain from regions of high scientific interest with constrained energy of multiple UMVs than other techniques. Monte Carlo simulations demonstrate the inherent robustness and superiority of the proposed planner based on the EGEA in comparison with other techniques.
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.
References
Zeng, Z., Lian, L., Sammut, K., He, F., Tang, Y., Lammas, A.: A survey on path planning for persistent autonomy of autonomous underwater vehicles. Ocean Eng. 110, 303–313 (2015)
Ferri, G., Cococcioni, M., Alvarez, A.: Mission planning and decision support for underwater glider networks: A sampling on-demand approach. Sensors 16(1) (2015)
Yilmaz, N. K., Evangelinos, Constantinos, Lermusiaux, P., Patrikalakis, N. M.: Path planning of autonomous underwater vehicles for adaptive sampling using mixed integer linear programming. IEEE J. Ocean. Eng. 33(4), 522–537 (2008)
Xiang, X., Yu, C., Zhang, Q.: On intelligent risk analysis and critical decision of underwater robotic vehicle. Ocean Eng. 140(January), 453–465 (2017)
Das, J., Py, F., Harvey, J.B.J., Ryan, J.P., Gellene, A., Graham, R., Caron, D.A., Rajan, K., Sukhatme, G.S.: Data-driven robotic sampling for marine ecosystem monitoring. Int. J. Robot. Res. 34(12), 1435–1452 (2015)
Tsardoulias, E. G., Iliakopoulou, A., Kargakos, A., Petrou, L.: A review of global path planning methods for occupancy grid maps regardless of obstacle density. J. Intell. Robot. Syst. Theory Appl. 84(1-4), 829–858 (2016)
Fiorelli, E., Leonard, N. E., Bhatta, P., Paley, D., Bachmayer, R., Fratantoni, D.M.: Multi-AUV control and adaptive sampling in Monterey Bay. IEEE J. Ocean. Eng. 31(4), 935–948 (2006)
Yang, Y., Wang, S., Wu, Z., Wang, Y.: Motion planning for multi-HUG formation in an environment with obstacles. Ocean Eng. 38(17-18), 2262–2269 (2011)
Cui, R., Li, Y., Yan, W.: Mutual Information-Based Multi-AUV Path Planning for Scalar Field Sampling Using Multidimensional RRT*. IEEE Trans. Syst. Man Cybern. Syst. 46(7), 993–1004 (2016)
Bucknall, R., Song, R., Liu, Y.: A multi-layered fast marching method for unmanned surface vehicle path planning in a time-variant maritime environment. Ocean Eng. 129(2016), 301–317 (2017)
Jaillet, L., Cortés, J, Siméon, T.: Transition-based RRT for path planning in continuous cost spaces. 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, (Section V), pp. 2145–2150 (2008)
Smith, R.N., Schwager, M., Smith, S.L., Jones, B.H., Rus, D., Sukhatme, G.S.: Persistent ocean monitoring with underwater gliders: Adapting sampling resolution. J. Field Robot. 28(5):714–741 (2011)
Binney, J., Sukhatme, G.S.: Branch and Bound for Informative Path Planning. In: 2012 IEEE International Conference on Robotics and Automation, pp. 2147–2154. IEEE (2012)
Hollinger, G.A., Sukhatme, G.S.: Sampling-based robotic information gathering algorithms. Int. J. Robot. Res. 33(9), 1271–1287 (2014)
Mishra, R., Chitre, M., Swarup, S.: Online Informative Path Planning Using Sparse Gaussian Processes. In: 2018 OCEANS - MTS/IEEE Kobe Techno-Oceans (OTO), pp. 1–5. IEEE (2018)
Ma, K.-C., Liu, L., Heidarsson, H.K., Sukhatme, G.S.: Data-driven learning and planning for environmental sampling. J. Field Robot. 35(5):643–661 (2018)
Zeng, Z., Sammut, K., Lammas, A., He, F., Tang, Y.: Efficient Path Re-planning for AUVs Operating in Spatiotemporal Currents. J. Intell. Robot. Syst. Theory Appl. 79(1), 135–153 (2015)
Cao, J., Cao, J., Zeng, Z., Yao, B., Lian, L.: Toward Optimal Rendezvous of Multiple Underwater Gliders: 3D Path Planning with Combined Sawtooth and Spiral Motion. J. Intell. Robot. Syst. 85(1):189–206 (2017)
Zhou, H., Zeng, Z., Lian, L.: Adaptive Re-planning of AUVs for Environmental Sampling Missions: A Fuzzy Decision Support System Based on Multi-objective Particle Swarm Optimization. Int. J. Fuzzy Syst. 20(2):650–671 (2018)
Miao, H., Tian, Y.-C.: Dynamic robot path planning using an enhanced simulated annealing approach. Appl. Math. Comput. 222, 420–437 (2013)
Zeng, Z., Lammas, A., Sammut, K., He, F., Tang, Y.: Shell space decomposition based path planning for AUVs operating in a variable environment. Ocean Eng. 91, 181–195 (2014)
Zeng, Z., Sammut, K., Lian, L., He, F., Lammas, A., Tang, Y.: A comparison of optimization techniques for AUV path planning in environments with ocean currents. Robot. Auton. Syst. 82, 61–72 (2016)
Zhuang, Y., Sharma, S., Subudhi, B., Huang, H., Wan, J.: Efficient collision-free path planning for autonomous underwater vehicles in dynamic environments with a hybrid optimization algorithm. Ocean Eng. 127 (October), 190–199 (2016)
Leonard, N.E., Paley, D.A., Davis, R.E., Fratantoni, D.M., Lekien, F., Zhang, F.: Coordinated control of an underwater glider fleet in an adaptive ocean sampling field experiment in Monterey Bay. J. Field Robot. 27(6):718–740 (2010)
Li, B., Moridian, B., Kamal, A., Patankar, S., Mahmoudian, N.: Multi-Robot Mission Planning with Static Energy Replenishment. Journal of Intelligent & Robotic Systems (2018)
MahmoudZadeh, S., Powers, D.M.W., Sammut, K., Atyabi, A., Yazdani, A.: A hierarchal planning framework for AUV mission management in a spatiotemporal varying ocean. Comput. Electr. Eng. 67:741–760 (2018)
Huang, H., Zhu, D., Ding, F.: Dynamic task assignment and path planning for multi-auv system in variable ocean current environment. J. Intell. Robot. Syst. Theory Appl. 74(3-4), 999–1002 (2014)
MahmoudZadeh, S., Powers, D.M.W., Sammut, K., Yazdani, A.M., Atyabi, A.: Hybrid Motion Planning Task Allocation Model for AUV’s Safe Maneuvering in a Realistic Ocean Environment. J. Intell. Robot. Syst. 94(1):265–282 (2019)
Ataei, M., Yousefi-Koma, A.: Three-dimensional optimal path planning for waypoint guidance of an autonomous underwater vehicle. Robot. Auton. Syst. 67:23–32 (2015)
Zhu, D., Huang, H., Yang, S.X.: Dynamic Task Assignment and Path Planning of Multi-AUV System Based on an Improved Self-Organizing Map and Velocity Synthesis Method in Three-Dimensional Underwater Workspace. IEEE Trans. Cybern. 43(2):504–514 (2013)
Paull, L., Saeedi, S., Seto, M., Li, H.: AUV navigation and localization: A review. IEEE J. Ocean. Eng. 39(1), 131–149 (2014)
Yu, C., Xiang, X., Lapierre, L., Zhang, Q.: Nonlinear guidance and fuzzy control for three-dimensional path following of an underactuated autonomous underwater vehicle. Ocean Eng. 146(August), 457–467 (2017)
Zeng, Z., Sammut, K., Lian, L., Lammas, A., He, F., Tang, Y.: Rendezvous Path Planning for Multiple Autonomous Marine Vehicles. IEEE J. Ocean. Eng. 43(3):640–664 (2018)
Vazquez-Cuervo, J., Gomez-Valdes, J., Bouali, M., Miranda, L.E., Van der Stocken, T., Tang, W., Gentemann, C.: Using saildrones to validate satellite-derived sea surface salinity and sea surface temperature along the California/Baja coast. Remote Sens. 11(17) (2019)
Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN’95 - International Conference on Neural Networks, volume 4, pp. 1942–1948. IEEE (1995)
Sipper, M., Fu, W., Ahuja, K., Moore, J.H.: Investigating the parameter space of evolutionary algorithms. BioData Min. 11(1):2 (2018)
Lee, C.-Y., Lee, D.: Determination of initial temperature in fast simulated annealing. Comput. Optim. Appl. 58(2):503–522 (2014)
Ben-Ameur, W.: Computing the Initial Temperature of Simulated Annealing. Comput. Optim. Appl. 29(3):369–385 (2004)
Shi, Y., Eberhart, R.C.: Parameter Selection in Particle Swarm Optimization. In: Evolutionary Programming VII, vol. 160, pp. 591–600 (1998)
Acknowledgements
This work is supported by the National Natural Science Foundation of China under Grant No.41706108 and No.41527901, the Shanghai Sailing Program under Grant No.17YF1409600 and the open project of Qingdao National Laboratory for Marine Science and Technology under Grant No.QNLM2016ORP0104.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Xiong, C., Lu, D., Zeng, Z. et al. Path Planning of Multiple Unmanned Marine Vehicles for Adaptive Ocean Sampling Using Elite Group-Based Evolutionary Algorithms. J Intell Robot Syst 99, 875–889 (2020). https://doi.org/10.1007/s10846-020-01155-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-020-01155-7