Path Planning for Improvement of A* Algorithm and Artificial Potential Field Method

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

Abstract

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

CLC Number:

TP391.9

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

Figures/Tables 16

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Table 1

Initialization parameters

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

Table 1

Fig. 8

Table 2

Fig. 9

Table 3

Fig. 10

Table 4

Table 5

Initialization parameters

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

Table 5

Fig. 11

References 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]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[2]	Ni Peilong, Mao Pengjun, Wang Ning, Yang Mengjie. Robot Path Planning Based on Improved A-DDQN Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2420-2430.
[3]	Zhang Kaixiang, Mao Jianlin, Wang Niya, Xu Zhihao. Multi-robot Hierarchical Collaborative k-robust Path Planning for Path Interference [J]. Journal of System Simulation, 2025, 37(8): 2074-2088.
[4]	Wan Yuhang, Zhu Zilu, Zhong Chunfu, Liu Yongkui, Lin Tingyu, Zhang Lin. Dynamic Path Planning for Robotic Arms Based on an Improved PPO Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1462-1473.
[5]	Ye Chen, Shao Peng, Zhang Shaoping, Li Wenting, Zhou Tengming. Enhanced Artificial Gorilla Algorithm for Mobile Robot Path Planning [J]. Journal of System Simulation, 2025, 37(6): 1474-1485.
[6]	Zhang Yan, Li Binghua, Huo Tao, Liu Rong. Research on Robot Dynamic Obstacle Avoidance Method Based on Improved A* and Dynamic Window Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1555-1564.
[7]	Zhou Xiaohui, Li Yanqiang, Wang Yong, Zhao Decai, Yang Xiaoyao. Robot Path Planning Based on Ant Colony Algorithm with Dual Heuristic Information [J]. Journal of System Simulation, 2025, 37(5): 1280-1289.
[8]	Yu Die, Bao Baizhong, Si Yan, Duan Jian, Zhan Xiaobin, Shi Tielin. Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm [J]. Journal of System Simulation, 2025, 37(4): 1041-1050.
[9]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[10]	He Zhigang, Li Dayan, Wang Niya, Mao Jianlin, Wang Ning. A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode [J]. Journal of System Simulation, 2025, 37(4): 953-967.
[11]	Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction [J]. Journal of System Simulation, 2025, 37(3): 667-678.
[12]	Bai Yuxin, Chen Zhenya, Shi Ruitao, Su Weitao, Ma Zhuoqiang, Yang Shangjin. Research on Robot Path Planning Based on Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2025, 37(3): 742-752.
[13]	Jin Xu, Mo Yuanbin. Multi-strategy Hybrid Mountain Gazelle Optimizer for Robot Path Planning [J]. Journal of System Simulation, 2025, 37(3): 803-821.
[14]	Li Jiongyi, Li Qiang, Zhang Xinwen, Htet Zin Myo, Cai Yongbin. Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2025, 37(2): 498-507.
[15]	Peng Yi, Lei Yunkui, Yang Qingqing, Li Hui, Wang Jianming. Improved PID Search Algorithm for UAV Path Planning in Mountainous Environments [J]. Journal of System Simulation, 2025, 37(12): 3075-3086.