AUV Path Planning Integrating Local-global Strategies in Unknown Environments

doi:10.16182/j.issn1004731x.joss.24-0983

Abstract

Abstract:

Existing path planning algorithms often struggle to efficiently explore and generate high-quality trajectories. To address this issue, this paper proposes a path planning algorithm that integrates local-global strategies. By employing the rolling window technique, the global one-time path planning problem is transformed into an iterative process of multiple local planning stages. During the global exploration phase, the rolling window is used to determine high-level path branches and to identify branch waypoints, thereby refining the calculation of local paths. In the local exploration phase, an improved RRT-Connect algorithm is proposed, which combines adaptive circular sampling with dynamic step length to reduce redundant sampling points. Simulation experiments demonstrate that the algorithm can efficiently achieve AUV path search in unknown complex environments. The improved RRT-Connect algorithm features faster convergence, generates shorter paths, and produces paths that are closer to the global path.

Key words: path planning, unknown underwater space, rolling planning, improved RRT-Connect algorithm

CLC Number:

TP242.6

Meng Wenlong, Pu Yanbo, Gong Ya. AUV Path Planning Integrating Local-global Strategies in Unknown Environments[J]. Journal of System Simulation, 2026, 38(4): 889-902.

Figures/Tables 16

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 1

Simulation parameters

主要仿真参数	量值
排斥系数 $u$	1.5
排斥效应上限 $D s u p$	160
排斥效应下限 $D i n f$	5
候选子目标点数 $m$	10
滚动窗口半径	100
固定步长 $s$	30
最大迭代次数	1 000
每一场景测试次数	50
重连搜索半径 $r$	20

Table 1

Fig. 6

Table 2

Fig. 7

Table 3

Fig. 8

Fig. 9

Fig. 10

Table 4

Fig. 11

Fig. 12

References 30

[1]	Sina Sharif Mansouri, Kanellakis Christoforos, Fresk Emil, et al. Cooperative Coverage Path Planning for Visual Inspection[J]. Control Engineering Practice, 2018, 74: 118-131.
[2]	Beck Zoltán, Teacy W, Rogers A, et al. Online Planning for Collaborative Search and Rescue by Heterogeneous Robot Teams[C]// Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. Richland: International Foundation for Autonomous Agents and Multiagent Systems, 2016: 1024-1033.
[3]	Kanellakis Christoforos, Sina Sharif Mansouri, Georgoulas George, et al. Towards Autonomous Surveying of Underground Mine Using MAVs[C]//Advances in Service and Industrial Robotics. Cham: Springer International Publishing, 2019: 173-180.
[4]	Carreras Marc, Juan David Hernández, Vidal Eduard, et al. Sparus II AUV-a Hovering Vehicle for Seabed Inspection[J]. IEEE Journal of Oceanic Engineering, 2018, 43(2): 344-355.
[5]	Oral Tugcem, Polat Faruk. MOD* Lite: An Incremental Path Planning Algorithm Taking Care of Multiple Objectives[J]. IEEE Transactions on Cybernetics, 2016, 46(1): 245-257.
[6]	李娟, 张子浩, 张宏瀚. 复杂环境下DWA与RRT算法融合的AUV局部路径规划[J]. 智能系统学报, 2024, 19(4): 961-973.
	Li Juan, Zhang Zihao, Zhang Honghan. Local Path Planning for AUV with Fusion of DWA and RRT Algorithms in a Complex Environment[J]. CAAI Transactions on Intelligent Systems, 2024, 19(4): 961-973.
[7]	张季然, 陈德山, 李廷文, 等. 面向水下未知空间探测的改进RRT路径搜索算法[J]. 武汉理工大学学报(交通科学与工程版), 2023, 47(2): 256-262.
	Zhang Jiran, Chen Deshan, Li Tingwen, et al. An Improved RRT Path Search Algorithm for Underwater Unknown Space Detection[J]. Journal of Wuhan University of Technology(Transportation Science & Engineering), 2023, 47(2): 256-262.
[8]	Meng Wenlong, Gong Ya, Xu Fan, et al. Efficient Path Planning for AUVs in Unmapped Marine Environments Using a Hybrid Local-global Strategy[J]. Ocean Engineering, 2023, 288, Part 2: 116227.
[9]	Orozco-Rosas Ulises, Montiel Oscar, Sepúlveda Roberto. Mobile Robot Path Planning Using Membrane Evolutionary Artificial Potential Field[J]. Applied Soft Computing, 2019, 77: 236-251.
[10]	Fan Xiaojing, Guo Yinjing, Liu Hui, et al. Improved Artificial Potential Field Method Applied for AUV Path Planning[J]. Mathematical Problems in Engineering, 2020, 2020(1): 6523158.
[11]	Chen Yongbo, Luo Guanchen, Mei Yuesong, et al. UAV Path Planning Using Artificial Potential Field Method Updated by Optimal Control Theory[J]. International Journal of Systems Science, 2016, 47(6): 1407-1420.
[12]	Min Gyu Park, Jae Hyun Jeon, Min Cheol Lee. Obstacle Avoidance for Mobile Robots Using Artificial Potential Field Approach with Simulated Annealing[C]//ISIE 2001. 2001 IEEE International Symposium on Industrial Electronics Proceedings. Piscataway: IEEE, 2001: 1530-1535.
[13]	Min Gyu Park, Min Cheol Lee. A New Technique to Escape Local Minimum in Artificial Potential Field Based Path Planning[J]. KSME International Journal, 2003, 17(12): 1876-1885.
[14]	Zhang Chungang, Xi Yugeng. Robot Path Planning in Globally Unknown Environments Based on Rolling Windows[J]. Science in China Series E: Technolgical Science, 2001, 44(2): 131-139.
[15]	张纯刚, 席裕庚. 基于局部探测信息的机器人滚动路径规划[J]. 自动化学报, 2003, 29(1): 38-44.
	Zhang Chungang, Xi Yugeng. Robot Rolling Path Planning Based on Locally Detected Information[J]. Acta Automatica Sinica, 2003, 29(1): 38-44.
[16]	Zhang Yalong, Liu Zhenghua, Chang Le. A New Adaptive Artificial Potential Field and Rolling Window Method for Mobile Robot Path Planning[C]//2017 29th Chinese Control and Decision Conference (CCDC). Piscataway: IEEE, 2017: 7144-7148.
[17]	Li Caihong, Wang Fengying, Song Yong, et al. A Complete Coverage Path Planning Algorithm for Mobile Robot Based on FSM and Rolling Window Approach in Unknown Environment[C]//2015 34th Chinese Control Conference (CCC). Piscataway: IEEE, 2015: 5881-5885.
[18]	Chu Zhenzhong, Wang Fulun, Lei Tingjun, et al. Path Planning Based on Deep Reinforcement Learning for Autonomous Underwater Vehicles Under Ocean Current Disturbance[J]. IEEE Transactions on Intelligent Vehicles, 2023, 8(1): 108-120.
[19]	Hadi Behnaz, Khosravi Alireza, Sarhadi P. Deep Reinforcement Learning for Adaptive Path Planning and Control of an Autonomous Underwater Vehicle[J]. Applied Ocean Research, 2022, 129: 103326.
[20]	Li Zhaolun, Luo Xiaonan. Autonomous Underwater Vehicles (AUVs) Path Planning Based on Deep Reinforcement Learning[C]//2022 9th International Conference on Digital Home (ICDH). Piscataway: IEEE, 2022: 257-262.
[21]	Carlos E García, Prett D M, Morari M. Model Predictive Control: Theory and practice-a Survey[J]. Automatica, 1989, 25(3): 335-348.
[22]	Kuffner J J, LaValle S M. RRT-connect: An Efficient Approach to Single-query Path Planning[C]//Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings. Piscataway: IEEE, 2000: 995-1001.
[23]	Garcia Vincent, Debreuve Eric, Barlaud Michel. Fast k Nearest Neighbor Search Using GPU[C]//2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. Piscataway: IEEE, 2008: 1-6.
[24]	Pan Jia, Lauterbach C, Manocha D. Efficient Nearest-neighbor Computation for GPU-based Motion Planning[C]//2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE, 2010: 2243-2248.
[25]	Zhao Leyang, Yan Li, Hu Xiao, et al. Efficient and High Path Quality Autonomous Exploration and Trajectory Planning of UAV in an Unknown Environment[J]. ISPRS International Journal of Geo-Information, 2021, 10(10): 631.
[26]	Li Juan, Li Chengyue, Chen Tao, et al. Improved RRT Algorithm for AUV Target Search in Unknown 3D Environment[J]. Journal of Marine Science and Engineering, 2022, 10(6): 826.
[27]	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, Part 3: 112873.
[28]	Masehian Ellips, Kakahaji Hossein. NRR: A Nonholonomic Random Replanner for Navigation of Car-like Robots in Unknown Environments[J]. Robotica, 2024, 32(7): 1101-1123.
[29]	Lavalle S J R R. Rapidly-exploring Random Trees: A New tool for Path Planning[J]. Research Report, 1998, 98: 11-19.
[30]	Karaman S, Frazzoli E. Sampling-based Algorithms for Optimal Motion Planning[J]. International Journal of Robotics Research, 2011, 30(7): 846-894.

探测范围/m	地图I		地图III
探测范围/m	时间/ms	长度	时间/ms	长度
10	124	2 021	247	1 889
50	47	1 982	123	1 752
100	15	1 873	54	1 658
200	11	1 733	36	1 564
400	7	1 654	19	1 497
1 000	4	1 564	11	1 354

方法	评价指标	地图I	地图III
本文方法	平均时间/ms	1.74	2.91
本文方法	平均长度	1 582	1 481
RRT^[29]	平均时间/ms	45.12	87.96
RRT^[29]	平均长度	1 656	1 698
RRT-Connect^[22]	平均时间/ms	3.38	5.6
RRT-Connect^[22]	平均长度	1 609	1 507
RRT*^[30]	平均时间/ms	3 613.24	10 329.6
RRT*^[30]	平均长度	1 335	1 281