A Kinematics-Constrained Grid-Based Path Planning Algorithm for Autonomous Parking
Source abstract
Abstract
This paper presents a kinematics-constrained grid-based path planning algorithm that generates real-time, safe, and executable trajectories, thereby enhancing the performance and reliability of autonomous vehicle parking systems. The grid resolution adapts to the minimum turning radius and steering limits, ensuring feasible motion primitives. The cost function integrates path efficiency, direction-switching penalties, and collision risk to ensure smooth and feasible maneuvers. A cubic spline refinement produces curvature-continuous trajectories suitable for vehicle execution. Simulation and experimental results demonstrate that the proposed method achieves collision-free and curvature-bounded paths with significantly reduced computation time and improved maneuver smoothness compared with conventional A* and Hybrid A*. In both structured and dynamic parking environments, the planner consistently maintained safe clearance and stable tracking performance under variations in vehicle geometry and velocity. These results confirm the robustness and real-time feasibility of the proposed approach, effectively unifying kinematic feasibility, safety, and computational efficiency for practical autonomous parking systems.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · Robotics and Sensor-Based Localization · Control and Dynamics of Mobile Robots
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Mechatronics Engineering, Changwon National University, Changwon 51140, Republic of Korea
Funding
Regional Innovation System & Education(RISE) program through the RISE Center, Gyeongsangnam-do · Ministry of Education(MOE) and the Gyeongsangnam-do Provincial Government, Republic of Korea · Global-Learning & Academic research institution for Master’s PhD students, and Postdocs(LAMP) Program of the National Research Foundation of Korea(NRF) grant funded by the Ministry of Education
References (48)
Show source-provided references
1. Parking policies in six continents: Mixed outcomes and multifaceted barriers to reform
2. The High Cost of Free Parking10.1177/0739456X9701700102 ↗
3. Olmos Medina, J.S., Maradey Lázaro, J.G., Rassõlkin, A., and González Acuña, H. (2025). An Overview of Autonomous Parking Systems: Strategies, Challenges, and Future Directions. Sensors, 25.10.3390/s25144328 ↗
4. Less workplace parking with fully autonomous vehicles?10.1108/JICV-07-2022-0029 ↗
5. Arasawa, K., Hoshi, Y., and Oya, H. (2024, January 8–10). A Path Planning Method for Automated Parking Systems Based on Circular Arcs and Lines with Smoothly Curves. Proceedings of the 2024 IEEE 3rd Industrial Electronics Society Annual On-Line Conference (ONCON), Online.10.1109/ONCON62778.2024.10931450 ↗
6. Ma, J., and Qian, Y. (2025). Research on Vertical Parking Path Planning Based on Circular Arcs, Straight Lines, and Multi-Objective Evaluation Function. World Electr. Veh. J., 16.10.3390/wevj16030152 ↗
7. Qin, Y., Liu, F., and Wang, P. (2019, January 20–22). A Feasible Parking Algorithm in Form of Path Planning and Following. Proceedings of the 2019 International Conference on Robotics, Intelligent Control and Artificial Intelligence, Shanghai, China.10.1145/3366194.3366196 ↗
8. Autonomous driving parking robot systems for urban environmental benefit evaluation10.1016/j.jclepro.2024.143215 ↗
9. Hamad, L., Khan, M.A., Menouar, H., Filali, F., and Mohamed, A. (2024, January 5–8). Haris: An advanced autonomous mobile robot for smart parking assistance. Proceedings of the 2024 IEEE International Conference on Consumer Electronics (ICCE), Las Vegas, NV, USA.10.1109/ICCE59016.2024.10444311 ↗
10. Enhancing the efficiency of charging & parking processes for Autonomous Mobile Robot fleets: A simulative evaluation10.1016/j.jpowsour.2021.230894 ↗
11. Alarabi, S., Luo, C., and Santora, M. (2022, January 18–20). A PRM approach to path planning with obstacle avoidance of an autonomous robot. Proceedings of the 2022 8th International Conference on Automation, Robotics and Applications (ICARA), Prague, Czech.10.1109/ICARA55094.2022.9738559 ↗
12. Parallelization of Probabilistic RoadMap for Generating UAV Path on a DTED Map
13. Probabilistic roadmaps for path planning in high-dimensional configuration spaces10.1109/70.508439 ↗
14. Li, Q., Xu, Y., Bu, S., and Yang, J. (2022). Smart vehicle path planning based on modified PRM algorithm. Sensors, 22.10.3390/s22176581 ↗
15. Suh, H.J., Deacon, J., and Wang, Q. (2025, July 21). A Fast PRM Planner for Car-like Vehicles. Available online: https://hjrobotics.net/wp-content/uploads/2018/10/A-Fast-PRM-Planner-for-Car-like-Vehicles.pdf.
16. Chen, J., Ma, R., Lu, C., and Deng, Y. (2025). Autonomous Parking Path Planning Method for Intelligent Vehicles Based on Improved RRT Algorithm. World Electr. Veh. J., 16.10.3390/wevj16070374 ↗
17. LaValle, S. (1998). Rapidly-Exploring Random Trees: A New Tool for Path Planning. Res. Rep. 9811, Available online: https://api.semanticscholar.org/CorpusID:14744621.
18. Solmaz, S., Muminovic, R., Civgin, A., and Stettinger, G. (2021, January 19–22). Development, analysis, and real-life benchmarking of rrt-based path planning algorithms for automated valet parking. Proceedings of the 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), Indianapolis, IN, USA.10.1109/ITSC48978.2021.9564413 ↗
19. Wang, Y., Jha, D.K., and Akemi, Y. (2017, January 20–23). A two-stage RRT path planner for automated parking. Proceedings of the 2017 13th IEEE conference on automation science and engineering (CASE), Xi’an, China.10.1109/COASE.2017.8256153 ↗
20. Zheng, K., and Liu, S. (2018, January 25–27). RRT based path planning for autonomous parking of vehicle. Proceedings of the 2018 IEEE 7th Data Driven Control and Learning Systems Conference (DDCLS), Enshi, China.10.1109/DDCLS.2018.8515940 ↗
21. Vlasak, J., Sojka, M., and Hanzálek, Z. (2025). Improving rapidly-exploring random trees algorithm for automated parking in real-world scenarios. J. Intell. Transp. Syst., in press.10.1080/15472450.2025.2548297 ↗
22. Smart indoor parking system based on dijkstra’s algorithm
23. Dijkstra, E.W. (2022). A note on two problems in connexion with graphs. Edsger Wybe Dijkstra: His Life, Work, and Legacy, Association for Computing Machinery.10.1145/3544585.3544600 ↗
24. Junehong, P., Hyewon, J., Dongmahn, S., and Soobin, J. (2022, January 19–21). 3D LiDAR based Localization and Dijkstra’s Algorithm-Based Path Planning. Proceedings of the 24th Korea Conference on Software Engineering (KCSE), Pyeongchang, Gangwon, Republic of Korea.
25. Wang, H., Zhang, F., and Cui, P. (2017, January 20–22). A parking lot induction method based on Dijkstra algorithm. Proceedings of the 2017 Chinese Automation Congress (CAC), Jinan, China.10.1109/CAC.2017.8243712 ↗
26. Yu, L., Jiang, H., and Hua, L. (2019). Anti-congestion route planning scheme based on Dijkstra algorithm for automatic valet parking system. Appl. Sci., 9.10.3390/app9235016 ↗
27. Chen, K.Y. (2022). An improved A* search algorithm for road networks using new heuristic estimation. arXiv.
28. A Pathfinding Algorithm Using Path Information10.7583/JKGS.2013.13.1.31 ↗
29. A formal basis for the heuristic determination of minimum cost paths10.1109/TSSC.1968.300136 ↗
30. Kabir, R., Watanobe, Y., Islam, M.R., and Naruse, K. (2024). Enhanced robot motion block of a-star algorithm for robotic path planning. Sensors, 24.10.3390/s24051422 ↗
31. A Study on A* Algorithm Applying Reversed Direction Method for High Accuracy of the Shortest Path Searching10.12815/kits.2013.12.6.001 ↗
32. Zhao, Y. (2024). Automated Parking Planning with Vision-Based BEV Approach. arXiv.
33. Theta*: Any-angle path planning on grids10.1613/jair.2994 ↗
34. Harabor, D., and Grastien, A. (2011, January 7–11). Online graph pruning for pathfinding on grid maps. Proceedings of the AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.10.1609/aaai.v25i1.7994 ↗
35. Acernese, A., Borrello, G., Lorusso, L., and Basso, M. (2024, January 25–28). Informed Hybrid A Star-based Path Planning Algorithm in Unstructured Environments. Proceedings of the 2024 European Control Conference (ECC), Stockholm, Sweden.10.23919/ECC64448.2024.10590977 ↗
36. Beomseong, C., Seungwon, C., Jaeun, R., and Kunsoo, H. (2022, January 16–19). Multi-Agent Path Planning Using Hybrid A* and Reinforcement Learning. Proceedings of the KSAE 2022 Annual Autumn Conference & Exhibition, Jeju, Republic of Korea.
37. Chang, T., and Tian, G. (2024). Hybrid A-Star path planning method based on hierarchical clustering and trichotomy. Appl. Sci., 14.10.3390/app14135582 ↗
38. Dolgov, D., Thrun, S., Montemerlo, M., and Diebel, J. (2008, January 13–14). Practical search techniques in path planning for autonomous driving. Proceedings of the First International Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR-08), Chicago, IL, USA.
39. Path planning for autonomous vehicles in unknown semi-structured environments10.1177/0278364909359210 ↗
40. Sedighi, S., Nguyen, D.-V., and Kuhnert, K.-D. (2019, January 19–22). Guided hybrid A-star path planning algorithm for valet parking applications. Proceedings of the 2019 5th International Conference on Control, Automation and Robotics (ICCAR), Beijing, China.10.1109/ICCAR.2019.8813752 ↗
41. Xiong, L., Gao, J., Fu, Z., and Xiao, K. (2021, January 29–31). Path planning for automatic parking based on improved Hybrid A* algorithm. Proceedings of the 2021 5th CAA International Conference on Vehicular Control and Intelligence (CVCI), Tianjin, China.10.1109/CVCI54083.2021.9661197 ↗
42. Hua, Y., Li, Z., Wu, H., Zhang, M., and Sun, H. (2023, January 6–8). Parking path planning of autonomous vehicle based on B-spline curve. Proceedings of the Ninth International Symposium on Sensors, Mechatronics, and Automation System (ISSMAS 2023), Xiamen, China.10.1117/12.3014949 ↗
43. Likhachev, M., Gordon, G.J., and Thrun, S. (2003, January 9–11). ARA*: Anytime A* with provable bounds on sub-optimality. Proceedings of the 17th International Conference on Neural Information Processing Systems, Whistler, BC, Canada.
44. Automated parking trajectory planning: A hybrid curve search and nonlinear optimisation approach10.1080/23335777.2024.2385910 ↗
45. Veerapaneni, R., Saleem, M.S., and Likhachev, M. (2023, January 8–13). Learning local heuristics for search-based navigation planning. Proceedings of the International Conference on Automated Planning and Scheduling, Prague, Czech Republic.10.1609/icaps.v33i1.27245 ↗
46. Wang, X., Li, G., and Bian, Z. (2025). Research on the A* Algorithm Based on Adaptive Weights and Heuristic Reward Values. World Electr. Veh. J., 16.10.3390/wevj16030144 ↗
47. Takehara, R., and Gonsalves, T. (2021, January 23–25). Autonomous Car Parking System using Deep Reinforcement Learning. Proceedings of the 2021 2nd International Conference on Innovative and Creative Information Technology (ICITech), Salatiga, Indonesia.10.1109/ICITech50181.2021.9590169 ↗
48. Xu, X., Xie, Y., Li, R., Zhao, Y., Song, R., and Zhang, W. (2024, January 10–14). Hierarchical Reinforcement Learning for Autonomous Parking Based on Kinematic Constraints. Proceedings of the 2024 IEEE International Conference on Robotics and Biomimetics (ROBIO), Bangkok, Thailand.10.1109/ROBIO64047.2024.10907532 ↗