Philippe Hérail
email: philippe.herail@laas.fr

Arthur Bit-Monnot
email: abitmonnot@laas.fr

Learning Operational Models from Demonstrations: Parameterization and Model Quality Evaluation

When acting in non-deterministic environments, autonomous agents must balance between long-term, complex goals with unpredictable events and reactive behavior. In this context, hierarchical operational models are attractive in that they allow the execution of complex behavior either in a purely reactive fashion or guided by a planning process. Just like for HTN models with which they share most characteristics, one key bottleneck in the exploitation of operational models is their acquisition. In this paper, we introduce an algorithm for learning hierarchical operational models from a set of demonstrations. Given an initial vocabulary of tasks and some demonstrations of how they could be achieved, we present how each task can be associated to a set of methods capturing the operational knowledge of how it can be achieved. We present the structure of the learned models, the algorithm used to learn them as well as a preliminary evaluation of this algorithm.

Introduction

To allow an autonomous agent to operate in its environment, we can differentiate two family of approaches, split by the way they select their next action: reactive or deliberative. While a reactive approach may cover several distinct acting techniques, these often present the common characteristic of being fast to act but short-sighted. Meanwhile, deliberative approaches typically rely on planning to consider longterm impacts of a decision, at the cost of increased deliberation time. In order to find a compromise between both these approaches hierarchical operational models [START_REF] Ghallab | Automated Planning and Acting[END_REF] have been developed along with acting engines such as in [START_REF] Patra | Deliberative Acting, Planning and Learning with Hierarchical Operational Models[END_REF]). This combination allows to have models that distinguish between different ways to achieve a given task through methods. These hierarchical models allow the agent to act either reactively, selecting one method without any reasoning about the future, or to make more elaborate choices. Furthermore, the hierarchical aspect allows to reduce the possibilities that need to be considered at any given time, similarly as in hierarchical planning.

Even though these hierarchical models are a formalism that allows to act more efficiently while remaining interpretable by human engineers, it is cumbersome to design such models from scratch. This difficulty stems from the quickly exploding number of possible contexts that need to be considered when carrying out even basic tasks in a simple environment. To address this issue, we intend to allow the agent to learn such operational models from previously observed execution traces, and in particular the ones resulting from a tutor's demonstration.

The goal of such a learning system would be to be able to solve any previously demonstrated tasks through a solution of at least equivalent quality to the demonstrated one. It should also be able to generalize the demonstrations to solve new unseen tasks, or previously demonstrated tasks in a new environment. This is done by learning, for any given task in the considered domain, a set of methods that achieve the high-level objectives associated to the task. This set of methods should cover all possible ways of achieving this task with the exception of clearly suboptimal ways. Any method should be associated with a validity scope that define whether it is applicable in a given state. When applicable, it should achieve the task.

Intuitively, if a learned operational model has these desirable properties, an acting engine facing a task to achieve could pick any applicable method and have the guarantee that it will fulfill the objectives associated to the task. While this might lead to suboptimal behavior, it should be possible for an automated planner to guide the choice of the method to obtain the optimal behavior.

The objective of this paper is to present a method for building hierarchical operational models based on past experiences. The experience takes the form of execution traces that can be the result of the agent's own activity or of demonstrations by a tutor. The agent is assumed to have a fixed set of primitive capabilities and to act in a Fully Observable Non-Deterministic (FOND) environment.

Related Work

Over the years, several approaches have been developed to learn hierarchical models.

HTN-MAKER [START_REF] Hogg | HTN-MAKER: Learning HTNs with Minimal Additional Knowledge Engineering Required[END_REF]) learns Hierarchical Task Networks (HTNs), for use in fullyobservable deterministic domains from execution traces. This approach uses tasks annotated with preconditions and postconditions so as to extract sequences that allow to achieve the postconditions starting from a state where the preconditions hold. The method was later extended by [START_REF] Hogg | Learning Hierarchical Task Networks for Nondeterministic Planning Domains[END_REF] to handle non-deterministic domains, through the use of a right recursive structure instead of sequences. However, the models learned are restricted to a limited task and method structure, resulting in rather flat hierarchies, which limits the guidance offered to an agent using them for planning.

HTNLearn [START_REF] Zhuo | Learning Hierarchical Task Network Domains from Partially Observed Plan Traces[END_REF]) also learns HTNs with similarly annotated tasks, through converting the learning problem into one of constraint satisfaction, building the constraints from, e.g., the ordering of tasks within the examples and the state preceding the application of a method. The problem is then solved using a MAXSAT approach and the solution converted back into an HTN model. While this approach does not handle nondeterminism, it supports partially observable states. A similar approach is even able to use partial, disordered input traces [START_REF] Zhuo | Learning Action Models from Disordered and Noisy Plan Traces[END_REF].

Recently, the learning of Hierarchical Goal Networks (HGNs) structure instead of HTNs, for nondeterministic domains, has been proposed as a preliminary work by Fine-Morris and Muñoz-Avila (2019), leveraging a vector representation of the states and unsupervised learning procedures to learn such networks while limiting the burden of annotating demonstration data.

Due to their similarities with HTNs, some work aiming at learning grammars is relevant and in particular the work on learning Combinatory Categorial Grammars (CCGs) for plan and goal recognition [START_REF] Geib | Recognizing Plans with Loops Represented in a Lexicalized Grammar[END_REF][START_REF] Kantharaju | Extracting CCGs for Plan Recognition in RTS Games[END_REF]. While the learned CCGs are not always practically usable, the authors propose several ideas for extracting interesting patterns from a set of execution traces.

The algorithm for learning probabilistic primitive action models (i.e. not hierarchical) presented by [START_REF] Pasula | Learning Symbolic Models of Stochastic Domains[END_REF] develop interesting solutions for handling the specificities of FOND environments.

Work has been done on the automated learning of Behavior Trees (BTs), a common framework for implementing hierarchical, reactive operational models. [START_REF] Colledanchise | Learning of Behavior Trees for Autonomous Agents[END_REF] and [START_REF] Zhang | Learning Behavior Trees for Autonomous Agents with Hybrid Constraints Evolution[END_REF] develop techniques to efficiently apply genetic programming to these structures.

Learning Problem Operational Model

For an agent acting in its environment, an operational model, as defined by [START_REF] Ghallab | Automated Planning and Acting[END_REF], represents an agent's knowledge about how to carry out a given activity in its environment. In this work, we are specifically interested in nondeterministic, fully observable environments.

We define an operational model O as an HTN-like structure which can be written as a tuple O = (T, A, M ) where T is a set of abstract tasks, A a set of primitive actions and M a set of possible methods decomposing the tasks t ∈ T into subtasks {t d | t d ∈ {T ∪ A}}. We consider the tasks to be possibly annotated with postconditions, similarly as [START_REF] Hogg | HTN-MAKER: Learning HTNs with Minimal Additional Knowledge Engineering Required[END_REF].

A primitive action a ∈ A models the basic acting capabilities of the agent, and represent directly executable prim-itives. They are represented using an identifier and a set of parameters, such as a = action name(arg 1 , . . . , arg n ). We do not assume any knowledge on the preconditions and effects of a primitive action. Furthermore, as we consider a non-deterministic environment, there is no guarantee that applying an action twice in the same state will produce an identical result.

An abstract (or non-primitive) task t ∈ T is defined as a tuple t = (P ost t , M t ), where P ost t are the postconditions of the task, that is the predicates that must hold after executing t for it to be considered a success. These are especially important in nondeterministic domains. A task without postconditions is considered successful whenever one of its method has been executed without failure. M t is the set of methods decomposing t.

A method m ∈ M t is a tuple m = (P re m , N m ), where P re m are the preconditions of the method, and N m is a task network defining a way to decompose t into subtasks. This task network represents a way to advance the task t towards its intended effects, in the case of a task with postconditions, or a way to achieve t if P ost t = ∅. A method is applicable in a given state s iff its preconditions hold in this state. For the sake of simplicity, we will assume that the set N m of subtasks is totally ordered.

We define an acting problem as an initial task network N p , representing the activity we wish to carry out, as well as an associated environment and a starting state s i described by a set of boolean state variables. When trying to solve an acting problem p, we associate it to an operational model O that will be used to select the actions to execute. We consider that at any instant, the current state s is fully observable and that it only evolves when a primitive action is executed (i.e. there are no exogenous events). This evolution may however be nondeterministic.

Acting with an Operational Model

To act with an operational model, abstract tasks are refined down to a sequence of executable primitive actions. This refinement is achieved through the methods associated with the tasks: each time the agent must choose an action to execute, the current best applicable method decomposing the task at hand is chosen. The process is iteratively repeated until a sequence of tasks starting with a primitive action is obtained. This sequence is then executed until a non-primitive task is encountered, at which point the same process is applied again. The choice of the best method may be done either reactively or deliberatively. In the first case, the best method is chosen greedily according to some metric, while in the second one an acting engine, such as the one described by [START_REF] Patra | Deliberative Acting, Planning and Learning with Hierarchical Operational Models[END_REF], may use planning techniques to select a method considering the long term implications of the actions.

During the refinement of a task t using the method m starting in a state s, several failure types may occur:

1. A primitive action fails to be executed, causing the whole parent method to be considered a failure. 2. A non-primitive descendant t from m has no applicable method. Then, the parent method of t is considered to have failed. 3. t can be completely refined, but the postconditions of t do not hold in the final state. This case is obviously valid only for a task t such that P ost t = ∅.

In the first two cases, when a method m decomposing a task t is detected as having failed, then some retrial strategy must be used to continue acting. A simple strategy could be to try another applicable method m applicable in the current state s. If no such method is available in the hierarchy, then the failure is to be propagated upwards to the parent task t, until we reach either a task with an applicable method or the root task, the latter case leading to a failure to solve the acting problem.

Learning of an Operational Model

Inputs to the Learning Problem For the learning problem itself, we consider as input a fixed set A of primitive actions as well as a vocabulary of non-primitive tasks T I .

Recall that each primitive action has the form action name(param 1 , . . . , param n ) and corresponds to a primitive directly executable by the agent. For a nonprimitive task t I ∈ T I , we assume its postconditions P ost t I to be non-empty, as they are required to assess the success of the task execution in the agent's nondeterministic environment. Note that these postconditions might be learned independently of the methods, which is out of the scope of this paper.

Then, for each task t I ∈ T I , the agent is given a set D t I of demonstration traces from the tutor. Each trace d ∈ D t I is an alternating sequence of states and tasks (either primitive or non-primitive), starting from a given initial state and ending in a final state in which the task t I has been successfully achieved. d is considered optimal and maximally abstract with regard to the initial task vocabulary: for every demonstrated task, no other more abstract task from the initial vocabulary T I may be used to abstract a subsequence of d, and each demonstration is optimal according to a chosen metric. For a case where actions are uniform in cost, one may naturally consider the total number of primitive actions required to achieve t I as the optimality metric.

Learner Objectives Given a learned operational model and an acting problem, we say that the operational model solves the problem if, when used by the acting engine, it allows to refine a given task network into an executable sequence of primitives. Considering a successful solution to the problem, we define the soundness metric as the number of failed method execution (i.e. number of times we had to resort to recovery behavior) within the execution, to allow the evaluation of the quality of the learned preconditions of the methods. We also define the efficiency metric as the ratio between the cost of the executed behavior and the cost of executing an optimal model. These metrics have been defined for a single acting problem. To assess the generalization capabilities of the model, we should consider a set of acting problems not encountered during learning. We define three metrics over this test set, namely the ratio of solved problems (coverage), the average number of method failures (average soundness), and the average efficiency.

m do t m check do t t m 1 m 2 m 3 (
Finally, to evaluate the algorithm as a whole, we should consider a set of demonstration and a set of acting problems. The performance of the algorithm is defined as the average performance of the model produced from the demonstrations on the acting problems, as defined in the previous paragraph.

Approach to Model Learning

In our approach, we develop operational models designed to handle nondeterministic environments. To this end we distinguish tasks with and without postconditions, as shown in figure 1, presenting the structural differences a task t with postconditions and a task t without.

In the case of t, (Post t = ∅, figure 1a), we observe that t has two methods, m check and m do , and a right recursive structure. The former has no subtask, and its preconditions correspond to the postconditions of t, while the latter has no preconditions and two subtasks, do t and t, recursively. The methods m i of do t encode different possible ways to act for the agent, with the intent to try and achieve t.

When decomposing t, m check has priority over m do , and is used to assess whether the goal associated with t has been achieved. We can note that t will thus be decomposed recursively until its associated goal is achieved, even in the case of unexpected events, provided there is a valid m i to handle it, as in HTN-MAKER [START_REF] Hogg | Learning Hierarchical Task Networks for Nondeterministic Planning Domains[END_REF]. Therefore, when decomposing t, in the case where its postconditions do not hold, we will choose one of the available method of do t , refine and execute it, and then try to refine the original instance of t again, hoping to have achieved the intended effects. It should be noted that a method of a task may either represent a way to completely achieve it, or merely to advance it (or recover from mistakes), leveraging the recursive call to finally achieve the original endeavor.

In the case of t , a task without postconditions (Post t = ∅, figure 1b), we have a task with a more standard structure, as a method will then always be considered successful if it is refined and executed to its completion. Indeed, it would not be possible to decide if the task should be recursively retried or not.

Requirements of Model Selection

Let us now give an initial intuition about the shape of models that could be learned and the implication for the learn- ) that could be generated based on two example sequences (figure 2a). All candidate models share the same recursive structure that we just saw (figure 2b) and only differ in the refinement of the do task.

The first one (2c) allows the choice of any of the four primitive actions {a, b, c, d}, each placed in a specific method. This model relies on the recursion to repropose the same choice until the task's postconditions are achieved. While this model allows building any sequence of actions it does not help the agent towards a meaningful sequence based on demonstrations. The second model (2d) takes the opposite approach and records each known trace into a method. This model is obviously strongly tied to the demonstration set and would fail to generalize to new problems. In between these two extreme, we have the models (2e) and (2f) that take different options to abstract common subsequences. The former encodes the repeated a b sequence in a single method and relies on the recursive call to complete the sequence. The latter delays the choice between c and d to after the execution of a and b, using a synthetic task t s .

These four models are just a handful of examples among the many possible models that could be generated. Denoting as Θ the set of possible models, the objective of a learning system is to find, or at least approach, the optimal model

θ * ∈ Θ θ * = arg min θ∈Θ cost(θ)
where cost(θ) is a function that measures the cost of a particular model and should typically account for the size of the model as well as its capacity to solve both demonstrated and unseen problems. With this in mind we now turn our attention to the characterization of the set of possible models Θ.

In a later section, we will propose a cost function to evaluate the models.

Generation of Candidate Operational Models

At a high level, the goal of the learning problem is to generate a model where some subtasks group together behaviors that happen repeatedly, with a sensible parameterization of methods depending on the current task, as well as reasonable preconditions to limit the search effort of the acting engine. It is easy to imagine an iterative process for this: we may extract some subsequence as a new task t, with a single method m 1 consisting of this subsequence. Once this is done, we may find another subsequence that achieves a similar goal, but using different tasks, thus allowing us to add a new method m 2 to t. Next, we may be able to extract a new task t using t as a subtask of this method. This process is to be repeated until it produces a model that become too complex, not improving the score defined in the previous section.

Devising such an iterative learning process is however error-prone as it is easy to get stuck in a local minimum due to bad decision in the early stages of learning. Because the quality of a model depends not only on its structure, but also on its parameterization, in order to efficiently develop this latter part of the learning algorithm, we developed a method for generating a large number models so as to conduct a preliminary evaluation and relegate a more efficient exploration of the set of possible models to future work.

Considering a set of primitive actions and a set of demonstrations, it is easy to imagine a way to generate a number of operational models that can be used to achieve any of the given demonstration. For instance, we could start with a basic flat model, and add any number of possible subtasks whose methods correspond to arbitrary sequences of primitive actions, with possible duplications. This model can al-ways fall back to choosing one of the single primitive actions if no subtask's method can be used, and therefore will always remain valid. As an infinite number of possible sequences can be used as subtasks, an infinite number of such models can be elicited, thus foregoing an exhaustive generation procedure. We therefore chose to restrict ourselves to a certain structure, described below, so that we could generate models exhaustively within this limited search space.

Considering an initial set of primitive actions {a, b, c, d}, we try and find all the ways to partition it, i.e. P = ({{a}{b}{c}{d}} , {{a, b}{c}{d}} , {{a, b, c}{d}} , . . . ). For each new set in P , we recursively apply the same process to each subpartition. The resulting sets will have a format such as {{{a}{b, c}}{d}} each of which corresponding to a particular model (e.g. see the one presented in figure 3 for this particular example). To build such a model, we consider each level, starting from the first one (here, this first level contains the subpartitions {{a}{b, c}} and {d}), considering that it shows different ways to decompose some task t that has been demonstrated. We then consider the subpartitions. If it is not further subpartitioned (as {d} here), we create a method refining t down to the primitive action contained. Otherwise, we create a subtask st and a method that refines t into st and recursively apply the same procedure, considering that this subpartition shows ways to decompose st. With this procedure, we will obtain models that are limited, as they will, e.g., never use the same primitive to decompose two different subtasks, nor will they contain methods that decompose as sequences of tasks. However, this generation process produces a number of models that scales exponentially with the number of primitive tasks given as input, due to the number of possible subpartitions of a set, therefore quickly making the use of the generated model set for evaluating our algorithm impractical. Adding more possible model structures would only worsen this issue, thus warranting the use of some local search procedure.

While this generation procedure allows us to generate new model structures, we still need to parameterize their tasks and methods to evaluate them properly on the existing demonstration set, and to eventually use the corresponding models for acting. This parameterization as well the extraction of methods' preconditions is detailed in the next section.

Parameters & Preconditions Extraction

For each method in the model, we need to identify the parameters that should be passed to its subtasks. When considering the abstract tasks, we need to distinguish two cases:

1. The set T I of tasks given as the starting vocabulary for which arguments and postconditions are known. 2. The tasks that are inferred during learning, by grouping common subsequences for example, for which arguments must be extracted. This second type of tasks are called synthetic tasks and their set is called T S . For these tasks, we do not consider the identification of intended effects in this work.

Process Overview Parameterization is a bottom-up, iterative process that selects a task or method whose subcomponents are already parameterized (i.e. their parameters are given or were previously identified). Those subcomponents are analyzed to identify the parameters of the current task/method, which in turn will enable the analysis of tasks/methods higher-up in the hierarchy.

1. We first consider any method m whose subtasks are all parameterized. For each such method we:

• Identify its parameters based on the parameters of its subtasks • Extract its preconditions by considering each state that precedes an instance of the method in the demonstrations.

2. For any synthetic task t ∈ T S whose methods are all parameterized (as a result of the previous step), we identify the parameters of t based on the ones of its methods. 3. For any initial task t ∈ T I whose methods are all parameterized (as a result of the previous step), we associate the parameters of t to the parameters of its methods.

We repeat this process until all tasks and methods are parameterized, resulting in a bottom up identification of the parameters of the tasks and methods.

For this process, we need to know how our model would have been used if it had to generate the demonstrations, while not having yet access to its parameterization. To this end, we use the technique developed for HTN plan verification [START_REF] Höller | Compiling HTN Plan Verification Problems into HTN Planning Problems[END_REF]) to obtain such a trace from an HTN planner. To use this strategy with a candidate model O c , we generate an HTN model by removing every argument and method precondition. We also replace each instance of a primitive action a by a new task a obs whose methods each correspond to a single observation of an instance of a in the currently considered demonstration d. Each such method has a single precondition: being currently at the right point in the sequence. This means the method containing the 6 th observation in the demonstration can only be selected between adding the 5 th and 7 th to the final plan.

Identifying the Arguments of a Method from its Subtasks When extracting the arguments of a method, we leverage the fact that we know the arguments of its subtasks as well as, for each method demonstration instance, their mapping to the ground arguments.

This allows us to unify the arguments of the subtasks as much as possible, by identifying the subtask arguments that are always bound to the same constant in each example. For instance, consider for a method m with st 1 (X 1 , X 2 ) and st 2 (Y 1 , Y 2 , Y 3 ) as its subtasks. In this example, without any unification, the arguments of m could be (X 1 , X 2 , Y 1 , Y 2 , Y 3 ), that is, the union of the arguments of its subtasks. If X 1 and Y 1 are bound to the same constant in each instantiation of the method (over all traces), we can unify them using a new variable Z 1 . Therefore, the arguments of m become (Z 1 , X 2 , Y 2 , Y 3 ), and its subtasks become parameterized as

st 1 (Z 1 , X 2 ) and st 2 (Z 1 , Y 2 , Y 3 )
To make the explanation clearer, let us consider an example deliver with truck method as presented in figure 4b, considering we also have two demonstration instances of this method, as presented in figure 4a. Since T 1 and T 2 are always bound to the same variable in each of the examples, we can introduce a new variable T , to replace each occurrence of T 1 or T 2 . This leads to the method presented in figure 4c.

E1 : s 1 0 → goto truck (t1, l1, l2) → s 1 1 → unloadtruck(t1, p1) → s 1 2 E2 : s 2 0 → goto truck (t2, l3, l4) → s 2 1 → unloadtruck(t2, p1) → s 2 2 (a)
Example traces associated to the method. Extracting the Preconditions of a Method Having identified the arguments of a method m, we can extract its preconditions. As we know the mapping between method arguments and constants, we can easily filter the predicates in the states preceding every instance of m to keep only the ones fully specified by its arguments. Then, we take the intersection of these sets of predicates.

                       package in (t1, p1) truck at(t1, l1) road(l1, l2) sunny(l2) truck at(t2, l2) T → t1 P → p1 L1 → l1 L2 → l2                                               package in(t2, p1) truck at(t2, l3) road(l3, l4) cloudy(l2) truck at(t3, l2) T → t2 P → p1 L1 → l3 L2 → l4                        s 1 0 s 2 0 (d)
Consider the method deliver with truck from figure 4, and the starting states as defined in figure 4d. Then, using our knowledge of the mappings between the method parameters and the examples' constants, we can first exclude the last truck at predicate from both examples, as at least one constant is not unified with a parameter. The preconditions of the method are therefore the intersection of the lifted and filtered states, i.e. P re = {package in(T, P ), truck at(T, L 1 ), road(L 1 , L 2 )}.

Associating the Arguments of a Method to the Known Arguments of the Task it achieves When learning methods for a task t in our initial vocabulary T I , we have to map the (known) arguments of t to the arguments of its methods, which were extracted as described previously. These arguments are mapped in the same way as when unifying arguments for methods subtasks. Having some examples of decompositions of t, we follow the same logic as for the subtasks in a method: all parameters that are always bound the same value are unified.

Consider a task t(Z 1 , Z 2 , Z 3 ) being decomposable with two methods, m 1 (X 1 , X 2 ) and m 2 (Y 1 , Y 2 , Y 3 , Y 4 ). Based on the traces of equation 1, we can replace X 1 and Y 1 with Z 1 , X 2 with Z 2 and Y 3 with Z 3 . We can therefore rewrite the methods' arguments as

m 1 (Z 1 , Z 2 ) and m 2 (Z 1 , Y 2 , Z 3 , Y 4 ).    E1 = t(a, b, c) : m1(a, b), t(a, b, c) : m2(a, c, c, d) E2 = t(x, y, x) : m1(x, y) E3 = t(m, n, o) : m2(m, n, o, q) ⇒              E1 :      (X1 → a), (X2 → b) (Y1 → a), (Y2 → c), (Y3 → c), (Y4 → d) (Z1 → a), (Z2 → b), (Z3 → c) E2 : (X1 → x), (X2 → y) (Z1 → x), (Z2 → y), (Z3 → x) E3 : (Y1 → m), (Y2 → n), (Y3 → o), (Y4 → q) (Z1 → m), (Z2 → n), (Z3 → o) (1)
To illustrate this with an example, let us consider the task described in figure 5a that represents the act of delivering a package P to a location L. It can be achieved either through a method delivering it via a truck (the same as described in the previous paragraph) or by a plane. Assuming we have some supporting examples, we can unify the arguments as presented in figure 5b.

Extracting the Arguments of a Synthesized Task from the Arguments of its Methods We now turn our attention to the identification of the arguments of synthetic tasks. This is done by leveraging the context of the instances of t to find method parameters that are always bound to the same constant in a given context.

Let us consider a new task t ∈ T S , for which we do not know the arguments, and whose methods' arguments have been identified. We assume that t has a parent task t p , possibly several levels higher in the hierarchy, whose arguments are known (i.e. t p ∈ T I ). We note C t the context surrounding an instantiation of t, defined as the variables bound from the instantiation of t p and from all the definitive parts of the methods' instantiations on the path down to t. Figure 6a shows an example for such a task t, for which a context would be an instantiation of

X 1 , X 2 , Y 1 , Y 2 , Z 1 . mdo(X1, X2) mdo,1(?) mt p,s1 (?) tp(X1, X2) mcheck dot p (X1, X2) tp(X1, X2) tp,s 1 (?) a(Y1, Y2) mdo,2(V1, V2, V3) b(V1, V2 , V3) t(?) c(Z1)
mt,2(W3) mt,1(W1, W2) mt,3(W4, W5, W6)

(a) Example task structure for contexts. After extracting all the contexts from the demonstrations, we wish to find a valid and relevant parameterization of t, such as the one of figure 6b. A valid parameterization is a mapping from args(t) (the set of arguments of t) to args(M t ) (the set of arguments of its methods) such that ∀a i ∈ args(t), ∃b j ∈ args(M t ) : a i → b j .

args(t) = {a1, a2} a1 → {W1, W3} a2 → {W4, W5} (b)
A single task parameter a i ∈ args(t) may map to several method arguments in args(M t ). The core process for identifying the a i arguments lies in identifying subsets of the methods' parameters that can be bound to the same task parameter. Intuitively, two methods parameters b j and b k can be bound to the same task parameter a i iff:

• there is a context C t where both b More formally, a parameterization of a task can be seen as a set of grouped methods parameters U = {U 0 , . . . , U n } where each U i is the subset of args(M t ) that the a i parameter maps to. To be valid, a parameterization U must be such that:

b j , b k ∈ U i ⇒ ∃C t : b j ≡ Ct b k C t : b j ≡ Ct b k U i ∩ U j = ∅ if i = j
Among all the possible valid parameterizations, the one leading to the smallest number of task arguments and containing the largest total number of method arguments is to be favored, in order to find relevant unifications. In practice, we implemented it by enumerating possible sets U i , which we then try and combine together.

Evaluation of Operational Models

Now that we are able to generate a set of full operational models from an initial structure candidate, we ought to compare these in order to find the best one among all candidates.

The metric used to evaluate the operational model should compromise between models that generalize too much and models that overfit. Indeed, as described earlier, we wish to allow our agent to generate solutions to new acting problems, but we also want these solutions to be sound, i.e., with limited failures during execution.

To devise such a metric, we turn to the Minimum Description Length (MDL) principle [START_REF] Grünwald | A Minimum Description Length Approach to Grammar Inference[END_REF]. This principle, coming from information theory, states that learning can be viewed as a form of data compression, as both intend to find some regularity in some source material. Therefore, in this framework, the best model is the one that can compress the data the most. Furthermore, as the total size of the compressed data includes the size of the model itself, used to reconstruct the source, this principle naturally guards against overly specific models.

Example uses of this technique range from learning Context Free Grammars (CFGs) of which HTNs, and thus our operational models, are close [START_REF] Sapkota | Unsupervised Grammar Inference Using the Minimum Description Length Principle[END_REF], to finding common graph patterns [START_REF] Bariatti | GraphMDL: Graph Pattern Selection Based on Minimum Description Length[END_REF].

Framing our problem in the context of this MDL principle, we can say that a desirable model should be able to "compress" the demonstrations, while not being so specific that nothing else can be generated, thus limiting the complexity and therefore the size of this model.

Assuming we have generated an operational model candidate O c as part of our search process, we define the description length of the operational model L opmod (O c ) and the description length of the demonstrations in D knowing O c , written as L dem (D|O c ). In order to compute the global length of the model and the demonstration set, we combine these two metrics, using a factor α to balance their relative importance, as defined in equation 2.

L(O c , D) = αL opmod (O c ) + L dem (D|O c ) (2)
To compute L opmod (O c ), we consider a simple (arbitrary) alphabet to describe our candidate model O c and compute the length of an optimal encoding of this description of our model. Considering a random variable X Oc that takes as possible values the symbols in our alphabet, information theory tells us that the entropy H(X Oc ) of this variable bounds the expected codeword length of our optimal code as H(X Oc ) ≤ E(L) ≤ H(X Oc ) + 1. Noting x 1 , . . . , x n the symbols of our alphabet, and their occurrence probability P (x 1 ), . . . , P (x n ), the entropy formula is: H(X Oc ) = -n i=1 P (x i ) log(P (x i )). As we know the frequency of each symbol in our model as well as their total number, we can therefore compute a bound on the optimal model encoding length as in the example below.

As an example, consider the structure of the simple model learned for performing a task t shown in figure 2c. Viewing our model as a grammar-like structure, we can describe it with the following rule: do : a | b | c | d ;. The frequency table of each symbol is given in the table in figure 7a, giving us the entropy H(X Oc ). Given that there are 9 symbols occurrence in the rule, this bounds the optimal value of L opmod (O c ) as shown in the equation in figure 7b. As this value will only be used for comparison, we arbitrarily choose the lower bound as L opmod . The trace can be mapped to a sequence of refinements from the original task to the primitive sequence. When planning or acting, each refinement of a task constitutes a choice point at which the engine must select one method among the applicable ones in the current state. Recalling all choices, we can reconstruct the refinement sequence and the corresponding trace. We define L dem (D | O c ) as the encoding size of all choice points, averaged over all examples. This leads us to equation 3, where C is the set of choices an optimal planner has to make to reconstruct d from O c , and M app,cp is the set of applicable methods at a choice point cp.

L dem (D | O c ) = 1 |D| d∈D cp∈C log (|M app,cp |) (3)
As an example, we will study the set of demonstration presented in figure 2a using again the model of figure 2c, assuming the methods have no preconditions. For each of the sequences in the demonstration set, we know that we have to choose three times among four methods, therefore L dem = 1 2 (3 log(4) + 3 log(4)) = 6 bits To show how this metric can be used, table 1 presents the different values computed for the examples presented in figure 2, using α = 0.505. In order to normalize the tree length and the sequence, based on the value obtained from the most basic model, i.e. the one presented in figure 2c. Using 1 2 α instead of α reduces the relative importance accorded to the model size compared to its efficiency at compressing the demonstrations. As the previous paragraph should have made clear, we need to know the choices that are required while acting with our candidate model O c , in order to generate a given demonstration trace d, for which we use again the technique presented by [START_REF] Höller | Compiling HTN Plan Verification Problems into HTN Planning Problems[END_REF]. We can then recover the choices made and their associated state by analyzing the resulting trace. Using an optimal planner, the computed demonstration length will be the true value of L dem (D | O c ), while a non-optimal one may lead to an overestimation.

O c L opmod (O c ) L dem (D|O c ) L(O c , D) α 1 2 α Fig. 2c 23

Preliminary Evaluation

While we are still implementing the ideas presented in this paper, we have been able to obtain some preliminary results on the metric to evaluate a candidate model for which preconditions and parameters have been identified as previously discussed.

A preliminary evaluation using these models on a given set of demonstration traces show that our metric appears indeed to favor structures that allow to efficiently generate the demonstrations, while still being of limited complexity, i.e. not favoring the deepest hierarchies, nor ones that are completely flat.

While we have shown some results earlier in table 1, the examples were too simple to show the interest of the metric, favoring the "lookup" model. However, working with more realistic examples, even simple ones, show the interest of our metric. Table 2 shows the results from an example dataset from a nondeterministic logistics domain with six primitive actions and three demonstration sequences long of respectively 11, 18 and 23 tasks. In the same way as before, we compute α = 1.35 to normalize the model length based on the flat model. As we can see, reducing the model size relative importance α allows our metric indeed to favor a balanced tree. Evaluation on datasets with smaller traces for which it is possible to analyze all the generated tree structures by hand shows that the best scoring tree is indeed the one most efficient to regenerate the demonstrations.

Conclusion and Future Work

Our current work is focused on implementing a basic reactive acting engine to evaluate the currently generated models on a test set of acting problems. This will allow us to conduct a first partial evaluation of the performance of the higher scoring models on some unseen acting problems. With this done, we will implement a local search strategy in lieu of the present crude generation method, to generate more complex models by removing the current structural restrictions. The next step will then be to integrate these operational models in a deliberative acting engine in order to leverage its lookahead capabilities, to make a better evaluation of the real world applicability of our models.

While we are still working on the implementation of the algorithm presented in the previous parts, there are some limitations that we are aware of and intend on addressing when the main algorithm will have been implemented. First, the current approach for extracting method preconditions is limited in which part of the preceding states is considered, which could be improved by integrating deictic references [START_REF] Pasula | Learning Symbolic Models of Stochastic Domains[END_REF], and superfluous predicates may be removed with an adaptation of the approach of [START_REF] Martínez | Learning Relational Models with Human Interaction for Planning in Robotics[END_REF]. Second, we wish to extract the postconditions of synthetic tasks with possibly disjunct intended effects, which may be done similarly to the extraction of the set of changes of an action of [START_REF] Pasula | Learning Symbolic Models of Stochastic Domains[END_REF]. Finally, it would be interesting to try and relax the assumptions made on the demonstration traces format.

Figure 1 :

 1 Figure 1: Structure of a task, with or without postconditions. The arguments of tasks and methods are omitted for clarity.

t

  → a b c t → a b d (a) Available demonstrations, showing that t was once achieved with the a b c action sequence and once with the a b d action sequence. Common right recursive structure, missing the refinement of the do task. A handful of possible models for the do task are shown in the subsequent figures.

  Generic model where the actor might pick any of the primitive actions and rely on the recursive call in m do to continue if needed. Model where each demonstration is fully encoded into a dedicated method. Intermediate model the common a b sequence is grouped. It relies on the recursive call to t in m do to produce a full sequence.

  Figure2: Illustration of the possible structures of the learned model for a simple learning task with two demonstration of how to perform a task t. Note that for conciseness the parameters or preconditions or the task and methods are omitted.

Figure 3 :

 3 Figure 3: Model corresponding to the {{{a}{b, c}}{d}} partitioning.

  State in the examples, with the mapping from method arguments to constants.

Figure 4 :

 4 Figure 4: Example method structure before and after argument identification.

Figure 5 :

 5 Figure 5: Example task before and after unification.

Figure 6 :

 6 Figure 6: Example method structure and parameterization.

  j and b k map to the same constant (positive example, noted b j ≡ Ct b k ), and • there is no context C t where b j and b k map to a different constant (counter-example, noted b j ≡ Ct b k ).

Figure 7 :

 7 Figure 7: Model length calculation for the one presented in figure 2c. To compute L dem (D | O c ), we need to evaluate the cost of encoding a trace d ∈ D based on our operational model.The trace can be mapped to a sequence of refinements from the original task to the primitive sequence. When planning or acting, each refinement of a task constitutes a choice point at which the engine must select one method among the applicable ones in the current state. Recalling all choices, we can reconstruct the refinement sequence and the corresponding trace. We define L dem (D | O c ) as the encoding size of all choice points, averaged over all examples. This leads us to equation 3, where C is the set of choices an optimal planner has to make to reconstruct d from O c , and M app,cp is the set of applicable methods at a choice point cp.

L

  opmod (O c ) L dem (D|O c ) L(O c , D)

Table 1 :

 1 Description length in bits for the examples presented in figure 2.

		.76	12	24	18
	Fig. 2d	24.57	2	14.4	8.2
	Fig. 2e	22	6.34	13.1 11.89
	Fig. 2f	29.21	2 16.75	9.37

Table 2 :

 2 Description length in bits for some real examples.

				α	1 2 α
	Flat	24.57	33.15	66.3 49.7
	Lookup	141.2	1.58 192.2 96.9
	Balanced	37.71	20.98	71.9 46.4