用顶点枚举法高效解决多面体碰撞检测难题
Polyhedral Collision Detection via Vertex Enumeration
- 将碰撞距离建模为凸优化的最优值，通过枚举极值点约束求解
- 在多障碍场景下比现有方法更可靠，部分情况更快
- 适合需要高精度碰撞判断的机器人路径规划应用
碰撞检测是机器人领域的关键功能。除球体外，任意形状的碰撞程度无法表示为连续可微函数。本文提出一种处理多面体间碰撞检测的框架，将两多面体间的有符号距离建模为凸优化问题的最优值，并在双层优化中约束该距离。为避免依赖专用双层求解器，方法利用有符号距离是与两物体相关的凸区域最小点这一特性，枚举该区域所有极值点并作为上层问题的约束。在使用相同混合互补问题求解器时，对比了现有方法的可靠性与速度。结果表明，该方法在包含多个障碍物的复杂碰撞检测问题中更具鲁棒性，且在某些情况下比现有方法更快。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。