Transcript Paper 2

Path Planning in Expansive C-Spaces
D. Hsu
J. C. Latombe
R. Motwani
presented by Niloy J. Mitra
1
Overview
Problem statement
Expansive Configuration Spaces


Definition
Probabilistic analysis
Path planning algorithm using
expansive configuration space
2
Issues with Path Planning Problem
Path planning: hard problem
Complete planner

Exponential in the number degrees of
the configuration space
Probabilistic roadmap

good for multiple path-planning query
Probabilistic completeness
Algorithm for the single-path query problem
3
Probabilistic Roadmaps
4
Coverage
Bad
Good
5
Coverage
Bad
Good
almost any point of the configuration space can be connected
by a straight line segment to some milestone
6
Connectivity
Bad
Good
7
Connectivity
Bad
Good
1-1 correspondence between
the connected components of the roadmap and those of F
8
Narrow Passages
Connectivity is difficult to capture when there are narrow passages.
a narrow passage is difficult to define.
Difficult
Easy
How to characterize coverage/connectivity? Expansiveness
9
Visibility
All configurations in Free Space that can be
seen by a free configuration p
p
10
Є-good
Every free configuration “sees” at least a
є fraction of the free space, є is in (0,1].
0.5-good
1-good
F is 0.5-good
11
β-lookout of a subspace S
Subset of points in S that can see a β
fraction of F\S, β is in (0,1].
0.4-lookout of S
0.4-lookout of S
S
F\S
S
F\S
This area is
about
40% of F\S
12
Definition: (ε,α,β)-expansive
The free space F is (ε,α,β)-expansive if
 Free space F is ε-good
 For each subspace S of F, its β-lookout is at least
α fraction of S.
ε, α, β are in (0,1]
S
F\S
F is ε-good  ε=0.5
β-lookout
 β=0.4
Volume(β-lookout)
 α=0.2
Volume(S)
F is (ε, α, β)-expansive,
where ε=0.5, α=0.2, β=0.4.
13
Why Expansive?
ε, α, and β measure
the expansiveness of a free space.
Bigger ε, α, and β

Easier to construct a roadmap
with good connectivity/coverage.
14
Linking sequence
Lookout of V(p)
Visibility of p
p1
p2
p
p3
q
pn
Pn+1
Pn+1 is chosen from the lookout of the subset seen by p, p1,…,pn
15
Size of lookout set
BETTER
Small lookout
big lookout
A C-space with larger lookout set has higher
probability to construct a linking sequence with the
same number of milestones.
16
Theorem 1
Probability of achieving good connectivity
increases exponentially with the number of milestones
(in an expansive space).
As (ε, α, β) decrease 
the number of milestones needs to be increased
(to maintain good connectivity).
17
Theorem 2
Probability of achieving good coverage,
increases exponentially with the number of
milestones (in an expansive space).
18
Probabilistic Completeness
In an expansive space, the probability that a PRM planner
fails to find a path when one exists goes to 0 exponentially
in the number of milestones (~ running time).
[Hsu, Latombe, Motwani, 97]
19
Summary
Main result

If a C-space is expansive,
then a roadmap can be constructed efficiently
with good connectivity and coverage.
Limitation in implementation


No theoretical guidance about the stopping time.
A planner stops when either a path is found or
Max steps have been taken.
20
Basic idea of the planner
1. Grow two trees from Init position and Goal position.
2. Randomly sample nodes around existing nodes.
3. Find linking sequence between Init and Goal by
Incorporating new nodes that see a large portion of the
free space  i.e., those that are likely in the lookout set
Init
Goal
Expansion + Connection
21
Algorithm: Expansion
• Pick a node x with probability 1/w(x).
• Randomly sample k points around x.
• For each sample y, calculate w(y),
which gives probability 1/w(y)
Disk with radius d, w(x)=3
root
22
Algorithm: Expansion
• Pick a node x with probability 1/w(x).
• Randomly sample k points around x.
• For each sample y, calculate w(y),
which gives probability 1/w(y)
1/W(y1)=1/4
root
1
2
3
23
Algorithm: Expansion
• Pick a node x with probability 1/w(x).
• Randomly sample k points around x.
• For each sample y, calculate w(y),
which gives probability 1/w(y), if y
1. has bigger probability; 2. collision free; 3. can sees x
then add y into the tree.
root
1
2
3
24
Algorithm: Connection
• If a pair of nodes (i.e., x in Init tree and y in Goal tree)
 distance(x,y)<L, check if
x can see y
YES, then connect x and y
y
Goal
Init
x
25
Algorithm: Terminate
• The program iterates between Expansion/Connection,
until
two trees are connected, OR
2. max number of expansion/connection steps
has been reached
1.
Init
Goal
26
Computed Example
27
Comments
Estimate complexity as a function of
geometric attributes

Other geometric qualities or properties
may be exploited
Dimension of narrow passages
28