16-04-2013, 04:22 PM
A Formal Design Methodology for Coordinated Multi-Robot Systems
A Formal Design Methodology.pdf (Size: 1.12 MB / Downloads: 25)
Abstract
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 experimentally demonstrated coordinated MRS;
however, most have been designed through ad hoc procedures, typically providing task-specic,
empirical insights with few contributions toward general-purpose, principled design methods.
This proposal presents a formal MRS design methodology applicable to homogeneous, distributed
MRS performing sequential tasks in a Markovian world. We introduce a suite of systematic
methods for synthesizing satiscing controllers for robots constituting a MRS. Each of these
methods synthesizes a MRS that achieves system-level, task-directed coordination through the
use of a variety of local control features: inter-robot communication, the maintenance of internal
state, and both deterministic and probabilistic action selection. Complimentary to the synthesis
methods, we present two MRS modeling approaches that share a common formal foundation with
the MRS synthesis methods. The rst modeling approach is a Bayesian macroscopic model and
the second is a probabilistic microscopic model. Both models are capable of quantitatively predicting
the task performance of a given MRS. Together, the unied synthesis and analysis methods
provide more than just pragmatic design tools. Based on their common formal foundations and
integrated nature, they provide a platform from which to formally characterize some relationships
and dependencies among MRS task requirements, individual robot control and capabilities, and
resulting task performance.
Introduction
The study of multi-robot systems (MRS) has received increased attention in recent years. This is
not surprising as continually improving technology has made the deployment of MRS consisting
of increasingly larger numbers of robots possible. With the growing interest in MRS comes the
expectation that, at least in some important respects, multiple robots will be superior to a single
robot in achieving a given task.
Potential advantages of MRS over a single robot system (SRS) are frequently discussed in
the literature. For example, total system cost, it is frequently claimed, may be reduced by
utilizing multiple simple and cheap robots as opposed to a single complex and expensive robot.
Furthermore, the inherent complexity of some task environments may require the use of multiple
robots as the necessary capabilities are too substantial to be met by a single robot. Finally,
multiple robots are often assumed to increase system robustness by taking advantage of inherent
parallelism and redundancy. Therefore, negative eects on task performance caused by individual
robot failure or the dynamic addition or removal of individual robots can be minimized.
Problem Statement
From a few robots performing a manipulation task [9], to tens of robots exploring a large indoor
area [28, 37], to thousands of ecosystem monitoring nano-robots [63], as the number of robots
in the system increases, so does the necessity and importance of coordination. Coordination is
dened as \the act of regulating and combining so as to produce harmonious results" [1]. In the
context of MRS, coordination involves the appropriate spatiotemporal regulation of the robots'
actions such that the probability of a given task or goal being successfully achieved is maximized.
Multi-Robot System Formalism
We present a formalism that provides a principled non-task-specic framework for precisely
dening and reasoning about the intertwined entities involved in any task-achieving MRS {
the world, task denition, and the capabilities of the robots themselves, including sensing,
maintenance of persistent internal state, inter-robot communication, and action selection.
This formalism is specically designed to capture the relevant aspects of MRS executing a
sequential task in a Markovian world.
Multi-Robot System Synthesis
We present a suite of systematic methods for synthesizing controllers for robots constituting
a MRS. Each of these methods synthesizes a MRS that achieves system-level, task-directed
coordination through the use of a unique combination of local control features, such as
inter-robot communication, the maintenance of persistent internal state, and deterministic
and probabilistic action selection. We apply each of the systematic synthesis methods to
the design of MRS in a multi-robot construction task domain.
Multi-Robot System Formal Characterization
The formal MRS design methodology provides more than just a pragmatic design tool.
Based on its formal foundation, it can be used to formally characterize relationships and
dependencies among task requirements, individual robot control and capabilities, and resulting
task performance. This characterization facilitates formal answers to such fundamental
questions as `In what conditions is it necessary for the robots to be able to communicate?',
`In what conditions is communication alone insucient?', and `When are the use of internal
state and communication interchangeable?'. We provide such characterizations for a sample
of tasks in a multi-robot construction task domain.
Related Work
Our work is on the development of a formal MRS design methodology, including integrated MRS
synthesis and analysis methods. As such, in this chapter we review related work in the following
areas: 1) empirically demonstrated coordinated MRS in Section 2.1, 2) MRS analysis methodologies
in Section 2.2, 3) MRS synthesis methodologies in Section 2.3, 4) a brief review of related
work in the multi-agent systems community in Section 2.4, 5) and a review of work related to our
multi-robot construction case study in Section 2.5.