Transcript large-kin

Algorithmic Robotics
and Motion Planning
Fall 2006/7
Dynamic Maintenance and Self-Collision Testing
for Large Kinematic Chains
Dan Halperin
Tel Aviv University
Kinematic structures
A collection of rigid
bodies hinged
together---motion
along joints
LARGE structures:
hyper-redundant
robots [Burdick,
Chirikjian, Rus, Yim and
others],macro-
molecules
The static model
n links of roughly the same size
possibly slightly interpenetrating
many favorable properties and simple
algorithms (HSR, union boundary
construction), in particular, data
structures for intersection queries:
O(n log n) preprocessing -> O(n) rand.
O(n) space
O(log n) query
-> O(1)
The kinematic model
links
joints
chain, tree, graph
http://www.youtube.com/watch?v=k-VgI4wNyTo
Dynamic maintenance,
self collision testing
the problem:
Carry out a sequence of operations
efficiently
update of joint values
the query is for self collision
sample motivation: monte carlo
simulation of protein folding paths
Dynamic maintenance:
what’s available
dynamic spatial data structures
insertions and deletions
kinetic data structures [Basch, Guibas, Hershberger 97]
independent movements
robot motion planning
small number of degrees of freedom
dynamic maintenance for kinematic struct’s
link-size queries [H-Latombe-Motwani 96,Charikar-HMotwani 98]
Dynamic maintenance,
self collision testing
the problem (reminder):
Carry out a sequence of operations efficiently
update of joint values
the query is for self collision
n: # of links ~ # of joints
theory, worst case: rebuild spatial
structure at each update
Collision testing,
existing techniques
Updating
I-COLLIDE
(Cohen et al ’95)
GRID
(e.g. Halperin and
Overmars ’98)
BV Hierarchies
(Quinlan
’94, Gottschalk et al ’96, van
den Bergen ’97, Klosowski et al
’98)
Self-collisions
O( N )
O( N )
O( N )
O( N )
O( N log N )
( N )
Self-collision testing, assumptions
a small number of joint values change
from one step to the other
the chain was self-collision free at the last
step
Chain representation
A Sequence of reference frames (links)
connected by rigid-body transformations (joints)
Hierarchy of “shortcut” transformations
Bounding Volume Hierarchy
Chain-aligned: bottom-up, along the chain
Each BV encloses its two children in the hierarchy
Shortcuts allow to efficiently compute relative
position of BVs
At each time step only BVs that contain the
changed joints need to be recomputed
Self-collision detection
Test the hierarchy against itself to find
collisions. But …
Do not test inside BVs that were not
updated after the last set of changes
Benefits:


Many unnecessary overlap tests are avoided
No leaf node tested against itself
Self-collision: Example
Experimental results
We tested our algorithm (dubbed
ChainTree) against three others:



Grid – Collisions detected by indexing into
a 3D grid using a hash table
1-OBBTree – An OBB hierarchy is created
from scratch after each change and then
tested against itself for collisions
K-OBBTree – After each change an OBB
hierarchy is built for each rigid piece of the
chain. Each pair of hierarchies is tested for
collisions
Results: Extended chain (1)
Single Joint Change
Results: Extended chain (2)
100 Joint Changes
Protein backbones
1SHG
(171 atoms)
1B4E
(969 atoms)
1LOX
(1941 atoms)
Results: Protein backbones (1)
Single Joint Change
Results: Protein backbones (2)
10 Joint Changes
Analysis – updating
For each joint change:
 O (log N ) shortcut transformations need

to be recomputed
O (log N ) BVs need to be recomputed
For k simultaneous changes O(k log N )
time, but never more than O( N )
Previous BV hierarchies required O(N log N)
updating time
Analysis – collision detection
4
( N 3 ) in the worst case
Upper bound holds for “not so tight” hierarchies like
ours
Lower bound holds for any convex BV
Slightly worse than ( N ) bound we prove for a
regular hierarchy
If topology of regular hierarchy is not updated, can
deteriorate to ( N 2 )
Guibas et al '02: bounds for spherical hierarchy
Upper bound
we first show for tight spherical hierarchy, the extend
to OBBs
tight hierarchy: the bounding sphere is the minimal for
the original links at each level
Reminder, well-behaved chain, two constants:
(1) the ratio between the biggest and smallest
bounding sphere of a link
(2) the minimum distance between the centers of two
bounding sphere of links
Upper bound, cont’d
Step 1: regularize chain
all spheres of same radius r
two successive spheres in the chain are not disjoint
level i=0, tree leaves
at level i there are gi = 2i each bounding volume, a
bounding sphere of radius gir
the number of bounding spheres at level i intersecting
a single bounding sphere is
Upper bound, cont’d
Mi can be as large as n/gi
Max Mi is attained for the smallest i such that
which, since gi = 2i, occurs when
Ti denotes the number of sphere overlaps at level I,
T is the overall number of sphere overlaps
Upper bound, cont’d
Upper bound, cont’d
Will the bound hold for a “not so tight”
hierarchy like ours?
YES!
• OBBs are larger than tight bounding spheres by a
constant factor at each level
• This factor is fixed for all levels of the hierarchy
Upper bound, cont’d
lemma: given two OBBs contained in a sphere D
of radius R, the OBB bounding both of them is
contained in a sphere of radius √3R concentric
with D
Upper bound, cont’d
lemma: at level I of an OBB hierarchy, each OBB
is contained in a sphere of radius c2ir, where c is
an absolutre constant
Proof:
C1 is chosen such that this is true for levels i =
0,1, …, 4
assume for i-1 (i>4) and prove for i
S sphere of radius 2ir containing the subchain
bounded by the 32 boxes at level i-5
S0 sphere concentric with S with radius 2ir(1+c/16)
Upper bound, cont’d
Consider the OBB at level i-4
S1 sphere concentric with S0 with radius √3 times
the radius of S0 contains all the OBBs at level i-4
Continuing up to level I we get sphere S5 of radius
√352ir(1+c/16) that contains the OBB at this level
that contains all the 32 OBBs of level i-5 in its
subtree
c must be such that
Upper bound, cont’d
finally we choose
Lower bound
parameter d
d
Lower bound, one unit (3d links)
Lower bound, a layer
a copy of a unit
tranalted by
(2r,-2r,0)
a layer:
d/8 units
Lower bound,
overall construction
a copy of a layer
tranalted by
(0,-2r,2r)
overall:
d/8 layers
a unit consists of
cn1/3 links
Lower bound,
overall construction, cont’d
there are c'n2/3 units at
the level where the links
of a unit are grouped
together
the convex hull of each
unit contains the point
(2(d-1)r, (d-1)r, (d-1)r/4)
overall (n4/3) overlaps
Based on the papers:
I.
Lotan, F. Schwarzer, D. Halperin and J.-C. Latombe
Algorithm and data structures for efficient energy
maintenance during Monte Carlo simulation of proteins
Journal of Computational Biology 11 (5), 2004, 902-932.
II.
Efficient maintenance and self-collision testing for kinematic
chains,
Proc. 18th ACM Symposium on Computational Geometry,
Barcelona, 2002, pp, 43-52.
THE END