Realising Deterministic Behavior from Multiple Non-Deterministic Behaviors

This paper considers the problem of composing or scheduling several (non-deterministic) behaviors so as to conform to a specified target behavior as well as satisfying constraints imposed by the environment in which the behaviors are to be performed. This problem has already been considered by several works in the literature and applied to areas such as web service composition, the composition of robot behaviors and co-ordination of distributed devices. We develop a sound and complete algorithm for determining such a composition which has a number of significant advantages over previous proposals: a) our algorithm is different from previous proposals which resort to dynamic logic or simulation relations, b) we realized an implementation in Java as opposed to other approaches for which there are no known implementations, c) our algorithm determines all possible schedulers at once, and d) we can use our framework to define a notion of approximation when the target behavior cannot be realized.

Thomas Ströder, Maurice Pagnucco