Optimal task automaton decomposabilization for a class of global specifications

Abstract

This paper addresses the optimal task automaton decomposabilization applicable in top-down cooperative control of multi-agent systems. In [1], we proposed a divide-and-conquer approach for task automaton decomposition. In that result, given the global specification, represented as an automaton, and the logical behavior of the multi-agent system, modeled as a parallel distributed system, we proposed a necessary and sufficient condition for task automaton decomposition for two agents, such that the parallel composition of subtask automata is bisimilar to the original task automaton. This work completes the decomposition result of [1], by proposing a decomposabi-lization result. In this work, as the main contributions, firstly, we introduce a guideline for the basic design of private and common events, based on the specification. Secondly, after the basic event pattern attribution, the decomposability condition is checked, and if the task automaton is not decomposable, a sufficient condition is given to make it decomposable by assigning some of the private events to be common. The method is then proven to be optimal in the sense of minimum number of event conversions leading to minimum increment in the required communication capacity. An example is given to illustrate the concept and significance of optimal task decomposabilization. © 2010 IEEE.