Exact and over-approximated guarantees for corner cutting avoidance in a multi-obstacle environment

Abstract

The corner cutting avoidance problem is an important but often overlooked part of motion planning strategies. Obstacle and collision avoidance constraints are usually imposed at the sampling time without regards to the intrasample behavior of the agent. Hence, it is possible for an agent to “cut the corner” of an obstacle while apparently respecting the constraints. This paper improves upon state of the art by providing exact and overapproximated descriptions of the undershadow (and of its complement, the visible) region generated by an agent against obstacles. We employ a hyperplane arrangement construction to handle multiple obstacles simultaneously and provide piecewise descriptions of the regions of interest and parametrizations of the corner cutting conditions (useful, eg, in finite horizon optimization problems). Mixed‐integer representations are used to describe the regions of interest, leading in the overapproximated case to binary‐only constraints. Illustrative proofs of concept, comparisons with the state of the art, and simulations over a standard multiobstacle avoidance problem showcase the benefits of the proposed approach