Behavior composition as fully observable non-deterministic planning

Abstract

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 systems for solving composition problems in an off-the-shelf manner. We then empirically evaluate three state-of-the-art synthesis systems (a domain-independent automated planne..