Thomas Ströder

 

Realizing Deterministic Behaviour from Multiple Non-Deterministic Behaviours

 

Abstract:

 

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 which is the first known implementation for solving
the behaviour composition problem, 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.