Introduction

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 [1]. 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[2], 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.

Previous work

In the book [1], 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 non-planar.
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 surfaces.

Goal

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 [2] 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.

Reference

[1] J. Latombe, Robot Motion Planning. Kluwer Academic Publishers, 1991.
[2] 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.
[3] G. Varadhan and D. Manocha, “Star-shaped roadmaps - a deterministic sampling approach for complete motion planning,” in Proc. of Robotics: Science and Systems, 2005.