Synthesis of Control Protocols for Multi-Agent Systems with Similar Actions

In this paper we investigate supervisor synthesis for a multi-agent system whose components' alphabets are bijectively similar to each other, i.e., they are "identical" under a pre-specified one-to-one relabeling scheme. We first introduce the concept of multi-agent systems with similar actions. Then we formulate a problem of control protocol synthesis, which aims to compute a supervisor template whose instantiations (via event relabeling) associated with local components form a distributed supervisor. After that, we show that protocol synthesis is always feasible for decomposable requirements, while the existence of a protocol is undecidable for an indecomposable requirement. In the former case, algorithms are presented to compute a protocol when a multi-agent system and a decomposable requirement is given, and in the latter case a conservative requirement decomposition algorithm is provided.