  Configuration space (C-space) has played a central role in collision-free
motion planning, particularly for robot manipulators. While it is possible to
check for collisions at a point using standard algorithms, to date no practical
method exists for computing collision-free C-space regions with rigorous
certificates due to the complexities of mapping task-space obstacles through
the kinematics. In this work, we present the first to our knowledge method for
generating such regions and certificates through convex optimization. Our
method, called C-Iris (C-space Iterative Regional Inflation by Semidefinite
programming), generates large, convex polytopes in a rational parametrization
of the configuration space which are guaranteed to be collision-free. Such
regions have been shown to be useful for both optimization-based and randomized
motion planning. Our regions are generated by alternating between two convex
optimization problems: (1) a simultaneous search for a maximal-volume ellipse
inscribed in a given polytope and a certificate that the polytope is
collision-free and (2) a maximal expansion of the polytope away from the
ellipse which does not violate the certificate. The volume of the ellipse and
size of the polytope are allowed to grow over several iterations while being
collision-free by construction. Our method works in arbitrary dimensions, only
makes assumptions about the convexity of the obstacles in the task space, and
scales to realistic problems in manipulation. We demonstrate our algorithm's
ability to fill a non-trivial amount of collision-free C-space in a 3-DOF
example where the C-space can be visualized, as well as the scalability of our
algorithm on a 7-DOF KUKA iiwa and a 12-DOF bimanual manipulator.
