Abstract
This paper describes path re-planning techniques and underwater obstacle avoidance for unmanned surface vehicle (USV) based on multi-beam forward looking sonar (FLS). Near-optimal paths in static and dynamic environments with underwater obstacles are computed using a numerical solution procedure based on an A* algorithm. The USV is modeled with a circular shape in 2 degrees of freedom (surge and yaw). In this paper, two-dimensional (2-D) underwater obstacle avoidance and the robust real-time path re-planning technique for actual USV using multi-beam FLS are developed. Our real-time path re-planning algorithm has been tested to regenerate the optimal path for several updated frames in the field of view of the sonar with a proper update frequency of the FLS. The performance of the proposed method was verified through simulations, and sea experiments. For simulations, the USV model can avoid both a single stationary obstacle, multiple stationary obstacles and moving obstacles with the near-optimal trajectory that are performed both in the vehicle and the world reference frame. For sea experiments, the proposed method for an underwater obstacle avoidance system is implemented with a USV test platform. The actual USV is automatically controlled and succeeded in its real-time avoidance against the stationary undersea obstacle in the field of view of the FLS together with the Global Positioning System (GPS) of the USV.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Campbell S, Naeem W, Irwin GW (2012). A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance maneuvers. Annual Reviews in Control, 36, 267–283.
Dechter R and Pearl J (1985). Generalized best-first search strategies and the optimality of A*. Journal of ACM, 32, 505–536.
Ebken J (2005). Applying unmanned ground vehicle technologies to unmanned surface vehicles. Technical Report, DTIC Document.
Gao J, Xu D, Zhao N, Yan W (2008). A potential field method for bottom navigation of autonomous underwater vehicles. Intelligent Control and Automation, Chongqing, 7466–7470.
Imagenex Technology Corp. (2011). DeltaT multi-beam sonar system model 837/A/B. Port Coquitlam, British Columbia, Canada.
Jan GE, Chang KY, Gao S, Parberry I (2005). A 4-geometry maze router and its application on multi-terminal nets. ACM Trans. on Design Automation of Electronic Systems, 10, 116–135.
Kim K, Ura T (2009). Optimal guidance for autonomous underwater vehicle navigation within undersea areas of current disturbances. Advanced Robotics, 23, 601–628.
Kondo H, Ura T (2004). Navigation of an AUV for investigation of underwater structures. Control Engineering Practice, 12, 1551–1559.
Larson J, Bruch M, Halterman R, Rogers J, Webster R (2007). Advances in autonomous obstacle avoidance for unmanned surface vehicles. AUVSI Unmanned Systems North America 2007, Washington DC.
Larson J, Ebken J, Bruch MH (2006). Autonomous navigation and obstacle avoidance for unmanned surface vehicles. SPIE Proc. 6230: Unmanned Systems Technology VIII, Defense Security Symposium, Orlando, 17–20.
Lester P (2005). A* Path finding for Beginners. http://www.policyalmanac.org/games/AStarTutorial.htm.
Maki T, Mizushima H, Kondo H, Ura T, Sakamaki T, Yanagisawa M (2007). Real time path planning of an AUV based on characteristics of passive acoustic landmarks for visual mapping of shallow vent fields. Proceedings of MTS/IEEE OCEANS2007, Aberdeen, 1–8.
McLain TW, Beard RW (1998). Successive Galerkin approximations to the nonlinear optimal control of an underwater robotic vehicle. Proceedings of the 1998 IEEE International Conference on Robotics & Automation, 762–767.
Petillot Y, Ruiz IT, Lane DM (2001). Underwater vehicle obstacle avoidance and path planning using a multi-beam forward looking sonar. IEEE Journal of Oceanic Engineering, 26(2), 240–251.
Rhoads B, Mezic I, Poje A (2010). Minimum time feedback control of autonomous underwater vehicles. Decision and Control, Georgia, 5828–5834.
Spangelo I, Egeland O (1994). Path planning and collision avoidance for underwater vehicles using optimal control. IEEE Journal of Oceanic Engineering, 19, 502–511.
Steimle E, Hall M (2006). Unmanned surface vehicles as environmental monitoring and assessment tools. MTS/IEEE OCEANS’06, Boston, 1–5.
Svec P, Thakur A, Shah BC, Gupta SK (2012). USV trajectory planning for time varying motion goals in an environment with obstacles. ASME 2012 IDETC and CIE Conference, Chicago, 1–11.
Yan RJ, Pang S, Sun HB, Pang YJ (2010). Development and missions of unmanned surface vehicle. Journal of Marine Science and Application, 9(4), 451–457.
Author information
Authors and Affiliations
Corresponding author
Additional information
Thanapong Phanthong received his B.Sc. and M.Sc. degrees both in Physics from Prince of Songkla University in 1995 and 2004, respectively. He is a Ph.D. candidate at Department of Physics, Faculty of Science, Prince of Songkla University, Songkhla, Thailand. His research interests are in sonar image processing, underwater vehicle motion control and obstacle avoidance system.
Toshihiro Maki received his Ph.D. in Environmental and Ocean Engineering from the University of Tokyo in 2008. He is an Associate Professor in the Underwater Technology Research Center at the Institute of Industrial Science, the University of Tokyo. His research interests include underwater robotics, platform systems, informatics, and observation strategies. He is a member of IEEE OES.
Tamaki Ura received his B.S. and M.S. and Ph.D. degrees in Naval architecture from the University of Tokyo, Tokyo, Japan, in 1972, 1974 and 1977, respectively. He was a Professor of the Institute of Industrial Science (IIS), the University of Tokyo where he also had been the Director of the Underwater Technology Research Center, since 1999. He has developed several AUVs such as ‘R-One’ and ‘r2D4’.
Takashi Sakamaki is an Associate Researcher of Maki laboratory at the Institute of Industrial Science (IIS), the University of Tokyo, Tokyo, Japan. He develops and contributes several AUVs such as ‘r2D4’, ‘Tri-Dog 1’, ‘Tri-Ton’, ‘Tuna-San’, etc. His work involves a mechanism and electricity for AUVs and USVs technologies.
Pattara Aiyarak received his B.Sc. in Physics from Prince of Songkla University, Thailand in 1995. He received his Ph.D. in Physics at the University of Essex, United Kingdom in 2000. He is currently an Assistant Professor at the Department of Computer Science, Faculty of Science, Prince of Songkla University, Songkhla, Thailand. His research interests are in artificial intelligences and robotics.
Rights and permissions
About this article
Cite this article
Phanthong, T., Maki, T., Ura, T. et al. Application of A* algorithm for real-time path re-planning of an unmanned surface vehicle avoiding underwater obstacles. J. Marine. Sci. Appl. 13, 105–116 (2014). https://doi.org/10.1007/s11804-014-1224-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11804-014-1224-3