An improved D* Lite path planning methodology for polar ships under dynamic ice conditions

Expand
  • (1a. National Engineering Research Center for Water Transport Safety (WTSC);1b. Intelligent Transportation Systems Research Center, Wuhan University of Technology, Wuhan 430063, China;2. Academician Workstation of COSCO SHIPPING Group, Shanghai 200137,China)

Received date: 2023-06-01

  Revised date: 2023-08-07

  Accepted date: 2023-08-07

  Online published: 2023-08-07

Abstract

To solve the problem of dynamic path planning of ships in polar waters, an improved D* Lite path planning algorithm was proposed combined with the Polar Operational Limit Assessment Risk Indexing System (POLARIS) to adapt to polar navigation. First, the POLARIS risk model was introduced,and by analyzing the grid-based sea ice concentration and sea ice thickness data, a polar navigation risk model was established combined with ship types. The grid environment map with navigation risk index was constructed, and the cost function of the D*Lite algorithm was reconstructed. Secondly, by extending the search neighborhood, the ship's turning Angle was not limited to integer multiples of π/2 or π/4,as a result  improving path smoothness and shortening  path length. Finally,  by introducing the navigable index of grids near non-navigable  areas due to safety factor expansion, the probability of pre-planned and re-planned routes moving away from immobilized obstacles was increased. Simulation experiments show that the improved algorithm of D* Lite algorithm not only reduces sea ice risk by 15.49 % to 40.3 % compared to traditional algorithms , but also reduces path length by 2.99% to 5.32% and path inflection points by 45.95% to 60.98%.

Cite this article

XIAO Juanjuan, ZHANG Jinfen, WU Da, HAN Bing . An improved D* Lite path planning methodology for polar ships under dynamic ice conditions[J]. Journal of Dalian Maritime University, 2023 , 49(4) : 20 -27 . DOI: 10.16411/j.cnki.issn1006-7736.2023.04.003

References

[1]XIAO J, ZHANG J, ZHANG D, et al. Research on the Current Status and Trend of Transit Vessels in the Northern Sea Route[C]//2022 10th International Conference on Traffic and Logistic Engineering (ICTLE). Macau, China: IEEE, 2022: 6-11.
[2]NAM J H, PARK I, LEE H J, et al. Simulation of optimal arctic routes using a numerical sea ice model based on an ice-coupled ocean circulation method[J]. International Journal of Naval Architecture and Ocean Engineering, 2013, 5(2): 210-226.
[3]CHOI M, CHUNG H, YAMAGUCHI H, et al. Arctic sea route path planning based on an uncertain ice prediction model[J]. Cold Regions Science and Technology, 2015, 109: 61-69.
[4]YAMAGUCHI H. Research on navigation support system for the Arctic sea routes[J]. 第31 回北方圏国際シンポジウム講演要旨集, (平28-2), 2016: 45-48.
[5]张学生, 王胜正, 杨兵. 基于雷达图像和深度Q网络的冰区航路规划方法[J]. 计算机应用, 2021, 41(增2): 304-308.
ZHANG X S, WANG S Z, YANG B. Path planning method based on radar image and deep Q-network in ice area[J]. Journal of Computer Applications, 2021, 41(S2): 304-308. (in Chinese)
[6]刘军, 冯硕, 任建华. 移动机器人路径动态规划有向D*算法[J]. 浙江大学学报(工学版), 2020, 54(2): 291-300.
LIU J, FENG S, REN J H. Directed D* algorithm for dynamic path planning of mobile robots[J]. Journal of Zhejiang University (Engineering Science), 2020, 54(2): 291-300. (in Chinese)
[7]王军, 乔丽颖, 撖昊展, 等. 基于改进D* Lite算法的移动机器人路径规划[J]. 中国科技论文, 2023, 18(7): 699-705.
WANG J, QIAO L Y, HAN H Z, et al. Path planning of mobile robot based on improved D* Lite algorithm[J]. CHINA SCIENCEPAPER, 2023, 18(7): 699-705. (in Chinese)
[8]YU JIABIN, YANG MENG,  ZHAO ZHIYAO, et al. Path planning of unmanned surface vessel in an unknown environment based on improved D* Lite algorithm[J]. Ocean Engineering, 2022, 266: 112873.
[9]连云霞, 樊永生, 余红英, 等. 改进D* Lite算法在虚拟士兵路径规划中的应用[J]. 现代电子技术, 2018, 41(6): 23-27+33.
LIAN Y X, FAN Y S, YU H Y, et al. Application of improved D* Lite algorithm in virtual soldier path planning[J]. Modern Electronics Technique, 2018, 41(6): 23-27+33. (in Chinese)
[10]张亚楠, 孙丰财, 史旭华. 基于快速D* Lite算法的移动机器人路径规划[J]. 数据通信, 2018(1): 46-51.
ZHANG Y N, SUN F C, SHI X H. Path planning of mobile robot based on fast D* Lite algorithm[J]. SHU-JU TONGXIN, 2018(1): 46-51. (in Chinese)
[11]随裕猛, 陈贤富, 刘斌. D-star Lite算法及其动态路径规划实验研究[J]. 微型机与应用, 2015, 34(7): 16-19.
SUI Y M, CHEN X F, LIU B. D-star Lite algorithm and its experimental study on dynamic path planning[J]. MICEOCOMPUTER and ITS APPLICATIONS, 2015, 34(7): 16-19. (in Chinese)
[12]LEE H W, ROH M I, KIM K S. Ship route planning in Arctic Ocean based on POLARIS[J]. Ocean Engineering, 2021, 234: 109297.
[13]曹云锋, 于萌, 惠凤鸣, 等. 北极冰区通航能力变化研究进展[J]. 科学通报, 2021, 66(1): 21-33.
CAO Y F, YU M, HUI F M, et al. Review of navigability changes in trans-Arctic routes[J]. Chinese Science Bulletin, 2021, 66(1): 21-33. (in Chinese)
[14]American Bureau of Shipping. International Maritime Organization (IMO) Polar Code Advisory. Huston: American Bureau of Shipping, 2016.
Outlines

/