| Planar rigid formations are of great interest in the field of robotics. In this dissertation, we model the interaction between robots using concepts from group theory and graph theory, and present an algorithmic approach for the enumeration of all minimally-rigid, acyclic, directed graphs. Minimally-rigid formations are those in which all inter-agent distances between robots must remain fixed, but would fail to be rigid through the removal of an edge (realized as a controlled relative distance between a pair of agents). Minimally rigid formations make maximally parsimonious use of relative configuration sensing, and are useful as a means of avoiding possible sensor based instabilities due to the presence of calibration errors and noise in the measurements. We show that there is exponential complexity in the number of possible formations as the number of agents increases. We describe a constructive procedure by which all minimally-rigid, acyclic directed graphs can be created starting with a single directed edge. An algorithm for enumerating all such formations is given. We also show that the formation graphs can be separated into 2 n-2 formation skeletons called stratification classes. A computer algorithm to solve the enumeration problem is discussed in detail and explicit results are given for low-order formations.;Next, we discuss the embeddings of these minimally rigid formations into various geometric shapes via the use of planar point lattices. By doing so, we investigate how the number of possible formations changes given constraints placed upon the overall geometry of the formation. We present embedding results subject to edge length constraints. This thesis also describes several problems in the controlled aggregation of robots to create minimally rigid formations. We develop a non-holonomic controller which will guide a robot from an initial location to a set distance away from a pair of other robots. We investigate stability properties of this control law and provide simulation results investigating agents in triangular configurations. Using formation shape deformation metrics, we explore how the properties of a class of distributed sensing control laws behave under changes in the lead robot trajectory in a triangular formation. This thesis concludes with an application in which a switched mode control law can be used to guide a robot through a lattice of obstacles. |
