  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\mu$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.
