A Comprehensive Survey and Analysis on Path Planning Algorithms and Heuristic Functions

Bin Yan, Tianxiang Chen, Xiaohui Zhu*, Yong Yue, Bing Xu, Kai Shi

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review

6 Citations (Scopus)


This paper explores the performance of four commonly used path planning algorithms of A*, D*, LPA* and D* Lite in both static and dynamic environments. To assess the effect of heuristic functions for path planning algorithms, four commonly used heuristic functions of Manhattan distance, diagonal distance, Euclidean distance and squared Euclidean distance are used based on three simulation environments with different map size and complexity. Experimental results show that the heuristic function significantly affects the computing performance and the final path of path planning algorithms, and Manhattan distance is the most efficiency heuristic function for all the four path planning algorithms. We apply A*, D*, LPA* and D* Lite algorithms to static and dynamic environments, respectively with different map size and complexity. We find that A* has the best performance in relatively simple static environments. When the map size and complexity of the static environment is highly increased, D* Lite is the best choice. In contrast, D* Lite has the best performance for path planning in dynamic environments. However, we also find that A* also has an excellent performance in dynamic environments when the map size and complexity are decreased.

Original languageEnglish
Title of host publicationIntelligent Computing - Proceedings of the 2020 Computing Conference
EditorsKohei Arai, Supriya Kapoor, Rahul Bhatia
Number of pages18
ISBN (Print)9783030522483
Publication statusPublished - 2020
EventScience and Information Conference, SAI 2020 - London, United Kingdom
Duration: 16 Jul 202017 Jul 2020

Publication series

NameAdvances in Intelligent Systems and Computing
Volume1228 AISC
ISSN (Print)2194-5357
ISSN (Electronic)2194-5365


ConferenceScience and Information Conference, SAI 2020
Country/TerritoryUnited Kingdom


  • A*
  • D*
  • D* Lite
  • Heuristic function
  • LPA*
  • Path planning
  • Path planning performance

Cite this