27-05-2014, 02:42 PM
Real-Time Randomized Path Planning for Robot Navigation
Real-Time Randomized.pdf (Size: 378.51 KB / Downloads: 18)
Abstract
Mobile robots often find themselves in a situation
where they must find a trajectory to another po-
sition in their environment, subject to constraints
posed by obstacles and the capabilities of the robot
itself. This is the problem of planning a path through
a continuous domain, for which several approaches
have been developed. Each has some limitations how-
ever, including requiring state discretizations, steep
efficiency vs. accuracy tradeoffs, or the difficulty
of adding interleaved execution. Rapidly-Exploring
Random Trees (RRTs) are a recently developed rep-
resentation on which fast continuous domain path
planners can be based. In this work, we build a path
planning system based on RRTs that interleaves plan-
ning and execution, first evaluating it in simulation
and then applying it to physical robots. Our planning
algorithm, ERRT (execution extended RRT), intro-
duces two novel extensions of previous RRT work,
the waypoint cache and adaptive cost penalty search,
which improve replanning efficiency and the quality
of generated paths.
Introduction
The path-planning problem is as old as mobile
robots, but is not one that has found a universal
solution. Specifically, in complicated, fast evolving
environments such as RoboCup [3], currently popu-
lar approaches to path-planning have their strengths,
but still leave much to be desired. In particular, most
require a state discretization and are best suited for
domains with relaxed time constraints for planning.
One of the relatively recently developed tools that
may help tackle the problem of real-time path plan-
ning are Rapidly-exploring random trees (RRTs) [7].
RRTs employ randomization to explore large state
spaces efficiently, and can form the basis for a prob-
abilistically complete though non-optimal kinody-
namic path planner [8]. Their strengths are that
they can efficiently find plans in high dimensional
spaces because they avoid the state explosion that
discretization faces. Furthermore, due to their incre-
mental nature, they can maintain complicated kine-
matic constraints if necessary. A basic planning al-
gorithm using RRTs is as follows: Start with a trivial
tree consisting only of the initial configuration.
Conclusion
In this work a robot control system was developed
that used an RRT path planner to turn a simple
reactive scheme into a high performance path plan-
ning system. The novel mechanisms of the waypoint
cache and adaptive beta search were introduced, with
the waypoint cache providing much improved perfor-
mance on difficult but possible path planning prob-
lems. The real robot was able to perform better than
previous fully reactive schemes, traveling 40% faster
while avoiding obstacles, and drastically reducing os-
cillation and local minima problems that the reactive
scheme had. This is also the first application of which
we are aware using an RRT-based path planner on a
real mobile robot.