Behavior Composition in the Presence of Failure

Sebastian Sardina, Fabio Patrizi, Giuseppe De Giacomo

In this paper we articulate theoretical bases for robust behavior composition of multiple modules (e.g., agents, devices, etc.) by relying on the formal notion of simulation. Specifically, we consider the problem of synthesizing a fully controllable target behavior from a library of available partially controllable behaviors that are to execute within a shared, fully observable, but partially predictable environment. Both behaviors and environment are represented as finite state transition systems. While previous solutions to this problem assumed full reliability, here we consider unforeseen potential failures, such as a module, or the environment, unexpectedly changes it state; or a module becomes temporarily unavailable or drops out permanently, etc. Based on the notion of simulation, we propose an alternative synthesis approach and show how to refine the solution in hand, either on-the-fly or parsimoniously, so as to cope with failures. Interestingly, it turns out that the proposed simulation-based technique is computationally an improvement over previously known methods which assumed full-reliability.


Subjects: 11. Knowledge Representation; 7.1 Multi-Agent Systems

Submitted: Jun 16, 2008

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.