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.

I. Introduction

Collision Evaluation is critical in a variety of fields, such as physics engines, computer graphics and robot navigation. In recent years, with the development of autonomy, an increasingly large number of robots are deployed in complex real-world scenarios, where they may be requested to navigate through dense and highly dynamic environments, as illustrated in Fig. 7, or even to cross narrow gaps of similar size to themselves as shown in Fig. 1. These planning problems where the robot's shape has to be taken into account, namely whole-body planning, urgently require exact and efficient collision evaluation of robots and environments.