Rapidly-exploring Random Trees (RRT) have become a foundational tool for solving high-dimensional motion planning problems in both static and dynamic environments. In this paper, we introduce a novel RRT algorithm designed specifically for dynamic settings. Most existing RRT* variants for dynamic environments rely on the robot’s current knowledge of obstacle positions and initiate replanning only after a collision risk is detected. This reactive strategy often leads to frequent replanning, which can be computationally expensive and result in longer paths. In contrast, our approach incorporates a general state prediction algorithm to estimate both current and future positions of moving obstacles. These predictions allow us to anticipate where obstacles are likely to appear in the configuration space and plan a motion that proactively avoids potential conflicts. Our RRT*-variant, PBRRT, modifies the traditional RRT* cost function to incorporate a measure of probabilistic feasibility. Simulation results demonstrate that PBRRT reduces path execution risk compared to other state-of-the-art algorithms.
Marey et al. (2026) studied this question.