Supremal Realizability of Behaviors with Uncontrollable Exogenous Events

Abstract

The behavior composition problem involves the automatic synthesis of a controller able to "realize" (i.e., implement) a desired target behavior specification by suitably coordinating a set of already available behaviors. While the problem has been thoroughly studied, one open issue has resisted a principled solution: if the target specification is not fully realizable, is there a way to realize it "at best"? In this paper we answer positively, by showing that there exists a unique supremal realizable target behavior satisfying the specification. More importantly we give an effective procedure to compute such a target. Then, we introduce exogenous events, and show that the supremal can again be computed, though this time, into two variants, depending on the ability to observe such events.