Behavior Composition in the Presence of Failure

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Contents

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.