Volume 17 Number 3
May 2020
Article Contents
Madhusmita Panda, Bikramaditya Das, Bidyadhar Subudhi, Bibhuti Bhusan Pati. A Comprehensive Review of Path Planning Algorithms for Autonomous Underwater Vehicles[J]. International Journal of Automation and Computing, 2020, 17(3): 321-352. doi: 10.1007/s11633-019-1204-9
Cite as: Madhusmita Panda, Bikramaditya Das, Bidyadhar Subudhi, Bibhuti Bhusan Pati. A Comprehensive Review of Path Planning Algorithms for Autonomous Underwater Vehicles[J]. International Journal of Automation and Computing, 2020, 17(3): 321-352. doi: 10.1007/s11633-019-1204-9

A Comprehensive Review of Path Planning Algorithms for Autonomous Underwater Vehicles

Author Biography:
  • Madhusmita Panda received the B. Tech. degree in electronics and instrumentation engineering from the Biju Patnaik University of Technology India in 2003 and M. Tech. degree in computer science engineering from the Biju Patnaik University of Technology, India in 2006. She is a Ph. D. degree candidate in control under communication constraints in Department of Electronics and Telecommunications Engineering, Veer Surendra Sai University of Technology Odisha, India. She is currently working as assistant professor at Department of Electronics and Telecommunication Engineering, Veer Surendra Sai University of Technology Odisha, India. She is a life time member of Institution of Engineers (India) (IEI) and Indian Society for Technical Education (ISTE).Her research interests include formation control of autonomous underwater vehicles, robotics and wireless communication. E-mail: mpanda_etc@vssut.ac.in ORCID ID: 0000-0002-6907-6586

    Bikramaditya Das received the B.Tech. degree in electronics and telecommunications engineering from the Biju Patnaik University of Technology, India in 2017, M. Tech. degree in wireless communication from Department of Electrical Engineering, National Institute of Technology Rourkela, India in 2010, and the Ph. D. degree in control under communication constraints from Department of Electrical Engineering, Veer Surendra Sai University of Technology Odisha, India in 2016. He is currently working as assistant professor at Department of Electronics and Telecommunication Engineering, Veer Surendra Sai University of Technology Odisha, India. He is an associate member of IEI. His research interests include formation control of autonomous underwater vehicles, robotics and wireless communication. E-mail: adibik09@gmail.com ORCID ID: 0000-0001-9734-806X

    Bidyadhar Subudhi has received a Bachelor Degree in Electrical Engineering from National Institute of Technology, India in 1988, M. Tech. degree in Control & Instrumentation from IIT Delhi in 1994 and Ph. D degree in control system engineering from University of Sheffield, UK in 2003. Currently he serves as professor and head, School of Electrical Sciences, Indian Institute of Technology, India. He is a Fellow of the Institution of Engineering & Technology (IET), Telecommunication Engineers (IETE), Institution of Engineers(IE) and Senior Member of Institute of Electrical and Electronics Engineers (IEEE). His research interests include adaptive control, estimation and filtering application to power system, control design for photovoltaic power system, micro grid system and autonomous underwater vehicles. E-mail: bidyadharnitrkl@gmail.com (Corresponding author) ORCID ID: 0000-0003-4383-6783

    Bibhuti Bhusan Pati is currently working as a professor in the Department of Electrical Engineering, Veer Surendra Sai University of Technology Odisha, India. He is the Fellow of Institution of Engineers, member of Indian Society for Technical Education (ISTE), Bigyan Academy, and Engineering Congress. He has published more than 150 papers in reputed journals and conferences. He is the investigator of many All India Council for Technical Education (AICTE) sponsored projects. His research of interests include control system and applications to power system. E-mail: pati_bibhuti@rediffmail.com ORCID ID: 0000-0003-0215-388X

  • Received: 2019-05-13
  • Accepted: 2019-09-18
  • Published Online: 2020-01-04
  • The underwater path planning problem deals with finding an optimal or sub-optimal route between an origin point and a termination point in marine environments. The underwater environment is still considered as a great challenge for the path planning of autonomous underwater vehicles (AUVs) because of its hostile and dynamic nature. The major constraints for path planning are limited data transmission capability, power and sensing technology available for underwater operations. The sea environment is subjected to a large set of challenging factors classified as atmospheric, coastal and gravitational. Based on whether the impact of these factors can be approximated or not, the underwater environment can be characterized as predictable and unpredictable respectively. The classical path planning algorithms based on artificial intelligence assume that environmental conditions are known apriori to the path planner. But the current path planning algorithms involve continual interaction with the environment considering the environment as dynamic and its effect cannot be predicted. Path planning is necessary for many applications involving AUVs. These are based upon planning safety routes with minimum energy cost and computation overheads. This review is intended to summarize various path planning strategies for AUVs on the basis of characterization of underwater environments as predictable and unpredictable. The algorithms employed in path planning of single AUV and multiple AUVs are reviewed in the light of predictable and unpredictable environments.
  • 加载中
  • [1] M. Dinc, C. Hajiyev.  Integration of navigation systems for autonomous underwater vehicles[J]. Journal of Marine Engineering & Technology, 2015, 14(1): 32-43. doi: 10.1080/20464177.2015.1022382
    [2] B. K. Sahu, B. Subudhi, M. M. Gupta.  Stability analysis of an underactuated autonomous underwater vehicle using extended-Routh′s stability method[J]. International Journal of Automation and Computing, 2018, 15(3): 299-309. doi: 10.1007/s11633-016-0992-4
    [3] J. J. Leonard, A. Bahr. Autonomous underwater vehicle navigation. In Springer Handbook of Ocean Engineering, M. R. Dhanak, N. I. Xiros, Eds., Cham, Germany: Springer, pp. 341–358, 2016. DOI: 10.1007/978-3-319-16649-0_14.
    [4] J. C. Kinsey, R. M. Eustice, L. L. Whitcomb. A survey of underwater vehicle navigation: Recent advances and new challenges. In Proceedings of IFAC Conference of Manoeuvring and Control of Marine Craft, IFAC, Lisbon, Portugal, vol. 88, pp. 1–12, 2006.
    [5] D. Soetanto, L. Lapierre, A. Pascoal. Adaptive, non-singular path-following control of dynamic wheeled robots. In Proceedings of the 42nd IEEE International Conference on Decision and Control, IEEE, Maui, USA, vol. 2, pp. 1765–1770, 2003. DOI: 10.1109/CDC.2003.1272868.
    [6] J. Płaskonka. Different kinematic path following controllers for a wheeled mobile robot of (2,0) Type. Journal of Intelligent and Robot Systems, vol. 77, no. 3–4, pp. 481–498, 2015.
    [7] P. Encarnaçao, A. Pascoal. Combined trajectory tracking and path following: An application to the coordinated control of autonomous marine craft. In Proceedings of the 40th IEEE Conference on Decision and Control, IEEE, Orlando, USA, vol. 1, pp. 964–969, 2001. DOI: 10.1109/CDC.2001.980234.
    [8] M. Aicardi, G. Casalino, G. Indiveri, A. Aguiar, P. Encarnaçäo, A. Pascoal. A planar path following controller for underactuated marine vehicles. In Proceedings of the 9th IEEE Mediterranean Conference on Control and Automation, IEEE, Dubrovnik, Croatia, pp. 1–6, 2001.
    [9] A. P. Aguiar, J. P. Hespanha.  Trajectory-tracking and path-following of underactuated autonomous vehicles with parametric modeling uncertainty[J]. IEEE Transactions on Automatic Control, 2007, 52(8): 1362-1379. doi: 10.1109/TAC.2007.902731
    [10] L. Lapierre, D. Soetanto.  Nonlinear path-following control of an AUV[J]. Ocean Engineering, 2007, 34(11-12): 1734-1744. doi: 10.1016/j.oceaneng.2006.10.019
    [11] L. Lapierre, B. Jouvencel.  Robust nonlinear path-following control of an AUV[J]. IEEE Journal of Oceanic Engineering, 2008, 33(2): 89-102. doi: 10.1109/JOE.2008.923554
    [12] T. Liu, Z. P. Dong, H. W. Du, L. F. Song, Y. S. Mao.  Path following control of the underactuated USV based on the improved line-of-sight guidance algorithm[J]. Polish Maritime Research, 2017, 24(1): 3-11. doi: 10.1515/pomr-2017-0001
    [13] Z. Li, J. Sun, S. Oh. Design.  analysis and experimental validation of a robust nonlinear path following controller for marine surface vessels[J]. Automatica, 2009, 45(7): 1649-1658. doi: 10.1016/j.automatica.2009.03.010
    [14] X. B. Xiang, C. Y. Yu, Q. Zhang.  Robust fuzzy 3D path following for autonomous underwater vehicle subject to uncertainties[J]. Computers & Operations Research, 2017, 84(): 165-177. doi: 10.1016/j.cor.2016.09.017
    [15] P. Maurya, A. P. Aguiar, A. Pascoal.  Marine vehicle path following using inner-outer loop control[J]. IFAC Proceedings Volumes, 2009, 42(18): 38-43. doi: 10.3182/20090916-3-BR-3001.0071
    [16] B. Subudhi, D. Atta.  Design of a path following controller for an underactuated AUV[J]. Archives of Control Sciences, 2009, 19(3): 245-259.
    [17] B. Subudhi, K. Mukherjee, S. Ghosh.  A static output feedback control design for path following of autonomous underwater vehicle in vertical plane[J]. Ocean Engineering, 2013, 63(): 72-76. doi: 10.1016/j.oceaneng.2013.01.029
    [18] T. I. Fossen. Guidance and Control of Ocean Vehicles, New York, USA: Wiley, pp. 6–54, 1994.
    [19] C. Silvestre, R. Cunha, N. Paulino, A. Pascoal.  A bottom-following preview controller for autonomous underwater vehicles[J]. IEEE Transactions on Control Systems Technology, 2009, 17(2): 257-266. doi: 10.1109/TCST.2008.922560
    [20] Z. P. Yan, Y. B. Liu, J. J. Zhou, D. Wu. Path following control of an AUV under the current using the SVR-ADRC. Journal of Applied Mathematics, vol. 2014, Article number 476419, 2014.
    [21] D. X. Ji, J. Liu, H. Y. Zhao, Y. Q. Wang. Path following of autonomous vehicle in 2D space using multivariable sliding mode control. Journal of Robotics, vol. 2014, Article number 217875, 2014.
    [22] V. Filaretov, D. Yukhimets. The synthesis of AUV high-precision path following control system on the base of PD-controller. In Proceedings of 2016 International Conference on Computer, Control, Informatics and its Applications, IEEE, Tangerang, Indonesia, pp. 131–136, 2016. DOI: 10.1109/IC3INA.2016.7863037.
    [23] M. Xiao.  Modeling and adaptive sliding mode control of the catastrophic course of a high-speed underwater vehicle[J]. International Journal of Automation and Computing, 2013, 10(3): 210-216. doi: 10.1007/s11633-013-0714-0
    [24] C. Shen, Y. Shi, B. Buckham. Path-following control of an AUV using multi-objective model predictive control. In Proceedings of 2016 American Control Conference, IEEE, Boston, USA, pp. 4507–4512, 2016. DOI: 10.1109/ACC.2016.7526062.
    [25] B. Das, B. Subudhi, B. B. Pati.  Cooperative formation control of autonomous underwater vehicles: An overview[J]. International Journal of Automation and Computing, 2016, 13(3): 199-225. doi: 10.1007/s11633-016-1004-4
    [26] J. Guerrero, E. Antonio, A. Manzanilla, J. Torres, R. Lozano.  Autonomous underwater vehicle robust path tracking: Auto-adjustable gain high order sliding mode controller[J]. IFAC-PapersOnLine, 2018, 51(13): 161-166. doi: 10.1016/j.ifacol.2018.07.272
    [27] Z. P. Yan, J. Y. Li, G. S. Zhang, Y. Wu. A real-time reaction obstacle avoidance algorithm for autonomous underwater vehicles in unknown environments. Sensors, vol. 18, no. 2, Article number 438, 2018.
    [28] J. Li, J. X. Zhang, H. H. Zhang, Z. P. Yan. A predictive guidance obstacle avoidance algorithm for AUV in unknown environments. Sensors, vol. 19, no. 13, Article number 2862, 2019.
    [29] D. L. Li, P. Wang, L. Du.  Path planning technologies for autonomous underwater vehicles-a review[J]. IEEE Access, 2019, 7(): 9745-9768. doi: 10.1109/ACCESS.2018.2888617
    [30] A. E. Bryson. Applied Optimal Control: Optimization, Estimation, and Control, New York, USA: Routledge, 2018.
    [31] Y. Petillot, I. T. Ruiz, D. M. Lane.  Underwater vehicle obstacle avoidance and path planning using a multi-beam forward looking sonar[J]. IEEE Journal of Oceanic Engineering, 2001, 26(2): 240-251. doi: 10.1109/48.922790
    [32] M. Chyba, T. Haberkorn. Autonomous underwater vehicles: Singular extremals and chattering. In Proceedings of the 22nd IFIP TC7 Conference on System Modeling and Optimization, Springer, Turin, Italy, pp. 103–113, 2006. DOI: 10.1007/0-387-33882-9_10.
    [33] M. Chyba, T. Haberkorn, R. N. Smith, S. K. Choi.  Design and implementation of time efficient trajectories for autonomous underwater vehicles[J]. Ocean Engineering, 2008, 35(1): 63-76. doi: 10.1016/j.oceaneng.2007.07.007
    [34] M. Eichhorn. An obstacle avoidance system for an autonomous underwater vehicle. In Proceedings of International Symposium on Underwater Technology, IEEE, Taipei, Taiwan, China, pp. 75–82, 2004. DOI: 10.1109/UT.2004.1405482.
    [35] M. Eichhorn.  A reactive obstacle avoidance system for an autonomous underwater vehicle[J]. IFAC Proceedings Volumes, 2005, 38(1): 331-336. doi: 10.3182/20050703-6-CZ-1902.01325
    [36] K. P. Carroll, S. R. McClaran, E. L. Nelson, D. M. Barnett, D. K. Friesen, G. N. William. AUV path planning: An A* approach to path planning with consideration of variable vehicle speeds and multiple, overlapping, time-dependent exclusion zones. In Proceedings of Symposium on Autonomous Underwater Vehicle Technology, IEEE, Washington, USA, pp. 79–84, 1992. DOI: 10.1109/AUV.1992.225191.
    [37] J. G. Bellingham, J. S. Willcox. Optimizing AUV oceanographic surveys. In Proceedings of Symposium on Autonomous Underwater Vehicle Technology, IEEE, Monterey, USA, pp. 391–398, 1996. DOI: 10.1109/AUV.1996.532439.
    [38] S. Hert, S. Tiwari, V. Lumelsky. A terrain-covering algorithm for an AUV. In Underwater Robots, J. Yuh, T. Ura, G. A. Bekey, Eds., Boston, USA: Springer, pp. 17–45, 1996. DOI: 10.1007/978-1-4613-1419-6_2.
    [39] B. Garau, A. Alvarez, G. Oliver. Path planning of autonomous underwater vehicles in current fields with complex spatial variability: An A* approach. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Barcelona, Spain, pp. 194–198, 2005. DOI: 10.1109/ROBOT.2005.1570118.
    [40] E. S. H. Hou, D. Zheng. Hierarchical path planning with hexagonal decomposition. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, IEEE, Virginia, pp. 1005–1010, 1991. DOI: 10.1109/ICSMC.1991.169819.
    [41] J. Kim, S. Kim, Y. Choo.  Stealth path planning for a high speed torpedo-shaped autonomous underwater vehicle to approach a target ship[J]. Cyber-Physical Systems, 2018, 4(1): 1-16. doi: 10.1080/23335777.2018.1431959
    [42] C. W. Warren.  A technique for autonomous underwater vehicle route planning[J]. IEEE Journal of Oceanic Engineering, 1990, 15(3): 199-204. doi: 10.1109/48.107148
    [43] M. L. Seto. Marine Robot Autonomy, New York, USA: Springer, pp. 178–224, 2012.
    [44] J. C. Latombe. Robot Motion Planning, Boston, USA: Springer, vol. 124, 1991. DOI: 10.1007/978-1-4615-4022-9.
    [45] T. Maki, Y. Noguchi, Y. Kuranaga, K. Masuda, T. Sakamaki, M. Humblet, Y. Furushima.  Low-altitude and high-speed terrain tracking method for lightweight AUVs[J]. Journal of Robotics and Mechatronics, 2018, 30(6): 971-979. doi: 10.20965/jrm.2018.p0971
    [46] I. Spangelo, O. Egeland.  Trajectory planning and collision avoidance for underwater vehicles using optimal control[J]. IEEE Journal of Oceanic Engineering, 1994, 19(4): 502-511. doi: 10.1109/48.338386
    [47] T. W. McLain, R. W. Beard. Successive Galerkin approximations to the nonlinear optimal control of an underwater robotic vehicle. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Leuven, Belgium, vol. 1, pp. 762–767, 1998. DOI: 10.1109/ROBOT.1998.677069.
    [48] N. Sakagami, S. Kawamura. Time optimal control for underwater robot manipulators based on iterative learning control and time-scale transformation. In Proceedings of Oceans 2003. Celebrating the Past··· Teaming Toward the Future, IEEE, San Diego, USA, vol. 3, pp. 1180–1186, 2003. DOI: 10.1109/OCEANS.2003.178015.
    [49] R. P. Kumar, A. Dasgupta, C. S. Kumar.  Real-time optimal motion planning for autonomous underwater vehicles[J]. Ocean Engineering, 2005, 32(11–12): 1431-1447. doi: 10.1016/j.oceaneng.2004.11.010
    [50] N. Sadegh. Time-optimal motion planning of autonomous vehicles in the presence of obstacles. In Proceedings of 2008 American Control Conference, IEEE, Seattle, USA, pp. 1830–1835, 2008. DOI: 10.1109/ACC.2008.4586758.
    [51] M. Soulignac, P. Taillibert, M. Rueher. Time-minimal path planning in dynamic current fields. In Proceedings of 2009 IEEE International Conference on Robotics and Automation, IEEE, Kobe, Japan, pp. 2473–2479, 2009. DOI: 10.1109/ROBOT.2009.5152426.
    [52] A. A. Pereira, J. Binney, G. A. Hollinger, G. S. Sukhatme.  Risk-aware path planning for autonomous underwater vehicles using predictive ocean models[J]. Journal of Field Robotics, 2013, 30(5): 741-762. doi: 10.1002/rob.21472
    [53] Y. Liu and Y. Qiu. Robot path planning based on genetic algorithms with two-layer encoding. Control Theory and Applications, vol. 17, no. 3, pp. 429–432, 2000.
    [54] A. Alvarez, A. Caiti.  A genetic algorithm for autonomous undetwater vehicle route planning in ocean environments with complex space-time variability[J]. IFAC Proceedings Volumes, 2001, 34(7): 237-242. doi: 10.1016/S1474-6670(17)35089-9
    [55] E. Elbeltagi, T. Hegazy, D. Grierson.  Comparison among five evolutionary-based optimization algorithms[J]. Advanced Engineering Informatics, 2005, 19(1): 43-53. doi: 10.1016/j.aei.2005.01.004
    [56] M. P. Aghababa, M. H. Amrollahi, M. Borjkhani. Application of GA, P SO.  and ACO algorithms to path planning of autonomous underwater vehicles[J]. Journal of Marine Science and Application, 2012, 11(3): 378-386. doi: 10.1007/s11804-012-1146-x
    [57] M. P. Aghababa.  3D path planning for underwater vehicles using five evolutionary optimization algorithms avoiding static and energetic obstacles[J]. Applied Ocean Research, 2012, 38(): 48-62. doi: 10.1016/j.apor.2012.06.002
    [58] C. Liu, Z. Q. Gao, W. H. Zhao. A new path planning method based on firefly algorithm. In Proceedings of the 5th International Joint Conference on Computational Sciences and Optimization, IEEE, Harbin, China, pp. 775–778, 2012. DOI: 10.1109/CSO.2012.174.
    [59] J. Xu, Z. P. Yan, X. Q. Bian. Application of improved analytic hierarchy process to AUV′s decision-making. In Proceedings of International Conference on Mechatronics and Automation, IEEE, Harbin, China, pp. 571–575, 2007. DOI: 10.1109/ICMA.2007.4303606.
    [60] A. Stentz. Optimal and efficient path planning for partially known environments. In Intelligent Unmanned Ground Vehicles: Autonomous Navigation Research at Carnegie Mellon, M. H. Hebert, C. Thorpe, A. Stentz, Eds., Boston, USA: Springer, pp. 203–220, 1997. DOI: 10.1007/978-1-4615-6325-9_11.
    [61] A. Stentz. The focussed D* algorithm for real-time replanning. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, Morgan Kaufmann Publishers Inc., Montreal, Canada, pp. 1652–1659, 1995.
    [62] D. Ferguson, A. Stentz.  Using interpolation to improve path planning: The field D* algorithm[J]. Journal of Field Robotics, 2006, 23(2): 79-101. doi: 10.1002/rob.20109
    [63] M. Soulignac, P. Taillibert, M. Rueher. Adapting the wavefront expansion in presence of strong currents. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Pasadena, USA, pp. 1352–1358, 2008. DOI: 10.1109/ROBOT.2008.4543391.
    [64] H. Cao, N. E. Brener, S. Sitharama Iyengar.  3D large grid route planner for the autonomous underwater vehicles[J]. International Journal of Intelligent Computing and Cybernetics, 2009, 2(3): 455-476. doi: 10.1108/17563780910982699
    [65] F. Khorrami, P. Krishnamurthy. A hierarchical path planning and obstacle avoidance system for an autonomous underwater vehicle. In Proceedings of American Control Conference, IEEE, St. Louis, USA, pp. 3579–3584, 2009. DOI: 10.1109/ACC.2009.5160300.
    [66] B. Garau, M. Bonet, A. Alvarez, S. Ruiz, A. Pascual.  Path planning for autonomous underwater vehicles in realistic oceanic current fields: Application to gliders in the western mediterranean sea[J]. Journal of Maritime Research, 2009, 6(2): 5-22.
    [67] C. Vasudevan, K. Ganesan.  Case-based path planning for autonomous underwater vehicles[J]. Autonomous Robots, 1996, 3(2-3): 79-89. doi: 10.1007/BF00141149
    [68] A. Atanassov, L. Antonov.  Comparative analysis of case based reasoning software frameworks jcolibri and myCBR[J]. Journal of the University of Chemical Technology and Metallurgy, 2012, 47(1): 83-90.
    [69] R. Philippsen, R. Siegwart. An interpolated dynamic navigation function. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Barcelona, Spain, pp. 3782–3789, 2005. DOI: 10.1109/ROBOT.2005.1570697.
    [70] C. Petres, Y. Pailhas, P. Patron, Y. Petillot, J. Evans, D. Lane.  Path planning for autonomous underwater vehicles[J]. IEEE Transactions on Robotics, 2007, 23(2): 331-341. doi: 10.1109/TRO.2007.895057
    [71] F. G. Ding, P. Jiao, X. Q. Bian, H. J. Wang. AUV local path planning based on virtual potential field. In Proceedings of IEEE International Conference Mechatronics and Automation, IEEE, Niagara Falls, Canada, pp. 1711–1716, 2005. DOI: 10.1109/ICMA.2005.1626816.
    [72] D. Q. Zhu, C. L. Cheng, B. Sun.  An integrated AUV path planning algorithm with ocean current and dynamic obstacles[J]. International Journal of Robotics and Automation, 2016, 31(5): 382-389.
    [73] W. Z. Zhang, T. Inanc, S. Ober-Blobaum, J. E. Marsden. Optimal trajectory generation for a glider in time-varying 2D ocean flows B-spline model. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Pasadena, USA, pp. 1083–1088, 2008. DOI: 10.1109/ROBOT.2008.4543348.
    [74] M. Eichhorn.  Optimal routing strategies for autonomous underwater vehicles in time-varying environment[J]. Robotics and Autonomous Systems, 2015, 67(): 33-43. doi: 10.1016/j.robot.2013.08.010
    [75] A. Saffiotti. Fuzzy logic in autonomous navigation. Fuzzy Logic Techniques for Autonomous Vehicle Navigation, D. Driankov, A. Saffiotti, Eds., Heidelberg, Germany: Springer, pp. 3–24, 2001. DOI: 10.1007/978-3-7908-1835-2_1.
    [76] V. Kanakakis, K. P. Valavanis, N. C. Tsourveloudis.  Fuzzy-logic based navigation of underwater vehicles[J]. Journal of Intelligent and Robotic Systems, 2004, 40(1): 45-88. doi: 10.1023/B:JINT.0000034340.87020.05
    [77] D. Loebis, R. Sutton, J. Chudley, W. Naeem.  Adaptive tuning of a Kalman filter via fuzzy logic for an intelligent AUV navigation system[J]. Control Engineering Practice, 2004, 12(12): 1531-1539. doi: 10.1016/j.conengprac.2003.11.008
    [78] K. P. Valavanis. Unmanned vehcle navigation and control: A fuzzy logic perspective. In Proceedings of International Symposium on Evolving Fuzzy Systems, IEEE, Ambleside, UK, pp. 200–207, 2006. DOI: 10.1109/ISEFS.2006.251168.
    [79] S. Kundu, D. R. Parhi.  Reactive navigation of underwater mobile robot using ANFIS approach in a manifold manner[J]. International Journal of Automation and Computing, 2017, 14(3): 307-320. doi: 10.1007/s11633-016-0983-5
    [80] A. H. D. Markazi, M. Maadani, S. H. Zabihifar, N. Doost-Mohammadi.  Adaptive fuzzy sliding mode control of under-actuated nonlinear systems[J]. International Journal of Automation and Computing, 2018, 15(3): 364-376. doi: 10.1007/s11633-017-1108-5
    [81] A. C. Schultz. Using a genetic algorithm to learn strategies for collision avoidance and local navigation. In Proceedings of the 7th International Symposium on Unmanned Untethered Submersible Technology, University of New Hampshire, Durham, UK, pp. 213–2151991.
    [82] H. Schmidt, E. Bovio.  Underwater vehicle networks for acoustic and oceanographic measurements in the littoral ocean[J]. IFAC Proceedings Volumes, 2000, 33(21): 105-110. doi: 10.1016/S1474-6670(17)37059-3
    [83] A. Alvarez, A. Caiti, R. Onken.  Evolutionary path planning for autonomous underwater vehicles in a variable ocean[J]. IEEE Journal of Oceanic Engineering, 2004, 29(2): 418-429. doi: 10.1109/JOE.2004.827837
    [84] H. J. Wang, J. Zhao, X. Q. Bian, X. C. Shi. An improved path planner based on adaptive genetic algorithm for autonomous underwater vehicle. In Proceedings of IEEE International Conference Mechatronics and Automation, IEEE, Niagara Falls, Canada, vol. 2, pp. 857–861, 2005. DOI: 10.1109/ICMA.2005.1626663.
    [85] Q. R. Zhang. A hierarchical global path planning approach for AUV based on genetic algorithm. In Proceedings of International Conference on Mechatronics and Automation, IEEE, Luoyang, China, pp. 1745–1750, 2006. DOI: 10.1109/ICMA.2006.257478.
    [86] D. Kruger, R. Stolkin, A. Blum, J. Briganti. Optimal AUV path planning for extended missions in complex, fast-flowing estuarine environments. In Proceedings IEEE International Conference on Robotics and Automation, IEEE, Roma, Italy, pp. 4265–4270, 2007. DOI: 10.1109/ROBOT.2007.364135.
    [87] V. Kanakakis, N. Tsourveloudis. Evolutionary path planning and navigation of autonomous underwater vehicles. In Proceedings of Mediterranean Conference on Control & Automation, IEEE, Athens, Greece, 2007. DOI: 10.1109/MED.2007.4433919.
    [88] C. B. Zhang, Y. J. Gong, J. J. Li, Y. Lin. Automatic path planning for autonomous underwater vehicles based on an adaptive differential evolution. In Proceedings of Annual Conference on Genetic and Evolutionary Computation, ACM, Vancouver, Canada, pp. 89–96, 2014. DOI: 10.1145/2576768.2598267.
    [89] A. Zamuda J. D. Hernández Sosa.  Differential evolution and underwater glider path planning applied to the short-term opportunistic sampling of dynamic mesoscale ocean structures[J]. Applied Soft Computing, 2014, 24(): 95-108. doi: 10.1016/j.asoc.2014.06.048
    [90] A. Zamuda, J. D. Hernández Sosa, L. Adler.  Constrained differential evolution optimization for underwater glider path planning in sub-mesoscale eddy sampling[J]. Applied Soft Computing, 2016, 42(): 93-118. doi: 10.1016/j.asoc.2016.01.038
    [91] J. Witt, M. Dunbabin. Go with the flow: Optimal AUV path planning in coastal environments. In Proceedings of 2008 Australian Conference on Robotics and Automation, ARAA, Canberra, Australia, vol. 2, pp. 1–9, 2008.
    [92] S. M. Zadeh.  Efficient deployment and mission timing of autonomous underwater vehicles in large-scale operations[J]. Robotics, 2018, 2018(): -.
    [93] Z. P. Yan, J. Y. Li, Y. Wu, G. S. Zhang.  A real-time path planning algorithm for AUV in unknown underwater environment based on combining PSO and waypoint guidance[J]. Sensors, 2019, 19(1): 20-. doi: 10.3390/s19010020
    [94] Y. N. Ma, Y. J. Gong, C. F. Xiao, Y. Gao, J. Zhang.  Path planning for autonomous underwater vehicles: An ant colony algorithm incorporating alarm pheromone[J]. IEEE Transactions on Vehicular Technology, 2019, 68(1): 141-154. doi: 10.1109/TVT.2018.2882130
    [95] M. Tavana, M. D. Bailey, T. E. Busch.  A multi-criteria vehicle-target allocation assessment model for network-centric joint air operations[J]. International Journal of Operational Research, 2008, 3(3): 235-254. doi: 10.1504/IJOR.2008.017531
    [96] M. Tavana, B. S. Bourgeowas.  A multiple criteria decision support system for autonomous underwater vehicle mission planning and control[J]. International Journal of Operational Research, 2010, 7(2): 216-239. doi: 10.1504/IJOR.2010.030804
    [97] N. K. Yilmaz, C. Evangelinos, P. F. J. Lermusiaux, N. M. Patrikalakis.  Path planning of autonomous underwater vehicles for adaptive sampling using mixed integer linear programming[J]. IEEE Journal of Oceanic Engineering, 2008, 33(4): 522-537. doi: 10.1109/JOE.2008.2002105
    [98] J. Isern-González, D. Hernández-Sosa, E. Fernández-Perdomo, J. Cabrera-Gámez, A. C. Domínguez-Brito, V. Prieto-Marañón. Path planning for underwater gliders using iterative optimization. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Shanghai, China, pp. 1538–1543, 2011. DOI: 10.1109/ICRA.2011.5980274.
    [99] A. García-Olaya, F. Py, J. Das, K. Rajan.  An online utility-based approach for sampling dynamic ocean fields[J]. IEEE Journal of Oceanic Engineering, 2012, 37(2): 185-203. doi: 10.1109/JOE.2012.2183934
    [100] C. T. Cheng, K. Fallahi, H. Leung, C. K. Tse. An AUVs path planner using genetic algorithms with a deterministic crossover operator. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Anchorage, USA, pp. 2995–3000, 2010. DOI: 10.1109/ROBOT.2010.5509335.
    [101] Z. Zeng, A. Lammas, K. Sammut, F. P. He. Optimal path planning based on annular space decomposition for AUVs operating in a variable environment. In Proceedings of IEEE/OES Autonomous Underwater Vehicles, IEEE, Southampton, UK, 2012. DOI: 10.1109/AUV.2012.6380759.
    [102] Z. Zeng, K. Sammut, F. P. He, A. Lammas. Efficient path evaluation for AUVs using adaptive B-spline approximation. In Proceedings of Oceans, IEEE, Honolulu, USA, 2012. DOI: 10.1109/OCEANS.2012.6405066.
    [103] Z. Zeng, K. Sammut, L. Lian, F. P. He, A. Lammas, Y. H. Tang.  A comparison of optimization techniques for AUV path planning in environments with ocean currents[J]. Robotics and Autonomous Systems, 2016, 82(): 61-72. doi: 10.1016/j.robot.2016.03.011
    [104] P. Yao, S. Q. Zhao.  Three-dimensional path planning for AUV based on interfered fluid dynamical system under ocean current (June 2018)[J]. IEEE Access, 2018, 6(): 42914-42916. doi: 10.1109/ACCESS.2018.2861468
    [105] Y. M. Li, H. Huang, Y. Xu, G. C. Zhang, J. Y. Li, H. D. Qin.  Cognition-based hybrid path planning for autonomous underwater vehicle target following[J]. International Journal of Advanced Robotic Systems, 2019, 16(4): 1-11. doi: 10.1177/1729881419857554
    [106] D. Ferguson, M. Likhachev, A. Stentz. A guide to heuristic-based path planning. In Proceedings of International Conference on Automated Planning and Scheduling, Jerusalem, Israel, pp. 9–18, 2005.
    [107] D. Ferguson, A. Stentz. Anytime RRTs. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, Beijing, China, pp. 5369–5375, 2006. DOI: 10.1109/IROS.2006.282100.
    [108] E. Hernández, M. Carreras, P. Ridao, A path planning algorithm for an AUV guided with homotopy classes. In Proceedings of the 21st International Conference on Automated Planning and Scheduling, Freiburg, Germany, pp. 82–89, 2011.
    [109] T. Ma, Y. Li, Y. Q. Jiang, R. P. Wang, Z. Cong, Y. S. Gong. A dynamic path planning method for terrain-aided navigation of autonomous underwater vehicles. Measurement Science and Technology, vol. 29, no. 9, Article number 095105, 2018.
    [110] E. Vidal, M. Moll, N. Palomeras, J. D. Hernández, M. Carreras, L. E. Kavraki. Online multilayered motion planning with dynamic constraints for autonomous underwater vehicles. In Proceedings of International Conference on Robotics and Automation, IEEE, Montreal, Canada, pp. 8936–8942, 2019. DOI: 10.1109/ICRA.2019.8794009.
    [111] D. R. Thompson, S. Chien, Y. Chao, P. Li, B. Cahill, J. Levin, M. Meisinger. Spatiotemporal path planning in strong, dynamic, uncertain currents. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Anchorage, USA, pp. 4778–4783, 2010. DOI: 10.1109/ROBOT.2010.5509249.
    [112] M. Soulignac.  Feasible and optimal path planning in strong current fields[J]. IEEE Transactions on Robotics, 2011, 27(1): 89-98. doi: 10.1109/TRO.2010.2085790
    [113] M. Z. Yan, D. Q. Zhu, S. X. Yang, S. X.  A novel 3-D bio-inspired neural network model for the path planning of an AUV in underwater environments[J]. Intelligent Automation & Soft Computing, 2013, 19(4): 555-566. doi: 10.1080/10798587.2013.869114
    [114] J. J. Ni, L. Y. Wu, P. F. Shi, S. X. Yang. A dynamic bioinspired neural network based real-time path planning method for autonomous underwater vehicles. Computational Intelligence and Neuroscience, vol. 2017, Article number 9269742, 2017.
    [115] M. Morin, I. Abi-Zeid, Y. Petillot, C. G. Quimper. A hybrid algorithm for coverage path planning with imperfect sensors. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, Tokyo, Japan, pp. 5988–5993, 2013. DOI: 10.1109/IROS.2013.6697225.
    [116] A. Bagnitckii, A. Inzartsev, A. Pavin. Planning and correction of the AUV coverage path in real time. In Proceedings of IEEE Underwater Technology, IEEE, Busan, South Korea, 2017. DOI: 10.1109/UT.2017.7890299.
    [117] D. Q. Zhu, C. Tian, B. Sun, C. M. Luo.  Complete coverage path planning of autonomous underwater vehicle based on GBNN algorithm[J]. Journal of Intelligent & Robotic Systems, 2019, 94(1): 237-249. doi: 10.1007/s10846-018-0787-7
    [118] G. Antonelli, S. Chiaverini, N. Sarkar, M. West.  Adaptive control of an autonomous underwater vehicle: Experimental results on ODIN[J]. IEEE Transactions on Control Systems Technology, 2001, 9(5): 756-765. doi: 10.1109/87.944470
    [119] Z. J. Li, C. G. Yang, N. Ding, S. Bogdan, T. Ge.  Robust adaptive motion control for underwater remotely operated vehicles with velocity constraints[J]. International Journal of Control, Automation and Systems, 2012, 10(2): 421-429. doi: 10.1007/s12555-012-0222-y
    [120] B. K. Sahu, B. Subudhi.  Adaptive tracking control of an autonomous underwater vehicle[J]. International Journal of Automation and Computing, 2014, 11(3): 299-307. doi: 10.1007/s11633-014-0792-7
    [121] Z. Zeng, A. Lammas, K. Sammut, F. P. He, Y. H. Tang.  Shell space decomposition based path planning for AUVs operating in a variable environment[J]. Ocean Engineering, 2014, 91(): 181-195. doi: 10.1016/j.oceaneng.2014.09.001
    [122] Z. Zeng, L. Lian, K. Sammut, F. P. He, Y. H. Tang, A. Lammas.  A survey on path planning for persistent autonomy of autonomous underwater vehicles[J]. Ocean Engineering, 2015, 110(): 303-313. doi: 10.1016/j.oceaneng.2015.10.007
    [123] Z. Zeng, K. Sammut, A. Lammas, F. P. He, Y. H. Tang.  Imperialist competitive algorithm for AUV path planning in a variable ocean[J]. Applied Artificial Intelligence, 2015, 29(4): 402-420. doi: 10.1080/08839514.2015.1004614
    [124] R. S. Yu, Z. Y. Shi, C. X. Huang, T. L. Li, Q. X. Ma. Deep reinforcement learning based optimal trajectory tracking control of autonomous underwater vehicle. In Proceedings of the 36th Chinese Control Conference, IEEE, Dalian, China, pp. 4958–4965, 2017. DOI: 10.23919/ChiCC.2017.8028138.
    [125] Y. S. Sun, J. H. Cheng, G. C. Zhang, H. Xu. Mapless motion planning system for an autonomous underwater vehicle using policy gradient-based deep reinforcement learning. Journal of Intelligent & Robotic Systems, Online First. DOI: 10.1007/s10846-019-01004-2.
    [126] B. Das, S. Das, C. S. Das.  Efficacy of multiband OFDM approach in high data rate ultra WideBand WPAN physical layer standard using realistic channel models[J]. International Journal of Computer Applications, 2010, 2(2): 81-87. doi: 10.5120/621-889
    [127] B. Das, C. S. Das, S. Das.  Interference cancellation schemes in UWB systems used in wireless personal area network based on wavelet based pulse spectral shaping and transmitted reference UWB using AWGN channel model[J]. International Journal of Computer Applications, 2010, 2(2): 88-92. doi: 10.5120/620-890
    [128] D. J. Stilwell, B. E. Bishop.  Platoons of underwater vehicles[J]. IEEE Control Systems Magazine, 2000, 20(6): 45-52. doi: 10.1109/37.887448
    [129] B. Jouvencel, V. Creuze, P. Baccou. A new method for multiple AUV coordination: A reactive approach. In Proceedings of the 8th International Conference on Emerging Technologies and Factory Automation, IEEE, Antibes-Juan les Pins, France, pp. 51–55, 2001. DOI: 10.1109/ETFA.2001.996353.
    [130] E. H. Turner, T. L. Briggs. Responding to unanticipated goals when planning travel for autonomous underwater vehicles. In Proceedings of the 10th Conference on Artificial Intelligence for Applications, IEEE, San Antonia, USA, pp. 493–494, 1994. DOI: 10.1109/CAIA.1994.323623.
    [131] Y. I. Lee, Y. G. Kim, L. J. Kohout.  An intelligent collision avoidance system for AUVs using fuzzy relational products[J]. Information Sciences, 2004, 158(): 209-232. doi: 10.1016/j.ins.2003.07.003
    [132] L. D. Bui, Y. G. Kim.  An obstacle-avoidance technique for autonomous underwater vehicles based on BK-products of fuzzy relation[J]. Fuzzy Sets and Systems, 2006, 157(4): 560-577. doi: 10.1016/j.fss.2005.05.042
    [133] R. Ghabcheloo, A. P. Aguiar, A. Pascoal, C. Silvestre, I. Kaminer, J. Hespanha. Coordinated path-following control of multiple underactuated autonomous vehicles in the presence of communication failures. In Proceedings of the 45th IEEE Conference on Decision and Control, IEEE, San Diego, USA, pp. 4345–4350, 2006. DOI: 10.1109/CDC.2006.376989.
    [134] A. P. Aguiar, R. Ghabcheloo, A. M. Pascoal, C. Silvestre. Coordinated path-following control of multiple autonomous underwater vehicles. In Proceedings of the 17th International Offshore and Polar Engineering Conference, ISOPE, Lisbon, Portugal, vol. 17, pp. 1–7, 2007.
    [135] R. Ghabcheloo, I. Kaminer, A. P. Aguiar, A. Pascoal. A general framework for multiple vehicle time-coordinated path following control. In Proceedings of American Control Conference, IEEE, St. Louis, USA, pp. 3071–3076, 2009. DOI: 10.1109/ACC.2009.5160564.
    [136] I. A. F. Ihle, M. Arcak, T. I. Fossen.  Passivity-based designs for synchronized path-following[J]. Automatica, 2007, 43(9): 1508-1518. doi: 10.1016/j.automatica.2007.02.018
    [137] D. B. Fogel, L. J. Fogel. Optimal routing of multiple autonomous underwater vehicles through evolutionary programming. In Proceedings of Symposium on Autonomous Underwater Vehicle Technology, IEEE, Washington, USA, pp. 44–47, 1990. DOI: 10.1109/AUV.1990.110436.
    [138] X. Wu, Z. Feng, J. Zhu, R. Allen.  GA-based path planning for multiple AUVs[J]. International Journal of Control, 2007, 80(7): 1180-1185. doi: 10.1080/00207170601145289
    [139] S. Mahmoud Zadeh, D. M. W. Powers, K. Sammut, A. M. Yazdani.  A novel versatile architecture for autonomous underwater vehicle′s motion planning and task assignment[J]. Soft Computing, 2018, 22(5): 1687-1710. doi: 10.1007/s00500-016-2433-2
    [140] Y. S. Jung, K. W. Lee, S. Y. Lee, M. H. Choi, B. H. Lee.  An efficient underwater coverage method for multi-AUV with sea current disturbances[J]. International Journal of Control, Automation and Systems, 2009, 7(4): 615-629. doi: 10.1007/s12555-009-0412-4
    [141] J. Almeida, C. Silvestre, A. Pascoal.  Cooperative control of multiple surface vessels in the presence of ocean currents and parametric model uncertainty[J]. International Journal of Robust and Nonlinear Control, 2010, 20(14): 1549-1565. doi: 10.1002/rnc.1526
    [142] X. B. Xiang, C. Liu, L. Lapierre, B. Jouvencel.  Synchronized path following control of multiple homogenous underactuated AUVs[J]. Journal of Systems Science and Complexity, 2012, 25(1): 71-89. doi: 10.1007/s11424-012-0109-2
    [143] B. Rhoads, I. Mezić, A. C. Poje.  Minimum time heading control of underpowered vehicles in time-varying ocean currents[J]. Ocean Engineering, 2013, 66(): 12-31. doi: 10.1016/j.oceaneng.2013.03.012
    [144] B. Das, B. Subudhi, B. B. Pati.  Adaptive sliding mode formation control of multiple underwater robots[J]. Archives of Control Sciences, 2014, 24(4): 515-543. doi: 10.2478/acsc-2014-0028
    [145] E. Peymani, T. I. Fossen.  Path following of underwater robots using Lagrange multipliers[J]. Robotics and Autonomous Systems, 2015, 67(): 44-52. doi: 10.1016/j.robot.2014.10.011
    [146] A. Matos, N. Cruz, A. Martins, F. L. Pereira. Development and implementation of a low-cost LBL navigation system for an AUV. In Proceedings of Riding the Crest into the 21st Century Conference and Exhibition, IEEE, Seattle, USA, pp. 774–779, 1999. DOI: 10.1109/OCEANS.1999.804906.
    [147] L. L. Whitcomb, D. R. Yoerger, H. Singh, J. Howland. Combined Doppler/LBL based navigation of underwater vehicles. Proceedings of the 11th International Symposium on Unmanned Untethered Submersible Technology, Durham, USA, pp. 1–7, 1999.
    [148] J. R. Stack, C. M. Smith, J. C. Hyland. Efficient reacquisition path planning for multiple autonomous underwater vehicles. In Proceedings of Oceans ′04 MTS/IEEE Techno-Ocean ′04, IEEE, Kobe, Japan, pp. 1564–1569, 2004. DOI: 10.1109/OCEANS.2004.1406355.
    [149] P. Rigby, O. Pizarro, S. B. Williams. Towards geo-referenced AUV navigation through fusion of USBL and DVL measurements. In Proceedings OCEANS 2006, IEEE, Boston, USA, 2006. DOI: 10.1109/OCEANS.2006.306898.
    [150] B. V. M. Carvajal, D. A. S. Bueno, R. V. Mejía.  Recent advances in navigation of underwater remotely operated vehicles[J]. Revista Facultad de Ingeniería, 2014, 69(): 167-180.
    [151] J. C. Crowell. Underwater Acoustic Positioning System and Method, U.S. Patent 8009516B2, Aug 2011.
    [152] A. Alcocer, P. Oliveira, A. Pascoal.  Study and implementation of an EKF GIB-based underwater positioning system[J]. Control Engineering Practice, 2007, 15(6): 689-701. doi: 10.1016/j.conengprac.2006.04.001
    [153] L. Paull, M. Seto, J. J. Leonard. Decentralized cooperative trajectory estimation for autonomous underwater vehicles. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, Chicago, USA, pp. 184–191, 2014. DOI: 10.1109/IROS.2014.6942559.
    [154] L. Medagoda, S. B. Williams, O. Pizarro, J. C. Kinsey, M. V. Jakuba.  Mid-water current aided localization for autonomous underwater vehicles[J]. Autonomous Robots, 2016, 40(7): 1207-1227. doi: 10.1007/s10514-016-9547-3
    [155] E. Fiorelli, N. E. Leonard, P. Bhatta, D. A. Paley, R. Bachmayer, D. M. Fratantoni.  Multi-AUV control and adaptive sampling in Monterey Bay[J]. IEEE Journal of Oceanic Engineering, 2006, 31(4): 935-948. doi: 10.1109/JOE.2006.880429
    [156] M. Barisic, Z. Vukic, N. Miskovic. Kinematic simulative analysis of virtual potential field method for AUV trajectory planning. In Proceedings of Mediterranean Conference on Control & Automation, IEEE, Athens, Greece, pp. 1–6, 2007. DOI: 10.1109/MED.2007.4433718.
    [157] L. C. Zhang, M. Y. Liu, D. M. Xu, W. S. Yan.  Cooperative localization and navigation for multiple UUVs[J]. Journal of System Simulation, 2008, 20(19): 5342-5344.
    [158] F. Sun, W. Xu, L. L. Jin, J. L. Li. Path planning of autonomous underwater vehicles for optimal environmental sampling. In Proceedings OCEANS′10 IEEE Sydney, IEEE, Sydney, Australia, 2010. DOI: 10.1109/OCEANSSYD.2010.5603984.
    [159] B. Allotta, L. Chisci, R. Costanzi, F. Fanelli, C. Fantacci, E. Meli, A. Ridolfi, A. Caiti, F. Di Corato, D. Fenucci. A comparison between EKF-based and UKF-based navigation algorithms for AUVs localization. In Proceedings OCEANS 2015- Genova, IEEE, Genoa, Italy, 2015. DOI: 10.1109/OCEANS-Genova.2015.7271681.
    [160] B. Allotta, A. Caiti, R. Costanzi, F. Fanelli, E. Meli, A. Ridolfi.  Development and online validation of an UKF-based navigation algorithm for AUVs[J]. IFAC-PapersOnLine, 2016, 49(15): 69-74. doi: 10.1016/j.ifacol.2016.07.711
    [161] B. Allotta, A. Caiti, R. Costanzi, F. Fanelli, D. Fenucci, E. Meli, A. Ridolfi.  A new AUV navigation system exploiting unscented Kalman filter[J]. Ocean Engineering, 2016, 113(): 121-132. doi: 10.1016/j.oceaneng.2015.12.058
    [162] B. Das, B. Subudhi, B. B. Pati.  Employing nonlinear observer for formation control of AUVs under communication constraints[J]. International Journal of Intelligent Unmanned Systems, 2015, 3(2-3): 122-155. doi: 10.1108/IJIUS-04-2015-0004
    [163] A. P. Aguiar, J. Almeida, M. Bayat, B. Cardeira, R. Cunha, A. Häusler, P. Maurya, A. Oliveira, A. Pascoal, A. Pereira, M. Rufino, L. Sebastião, C. Silvestre, F. Vanni.  Cooperative control of multiple marine vehicles theoretical challenges and practical issues[J]. IFAC Proceedings Volumes, 2009, 42(18): 412-417. doi: 10.3182/20090916-3-BR-3001.0072
    [164] B. Chow. Assigning Closely Spaced Targets to Multiple Autonomous Underwater Vehicles, Master dissertation, University of Waterloo, Canada, 2009.
    [165] A. Bahr, J. J. Leonard, M. F. Fallon.  Cooperative localization for autonomous underwater vehicles[J]. International Journal of Robotics Research, 2009, 28(6): 714-728. doi: 10.1177/0278364908100561
    [166] G. Papadopoulos, M. F. Fallon, J. J. Leonard, N. M. Patrikalakis. Cooperative localization of marine vehicles using nonlinear state estimation. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, Taipei, Taiwan, China, pp. 4874–4879, 2010. DOI: 10.1109/IROS.2010.5650250.
    [167] J. Binney, A. Krause, G. S. Sukhatme. Informative path planning for an autonomous underwater vehicle. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Anchorage, USA, pp. 4791–4796, 2010. DOI: 10.1109/ROBOT.2010.5509714.
    [168] H. W. Jia, J. Zhao.  Output regulation of multiple heterogeneous switched linear systems[J]. International Journal of Automation and Computing, 2018, 15(4): 492-499. doi: 10.1007/s11633-017-1058-y
    [169] L. C. Zhang, D. M. Xu, M. Y. Liu. Cooperative navigation algorithm for two leaders GUUV. In Proceedings of the 4th International Conference on Intelligent Computation Technology and Automation, IEEE, Shenzhen, China, pp. 970–973, 2011. DOI: 10.1109/ICICTA.2011.528.
    [170] B. K. Sahu, M. M. Gupta, B. Subudhi. Fuzzy separation potential function based flocking control of multiple AUVs. In Proceedings of Joint IFSA World Congress and NAFIPS Annual Meeting, IEEE, Edmonton, Canada, pp. 1429–1434, 2013. DOI: 10.1109/IFSA-NAFIPS.2013.6608611.
    [171] B. Das, B. Subudhi, B. B. Pati.  Co-operative control of a team of autonomous underwater vehicles in an obstacle-rich environment[J]. Journal of Marine Engineering & Technology, 2016, 15(3): 135-151. doi: 10.1080/20464177.2016.1247636
    [172] B. Das, B. Subudhi, B. B. Pati.  Co-operative control coordination of a team of underwater vehicles with communication constraints[J]. Transactions of the Institute of Measurement and Control, 2016, 38(4): 463-481. doi: 10.1177/0142331215590010
    [173] A. S. Gadre, D. J. Stilwell. Toward underwater navigation based on range measurements from a single location. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, New Orleans, USA, pp. 4472–4477, 2004. DOI: 10.1109/ROBOT.2004.1302422.
    [174] G. Rui, M. Chitre. Cooperative positioning using range-only measurements between two AUVs. In Proceedings of OCEANS′10 IEEE Sydney, IEEE, Sydney, Australia, 2010. DOI: 10.1109/OCEANSSYD.2010.5603615.
    [175] M. Chitre. Path planning for cooperative underwater range-only navigation using a single beacon. In Proceedings of International Conference on Autonomous and Intelligent Systems, IEEE, Povoa de Varzim, Portugal, 2010. DOI: 10.1109/AIS.2010.5547044.
    [176] M. F. Fallon, G. Papadopoulos, J. J. Leonard, N. M. Patrikalakis.  Cooperative AUV navigation using a single maneuvering surface craft[J]. International Journal of Robotics Research, 2010, 29(12): 1461-1474. doi: 10.1177/0278364910380760
    [177] M. F. Fallon, M. Kaess, H. Johannsson, J. J. Leonard. Efficient AUV navigation fusing acoustic ranging and side-scan sonar. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Shanghai, China, pp. 2398–2405, 2011. DOI: 10.1109/ICRA.2011.5980302.
    [178] T. Y. Teck, M. Chitre. Single beacon cooperative path planning using cross-entropy method. In Proceedings of OCEANS′11 MTS/IEEE Kona, IEEE, Waikoloa, USA, 2011. DOI: 10.23919/OCEANS.2011.6107044.
    [179] Y. T. Tan, R. Gao, M. Chitre.  Cooperative path planning for range-only localization using a single moving beacon[J]. IEEE Journal of Oceanic Engineering, 2014, 39(2): 371-385. doi: 10.1109/JOE.2013.2296361
    [180] C. F. Wang, L. Wei, Z. H. Wang, M. Song, N. Mahmoudian. Reinforcement learning-based multi-AUV adaptive trajectory planning for under-ice field estimation. Sensors, vol. 18, no. 11, Article number 3859, 2018.
    [181] J. Gimenez, A. Amicarelli, J. M. Toibero, F. di Sciascio, R. Carelli.  Iterated conditional modes to solve simultaneous localization and mapping in Markov random fields context[J]. International Journal of Automation and Computing, 2018, 15(3): 310-324. doi: 10.1007/s11633-017-1109-4
    [182] A. Bahr, J. J. Leonard, A. Martinoli. Dynamic positioning of beacon vehicles for cooperative underwater navigation. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, Algarve, Portugal, pp. 3760–3767, 2012. DOI: 10.1109/IROS.2012.6386168.
    [183] A. Khan, I. Noreen, Z. Habib.  On complete coverage path planning algorithms for non-Holonomic mobile robots: Survey and challenges[J]. Journal of Information Science and Engineering, 2017, 33(1): 101-121. doi: 10.6688/JISE.2017.33.1.7
    [184] T. Matsuda, T. Maki, T. Sakamaki, T. Ura.  Performance analysis on a navigation method of multiple AUVs for wide area survey[J]. Marine Technology Society Journal, 2012, 46(2): 45-55. doi: 10.4031/MTSJ.46.2.6
    [185] T. Matsuda, T. Maki, Y. Sato, T. Sakamaki. Cooperative navigation method of multiple autonomous underwater vehicles for wide seafloor survey-Sea experiment with two AUVs. In OCEANS 2014-Taipei, IEEE, Taipei, China, 2014. DOI: 10.1109/OCEANS-TAIPEI.2014.6964386.
    [186] J. M. Walls, R. M. Eustice. Toward informative planning for cooperative underwater localization. In Proceedings of 2014 Oceans – St. John′s, IEEE, St. John′s, Canada, 2014. DOI: 10.1109/OCEANS.2014.7003099.
    [187] A. Zhu, S. X. Yang.  A neural network approach to dynamic task assignment of multirobots[J]. IEEE Transactions on Neural Networks, 2006, 17(5): 1278-1287. doi: 10.1109/TNN.2006.875994
    [188] H. Li, S. X. Yang, M. L. Seto.  Neural-network-based path planning for a multirobot system with moving obstacles[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2009, 39(4): 410-419. doi: 10.1109/TSMCC.2009.2020789
    [189] K. Shojaei.  Neural network formation control of underactuated autonomous underwater vehicles with saturating actuators[J]. Neurocomputing, 2016, 194(): 372-384. doi: 10.1016/j.neucom.2016.02.041
    [190] X. D. Kang, H. L. Xu, X. S. Feng. Fuzzy logic based behavior fusion for multi-AUV formation keeping in uncertain ocean environment. In Proceedings of OCEANS 2009, IEEE, Biloxi, USA, 2009. DOI: 10.23919/OCEANS.2009.5422361.
    [191] M. Abbasi, M. Danesh, M. Ghayour. A path fuzzy planner for autonomous underwater vehicles to avoid moving unknown obstacles. In Proceedings of IEEE International Conference on Mechatronics and Automation, IEEE, Xi′an, China, pp. 1264–1269, 2010. DOI: 10.1109/ICMA.2010.5588564.
    [192] J. Li, R. Zhang, Y. Yang.  AUV Search Target Research Based Meta-heuristic Algorithm[J]. Advanced Science and Technology Letters, 2014, 79(): 22-26.
    [193] Z. Zeng, A. Lammas, K. Sammut, F. P. He, Y. H. Tang, Q. J. Ji. Path planning for rendezvous of multiple AUVs operating in a variable ocean. In Proceedings of the 4th Annual IEEE International Conference on Cyber Technology in Automation, Control and Intelligent, IEEE, Hong Kong, China, pp. 451–456, 2014. DOI: 10.1109/CYBER.2014.6917506.
    [194] Z. Zeng, K. Sammut, A. Lammas, F. P. He, Y. H. Tang.  Efficient path re-planning for AUVs operating in spatiotemporal currents[J]. Journal of Intelligent & Robotic Systems, 2015, 79(1): 135-153. doi: 10.1007/s10846-014-0104-z
    [195] D. Q. Zhu, H. Huang, S. X. Yang.  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[J]. IEEE Transactions on Cybernetics, 2013, 43(2): 504-514. doi: 10.1109/TSMCB.2012.2210212
    [196] H. Huang, D. Q. Zhu, F. Ding.  Dynamic task assignment and path planning for multi-AUV system in variable ocean current environment[J]. Journal of Intelligent & Robotic Systems, 2014, 74(3–4): 999-1012. doi: 10.1007/s10846-013-9870-2
    [197] X. Cao, D. Q. Zhu.  Multi-AUV underwater cooperative search algorithm based on biological inspired neurodynamics model and velocity synthesis[J]. The Journal of Navigation, 2015, 68(6): 1075-1087. doi: 10.1017/S0373463315000351
    [198] X. Cao, D. Q. Zhu, S. X. Yang.  Multi-AUV target searching under ocean current based on PPSO and velocity synthesis algorithm[J]. Underwater Technology, 2015, 33(1): 31-39. doi: 10.3723/ut.33.031
    [199] M. Y. Liu, B. G. Xu, X. G. Peng.  Cooperative path planning for multi-AUV in time-varying ocean flows[J]. Journal of Systems Engineering and Electronics, 2016, 27(3): 612-618. doi: 10.1109/JSEE.2016.00065
    [200] Y. Y. Deng, P. P. J. Beaujean, E. An, E. Carlson.  Task allocation and path planning for collaborative autonomous underwater vehicles operating through an underwater acoustic network[J]. Journal of Robotics, 2013, 2013(): 483095-. doi: 10.1155/2013/483095
    [201] J. D. Hernández, G. Vallicrosa, E. Vidal, È. Pairet, M. Carreras, P. Rida.  On-line 3D path planning for close-proximity surveying with AUVs[J]. IFAC-PapersOnLine, 2015, 48(2): 50-55. doi: 10.1016/j.ifacol.2015.06.009
    [202] R. X. Cui, Y. Li, W. S. Yan.  Mutual information-based multi-AUV path planning for scalar field sampling using multidimensional RRT[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016, 46(7): 993-1004. doi: 10.1109/TSMC.2015.2500027
  • 加载中
  • [1] Ying Li, Xi-Long Liu, De Xu, Da-Peng Zhang. Orientation Measurement for Objects with Planar Surface Based on Monocular Microscopic Vision . International Journal of Automation and Computing, 2020, 17(2): 247-256.  doi: 10.1007/s11633-019-1202-y
    [2] Atlas Khan, Yan-Peng Qu, Zheng-Xue Li. Convergence Analysis of a New MaxMin-SOMO Algorithm . International Journal of Automation and Computing, 2019, 16(4): 534-542.  doi: 10.1007/s11633-016-0996-0
    [3] Tian-Jie Zhang. Unmanned Aerial Vehicle Formation Inspired by Bird Flocking and Foraging Behavior . International Journal of Automation and Computing, 2018, 15(4): 402-416.  doi: 10.1007/s11633-017-1111-x
    [4] Nagendra Kumar, Barjeev Tyagi, Vishal Kumar. Application of Fractional Order PID Controller for AGC Under Deregulated Environment . International Journal of Automation and Computing, 2018, 15(1): 84-93.  doi: 10.1007/s11633-016-1036-9
    [5] Marwa Taleb, Edouard Leclercq, Dimitri Lefebvre. Model Predictive Control for Discrete and Continuous Timed Petri Nets . International Journal of Automation and Computing, 2018, 15(1): 25-38.  doi: 10.1007/s11633-016-1046-7
    [6] Basant Kumar Sahu, Bidyadhar Subudhi, Madan Mohan Gupta. Stability Analysis of an Underactuated Autonomous Underwater Vehicle Using Extended-Routh's Stability Method . International Journal of Automation and Computing, 2018, 15(3): 299-309.  doi: 10.1007/s11633-016-0992-4
    [7] Deqing Huang, Jian-Xin Xu, Xin Deng, Venkatakrishnan Venkataramanan, The Cat Tuong Huynh. Differential Evolution Based High-order Peak Filter Design with Application to Compensation of Contact-induced Vibration in HDD Servo Systems . International Journal of Automation and Computing, 2017, 14(1): 45-56.  doi: 10.1007/s11633-016-1034-y
    [8] Ao-Lei Yang, Wasif Naeem, Min-Rui Fei, Li Liu, Xiao-Wei Tu. Multiple Robots Formation Manoeuvring and Collision Avoidance Strategy . International Journal of Automation and Computing, 2017, 14(6): 696-705.  doi: 10.1007/s11633-016-1030-2
    [9] Edi Kurniawan, Zhen-Wei Cao, Maria Mitrevska, Zhi-Hong Man. Design of Decentralized Multi-input Multi-output Repetitive Control Systems . International Journal of Automation and Computing, 2016, 13(6): 615-623.  doi: 10.1007/s11633-016-1013-3
    [10] Bikramaditya Das, Bidyadhar Subudhi, Bibhuti Bhusan Pati. Cooperative Formation Control of Autonomous Underwater Vehicles: An Overview . International Journal of Automation and Computing, 2016, 13(3): 199-225.  doi: 10.1007/s11633-016-1004-4
    [11] David H. Owens,  Chris T. Freeman,  Bing Chu. Generalized Norm Optimal Iterative Learning Control with Intermediate Point and Sub-interval Tracking . International Journal of Automation and Computing, 2015, 12(3): 243-253.  doi: 10.1007/s11633-015-0888-8
    [12] Bao-Chang Xu,  Ying-Ying Zhang. An Improved Gravitational Search Algorithm for Dynamic Neural Network Identification . International Journal of Automation and Computing, 2014, 11(4): 434-440.  doi: 10.1007/s11633-014-0810-9
    [13] Basant Kumar Sahu,  Bidyadhar Subudhi. Adaptive Tracking Control of an Autonomous Underwater Vehicle . International Journal of Automation and Computing, 2014, 11(3): 299-307.  doi: 10.1007/s11633-014-0792-7
    [14] Modeling and Adaptive Sliding Mode Control of the Catastrophic Course of a High-speed Underwater Vehicle . International Journal of Automation and Computing, 2013, 10(3): 210-216.  doi: 10.1007/s11633-013-0714-0
    [15] Xin-Min Xu, Yao Chen, Wen-Yao Xu, Fang Gong. An Efficient Algorithm for Mobile Localization in Sensor Networks . International Journal of Automation and Computing, 2012, 9(6): 594-599 .  doi: 10.1007/s11633-012-0684-7
    [16] Huan-Yin Zhou, Kai-Zhou Liu, Xi-Sheng Feng. State Feedback Sliding Mode Control without Chattering by Constructing Hurwitz Matrix for AUV Movement . International Journal of Automation and Computing, 2011, 8(2): 262-268.  doi: 10.1007/s11633-011-0581-5
    [17] Ting-Kai Wang,  Quan Dang,  Pei-Yuan Pan. Path Planning Approach in Unknown Environment . International Journal of Automation and Computing, 2010, 7(3): 310-316.  doi: 10.1007/s11633-010-0508-6
    [18] Qing-Jin Peng,  Xiu-Mei Kang,  Ting-Ting Zhao. Effective Virtual Reality Based Building Navigation Using Dynamic Loading and Path Optimization . International Journal of Automation and Computing, 2009, 6(4): 335-343.  doi: 10.1007/s11633-009-0335-9
    [19] Cheng-Dong Wu, Ying Zhang, Meng-Xin Li, Yong Yue. A Rough Set GA-based Hybrid Method for Robot Path Planning . International Journal of Automation and Computing, 2006, 3(1): 29-34.  doi: 10.1007/s11633-006-0029-5
    [20] David H. Owens, Maria Tomas-Rodriguez, Jari J. Hatönen. Limiting Behaviour in Parameter Optimal Iterative Learning Control . International Journal of Automation and Computing, 2006, 3(3): 222-228.  doi: 10.1007/s11633-006-0222-6
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures (38)  / Tables (2)

Metrics

Abstract Views (484) PDF downloads (66) Citations (0)

A Comprehensive Review of Path Planning Algorithms for Autonomous Underwater Vehicles

Abstract: The underwater path planning problem deals with finding an optimal or sub-optimal route between an origin point and a termination point in marine environments. The underwater environment is still considered as a great challenge for the path planning of autonomous underwater vehicles (AUVs) because of its hostile and dynamic nature. The major constraints for path planning are limited data transmission capability, power and sensing technology available for underwater operations. The sea environment is subjected to a large set of challenging factors classified as atmospheric, coastal and gravitational. Based on whether the impact of these factors can be approximated or not, the underwater environment can be characterized as predictable and unpredictable respectively. The classical path planning algorithms based on artificial intelligence assume that environmental conditions are known apriori to the path planner. But the current path planning algorithms involve continual interaction with the environment considering the environment as dynamic and its effect cannot be predicted. Path planning is necessary for many applications involving AUVs. These are based upon planning safety routes with minimum energy cost and computation overheads. This review is intended to summarize various path planning strategies for AUVs on the basis of characterization of underwater environments as predictable and unpredictable. The algorithms employed in path planning of single AUV and multiple AUVs are reviewed in the light of predictable and unpredictable environments.

Madhusmita Panda, Bikramaditya Das, Bidyadhar Subudhi, Bibhuti Bhusan Pati. A Comprehensive Review of Path Planning Algorithms for Autonomous Underwater Vehicles[J]. International Journal of Automation and Computing, 2020, 17(3): 321-352. doi: 10.1007/s11633-019-1204-9
Citation: Madhusmita Panda, Bikramaditya Das, Bidyadhar Subudhi, Bibhuti Bhusan Pati. A Comprehensive Review of Path Planning Algorithms for Autonomous Underwater Vehicles[J]. International Journal of Automation and Computing, 2020, 17(3): 321-352. doi: 10.1007/s11633-019-1204-9
    • Autonomous underwater vehicles (AUVs) are considered as a substantial group of submerged systems known as “unmanned underwater vehicles (UUVs)”. UUVs are generally classified as AUV and remotely operated vehicle (ROV). ROVs are powered and operated from a surface control station by an umbilical cord or remote control. AUVs carry their independent onboard power supply. They are cylindrical in shape and do not have attached cables. AUV designs include “torpedo-like geometry”, “gliders” and “hovering”. AUVs scale from portable to huge sizes of hundred tons[1]. An AUV is a highly nonlinear robotic vessel[2], whose dynamic equation include square terms due to hydrodynamic damping factors. It can operate both above and beneath the ocean′s surface. The AUV propagates by changing its buoyancy in small steps, thereby converting the resultant vertical displacement to horizontal movement. This is accomplished by the interactivity between the surface control station and the water column.

      Motion planning is familiarly associated with “path planning (PP)” and “trajectory planning (TP)”. Path planning is finding the course of points across which AUV has to travel to reach the predefined destination from the starting location, whereas the time history of this journey of the AUV is referred to as trajectory planning. AUV navigation is a very important aspect of path planning. No external communication and “global positioning system (GPS)” signals are available in underwater environments. Thus, without information of direction and restricted power, it is very difficult for an AUV to navigate towards the desired target. Three primary navigation methods have been suggested for AUVs[3] that are “dead-reckoning and inertial navigation systems (DR-INS), acoustic navigation and geophysical navigation”. Referring to the literature available on AUV navigation[4], one can distinguish three different problems that are “close-to-surface navigation, navigation in the mid-depth zone, close-to-bottom navigation”.

      In the path planning control (PPC) problem, an AUV has to traverse a convergent path without temporal constraints[5]. Earlier works on PPC of wheeled robots solved two major issues reported as “path parameterization” and the selection of the termination point on the path[6]. A control system for the coordinated operation of an “autonomous surface craft (ASC)” and an AUV has been designed by Encarnacao and Pascoal[7], which is based on combined trajectory tracking and path planning control. A number of PPC for marine vehicles have been proposed in the literature based on the vehicle′s dynamic[8], Lyapunov theory[9-12], Serret–Frenet equations[13], and fuzzy logic[14]. An “inner-outer control” scheme that can successfully implement path planning controllers on a vast range of AUVs has been presented by Maurya et al.[15] Subudhi et al.[16-18] also proposed a tracking controller and an output feedback controller using AUV dynamics. Silvestre et al.[19] proposed a discrete time PP strategy based on the piecewise affine parameter-dependent model of an AUV. This methodology suggested a solution to the problem of “bottom-planning” of the AUV. The resulting nonlinear controller has been implemented as a gain-scheduled controller using the D-methodology and verified on a dynamic model of the “Infante AUV” in the vertical plane. “Infante” is the Spanish term for “infant” that represents miniature version. Different path planning controllers such as “active disturbance rejection controller (ADRC)”[20], “sliding mode controller (SMC)”[21] and high precision PD controller[22] have also been proposed in the literature. An adaptive SMC controller to cope with speed changes when a high speed AUV surfaces to strike air targets has been proposed by Xiao[23]. A “multi-objective model predictive control (MO-MPC)” has been proposed on the Saab Sea Eye Falcon open-frame ROV/AUV and validated as an effective PPC by Shen et al.[24] In order to improve the performance of AUVs deployed in different applications such as oceanographic survey, search and detection of mines in military missions, it is necessary to develop an appropriate path planning controller which should provide precise and fast control of the propeller system of an AUV. Different PPC employed for formation control of multiple AUVs to follow a specified path while retaining a desired spatial pattern are reviewed by Das et al.[25] Guerrero et al.[26] introduced a second-order SMC named “generalized super-twisting algorithm (GSTA)” for automatic gain adjustment to cope with external disturbances along with uncertain dynamic errors. Yan et al.[27] and Li et al.[28] respectively proposed a “real-time reaction obstacle avoidance algorithm (RRA)” and a “predictive guidance obstacle avoidance algorithm (PGOA)” to deal with complicated terrain structure in the unpredictable oceanic environment based on information provided by “forward looking sonar (FLS)”.

      The underwater environment plays a significant part in the path planning of AUVs. The sea environment is subjected to a large set of challenging factors such as atmospheric factors, coastal factors and gravitational factors[29]. Atmospheric factors include winds, sunlight and precipitation. Coastal factors deal with rivers, glaciers, and gravitational factors include earth rotation, seabed and tides. Navigation of an AUV is majorly affected by wind generated waves, wind and oceanic current. The effect of oceanic current needs much consideration in path determination. The ocean environment is unpredictable and time-varying, but sometimes the effects of the environmental factors can be approximated to produce a predictable behavioral model of the underwater environment. The environment is considered as unpredictable when the changes in the environment are uncertain or unknown. Hence, the underwater environment can be characterized as predictable and unpredictable. A qualitative analysis of different path planning algorithms used in AUV PP is presented in this paper. Various algorithms are reviewed for both single and multiple AUVs based on predictable and unpredictable ocean environments. This review is expected to be very useful for future researchers from the qualitative analysis of different path planning control (PPC) techniques employed in the area of AUV path planning and their merits, demerits and scope of avoiding the difficulties.

      This review is organized as follows. Section 2 reviews the different methodologies employed for the path planning task of a single AUV. Section 3 describes the path planning strategies for multiple AUVs and the paper is concluded in Section 4.

    • In the underwater environment, it is hard to communicate because of the availability of low bandwidth undersea channels. Thus, PP for AUV is a very challenging task. Here we attempt to categorize the work reported in the literature on PP of an AUV considering both the predictable and unpredictable oceanic environments. The path planning algorithms for single AUV are summarized in Table 1.

      Type of environmentMethods & algorithmType of path generatedCollision/Obstacle avoidancePath costAnalysis
      PredictableGraph search and DR[30,31]Time optimalAchievedHigh●Provides time optimized obstacle free path
      ●Ignores the energy and workspace limitations
      ●High computational cost
      PredictableSequential quadratic programming[32-35]]Time optimalAchievedLow●Generates time optimized obstacle free path
      ●Ignores the energy cost and open nodes
      ●Computation complexity increases with increase in the number of “radiated edges”
      PredictableGraph-based shortest path algorithms[36-41]Time and energy optimalAchievedLow●Generates energy cost optimized obstacle free path
      ●Robust to local minima
      ●Computation complexity is high and difficult to use in high-dimensional problem
      PredictableAPF[42-45]Time optimalAchievedLow●Fast method that can be applied to higher dimensional problems
      ●Vulnerable to local minima
      PredictableControl vector parameterization[46]Energy optimalAchievedLow●Energy optimal trajectories are obtained with collision avoidance
      ●Computation cost increase with increasing number of parameters
      PredictableGalerkin′s method[47]Energy optimalPoorModerate●The final solution for a nonlinear optimal station-keeping control problem of an AUV
      ●Computation complexity is high
      PredictableIterative learning control[48-50]Time optimalPoorHigh●Near optimal path following control for AUVs both in two- and three-dimensional environments
      ●Computation complexity is low
      ●Not suitable for slow moving AUVs
      PredictableSymbolic wavefront expansion[51]Time optimalPoorModerate●Predicts the time optimized path and the leaving time of an AUV
      ●Computation complexity is high
      ●Only simulation analysis is available
      PredictableMDP planning[52]Time optimalAchievedModerate●Provides safe and reliable path for slow moving AUVs in the coastline
      ●Computational complexity is high
      PredictableMetaheuristic algorithms[53-58]Energy optimalPoorLow●Searches the solution from a large solution space
      ●Requires effective memory management
      PredictableMCDA[59]Time optimalPoorLow●Provides time optimized path
      ●Computational complexity is high
      UnpredictableGraphical method[60-66]Time and energy optimalPoorLow●Time optimized, safe paths with less energy cost
      ●Computation complexity is low
      ●Continuous cost updations applied to minimize expansions of state and the computational costs
      ●Field D* assumes constant AUV thrust that neglects the effect of sea currents
      ●For A*, the spatial structure of the current field plays a major role
      UnpredictableCBR[67, 68]Time optimalPoorLow●Generates shorter and reliable path
      ●Only simulation analysis is available
      UnpredictableFM[69, 70]Time optimalPoorModerate●Low computational complexity
      ●Converges to a time optimal trajectory on a discrete grid
      UnpredictablePotential field[71, 72]Time optimalPoorLow●Achieved obstacle avoidance and generates time optimized path
      ●Susceptible to local minima
      UnpredictableNTG[73, 74]Time optimalPoorModerate●Provides time optimized path considering the effect of both the AUV characteristics and the dynamic ocean current
      ●High computation complexity
      ●Depends on spatial structure of the current field
      UnpredictableFuzzy logic[75-79]Time optimalAchievedLow●Intelligent system that achieves collision avoidance
      ●Deals with inaccuracy and uncertainty with low computational cost
      ●Somehow depends on type of AUVs involved
      UnpredictableEvolutionary algorithms[80-89]Time optimalAchievedLow●Minimizes the time expanses
      ●Searches the solution from a large solution space
      ●GA requires effective memory management
      ●DE provides time optimized path in the corridor area but untimely collisions in obstruct evaluation of some good paths
      ●The cost of computation is high
      UnpredictableSwarm optimization[90-93]Time and Energy optimalAchievedLow●Energy optimal paths are obtained by exploiting ocean currents
      ●Less susceptible to “large local minima” when the “cost surface” is complex
      ●Computational complexity increases for higher dimensional problems
      UnpredictableDynamic MCDA[94, 95]Energy optimalPoorModerate●Minimize the AUV PP solution space and maximize “time-on station” in hostile environments
      ●Requires more time for computation
      UnpredictableMILP[96]Time optimalAchievedHigh●Flexible and can successfully handle constraints like intervehicle communication and synchronization, collision avoidance, etc.
      ●Suffers from an exponential increase in computational time in large solution space
      UnpredictableIterative optimization[97, 98]Time optimalPoorLow●Provides a balance between time and space parameters of marine sampling
      ●Can be applied to any “sequential sampling” schemes with any degree of available feature information
      ●Computational complexity is high
      UnpredictableHybrid algorithms[99-104]Time optimalPoorModerate●Time optimized trajectory with fast convergence speed and less computational cost
      ●The search space is restricted
      UnpredictableRRT[105-109]Time optimalAchievedLow●Rapidly provides some good obstacle free paths
      ●Low computational complexity
      ●Simulation results are obtained only for 2D environments
      UnpredictableWave front expansion[110,111]Time optimalPoorLow●Detects the dangerous destinations that have to be avoided with low computational cost
      ●Only simulation results are available
      UnpredictableBio-inspired neuro-dynamics[112, 113]Time optimalAchievedLow●Deals with complex repetitive route computing problem when the obstacle dimension exceeds the sensor′s detection range
      ●High computational time
      ●Longer PP time
      UnpredictableCPP[114-116]Time optimalAchievedLow●Provides a complete coverage path with low computational cost
      ●Requires knowledge of the water area bounds and the distance between tracks
      UnpredictableAdaptive control law[117,119]Time optimalPoorLow●Provides a path planning controller with poorly known and time-varying dynamic parameters
      ●The results obtained are satisfactory within the constraints of the “sonar sensory system”
      ●High computational cost
      UnpredictableSSD[120, 121]Time optimalAchievedModerate●Generate optimal path in dynamic and hostile environment with low computational cost
      ●Supports long range operations
      ●Only simulation results available
      UnpredictableICA[122]Time optimalPoorLow●Provides a control point coordinate optimization algorithm for generating a “spline path”
      ●Computational complexity is high
      UnpredictableReinforcement learning[123,124]Time optimalAchievedModerate●Solves MPP and can be easily extended for application involving unknown environments
      ●Able to cope with effect of sea current
      ●Successful in avoiding obstacle
      ●Computational complexity is high

      Table 1.  Comparison of path planning algorithms for single AUV

    • The underwater environment is subjected to variability. But for many applications, the effect of the marine environment in the path planning can be approximated and considered as predictable. In a predictable environment, path planning is concerned with traversing a collision-free trajectory from initial to end position while avoiding the obstacles in the path of the AUV. Various optimization algorithms are further available in the literature to generate optimal paths for single AUV as represented by Fig. 1.

      Figure 1.  Summary of path planning control of a single AUV

    • The PP problem can be formulated as generating a series of state changes along a graph from some primary state to a final state. The “geometrical graph” is a mathematical model which describes the field of activity with all its attributes using different procedures such as “dynamic programming (DP)”. DP[30] is generally employed as a “graph-searching” technique for a weighted graph. Here, weights symbolize the associated cost of an edge. There exist many theories to explain an obstacle environment as a directed graph with a minimum number of vertices and edges to decrease the computing time. Petillot et al.[31] designed a time minimal obstacle free PP framework for AUVs based on a “multi-beam forward looking sonar sensor” (Fig. 2). Here the input data has been segmented to extract the required information. However, this approach ignored the energy and workspace limitations.

      Figure 2.  Phases of sonar based path planning[31]

    • The “sequential quadratic programming (SQP)” technique is based on a constructive solid geometry. SQP describes the obstacles as constraints to be satisfied during exploring the space while minimizing the “Euclidean distance” to the destination. The problem of “local minima” and fast-moving obstacles has been well addressed in this context. Chyba et al.[32, 33] applied SQP to obtain time-optimal paths parameterized by the switching times for a distinctive group of “fully actuated” AUVs called “underwater gliders”. The approach employed the maximum principle for optimizing the structure of “singular extremals”, but ignored the energy cost. Another obstacle avoidance scheme comprised of a two-level framework is proposed by Eichhorn[34], that emphasizes search rate and space requirements. The upper level is concerned with the course planning to generate a locus for the AUV to follow. The lower level deals with obstacle avoidance and deactivation of the course module using a “reactive controller”. This method relied on local optimization and instantaneous sensor detected obstacle information, but neglected the open nodes. The greater number of “radiated edges”[35] causes increase in lengths which is impractical for reflecting the variation in current flow.

    • A graph-based A* path planning algorithm has been implemented by Carroll et al.[36] using a quad tree to separate a large two-dimensional sea environment. A sub optimal minimum cost path is generated as the path is bound to pass through the centers of quadrants. A “post-processing phase” has been used to examine and remove an unnecessary node to generate a cost-effective collision free path. A path is regarded as collision free if it does not cross obstacles, “active exclusion zones”, or ground masses; collectively known as non-entry regions. The oceanic environment under the influence of strong currents, spatial and temporal variations increases the energy cost of AUV missions. Thus, an AUV path with a minimum energy cost is needed during missions with extensive energy requirements. Bellingham and Willcox[37] used error matrix calculations and obtained an energy efficient path that ensured spatiotemporal coverage in oceanographic sampling. Tradeoffs between resolution, total survey time, and vehicle speed have been made to satisfy platform constraints. A shortest route optimization problem has been formulated by Hert et al.[38], that optimizes the energy cost while guaranteeing terrain coverage with a sonar system. Garau et al.[39] adapted the A* algorithm, assuming constant and two-dimensional currents. In this method, paths were constrained to a grid with the axis aligned or 45° angled movements and unable to take benefits of currents while the AUV thrust is assumed constant. Another possibility to define a mesh has been reported by Hou and Zheng[40], based on hexagons where there were six direct neighbors with the same distances to their centers. Kim et al.[41] introduced “stealth path planning algorithm” to decrease the time of travel of a back propelled “torpedo-shaped AUV” to reach a “target ship” faster without being found in a calm oceanic environment. This approach used a “Dijskstra algorithm” based on turning angle variation to plan a time optimal path and also to reduce acoustic measurement at the target end by minimizing the sound generated by the torpedo. “Graph-searching” techniques are robust to local minima, but are difficult to use in high-dimensional problems.

    • The “artificial potential fields (APF)” scheme has been suggested by Warren[42] in 1990. A potential field algorithm along with other algorithms applied to AUV path planning is also discussed in [43]. APF methods are implemented to the obstacles and target points[44] and the resultant field determines the route of an AUV. A cost function has been introduced to evaluate a path and to optimize the path parameters for a minimum value. APF is a fast method that can be applied to higher dimensional problems, but is vulnerable to local minima. Maki et al.[45] proposed a path planner using potential fields for a seabed imaging application. The AUVs are employed at low altitude with high surge velocity and don′t need expensive sensors.

      Algorithm 1. APF pseudocode[43]

      Initialize: Map M, starting point mstart, Destination point mend

      Decide path P

      for all location m in M do

      $ {F_{att}}\left( m \right) \leftarrow \dfrac{1}{2}\varepsilon {\left| {m - {m_{goal}}} \right|^2}$, where Fatt(m) is attraction force at point m

      for all obstacle Oi, i=1, 2,···, n do

      if m is O then

      Frep(m)←∞, where Frep(m) is the repulsive force at point M

      else

      Dminimumdistancetopolygon(m, Oi)

      CiclosestPointOnObstacle(m, Oi)

      if D<Mi* then

      $ {F_{rep}}_i\left( m \right) \leftarrow \eta \left( {\dfrac{1}{{M_i^*}} - \dfrac{1}{{{D_i}\left( m \right)}}} \right)\dfrac{{m - {C_i}}}{{{D_i}^2\left( m \right)}}$

      else

      Frepj(m)←0

      end if

      end if

      end for

      end for

      while m mend do

         Add m to P

      $ \nabla F\left( m \right) \leftarrow \nabla {F_{att}}\left( m \right) + \mathop \sum \nolimits_{i = 1}^n \nabla {F_{rep}}_j\left( m \right)$

      $m \leftarrow m - \Delta \nabla F\left( m \right)$

      end while

    • Path planning in three dimensional spaces is a “nonlinear optimal control problem (NOCP)” which results in an open-loop path that has to be calculated off line. CVP and single shooting methods have been applied by Spangelo and Egeland[46] to solve this NOCP problem. Energy optimal trajectories are obtained with collision avoidance with this strategy. The proposed method included gradient calculations and computation of a new search direction. Thus, the cost, increases with increasing number of parameters.

    • These methods are employed for solving partial differential equations. Galerkin′s methods are discretised as “finite element methods (FEMs)”, “spectral element methods (SEMs)”, and “spectral methods”. These methodologies used integrals of functions that can be solved to provide arbitrary shapes and are geometrically more flexible. A control approach using numerical approximation results for the “Hamilton-Jacobi-Bellman equation” has been proposed in [47]. A repetitive “Galerkin′s method” has been employed to obtain the final solution for a nonlinear optimal station-keeping control problem of an AUV.

    • A time optimal control method using “repetitive learning control and time-scale transformation” has been presented in [48] for AUVs. This approach assumed fixed spatial paths of motions for AUV and physical parameter estimation is not essential to formulate an input torque pattern. The problem of real-time optimal PP for AUV with symmetric thruster configuration has been addressed in [49] to estimate an analytical solution. It yielded a near optimal path following control for AUVs both in two- and three-dimensional environments (Fig. 3). This approach is not suitable when the speed of the AUV is very low as at very low speed, the mathematical results differ from approximate results. Dynamic programming (DP) has been used to address, the time optimal PP problem of AUVs in the presence of the hindrances by Sadegh[50].

      Figure 3.  An unstable AUV moving in a vertical plane[49]

    • An appropriate selection of departure time of an AUV is an important issue for many applications as it varies with the time. Soulignac et al.[51] employed “symbolic wavefront expansion (SWE)”, to address this problem. Functions with appropriate operators have been used in place of numerical values. This method predicted both the path and the leaving time of an AUV while reducing the travel time.

      Algorithm 2. Wavefront expansion pseudocode[43]

      Initialize: Map M, starting cell mstart, destination cell mgoal

      Decide path P

      mark all free space as notvisited

      indexindex+1

      mgoalindex

      mark mgoal as visited

      while mstart is unvisited do

      set all notvisited cells neighboring a cell with value index to index + 1

      mark all cells with value index + 1 as visited

      indexindex+1

      end while

      mmstart

      add m to P

      while mgoal not in P do

      m←with neighbor of m with minimum value

      add m to P

      end while

    • Operation of slow-moving AUVs along the coastline involves the threat of collision with ships and land. The strong water current levels in these regions can remarkably change the planned AUV path. For a safe and reliable AUV functioning in such coastline areas, Pereira et al.[52] introduced two stochastic planners: a “minimum expected risk planner” and a risk alert “Markov decision process” (MDP). Both of them utilized the sea current predictions probabilistically. The approach adopted the “shortest-path search” and “MDP planning” algorithms to reduce surfacing threat for AUVs.

    • The metaheuristic algorithms include “evolutionary algorithms (EAs)” and “swarm intelligence (SI) optimization”. The EAs are probabilistic search techniques that imitate the biological evolution. The SIs are “population based” optimizations that inherit the societal behavior of natural species. The best example of EA is “genetic algorithm (GA)” and examples of SI are “memetic algorithm (MA)”, “particle swarm optimization (PSO)”, “ant colony optimization (ACO)” and “shuffled frog leaping algorithm (SFLA)”, “cuckoo search (CS)”, “fire fly optimization (FLO)”, etc. The intelligent algorithms such as GA, MA, PSO, ACO, and SFLA are suggested to obtain time and energy efficient paths, by minimizing a nonlinear “time-energy” cost function. The genetic algorithm (GA) has been preferred for AUV PP in large, but static environments[53, 54]. It searches the solution from a large solution space, thus requires effective memory management.

      Elbeltagi et al.[55] reported that linear programming and DP techniques, often fail in solving “nonlinear optimization problems (NOPs)”. NOPs include many variables and the objective functions are nonlinear. For this kind of problem, evolutionary algorithms can be considered as an alternative solution. Energy minimization for AUV path planning requires the solution of a NOP with nonlinear state space equations and a “non-quadratic” performance index that results in a “two-point boundary value problem (TPBVP)”. Aghababa et al.[56, 57] suggested numerical solutions to this problem using GA, MA, PSO, ACO and SFLA methods. The research suggested the existence of some sources of energy in the ocean. When an AUV passed through any of these sources, it spends some extra energy. In this research, Aghababa et al. computed near-optimal trajectories using the “conjugate-gradient (CG)” method and three-dimensional optimal trajectories applying the “conjugate gradient penalty (CGP)” method in functional space. A new 3D path planning method for AUV based on a modified firefly algorithm has been presented by Liu et al.[58] The algorithm parameters and the random movement steps are adapted to the implementation process. An autonomous planning scheme has been instigated to avoid instances of invalid paths. An “excluding operator” is used to avoid collision with obstacles and a “contracting operator” is used to increase the rate of convergence (Fig. 4).

      Figure 4.  Flowchart of 3D path planning using a Firefly algorithm[58]

    • “Multi-criteria decision analysis (MCDA)” is a familiar term for modeling and simulation of AUVs. Xu et al.[59] developed a hierarchical weighted-sum model for AUV decision-making with an “analytic hierarchy process (AHP)” based on expending energy, time and distance covered and accomplished the goal assuming a static environment.

    • The path planning controller is a necessary component for navigating AUV in an unpredictable environment. The performances of classical PP algorithms in “artificial intelligence” are not satisfactory. These algorithms are also unsuitable for systems moving in a hostile oceanic environment with real-time constraints. To resolve the aforesaid issues, methods such as evolutionary algorithms, graph search method, FM based algorithms, rapidly-exploring random tree (RRT), etc. have been proposed and many more are still to come.

    • The graphical methods focused on PP algorithms to generate “time-optimal” paths for AUVs travelling from source to destination positions in an environment subjected to dynamic sea current effect. This is a difficult task to accomplish as the available information is incomplete and inaccurate. Anthony Stentz introduced a new algorithm D*[60] that is dynamic in nature and allows changes in the parameter′s effecting arc cost during the solving process. The original D* algorithm consists of two functional phases, namely “process-state” and “modify-cost”. The “process-state” function computes optimal cost of the path from source to destination while the “modify-cost” function allows the affected states that undergo modification of the arc cost to enter in the “open list”. The “open list” provides the information about modifications in the arc cost and path cost to different states in space. He has also proposed an extension to the D* algorithm known as focused D*[61] for PPC of AUVs. In this method, continuous cost upgradation has been applied to minimize expansions of the state and the computational costs.

      The “field D* algorithm” is a modified D* algorithm[62] to find complete and optimal paths that eliminate unnecessary turning. In this approach, uniform resolution grid represented the environment. Only linear energy cost functions have been used and the strong current which may lead to infeasible paths has not been considered. This scheme produced the pathological cases when the “gradient descent (GD)” method is used to obtain a path. Soulignac et al.[63] improvised this approach to work under the influence of strong current by employing a nonlinear cost function. But they assumed constant AUV thrust that neglects the effect of sea currents.

      A 3D A* route planner, called “3DPLAN”, has been developed by Cao et al.[64] It could run efficiently for larger grids and is guaranteed to give the optimum path. A “maritime underwater navigation system (MUNS)” for AUVs has been proposed by Khorrami and Krishnamurthy[65] (Fig. 5). The proposed system has a layered architecture comprising of a “wide area planner (WAP)” and a “local area planner (LAP)”. MUNS being flexible can be employed for “point-to-point” motion tracking, object investigation, route planning, and location searching. It extended the operational capabilities of AUVs in “cluttered and littoral” environments, but its application has been restricted to lower dimensions only. Planning safe paths with less energy cost has been a major challenge for AUV path planning as complex spatial variability of ocean environments can jeopardize its mission. The benefits of PP in oceanic environments subjected to space variations have been discussed by Garau et al.[66] in terms of travelling time. It generates time optimal paths in the realistic ocean environment. Here, spatial structure of the current field plays as major roles in PP.

      Figure 5.  Conceptual MUNS architecture[65]

    • Case-based reasoning has been presented by Vasudevan and Ganesan[67] for AUV mission planning. The navigation environment representation included previous paths and entities in the navigational space. Then the routes have been retrieved and repaired. Further, the scheme for incorporating new paths has been adopted. CBR is based on reasoning and can be seen as a cycle of the planning four tasks: retrieve, reuse, revise, and retain.[68] CBR generates a shorter and reliable path using an enriched “map database” as shown in Fig. 6.

      Figure 6.  Phases of CBR[68]

    • Sethian′s “fast marching algorithm (FMA)” is an essential aid to path planning with fewer complications. An FMA based path planner has been suggested in [69] with active re-planning. It minimizes the rate of failure when unknown terrains appear in the path. But no heuristic has been employed to improve the exploration speed. Petres et al.[70], proposed an FM method, i.e., precise and able to control the curvature of the final trajectory with consideration to vehicle kinematics (Fig. 7). The path planners are capable of managing smooth fields of force. A multi-resolution scheme has been used to fasten the overall procedure by coupling “octree decomposition” along with “adaptive mesh generation”. The proposed FM is of low complexity and converges to an optimal trajectory on a discrete grid.

      Figure 7.  Communication interface for both simulator and real AUV remains the same using a communication protocol providing transparent access[70].

    • A potential-field-based method in conjunction with the virtual force concept to maneuver AUV in an unknown environment has been illustrated by Ding et al.[71], that resolved the local minima problem in PFA based path following. Zhu et al.[72] presented an integrated AUV PP algorithm by incorporating “velocity synthesis (VS)” and “artificial potential field (APF)” methods together. An improvised APF algorithm has been used for obstacle avoidance and an optimized path has been generated using VS method.

    • An optimal path planning control for an AUV subjected to dynamic ocean currents has been suggested by Zhang et al.[73] The “nonlinear trajectory generation (NTG)” algorithm has been applied to a “B-spline” glider model. The cost function is a weighted sum of a time and energy expanses. A “graph based” PP algorithm in a dynamic environment has been proposed by Eichhorn[74] considering the effect of both the AUV characteristics and the dynamic ocean current. But this path planning algorithm depends on spatial structure of the current field.

    • Many authors advocated the use of fuzzy logic in autonomous navigation as it does not necessitate an explicit mathematical modelling of the system to control. However, this leads two main limitations. First, classical tools cannot be used for formal design without mathematical models. Secondly, the designed controller has not been guaranteed to produce the desired behavior[75]. An effective and standard path planning control for AUV with collision avoidance has been developed by Kanakakis et al.[76] applying FL. The proposed controller is simple, modular, expandable and applicable to any type of AUV. It consists of three modules known as “sensor fusion”, “collision avoidance” and “motion control” as shown in Fig. 8. Though the model is assumed to be independent of the type of the AUV, knowledge of the underwater environment and the obstacles, the “motion control” module was still dependent on the type of AUV involved.

      Figure 8.  Overall AUV navigation & control architecture[76]

      Loebis et al.[77] implemented an intelligent navigation system by using “global positioning system (GPS)” and “inertial navigation system (INS)” sensors. A “simple Kalman filter (SKF)” and an “extended Kalman filter (EKF)” have been used to merge the information of INS sensors and GPS for AUV applications. Both these filters are sensitive to variation of sensor noise attributes. Thus, FL is used for the adaptation of initial statistics to these variations. The effectiveness of FL as an alternative to analytical approaches and its applicability as a “modeling tool” that deals with inaccuracy and uncertainty has been advocated by Valavanis[78]. An “adaptive network based fuzzy inference system (ANFIS)”[79] has been proposed for controlling multiple variables during AUV navigation. This model can find time optimized path for AUV. An improved “adaptive fuzzy sliding mode control (AFSMC)” for “under-actuated MIMO” system with uncertainties has been recently studied in [80].

    • Many unforeseen events may occur, while an AUV is in the ocean, leading to violation of the constraints of the existing path. A GA based learning system[81] has been used to develop a robust collision avoidance algorithm for PP of AUV in such real time situations (Fig. 9). In coastal regions, the ocean environment varies both in space and time. Here AUV also encounters strong current fields. Thus, mission planning that minimizes the energy expense is always encouraged. This can be achieved by integrating environmental space–time variability information into existing PP algorithms[82]. GA is useful for finding the solution from a large population, but required proper memory management.

      Figure 9.  Simulation model-based learning[81]

      The PP problems with directional restrictions has been explained by Alvarez et al.[83] The “genetic operators” are employed to converge the local minima due to structure of the current field to the global minimum. DP has been used as an optimizing technique to generate a safe route for the AUV employed in energy-exhaustive missions by minimizing the energy cost. Here the thrust on the AUV has been assumed to be constant. Zero energy paths cannot be generated due to the lack of decision freedom. When the problem scale increases, the deterministic algorithms encounter problems as PP for AUVs is very complex. An adaptive GA has been presented by Wang et al.[84] that can explore the larger solution space to find an approximate global solution for the AUV path planning problem. This approach generated a real time optimal, obstacle-free path with lesser waypoints in a wide underwater environment. Zhang[85] assumed a static underwater environment and applied GA to path planning of an AUV. It can find nearly global optima for AUV navigation with minimal energy expenditure. Another approach to AUV path planning has been proposed by Kruger et al.[86] They formulated an optimization problem depending on the thrust of the AUV to minimize both energy and time cost. A path planning and navigation methodology has been suggested by Kanakakis and Tsourveloudis[87], applicable to different types of AUVs. It enabled three separate operational levels that are “planning, optimization and motion control”. Planning and optimization are done offline before starting the mission, while motion control is accountable for the online navigation with collision avoidance of the AUV.

      Zhang et al.[88] defined the path of AUVs as a series of points in the problem domain. The problem domain has been divided into parallel sub-domains. A subdomain is known as a “waypoint” and represented by grids (Fig. 10). The path of the AUV has been obtained by connecting these “waypoints”. Path cost is calculated as a function of path length, energy cost, safety and curvature restrictions of AUVs by employing “penalty method”. The quality of paths has been evaluated using an adaptive “differential evolution (DE)” algorithm. Zamuda and Hernández Sosa[89] addressed the “underwater glider path planning (UGPP)” problem with specific “land constraints” by applying DE. When a collision is detected, the glider velocity became zero and it remained in that location till the simulation stops. Untimely collisions obstruct evaluation of some good paths and no special corridor to the sea has been specified. A “corridor-constrained” UGPP where the resultant AUV paths have been completely restricted to a “corridor area” throughout the borderline of an oceanic “sub-mesoscale eddy” has been suggested using a self-adjusting DE algorithm employing level adjustment in [90].

      Figure 10.  Individual component[88]

    • A path planning algorithm based on “parallel swarm search (PSS)” has been proposed by Witt and Dunbabin[91]. It is employed for time-stretched AUV missions in a dynamic underwater environment where both time and space are the variables. The energy optimal paths are obtained by exploiting ocean currents to accomplish missions. Also, there may be a possible tradeoff between time and energy expanses to obtain solutions. PSS minimizes the vulnerability of the solutions to “large local minima” when the “cost surface” is complex.

      Zadeh[92] employed the “firefly optimization algorithm (FOA)” to design a connectivity module that comprises of a route planner and path planner. It is designed for real-time operation with wider coverage and limited battery life. It is robust and capable of re-routing by reordering nodes as per varying water currents to provide time and energy optimal path.

      Yan et al.[93] analysed PP of AUV in a dynamic, unpredictable underwater work space as a “multi-objective optimization problem”. He proposed a “real-time” PP algorithm by integrating PSO with “waypoint guidance”. He has applied “multi-beam forward looking sonar (FLS)” for obstacle detection and PSO for searching and generating optimized waypoints. This method is suitable for finding a flexible optimal path as per the assigned task and successfully avoids collision.

      Ma et al.[94] integrated the essence of alarming with the guiding function of basic ACO to develop an algorithm known as “alarm pheromone-assisted ant colony system (AP-ACS)”. The cost function is intended to optimize the path length and energy uses while avoiding collision.

    • Tavana et al.[95, 96] proposed a dynamic MCDA system (Fig. 11). The proposed method considered dynamic surface current to provide a reasonable path planning strategy with defined objectives. MCDA with analytical network process and fuzzy sets is employed in the framework to minimize the AUV PP solution space and maximize “time-on station” in hostile environments.

      Figure 11.  Illustration of DP, where stage Si is the initial stage, Sf is the final stage and j is the number of intermediate stages[96]

    • The “mixed integer linear programming (MILP)” has been used by Yilmaz et al.[97], for path planning of AUV. The path has been computed mathematically that maximizes the line integral of the uncertain field approximations along the course. The accuracy of these approximations can be improvised by sampling the computed path. It is flexible and can successfully handle constraints like inter-vehicle communication and synchronization, collision avoidance, etc. but suffers from an exponential increase in computational time in large solution space.

    • In ocean research, AUV is employed for relatively less expensive and long-range missions. Isern-González et al.[98] suggested a PP algorithm for AUVs based on “iterative optimization”. This methodology operated on varying current scenarios. There is no distinction between space and bearings variables and accurate modeling of the vehicle′s behavior is not needed. A sample utility computation-based structure has been presented in [99]. The utility is calculated as a function of preferences and constraints. This approach provides a balance between time and space parameters of marine sampling. It can be applied to any “sequential sampling” schemes with any degree of available feature information.

    • Cheng et al.[100] merged GA and DP to formulate a “hybrid genetic algorithm (HGA)”, that inherited the fastness of DP algorithms and the scalable nature of GA. It obtained a higher convergence rate and solutions with better fitness than conventional GA-based path planners.

      Zeng et al.[101] employed “annular space decomposition” strategy to represent the problem space. A hybrid PP algorithm comprising GA and “quantum-behaved PSO” has been developed. The proposed planner obtained an optimized trajectory with fast convergence speed and less computational cost, but in a restricted search space. A GA based efficient route planner has also been presented using “adaptive B-spline approximation” technique for AUVs employed in dynamic and unstable environments. Some intermediate “knots” are inserted as per requirement of each path until a smooth “B-Spline curve” satisfying accuracy condition has been estimated[102]. He also reviewed some of the important algorithms employed for PP of AUV and proposed an quantum behaved particle swarm optimization (QPSO) algorithm[103] for solving the optimal PP problem under the significant effects of oceanic currents (Fig. 12).

      Figure 12.  Flow chart of QPSO based path planner[103]

      An “interfered fluid dynamical system (IIFDS)” and “improved genetic algorithm (IGA)” has been proposed by Yao and Zhao[104]. This research uses “grey wolf optimization (GWO)” to improvise the mutation operator of GA and generates energy optimal paths in a 3-D environment with both static and dynamic obstacles. Li et al.[105] suggested a hybrid algorithm for PP of AUV for detecting and tracking both static and mobile targets in a turbulent underwater environment. It is an “intelligent cognitive architecture” where adaptive ACO and PSO algorithms are integrated to improvise basic fuzzy rules.

    • A prospective anytime algorithm called “anytime-RRT (ARRT)”[106,107] has been proposed by Ferguson et al. It is a sampling-based PP method. In this process, a chain of RRTs has been generated where each new RRT utilized the cost information from the previous, RRT to grow, resulting in an optimal trajectory.

      Algorithm 3. RRT pseudocode[49]

      Initialize RRT (M, T)

      T.add (mstart);

      Grow RRT (m, T)

        mnew=mstart;

        while (Distance (mnew, mgoal) > distance - threshold)

        mtarget =Choose Target O;

        mnearest =Nearest Neighbor (mtarget, T);

        mnew =Extend (mnearest, mtarget, T);

        if (mnewnull)

        T.add(mnew)

      Choose Target ()

        p = Random Real ([0.0,1.0]);

        if (p < goalsamplingprob)

        return mgoal;

        else

        return Random Configuration O;

      Main ()

        Initialize RRT (tree);

        Grow RRT (tree);

      Hernandez et al.[108] proposed a method using work-domain information to identify “homotopy classes”. These classes graphically describe the paths going through the obstacles in the 2D work-domain. These classes have been arranged as per the heuristic approximation of the class′s “lower bound”. Classes with smaller “lower bound” can only be allowed to guide an RRT path planner, called “homotopic RRT (HRRT)”. This method rapidly provided some good obstacle free paths and thus acts as an anytime algorithm.

      Ma et al.[109] proposed a dynamic “terrain-aided navigation (TAN)” approach for dynamic path planning based on change in topographical variations of seafloor with improved positional accuracy. This research employs the RRT* algorithm for path planning modules. In RRT*, the parent and child node have a minimum cost relationship rather than the minimum distance as in RRT. RRT* is also useful as an offline geometric path planner[110] for planning safety routes for AUV. But it is impractical to implement due to difficulties in reconnection with respect to AUV dynamics.

    • The planner proposed by Thompson et al.[111] used a “wavefront expansion” to calculate the travel time of AUV to reach any destination in a spatial-temporal 3D space (Fig. 13). It optimized a justified fastest “arrival criterion” to arrive at a predefined destination as fast as possible, assuming that the AUV can then sustain its position against sea currents until the required time is elapsed so as to recover from execution uncertainty errors. This method could detect dangerous destinations to be avoided. Soulignac[112] proposed the “sliding wave front expansion” scheme which optimizes a valid cost function. It guaranteed the availability of an arbitrary precise path in a 2D environment.

      Figure 13.  Dive profile for a simplified AUV motion[111]

    • A hierarchical 3D neural network (NN) framework inspired by biological neuro-dynamics is presented by Yan et al.[113] for the PP of an AUV. Each neuron in the NN characterizes a distinct subspace in the workspace. The mission to be accomplished acts as an “excitatory” input, whereas hindrances to achieve the goal are treated as inhibitory inputs to the NN. The excitatory input globally encourages an AUV to move through the NN to achieve its goal, whereas inhibitory inputs locally prevent the collisions. A “dynamic BINN” is recently proposed by Ni et al.[114] for PP of AUV in a dynamic and large 3D environment, that deals with complex repetitive route computing problem when the obstacle dimension exceeds the sensor detection range.

    • A “coverage path planning (CPP)” problem is aimed at full coverage of the entire uncertain environment with unknown obstacles. Longer paths to cover an area and turnings are avoided as they may increase time for completion and introduce navigational errors. Employing mobile AUVs for mine counter measures has been addressed as a CPP problem by Morin et al.[115] The seabed has been divided into a number of uniform square cells using cellular decomposition methods. An AUV equipped with sonar surveyed a fixed number of cells to locate mines. The chances of detection vary as a function of seafloor condition and distance. A path has been calculated offline employing DP and “traveling salesman problem” reduction. The resultant path guaranteed the optimum coverage in every cell by reducing the total distance covered and the total number of turns, but needed repeated visits to each cell. An algorithm that can provide a complete coverage path with low computational cost, has been developed by Bagnitckiiet al.[116] This algorithm can be applied for both offline PP and real time path correction, utilizing the knowledge of the water area bounds and the distance between tracks. Zhu et al.[117] proposed the “glasius bio-inspired neural network (GBNN)” algorithm to overcome drawbacks of BINN algorithms. The GBNN is intended to provide complete CPP for an AUV based on the previous position of the vehicle along with dynamic activities of neurons. It does not include a learning phase, thus there is less computationally complexity.

    • Designing a controller for tracking of an AUV along a required locus is difficult with poorly known and time-varying dynamic parameters. An adaptive control algorithm using 6 degree-of-freedom (DOF) is formulated for AUV by Antonelli et al.[118] This algorithm used quaternions to represent attitude errors and thus avoids singularities representation that occurs with “Euler angle” description of orientation. The results obtained are satisfactory within the constraints of the “sonar sensory system”. Li et al.[119] designed an adaptive robust controller for ROVs with velocity limitations. “Barrier Lyapunov function (BLF)” has been used in “Lyapunov synthesis”. It has been verified that the BLF is bounded and the velocity limitations are not violated. An adaptive controller has been developed by Sahoo and Subudhi[120] for AUV PP algorithm for planning a desired trajectory and to sustain parametric variations due to hydrodynamic effects.

    • The “shell space decomposition (SSD)” scheme has been proposed for AUVs dwelling in hostile and dynamic environmental conditions in [121]. The search space is decomposed into “shells”. Each of them has a “control point” within their boundaries. These shells spread from initial to end positions. The path is provided by the control points using “Splines”. The SSD scheme is combined with a “quantum-behaved particle swarm optimization (QPSO)” based path follower to generate an optimal path in a dynamic obstacle rich underwater environment. Mission planning and path planning support long range operations of AUVs which results in improved levels of autonomy[122].

      Algorithm 4. SSD pseudocode[49]

      Initialize: Map, M

      Ensure shell decomposition

      for left-most point to right-most point define vertical slice s do

      if s is tangential to an obstacle then

      add s to set of critical slices

      end if

      add all shells to graph as nodes

      for all critical slices do

      add edges in the graph connecting bordering shells

      end for

      end for

    • An “imperialist competitive algorithm (ICA)” has been introduced by Zeng et al.[123] for solving the optimal PP problem for AUVs. ICA is a socio-politically inspired global search algorithm, which represents the competition between “imperialist forces” and “opposing colonies”. It can be employed as a control point coordinate optimization algorithm for generating a “spline path”.

    • Yu et al.[124] proposed a “reinforcement learning” model to address PP of AUV to cope with the effect of the dynamic environment and actuator failure. The research done by Sun et al.[125] addresses “motion planning problem (MPP)” in a map-less underwater environment for an underactuated AUV. The MPP is an “end-to-end” planning method and realized by taking inputs from sensors to control “surge force and yaw moment” of the AUV. This research work is based on “deep reinforcement learning (DRL)” that incorporate the “proximal policy optimization (PPO)” for finding optimal paths. A “reward curriculum learning” is employed for training that resolves sparse reward problems and circumvents the effect of obstructing intermediate rewards during training.

    • Path planning for multiple AUVs is commonly known as cooperative path planning. Underwater cooperative path planning is a challenging problem as the GPS signals are not available. With the development of advanced communication technology[126, 127], this area of research has received remarkable attention in recent times. Cooperative path planning control can be categorized as “formation” and “flocking”[25]. In the formation control, the AUVs are moving in a team with fixed distances and avoid collisions among themselves, while maintaining a common average heading angle (Fig. 14). Flocking control is said to be attained when a set of multiple AUVs are directed to achieve a target (Fig. 15). It can be defined as formation control without distance restrictions among AUVs. Different path planning methods used for multiple AUVs are summarized in Fig. 16 in the light of predictable and unpredictable underwater environments. The path planning algorithms for multiple AUVs are summarized in Table 2.

      Type of environmentMethods & algorithm Type of path generatedCollision/Obstacle avoidancePath costMerits & demerits analysis
      PredictableAbstract plan[129]Time optimalPoorLow●Planning can be adjusted according to the dynamics of the environment.
      ●Low computation cost
      ●Only simulation results are obtained
      PredictableFuzzy logic[130, 131]Time optimalAchievedHigh●Generates safe and optimized path to the target through the obstacle
      ●Search depends on the fuzzy relation between the sections of sonar and the actual environment
      PredictableTC-PF[132-134]Time optimalPoorLow●Enables cooperatively path planning subjected to space, time, and energy restrictions
      ●Constrained by the layout of communications network among AUVs and AUV dynamics
      ●High computation cost involved
      PredictablePassivity approach[135]Time optimalPoorLow●Improves stability, robustness and performance of the system
      ●Low computation cost
      ●Each block is designed to be passive
      PredictableEvolutionary algorithms[136-138]Time optimalAchievedLow●Generates cost effective, safe paths for a team of AUVs relying on the knowledge of the waypoints and obstacles
      ●Processing time is more
      PredictableLOS Guidance law[139, 156]Time optimalPoorHigh●Address the dynamics of shallow water effectively without missing targets while maintaining inter vehicular formation
      ●Only simulation results are obtained
      PredictableSynchronized path planning control[141-143]Time optimalPoorModerate●The required communication variables are minimized and the knowledge of network layout is not necessary to be known by everyone
      ●Computational complexity is high
      PredictableLagrangian multipliers[144]Time optimalPoorLow●Simple and physical interpretable methodology for motion control
      ●Low computation cost
      ●Lagrange multipliers are subjected to complimentary constraint problems
      PredictableDR & LBL[145-149]Time optimalLimitedHigh●Provides superior navigation precision and update rates
      ●Computationally efficient
      ●Efficiency depends on the accuracy of sensor data
      PredictableGIB system[150, 151]Time optimalPoorHigh●Effective real time submerged target positioning system
      ●It is difficult to deploy and retrieve buoy, costly and inflexible method
      ●Unsuitable for longer range missions
      PredictableCL[152, 153]Time optimalLimitedModerate●AUVs waste less time in surfacing for GPS fixation. And uncertainty is reduced over the entire AUV trajectory
      ●Simultaneous localization and mapping are not possible
      ●High computation cost
      UnpredictableVBAP[154,155]Time optimalPoorModerate●Effective for gradient climbing and feature tracking in a dynamic environment
      ●Unbounded error growth makes it less efficient with high computational cost
      UnpredictableKalman filtering[156-161]Time optimalPoorLow●Cost-effective method for cooperative path planning
      ●Less robust to system failure
      ●Depends on on-board sensor data
      UnpredictableK-means method[162-164]Time optimalPoorHigh●Addresses task allocation problem of multiple AUVs in the existence of a constant ocean current
      ●Computationally efficient, scalable and satisfies the bandwidth requirement of available modem
      ●Supports long range missions
      ●Communication expanses are high
      UnpredictableCooperative localization[165, 166]SuboptimalPoorHigh●Provides near optimal paths while avoiding heavy traffics during pre-assigned time intervals
      ●Requires expensive navigation sensors
      UnpredictableLeader follower structure[167-170]Time optimalPoorModerate●High precision navigation methods
      ●Complexity increased as a double acoustic measurement method
      UnpredictableBeacon vehicle range only localization[171-175]SuboptimalPoorModerate●Optimal, consistent and computationally efficient
      ●Performance degraded due to inefficient ranging techniques and infrequent monitoring of sonar targets
      UnpredictableBeacon AUV with MDP[176-178]Time optimalPoorModerate●Beacon AUV has to be positioned at the critical positions when the acoustic signal transmitted
      ●Avoids the use of LBL acoustic positioning systems
      UnpredictableGreedy approach[179, 180]Time optimalPoorModerate●The survey vehicles′ trajectory information is not needed a priori
      ●Independent of the group size of the participating vehicle
      UnpredictableLandmark AUV[181, 182]Time optimalPoorHigh●A larger space can be explored
      ●Subjected to the effect of sensor noise in the state estimation and Doppler drift
      UnpredictableServer-client CL[183]Time optimalPoorHigh●Plan a feasible path for a surface vessel that supplies span measurements
      ●Requires the knowledge of the formal client mission plan and potential server trajectory
      UnpredictableNN[184-186]SuboptimalAchievedHigh●Able to cope with the actuator saturation and model uncertainties
      ●High computational complexity
      UnpredictableFuzzy logic[187, 188]OptimalPoorModerate●Enabled examination of a wide unknown region with real-time obstacle avoidance
      ●Deals with inaccuracy and uncertainty
      ●Somehow depends on type of AUVs involved
      UnpredictableACO[189]OptimalPoorLow cost●Solves multiple AUVs coordination problem for collaborative task allocation
      ●Computational cost increases with the increase in problem scale
      UnpredictableQPSO[190, 191]Time optimalAchievedModerate●Optimize the overall traveling time considering the chronospatial current effects along with nonsymmetrical terrains and dynamic obstacles
      ●High computational cost
      UnpredictableIntegrated VS[192-195]OptimalPoorModerate●Successfully achieved workload balance and energy efficiency
      ●High computational complexities
      UnpredictableDynamic programming[196]Time optimalAchievedHigh●Avoids obstacles and enable the team of AUV to achieve the target with a minimum time difference
      ●Requires effective memory management
      ●High computation cost involves
      UnpredictableLAAF and GMOOP[197]Time optimalPoorHigh●Can solve task allocation problem of multiple AUVs avail with minimal acoustic communications
      ●Deterministic in nature
      ●Requires more computation time and cost
      UnpredictableRRT[198, 199]Time optimalAchievedHigh●Generates better quality samples
      ●High computational cost

      Table 2.  Comparison of path planning algorithms for multiple AUV

      Figure 14.  Formation control of AUVs[25]

      Figure 15.  Flocking control of AUVs[25]

      Figure 16.  Path planning for multiple AUVs

    • Initial researches in cooperative path planning are concerned with avoidance of collisions with obstacles and other AUVs while moving in a predictable environment. A decentralized control design for regulating global functions of cooperating AUVs[128] have been presented by Stilwell and Bishop. It determined the communication strategies that are required to obtain a stable decentralized control. Theoretically, it is verified that the departure of the actual formation of AUVs from the required formation can be calculated by using a coordination system based on differential geometry[129] to compute the desirable motion of each AUV that leads to no deformation.

    • Turner and Briggs[130] presented an approach for PP, that relies upon estimations made by an “agent”. An abstract plan has been prepared by the agent instantly, based on the known achievable goals and natural boundaries. The agent can exploit the well-organized abstract plan to incorporate a new goal into suitable steps. It saves the expense of planning actions as planning can be adjusted according to the dynamics of the environment.

    • A heuristic search technique for AUVs has been described by Lee et al.[131] to escape the collision. It employs “fuzzy relation products” to conduct PP of “intelligent navigation system”. The “evaluation function (EVF)” comprises of “local cost function (LCF)”, “avoidance distance cost function (ADCF)” and “remainder distance cost function (RDCF)” (Fig. 17). A higher priority is assigned to the aspirant “successor node” having lower “EVF return”, as EVF transforms the safety and optimization cost of successor nodes into energy consumption.

      Figure 17.  Framework of EVF[131]

      A modified heuristic search method for PP of AUV to avoid obstacles employing the “Bandler and Kohoutt′s product (BKP)” of fuzzy logic with a seven sectioned sonar has been proposed by Bui and Kim[132]. This search depends on the fuzzy relation between the sections of sonar and the actual environment (Fig. 18). Safe and optimized paths to the target through the obstacle have been generated by this approach.

      Figure 18.  Fuzzy logic controller using BKP-triangle sub-products[132]

    • A coordinated path-planning problem for a common group of under-actuated AUVs[133] has been solved using “Lyapunov theory”. The proposed system is stable and is able to deal with the problem of temporary communication failures. The “time-coordinated path following (TC-PF)” is a structure suggested to investigate the problem in controlling multiple AUVs[134,135]. It enables cooperative path planning subjected to space, time, and energy restrictions. Parallel formation designing and synchronization are constrained by two factors. The first factor is layout of communication network and the second factor is AUV dynamics.

    • A framework, that represented a closed-loop system comprising of an AUV dynamic block and a path planning system based on “passivity approach” as a feedback element[136] has been proposed by Ihle et.al. Here each block is designed to be passive (Fig. 19). The dynamics block deals with path variable synchronization. The proposed framework achieved improved stability, robustness and performance of the system.

      Figure 19.  Passivity controller for formation[136]

    • Evolutionary algorithms can be described as “inductive reasoning” procedures. In the EA, there is the selective introduction of uncertainties at required steps to develop a logic that copes with adversities of the environment. Fogel et al.[137] proposed an evolutionary optimization algorithm that avoids use of a complex genetic operator. This method has been applied to the operations where multiple AUVs are employed to visit scattered locations in a predefined time. The AUV behavior has been computed offline and described as a sequence of changes in their paths of travel and velocities in a 2D environment.

      Wu et al.[138] applied the GA subjected to non-linear constraints to generate cost effective, safe paths for a team of AUVs relying on the knowledge of the waypoints and obstacles. The algorithm is segregated in three modules. The first module deals with allocating “waypoints” to AUVs. The second module optimizes the path, thus reducing the overall travel of the AUV. The chances of the existence of stationary and/or moving collisions are checked in the final route validation module. The application of GA to the PP problem is shown in Fig. 20.

      Figure 20.  Genetic algorithm applied to the PP problem

      A hybrid three-layer module implemented through a “global route planner (GRP)” using GA, a “local path planner” using PSO and re-planner module has been proposed by Mahmoud Zadeh et al.[139] This is a robust and flexible method for assigning tasks, PP and avoiding collision among AUVs which are employed in long range missions.

    • Jung et al.[140] used “line of sight (LOS)” navigation and proposed a methodology for PP of AUVs (Fig. 21). It assumed that AUVs track a LOS path as per required formation motion. It was intended to address the dynamics of shallow water effectively without missing targets. The problem of cooperative path-planning (CPP) with discrete communications has been addressed in [141], where a group of surface vessels tracks a set of default trajectories in space while maintaining inter-vehicle formation in the time domain.

      Figure 21.  AUV controller using LOS algorithm[140]

    • Xiang et al.[142] modeled a bi-layer synchronized path planning controller for multiple AUVs. The individual path planning controller forms the first layer and drives the AUV converging to the paths, with a “helmsman-like behavior” incorporated in heading reference design. The second layer comprises a global controller for synchronization through distributed speed adjustment. In this method, the required communication variables are minimized and the knowledge of network layout is not required to be known by everyone. A mathematical framework to reduce time heading control for AUVs moving with constant speed has been proposed in [143]. A front tracking method has been discussed by Das et al.[144] for synchronized motion of a set of AUVs along a required trajectory in availing full communications (Fig. 22). The global optima have been identified in a dynamic ocean flow field by the above-mentioned methods.

      Figure 22.  Formation control using SMC controller[144]

    • A simple and physical interpretable methodology for motion control of AUVs has been simulated as a constrained multi-AUV system in [145]. Then, “Lagrangian mechanics” has been utilized to obtain the equation of motion. To illustrate the approach, a path maneuvering controller defined as a “virtually constrained motion” controller has been modelled in order to drive the AUV to converge to and follow a predetermined parameterized locus (Fig. 23).

      Figure 23.  Path planning controller virtually constrained system[145]

    • The most common and established method for AUV navigation is the dead reckoning. The mostly used sensors in the DR are the interoceptive sensors like compass, “doppler velocity log (DVL)”, and “inertial navigation system (INS)” to predict the positions of AUV due to unavailability of the GPS signals as radio waves cannot penetrate very far in the sea.

      A sub-water “long-baseline (LBL)” acoustic positioning system can be considered as an alternative that operated by deploying baseline transponders such as beacons within a framework of the seabed. These beacons positioned to surround the AUV′s operational region and are retrieved after accomplishment of the goal. If a surface ship is available as a reference position, then “ultra-short baseline (USBL)” or “short-baseline (SBL)” localization can be employed to know the relative position of an AUV with respect to the reference GPS location of the surface ship. USBL has been designed by Matos et al.[146] comprises a “search-classify-map (SCM) vehicles” and a “communication-navigation-aid (CNA) vehicles”. SCM is used for oceanographic mapping with the help of low-cost interoceptive sensors.

      CNA employed DVL and INS to help in SCM′s path planning. The CNA has to surface frequently for GPS fixation. The GPS location estimate of the surface ship has been transmitted by it using an acoustic modem for every communication. The receiver AUV uses this information along with its own DR data to predict its location. It has been verified experimentally that a system combining LBL acoustic navigation data with Doppler navigation data[147] provides superior navigation precision and update rates in comparison to individual LBL or Doppler navigation alone (Fig. 24). Stack et al.[148] proposed a PP algorithm to revisit an already surveyed surface area using a three-phase planning algorithm. This algorithm is computationally efficient and is helpful in removing false alarms in mine countermeasures. Rigby et al.[149] improvised the 3D location estimates for the AUV combining information both from a DVL and an USBL system. Performance of DR can be improved by using Doppler sensors that sense the difference between the transmitted and received signals to approximate the AUV′s speed[150] based on the Doppler Effect. These sensors again suffer from two measure limitations. In the first case, it is unable to calculate the velocity components due to the oceanic currents leading to error in position estimation of AUVs. Secondly a number of transducers directed at diversified angles are used that continuously transmit an acoustic signal of a certain frequency towards the bottom of the sea.

      Figure 24.  LBL/ Doppler complementary filter navigation system[147]

    • A “GPS intelligent buoy (GIB)” may be classified as an inverted LBL oceanic positioning devices, where the transducers are installed on GPS-equipped son buoys[151] (Fig. 25). An alternative system consisting of four surface buoys loaded with “differential GPS (DGPS)” receivers and immersed hydrophones for calculating the location of the immersed AUV has been discussed in [152]. The demerits of using GIBs lie in the difficulties in deploying and retrieving, high cost, and inflexibility. It is also unsuitable for longer range missions.

      Figure 25.  Illustration of GIB system[151]

    • Paull et al.[153] presented a cooperative path prediction technique for a team of AUVs using cooperative localization (CL) algorithm, capable to favorably exploit the underwater acoustic communication channels (Fig. 26). This is an efficient method as AUVs waste less time in surfacing for GPS fixation and uncertainty is reduced over the entire AUV trajectory. Simultaneous localization and mapping are not possible with this method.

      Figure 26.  Acoustic communication of AUVs using TDM[153]

      In this case, payload data are more accurate and localized through the smoothing approach. LBL can also provide path planning during descent but desired time-consuming positioning of transponders. Due to the unavailability of both GPS and DVL positioning in the mid-water, column communication between the surface and the seabed AUVs is very difficult. To avoid these problems, Medagoda et al.[154] proposed a positioning solution in the mid-water column that takes advantage of the nearly constant current profile layer velocities over short time intervals.

    • It has been proved by a number of researchers that the major issues of the cooperative path planning for multiple AUVs in the unpredictable underwater environment can be decomposed in three phases. In the first phase, it has been considered that the cooperative path planning algorithm for multiple-AUVs are very hard to design using the existing methods due to the exponential increase in computation time with increase in the number of AUVs. Thus, new algorithms have to be designed to reduce computational complexity. Secondly, the calculation of cost in terms of time between two positions is quite troublesome as the ocean flows are typically continuous and time-varying vector fields. Finally, an evaluation function is required to approximate overall performance. Consequently, various methods and algorithms have been developed by researchers for solving the above-mentioned problems. Here an attempt is made to review the available literature in this field to the best of our knowledge.

    • Fiorelli et al.[155] proposed a method for cooperative path planning control of collective AUVs based on “virtual bodies and artificial potentials (VBAP)” (Fig. 27). This is an adaptable formation control used for applications like gradient climbing and feature tracking in a dynamic environment. But unbounded error growth made this method less efficient. A study of different applications, capabilities, merits and demerits of using VBAP with cross-layer design features to autonomously planning trajectories in non-communicating AUVs has been presented by Barisic et al.[156]

      Figure 27.  Operational configuration & data flow diagram of AOSN-II VBAP glider AUV[155]

    • Research on cooperative navigation of “group unmanned underwater vehicle (GUUV)” has been proved effective to resolve the path planning problem in long range and deep-ocean. Zhang et al.[157] presented EKF as a cost-effective method for cooperative path planning. It can be described in two forms that are parallel form & leader-follower form. In the first form, all of the UUVs are equipped with the same sensors and played the same role. They have been considered equal and able to get the information of any other UUV. In the second form, few leader UUVs known as “master” equipped with high level sensors and many fellow UUVs equipped with low-cost sensors has been used. Fellow UUVs known as “slave” update their positions based on the information from the leader as shown in Fig. 28. Lack of robustness of system failures resulted in less efficiency for this proposed method. An optimal path planning strategy for the AUV to eliminate sound velocity profile prediction uncertainty in the water has been discussed by Sun et al.[158] The proposed methodology is based on the MAP estimation framework and one step Kalman filters. Allotta et al.[159] compared underwater path planning systems relying on EKF and on “unscented Kalman filter (UKF)” for estimating the AUV position. This method required on board sensors, such as inertial, linear velocity, acoustic and depth sensors. It offered a compromise between performance and computational complexity. A motion estimation algorithm has also been proposed by the authors based on the UKF[160, 161]. The proposed filtering algorithm is executed offline on the data acquired by the two “typhoon AUVs”. A formation control algorithm that mitigate larger initial estimation has been proposed by Das et al.[162] It involved a nonlinear observer for compensating the delay in the sensor signal transmission to the controller because of packet dropout in an acoustic medium without using “Jacobian matrices”.

      Figure 28.  Moving LBL scheme[157]

    • The general issue of cooperative path planning with the help of an explanatory mission scenario developed jointly by the GREX partners[163] has been introduced by Aguiar et al. The proposed method is computationally efficient, scalable and the bandwidth requirements of available AUV modems are satisfied. A k-means method has been developed by Chow[164] to address the task allocation problem of multiple AUVs in the existence of a constant oceanic current. The framework is a combination of a “Dubin′s model”, an AUV dynamic model and a dynamic ocean current model. Bahr et al.[165] used the same model for a fully mobile network of AUVs (Fig. 29). These AUVs execute acoustic ranging and share information among them to achieve cooperative localization for long duration operations over wide areas. The trajectory selection is done by minimizing a cost function subjected to constraints.

      Figure 29.  Beacon-based underwater localization techniques[165]

    • Papadopoulos et al.[166] suggested a real time algorithm for cooperative positioning of immersed AUVs reinforced by an autonomous surface ship. Navigation has been done by sharing location information and acoustic range measurements. The unavailability of GPS signals is compensated by using expensive navigation sensors to reduce the speed of dead-reckoning divergence. Binney et al.[167] presented a path planning control for AUVs in order to maximize the mutual information employing acoustic ranging and “side-scan sonar”. Near-optimal paths have been generated while avoiding heavy traffics during pre-assigned time intervals. Some temporal resolution has been the tradeoff for achieving higher spatial resolution.

      A “multiple Lyapunov function (MLF)” method has been proposed in [168], to address the “cooperative output regulation problem” for a group of “multi-agent systems (MASs)”.

    • Zhang et al.[169] proposed a high precision navigation method using “leader-follower” frameworks in 2011. Each AUV has been provided with navigation systems along with acoustic devices to measure relative positions. The navigation system of the leader is highly accurate in comparison to the follower navigation system. The position of the follower is calculated using triangulation geometry. The complexity increased as a double acoustic measurement method is used with “proprioceptive” and “exteroceptive” sensors to avoid fault error solution. Sahu et al.[170] developed an algorithm for multiple AUVs′ navigation based on flocking control using leader-follower structure. The leader AUV supplied with the prior knowledge of the intended path, but the follower AUVs don′t have this information. The flocking center has been calculated using the consensus algorithm and known to all AUVs. Bounded APFs have been used for development of the controller. The leader-follower formation control of multiple “nonholonomic AUVs” has been described by Das et al.[171] Here, one of the AUVs is “leader” and the rest of the AUVs are called the “followers”. The path planning control strategies to attain the goal of AUVs are categorized as “trajectory tracking”, “path planning” and “waypoint tracking”[172] (Fig. 30).

      Figure 30.  Leader- follower structure of AUVs[172]

    • Several researchers acknowledged the use of a single-beacon AUV loaded with highly accurate sensors for navigation to send location information at crucial positions to other AUVs in an unpredictable ocean environment. The received information along with the range measurement data leads to better position estimation[173] with less error by the AUVs. An EKF has been implemented by Rui and Chitre[174], to fuse the range information updates obtained from beacon AUV with the navigational sensor data on the survey AUV. Chitre[175] developed a path planning algorithm for beacon AUV′s operation that reduces the location estimation errors being collected by other AUVs (Fig. 31). In the stated method, optimal maneuver determination for the beacon AUV received little attention.

      Figure 31.  Error estimation using range measurements[175]

      Fallon et al.[176, 177] proposed that a beacon AUV could play the role of CNA to move in zigzag path or circumscribe the AUV, resulting in a completely visible path in 2010. The proposed method is optimal, consistent and computationally efficient, but the performance degraded due to inefficient ranging techniques and infrequent monitoring of sonar targets.

    • The beacon AUV′s PP problem within the structure of “markov decision process (MDP)” has been presented by Tan et al. using the cross-entropy method[178] and DP method[179]. In this method, the beacon AUV has to be positioned at the critical positions when the acoustic signal is transmitted. It avoids the use of LBL acoustic positioning systems. The supported AUV is allowed to stay immersed for a longer duration with minor positional error. The adaptive path planning problem is implemented as MDP and an online method based on “reinforcement learning” is used to plan optimal paths for AUVs with space restriction[180]. The “simultaneous localization and mapping (SLAM)” problem has been modelled as a flexible MDP in [181]. It can be employed for SLAM with dynamic environment.

    • Bahr et al.[182] used the greedy approach to compute optimal paths assuming that the client paths are unknown and their positions have been estimated from announced oceanic broadcasts. The proposed approach located a set of AUV clients, optimizing a single trace-based target function. Greedy methods are fast in obtaining a global optimum solution through a series of intermediate local optimum solutions. But, sometimes global optimum solution cannot be obtained due to inexhaustive data operation[183].

    • Vehicles often misled by factors such as underwater currents, positioning errors, etc. are unable to reach even precisely located destinations. To overcome these problems, Matsuda et al.[184, 185] proposed a positioning method for travelling AUVs that estimates their location based on a stationary “landmark AUV” on the seabed by conducting the sea experiments using two AUVs (Fig. 32). The landmark role has been exchanged among AUVs so that a larger space can be explored by them. AUVs exchange the position estimations by the moving AUV, using the data compression method. The stated strategy is subjected to the effect of sensor noise in the state estimation and Doppler drift.

      Figure 32.  The relative positioning principle. M and L stand for “moving” and “landmark” respectively[185].

    • A server-client cooperative localization method has been proposed where the information about the respective span of the mission is supplied by the “server AUV” to reduce the uncertainty of a “client AUV”. The proposed algorithm is intended to plan a feasible path for a surface vessel that supplies span measurements[186] to an AUV. This approach assumes that the formal client mission plan is available. A potential server trajectory has been drawn from a set of specified path classes.

      Algorithm 5. Server-client cooperative localization pseudocode[186]

      Require: Ac, ηc /*Intial client distribution*/

      Decide Mbest, θbest /*Optimal trajectory class and parameters*/

      Ibest = 0, Mbest = ϕ, θbest = ϕ

      for Mi $\in ${M0,···,Mm}

      for θ $\in $ dom Mi do

      $ {\theta ^*} = {\rm{argma}}{x_\theta }I\left( {P\left( {{M_i},\theta } \right)} \right)$

      If I (P(Mi, θ*)) > Ibest then

      Ibest = I(P(Mi, θ*))

      Mbest =Mi

      θbest=θ*

      end if

      end for

      end for

      return Mbest, θbest

    • A neural network (NN) based approach has been proposed by Zhu and Yang[187] for a “multi robot system”. It is applied for dynamic task assignment along with route planning and synchronization of “multi-agent systems (MASs)” with moving obstacles[188]. A NN based path planning control of under-actuated AUVs with restricted torque input subjected to the noisy 3D environment has been addressed by Shojaei[189]. Multilayer NNs in association with a self-adaptive robust control method is used. The stated method is able to cope with the actuator saturation and model uncertainties (Fig. 33), such as unknown AUV dynamics, approximation errors, and noise induced by waves and sea currents.

      Figure 33.  AUV model with actuator saturation[189]

    • A fuzzy path planner-based navigation method for multiple AUVs (Fig. 34) subjected to varying oceanic current has been introduced in [190]. The given method enabled examination of a wide unknown region with real-time obstacle avoidance. This approach allowed a multi AUV system to maintain a spatial formation[191].

      Figure 34.  Architecture for the swarm AUV[190]

    • A meta-heuristic “ant colony optimization” algorithm has been implemented to solve the multiple AUVs coordination problem by Li et al.[192] An optimum solution has been obtained to the collaborative task allocation problem.

    • Zeng et al.[193] proposed a strategy that integrates an optimized mass-center assembling point selection method with an evolutionary route planner to generate paths for a group of AUVs. The proposed path focused on minimum time expenditure over all candidate AUVs and the simultaneous arrival of the AUVs at their selected assembling point. Another path planner has been designed by the same author that employed QPSO algorithm with a cost function to optimize the overall traveling time considering the chronospatial current effects along with nonsymmetrical terrains and dynamic obstacles[194] (Fig. 35).

      Figure 35.  Multiple AUVs guidance system[194]

    • An integrated algorithm of dynamic task assignment and path planning control in a 3D oceanic environment for multiple AUVs is formulated by Zhu et al.[195] It integrates the modified “self-organizing map (SOM)”, NN and a VS approach to guide a group of AUVs to cover all selected destinations only once. The proposed method successfully achieved workload balance and energy efficiency with minimal total and individual consumption in the face of the varying oceanic current. The structure of SOM network is shown in Fig. 36.

      Figure 36.  Structure of the SOM network[195]

      A similar integrated algorithm has been proposed by Huang et al.[196], where each destination has to be visited through the shortest route by a single AUV only assuming varying current and destinations. An integrated cooperative search algorithm in an unpredictable oceanic environment subjected to varying currents has been proposed by Cao et al.[197] The “biological inspired neurodynamic model (BINM)” and VS methodology are integrated to achieve the target. A similar algorithm by integrating “potential field-based particle swarm optimization (PPSO)” and VS algorithms (Fig. 37)[198] has also been suggested by the same authors. The proposed algorithm is able to guide a set of AUVs to search a target in 2D environment while monitoring every AUV′s movement that can offset the impact of oceanic currents.

      Figure 37.  Block diagram of multi-AUV target searching[198]

    • Recently, a collaborative path planning method has been presented by Liu et al.[199] for multiple-AUV in the face of dynamic oceanic currents based on the DP. In the proposed methodology, each AUV coordinated with the AUV with the longest estimated time of travel. The time consumed during the travel from one node to another has been considered as the weight “w”. The objective function of the algorithm is defined as follows:

      $ f\left( {{t_{i,j}}} \right) = \mathop {\min }\limits_{k\epsilon n} \left\{ {f\left( {{t_{i - 1,k}}} \right) + w\left( {{t_{i - 1,k}},{t_{i,j}}} \right)} \right\} $

      (1)

      where $ f\left( {{t_{i,j}}} \right)$ represents the minimum time of travel from starting point to ti,j node. The proposed method avoids obstacles and enables the team of AUV to achieve the target with a minimum time difference.

      Algorithm 6. DE pseudocode[199]

      for each i do

      for each j do

      for each k do

        if $ f\left( {{t_{i,j}}} \right) > f\left( {{t_{i - 1,k}}} \right) + w\left( {{t_{i - 1,k}},{t_{i,j}}} \right)$

      then

        $ f\left( {{t_{i,j}}} \right) = f\left( {{t_{i - 1,k}}} \right) + w\left( {{t_{i - 1,k}},{t_{i,j}}} \right)$

      end if

      end for

      end for

      end for

    • The application of deterministic algorithms over a stochastic algorithm for the PP and task assignment for a multiple AUV system has been advocated in the literature due to its algorithmic completeness and predictability. The algorithm outputs will remain similar, if the traffic scenario is evaluated on a different AUV, as the overall traffic configuration remains unchanged. Deng et al.[200] solved the task assignment and PP problem for multiple AUV system with minimal acoustic communications. A “location-aided task allocation framework (LAAF)” algorithm for multi-target task allocation and a “grid-based multi objective optimal programming (GMOOP)” model has been developed for achieving an optimum AUV command decision with state targets and limitations (Fig. 38).

      Figure 38.  Architecture of GMOOP[200]

    • Hernández et al.[201] presented an online methodology for planning collision-free paths for multiple AUVs. This approach is composed of a leading AUV equipped with “multibeam sonar” and highspeed processor and a camera vehicle (CV). Paths have been planned using a modified RRT known as “transition-based RRT (T-RRT)” algorithm. The cost function depended on “AUV′s configuration space”, or “cost map”. Cost map is a function of seafloor distance and the path distance. An adaptive path planning algorithm based on the “multidimensional multi-input RRT star (MDMI-RRT star)” algorithm[202] has been proposed by Cui et al. It generates better quality future samples by maximizing the mutual information between the scalar field model and observations but involved communication costs.

      Algorithm 7. T-RRT pseudocode[201]

      Input: States qinit and qgoal, cost function, $ c\left( q \right) = Cost\left( {d\left( q \right)} \right)$

      Output: tree (T), contains the collision-free path.

      begin

        $ T \leftarrow InitTree\left( {{q_{init}}} \right)$

        while not $ StopCondition\left( {T,goal} \right)$ do

        $ {q_{rand}} \leftarrow SampleConf\left( {C - space} \right)$

        $ {q_{near}} \leftarrow NearestNeighbour\left( {{q_{rand}},T} \right)$

        $ {q_{new}} \leftarrow Extend\left( {T,{q_{rand,}},{q_{near}}} \right)$

        $ f{q_{new}} \ne $ NULL and $ TransitionTest\left(c\left( {{q_{near}}} \right)\right.,$$\left.c\left( {{q_{new}}} \right),d{_{nnear - new}} \right)$ and $MinExpandControl (T,{q_{rand,}},$ qnear) then

          AddNewNode$ \left( {T,{q_{new,}}} \right)$

          AddNewEdge$ \left( {T,{q_{new,}},{q_{near}}} \right)$

      end

    • This survey presents a qualitative analysis of the impact of the marine environment on the path planning of AUVs. The underwater environment is characterized as predictable and unpredictable depending on path planning approximations. This paper summarizes the available path planning algorithms employed for single and multiple AUVs with reference to predictable and unpredictable behavioral models of the environment. The issues involved in path planning of AUVs are discussed briefly. The algorithms are compared considering the type of the environment, type of the path generated, path cost and collision avoidance features. Merits and demerits of every method have been discussed briefly. Type of path generated by the methods are classified as time optimal (time minimal solution), energy optimal (energy minimal solution), sub-optimal (near optimal solution) and optimal (best possible solution). Path costs are compared as low, moderate and high. Collision and obstacle avoidance are discussed as achieved, limited and poor based on whether the algorithm focused on these issues or not. Based on this study, we can conclude that the issues of unreliability have not been addressed much in the studied literature. Many assumptions are taken for AUV dynamics and operating environment, which are required to be critically analyzed for stability in real world scenarios. Thus, there is a need for formulating optimized algorithms in the future that is computationally efficient and rugged for real time applications of AUVs.

    • This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Reference (202)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return