Path planning is a fundamental problem in the aspect of autonomous driving. A-star (A*) algorithm is a heuristic algorithm for path planning. However, there are two problems need to be solved in the traditional A-star algorithm: firstly, the tracking error caused by vehicle speed and vehicle size are not considered in path planning; secondly, the kinematics constraints of the vehicle itself and the smoothness of the path in the actual driving process are not considered. Therefore, this paper proposes an improved A-star algorithm to address the above deficiencies. By designing the collision cost heuristic function based on the position of obstacles, the vehicle contour and speed are considered and the vehicle safety is improved by setting a safe space around the vehicle, and establishing a steering cost heuristic function based on the control of heading angle difference, the vehicle dynamics constraints are satisfied, so as to improve the feasibility of path planning. The experimental results show that the improved A-star algorithm can avoid vehicle contours collision at different speeds and output a smoother path, and effectively generate higher quality path.
RobergeVTarbouchiMLabonteG.Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Trans Ind Inform2013; 9(1): 132–141.
2.
Besada-PortasEde la TorreLMorenoA, et al. On the performance comparison of multi-objective evolutionary UAV path planners. Inf Sci2013; 238: 111–125.
3.
FuYDingMZhouC.Phase angle-encoded and quantum-behaved particle swarm optimization applied to three-dimensional route planning for UAV, IEEE Trans Syst Man Cybern A Syst Hum2012; 42(2): 511–526.
4.
FuYDingMZhouC, et al. Route planning for unmanned aerial vehicle (UAV) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization, IEEE Trans Syst Man Cybern Syst2013; 43(6): 1451–1465.
5.
DuanHYuYZhangX, et al. Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm. Simul Model Pract Theory2010; 18(8): 1104–1115.
6.
DuanHBZhangXYWuJ, et al. Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments. J Bionic Eng2009; 6: 161–173.
7.
GigrasYGuptaK.Artificial intelligence in robot path planning. Int J Soft Comput Eng2012; 2(2): 71–474.
SombolestanSMRasooliAKhodayganS.Optimal path-planning for mobile robots to find a hidden target in an unknown environment based on machine learning. J Ambient Intell Humaniz Comput2019; 10(5): 1841–1850.
10.
HartPNilssonNRaphaelB.A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern1968; 4(2): 100–107.
11.
StentzA.Optimal and efficient path planning for partially known environments. In: HebertMHThorpeCStentzA (eds) Intelligent unmanned ground vehicles. Autonomous navigation research at Carnegie Mellon. Boston, MA: Springer US, 1997, pp.203–220.
12.
DijkstraEW.A note on two problems in connexion with graphs. Numer Math1959; 1(1): 269–271.
13.
JailletLCortésJSiméonT.Sampling-based path planning on configuration-space costmaps. IEEE Trans Robot2010; 26(4): 635–646.
14.
JeongIBLeeSJKimJH.Quick-RRT*: triangular inequality-based implementation of RRT* with improved initial solution and convergence rate. Expert Syst Appl2019; 123: 82–90.
15.
KuffnerJJLavalleSM.RRT-Connect: an efficient approach to single-query path planning. In: Proceedings 2000 ICRA. Millennium conference. IEEE international conference on robotics and automation. Symposia proceedings (Cat. No.00CH37065), San Francisco, CA, 24–28 April 2000, pp. 995–1001. New York: IEEE.
FanCChenWXiY.Hopfield neural networks for path planning in dynamic and unknown environments. Control Theory and Applications2004; 21(3): 345–350.
18.
GarciaMAPMontielOCastilloO, et al. Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation. Appl Soft Comput2009; 9(3): 1102–1110.
19.
MohantaJCParhiDRPatelSK.Path planning strategy for autonomous mobile robot navigation using Petri-GA optimisation. Comput Electr Eng2011; 37(6): 1058–1070.
20.
HartPENilssonNJRaphaelB. Correction to “A formal basis for the heuristic determination of minimum cost paths.”IEEE Trans Syst Sci Cybern1972; 4(2): 28–29.
21.
PollackMWiebensonW.Solutions of the shortest-route problem—a review. Oper Res1960; 8(2): 224–230.
22.
SamuelAL.Some studies in machine learning using the game of checkers. II—recent progress. In: LevyDNL (ed.) Computer Games I. New York, NY: Springer, 1988.
23.
LengXSunG.Asynchronous parallelism weighted A* algorithm for the finding shortest path on road networks. J Univ Sci Technol China2014; 44: 867–873.
IslamFNarayananVLikhachevM.Dynamic multi-heuristic A*. In: Proceedings - IEEE international conference on robotics and automation, Seattle, WA, 26–30 May 2015, pp. 2376–2382, 2152–4092.
LuanPGThinhNT.Real-time hybrid navigation system-based path planning and obstacle avoidance for mobile robots. Appl Sci2020; 10: 3355.
28.
FuBChenLZhouY, et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length. Robot Auton Syst2018; 106: 26–37.
29.
da Silva CostaLTonidandelF. DVG+A* and RRT path-planners: a comparison in a highly dynamic environment. J Intell Robot Syst2021; 101(3).
30.
LiuZLiuHLuZ, et al. A dynamic fusion path finding algorithm using delaunay triangulation and improved A-star for mobile robots (January 2021). IEEE Access2021; 99: 1–1.
31.
TangGTangCClaramuntC, et al. Geometric A-star algorithm: an improved A-star algorithm for AGV path planning in a port environment. IEEE Access2021; 9(99): 59196–59210.
32.
ShijuPHuaLZhiyuanS, et al. Trajectory tracking method for intelligent vehicles based on tracking-error model. Automotive engineering. Chin Autom Congr2019; 41(9): 7.
33.
SunCZhangXZhouQ, et al. A model predictive controller with switched tracking error for autonomous vehicle path tracking. IEEE Access2019; 7(99): 53103–53114.
34.
GuoHLiuJCaoD, et al. Dual-envelop-oriented moving horizon path tracking control for fully automated vehicles. Mechatronics2018; 50: 422–433.
35.
WangRLiYFanJ, et al. A Novel pure pursuit algorithm for autonomous vehicles based on Salp Swarm Algorithm and velocity controller. IEEE Access2020; 8: 166525–166540.
36.
WangRJingHHuC, et al. Robust H-infinity path following control for autonomous ground vehicles with delay and data dropout. IEEE Trans Intell Transp Syst2016; 17(7): 2042–2050.
37.
XuSPengH.Design, analysis, and experiments of preview path tracking control for autonomous vehicles. IEEE Trans Intell Transp Syst2020; 21: 48–58.
38.
PaeDSKimGHKangTK, et al. Path planning based on obstacle-dependent Gaussian model predictive control for autonomous driving. Appl Sci2021; 11: 3703.
39.
SangeethaVKrishankumarRRavichandranKS, et al. A fuzzy gain-based dynamic ant colony optimization for path planning in dynamic environments. Symmetry2021; 13: 280.
40.
NagyACsorvasiGKissD. Path planning and control of differential and car-like robots in narrow environments. In: 2015 IEEE 13th International Symposium on Applied Machine Intelligence and Informatics (SAMI), Herl’any, Slovakia, 22–24 January 2015, pp. 103–108. New Yok: IEEE.
41.
LaghmaraHBoudaliMTLaurainT, et al. Obstacle avoidance, path planning and control for autonomous vehicles. In: 2019 IEEE intelligent vehicles symposium (IV), Paris, France, 9–12 June 2019, pp. 529–534. New Yok: IEEE.
42.
LiBDuHLiW, et al. Dynamically integrated spatiotemporal-based trajectory planning and control for autonomous vehicles. IET Intell Transp Syst2018; 12: 1271–1282.
43.
ZhangGChengSShuJ, et al. Accelerating breadth-first graph search on a single server by dynamic edge trimming. J Parallel Distr Comput2018; 120: 383–394.
MartinTCOrchardMESánchezPV.Design and simulation of control strategies for trajectory tracking in an autonomous ground vehicle. IFAC Proc Volumes2013; 46(24): 118–123.
