基于改进的CBS 算法的USV 路径规划  

Path planning for unmanned surface vehicle with improved CBS algorithm

作　　者：姚吉宇 冮龙晖[1] YAO Jiyu;GANG Longhui(Navigation College,Dalian Maritime University,Dalian 116026,China)

机构地区：[1]大连海事大学航海学院,辽宁大连116026

出　　处：《中国航海》2023年第2期1-8,16,共9页Navigation of China

基　　金：国家自然科学基金(52171345)。

摘　　要：为实现无人艇(Unmanned Surface Vehicles,USV)在航路上的安全航行,充分考虑USV的风险约束,使航行轨迹更加符合航海实践,基于改进的冲突搜索(Conflict-Based Search,CBS)算法为USV规划路径。基于CBS的USV路径规划算法分为上下两层,上层利用约束树搜索无冲突的节点与路线,下层A*算法为每一艘USV寻找最优路径,并且结合价值函数求解全局最优的USV路径方案。研究通过添加最小安全距离约束和基于模糊理论的碰撞风险约束修正以最短距离为目标的价值函数,从而迭代生成具有安全性和经济性的USV路径方案。结果表明:该方法可在较快的时间内为多种航行环境的USV提供风险小和距离短的最优路径方案。该研究能够有效地为二维环境下的USV避碰规划路径,甚至给航海领域的多船避碰提供新的解决思路。An improved conflict-based search algorithm is introduced into USV(Unmanned Surface Vehicles,USV)path planning program to improve the feasibility of the path plan under practical navigational constraints.The path planning algorithm consists of 2 layers.The upper layer searches for conflict-free nodes and routes by using a constraint tree,and the lower layer includes an A*algorithm to find the optimal path for each USV and solves the globally optimal USV path plan according to a value function.The value function is adjusted by integrating 2 constraints,the shortest safe distance and the collision risk.The latter is decided by means of fuzzy theory.The optimization problem is solved for the object of shortest travel distance under given constraints.Tests show that the proposed algorithm is effective in 2D navigational environments.The design concept here may be used in multi-ship collision avoidance.

关 键 词：路径规划 无人艇 碰撞危险度 冲突搜索算法 

分 类 号：U675.96[交通运输工程—船舶及航道工程]