Please use this identifier to cite or link to this item:
Title: Cooperative tasking for multi-agent systems
Keywords: Cooperative Tasking, Automaton Decomposition, Fault-tolerant Cooperative Tasking, Task Decomposabilization, Multi-agent Systems, Decentralized Superv
Issue Date: 17-Aug-2011
Citation: MOHAMMAD KARIMADINI (2011-08-17). Cooperative tasking for multi-agent systems. ScholarBank@NUS Repository.
Abstract: It is an amazing fact that remarkably complex behaviors could emerge from a large collection of very rudimentary dynamical agents through very simple local interactions. However, it still remains elusive on how to design these local interactions among agents so as to achieve certain desired collective behaviors. This thesis aims to tackle this challenge and proposes a divide-and-conquer approach to guarantee specified global behaviors through local coordination and control design for multi-agent systems. The basic idea is to decompose a requested global specification into subtasks for each individual agent such that the fulfillment of these subtasks by each individual agent leads to the satisfaction of the global specification as a team. For this purpose, three issues are studied here: (1) task decomposition for top-down design, such that the fulfillment of local tasks guarantees the satisfaction of the global task, by the team; (2) fault-tolerant top-down design, such that the global task remains decomposable and achievable, in spite of some failures, and (3) the design of interactions among agents to make an indecomposable task decomposable and achievable in the top-down framework. To address the first question, namely cooperative tasking of multi-agent systems, it is firstly shown by a counterexample that not all specifications can be decomposed in this sense. Then, necessary and sufficient conditions are identified for the decomposability of a task for two cooperative agents; based on the decision making on the orders and selections of transitions, interleaving of synchronized strings and determinism of local tasks. The decomposability conditions are then generalized to the case of arbitrary finite number of agents, and furthermore, it is shown that the fulfillment of local specifications can guarantee the satisfaction of the global specification. Finally, a cooperative control scenario for a team of three robots is developed to illustrate the task decomposition procedure. The thesis then deals with the robustness issues of the proposed top-down design approach with respect to event failures in the multi-agent system. The main concern under event failure is whether a previously decomposable task can still be achieved collectively by the agents and if not, we would like to investigate that under what conditions the global task could be robustly accomplished. This is actually the fault-tolerance issue of the top-down design, and the results provide designers with hints on which events are fragile with respect to failures, and whether redundancies are needed. The main objective of this part of the work is to identify conditions on failed events under which a decomposable global task can still be achieved successfully. For such a purpose, a notion called passivity is introduced to characterize the type of event failures. The passivity is found to reflect the redundancy of communication links over shared events, based on which necessary and sufficient conditions for the reliability of the task decomposability and conditions on cooperative tasking under event failures are derived. As the next important question, the thesis aims to study whether one can modify the communication pattern between agents so as to make an indecomposable task decomposable. In particular, we would like to ask what is exactly needed to share by communication among agents such that an originally indecomposable task becomes decomposable. To answer this question, the decomposability conditions are revisited and all possible causes for indecomposibility are identified. As the main contribution of this part, the thesis then proposes a procedure, as a sufficient condition, to make an indecomposable deterministic task automaton decomposable in order to facilitate the cooperative tasking. This result may pave the way towards a new perspective for decentralized cooperative control of multi-agent systems.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
Karimadini-Mohammad.pdf1.47 MBAdobe PDF



Page view(s)

checked on Dec 16, 2018


checked on Dec 16, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.