Path planning of unmanned ships based on A* and dynamic window approach

FU Long; SHEN Zhen; TAO Hao; HAN Yunjun; DONG Xisong; XIONG Gang

doi:10.11959/j.issn.2096-6652.202519

您当前的位置：

首页 >

文章列表页 >

Path planning of unmanned ships based on A* and dynamic window approach

Papers and Reports | 更新时间：2025-07-21

- Path planning of unmanned ships based on A* and dynamic window approach
- Chinese Journal of Intelligent Science and Technology Vol. 7, Issue 2, Pages: 184-199(2025)
- 作者机构：
  
  1.中国科学院大学人工智能学院，北京 100149
  2.中国科学院自动化研究所多模态人工智能系统全国重点实验室，北京 100190
  3.中国科学院自动化研究所北京市智能化技术与系统工程技术研究中心，北京 100190
  4.东莞中科云计算研究院，广东东莞 523808
  5.中国舰船研究设计中心，湖北武汉 430064
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(62461160259;92360307;92267103);The Natural Science Foundation of Beijing(L241016;L243009;L233005)
- DOI：10.11959/j.issn.2096-6652.202519
  CLC： TP242.6
- Received：28 February 2025，
  
  Revised：2025-04-11，
  
  Published：15 June 2025
- 稿件说明：
移动端阅览
付龙,沈震,陶浩等.基于A*与动态窗口法的无人船路径规划[J].智能科学与技术学报,2025,07(02):184-199.

FU Long,SHEN Zhen,TAO Hao,et al.Path planning of unmanned ships based on A* and dynamic window approach[J].Chinese Journal of Intelligent Science and Technology,2025,07(02):184-199.
付龙,沈震,陶浩等.基于A*与动态窗口法的无人船路径规划[J].智能科学与技术学报,2025,07(02):184-199. DOI： 10.11959/j.issn.2096-6652.202519.

FU Long,SHEN Zhen,TAO Hao,et al.Path planning of unmanned ships based on A* and dynamic window approach[J].Chinese Journal of Intelligent Science and Technology,2025,07(02):184-199. DOI： 10.11959/j.issn.2096-6652.202519.

摘要

海岸线突袭任务要求无人水面船（unmanned surface vessel，USV）在复杂的海岸环境中完成精确的定点突袭。海岸区域地形多变，存在礁石、浅滩等静态障碍物与海上漂浮物等动态障碍物，同时任务时间有严格要求。因此，为USV提供实时、安全、准确的路径规划非常重要。针对当前路径规划存在无法兼顾全局寻优、时效性和安全性的难题，基于A*算法和动态窗口法（dynamic window approach，DWA）提出了全局探索与局部优化相融合的方法：A*算法提供静态环境下全局最短路径，路径节点之间使用改进的DWA进行局部路径避障优化。通过引入动态指数衰减加权的启发式函数改进A*算法，降低了全局路径规划的运行时间和探索空间；通过引入动态障碍物航向角和USV预测轨迹航向角的夹角评价子函数和基于Logistic函数的距离评价子函数来改进DWA，增强了局部避障中的实时反应能力。仿真结果表明，融合算法在海岸线突袭任务中能够实时探索全局近优解，有效应对静态和动态障碍物的影响，显著提升USV在复杂海岸线环境中的任务完成效率和稳定性。

Abstract

The coastline raid task requires an unmanned surface ship to carry out precise

fixed-point raids in a complex coastal environment. The terrain of the coastal area is highly varied

with static obstacles such as reefs and shoals

as well as moving obstacles like floating objects at sea. Moreover

the task must be completed within a strict time frame. Therefore

real-time

safe

and accurate path planning for the unmanned surface ship is crucial. To address the challenge of balancing global optimization

efficiency

and safety in path planning

a method that integrates global search and local optimization was proposed

based on the A* algorithm and the dynamic window approach (DWA). The A* algorithm computed the global shortest path in a static environment

while the improved DWA optimized local path obstacle avoidance between path nodes. The A* algorithm was enhanced by incorporating a heuristic function with dynamic exponential decay weighting

which reduced the running time and exploration space for global path planning. Additionally

the DWA was improved by introducing an evaluation function based on the angle between the heading of dynamic obstacles and the predicted trajectory of the unmanned surface ship

as well as a distance evaluation function based on a logistic curve

which enhanced the real-time responsiveness of local obstacle avoidance. Simulation results demonstrate that the proposed hybrid algorithm can search for a near-optimal global solution in real-time

effectively handle both static and dynamic obstacles

and significantly improve the task completion efficiency and stability of the unmanned surface ship in complex coastal environments.

关键词

Keywords

references

BALADO J, DÍAZ-VILARIÑO L, ARIAS P, et al. Point clouds for direct pedestrian pathfinding in urban environments[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2019, 148: 184-196.

董璐, 熊爱玲. 基于改进RRT * -Smart的复杂动态环境下的无人艇路径规划[J ] . 智能科学与技术学报, 2022, 4(2): 264-276.

DONG L, XIONG A L. Path planning for unmanned surface vehicle in complex dynamic environment based on improved RRT * -Smart[J ] . Chinese Journal of Intelligent Science and Technology, 2022, 4(2): 264-276.

DEVAURS D, SIMÉON T, CORTÉS J. Optimal path planning in complex cost spaces with sampling-based algorithms[J]. IEEE Transactions on Automation Science and Engineering, 2016, 13(2): 415-424.

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.

辛峻峰, 张永波, 伯佳更, 等. 基于数据驱动的遗传算法的无人艇路径规划研究[J]. 智能科学与技术学报, 2019, 1(2): 171-180.

XIN J F, ZHANG Y B, BO J G, et al. Study on path planning of unmanned surface vessel based on data-driven genetic algorithm[J]. Chinese Journal of Intelligent Science and Technology, 2019, 1(2): 171-180.

LI C G, HUANG X, DING J, et al. Global path planning based on a bidirectional alternating search A* algorithm for mobile robots[J]. Computers & Industrial Engineering, 2022, 168: 108123.

LIN Z, WU K, SHEN R L, et al. An efficient and accurate A-star algorithm for autonomous vehicle path planning[J]. IEEE Transactions on Vehicular Technology, 2024, 73(6): 9003-9008.

王洪斌, 尹鹏衡, 郑维, 等. 基于改进的A*算法与动态窗口法的移动机器人路径规划[J]. 机器人, 2020, 42(3): 346-353.

WANG H B, YIN P H, ZHENG W, et al. Mobile robot path planning based on improved A* algorithm and dynamic window method[J]. Robot, 2020, 42(3): 346-353.

朱泺谕, 胡明, 吴湘, 等. 基于A*算法奖惩机制改进并优化路径选择的AGV路径规划[J]. 计算机集成制造系统, 已录用, doi.org/10.13196/j.cims.2024.0380.

ZHU L Y, HU M, WU X, et al. AGV path planning based on A* algorithm reward and punishment mechanism to improve and optimize path selection[J]. Computer Integrated Manufacturing Systems, accepted, doi.org/10.13196/j.cims.2024.0380.

赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910.

ZHAO X, WANG Z, HUANG C K, et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot, 2018, 40(6): 903-910.

张伟民, 徐森生, 张月. 基于改进A*算法的室内巡检机器人路径规划研究[J]. 机械工程学报, 2024, 60(20): 315-326.

ZHANG W M, XU S S, ZHANG Y. Research on path planning of indoor inspection robot based on improved A* algorithm[J]. Journal of Mechanical Engineering, 2024, 60(20): 315-326.

张浩杰, 张玉东, 梁荣敏, 等. 改进A*算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45(2): 513-520.

ZHANG H J, ZHANG Y D, LIANG R M, et al. Energy-efficient path planning method for robots based on improved A* algorithm[J]. Systems Engineering and Electronics, 2023, 45(2): 513-520.

陈艺文, 江文松, 杨力, 等. 基于运动约束的移动机器人路径规划[J]. 计算机集成制造系统, 2023, 29(4): 1186-1193.

CHEN Y W, JIANG W S, YANG L, et al. Path planning based on motion constraints for mobile robot[J]. Computer Integrated Manufacturing Systems, 2023, 29(4): 1186-1193.

GAO Y, LI D Z, SUI Z, et al. Trajectory planning and tracking control of autonomous vehicles based on improved artificial potential field[J]. IEEE Transactions on Vehicular Technology, 2024, 73(9): 12468-12483.

FOX D, BURGARD W, THRUN S. The dynamic window approach to collision avoidance[J]. IEEE Robotics & Automation Magazine, 1997, 4(1): 23-33.

OGREN P, LEONARD N E. A convergent dynamic window approach to obstacle avoidance[J]. IEEE Transactions on Robotics, 2005, 21(2): 188-195.

王永雄, 田永永, 李璇, 等. 穿越稠密障碍物的自适应动态窗口法[J]. 控制与决策, 2019, 34(5): 927-936.

WANG Y X, TIAN Y Y, LI X, et al. Self-adaptive dynamic window approach in dense obstacles[J]. Control and Decision, 2019, 34(5): 927-936.

LEE D H, LEE S S, AHN C K, et al. Finite distribution estimation-based dynamic window approach to reliable obstacle avoidance of mobile robot[J]. IEEE Transactions on Industrial Electronics, 2021, 68(10): 9998-10006.

DOBREVSKI M, SKOČAJ D. Dynamic adaptive dynamic window approach[J]. IEEE Transactions on Robotics, 2024, 40: 3068-3081.

JIAN Z Q, ZHANG S Y, SUN L F, et al. Long-term dynamic window approach for kinodynamic local planning in static and crowd environments[J]. IEEE Robotics and Automation Letters, 2023, 8(6): 3294-3301.

YASUDA S, KUMAGAI T, YOSHIDA H. Safe and efficient dynamic window approach for differential mobile robots with stochastic dynamics using deterministic sampling[J]. IEEE Robotics and Automation Letters, 2023, 8(5): 2614-2621.

张伟龙, 单梁, 常路, 等. 基于改进DWA的多无人水面艇分布式避碰算法[J]. 控制与决策, 2023, 38(4): 951-962.

ZHANG W L, SHAN L, CHANG L, et al. Distributed collision avoidance algorithm for multiple unmanned surface vessels based on improved DWA[J]. Control and Decision, 2023, 38(4): 951-962.

FU J Y, SUN G H, YAO W R, et al. On trajectory Homotopy to explore and penetrate dynamically of multi-UAV[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(12): 24008-24019.

王洪斌, 刘德垚, 郑维, 等. 异构多目标差分-动态窗口算法及其在移动机器人中的应用[J]. 控制与决策, 2023, 38(12): 3390-3398.

WANG H B, LIU D Y, ZHENG W, et al. Heterogeneous multi-objective differential evolution-dynamic window algorithm and application for energy-saving motion planning of mobile robot[J]. Control and Decision, 2023, 38(12): 3390-3398.

迟旭, 李花, 费继友. 基于改进A*算法与动态窗口法融合的机器人随机避障方法研究[J]. 仪器仪表学报, 2021, 42(3): 132-140.

CHI X, LI H, FEI J Y. Research on robot random obstacle avoidance method based on fusion of improved A* algorithm and dynamic window method[J]. Chinese Journal of Scientific Instrument, 2021, 42(3): 132-140.

WANG D, CHEN H M, LAO S H, et al. Efficient path planning and dynamic obstacle avoidance in edge for safe navigation of USV[J]. IEEE Internet of Things Journal, 2024, 11(6): 10084-10094.

HAN S, WANG L, WANG Y T, et al. A dynamically hybrid path planning for unmanned surface vehicles based on non-uniform Theta* and improved dynamic windows approach[J]. Ocean Engineering, 2022, 257: 111655.

YANG H X, XU X M, HONG J C. Automatic parking path planning of tracked vehicle based on improved A* and DWA algorithms[J]. IEEE Transactions on Transportation Electrification, 2023, 9(1): 283-292.

HAN L, WU X H, SUN X. Hybrid path planning algorithm for mobile robot based on A* algorithm fused with DWA[C]//Proceedings of the 2023 IEEE 3rd International Conference on Information Technology, Big Data and Artificial Intelligence (ICIBA). Piscataway: IEEE Press, 2023: 1465-1469.

GUAN W, WANG K. Autonomous collision avoidance of unmanned surface vehicles based on improved A-star and dynamic window approach algorithms[J]. IEEE Intelligent Transportation Systems Magazine, 2023, 15(3): 36-50.

唐炜, 谭啸, 孙宇, 等. 基于A*与动态窗口法的物料传输平台路径规划研究[J]. 智能科学与技术学报, 2023, 5(4): 515-524.

TANG W, TAN X, SUN Y, et al. Research on path planning of material transportation platform based on A* and dynamic window method[J]. China Industrial Economics, 2023: 1-10.

邹文, 韩丙辰, 李鹏飞, 等. 融合改进A*算法和优化动态窗口法的路径规划[J]. 计算机集成制造系统, 2024, 30(1): 184-195.

ZOU W, HAN B C, LI P F, et al. Path planning by integrating improved A* algorithm and optimized dynamic window approach[J]. Computer Integrated Manufacturing Systems, 2024, 30(1): 184-195.

孙岩霆, 王荣杰, 蒋德松. 融合A*与DWA算法的水面船艇动态路径规划[J]. 仪器仪表学报, 2024, 45(1): 301-310.

SUN Y T, WANG R J, JIANG D S. Dynamic path planning of surface ship by combining A* and dynamic window algorithm[J]. Chinese Journal of Scientific Instrument2024, 45(1): 301-310.

赖荣燊, 窦磊, 巫志勇, 等. 融合改进A*算法和动态窗口法的移动机器人路径规划[J]. 系统仿真学报, 2024, 36(8): 1884-1894.

LAI R S, DOU L, WU Z Y, et al. Fusion of improved A* and dynamic window approach for mobile robot path planning[J]. Journal of System Simulation, 2024, 36(8): 1884-1894.

王彬, 聂建军, 李海洋, 等. 优化A*与动态窗口法的移动机器人路径规划[J]. 计算机集成制造系统, 2024, 30(4): 1353-1363.

WANG B, NIE J J, LI H Y, et al. Mobile robot path planning based on optimized A* and dynamic window approach[J]. Computer Integrated Manufacturing Systems,2024, 30(4): 1353-1363.

郁洲, 毕敬, 苑海涛. 基于改进DQN算法的复杂海战场路径规划方法[J]. 智能科学与技术学报, 2022(3): 418-425.

YU Z, BI J, YUAN H T. A path planning method for complex naval battle field based on an improved DQN algorithm[J]. Chinese Journal of Intelligent Science and Technology, 2022(3): 418-425.

QU T C, XIONG G, ALI H, et al. USV path planning under marine environment simulation using DWA and safe reinforcement learning[C]//Proceedings of the 2023 IEEE 19th International Conference on Automation Science and Engineering (CASE). Piscataway: IEEE Press, 2023: 1-6.

QU T C, XIONG G, ALI H, et al. DWAS-RL: a safety-efficiency balanced reinforcement learning approach for path planning of Unmanned Surface Vehicles in complex marine environments[J]. Ocean Engineering, 2025, 317: 119641.

ALI H, XIONG G, HAIDER M H, et al. Feature selection-based decision model for UAV path planning on rough terrains[J]. Expert Systems with Applications, 2023, 232: 120713.

ALI H, XIONG G, QU T C, et al. Autonomous ship navigation with an enhanced safety collision avoidance technique[J]. ISA Transactions, 2024, 144: 271-281.

傅汇乔, 唐开强, 邓归洲, 等. 基于深度强化学习的六足机器人运动规划[J]. 智能科学与技术学报, 2020, 2(4): 361-371.

FU H Q, TANG K Q, DENG G Z, et al. Motion planning for hexapod robot using deep reinforcement learning[J]. Chinese Journal of Intelligent Science and Technology, 2020, 2(4): 361-371.

HSU D, LATOMBE J C, MOTWANI R. Path planning in expansive configuration spaces[C]//Proceedings of the Proceedings of International Conference on Robotics and Automation. Piscataway: IEEE Press, 1997: 2719-2726.

LIU Z X, ZHANG Y M, YU X, et al. Unmanned surface vehicles: an overview of developments and challenges[J]. Annual Reviews in Control, 2016, 41: 71-93.

Views

757

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on path planning of material transmission platform based on A* and dynamic window method

Path planning for oversized cargo vehicles considering three-dimensional collision risks

Research on unmanned mining truck path planning based on grey wolf optimization adaptive hybrid A* and artificial potential field

Multi-AUV cooperative localization in adaptive sampling for marine environmental monitoring

A path planning method for complex naval battle field based on an improved DQN algorithm

Related Author

TAN Xiao

SUN Yu

YAN Jiapeng

YAN Guangrui

TANG Wei

ZHANG Yun

WANG Jing

SONG Ge

Related Institution

School of Mechanical Engineering, Jiangsu University of Science and Technology

College of Engineering Science and Technology, Shanghai Ocean University

College of Information Technology, Shanghai Ocean University

Institute of Artificial Intelligence and Robotics, Xi’an Jiaotong University

State Key Laboratory of Industrial Control Technology, Zhejiang University

Postal code：100079
Tel：（010）53879206 Email：cjist@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
Total Visits：161982 Visits Today：145

⁰