Dynamic Region RRT Application to Kinodynamic Systems
Abstract
In the general motion planning problem the robot must satisfy basic constraints such as avoiding obstacles and remaining within the boundary of the environment. Kinodynamic motion planning is a type of planning where additional constraints must be satisfied. Kinodynamic planning is a more realistic planning problem as the robot must operate under constraints such as friction, gravity, velocity, and acceleration while avoiding obstacles as well. Sampling-based methods are often used to solve these types of problems. These methods generate robot configurations throughout the environment in order to eventually connect them to form a valid path from the start position to the goal. Rapidly-exploring Random Trees (RRT) are types of sampling-based methods that grow a tree from the start to goal. One important problem with these types of methods appears when planning in an environment with a narrow passage or cluttered space. In these problems it is unlikely to generate a sample in the narrow spaces and the robot does not explore these locations. Dynamic Region-biased Rapidly-exploring Random Trees (DRRRT) is a method that addresses these issues by guiding an RRT with dynamic sampling regions along an embedded graph of the workspace. DRRRT is effective in general motion planning problems, but faces issues in kinodynamic problems. Oftentimes, a sample is generated near an obstacle that is valid, but is found to be unrecoverable because if the robot were to move from that state with any of the available controls it would collide with an obstacle. This often occurs in environments with narrow spaces and tight turns such as a maze.
In this work, we aim to address the problems DRRRT faces in kinodynamic problems with a series of improvements. The resulting method is compared with other motion planning techniques on two kinodynamic problems consisting of a car-like robot navigating a grid-like city and a maze, simulating narrow paths with numerous turns.
Citation
Smith, Benjamin R (2018). Dynamic Region RRT Application to Kinodynamic Systems. Undergraduate Research Scholars Program. Available electronically from https : / /hdl .handle .net /1969 .1 /164553.