Automatic Synthesis of a Global Behavior from Multiple Distributed Behaviors

Sebastian Sardina, Fabio Patrizi, Giuseppe De Giacomo

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.

Subjects: 3. Automated Reasoning; 15.3 Control

Submitted: Apr 24, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.