Rapidly Re-planning RRT* A Novel Re-Planning Algorithm

Abstract

Sampling based motion planning algorithms such as RRT* provide an optimal path from a start to goal point. However, any change in either of these points requires re-spawning of the tree from scratch or using a multi-query algorithm, both of which are time consuming options. An alternative is to re-use the existing tree to find path between the new start and goal points. A novel algorithm, Rapidly Re-planning RRT* [R4T*], is being presented here which caters for these requirements. R4T* builds a Smart-Graph using an existing RRT* tree to find optimal paths between any two points in the workspace. The graph can be developed from an existing RRT* tree or alongside one being built. The algorithm caters for a real-time environment, where the robot starts moving as soon as a path to goal is found. If the goal is changed at any stage, the algorithm yields a path from current position of the robot to the new goal. The path found has comparable cost to a 7000 node RRT* algorithm run for the same start and goal points. The research work thus presents an optimal re-planning algorithm which yields optimal real-time paths between any two points in the workspace with minimum computational overload.