基于速度障碍法和动态窗口法的无人水面艇动态避障

doi:10.3969/j.issn.1007-2861.2016.07.021

Abstract

Abstract:

Velocity obstacle is a dynamic obstacle avoidance algorithm widely used on an unmanned surface vehicle (USV). However, traditional velocity obstacle does not consider the effect of USV’s kinematics and obstacle’s motion information error, and does not know when to start and terminate avoidance. Based on velocity obstacle, USV and obstacle are represented by an ellipse. A method for solving ellipse tangent is proposed. Considering the kinematics performance of USV, a dynamic window method and velocity obstacle are combined. Only the speed and course that the USV can reach in a given time are used in calculation. By comparing the collision time and the time required for the USV to finish avoidance to determine when to start avoidance, a method to terminate obstacle avoidance is proposed. A virtual obstacle method is then proposed to reduce influence of obstacle’s motion information error. Feasibility and effectiveness of the method are verified by simulation.

Key words: dynamic window , dynamic avoidance , velocity obstacle , virtual obstacle, unmanned surface vehicle (USV)

ZHANG Yangyang, QU Dong, KE Jun, LI Xiaomao. Dynamic obstacle avoidance for USV based on velocity obstacle and dynamic window method[J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(1): 1-16.

References

[1] Fox D, Burgard W, Thrun S. The dynamic window approach to collision avoidance [J]. IEEE Robotics & Automation Magazine, 1997, 4(1): 23-33.
[2] Campbell S, Naeem W, Irwin GW. A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance manoeuvres [J]. Annual Reviews in Control, 2012, 36(2): 267-283.
[3] Casalino G, Turetta A, Simetti E. A three-layered architecture for real time path planning and obstacle avoidance for surveillance USVs operating in harbour fields [C]// Oceans. 2009: 1-8.
[4] Dijkstra E W. A note on two problems in connexion with graphs [J]. Numerische Mathematik, 1959, 1(1): 269-271.
[5] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
[6] Kim H, Kim D, Shin J U, et al. Angular rate-constrained path planning algorithm for unmanned surface vehicles [J]. Ocean Engineering, 2014, 84: 37-44.
[7] Koenig S, Likhachev M, Furcy D. Lifelong planning A* [J]. Artificial Intelligence, 2004, 155(1): 93-146.
[8] Likhachev M, Ferguson D I, Gordon G J, et al. Anytime dynamic A*: an anytime, replanning algorithm [C]// Fifteenth International Conference on Automated Planning and Scheduling. 2005: 262-271.
[9] Likhachev M, Koenig S. A generalized framework for lifelong planning A* search [C]// Fifteenth International Conference on Automated Planning and Scheduling. 2005: 99-108.
[10] Stentz A. The focussed D* algorithm for real-time replanning [C]// International Joint Conference on Artificial Intelligence. 2000: 3310-3317.
[11] Botea A, Müler M, Schaeffer J. Near optimal hierarchical path-finding [J]. Journal of Game Development, 2004, 1(7): 7-28.
[12] Leigh R, Louis S J, Miles C. Using a genetic algorithm to explore A*-like pathfinding algorithms[C]// IEEE Symposium on Computational Intelligence and Games. 2007: 72-79.

[13] Yang S X, Luo C. A neural network approach to complete coverage path planning [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2004, 34(1): 718-724.
[14] Melchior N A, Simmons R. Particle RRT for path planning with uncertainty [C]// IEEE International Conference on Robotics and Automation. 2007: 1617-1624.
[15] Hsu D, Kindel R, Latombe J C, et al. Randomized kinodynamic motion planning with moving obstacles [J]. International Journal of Robotics Research, 2002, 21(3): 233-255.
[16] Rodriguez, Tang X, Lien J M, et al. An obstacle-based rapidly-exploring random tree [C]//IEEE International Conference on Robotics and Automation. 2006: 895-900.
[17] Kamon I, Rivlin E, Rimon E. A new range-sensor based globally convergent navigation algorithm for mobile robots [C]// IEEE International Conference on Robotics & Automation. 1995: 429-435.
[18] Ng J, Bränl T. Performance comparison of bug navigation algorithms [J]. Journal of Intelligent and Robotic Systems, 2007, 50(1): 73-84.
[19] Kamon I, Rimon E, Rivlin E. TangentBug: a range-sensor-based navigation algorithm [J]. International Journal of Robotics Research, 1998, 17(9): 934-953.
[20] Maravall D, Lope J D, Fuentes J P. Visual bug algorithm for simultaneous robot homing and obstacle avoidance using visual topological maps in an unmanned ground vehicle [M]. New York: Springer International Publishing, 2015: 301-310.
[21] Zohaib M, Pasha S M, Javaid N, et al. Intelligent bug algorithm (IBA): a novel strategy to navigate mobile robots autonomously [C]// Springers International Multi Topic Conference. 2013.
[22] Hashmi U, Afshan F, Rafiq M. Performance analysis of different optimal path planning bug algorithms on a client server based mobile surveillance UGV [C]// International Conference on Intelligent Systems Modelling & Simulation. 2013: 30-35.
[23] Buniyamin N, Wan N W, Sariff N, et al. A simple local path planning algorithm for autonomous mobile robots [J]. International Journal of Systems Applications, Engineering & Development, 2011, 5(2): 151-159.
[24] Mohamed E F, ElMetwally K, Hanafy A. An improved Tangent Bug method integrated with artificial potential field for multi-robot path planning [C]// International Symposium on Innovations in Intelligent Systems and Applications. 2011: 555-559.
[25] Khatib M, Chatila R. An extended potential field approach for mobile robot sensor-based motions [C]// Intelligent Autonomous Systems. 1995: 490-496.
[26] Khatib O. Real-time obstacle avoidance for manipulators and mobile robots [J]. International Journal of Robotics Research, 1986, 5(1): 90-98.
[27] Huang Y, Hu H, Liu X. Obstacles avoidance of artificial potential field method with memory function in complex environment [C]// Intelligent Control and Automation. 2010: 6414-6418.
[28] Zohaib M, Pasha S M, Javaid N, et al. An improved algorithm for collision avoidance in environments having U and H shaped obstacles [J]. Studies in Informatics & Control, 2014, 23(1): 97-106.
[29] Sezer V, Gokasan M. A novel obstacle avoidance algorithm: “follow the gap method” [J]. Robotics & Autonomous Systems, 2012, 60(9): 1123-1134.

[30] Brock O, Khatib O. High-speed navigation using the global dynamic window approach [C]//IEEE International Conference on Robotics and Automation. 1999: 341-346.
[31] Seder M, Petrovic I. Dynamic window based approach to mobile robot motion control in the presence of moving obstacles [C]// IEEE International Conference on Robotics and Automation. 2007: 1986-1991.
[32] Tang P, Zhang R, Liu D, et al. Research on near-field obstacle avoidance for unmanned surface vehicle based on heading window [C]// 24th Chinese Control and Decision Conference. 2012: 1262-1267.
[33] Zhang R, Tang P, Su Y, et al. An adaptive obstacle avoidance algorithm for unmanned surface vehicle in complicated marine environments [J]. IEEE/CAA Journal of Automatica Sinica, 2014, 1(4): 385-396.
[34] Simetti E, Torelli S, Casalino G, et al. Experimental results on obstacle avoidance for high speed unmanned surface vehicles [C]// Oceans. 2014: 1-6.
[35] Wu G, Shi D, Guo J. Deliberative collision avoidance for unmanned surface vehicle based on the directional weight [J]. Journal of Shanghai Jiaotong University (Science), 2016, 21(3): 307-312.
[36] Chakravarthy A, Ghose D. Obstacle avoidance in a dynamic environment: a collision cone approach [J]. Systems & Humans, 1998, 28(5): 562-574.
[37] Chakravarthy A, Ghose D. Collision cones for quadric surfaces [J]. IEEE Transactions on Robotics, 2011, 27(6): 1159-1166.
[38] Fiorini P. Motion planning in dynamic environments using velocity obstacles [J]. International Journal of Robotics Research, 1998, 17(7): 760-772.
[39] Kuwata Y, Wolf M T, Zarzhitsky D, et al. Safe maritime autonomous navigation with colregs, using velocity obstacles [J]. IEEE Journal of Oceanic Engineering, 2014, 39(1): 110-119.
[40] Johansen T A, Perez T, Cristofaro A. Ship collision avoidance and colregs compliance using simulation-based control behavior selection with predictive hazard assessment [J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17: 1-16.
[41] Naeem W, Irwin G W, Yang A. COLREGs-based collision avoidance strategies for unmanned surface vehicles [J]. Mechatronics, 2012, 22(6): 669-678.
[42] Breivik M, Hovstein V, Fossen T. Straight-line target tracking for unmanned surface vehicles [J]. Modeling Identification and Control, 2008, 29(4): 131-149.
[43] Breivik M, Fossen T I. Guidance laws for planar motion control [C]// IEEE Conference on Decision and Control. 2008: 570-577.

Dynamic obstacle avoidance for USV based on velocity obstacle and dynamic window method

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 6

Recommended Articles

Metrics

Comments

[1]	Dong QU, Yan PENG, Huayan PU, Jun LUO, Chengyi HUANG, Jun KE. Dynamic collision avoidance for unmanned surface vessels under the uncertainty of obstacle velocity [J]. Journal of Shanghai University（Natural Science Edition）, 2019, 25(5): 655-667.
[2]	Wei CHEN, Yi YANG, Xiaomao LI, Yuan LIU, Xin ZHANG. Maritime ships detection for USV based on object proposals [J]. Journal of Shanghai University（Natural Science Edition）, 2019, 25(5): 668-678.
[3]	Yan PENG, Lei GE, Xiaomao LI, Yuxuan ZHONG, Xin ZHANG. Research status and development trend of unmanned surface vehicle [J]. Journal of Shanghai University（Natural Science Edition）, 2019, 25(5): 645-654.
[4]	LI Xiaomao, ZHANG Xin, WANG Wentao, QU Dong, ZHU Chuan. 3D Lidar-based marine object detection for USV [J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(1): 27-36.
[5]	ZHONG Yuxuan, GE Lei, ZHANG Xin, PENG Yan, YANG Yi, LI Xiaomao. Complete coverage path planning of USV used for mapping round island [J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(1): 17-26.
[6]	HU Xinming1, ZHANG Xin1, ZHONG Yuxuan1 PENG Yanqing2, YANG Yi1, YAO Junfeng1. Design and implementation of USV simulation system [J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(1): 56-67.