On the heuristics of A* or A algorithm in ITS and robot path-planning

Abstract

Based on many large data set, we calibrate a near-optimal heuristic as a constant function for guiding efficiently A or A* algorithm. We claim that this magic number exists as a universal constant for several kinds of data sets. This is perhaps related to the nature of their data sets though it is not theoretically analyzed. In general A* and Dijkstra algorithms always pick up the optimal (e.g., the shortest) path between two nodes on a given graph. However, because they do not use any good heuristics, they spend much time to calculate. To overcome this drawback, we propose A of A* algorithm with a smart heuristics. The algorithm quickly investigates an optimal or near-optimal path. Unfortunately, the heuristics does not always maintain the admissibility, and thus our algorithm does not sometimes pick up the optimal path. Finally, we ascertain superiority of the proposed algorithm to the classic A* and Dijkstra algorithms by two kinds of extremely different data sets.