Reliable task decomposability for cooperative multi-agent systems

Abstract

One of the challenging issues in control of multi-agent systems is top-down formal design through global task decomposition such that fulfillment of local tasks result in satisfaction of the global specification. To tackle this problem, in our previous work, we proposed a divide-and-conquer approach, based on task automaton decomposition for two cooperative agents. The result proposed necessary and sufficient conditions under which a task automaton can be decomposed into its natural projections such that the parallel composition of local task automata bisimulates the original task automaton. It was also shown that for a decomposable task automaton, satisfaction of local task automata leads to the satisfaction of the global task automaton. Subsequently, this paper aims at investigating the task decomposability under failure to understand whether a previously decomposable task automaton can be still achieved by a team of two agents, in spite of some event failures. For this purpose, the result defines a notion of called passivity for failed events that reflects the redundancy of shared events and transforms the decomposability under event failures to the standard task automaton decomposability problem. Given the passivity of failed events, it is proven that a decomposable task automaton remains decomposable under failures if and only if any decision on order or choice of failed events with respect to other events can be accommodated by at least one agent; cooperative tasking of agents does not allow illegal interleaving of strings, after failures, and event failures do not impose nondeterministic local tasks. Illustrative examples are presented to elaborate the decomposability conditions under event failures and finally it is proven that under the proposed conditions, the global task can be still achieved by the team, in spite of passive event failures. © 2011 Chinese Assoc of Automati.