Application of A* algorithm for real-time path re-planning of an unmanned surface vehicle avoiding underwater obstacles

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.

Keywords

underwater obstacle avoidance / real-time path re-planning / A* algorithm / sonar image / unmanned surface vehicle

References

[1] Campbell S, Naeem W, Irwin GW. A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance maneuvers. Annual Reviews in Control, 2012, 36: 267-283

[2] Dechter R, Pearl J. Generalized best-first search strategies and the optimality of A*. Journal of ACM, 1985, 32: 505-536

[3] Ebken J. Applying unmanned ground vehicle technologies to unmanned surface vehicles, 2005

[4] Gao J, Xu D, Zhao N, Yan W. A potential field method for bottom navigation of autonomous underwater vehicles. Intelligent Control and Automation, Chongqing, 2008, 7466-7470

[5] Imagenex Technology Corp. DeltaT multi-beam sonar system model 837/A/B, 2011, British Columbia, Canada: Port Coquitlam

[6] Jan GE, Chang KY, Gao S, Parberry I. A 4-geometry maze router and its application on multi-terminal nets. ACM Trans. on Design Automation of Electronic Systems, 2005, 10: 116-135

[7] Kim K, Ura T. Optimal guidance for autonomous underwater vehicle navigation within undersea areas of current disturbances. Advanced Robotics, 2009, 23: 601-628

[8] Kondo H, Ura T. Navigation of an AUV for investigation of underwater structures. Control Engineering Practice, 2004, 12: 1551-1559

[9] Larson J, Bruch M, Halterman R, Rogers J, Webster R. Advances in autonomous obstacle avoidance for unmanned surface vehicles. AUVSI Unmanned Systems North America 2007, Washington DC, 2007

[10] Larson J, Ebken J, Bruch MH. Autonomous navigation and obstacle avoidance for unmanned surface vehicles. SPIE Proc. 6230: Unmanned Systems Technology VIII, Defense Security Symposium, Orlando, 2006, 17-20

[11] Lester P. A* Path finding for Beginners, 2005

[12] Maki T, Mizushima H, Kondo H, Ura T, Sakamaki T, Yanagisawa M. 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, 2007, 1-8

[13] McLain TW, Beard RW. Successive Galerkin approximations to the nonlinear optimal control of an underwater robotic vehicle. Proceedings of the 1998 IEEE International Conference on Robotics & Automation, 1998, 762-767

[14] Petillot Y, Ruiz IT, Lane DM. Underwater vehicle obstacle avoidance and path planning using a multi-beam forward looking sonar. IEEE Journal of Oceanic Engineering, 2001, 26(2): 240-251

[15] Rhoads B, Mezic I, Poje A. Minimum time feedback control of autonomous underwater vehicles. Decision and Control, Georgia, 2010, 5828-5834

[16] Spangelo I, Egeland O. Path planning and collision avoidance for underwater vehicles using optimal control. IEEE Journal of Oceanic Engineering, 1994, 19: 502-511

[17] Steimle E, Hall M. Unmanned surface vehicles as environmental monitoring and assessment tools. MTS/IEEE OCEANS’06, Boston, 2006, 1-5

[18] Svec P, Thakur A, Shah BC, Gupta SK. USV trajectory planning for time varying motion goals in an environment with obstacles. ASME 2012 IDETC and CIE Conference, Chicago, 2012, 1-11

[19] Yan RJ, Pang S, Sun HB, Pang YJ. Development and missions of unmanned surface vehicle. Journal of Marine Science and Application, 2010, 9(4): 451-457