Path Planning Based on Improved Hybrid A* Algorithm
Bijun Tang, Kaoru Hirota, Xiangdong Wu, Yaping Dai, and Zhiyang Jia
School of Automation, Beijing Institute of Technology
No.5 Zhongguancun South Street, Haidian District, Beijing 100081, China
Hybrid A* algorithm has been widely used in mobile robots to obtain paths that are collision-free and drivable. However, the outputs of hybrid A* algorithm always contain unnecessary steering actions and are close to the obstacles. In this paper, the artificial potential field (APF) concept is applied to optimize the paths generated by the hybrid A* algorithm. The generated path not only satisfies the non-holonomic constraints of the vehicle, but also is smooth and keeps a comfortable distance to the obstacle at the same time. Through the robot operating system (ROS) platform, the path planning experiments are carried out based on the hybrid A* algorithm and the improved hybrid A* algorithm, respectively. In the experiments, the results show that the improved hybrid A* algorithm greatly reduces the number of steering actions and the maximum curvature of the paths in many different common scenarios. The paths generated by the improved algorithm nearly do not have unnecessary steering or sharp turning before the obstacles, which are safer and smoother than the paths generated by the hybrid A* algorithm for the autonomous ground vehicle.
-  M. Baumann, S. Léonard, E. A. Croft, and J. J. Little, “Path Planning for Improved Visibility Using a Probabilistic Road Map,” IEEE Trans. on Robotics, Vol.26, No.1, pp. 195-200, 2010.
-  M. Kothari and I. Postlethwaite, “A Probabilistically Robust Path Planning Algorithm for UAVs Using Rapidly-Exploring Random Trees,” J. of Intelligent & Robotic Systems, Vol.71, Issue 2, pp. 231-253, 2013.
-  Z. Zhu, E. Schmerling, and M. Pavone, “A Convex Optimization Approach to Smooth Trajectories for Motion Planning with Car-Like Robots,” Proc. of the 2015 54th IEEE Conf. on Decision and Control (CDC), pp. 835-842, 2015.
-  D. J. Webb and J. Van Den Berg, “Kinodynamic RRT*: Asymptotically Optimal Motion Planning for Robots with Linear Differential Dynamics,” Proc. of the 2013 IEEE Int. Conf. on Robotics and Automation, pp. 5054-5061, 2013.
-  J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, “Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic,” Proc. of the 2014 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 2997-3004, 2014.
-  A. V. Le, V. Prabakaran, V. Sivanantham, and R. E. Mohan, “Modified A-Star Algorithm for Efficient Coverage Path Planning in Tetris Inspired Self-Reconfigurable Robot with Integrated Laser Sensor,” Sensors, Vol.18, No.8, Article No.2585, 2018.
-  M. Likhachev, G. J. Gordon, and S. Thrun, “ARA*: Anytime A* with Provable Bounds on Sub-optimality,” Proc. of the 16th Int. Conf. on Neural Information Processing Systems, pp. 767-774, 2004.
-  D. Harabor and A. Grastien, “Online Graph Pruning for Pathfinding on Grid Maps,” Proc. of the 25th AAAI Conf. on Artificial Intelligence (AAAI’11), pp. 1114-1119, 2011.
-  D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, “Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments,” The Int. J. of Robotics Research, Vol.29, Issue 5, pp. 485-501, 2010.
-  K. Kurzer, “Path Planning in Unstructured Environments: A Real-time Hybrid A* Implementation for Fast and Deterministic Path Generation for the KTH Research Concept Vehicle,” Master Thesis, KTH Royal Institute of Technology, 2016.
-  J. A. Reeds and L. A. Shepp, “Optimal Paths for a Car That Goes Both Forwards and Backwards,” Pacific J. of Mathematics, Vol.145. No.2, pp. 367-393, 1990.
-  O. Khatib, “Real-time Obstacle Avoidance for Manipulators and Mobile Robots,” Proc. of the 1985 IEEE Int. Conf. on Robotics and Automation, pp. 500-505, 1985.
-  Z. Jin, B. Yan, and R. Ye, “The Flight Navigation Planning Based on Potential Field Ant Colony Algorithm,” Proc. of the 2018 Int. Conf. on Advanced Control, Automation and Artificial Intelligence (ACAAI 2018), pp. 200-204, 2018.
-  T. Weerakoon, K. Ishii, and A. A. F. Nassiraei, “An Artificial Potential Field Based Mobile Robot Navigation Method to Prevent from Deadlock,” J. of Artificial Intelligence and Soft Computing Research, Vol.5, No.3, pp. 189-203, 2015.
-  Z.-Z. Yu, J.-H. Yan, J. Zhao, Z.-F. Chen, and Y.-H. Zhu, “Mobile Robot Path Planning Based on Improved Artificial Potential Field Method,” J. of Harbin Institute of Technology, Vol.43, No.1, pp. 50-55, 2011 (in Chinese).
-  N. Zhang, Y. Zhang, C. Ma, and B. Wang, “Path Planning of Six-DOF Serial Robots Based on Improved Artificial Potential Field Method,” Proc. of the 2017 IEEE Int. Conf. on Robotics and Biomimetics (ROBIO), pp. 617-621, 2017.