Automatic synthesis of a global behavior from multiple distributed behaviors
Sebastian Sardiña, Fabio Patrizi, Giuseppe De Giacomo · 2007
We consider the problem of synthesizing a team of local behavior controllers to realize a fully controllable target behavior from a set of available partially controllable behaviors that execute distributively within a shared partially predictable, but fully observable, environment. Available behaviors stand for existing distributed components and are represented with (finite) nondeterministic transition systems. The target behavior is assumed to be fully deterministic and stands for the collective behavior that the system as a whole needs to guarantee. We formally define the problem within a general framework, characterize its computational complexity, and propose techniques to actually generate a solution. Also, we investigate the relationship between the distributed solutions and the centralized ones, in which a single global controller is conceivable. target behavior from a set of available partially controllable behaviors that execute distributively within a shared partially predictable, but fully observable, environment. Available behaviors stand for existing distributed components and are represented with (finite) nondeterministic transition systems. The target behavior is assumed to be fully deterministic and stands for the collective behavior that the system as a whole needs to guarantee. We formally define the problem within a general framework, characterize its computational complexity, and propose techniques to actually generate a solution. Also, we investigate the relationship between the distributed solutions and the centralized ones, in which a single global controller is conceivable.