Welcome to Scholar Publishing Group

International Journal of Big Data Intelligent Technology, 2024, 5(1); doi: 10.38007/IJBDIT.2024.050113.

Improved A* Algorithm Based on Fused Theta Optimization

Author(s)

Tengsheng Yang, Huiheng Suo, Rui Rao, Jian Wu, Tao Sun, Xie Ma, Bibo Yu, Yingping Bai, Xiaoqin Li, Yuhan Sun, Xiushui Ma

Corresponding Author:
Jian Wu
Affiliation(s)

Nanchang Hangkong University, Nanchang, China

Abstract

In this paper, an improved A* algorithm based on fused Theta* is proposed. Firstly, the traditional search strategy of the A* algorithm is changed to a jumping search strategy, which intelligently determines which nodes need to be expanded and which nodes do not need to be expanded at each step of the expansion, based on the direction that the parent node is expanding from, and whether there is any obstacle and its location information around it, The idea of Theta* algorithm is also introduced to check whether the nodes in the final path can be directly connected, if so, the intermediate nodes are skipped and the intermediate path is pruned. The improved A* algorithm is then combined with the Bessel curve optimization algorithm to eliminate redundant inflection points in the robot's path, resulting in a smoother and near-optimal path. As analyzed by simulation experiments, compared to the traditional A* algorithm, the improved A* algorithm shortens the path length by 4.34%, reduces the computation time by 76.9%, and reduces the number of search nodes by 67.4%. The experimental results show that the fusion algorithm improves the efficiency of path planning, increases the stability and path smoothness, and is easier to apply in practice.

Keywords

Improved A*, Bezier curves, Jump point search, Theta*, Path planning

Cite This Paper

Tengsheng Yang, Huiheng Suo, Rui Rao, Jian Wu, Tao Sun, Xie Ma, Bibo Yu, Yingping Bai, Xiaoqin Li, Yuhan Sun, Xiushui Ma. Improved A* Algorithm Based on Fused Theta Optimization. International Journal of Big Data Intelligent Technology (2024), Vol. 5, Issue 1: 112-127. https://doi.org/10.38007/IJBDIT.2024.050113.

References

[1] Liu Y, Huang RY, Xiong QH. Robot path planning based on A* algorithm[J]. Automation and Instrumentation, 2015(4): 1-4.

[2] Jian Zhang, Liguo Liu, Wei Chen. Research on robot path planning based on Bessel curve[J]. Mechanical Design and Manufacturing, 2017(7): 61-64.

[3] Yongquan Wang, Robot path planning based on A* algorithm and Bessel curve [D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2018.

[4]Sujit, P. B., et al. "Path planning and optimization: a review." Journal of Mechanical Science and Technology 25.7 (2011): 1553-1563.

[5] R. Cao, Research on robot path planning based on A* algorithm and Bessel curve[J]. Automation and Instrumentation, 2016(1): 9-12.

[6]K. Karaman and E. Frazzoli. Sampling-Based Algorithms for Optimal Motion Planning. International Journal of Robotics Research, 30(7):846-894,. 2011.

[7] Qi Li, Jian Zhang, Research on robot path planning algorithm based on Bessel curve[J]. Robotics Technology and Application, 2017(1): 37-40.

[8] Tao Wang, Peiyi Xu, Robot path planning based on A* algorithm[J]. Computer and Modernization, 2015(10): 84-87.

[9] Zhen Liu, Robot path planning in unknown environment based on fuzzy logic[J]. Robotics Technology and Application, 2015(2):22-25.

[10]Gao Ming, Robot path planning in unknown environment based on ant colony algorithm[J]. Automation and Control, 2011(3): 23-26.

[11] Schiller, Ulf, et al. "Smooth paths for mobile robots using Bézier curves." Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003). IEEE, 2003.

[12] D. Fox, W. Burgard, and S. Thrun. The dynamic window approach to collision avoidance. IEEE Robotics & Automation Magazine, 4(1):23-33, 1997.

[13] state-of-the-art robot path planning techniques for unknown environments. in 2018 IEEE International Conference on Robotics and Biomimetics ( ROBIO) (pp. 28-33). 

[14] Qi Li. Robot path planning in unknown environment based on A* algorithm[J]. Robotics and Applications, 2018(1): 32-35.

[15]Nash, Alex, and Simon Chapuis. "Dynamic Path Smoothing for Mobile Robots using A* Path Planning. "Robotics and Autonomous Systems 123 (2020). 103340. 

[16] Pan Jianwei, Lidar technology and its application in UAV navigation and control [J]. Computer Science and Applications, 2014, 4(2): 163-171.

[17] Hess, Wolfgang, Damon Kohler, Holger Rapp, and Daniel Andor. "Real-time loop closure in 2D LIDAR SLAM." in 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 1271-1278. ieee, 2016.