Abstract:
We consider the problem of controlling hundreds of robots to perform a task in concert. This problem presents many fundamental issues to robotics, control theory and computer science. With a great number of robots, decentralization is critical due to the cost of communication and the need for fault tolerance. In decentralized control, each robot should act based only on information local to it. It then becomes difficult, however, to guarantee or even derive the behavior of the entire system given the behaviors of the individual components. In this paper we address this difficulty in a novel way: We begin with a specification of an assembly and develop methods that allow us to automatically synthesize individual behaviors so that they are guaranteed to produce the desired global behavior. Specifically, we consider the task of assembling many disk-shaped parts in the plane into copies of a prescribed assembly (formation), which is specified by a graph. We not allow the parts to collide, making the task more difficult due to the non-trivial topology of the resulting 2n dimensional configuration space. As shown in Figure 1 we suppose that each part can move itself and can play any role in an assembly, which makes the task particularly rich. We first demonstrate a means of synthesizing from the specified assembly, a set of identical controllers for the parts to run which have the net effect of moving the parts to form copies of the specified assembly without colliding. The idea is that parts should join together to into subassemblies which should in turn join together to make larger assemblies and so on.