頂点列挙による多面体衝突検出
Polyhedral Collision Detection via Vertex Enumeration
多面体間の符号付き距離を凸最適化の最適値として定式化し、その極値点を列挙して制約化することで、二段階最適化問題における衝突検出を高信頼・高速に解く手法を提案した。
著者: Andrew Cinar, Yue Zhao, Forrest Laine
分類: cs.CG, cs.RO
原文アブストラクト
Collision detection is a critical functionality for robotics. The degree to which objects collide cannot be represented as a continuously differentiable function for any shapes other than spheres. This paper proposes a framework for handling collision detection between polyhedral shapes. We frame the signed distance between two polyhedral bodies as the optimal value of a convex optimization, and consider constraining the signed distance in a bilevel optimization problem. To avoid relying on specialized bilevel solvers, our method exploits the fact that the signed distance is the minimal point of a convex region related to the two bodies. Our method enumerates the values obtained at all extreme points of this region and lists them as constraints in the higher-level problem. We compare our formulation to existing methods in terms of reliability and speed when solved using the same mixed complementarity problem solver. We demonstrate that our approach more reliably solves difficult collision detection problems with multiple obstacles than other methods, and is faster than existing methods in some cases.
