This dissertation focuses on methods for automatic synthesis of discrete event controllers (DEC's) for robotic assembly of polyhedral parts. A DEC reacts to contact transitions and issues desired transitions to the underlying continuous system. A DEC can be implemented by an augmented adjacency graph. Each node represents a qualitative configuration state of the objects. Spatially adjacent states are connected by arcs. Each node is augmented with a desired transition. The graph can be constructed while searching backwards. A state is expanded by generating hypotheses about spatially adjacent states and subsequently rejecting the infeasible hypotheses. This paradigm requires a representation with the following properties: (i) the representation must contain all information about contacts; (ii) spatial adjacency must be easy to verify and, (iii) a necessary condition for spatial adjacency suitable for hypothesis generation must exist. Two representations have been considered: sets of elementary contacts; and feature interaction matrices (FIM's). Spatial adjacency is difficult to verify for sets of elementary contacts. Hypothesis generation is complicated by the lack of a suitable necessary condition for spatial adjacency. These problems make sets of elementary contacts ill-suited as a representation for automatic synthesis of DEC's. A FIM encodes besides contact information about the relative configuration. An important advantage of using FIM's representation is that spatial adjacency can be verified easily using convex cone techniques. Furthermore, there exists a simple necessary condition for spatial adjacency that can be used for hypothesis generation. Complete algorithms for hypothesis generation are presented. An optimization-based approach is presented to verify the geometric feasibility of hypothetical feature interaction matrices. Some hypothetical FIM's constrain the relative configuration such that the objects necessarily penetrate each other. An algorithm has been presented that can falsify some of these hypotheses by simple processing of the FIM's.
展开▼
