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 cumbersome 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 applications. 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.