Synchronized task decomposition for two cooperative agents

One of the most important issues in top-down cooperative control of multi-agent systems is to decompose the global specification in order to design the local supervisors such that the fulfilment of these sub-specifications by each individual agent, results in the satisfaction of the global specification as a team. Given the global desired behavior, represented as an automaton, and the distribution of its events into local plants, the question is whether it is always possible to decompose the task automaton into a finite number of sub-automata such that the parallel composition of sub-automata is bisimilar to the original task automaton, and if not, what are the necessary and sufficient conditions for such decomposability. It is shown that it is not always possible to do so. We then present the necessary and sufficient conditions for decomposability of a given task automaton such that the parallel composition of these local task automata bisimulates the original task automaton. It is found that the task automaton is decomposable if and only if it satisfies some symmetry properties, representing independence of the order and the choice of private events from different local event sets, and some properties on the interleaving of strings that share the same first appearing common event. This result will help to design the local controllers from the global logical specification, to be used in the top-down cooperative control of distributed systems.