C-obstacle Query Computation for Motion Planning
Robot Motion Planning
Project Presentation | PPT | PDF | Video
The configuration space of a robot is partitioned into free space
and configuration space obstacle (C-obstacle) space. Most of the prior
work in collision detection and motion planning algorithms is targeted
towards checking whether a configuration or a 1D path lies in the free space. In this project, we
are focusing on the problem of checking whether a C-space primitive or
a spatial cell lies completely inside C-obstacle space, without
explicitly computing the boundary of C-obstacle. We refer to this
problem as the C-obstacle query.
The C-obstacle query is useful for cell decomposition based
algorithms for motion planning . These algorithms subdivide
the configuration space into cells and need to check whether a cell is
fully contained either in the free space or in C-obstacle space.
The C-obstacle query also arises in sampling based approaches for
motion planning, especially complete motion planning. These
include the star-shaped roadmap algorithm, which is a deterministic
sampling algorithm and subdivides the configuration space into a
collection of cells in a hierarchial fashion. Given that the time and
space complexity of these methods grows quickly with the level of
subdivision, it is important to identify cells that lie in C-obstacle
and no further subdivision is executed for them.
In the book , Latombe has described a cell labelling algorithm
based on contact surface constraint testing and convex decomposition. A
configuration cell lies entirely inside C-obstacle if it lies inside a
C-obstacle region mapped by a pair of convex pieces from the robot and
the obstacles respectively. If C-space is defined in R^2, the test against each
C-obstacle region can be performed by using half-plane constraints
imposed by planar contact surfaces; whereas, in case of C-space in R^2 * SO(1), the algorithm is
required to use non-linear constraints as the contact surfaces are
One computational drawback of this method is that it enumerates all the
contact surfaces for all convex pairs to test the constraints.
Moreover, it is rather difficult to extend this approach to higher DOFs
robots due to the increasing dimensionality of the underlying contact
Our goal is try to address the problem of checking whether a
configuration space primitive or cell lies completely in C-obstacle
space (i.e. C-obstacle query).
Given it is difficult to solve this problem in C-space, we would like
to map the problem into the workplace first, and solve it in the
workspace. We are expecting to solve this problem in the similar method
introduced by Schwarzer et al.'s
 for local path checking, which uses the
'distance between objects' and 'bounding motion in workspace' to check
whether a line in C-space entirely lies inside the free space.
 J. Latombe, Robot Motion Planning.
Kluwer Academic Publishers, 1991.
 F. Schwarzer, M. Saha, and J. Latombe, “Adaptive
dynamic collision checking for single and multiple articulated robots
in complex environments,” IEEE Tr. on Robotics, vol. 21, no. 3, pp.
338–353, June 2005.
 G. Varadhan and D. Manocha, “Star-shaped roadmaps - a deterministic
sampling approach for complete motion planning,” in Proc. of Robotics:
Science and Systems, 2005.