TITLE:
An Intelligent Bi-Directional Parallel B* Routing Algorithm
AUTHORS:
Xueyu Zhang, Caihong Li
KEYWORDS:
B* Algorithm, Path Planing, Parallel
JOURNAL NAME:
Journal of Computer and Communications,
Vol.8 No.7,
June
30,
2020
ABSTRACT: Pathfinding is a kind of problem widely used in daily life. It is widely used in network games, map navigation and other fields. However, the traditional A* algorithm has some shortcomings, such as heuristic function needs to be designed according to different problems, path has many inflection points, and algorithm stability is poor. B* algorithm also has the shortcoming of inaccurate pathfinding. In order to solve the problems existing in A* and B* algorithms, obstacle avoidance regeneration mechanism, pre-exploration mechanism and equivalent waiting strategy are proposed. It adds a bidirectional parallel search mechanism to form an IBP-B* algorithm (Intelligent bi-directional parallel B* routing algorithm). The simulation results show that the speed of IBP-B* algorithm is 182% higher than that of A* algorithm and 366% higher than that of BFS algorithm. Meanwhile, compared with B* algorithm, IBP-B* algorithm improves the pathfinding accuracy of the algorithm.