Automatic Synthesis of a Global Behavior from Multiple Distributed Behaviors

Abstract

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.\ntarget behavior from a set of available partially controllable\nbehaviors that execute distributively within a\nshared partially predictable, but fully observable, environment.\nAvailable behaviors stand for existing distributed\ncomponents and are represented with (finite)\nnondeterministic transition systems. The target behavior\nis assumed to be fully deterministic and stands for\nthe collective behavior that the system as a whole needs\nto guarantee. We formally define the problem within a\ngeneral framework, characterize its computational complexity,\nand propose techniques to actually generate a\nsolution. Also, we investigate the relationship between\nthe distributed solutions and the centralized ones, in\nwhich a single global controller is conceivable.