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]	Li Gaoyang, Li Xiangfeng, Zhao Kang, Jin Yuchao, Yi Zhidong, Zuo Dunwen. Three-Dimensional Path Planning of UAV Based on All Particles Driving Wild Horse Optimizer Algorithm [J]. Journal of System Simulation, 2024, 36(3): 595-607.
[2]	Zhang Guohui, Zhang Ya'nan, Gao Ang, Xu Aoyu. Reconnaissance Mission Planning Method for Air-ground Heterogeneous Unmanned Systems [J]. Journal of System Simulation, 2024, 36(2): 497-510.
[3]	Tang Yunchao, Qi Shaojun, Zhu Lixue, Zhuo Xianrong, Zhang Yunqi, Meng Fan. Obstacle Avoidance Motion in Mobile Robotics [J]. Journal of System Simulation, 2024, 36(1): 1-26.
[4]	Chen Dejun, Fang Zihao, Zeng Yunxiu, Xu Kai. Deceptive Path Planning in Fog of War [J]. Journal of System Simulation, 2023, 35(9): 1895-1908.
[5]	Li Wenjing, Luo Yanlin, Wang Yuhui, Zhu Li. Virtual Navigation Path Planning Based on Octree Potential Field for Endonasal Endoscope [J]. Journal of System Simulation, 2023, 35(9): 2054-2063.
[6]	Junqiang Lin, Hongjun Wang, Xiangjun Zou, Po Zhang, Chengen Li, Yipeng Zhou, Shujie Yao. Obstacle Avoidance Path Planning and Simulation of Mobile Picking Robot Based on DPPO [J]. Journal of System Simulation, 2023, 35(8): 1692-1704.
[7]	Laiyi Yang, Jing Bi, Haitao Yuan. Intelligent Path Planning for Mobile Robots Based on SAC Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1726-1736.
[8]	Menglong Cao, Wenbin Zhao, Zhiqiang Chen. Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1768-1775.
[9]	Hailan Yang, Yongqiang Qi, Baolei Wu, Dan Rong, Miaoying Hong, Jun Wang. Path Planning of Mobile Robots Based on Memristor Reinforcement Learning in Dynamic Environment [J]. Journal of System Simulation, 2023, 35(7): 1619-1633.
[10]	Dalei Song, Wenhao Gan, Yingzhi Xu, Xiuqing Qu, Jiangli Cao. Simulation of Real-Time Path Planning and Formation Control for Unmanned Surface Vessel [J]. Journal of System Simulation, 2023, 35(5): 957-970.
[11]	Yuwen Wu, Zhiyue Niu, Zhenping Li. Picking Path Planning of Container Robots Based on Improved Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1086-1097.
[12]	Junxiao Xue, Xiangyan Kong, Bowei Dong, Hao Tao, Haiyang Guan, Lei Shi, Mingliang Xu. Obstacle Avoidance and Simulation of Carrier-Based Aircraft on the Deck of Aircraft Carrier [J]. Journal of System Simulation, 2023, 35(3): 592-603.
[13]	Guohui Zhang, Xuan Wang, Yanan Zhang, Ang Gao. Research on Cooperative Path Planning Model of Multiple Unmanned Vehicles in Real Environment [J]. Journal of System Simulation, 2023, 35(2): 408-422.
[14]	Yang Qingqing, Deng Minyi, Peng Yi. Urban UAV Path Planning Based on Improved Beetle Search Algorithm [J]. Journal of System Simulation, 2023, 35(12): 2527-2536.
[15]	Teng Li, Peipei Ding, Jinfang Liu. Multi-Stage Multi-AGV Path Planning with Walk under Shelves for Robotic Mobile Fulfillment Systems [J]. Journal of System Simulation, 2022, 34(7): 1512-1523.