In robotic tasks and in mechanism design, planning motion compliant to contacts is often desired, but planning such motion poses special challenges not present in collision-free motion planning. One challenge is how to achieve exactness, i.e., how to make sure that a planned path is exactly compliant to a desired contact state, especially when the configuration manifold of such a contact state is hard to describe analytically due to high geometrical complexity and/or high dimensionality. We tackle the problem with a hybrid approach of direct computation to exploit contact constraints and randomized planning. We describe such a planner for planning motion compliant to a contact formation between two arbitrary polyhedra and present results of implementation.

Random sampling strategies play critical roles in randomized motion planners, which are promising and practical for motion planning problems with many degrees of freedom (dofs). In this paper, we explore random sampling in a constrained configuration space-the contact configuration space between two polyhedra, motivated by the need for generating contact motion plans. Given a contact formation (CF) between two polyhedra A and B, our approach is to randomly generate configurations of A satisfying the contact constraints of the CF. Key to the approach is to guarantee that sampling happens only in the constrained space to be efficient, which has not been addressed in the literature. We have implemented a strategy for random sampling of configurations constrained by CF consisting of a single principal contact (PC) with good results. We plan to further extend the approach to CFs with multiple PCs, and apply the results to contact motion planning.

Planning contact motion is important for many robotic tasks but difficult in general due to high variability and geometrical complexity of contact states. It is desirable to decompose the problem into simpler subproblems. A promising decomposition treats the problem as consisting of: 1) automatic generation of a discrete contact state graph, and 2) planning contact transitions between neighboring contact states and contact motions within the same contact state. This paper addresses a divide-and-merge approach on solving the general problem by such a decomposition. It discusses issues related to solving the two subproblems and provides examples of automatically generated contact state graphs between two contacting 3D polyhedra by the approach, which extend the results for 2D polygons reported by Ji et al. (1999).

Planning in contact state space is very important for many robotics tasks. This paper introduces a general and novel approach for automatic creation of high-level, discrete contact state space between two objects, called contact formation (CF) graphs. A complete CF graph is the result of merging several special subgraphs, called the goal-contact relaxation graphs. We have implemented our algorithm for arbitrary contacting polygons, and the results obtained are presented in this paper. The implementation is extended for arbitrary contacting polyhedra. The time complexity of our algorithm is bounded by O(M/sup 2/), where M characterizes the maximum complexity of the two objects.