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

doi:10.3969/j.issn.1007-2861.2016.07.021

上海大学学报(自然科学版) ›› 2017, Vol. 23 ›› Issue (1): 1-16.doi: 10.3969/j.issn.1007-2861.2016.07.021

• 无人艇 • 下一篇

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

张洋洋, 瞿栋, 柯俊, 李小毛

上海大学机电工程与自动化学院, 上海200072

收稿日期:2017-01-07 出版日期:2017-02-28 发布日期:2017-02-28
通讯作者: 李小毛(1981—), 男, 研究员, 研究方向为图像处理、雷达数据处理、无人艇环境感知、导航和控制及其总体技术. E-mail: lixiaomao@shu.edu.cn
作者简介:李小毛(1981—), 男, 研究员, 研究方向为图像处理、雷达数据处理、无人艇环境感知、导航和控制及其总体技术. E-mail: lixiaomao@shu.edu.cn
基金资助:
国家自然科学基金资助项目(61673254); 上海市自然科学基金资助项目(13ZR1454300); 上海市科委能力建设资助项目(14500500400)

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

ZHANG Yangyang, QU Dong, KE Jun, LI Xiaomao

School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China

Received:2017-01-07 Online:2017-02-28 Published:2017-02-28

摘要/Abstract

摘要：

速度障碍法是一种普遍应用在无人水面艇(unmanned surface vehicle, USV)上的动态避障方法, 但传统的速度障碍法未考虑无人水面艇运动学性能与障碍物运动信息误差的影响,也未明确何时开始避障与结束避障. 在速度障碍法的基础上, 用椭圆表示无人水面艇与障碍物, 给出一种求解椭圆切线的方法; 将动态窗口法与速度障碍物法相结合, 考虑无人水面艇的运动学性能, 只使用无人水面艇在给定时间内能到达的速度和方向进行避障计算; 通过比较碰撞时间与无人水面艇避开障碍物所需的时间来确定何时开始避障, 并提出一种结束避障的判断方法; 为了减小障碍物运动信息误差的影响, 提出了一种虚拟障碍物方法. 最后, 通过仿真实验验证了该避障方法的可行性与有效性.

关键词: 动态避障, 动态窗口, 速度障碍, 无人水面艇, 虚拟障碍物

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)

张洋洋, 瞿栋, 柯俊, 李小毛. 基于速度障碍法和动态窗口法的无人水面艇动态避障[J]. 上海大学学报(自然科学版), 2017, 23(1): 1-16.

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.

参考文献

[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

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	瞿栋, 彭艳, 蒲华燕, 罗均, 黄承义, 柯俊. 面向障碍速度不确定性的无人艇动态避碰[J]. 上海大学学报(自然科学版), 2019, 25(5): 655-667.
[2]	陈伟, 杨毅, 李小毛, 刘远, 张鑫. 基于目标候选的 USV 海上船艇检测[J]. 上海大学学报(自然科学版), 2019, 25(5): 668-678.
[3]	彭艳, 葛磊, 李小毛, 钟雨轩, 张鑫. 无人水面艇研究现状与发展趋势[J]. 上海大学学报(自然科学版), 2019, 25(5): 645-654.
[4]	李小毛, 张鑫, 王文涛, 瞿栋, 祝川. 基于3D激光雷达的无人水面艇海上目标检测[J]. 上海大学学报(自然科学版), 2017, 23(1): 27-36.
[5]	钟雨轩, 葛磊, 张鑫, 彭艳, 杨毅, 李小毛. 无人水面艇岛礁海域完全遍历路径规划[J]. 上海大学学报(自然科学版), 2017, 23(1): 17-26.
[6]	胡辛明1, 张鑫1, 钟雨轩1, 彭艳青2, 杨毅1, 姚骏峰1. 无人水面艇仿真系统设计与实现[J]. 上海大学学报(自然科学版), 2017, 23(1): 56-67.