改进A*算法和人工势场法的路径规划

doi:10.16182/j.issn1004731x.joss.23-0255

摘要/Abstract

摘要：

A*算法存在折线路径多和搜索节点多的问题，人工势场(artificial potential field, APF)法存在局部最优和不可到达的问题，针对两种算法存在的问题进行了研究。利用欧氏距离与投影距离提出一种新的混合式启发函数，依据该函数对 $A *$ 算法的流程进行改进，减少A*算法的搜索节点，提高搜索效率。利用新A*算法生成的最优节点作为APF算法的局部目标点，辅助机器人摆脱局部最优点；通过加入机器人和目标点的位置关系改进势场函数，修改斥力的增益，优化斥力的生成方向。在改进的基础上将两种算法融合提出一种新的算法，利用APF法的势场函数引导 $A *$ 算法的搜索。从路径长度、避障效果、迭代次数对改进算法进行对比分析，仿真结果表明，提出的改进算法搜索效率高，实现避障的同时保证计算的路径最优。

关键词: APF算法, A*算法, 路径规划, 引力势场, 斥力势场

Abstract:

A* algorithm has the problem of too many polyline paths and search nodes, while the artificial potential field (APF) method has the problems of local optimality and unattainability. These problems are investigated in this paper. A new hybrid heuristic function is proposed based on the Euclidean distance and projection distance, based on which the $A *$ algorithm process is improved accordingly.The search nodes of the A* algorithm are reduced, and the search efficiency is improved. The optimal node generated by the new A* algorithm is used as the local target point of the APF algorithm to assist in getting rid of the local optimal point. The potential field function is improved by adding the position relationship between the robot and the target point, and the gain of repulsive force is modified. The generation direction of the repulsive force is optimized. A new algorithm is proposed by fusing the improved two algorithms, and the potential field function of $A P F$ method is used to guide the search of the A* algorithm. The improved algorithms are compared in terms of path length, obstacle avoidance effect, and iteration times. The simulation results show that the improved algorithm proposed in this paper has high search efficiency and achieves obstacle avoidance while ensuring the optimal path of the calculation.

Key words: artificial potential field (APF) algorithm, A* algorithm, path planning, gravitational potential field, repulsive potential field

中图分类号:

TP391.9

余翔,姜陈,段思睿等 . 改进A*算法和人工势场法的路径规划[J]. 系统仿真学报, 2024, 36(3): 782-794.

Yu Xiang,Jiang Chen,Duan Sirui,et al . Path Planning for Improvement of A* Algorithm and Artificial Potential Field Method[J]. Journal of System Simulation, 2024, 36(3): 782-794.

图/表 16

图1

图2

图3

图4

图5

图6

图7

表1

初始化参数

参数	数值
斥力相关系数 $φ$	0.8
引力比例系数 $μ$	1.5
虚拟点引力系数 $ϕ$	0.5
障碍物碰撞范围 $ρ$	1.8
机器人与目标点的 $η$ 次方	0.5
仿真步长	0.1
最大迭代次数	500
障碍物数量	34或8
目标点位置	(23,24)

表1

图8

表2

图9

表3

图10

表4

表5

初始化参数

参数	数值
斥力相关系数 $φ$	0.75
引力比例系数 $μ$	1.5
虚拟点引力系数 $ϕ$	0.5
障碍物碰撞范围 $ρ$	2
机器人与目标点的 $η$ 次方	0.5
仿真步长	0.1
动态障碍物数量	7
静态障碍物数量	17
目标点位置	(10,10)

表5

图11

参考文献 20

1	张树生, 裴文良, 孙宁, 等. 消防灭火侦察机器人的研制与应用[J]. 制造业自动化, 2016, 38(6): 55-58.
	Zhang Shusheng, Pei Wenliang, Sun Ning, et al. Development and Application of Fire Fighting Reconnaissance Robot[J]. Manufacturing Automation, 2016, 38(6): 55-58.
2	Shakhatreh Hazim, Sawalmeh Ahmad H, Al-Fuqaha A, et al. Unmanned Aerial Vehicles (UAVs): A Survey on Civil Applications and Key Research Challenges[J]. IEEE Access, 2019, 7: 48572-48634.
3	Han Jinlu, Xu Yaojin, Di Long, et al. Low-cost Multi-UAV Technologies for Contour Mapping of Nuclear Radiation Field[J]. Journal of Intelligent & Robotic Systems, 2013, 70(1): 401-410.
4	杨艳红, 钟宝江, 田宏伟. DS-YOLOv4-tiny救援机器人目标检测模型[J]. 计算机仿真, 2022, 39(1): 387-393.
	Yang Yanhong, Zhong Baojiang, Tian Hongwei. Target Detection Model of DS-YOLOv4-tiny Rescue Robot[J]. Computer Simulation, 2022, 39(1): 387-393.
5	余翔, 邓千锐, 段思睿, 等. 一种多无人机协同优先覆盖搜索算法[J/OL]. 系统仿真学报. (2023-03-15) [2023-04-19]. .
	Yu Xiang, Deng Qianrui, Duan Sirui, et al. A Multi-UAV Cooperative Priority Coverage Search Algorithm[J/OL]. Journal of System Simulation. (2023-03-15) [2023-04-19]. .
6	林韩熙, 向丹, 欧阳剑, 等. 移动机器人路径规划算法的研究综述[J]. 计算机工程与应用, 2021, 57(18): 38-48.
	Lin Hanxi, Xiang Dan, Ouyang Jian, et al. Review of Path Planning Algorithms for Mobile Robots[J]. Computer Engineering and Applications, 2021, 57(18): 38-48.
7	Chhikara Prateek, Tekchandani Rajkumar, Kumar Neeraj, et al. DCNN-GA: A Deep Neural Net Architecture for Navigation of UAV in Indoor Environment[J]. IEEE Internet of Things Journal, 2021, 8(6): 4448-4460.
8	王东署, 赵红燕. 移动机器人动态避障的调节发育学习[J]. 控制与决策, 2023, 38(11): 3112-3120.
	Wang Dongshu, Zhao Hongyan. Motivated Developmental Learning of Mobile Robots in Dynamic Collision-avoidance[J]. Control and Decision, 2023, 38(11): 3112-3120.
9	Gao Fei, Wang Luqi, Zhou Boyu, et al. Teach-repeat-replan: A Complete and Robust System for Aggressive Flight in Complex Environments[J]. IEEE Transactions on Robotics, 2020, 36(5): 1526-1545.
10	Yang Xin, Chen Jingyu, Dang Yuanjie, et al. Fast Depth Prediction and Obstacle Avoidance on a Monocular Drone Using Probabilistic Convolutional Neural Network[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(1): 156-167.
11	Hong Dooyoung, Lee Seonhoon, Hoo Cho Young, et al. Energy-efficient Online Path Planning of Multiple Drones Using Reinforcement Learning[J]. IEEE Transactions on Vehicular Technology, 2021, 70(10): 9725-9740.
12	罗强, 王海宝, 崔小劲, 等. 改进人工势场法自主移动机器人路径规划[J]. 控制工程, 2019, 26(6): 1091-1098.
	Luo Qiang, Wang Haibao, Cui Xiaojin, et al. Autonomous Mobile Robot Path Planning Based on Improved Artificial Potential Method[J]. Control Engineering of China, 2019, 26(6): 1091-1098.
13	翁理国, 纪壮壮, 夏旻, 等. 基于改进多目标粒子群算法的机器人路径规划[J]. 系统仿真学报, 2014, 26(12): 2892-2898.
	Weng Liguo, Ji Zhuangzhuang, Xia Min, et al. Robot Path Planning Based on Improved Multi-objective Particle Swarm[J]. Journal of System Simulation, 2014, 26(12): 2892-2898.
14	江明, 王飞, 葛愿, 等. 基于改进蚁群算法的移动机器人路径规划研究[J]. 仪器仪表学报, 2019, 40(2): 113-121.
	Jiang Ming, Wang Fei, Ge Yuan, et al. Research on Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm[J]. Chinese Journal of Scientific Instrument, 2019, 40(2): 113-121.
15	Xiong Xiaoyong, Min Haitao, Yu Yuanbin, et al. Application Improvement of A^* Algorithm in Intelligent Vehicle Trajectory Planning[J]. Mathematical Biosciences and Engineering, 2021, 18(1): 1-21.
16	Montiel Oscar, Sepúlveda Roberto, Orozco-Rosas Ulises. Optimal Path Planning Generation for Mobile Robots Using Parallel Evolutionary Artificial Potential Field[J]. Journal of Intelligent & Robotic Systems, 2015, 79(2): 237-257.
17	Zhang Wei, Wei Shilin, Zeng Jia, et al. Multi-UUV Path Planning Based on Improved Artificial Potential Field Method[J]. International Journal of Robotics & Automation, 2021, 36(4): 231-239.
18	王彬, 聂建军, 李海洋, 等. 优化A^*与动态窗口法的移动机器人路径规划[J/OL]. 计算机集成制造系统. (2022-03-08) [2023-05-04]. .
	Wang Bin, Nie Jianjun, Li Haiyang, et al. Optimization of A^* and Dynamic Window Method for Mobile Robot Path Planning[J/OL]. Computer Integrated Manufacturing Systems. (2022-03-08) [2023-05-04]. .
19	Wu Zhengtian, Dai Jinyu, Jiang Baoping, et al. Robot Path Planning Based on Artificial Potential Field with Deterministic Annealing[J]. ISA Transactions, 2023, 138: 74-87.
20	周克帅, 范平清. 改进A^*算法与人工势场算法移动机器人路径规划[J]. 电子器件, 2021, 44(2): 368-374.
	Zhou Keshuai, Fan Pingqing. Improved A^* Algorithm and Artificial Potential Field Algorithm for Mobile Robot Path Planning[J]. Chinese Journal of Electron Devices, 2021, 44(2): 368-374.

图例	路径长度	迭代次数
图8 (a)	40.48	285
图8 (b)	35.13	231
图8 (c)	32.24	196

图例	路径长度
图9 (a)	未到达
图9 (b)	39.03
图9 (c)	34.24

图例	路径长度	迭代次数
图10 (a)	未到达	500
图10 (b)	42.69	313

[1]	李高扬, 黎向锋, 赵康, 金玉超, 易志东, 左敦稳. 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.
[2]	闫星宇, 李大焱, 王妮娅, 张凯翔, 毛剑琳. 带障碍物惩罚因子的多机器人路径规划[J]. 系统仿真学报, 2024, 36(3): 673-685.
[3]	庄鹤林, 夏小云, 李康顺, 陈泽丰, 张先超. 电动汽车路径规划模型与算法研究进展[J]. 系统仿真学报, 2024, 36(2): 320-337.
[4]	张国辉, 张雅楠, 高昂, 许奥宇. 空地异构无人系统侦察任务规划方法[J]. 系统仿真学报, 2024, 36(2): 497-510.
[5]	唐昀超, 祁少军, 朱立学, 卓献荣, 张芸齐, 孟繁. 移动机器人避障运动研究[J]. 系统仿真学报, 2024, 36(1): 1-26.
[6]	陈德峻, 方子豪, 曾云秀, 许凯. 战场迷雾中的欺骗路径规划[J]. 系统仿真学报, 2023, 35(9): 1895-1908.
[7]	李文静, 骆岩林, 王玉辉, 朱丽. 基于八叉树势场的鼻内镜虚拟导航路径规划[J]. 系统仿真学报, 2023, 35(9): 2054-2063.
[8]	林俊强, 王红军, 邹湘军, 张坡, 李承恩, 周益鹏, 姚书杰. 基于DPPO的移动采摘机器人避障路径规划及仿真[J]. 系统仿真学报, 2023, 35(8): 1692-1704.
[9]	杨来义, 毕敬, 苑海涛. 基于SAC算法的移动机器人智能路径规划[J]. 系统仿真学报, 2023, 35(8): 1726-1736.
[10]	曹梦龙, 赵文彬, 陈志强. 融合粒子群算法与改进灰狼算法的机器人路径规划[J]. 系统仿真学报, 2023, 35(8): 1768-1775.
[11]	杨海兰, 祁永强, 吴保磊, 荣丹, 洪妙英, 王军. 动态环境下基于忆阻强化学习的移动机器人路径规划[J]. 系统仿真学报, 2023, 35(7): 1619-1633.
[12]	宋大雷, 干文浩, 许嘤枝, 曲秀青, 曹江丽. 无人船实时路径规划与编队控制仿真研究[J]. 系统仿真学报, 2023, 35(5): 957-970.
[13]	吴玉文, 牛智越, 李珍萍. 基于改进遗传算法的货箱机器人拣选路径规划[J]. 系统仿真学报, 2023, 35(5): 1086-1097.
[14]	薛均晓, 孔祥燕, 董博威, 陶浩, 管海洋, 石磊, 徐明亮. 航母甲板上舰载机的混合避障和仿真[J]. 系统仿真学报, 2023, 35(3): 592-603.
[15]	张国辉, 王璇, 张雅楠, 高昂. 实际环境中多无人车协同路径规划模型研究[J]. 系统仿真学报, 2023, 35(2): 408-422.