A Linear and Exact Algorithm for Whole-Body Collision Evaluation Via Scale Optimization

Collision evaluation is of essential importance in various applications. However, existing methods are either cum- bersome to calculate or not exact. Therefore, considering the cost of implementation, most whole-body planning works, which require evaluating collision between robots and environments, struggle to tradeoff between accuracy and computationally efficiency. In this paper, we propose a zero-gap whole-body collision evaluation that can be formulated as a low-dimensional linear programming. This evaluation can be solved analytically in linear complexity. Moreover, the method provides gradient efficiently, making it accessible to optimization-based applica- tions. Additionally, this method provides support for obstacles represented by either points or hyperplanes. Experiments on the widely used aerial and car-like robots validate the versatility and practicality of our method.