30-07-2012, 04:43 PM
Finding Narrow Passages with Probabilistic Roadmaps: The Small Step Retraction Method
[attachment=29592]
INTRODUCTION
Probabilistic Roadmaps (PRM) are an effective approach
to plan collision-free paths for articulated robots and virtual
characters in geometrically complex environments [1, 2, 8, 15,
16, 18, 24]. A PRM planner samples robot configurations at
random with some probabilistic distribution and retains the
collision-free ones as nodes – called milestones – of a graph
(the roadmap). It connects each milestone to a small number
of neighboring milestones by local paths (usually, straight-line
segments in configuration space) and retains collision-free
connections as the roadmap edges. Sampled configurations
and connections between milestones are tested using an
efficient collision checker [7, 9, 20, 21]. In this way, the PRM
planner avoids the prohibitive cost of computing a complete
representation of the robot’s (collision-)free space F.
RELATED WORK
Neither the notion of a narrow passage, nor its impact on
PRM planning is straightforward. In [17], the clearance of a
path is used to estimate planning time. However, path
clearance incompletely characterizes narrow passages. A more
thorough analysis yields the notion of the expansiveness of
free space F, which was used to provide tighter bounds on the
convergence of a PRM planner [15].
Several milestones sampling strategies have been used to
alleviate the narrow-passage issue. Two types of strategies –
filtering and retraction strategies – explicitly address this
issue.
PRELIMINARY OBSERVATIONS
Several components of our small-step retraction method
were suggested by observations made during preliminary tests
in 2-D configuration spaces. These observations were later
confirmed by our experiments with SSRP (Section VI). For
lack of space, we only report here on one key observation.
Consider the example in Fig. 1(a). The robot R is a disc
(shown red) of radius r. Its configuration is defined by its
center’s coordinates. The start and goal configurations are s
and g, respectively. The obstacles create a long and jaggy
narrow passage of width w that the robot must traverse to
reach g from s. The figure shows the robot’s workspace, but
the configuration space is also 2-D, with similar geometry.
The passage’s width in configuration space is w-2r.
SMALL-STEP RETRACTION PLANNER
SSRP uses the pre-existing SBL planner [23] as a building
block, but we could have used almost any other single-query
PRM planner as well. SSRP combines two algorithms (each
calling SBL). OPTIMIST, which is very fast, but not fully
reliable, is invoked first. If it fails to find a path, then
PESSIMIST, a slower but more reliable algorithm, is invoked.
CONCLUSION
The main contribution of this paper is a new retraction
method – small-step retraction – that helps PRM planners find
paths through narrow passages. The core idea underlying this
method is that retracting sampled configurations that are
barely colliding is sufficient to speed up the generation of
roadmap milestones within narrow passages. Barely colliding
configurations are relatively easy to retract out of collision. In
addition, they can be efficiently identified by running a
classical collision checker on thinned geometric models precomputed
using a medial-axis-based technique. A slight
drawback of the method is that it increases pre-computation
time. Another idea of our work is the combination of two
algorithms, OPTIMIST and PESSIMIST, which complement
each other well.
[attachment=29592]
INTRODUCTION
Probabilistic Roadmaps (PRM) are an effective approach
to plan collision-free paths for articulated robots and virtual
characters in geometrically complex environments [1, 2, 8, 15,
16, 18, 24]. A PRM planner samples robot configurations at
random with some probabilistic distribution and retains the
collision-free ones as nodes – called milestones – of a graph
(the roadmap). It connects each milestone to a small number
of neighboring milestones by local paths (usually, straight-line
segments in configuration space) and retains collision-free
connections as the roadmap edges. Sampled configurations
and connections between milestones are tested using an
efficient collision checker [7, 9, 20, 21]. In this way, the PRM
planner avoids the prohibitive cost of computing a complete
representation of the robot’s (collision-)free space F.
RELATED WORK
Neither the notion of a narrow passage, nor its impact on
PRM planning is straightforward. In [17], the clearance of a
path is used to estimate planning time. However, path
clearance incompletely characterizes narrow passages. A more
thorough analysis yields the notion of the expansiveness of
free space F, which was used to provide tighter bounds on the
convergence of a PRM planner [15].
Several milestones sampling strategies have been used to
alleviate the narrow-passage issue. Two types of strategies –
filtering and retraction strategies – explicitly address this
issue.
PRELIMINARY OBSERVATIONS
Several components of our small-step retraction method
were suggested by observations made during preliminary tests
in 2-D configuration spaces. These observations were later
confirmed by our experiments with SSRP (Section VI). For
lack of space, we only report here on one key observation.
Consider the example in Fig. 1(a). The robot R is a disc
(shown red) of radius r. Its configuration is defined by its
center’s coordinates. The start and goal configurations are s
and g, respectively. The obstacles create a long and jaggy
narrow passage of width w that the robot must traverse to
reach g from s. The figure shows the robot’s workspace, but
the configuration space is also 2-D, with similar geometry.
The passage’s width in configuration space is w-2r.
SMALL-STEP RETRACTION PLANNER
SSRP uses the pre-existing SBL planner [23] as a building
block, but we could have used almost any other single-query
PRM planner as well. SSRP combines two algorithms (each
calling SBL). OPTIMIST, which is very fast, but not fully
reliable, is invoked first. If it fails to find a path, then
PESSIMIST, a slower but more reliable algorithm, is invoked.
CONCLUSION
The main contribution of this paper is a new retraction
method – small-step retraction – that helps PRM planners find
paths through narrow passages. The core idea underlying this
method is that retracting sampled configurations that are
barely colliding is sufficient to speed up the generation of
roadmap milestones within narrow passages. Barely colliding
configurations are relatively easy to retract out of collision. In
addition, they can be efficiently identified by running a
classical collision checker on thinned geometric models precomputed
using a medial-axis-based technique. A slight
drawback of the method is that it increases pre-computation
time. Another idea of our work is the combination of two
algorithms, OPTIMIST and PESSIMIST, which complement
each other well.