A principled design methodology for minimalist multi-robot system controllers

To enable the successful deployment of task-achieving multi-robot systems (MRS), the interactions must be coordinated among the robots within the MRS and between the robots and the task environment. There have been a number of impressive experimentally demonstrated coordinated MRS; however, most have been designed through ad hoc procedures, typically providing task-specific, empirical insights with few contributions toward greatly needed general-purpose, principled design methods.; This dissertation presents a principled MRS controller design methodology applicable to minimalist MRS performing acyclic tasks. The methodology is formally grounded and provides precise definitions for the intertwined entities involved in any task-achieving MRS---the world, task definition, and the capabilities of the robots. Built from this formal foundation, the methodology includes a suite of systematic controller synthesis procedures. Through the execution of the synthesized controllers, system-level coordination is achieved through the use of a number of local control features: broadcast inter-robot communication, the maintenance of internal state, and both deterministic and probabilistic action selection. A probabilistic microscopic MRS modeling technique is integrated with the synthesis methods in order to provide system performance estimates during controller synthesis in order to optimize the resulting controllers. The presented controller design methodology is more than a pragmatic design tool. Based on its formal foundations, it provides a platform to formally characterize interesting relationships and dependencies among MRS task requirements, individual robot control and capabilities, and resulting task performance.; The design methodology is validated in a multi-robot construction task domain and a multi-foraging task domain through physically-realistic simulations and real-robot demonstrations. In these domains, the design methodology is used to synthesize a number of robot controllers, thereby demonstrating the utility of the controller synthesis methods as well as providing data for a comparative analysis on the use of different control features in coordinating minimalist MRS.