The distance between convex sets with Minkowski sum structure: application to collision detection
- PDF / 2,560,135 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 74 Downloads / 202 Views
The distance between convex sets with Minkowski sum structure: application to collision detection Xiangfeng Wang1 · Junping Zhang2 · Wenxing Zhang2 Received: 21 July 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The distance between sets is a long-standing computational geometry problem. In robotics, the distance between convex sets with Minkowski sum structure plays a fundamental role in collision detection. However, it is typically nontrivial to be computed, even if the projection onto each component set admits explicit formula. In this paper, we explore the problem of calculating the distance between convex sets arising from robotics. Upon the recent progress in convex optimization community, the proposed model can be efficiently solved by the recent hot-investigated first-order methods, e.g., alternating direction method of multipliers or primal-dual hybrid gradient method. Preliminary numerical results demonstrate that those firstorder methods are fairly efficient in solving distance problems in robotics. Keywords Distance · Minkowski sum of sets · Projection · Alternating direction method of multipliers · Primal-dual hybrid gradient method · Collision detection
1 Introduction The Minkowski sum of sets (also known as dilation, sumset) is a long-standing and fundamental nomenclature in computational geometry. It plays an important role in the fields, such as mathematical morphology in image processing [44], collision detection in robotics [29], configuration space computation in mechanics [48], * Wenxing Zhang [email protected] Xiangfeng Wang [email protected] Junping Zhang [email protected] 1
School of Computer Science and Technology, East China Normal University, Shanghai 200062, China
2
School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, China
13
Vol.:(0123456789)
X. Wang et al.
Fig. 1 Diagram representations of the Minkowski sum of Ω1 = {x ∈ ℝn ∣ ‖x‖1 ≤ 1, xn ≥ 0} , Ω2 = {x ∈ ℝn ∣ ‖x‖2 ≤ 1} and Ω3 = {x ∈ ℝn ∣ ‖x‖∞ ≤ 1} . Top row: the case of n = 2 . Bottom row: the case of n = 3
numerical control machining in computer-aided manufacturing [45], and aggregation theory in economics [33]. Given two sets A ⊂ ℝn and B ⊂ ℝn (henceforth, we symbolize set by capital calligraphic), the Minkowski sum of A and B , denoted by A ⊕ B , is defined as
A ⊕ B ∶= {a + b ∣ a ∈ A, b ∈ B}.
(1.1)
Specially, if one of the sets consists of a unique element, e.g., A = {a} , we briefly adopt the notation a ⊕ B to indicate the translation of set B toward a. It follows immediately from (1.1) that the zero set {0} plays the role of identity element under the additive operation ⊕ . Figure 1 displays the diagrams of Minkowski sum of ball, box and convex polytope in two- and three-dimensions. Let F ⊂ ℝn be a nonempty set. The support function of F , denoted by 𝜎F ∶ ℝn → (−∞, +∞] , is defined as
𝜎F (x) ∶= sup {⟨x, y⟩ ∣ y ∈ F},
(1.2)
where ⟨x, y⟩ ∶= x⊤ y is the inner product endowed on ℝn . Because of the closedness
Data Loading...
