Automatic generation of high-level contact state space

A divide-and-merge approach is introduced for automatic generation of high- level. discrete contact state space, represented as contact state graphs, b etween two contacting polyhedral solids from their geometric models. Based on the fact that a contact state graph is the union of the subgraphs called a goal-contact relaxation (GCR) graph, the approach consists of algorithms (1) to generate a complete GCR graph automatically given the most constrai ned contact state in the GCR graph and (2) to merge GCR graphs automaticall y. The algorithms are implemented for cases in which the most constrained c ontact state in a GCR graph consists of up to three principal contacts. The ability to capture and represent contact state information effectively and efficiently is essential for robotic operations involving compliant motion s, for simulation of contact motions, and for haptic interactions.