| dc.description.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.
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 address the address the problems DRRRT faces in the kinodynamic
problem with a series of improvements. First, we use the embedded graph to bias the
direction that the tree extends to keep the robot moving along the graph. Second, also
using the embedded graph we limit the candidates while neighborhood finding so that the
entire tree is not searched each time a sample is chosen. Lastly, instead of uniformly selecting
which region to be sampled, a bias is applied to the regions according to a heuristic
designed to promote more successful regions.
iii | en |
