Fast Certification of Collision Probability Bounds with Uncertain Convex Obstacles
This addresses the need for real-time safety assurance in robotics, enabling reactive operation in uncertain settings, though it is incremental as it builds on prior work with convex decomposition.
The paper tackles the problem of quickly estimating collision risk for robots in uncertain environments by presenting two algorithms that compute upper bounds on collision probability with theoretical guarantees and fast query times (<200μs), achieving at least an order of magnitude speedup over existing methods.
To operate reactively in uncertain environments, robots need to be able to quickly estimate the risk that they will collide with their environment. This ability is important for both planning (to ensure that plans maintain acceptable levels of safety) and execution (to provide real-time warnings when risk exceeds some threshold). Existing methods for estimating this risk are often limited to models with simplified geometry (e.g. point robots); others handle complex geometry but are too slow for many applications. In this paper, we present two algorithms for quickly computing upper bounds on the risk of collision between a robot and uncertain obstacles by searching for certificate regions that capture collision probability mass while avoiding the robot. These algorithms come with strong theoretical guarantees that the true risk does not exceed the estimated value, support arbitrary geometry via convex decomposition, and provide fast query times ($<200μ$s) in representative scenarios. We characterize the performance of these algorithms in environments of varying complexity, demonstrating at least an order of magnitude speedup over existing techniques.