Sardiña: Automatic Synthesis of New Behaviors from a Library of Available Behaviors

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 ob-servable, 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 non-deterministic 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 for-mally define the problem within an abstract frame-work, 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 mul-tiple specific settings in different contexts and can thus be linked to different research areas of AI, in-cluding agent-oriented programming and cognitive robotics, control, multi-agent coordination, plan in-tegration, and automatic web-service composition.