iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10586-024-04287-9
AAPF*: a safer autonomous vehicle path planning algorithm based on the improved A* algorithm and APF algorithm | Cluster Computing Skip to main content
Springer Nature Link
Log in

AAPF*: a safer autonomous vehicle path planning algorithm based on the improved A* algorithm and APF algorithm

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

In this paper, we introduce the AAPF* algorithm, an innovative approach that synergistically integrates the A-star search algorithm (A*) with the artificial potential field (APF) method. This algorithm is designed to enhance safety and ensure smoother global path planning for autonomous vehicles, particularly addressing vehicle cornering constraints. Initially, for augmenting the safety of autonomous vehicle, we implement an obstacle expansion strategy with a factor of 2 units, enhancing environmental adaptability. The study then delves into the classical A* algorithm, examining its core principles and characteristics, leading to the development of novel heuristic functions and search strategies that address the limitations inherent in the classic A* algorithm. Subsequently, we explore the APF algorithm, recognized for its excellence in obstacle avoidance in path planning. The paper culminates in the amalgamation of the APF’s repulsive field concept with the improved A* algorithm, crafting a comprehensive global planning algorithm tailored for autonomous vehicle path planning schemes. Experiments conducted in a simulated environment model validate the AAPF* algorithm’s efficacy in improving both the safety and smoothness, demonstrating its potential for real-world applications.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Data availability

Enquiries about data availability should be directed to the authors.

References

  1. Hussain, D., Khan, M.A., Abbas, S., et al.: Enabling smart cities with cognition based intelligent route decision in vehicles empowered with deep extreme learning machine. Comput. Mater. Contin 66, 141 (2021)

    Google Scholar 

  2. Gollapalli, M., Musleh, D., Ibrahim, N., et al.: A Neuro-Fuzzy Approach to Road Traffic Congestion Prediction. Comput. Mater. Contin. 73(1), 295 (2022)

    Google Scholar 

  3. Farkh, R., Alhuwaimel, S., Alzahrani, S., et al.: Deep Learning Control for Autonomous Robot. Comput. Mater. Contin. 72(2), 2811 (2022)

    Google Scholar 

  4. Zhan, H., Wan, D., Huang, Z.: On the responsible subjects of self-driving cars under the sae system: An improvement scheme. IEEE Int. Symp. Circuits Syst. (ISCAS) 2020, 1–5 (2020)

    Google Scholar 

  5. Anderson, J.M., Nidhi, K., Stanley, K.D., et al.: Autonomous vehicle technology: A guide for policymakers. Rand Corporation, Santa Monica (2014)

    Google Scholar 

  6. Yurtsever, E., Lambert, J., Carballo, A., et al.: A survey of autonomous driving: common practices and emerging technologies. IEEE Access 8, 58443–58469 (2020)

    Article  Google Scholar 

  7. Liu, J., Yang, J., Liu, H., et al.: An improved ant colony algorithm for robot path planning. Soft. Comput. 21, 5829–5839 (2017)

    Article  Google Scholar 

  8. Chai, R., Tsourdos, A., Gao, H., et al.: Dual-loop tube-based robust model predictive attitude tracking control for spacecraft with system constraints and additive disturbances. IEEE Trans. Industr. Electron. 69(4), 4022–4033 (2021)

    Article  Google Scholar 

  9. Kong, F., Guo, Y., Lyu, W.: Dynamics modeling and motion control of an new unmanned underwater vehicle. IEEE Access 8, 30119–30126 (2020)

    Article  Google Scholar 

  10. Wang, D., Zheng, S., Ren, Y., et al.: Path planning based on the improved RRT* algorithm for the mining truck. Comput. Mater. Contin. 71(2), 3571 (2022)

    Google Scholar 

  11. Dolgov, D., Thrun, S., Montemerlo, M., et al.: Path planning for autonomous vehicles in unknown semi-structured environments. Int. J. Robot. Res. 29(5), 485–501 (2010)

    Article  Google Scholar 

  12. Qu, Y., Zhang, Y., Zhang, Y.: A global path planning algorithm for fixed-wing UAVs. J. Intell. Rob. Syst. 91, 691–707 (2018)

    Article  Google Scholar 

  13. Zhang, Y., Chen, H., Waslander, S.L., et al.: Hybrid trajectory planning for autonomous driving in highly constrained environments. IEEE Access 6, 32800–32819 (2018)

    Article  Google Scholar 

  14. Schmid, L., Pantic, M., Khanna, R., et al.: An efficient sampling-based method for online informative path planning in unknown environments. IEEE Robot. Autom. Lett. 5(2), 1500–1507 (2020)

    Article  Google Scholar 

  15. Labakhua, L., Nunes, U., Rodrigues, R., et al.: Smooth trajectory planning for fully automated passengers vehicles: Spline and clothoid based methods and its simulation. Informatics in Control Automation and Robotics: Selected Papers from the International Conference on Informatics in Control Automation and Robotics 2006. Springer, Heidelberg, 169–182 (2008)

  16. Li, S., Wang, J.: Parallel parking path planning in narrow space based on a three-stage curve interpolation method. IEEE Access 11, 93841 (2023)

    Article  Google Scholar 

  17. Ziegler, J., Bender, P., Dang, T., et al.: Trajectory planning for Bertha—a local, continuous method. IEEE Intell. Vehicles Symp. Proc. IEEE 2014, 450–457 (2014)

    Google Scholar 

  18. Bergman, K., Ljungqvist, O., Axehill, D.: Improved path planning by tightly combining lattice-based path planning and optimal control. IEEE Trans. Intell. Vehicles 6(1), 57–66 (2020)

    Article  Google Scholar 

  19. Chai, R., Tsourdos, A., Savvaris, A., et al.: Six-DOF spacecraft optimal trajectory planning and real-time attitude control: a deep neural network-based approach. IEEE Trans. Neural Netw. Learn. Syst. 31(11), 5005–5013 (2019)

    Article  Google Scholar 

  20. Chai, R., Liu, D., Liu, T., et al.: Deep learning-based trajectory planning and control for autonomous ground vehicle parking maneuver. IEEE Trans. Autom. Sci. Eng. 20, 1633 (2022)

    Article  Google Scholar 

  21. Chai, R., Niu, H., Carrasco, J., et al.: Design and experimental validation of deep reinforcement learning-based fast trajectory planning and control for mobile robot in unknown environment. IEEE Trans. Neural Netw. Learn. Syst. (2022). https://doi.org/10.1109/TNNLS.2022.3209154

    Article  Google Scholar 

  22. Hwang, J.Y., Kim, J.S., Lim, S.S., et al.: A fast path planning by path graph optimization. IEEE Trans. Syst. Man Cybern. Part A: Syst. Humans 33(1), 121–129 (2003)

    Article  Google Scholar 

  23. Adnan, S., Abdulmuhsin, W.: The multi-point delivery problem: shortest path algorithm for real roads network using Dijkstra. J. Phys.: Conf. Ser. IOP Publ. 1530(1), 012040 (2020)

    Google Scholar 

  24. Stentz, A.: Optimal and efficient path planning for partially-known environments. Proc. IEEE Int. Conf. Robot. Autom. IEEE 1994, 3310–3317 (1994)

    Google Scholar 

  25. Qu, Y., Zhang, Y., Zhang, Y.: Optimal flight path planning for UAVs in 3-D threat environment. Int. Conf. Unmanned Aircr. Syst. (ICUAS) IEEE 2014, 149–155 (2014)

    Google Scholar 

  26. Ziegler, J., Stiller, C.: Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios. IEEE/RSJ Int. Conf. Intell. Robot. Syst. IEEE 2009, 1879–1884 (2009)

    Google Scholar 

  27. Werling, M., Kammel, S., Ziegler, J., et al.: Optimal trajectories for time-critical street scenarios using discretized terminal manifolds. Int. J. Robot. Res. 31(3), 346–359 (2012)

    Article  Google Scholar 

  28. McNaughton, M., Urmson, C., Dolan, J.M., et al.: Motion planning for autonomous driving with a conformal spatiotemporal lattice. IEEE Int. Conf. Robot. Autom. IEEE 2011, 4889–4895 (2011)

    Article  Google Scholar 

  29. Fan, H., Zhu, F., Liu, C., et al.: Baidu apollo em motion planner. Preprint arXiv:1807.08048 (2018)

  30. Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)

    Article  Google Scholar 

  31. Koenig, S., Likhachev, M., Furcy, D.: Lifelong planning A∗. Artif. Intell. 155(1–2), 93–146 (2004)

    Article  MathSciNet  Google Scholar 

  32. Ferguson, D., Stentz, A.: Using interpolation to improve path planning: the field D* algorithm. J. Field Robot. 23(2), 79–101 (2006)

    Article  Google Scholar 

  33. Nash, A., Koenig, S.: Any-angle path planning. AI Mag. 34(4), 85–107 (2013)

    Google Scholar 

  34. Likhachev, M., Gordon. G.J., Thrun, S.: ARA*: Anytime A* with provable bounds on sub-optimality. Advances in neural information processing systems 16 (2003)

  35. Likhachev, M., Ferguson, D.I., Gordon, G.J., et al.: Anytime dynamic A*: An anytime, replanning algorithm. ICAPS 5, 262–271 (2005)

    Google Scholar 

  36. Zhang, J., Wu, J., Shen, X., et al.: Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star. Int. J. Adv. Rob. Syst. 18(5), 17298814211042730 (2021)

    Google Scholar 

  37. Nilsson, N.J.: Artificial intelligence: a new synthesis. Morgan Kaufmann (1998)

  38. Huang, Y., Ding, H., Zhang, Y., et al.: A motion planning and tracking framework for autonomous vehicles based on artificial potential field elaborated resistance network approach. IEEE Trans. Industr. Electron. 67(2), 1376–1386 (2019)

    Article  Google Scholar 

  39. Likhachev, M., Ferguson, D.: Planning long dynamically feasible maneuvers for autonomous vehicles. Int J. Robot. Res 28(8), 933–945 (2009)

    Article  Google Scholar 

  40. Chai, R., Tsourdos, A., Chai, S., Xia, Y., Savvaris, A., Chen, C.L.P.: Multiphase overtaking maneuver planning for autonomous ground vehicles via a desensitized trajectory optimization approach. IEEE Trans. Industr. Inf. 19(1), 74–87 (2023). https://doi.org/10.1109/TII.2022.3168434

    Article  Google Scholar 

Download references

Funding

This work was supported by Science and Technology Innovation Key R&D Program of Chongqing (CSTB2023TIAD-STX0030),the National Key Research and Development Projects (SKLMT-ZZKT2022M09), the National Key Research and Development Program Intergovernmental International Science and Technology Innovation Cooperation Projects (2021YFE0193800), and the Chongqing Science and Technology Bureau Key Projects (CSTB2022TIAD-KPX0038).

Author information

Authors and Affiliations

  1. Chongqing University, Chongqing, 400030, China

    Yalian Yang & Xinyu Luo

  2. Oppo Communication Technology Co., Ltd, Wuhan, 430000, China

    Wei Li

  3. SERES Automotive Co., Ltd, Chongqing, 401335, China

    Changdong Liu & Peng Liang

  4. China Merchants Chongqing Communications Technology Research and Design Institute Co., Ltd, Chongqing, 400067, China

    Qing Ye

Authors
  1. Yalian Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xinyu Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wei Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Changdong Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Qing Ye
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Peng Liang
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed to the study conception and design. Study conception and design were performed by Yalian Yang and Xinyu Luo. The all drafts of the manuscript were written by Yalian Yang, Xinyu Luo, Wei Li and Changdong Liu. The all images of the manuscript were by Yalian Yang, Xinyu Luo, Wei Li, Changdong Liu, Qing Ye, Peng Liang. And all authors commented on previous versions of the manuscript.

Corresponding author

Correspondence to Yalian Yang.

Ethics declarations

Competing interests

The authors have not disclosed any competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yang, Y., Luo, X., Li, W. et al. AAPF*: a safer autonomous vehicle path planning algorithm based on the improved A* algorithm and APF algorithm. Cluster Comput 27, 11393–11406 (2024). https://doi.org/10.1007/s10586-024-04287-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-024-04287-9

Keywords

Search

Navigation