Path Planning Based on Closed-Form Characterization of Collision-Free Configuration-Spaces for Ellipsoidal Bodies, Obstacles, and Environments

Yan Yan, Qianli Ma, and Gregory Chirikjian

Abstract:
A closed-form parameterization of the collisionfree configuration spaces (C-spaces) of robots and obstacles represented as finite unions of ellipsoids is presented. These objects can be quite general, including nonconvex bodies, and this approach represents an alternative to polyhedral representations of bodies. With this method, there is never any reason to sample and discard configurations suspected of being in collision, and existing sample-based planners can be modified to operate in areas of C-space that are a priori guaranteed to be collision-free. This all builds on the recent work on computing exact boundaries of Minkowski sums and differences of two arbitrary ellipsoids using affine transformations and the analytic properties of offset surfaces.
A "highway" roadmap system is then constructed to connect the collision-free regions. Unlike other skeletal/roadmap decompositions of C-space, collision checking in this C-space graph can be eliminated not only for the vertices, but also for the edges, and the problem is simplified to a search for a connected path in an adjacency graph of the roadmap. We apply this approach of "knowing where to look" for path planning in C-spaces with narrow passages and demonstrate its potential by comparing with the well known sample-based path planning method that does not currently have the ability to take advantage of a priori knowledge of collision-free regions of C-space.