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 o r d e r to 3 o r d e r 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 × 32 map. Furthermore, CBS-D* gives a superiority of self-adaptability and intelligence in unknown dynamic environments. [Display omitted] • A CBS-D* algorithm is presented for robot path planning in unknown environments. • This algorithm extends the incremental search range from 1order to 3order neighbors. • A collision avoidance mechanism and a wait and circuity strategy are presented. [ABSTRACT FROM AUTHOR]