Behavior composition in the presence of failure

In this paper we articulate theoretical bases for robust behav-ior composition of multiple modules (e.g., agents, devices, etc.) by relying on the formal notion of simulation. Specifi-cally, we consider the problem of synthesizing a fully control-lable target behavior from a library of available partially con-trollable behaviors that are to execute within a shared, fully observable, but partially predictable, environment. Both be-haviors and environment are represented as finite state tran-sition systems. While previous solutions to this problem as-sumed full reliability, here we consider unforeseen potential failures, such as a module, or the environment, unexpectedly changing its state, or a module becoming temporarily unavail-able or dropping out permanently. Based on the notion of sim-ulation, we propose an alternative synthesis approach that al-lows for refining the solution at hand, either on-the-fly or par-simoniously, so as to cope with failures. Interestingly, it turns out that the proposed simulation-based technique is computa-tionally an improvement over previously known methods that assumed full-reliability