Mattmüller et al. (2010) is a planner based on an adapted version of Hansen and Zilberstein (2001), a heuristic search algorithm that has theoretical guarantees to extract strong cyclic solutions for Markov decision problems. Kuter et al. (2008) makes use of Classical Planning algorithms to solve planning tasks. Fu et al. (2011) is similar to, but the main difference is that avoids exploring already explored/solved states, being more efficient than . Muise et al. (2012) is one the most efficient planners in the literature, and it is built upon some improvements over the state relevance techniques, such as avoiding dead-ends states. The main idea of these planners is selecting a reachable state s by the current policy that still is undefined in the current policy.

The behavior composition problem involves the automatic synthesis of a controller able to “realize” (i.e., implement) a target behavior module by suitably coordinating a collection of partially controllable available behaviors. In this paper, we show that the existence of a composition solution amounts to finding a strong cyclic plan for a special non-deterministic planning problem, thus establishing the formal link between the two synthesis tasks. Importantly, our results support the use of non-deterministic planing systemsfor solving composition problems in an off-the-shelf manner. We then empirically evaluate three state-of-the-art synthesis systems (a domain-independent automated planner and two game solvers based on model checking techniques) on various non-trivial composition instances. Our experiments show that while behavior composition is EXPTIME-complete, the current technology is already able to handle instances of significant complexity. Our work is, as far as we know, the first serious experimental work on behavior composition.