A novel RRT*-based algorithm for motion planning in Dynamic environments

Abstract

Sampling-based motion planning has become a powerful framework for solving complex robotic motion-planning tasks. Despite the introduction of a multitude of algorithms, most of these deal with the static case involving non-moving obstacles. In this work, we are extending our memory efficient RRT*FN algorithm to dynamic scenarios. Specifically, we retain the useful parts of the tree (the data structure storing the motion plan information) after a dynamic obstacle invalidates the solution path. We then employ two greedy heuristics to repair the solution instead of running the whole motion planning process from scratch. We call this new algorithm, RRT*FN-Dynamic (RRT*FND). To compare our method to the state-of-the-art motion planners, RRT* and RRT*FN, we conducted an extensive set of benchmark experiments in dynamic environments using two robot models: a non-holonomic mobile robot and an industrial manipulator. The results of these experiments show that RRT*FND finds the solution path in shorter time in most of the cases and verifies the efficacy of it in dynamic settings.