程序代写代做代考 algorithm assembly Minkowski Sums

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).