Adaptive Step-length RRT Algorithm for Improved Coverage

Abstract

This paper considers the problem of quickly identifying feasible paths in a congested environment. While there are many existing path planning algorithms, not many consider the problem of real-time replanning based on new information. As a robot moves through a given environment and new information becomes available, it is often beneficial to change the planned path to move towards a new location, for example, in target tracking applications. This paper studies a variation on the standard RRT algorithm that adapts the step size of the algorithm based on distance from the root node. This adaptive step-length RRT algorithm generates desirable paths for real-time applications that are precisely planned in the short planning horizon and coarsely planned in the longer planning horizon. These far-reaching coarse paths are generated quickly and provide a dynamic planner with more candidates when deciding on a particular path. This reach of the path is shown in this paper using a notation of coverage.