Transcript Paper 2

Path Planning in Expansive C-Spaces
D. Hsu
J. –C. Latombe
R. Motwani
Prepared for CS326A, Spring 2003
By Xiaoshan (Shan) Pan
1
Structure of the Paper
 1st section
 Theoretical analysis of expansiveness
2nd section (will not be covered)
 A new PRM planner
2
Issues of probabilistic roadmaps
 Coverage
 Connectivity
3
Is the coverage adequate?

It means that milestones are distributed such that almost
any point of the configuration space can be connected by a
straight line segment to one milestone
Bad
Good
4
Connectivity

There should be a one-to-one correspondence between the
connected components of the roadmap and those of F
Bad
Good
5
Narrow Passage

Connectivity is difficult to capture when there are narrow
passages.

a narrow passage is difficult to define.
Difficult
Easy
Characterize coverage & connectivity?
 Expansiveness
6
Notion: Visibility
 All configurations in Free Space that can
be seen by a free configuration p
p
7
Notion: Є-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
8
Notion: β-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
9
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.
10
Why expansive?
 ε, α, and β measure the expansiveness of a
free space.
 Bigger ε, α, and β  less cost of constructing
a roadmap with good connectivity/coverage.
11
Definition: 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
12
Size of lookout set
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.
13
Theorem 1
 Probability of achieving good connectivity increases
exponentially with the number of milestones (in an
expansive space).
 If (ε, α, β) decreases  then need to increase a
great amount of milestones (to maintain good
connectivity)
14
Theorem 2
 Probability of achieving good coverage, increases
exponentially with the number of milestones (in an
expansive space).
15
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]
16
Summary
 Main result
 If a C-space is expansive, then a roadmap
can be constructed efficiently with good
connectivity and coverage.
 Limitation in implementation
 It does not tell you when to stop growing the
roadmap.
 A planner stops when either a path is found
or Max steps are reached.
17
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
18
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
19
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
20
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(y2)=1/1
root
1
2
3
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)
1/W(y3)=1/2
root
1
2
3
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), if y
1. has bigger probability; 2. collision free; 3. can sees x
then add y into the tree.
root
1
2
3
23
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
24
Algorithm: terminate condition
• The program iterates between Expansion and
Connection, until
1. two trees are connected, or
2. max number of expansion & connection steps is reached
Init
Goal
25
Computed example
26
Future research
• Accelerate the planner by automatically generating
intermediate configurations to decompose the free space
into expansive components.
27
Future research
• Accelerate the planner by automatically generating
intermediate configurations to decompose the free space
into expansive components.
• Use geometric transformations to increase the
expansiveness of a free space. E.g., widening narrow
passages.
28
Future research
• Accelerate the planner by automatically generating
intermediate configurations to decompose the free space
into expansive components.
• Use geometric transformations to increase the
expansiveness of a free space. E.g., widening narrow
passages.
• Integrate the new planner with other planner for
multiple-query path planning problems.
Questions?
29