Behavior Composition Optimization

1 Introduction

With computers now present in everyday devices such as mobile devices, credit cards, cars and planes or places like homes, offices and factories, the trend is to build embedded complex systems from a collection of simple components. For example, a complex surveillance system for a smart house can be "realised" (i.e., implemented) by suitably coordinating the behaviour (i.e., the operational logic) of hundreds (or thousands) of simple devices and artifacts-lights, phones, blinds, vacuum cleaners, video cameras. Such embedded systems can provide services that range from simple tasks, such as "turn on the lights in the bedroom," to more complex ones, such as "bring me a cup of coffee" or "handle house intruder" (by tracking and taking pictures of the intruder, toggling lights rapidly, and alerting the owner by email or phone). Other domains of applicability include composition of web services, factory robotic settings, and agent programming, among others.

The problem of automatically synthesising, that is, building, such an embedded controller-coordinator for a given desired, though not readily available, complex target system is called the behaviour composition problem and is the focus of this doctoral work. From an AI perspective, a behavior refers to the abstract operational model of a device or program, and is generally represented as a nondeterministic transition system. The classical behavior composition task has been extensively investigated in the recent literature (see [De Giacomo et al., 2013] for an extensive review). However, one open issue has resisted principled solutions: if the target behavior specification is not fully realizable, is there a way to realize it "at best"? The fact is that, many (if not most) realistic problem instances will have no complete realization and a (merely) "no solution" outcome may turn out extremely unsatisfactory.

∗This work was partially funded by the Australian Research Council (DP1094627 &DP120100332).

In this doctoral work, we answer such question positively. Concretely, we develop qualitative as well as quantitative principled extensions of the classical composition framework in which problem instances that are otherwise unsolvable in the classical sense, do have meaningful solution concepts beyond the highly unsatisfactory "no solution" answer. Importantly, we the proposed extensions strictly subsume the classical framework. Moreover, effective techniques for computing the new solution concepts are developed.

2 The Classical Composition Framework

The behavior composition problem amounts to synthesising a controller that is able to "realize" (i.e., implement) a desired, but nonexistent, target behavior module, by suitably coordinating a set of available behaviors [De Giacomo et al., 2013].

Technically, a behavior is a tuple B = 〈B, A, b0, δ〉, where (i) B is the finite set of states; (ii) A is the set of actions; (iii) b0 ∈ B is the initial state; and (iv) δ ⊆ B ×A×B is the behavior's (nondeterministic) transition relation: 〈b, σ, b′ 〉 ∈ δ denotes that action σ executed in behavior state b may lead the behavior to successor state b′ . An (available) system is a tuple S = 〈B1, . . . , Bn〉, where each Bi = 〈Bi, A, b0i, δi〉 is referred to as an available behavior in S (over shared actions A). The target behavior is just a deterministic behavior. Informally, the behavior composition task is stated as follows:

Given a system S and a target behavior T , is it possible to (partially) control the available behaviors in S in a step-by-step manner-by instructing them on which action to execute next and observing, afterwards, their evolution-so as to "realize" the desired target behavior, that is, it appears as if one was actually executing the target module T .

Though technically involved, one can formally define when a so-called controller, a function taking a history (i.e., a run) of the system and the next action request and outputting the index of the available behavior where the action is being delegated, realizes the target behavior. Such controllers are called exact compositions, solutions to the composition problem guaranteeing the complete realization of the target in the system. It was shown that, while decidable, checking the existence of exact compositions is a demanding task, namely, EXPTIME-complete [De Giacomo et al., 2013].

All the literature on behaviour composition has only dealt with exact compositions. This poses a major limitation in that for many, if not most, problem instances there will be no composition at all. For such cases, a (merely) "no solution" outcome is extremely unsatisfactory.

3 Quantitative Optimization

In order to better deal with non-solvable composition instances, a framework in which non-exact controllers can be compared is required. To that end, in [Yadav and Sardina, 2011], we proposed an extension of the classical composition problem that goes beyond strict uncertainty and judging how well a controller is expected to perform.

The outcome of this work is a decision-theoretic behavior composition framework, in which the task is to maximize the so-called expected realizabability of a target behavior T in an available system S. To facilitate that, the two sources of uncertainty ought to be quantified. First, the uncertainty on the nondeterminism in available behaviors needs to be measured. Second, the relative importance of each potential target request at a given state is specified. Note these are reasonable assumptions in many settings, in which such information is readily available to the modeller. For example, the failure rate of a gripper arm when grasping an object may be available to the domain expert, who may also encode that, in a gardening maintenance target module, watering plants is a more frequent and important action request than collecting fruits.

With the uncertainty represented into the model, we defined the notion of optimal composition controllers based on the notion of "expected target realizability." Clearly, the new framework is able to output "best" controllers even for problems that do not accept exact controllers. Importantly, we characterized when a best controller is also an exact composition, thus subsuming the classical setting.

Second, we provided a translation of a decision theoretic behavior composition problem into a Markov decision process (MDP), and show that finding an optimal policy for such MDP amounts to finding an optimal composition.

4 Qualitative Optimization

When the uncertainty cannot be quantified, an account of composition optimization in a purely strict uncertainty setting is required. In [Yadav and Sardina, 2012] we developed a qualitative composition theory for "supremal realizablilty." Intuitively, the overarching idea here is to look for those parts of the target module that can be realized with the available modules, and provide this as an (approximate) solution.

So, relying on the well-established formal notion of simulation [Milner, 1971] in computer science, we characterize the notion for the closest target module ˜ T (to the original target T ) that admits a complete implementation with the behaviors at hand in system S: ˜ T is the supremal realizable fragment (or optimal approximation) of T .

Of course, it is expected that such alternative target ˜ T will generally provide less functionalities than the original one. More concretely, some execution paths may be impossible to generate with the new target (e.g., it may no more be feasible to play video games when listening to music). Moreover, the alternative target may accommodate less "freedom" of choices in executions (e.g., when requesting to watch a movie, one may now need to commit to whether one will be playing a video game or listening to radio afterwards). Nonetheless, all requests as per ˜ T will be always fulfilled.

Importantly, we proved that the supremal realizable target is indeed unique. Moreover, we showed the soundness of the supremal characterization by showing that supremals amount to synthesising maximal controllers, the best controllers that one could hope for. Finally, we studied effective techniques to compute supremal fragments using model checking techniques. However, so far, tight complexity bounds were identified for the special case of deterministic systems only.

5 Conclusion

The overarching objective of this doctoral project is to develop behavior composition frameworks, and techniques for the actual computation of solutions, that will accommodate non-solvable problem instances. The need for dealing with approximate solution concepts was first recognized by Stroeder and Pagnucco [2009], but has resisted principled approaches. Since those instances are arguably common ones in many realistic scenarios, this will make the behaviour composition problem applicable to a much wider range of cases.

To achieve this, we propose quantitative and qualitative frameworks for behavior composition optimization. To our knowledge, this is the first account that is able to accommodate instances with no complete solutions, while strictly subsuming the standard problem formulation. Remaining work in the topic includes a hybrid account integrating both approaches, finding tight bounds for the general qualitative setting, and adapting our recent planning technique [Miguel et al., 2013] to supremal realizations.