Automatic Synthesis of New Behaviors from a Library of Available Behaviors

Giuseppe De Giacomo, Sebastian Sardina

We consider the problem of synthesizing a fully controllable target behavior from a set of available partially controllable behaviors that are to execute within a shared partially predictable, but fully observable, environment. Behaviors are represented with a sort of nondeterministic transition systems, whose transitions are conditioned on the current state of the environment, also represented as a nondeterministic finite transition system. On the other hand, the target behavior is assumed to be fully deterministic and stands for the behavior that the system as a whole needs to guarantee. We formally define the problem within an abstract framework, characterize its computational complexity, and propose a solution by appealing to satisfiability in Propositional Dynamic Logic, which is indeed optimal with respect to computational complexity. We claim that this problem, while novel to the best of our knowledge, can be instantiated to multiple specific settings in different contexts and can thus be linked to different research areas of AI, including agent-oriented programming and cognitive robotics, control, multi-agent coordination, plan integration, and automatic web-service composition.