No abstract available.

In distributed multi-robot construction it is important to set the relative rates at which different construction sites receive raw building materials. Otherwise, subtasks finish at different times introducing unnecessary delays. We present a feedback algorithm to achieve robust load balancing in routing building materials for stochastic, distributed, multi-robot construction systems. We express global behavior in terms of local reactive behavior via Guarded Command Programming with Rates and prove correctness of the load-balancing controller for a wide range of conditions. We adapt a proof from earlier work on controlling Stochastic Chemical Kinetic systems and illustrate the algorithm on the Factory-Floor robotic testbed [1].

This paper describes how to specify the local reactive behavior of robots via guarded command programs with rates. These programs express concurrency and can be composed easily. Rates allow programs to be interpreted as Markov processes, which we use to define an appropriate notion of robustness and performance. We use composition to “robustify” programs with good performance, i.e. create a robust program with good performance from a program that has good performance but is not robust. We demonstrate this approach on a sub process of a reconfiguration program in a multi-robot system.

We describe how a graph grammar program for robotic self-assembly, together with measurements of kinetic rate data yield a Markov process model of the dynamics of programmed self-assembly. We demonstrate and validate the method by applying it to a physical testbed consisting of a number of "programmable parts", which are able to control their local interactions according to their on-board programs. We describe a technique for obtaining kinetic rate constants from simulation and a comparison of the behavior predicted by the Markov model with the behavior predicted by a high-fidelity simulation of the system

In this paper, we introduce a robotic implementation of the theory of graph grammars (Klavins et al., 2005), which we use to model and direct self-organization in a formal, predictable and provably-correct fashion. The robots, which we call programmable parts, float passively on an air table and bind to each other upon random collisions. Once attached, they execute local rules that determine how their internal states change and whether they should remain bound. We demonstrate through experiments how they can self-organize into a global structure by executing a common graph grammar in a completely distributed fashion. The system also presents a challenge to the grammatical method (and to distributed systems approaches in general) due to the stochastic nature of its dynamics. We conclude by discussing these challenges and our initial approach to addressing them.

In this paper we describe a software tool called CCLi (for CCL interpreter) that implements the Computation and Control Language (CCL). CCL is a language for modeling and programming of robotic and control systems. CCLi is used to simulate CCL models and programs and can also be used to execute CCL programs on actual robots. The language is particularly well suited to concurrent, partially synchronized processes interacting via communications and the environment, such as would describe cooperative control tasks. This paper describes the syntax and semantics of the language and gives examples of its use in modeling and programming cooperative control and multi-robot systems.

In this paper we define a class of graph grammars that can be used to model and direct distributed robotic assembly or formation forming processes. We focus on the problem of synthesizing a grammar so that it generates a given, prespecified assembly. In particular, to generate an acyclic graph we synthesize a binary grammar (rules involve at most two parts), and for a general graph we synthesize a ternary grammar (rules involve at most three parts). We then show a general result that implies that no binary grammar can generate a unique stable assembly. We conclude the paper with a discussion of how graph grammars can be used to direct the synthesis of parts floating in a fluid or for self-motive robotic parts.

We consider the task of assembling a large number of self controlled parts (or robots) into copies of a prescribed assembly (or formation). In particular, we introduce a way to synthesize, from a specification of the desired assembly, local controllers to be used by each part which, when taken together, have the global effect of assembling the parts. We pay careful attention to the time and space complexity of the synthesis procedure, showing that the size of the representation of the synthesized controller is polynomial in the size of the specification and that the computational power needed by the controller is low.

We describe a method for the decentralized phase regulation of two coupled hybrid oscillators. In particular, we prove that the application of this synchronization method to two hopping robots, each of which individually achieves only asymptotically stable hopping, results in an asymptotically stable limit cycle for the coupled system exhibiting the desired phase difference. This extends our previous work wherein the application of the method to two individually deadbeat-stabilized oscillators (paddle juggling mechanisms) was shown to yield the desired result. Central to this method is the idea that cyclic systems may be composed into a larger, aggregate, cyclic system. Its application entails moving from physical coordinates (for example, the position and velocity of each constituent mechanism) to the coordinates of phase and phase velocity. Within this canonical coordinate system we construct a model dynamical system, called a reference field, which encodes the desired behavior of each cyclic system as well as the phase relationships between them. We then force the actual composite system to behave like the model.

We introduce tools which help one to compose concurrent, hybrid control programs for a class of distributed robotic systems, assuming a palette of controllers for individual tasks is already constructed. These tools, which combine the backchaining of continuous robot behaviors with Petri nets, expand on successful work in sequential composition of robot behaviors. We apply these ideas to the design and verification of a robotic bucket brigade and to simple, distributed assembly tasks as found in automated factories.