Minkowski Sums
\
Minkowski Sums
2
Problem – Configuration Space of a
Translating Robot
Input:
Polygonal moving object translating in 2-D workspace
Polygonal obstacles
Output: configuration space obstacles represented as polygons
Is C-obstacle a polygon?
3
Configuration Space of a
Translating Robot
Workspace
Configuration Space
x
y
Robot
Obstacle
C-obstacle
Robot
C-obstacle is a polygon.
4
Minkowski Sum
A
B
5
Minkowski Sum
6
Minkowski Sum
7
Minkowski Sum
8
Configuration Space Obstacle
O -R
Obstacle
O
Robot
R
C-obstacle
C-obstacle is
O -R
Classic result by Lozano-Perez and Wesley 1979
9
Properties of Minkowski Sum
Minkowski sum of boundary of P and boundary of Q is a subset of boundary of
Minkowski of two convex sets is convex
P⊕Q
10
Minkowski sum of convex polygons
The Minkowski sum of two convex polygons P and Q of m and n vertices respectively
is a convex polygon P + Q of m + n vertices.
The vertices of P + Q are the “sums” of vertices of P and Q.
=
11
Gauss Map
Gauss map of a convex polygon
Edge point on the circle defined by the normal
Vertex arc defined by its adjacent edges
12
Gauss Map Property of
Minkowski Sum
p+q belongs to the boundary of Minkowski sum
only if the Gauss map of p and q overlap.
13
Computational efficiency
Running time O(n+m)
Space O(n+m)
14
Minkowski Sum of Non-convex Polygons
Decompose into convex polygons (e.g., triangles or trapezoids),
Compute the Minkowski sums, and
Take the union
Complexity of Minkowski sum O(n2m2)
15
Worst case example
O(n2m2) complexity
2D example
Agarwal et al. 02
16
3D Minkowski Sum
Convex case
O(nm) complexity
Many methods known for computing Minkowski sum in this case
Convex hull method
Compute sums of all pairs of vertices of P and Q
Compute their convex hull
O(mn log(mn)) complexity
More efficient methods are known [Guibas and Seidel 1987]
17
3D Minkowski Sum
Non-convex case
O(n3m3) complexity
Computationally challenging
Common approach resorts to convex decomposition
18
3D Minkowski Sum Computation
Two objects P and Q with m and n convex pieces respectively
Compute mn pairwise Minkowski sums between all pairs of convex pieces
Compute the union of the pairwise Minkowski sums
Main bottleneck
Union computation
mn is typically large (tens of thousands)
Union of mn pairwise Minkowski sums has a complexity close to O(m3n3)
No practical algorithms known for exact Minkowski sum computation
19
Minkowski Sum Approximation
We developed an accurate and efficient approximate algorithm [Varadhan and Manocha 2004]
Provides certain “geometric” and “topological” guarantees on the approximation
Approximation is “close” to the boundary of the Minkowski sum
It has the same number of connected components and genus as the exact Minkowski sum
20
Brake Hub
(4,736 tris)
Union of
1,777 primitives
Rod
(24 tris)
21
Union of
4,446 primitives
Anvil
(144 tris)
Spoon
(336 tris)
22
Knife
(516 tris)
Scissors
(636 tris)
Union of
63,790 primitives
23
444 tris
1,134 tris
24
Union of
66,667 primitives
25
Cup
(1,000 tris)
Cup Offset
Gear
2,382 tris)
Gear Offset
Offsetting
26
Configuration Space Approximation
– 3D Translation
Obstacle
O
Robot
R
O -R
C-obstacle
In translational motion planning, the C-obstacle is the Minkowski sum of the obstacle and the robot reflected about its origin.
27
Assembly
Obstacle
Robot
The figure shows two identical parts each with pegs and holes. The goal is to assemble the two
parts so that the pegs of one part fit into the holes of the other. The parts are allowed to only translate in 3D.
28
Assembly
Roadmap
16 secs
Path Search
0.22 secs
Start
Goal
Obstacle
This problem can be treated as a motion planning problem by considering one of the parts as a robot and the other as the obstacle. This is a challenging example because the goal configuration, where the pegs fit into the holes, is lodged within a very narrow passage.
29
Assembly
We applied our algorithm to the assembly scenario I showed in the beginning of the talk.
Our algorithm computed a roadmap in 16 secs. Once this roadmap is computed, we can
then answer multiple path planning queries between two configurations. The queries
took only 0.22 secs.
Here is the path in configuration space.
This is a challenging example because the goal configuration is lodged within a narrow passage.
30
Path in Configuration Space
Start
Goal
Path
31
Other Applications
Minkowski sums and configuration spaces have also been used for
Morphing
Tolerance Analysis
Knee/Joint Modeling
Interference Detection
Penetration Depth
Packing
Here are many other applications of Minkowski sums and configuration spaces
32
Applications – Dynamic Simulation
Kim et al. 2002
Interference Detection
Penetration Depth
Computation
33
Morphing
A
B
Morph
34
Applications – Packing
Configuration Space of
2T+1R Robot
36
Polygonal robot translating & rotating in 2-D workspace
workspace
configuration space
37
Polygonal robot translating & rotating in 2-D workspace
x
y
θ
38
Contact Surfaces (C-surfaces)
A C-surface arises from a contact between features of the robot and the obstacle
R
O
O
R
Type A contact
Type B contact
39
Type A Contact Surface
ai+1(q)
ai(q)
bj
bj-1
bj+1
R
O
vi R(q)
Contact is feasible when
vi R(q) . (bj-1 – bj ) ≥ 0 Λ
vi R(q) . (bj+1 – bj ) ≥ 0
APPLAi,j
40
2D Translation and Rotation
Obstacles
Robot
Here is a planar robot with translational and rotational DOF. There are two gear-shaped obstacles (shown in gray) and a gear-shaped robot (shown in blue).
41
2D Translation and Rotation
Here is a planar robot with translational and rotational DOF. There are two gear-shaped obstacles (shown in gray) and a gear-shaped robot (shown in blue).
42
Contact Surfaces
x
q
y
3,929
contact surfaces
The configuration space is three dimensional. I have shown the contact surfaces. These are close to 4000 surfaces.
And these surfaces are non-linear and can have a maximum degree of 4.
43
Representation of C-obstacle
How can we represent C-obstacle in terms of C-surfaces?
Non-convex case
Resort to convex decomposition
q ∈ CO
For the case of a convex robot and a convex obstacle,
CONSTAi,j (q) Λ CONSTBi,j(q) is true for all contacts (edge-vertex pairs)
44
Free Space and Contact Surfaces
F is bounded by the C-surfaces
C-surfaces
Free space
F
F
C-obstacle
F
∂F
…
45
Free Space Computation
To obtain the free space requires computing “arrangement” of the C-surfaces
…
46
Arrangement
Arrangement A(S) of a set S of geometric objects [Halperin 1997; Agarwal & Sharir 2000]
Arrangement of lines
(clipped within a window)
Decomposition of space into relatively open connected cells of dimensions 0,…,d
All the surface extraction problems can be reduced ….
Arrangement of a set of geometric objects is the decomposition of the space
into connected cells bounded by the geometric objects.
The figure shows an example of arrangement of lines.
47
Free Space Computation
Compute an arrangement of the C-surfaces
Compute intersections between the C-surfaces
Retain the appropriate portions of the arrangement
Free space
F
F
C-obstacle
F
…
48
Free Space Computation
Arrangement computation is difficult
Computing surface-surface intersection is prone to robustness problems
Typically O(n2) number of contact surfaces
Contact surfaces are non-linear
…
49
Free Space Approximation
We have developed an accurate and efficient approximate algorithm [Varadhan and Manocha 2004]
Provides certain “geometric” and “topological” guarantees on the approximation
Approximation is “close” to the boundary of the free space
It has the same number of connected components and genus as the exact Minkowski sum
50
Free Space Approximation
x
q
y
3,929
contact surfaces
Free space boundary
approximation
The configuration space is three dimensional. I have shown the contact surfaces. These are close to 4000 surfaces.
And these surfaces are non-linear and can have a maximum degree of 4.
51
2T+1R: Gears
Start
Goal
The start and goal configurations are shown in red and green respectively. The robot must move in between the narrow passage between the obstacles to reach the goal. It needs to both translate as well as rotate in order to pass through the narrow passage.
52
2T+1R: Gears
Here is a video of the robot motion.
53
2D Translation and Rotation
Here is a planar robot with translational and rotational DOF. There are two gear-shaped obstacles (shown in gray) and a gear-shaped robot (shown in blue).
54
2T+1R: Gears
Path in Configuration Space
x
y
q
Goal
Start
Path
Narrow passage
Robot
Obstacle
Obstacle
Here is the free space approximation. And here is the path superimposed on the approximation.
narrow passage – does not have too much room to wiggle
Challenging to find paths through such narrow passages.
55
3R Manipulators
Here is a planar robot with translational and rotational DOF. There are two gear-shaped obstacles (shown in gray) and a gear-shaped robot (shown in blue).