Efficient Probabilistic Collision Detection for Non-Convex Shapes

Jae Sung Park, Chonhyon Park and Dinesh Manocha
University of North Carolina at Chapel Hill

Abstract

We present new algorithms to perform fast probabilistic collision queries between convex as well as non-convex objects. Our approach is applicable to general shapes, where one or more objects are represented using Gaussian probability distributions. We present a fast new algorithm for a pair of convex objects, and extend the approach to non-convex models using hierarchical representations. We highlight the performance of our algorithms with various convex and non-convex shapes on complex synthetic benchmarks and trajectory planning benchmarks for a 7-DOF Fetch robot arm.

Papers

Efficient Probabilistic Collision Detection for Non-Convex Shapes (PDF)
IEEE International Conference on Robotics and Automation (ICRA), 2017.

Fast and Bounded Probabilistic Collision Detection for High-DOF Robots in Dynamic Environments (PDF)
Workshop on the Algorithmic Foundations of Robotics (WAFR), 2016.

Efficient Probabilistic Collision Detection for Non-Gaussian Noise Distributions (PDF)
IEEE Robotics and Automation Letters (RA-L), 2020.

Algorithm Description

Our approach is applicable to any models represented in terms of inexact polygons or noisy point cloud data in which we are given two general shapes and the error is represented using Gaussian probability distributions. We compute hierarchical representations of non-convex models using simpler bounding volumes and present a novel hierarchical probabilistic collision detection algorithm. Moreover, we present fast and reliable algorithms to perform probabilistic collision detection on simple shapes such as AABBs (axis-aligned bounding boxes), OBBs (oriented-bounding boxes), k-DOPs (k discretely oriented polytopes), and convex polytopes.

Results

Probabilistic Collision Detection between a Predicted Human Pose and a Real Robot

Benchmarks for Probabilistic Collision Detection between Complex Shapes