Conflict-based search with D* lite algorithm for robot path planning in unknown dynamic environments

This study proposes a locally observable robot pathfinding algorithm, conflict-based search with D* lite (CBS-D*), to realize automatic and effective pathfinding in mixed environments with dynamic obstacles. This algorithm takes Manhattan distance as the heuristic function and extends the incremental search range from 1(order) to 3(order) neighbors. It presents a prejudgment mechanism of collision avoidance and investigates a wait and circuity strategy to promote pathfinding performance. Compared with the D* lite, the experimental results demonstrate that CBS-D* achieves a higher success rate and obstacle avoidance number, and a lower time step. By this collision avoidance mechanism, CBS-D* gives all successes in pathfinding in various dynamic environments, while D* lite may result in some failures. Specifically, CBS-D* has around 31% in the average success rate of pathfinding improved to D* lite in a 32 x 32 map. Furthermore, CBS-D* gives a superiority of self-adaptability and intelligence in unknown dynamic environments.