Learning Task Knowledge and its Scope of Applicability in Experience-Based Planning Domains
Vahid Mokhtari Luis Seabra Lopes Armando Pinho Roman Manevich

Experience-Based Planning Domains]
Learning Task Knowledge and its Scope of Applicability
in Experience-Based Planning Domains





  The University of Aveiro
  Portugal
mokhtari.vahid@ua.pt



  The University of Texas at Austin
  USA

romanm@cs.bgu.ac.il




§ ABSTRACT

Experience-based planning domains
(EBPDs) have been recently proposed to improve problem solving by learning
from experience.
EBPDs provide important concepts for long-term learning and planning in robotics.
They rely on acquiring and using task knowledge, i.e., activity schemata,
for generating concrete solutions to problem instances in a class of tasks.
Using Three-Valued Logic Analysis (TVLA), we extend previous work to generate
a set of conditions as the scope of applicability for an activity schema.



The inferred scope is a bounded representation of a set of problems
of potentially unbounded size, in the form of a 3-valued logical structure,
which allows an EBPD system to automatically find an applicable activity
schema for solving task problems.


We demonstrate the utility of our approach in a set of classes of problems
in a simulated domain and a class of real world tasks in a fully physically
simulated PR2 robot in Gazebo.






[
    Roman Manevich
    
==================















§ INTRODUCTION


Planning is a key ability for intelligent robots, increasing their autonomy 
and flexibility through the construction of sequences of actions to achieve 
their goals <cit.>.
Planning is a hard problem and even what is known historically as 
classical planning is PSPACE-complete over propositional state variables 
<cit.>.
To carry out increasingly complex tasks, robotic communities make strong 
efforts on developing robust and sophisticated high-level decision making 
models and implement them as planning systems. 
One of the most challenging issues is to find an optimum in a trade-off 
between computational efficiency and needed domain expert engineering 
work to build a reasoning system. 
In a recent work <cit.>, 
we have proposed and integrated the notion of Experience-Based 
Planning Domain (EBPD)—a framework that integrates important concepts 
for long-term learning and planning—into robotics. 
An EBPD is an extension of the standard planning domains which 
in addition to planning operators, includes experiences and methods 
(called activity schemata) for solving classes of problems. 
Figure <ref> illustrates the experience extraction, learning and 
planning pipeline for building an EBPD system. 
Experience extraction provides a human-robot interaction for teaching 
tasks and an approach to recording experiences of past robot's observations 
and activities.
Experiences are used to learn activity schemata, i.e., methods of guiding a 
search-based planner for finding solutions to other related problems. 
Conceptualization combines several techniques, including deductive 
generalization, different forms of abstraction, feature extraction, loop 
detection and inferring the scope of applicability, to generate activity 
schemata from experiences. Planning is a hierarchical problem solver 
consisting of an abstract and a concrete planner which applies learned 
activity schemata for problem solving. 
In previous work, algorithms have been developed for experience extraction 
<cit.>, activity schema learning and 
planning <cit.>.


box=[rectangle, draw=black, 
               rectangle split, rectangle split parts=2,
               rounded corners, minimum width=5.5cm, minimum height=5.6cm]




In this paper, we present several recent improvements and extensions of 
EBPDs. The procedures highlighted in bold in Figure <ref> outline 
the contribution of this paper. 
As the main contribution of this paper, we extend and improve the EBPDs 
framework to automatically retrieve an applicable activity schema 
for solving a task problem. 
We propose an approach to infer a set of conditions from an experience 
that determines the scope of applicability of an activity schema 
for solving a set of task problems. The inferred scope is a 3-valued 
logical structure <cit.> (i.e., a structure that 
extends Boolean logic by introducing an indefinite value  to denote 
either 0 or 1) which associates a bounded representation for a set of 
problems in the form of 2-valued logical structures of potentially 
unbounded size. 
We employ Three-Valued Logic Analysis (TVLA) <cit.> both 
to infer the scope of applicability of activity schemata 
(Section <ref>) and to test whether existing activity 
schemata can be used to solve given task problems 
(Section <ref>). 

We also extend and improve the abstraction methodology used in EBPDs 
(Section <ref>). We propose to apply two independent 
abstraction hierarchies for reducing the level of detail during both 
learning an activity schema and planning, which leads to generate an 
abstract solution useful to reduce the search at the more concrete 
planning level. 

In the rest of the paper, we recapitulate the previous work and present 
an integrated and up-to-dated formal model of EBPDs 
(Section <ref>), and the approaches to learning 
activity schemata from robot experiences and task planning 
(Sections <ref>–<ref>) 
(note that Sections <ref> and <ref> are prior works).
A special attention is given to abstracting an experience and inferring the 
scope of applicability of an activity schema using the TVLA 
(Sections <ref> and <ref>). 
We validate our system over a set of classes of problems in a simulated 
domain and a class of real world task in a fully physically simulated PR2 
robot in Gazebo (Section <ref>).












§ RELATED WORK


The EBPDs' objective is to perform tasks.
Learning of Hierarchical Task Networks (HTNs) is among the most
related works to EBPDs.
In HTN planning, a plan is generated by decomposing a method for a given
task into simpler tasks until primitive tasks are reached that can be
directly achieved by planning operators.
CaMeL <cit.> is an HTN learner which 
receives as input plan traces and the structure of an HTN method and tries 
to identify under which conditions the HTN is applicable. 
CaMeL requires all information about methods except for the preconditions.
The same group transcends this limitation in a later work <cit.>
and presents the HDL algorithm which starts with no
prior information about the methods but requires hierarchical plan
traces produced by an expert problem-solver.
HTN-Maker <cit.> generates an HTN domain model from a STRIPS 
domain model, a set of STRIPS plans, and a set of annotated tasks.
HTN-Maker generates and traverses a list of states by applying the actions
in a plan, and looks for an annotated task whose effects and preconditions
match some states. Then it regresses the effects of the annotated task
through a previously learned method or a new primitive task.
Overall, identifying a good hierarchical structure is an issue,
and most of the techniques in HTN learning rely on the hierarchical
structure of the HTN methods specified by a human expert.
On the contrary, the EBPDs framework presents a fully autonomous
approach to learning activity schemata with loops from single experiences.
The inclusion of loops in activity schemata is an alternative to recursive HTN methods.

Aranda <cit.> takes a planning problem and finds 
a plan that includes loops. 
Using TVLA <cit.> and back-propagation, Aranda finds 
an abstract state space from a set of concrete states of problem 
instances with varying numbers of objects
that guarantees completeness, i.e., the plan works for all
inputs that map onto the abstract state.

These strong guarantees come at a cost: (i) restrictions on the language
of actions; and (ii) high running times. Indeed computing the abstract state 
is worst-case doubly-exponential in the number of predicates.

In contrast, the EBPDs system assumes standard PDDL actions. We also use 
TVLA to compute an abstract structure that determines 
the scope of applicability of an activity 
schema, however, we trade completeness for a polynomial time algorithm, 
which results in dramatically better performance.

LoopDistill <cit.> also 
learns plans with loops from example plans.
It identifies the largest matching sub-plan in a given example
and converts the repeating occurrences of the sub-plans into
a loop. The result is a domain-specific planning program
(dsPlanner), i.e., a plan with if-statements and while-loops
that can solve similar problems of the same class.
LoopDistill, nonetheless, does not address the applicability test of plans.

Other approaches in AI planning including
case based planning <cit.>,
and macro operators <cit.>
are also related to our work.
These methods tend to suffer from the utility problem, in which
learning more information can be counterproductive due to
the difficulty with storage and management of the information
and with determining which information should be used to solve a
particular problem.
In EBPDs, by combining generalization with abstraction in task learning,
it is possible to avoid saving large sets of concrete cases.
Additionally, since in EBPDs, task learning is supervised,
solving the utility problem can be to some extent delegated to
the user, who chooses which tasks and associated procedures to teach.

Other related work includes Learning from Demonstration (LfD) which puts 
effort into learning robot control programs by simply showing robots 
how to achieve tasks <cit.>. 
This has the immediate advantage of requiring no specialized skill or training, 
and makes use of a human demonstrator's knowledge to identify which control 
program to acquire, typically by regression-based methods.
Although LfD is useful in learning primitive action-control policies (such 
as for object manipulation), it is unsuitable for learning complex tasks. 
LfD usually requires many examples in order to induce the intended control 
structure <cit.>. 
Moreover, the representations are task-specific and are not 
likely to transfer to structurally similar tasks <cit.>.












§ RUNNING EXAMPLE



We develop a planning domain, based on the blocks 
world domain, for representing provided concepts and definitions. 
Assume a set of blocks of red and blue colors sitting on a table. 
The goal is to build a vertical stack of red and blue blocks. 
The state of a problem in this domain consists of predicates with 
the following meanings. 
,
,
,
,
:  is a pile, table, red block, 
blue block, or pallet, respectively.
: pile  is attached to location .
: hoist  belongs to location .
: hoist  is at place .
: hoist  is holding block .
: hoist  is empty.
: block  is on block .
: block  is on table .
: block  is the top of pile .

The domain has the actions with the following meanings. 
: 
hoist  moves from place  to place  
at location . 
: hoist  unstacks block  
from block  on pile  at location . 
: hoist  puts block  
on block  on pile  at location . 
: hoist  picks up block  
from table  at location . 
: hoist  puts down block  
on table  at location .

We define a specific class of `stack' problems where an equal number of 
red and blue blocks are initially on a table and need to be stacked on a 
pile with blue blocks at bottom and red blocks on top using a hoist 
which can hold only one block at a time. 
Generalizing from this example, we formally present and define concepts 
used for creating this domain and problem solving in EBPDs. 




§ A FORMAL MODEL OF EXPERIENCE-BASED PLANNING DOMAINS



An EBPD is a unified framework that provides intelligent robots with 
the capability of problem solving by learning from experience 
<cit.>. Problem solving in this 
framework is achieved using a hierarchical problem solver, consisting 
of an abstract and a concrete planning domain, which employs a set of 
learned activity schemata for guiding a search-based planning. 


Formally, an EBPD is described as a tuple 
 
where 
D_a is an abstract planning domain, 
D_c is a concrete planning domain, 
R is a set of abstraction hierarchies (i.e., inference rules) 
f:D_c→D_a to translate the concrete space in D_c 
into the abstract space in D_a, 
E is a set of experiences, 
and M is a set of methods in the form of activity schemata for 
solving problems. 


In general, a planning domain of problem solving  is described by 
a first-order logic language L, a finite subset of ground atoms 
Σ of L for representing the static or invariant properties 
of the world (properties of the world that are always true), a set of all 
possible states S, in which every state s∈S is a set of 
ground atoms of L representing dynamic or transient properties of 
the world (i.e., s∩Σ≠∅), and a set of planning 
operators O.  In EBPDs, the abstract and concrete planning 
domains are denoted by  and  respectively.


A planning operator o ∈O is described as a tuple 
( h,S,P,E ) where 
h is the planning operator head, 
S is the static precondition of o, a set of predicates that must 
be proved in Σ,  
P is the precondition of o, a set of literals that must be proved 
in a state s ∈S in order to apply o in s, and 
E is the effect of o, a set of literals specifying the changes on s 
effected by o.
A head takes a form n(x_1,...,x_k) in which 
n is the name and x_1,...,x_k are the arguments, e.g., 
 
[ The notation in the Planning Domain Definition Language 
(PDDL) is used to represent EBPDs. All terms starting with a question 
mark (?) are variables, and the rest are constants or function symbols.].
Any ground instance of a planning operator is called an action.
absoperator shows a planning operator in EBPDs.



[style=customlst,
    label=lst:absoperator,
    float,
    
    morekeywords=action, static, parameters, precondition, effect,
    caption=Representation of a planning operator in EBPDs.]
listings/abs_operator


Abstraction in EBPDs is achieved by dropping or transforming predicates 
and operators of the concrete planning domain D_c into the abstract 
planning domain D_a. This transformation involves two independent 
abstraction hierarchies: a predicate abstraction hierarchy and an 
operator abstraction hierarchy which are expressed in R. 
The predicate abstraction hierarchy is a set of abstraction relations, 
each one relating a concrete predicate 
p_c(u_1,…, u_n)∈L_c to an abstract 
predicate p_a(v_1,…,v_m) ∈L_a, such that m ≤ n and 
(v_1,…, v_m) ⊆ (u_1,…,u_n); 
or to  (nil).
That is, a concrete predicate in L_c might: map onto 
an abstract predicate in L_a by replacing predicate symbols and 
excluding some arguments of the concrete predicate from the arguments of 
the abstract predicate, e.g., 
; 
or map onto ∅ (nil), that is, it is excluded 
from the abstract predicates, e.g., 
. 
Similarly, the operator abstraction hierarchy translates concrete 
operators in O_c into abstract operators in O_a. 
In this abstraction, a concrete operator in O_c might: map onto 
an abstract operator in O_a by replacing operator symbols and 
excluding some arguments of the concrete operator from the arguments 
of the abstract operator, e.g., 
;
or map onto ∅ (nil), that is, it is excluded 
from the abstract operators, e.g., 
. 

In this paper, a functional expression (x), wherever it 
is used, given a concrete predicate/operator, returns the parent of x, 
i.e., an abstract predicate/operator corresponding to the concrete 
predicate/operator.
Tables <ref> and <ref> 
present the predicate and operator abstraction hierarchies in the 
EBPD. 
[ As a prerequisite of EBPDs, it is assumed that descriptions 
of the abstract and concrete planning domains (D_a,D_c) with 
operators and predicates abstraction hierarchies R are given by a 
domain expert. Although it may require more effort to specify the abstract 
language, but we believe this is a price we have to pay to make planning 
more tractable in certain situation. Moreover, automatic definition of 
abstract and concrete planning domains is beyond the scope of this work.]










We propose to use experience given in the form of a concrete previously 
solved problem and to abstract this experience for its reuse in new 
situations. 

An experience e ∈E is a triple of ground structures 
( t,K,π ) where t is a task achieved in the experience, i.e., a 
functional expression of the form n(c_1,...,c_k) with n being the 
task name and each c_i a constant, e.g., (stack table1 pile1), 
K is a set of key-properties describing properties of the world in 
the experience, and π is a solution plan to achieve t. 
Every key-property is of the form τ(p) where τ is a 
temporal symbol and p is a predicate. Temporal symbols specify the 
temporal extent of predicates in the experience. Three types of temporal 
symbols are used in key-properties, namely 
—true at the initial state, 
—always true during an experience, and
—true at the final state, 
e.g., (end(top block8 pile1)). 
experience shows part of an experience in EBPDs.


Experiences are collected through human-robot interaction and 
instruction-based teaching. We previously presented methods and 
approaches of instructing and teaching a robot how to achieve a 
task as well as extracting and recording experiences 
<cit.>. Experience extraction 
is beyond the scope of this paper. 





Extracted experiences are the main inputs to acquire activity schemata.
Activity schemata are task planning knowledge obtained from experiences 
and contain generic solutions to classes of task problems. 

An activity schema m ∈M is a triple of ungrounded 
structures , where t is the target task to perform by a robot, 
e.g., ,  is the scope of 
applicability of m, and Ω is a sequence of enriched abstract 
operators (also called en enriched abstract plan). Each enriched 
abstract operator, denoted by ω, is a pair (o, F), where o 
is an abstract operator head, and F is a set of features of o, 
i.e., ungrounded key-properties, obtained from an experience, that 
characterize o.

In Section <ref>, we present the method of learning and a 
concrete example of an activity schema. In Section <ref>, 
we further develop the definition of the scope of applicability and present 
a method of inferring the scope of applicability for an activity schema 
from an experience.


Finally, a task planning problem in EBPDs is described as a tuple 
of ground structures P=( t,σ,s_0,g )
where t is the target task, 
σ⊆Σ is a subset of the static world information, 
s_0 is the initial world state, and g is the goal. 
[
A full representation and implementation of the 
EBPD, and a set of all concepts required for 
problem-solving in this EBPD are available at: <https://github.com/mokhtarivahid/ebpd/tree/master/domains/>.]













§ LEARNING ACTIVITY SCHEMATA


In this section, we recapitulate the procedure for learning an 
activity schema in EBPDs. We also improve the abstraction methodology in 
EBPDs to achieve more compact and applicable concepts. 






 §.§ Genralization
 


The first stage, applied to an experience, in order to extract its basic 
principles, is a deductive generalization method based on the tradition 
of PLANEX <cit.> and Explanation-Based Generalization 
(EBG) <cit.>. 
Through the generalization, a general concept is formulated from a single 
experience and domain knowledge. 
The proposed EBG method is carried out over the plan of the experience. 
In this transformation, constants appearing in the plan are replaced 
with variables, hence the plan becomes free from the specific constants 
and could be used in situations involving arbitrary constants. 
The EBG method consistently variablizes all constants appearing in the 
actions of the plan in the experience and when it gets the last action in 
the plan, propagates the variables for constants in the whole experience, 
i.e., the constants in the key-properties of the experience are also 
replaced with the variables obtained by the EBG. EBG then generates a 
generalized experience, i.e., a new planning control knowledge, which 
forms the basis of a learned activity schema.





 §.§ Abstraction
 


We propose to use an abstraction methodology for translating the obtained 
generalized experience into an abstracted generalized experience. Abstract 
representation allows, during problem solving, to solve given problems with 
a reduced computational effort. It also makes the learned concepts broader, 
more compact and widely applicable.
Given the predicate and operator abstraction hierarchies R, the 
abstraction of an experience is achieved by transforming the concrete 
predicates and operators into abstract predicates and operators, which 
results in reducing the level of detail in the generalized experience. 
The predicate and operator abstraction hierarchies in R specify 
which of the concrete predicates/operators are mapped and which are skipped.

A concrete (generalized) experience e=(t,K,π) is translated into an 
abstracted (generalized) experience 
e_a=(t,K_a,π_a), denoted by Abs(e), as follows:

    K_a   = {τ(parent(p)) |τ(p) ∈ K},   π_a = {parent(o) | o ∈π}.


Listing <ref> partially shows an experience after the 
generalization and abstraction. In this example, the abstraction is based 
on the predicate and operator abstraction hierarchies presented in 
Tables <ref> and <ref>.


[style=customlst,
    float=t,
    label=lst:experience_gen,
    belowskip=0pt,
    
    morekeywords=define, experience, domain, episode_id,
    task, parameters, key, properties, plan, objects,
    caption=After generalization and abstraction, the constants are replaced 
    with variables (Generalization), and some key-properties and actions are 
    excluded from the generalized experience (Abstraction) as specified in 
    the predicate and operator abstraction hierarchies.]
listings/robotic_arm_exp_generalized.ebpd







 §.§ Feature extraction
 


The discovery of meaningful features can contribute to the creation of 
a more concise and accurate learned concept <cit.>. 
While abstraction reduces the level of detail in an experience, 
extracting other features would help to capture the essence of the 
experience. 
Features are properties of abstract operators in learned planning knowledge. 
In an experience, a feature of an abstract operator is a 
key-property τ(p) such that p contains at least one argument 
of the abstract operator and at least one argument of the task in the 
experience, that is, the feature links the abstract operator with the 
task in the experience. 
For example in Listing <ref>, the key-property 
 is a feature connecting 
, the argument of an abstract operator , 
to , the argument of the task `stack'. 
For each abstract operator in a generalized and abstracted experience, 
all possible relations between the arguments of the abstract operator 
and the task arguments are automatically extracted and associated to 
the abstract operator. 
Features are intended to improve the performance of problem solving by 
guiding a planner toward a goal state and reducing the probability of 
backtracking, that is, during problem solving, objects that satisfy the 
features are preferable to instantiate actions. 
Listing <ref> shows thus far the learned activity schema 
from the `stack' experience, after generalization, abstraction and 
feature extraction.


[style=customlst, 
    label=lst:schema, 
    float=t, 
    morekeywords=parameters, domain, define, method,
    activity, schema, abstract, plan, objects,
    caption=A learned activity schema thus far for the `stack' 
    task after generalization, abstraction and feature extraction. 
    Each abstract operator is associated with a set of features 
    (some are omitted due to limited space) that during problem 
    solving determine which objects can be used to instantiate 
    abstract actions. 
    ]
listings/robotic_arm_schema.ebpd







 §.§ Loop detection
 


Detecting and representing possible loops of enriched abstract operators 
in an activity schema would help to improve the compactness and to increase 
the applicability of the activity schema. 
In the previous work <cit.>, we proposed 
a loop detection approach based on the standard methods of computing 
Suffix Array (SA) of a string — an array of integers providing 
the starting positions of all suffixes of a string, sorted in lexicographical 
order — and the Longest Common Prefix (LCP) array — an array of 
integers storing the lengths of the longest common prefixes between all 
pairs of consecutive suffixes in a suffix array <cit.>. 
[ Suffix array and the longest common prefix array allow 
efficient implementations of many important string operations.]
Since the LCP algorithm also selects the overlapping longest repeated 
substrings in a string, it cannot be independently used to detect potential 
loops in the string. We extend the definition of the LCP to the Non-overlapping 
Longest Common Prefix (NLCP) and build an NLCP array from a string:



Let A and B be two strings, and A[i:j] and B[i:j] denote the 
substrings of A and B ranging from i to j-1 respectively. 
The length of the Non-overlapping Longest Common Prefix (NLCP) of 
A and B, denoted by nlcp(A,B), is the largest integer 
l ≤min(A,B,abs(A-B)) such that 
A[0:l] = B[0:l].




Let S be a string and SA the suffix array of S. 

An NLCP array, built from S and SA, 
is an array of integers of size n=len(S) such that NLCP[0] 
is undefined and NLCP[i]=nlcp(S[SA[i-1]:n],S[SA[i]:n]), 
for 1≤ i<n.


The NLCP array gives a list of potential patterns in a string, however, 
it does not warrant the obtained patterns are consecutive. We 
proposed the Contiguous Non-overlapping Longest Common Prefix array 
obtained form the NLCP array:



A Contiguous Non-overlapping Longest Common Prefix (CNLCP) array 
is an array of structures, constructed from the SA and NLCP arrays of a 
string, such that each CNLCP[i], for i≥ 0, contains a substring, 
representing a pattern that consecutively occurs in the string, and a list of 
starting positions of the pattern in the string. A non-overlapping longest 
common prefix between NLCP[i] and NLCP[i-1] is consecutive if 
NLCP[i]=abs(SA[i]-SA[i-1]) for 1≤ i<n. 


When the CNLCP array is constructed for the abstract plan of a generalized 
and abstracted experience (represented as a string), we start by selecting an 
iteration with the largest length in the CNLCP array and construct a loop 
by merging all iterations of the loop, that is, the loop iterations are merged 
and an intersection of their corresponding features is computed, and a new 
variable represents the different variables playing the same role in the 
corresponding abstract operators and in their corresponding features in each 
subsequence. We continue this process for all iterations in the CNLCP array 
until no more loops are formed. 
In Appendix <ref>, we present an updated version of the CNLCP 
algorithm and a concrete example of computing the CNLCP array.
schema_loop shows a learned activity schema of the `stack' task in 
the EBPD with two potential loops of actions.

The specific algorithms for learning activity schemata have been 
described in <cit.>.


[style=customlst,
    label=lst:schema_loop,
    float=t,
    captionpos=b,
    
    
    
    morekeywords=parameters, domain, objects,
    define, activity, schema, method, abstract, plan, precondition,
    caption=A learned activity schema for the `stack' task with loops 
    (note only key-properties that make distinction between abstract 
    operators are shown and the rest are omitted due to limited space).
    There are two loops in this activity schema. 
    During problem solving, iterations of loops are generated for blue 
    and red blocks on a table, respectively.
    ]
listings/robotic_arm_schema_loop.ebpd












§ INFERRING THE SCOPE OF AN ACTIVITY SCHEMA



To extend the EBPDs framework, we propose to infer the scope of 
applicability of the learned activity schema. The scope allows for testing 
the applicability of the activity schema to solve a given problem. We 
develop an approach based on Canonical Abstraction <cit.>, 
which creates a finite representation of a (possibly infinite) set of 
logical structures. The approach is based on Kleene's 3-valued logic 
<cit.>, which extends Boolean logic by introducing 
an indefinite value , to denote either 0 or 1. 
We infer the scope of an activity schema from the key-properties of a 
generalized and abstracted experience in the form of a 3-valued logical 
structure, which can be used as an abstraction of a larger 2-valued 
logical structure. 

We first represent the key-properties of a generalized and abstracted 
experience using a 2-valued logical structure: 




A 2-valued logical structure, 
also called a concrete structure, 
over a set of predicate symbols P and a set of temporal symbols T
is a pair, 

    C=( U, ι),

where U is a set of individuals called the universe of C 

and ι is an interpretation for P and T over U. 
The interpretation of a predicate symbol p∈ P with 
a temporal symbol τ∈ T, denoted by ι(τ(p)), 
is a function mapping τ(p) over the universe U to its 
the truth-value in C: 
for every predicate symbol p^(k) of arity k and temporal symbol 
τ, ι(τ(p)):U^k →{0,1}.



A set of key-properties K is converted into a 2-valued logical structure, 
denoted by (K) =(U, ι), as follows:

    [                                                                                                                                                         P                                                                                                                                                         =                                                                                                                                 ⋃_τ(p(t_1,…,t_k)) ∈ K{p},;                                                                                                                                                         T                                                                                                                                                         =                                                                                                                                 ⋃_τ(p(t_1,…,t_k)) ∈ K{τ},;                                                                                                                                                         U                                                                                                                                                         =                                                                                                                         ⋃_τ(p(t_1,…,t_k)) ∈ K{t_1,…,t_k},;                                                                                                                                                         ι                                                                                                                                                         = λτ∈ T, p^(k)∈ P . λ(t_1,…,t_k)∈ U^k.
              {[                       1, if  τ(p(t_1,…,t_k)) ∈ K;;                       0,               otherwise. ]. ]

That is, the universe of (K) consists of the objects appearing 
in the key-properties of K, and the interpretation is defined over the 
key-properties of K. The interpretation of a temporal symbol τ∈ T, 
where T={,,}, and a predicate symbol p^(k)∈ P 
of arity k, for a tuple of objects (t_1,…,t_k)∈ U 
is 1, i.e., ι(τ(p))(t_1,…,t_k)=1, if a corresponding 
key-property τ(p(t_1,…,t_k)) appears in K. 

2-valued logical structures are drawn as directed graphs. The individuals 
of the universe are drawn as nodes, and the key-properties with definite 
values (1) are drawn as directed edges. 


For example, tvla_abstraction(a) shows a 2-valued logical 
(concrete) structure C representing the generalized and abstracted 
experience in Listing <ref>. 
In this example, the universe and the truth-values (interpretations) of 
the key-properties over the universe of C are as follows: 
[ The truth-value 
of a predicate is 0 if it is not present in ι.]


    [                                                                               P                                                                               =                                                   {pile, table, pallet, block},;                                                                               T                                                                               =                                                            {static, init, end},;                                                                               U                                                                               = {?pile, ?table, ?pallet, ?block1, 
             ?block2, ?block3, ?block4, ?block5,;                                                                                                                                                                                                                     ?block6, ?block7, ?block8},;                                                                               ι                                                                               =                                               {(static(pile ?pile))      =   1,;                                                                                                                                                                                                                 (static(table ?table))   =   1,;                                                                                                                                                                                                                 (static(pallet ?pallet)) =   1,;                                                                                                                                                                                                                 (static(block ?block1))  =   1,;                                                                                                                                                                                                                 (static(block ?block2))  =   1,;                                                                                                                                                                                                                  (static(block ?block3)) =   1,;                                                                                                                                                                                                                  (static(block ?block4)) =   1,;                                                                                                                                                                                                                                         ⋮    }. ]



The scope inference procedure converts a 2-valued logical structure 
into a 3-valued logical structure <cit.>: 




A 3-valued logical structure, 
also called an abstract structure, 
over a set of predicate symbols P and a set of temporal symbols T
is a pair, 

    =( U, ι),

where U is a set of individuals called the universe of  
and ι is an interpretation ι(τ(p)) for every predicate 
symbol p∈ P and temporal symbol τ∈ T. 
For every predicate symbol p^(k) of arity k with a temporal symbol 
τ, 
ι(τ(p)):U^k →{0,1,}, where  denotes unknown values. 


The scope inference procedure converts a 2-valued logical structure 
into a 3-valued logical structure <cit.>. 
This transformation is based on canonical names, the Kleene's join operation 
<cit.> and a canonical abstraction function:




Let (U,ι) be a (2-valued logical/3-valued logical) 
structure over a set of temporal symbols T and 
a set of predicate symbols P. 
The canonical name of an object u ∈ U, also called 
an abstraction predicate, denoted by canon(u), 
is a set of unary predicate symbols with temporal symbols 
that hold for u in the structure: 

    canon(u) = {τ(p) |τ∈ T, p∈ P,ι(τ(p))(u)=1}.





For example, the canonical names of the objects in U in the above example
are the following:


    [                canon(?table)                            =              {static(table)};                 canon(?pile)                            =               {static(pile)};               canon(?pallet)                            =             {static(pallet)};               canon(?block1)                            = {static(block),static(blue)};               canon(?block2)                            = {static(block),static(blue)};               canon(?block3)                            = {static(block),static(blue)};               canon(?block4)                            = {static(block),static(blue)};               canon(?block5)                            =  {static(block),static(red)};               canon(?block6)                            =  {static(block),static(red)};               canon(?block7)                            =  {static(block),static(red)};               canon(?block8)                            = {static(block),static(red)}. ]






In Kleene's 3-valued logic, let say the values 0 and 1 are definite 
values and  is an indefinite value. For l_1,l_2∈{0, 1, }, 
l_1 has more definite information than l_2, denoted by 
l_1≼ l_2, if l_1=l_2 or l_2=.
The Kleene's join operation of l_1 and l_2, denoted by 
l_1 l_2, is the least-upper-bound operation with respect to 
≼ defined as follows:

    l_1 l_2 = {[          l_1, if   l_1=l_2;;             ,    otherwise. ].






Let C=( U, ι) be a 2-valued logical structure. 
The canonical abstraction of C, denoted by β(C), 
is a 3-valued logical structure =( U', ι') defined as follows:

    U' = {canon(u) | u ∈ U },
       ι'(τ(p^(k)))(t_1',…,t_k') = 
    _t_1,…,t_k{ι(τ(p^(k)))(t_1,…,t_k) 
    |∀ i=1..k. t_i' = canon(t_i) }.
 

 may contain summary objects, that is, 
a set of objects in U with a canonical name, c, is 
merged [Note that we avoid merging objects appearing 
in the task (parameters) of an experience into a summary object.]
into a summary object in U', denoted by summary(c): 

    summary(c)={ u∈ U |canon(u)=c}.



Kleene's join operation determines the truth-value (interpretation) of 
key-pro­perties in a 3-valued logical structure. That is, the 
interpretation of a key-property in the 3-valued logical structure 
is 1 (solid arrows) if the key-property exists for all objects of 
the same canonical name in the 2-valued logical structure, otherwise 
the truth-value is  if the key-property exists for some objects 
of the same canonical name (dashed arrows), and 0 if no key-property 
exists.
[
In a planning domain description, the set of unary predicates is used 
to build the set of abstraction predicates. The function of canonical 
abstraction suggests that we should have sufficient unary predicates 
to be able to determine if an abstract structure exists for a 
concrete structure. In all example domains used in this work, we 
provided sufficient unary predicates. However, the type of objects 
(in typed planning domains descriptions) are also assumed 
as unary predicates when unary predicates are not sufficient.
]

Computing β((K)) for a set of key-properties K of the 
(generalized and abstracted) experience takes polynomial time in 
|K|+|U|.


3-valued logical structures are also drawn as directed graphs. 
Summary objects are drawn as double circles. Definite values are drawn 
as in the 2-values logical structures, and indefinite values () 
are drawn as dashed directed edges. 
For example, tvla_abstraction(b) shows a 3-valued logical structure 
 of the concrete structure C in tvla_abstraction(a). 
The double circles stand for summary objects, e.g., 
summary({(during,block),(during,blue)}) is a 
summary object in  corresponding to the objects 
() in C with the same canonical name. 
Solid (dashed) arrows represent truth-values of 1 (). 
Intuitively, because of the summary objects, the abstract structure  
represents the concrete structure C and all other `Stack' problems that 
have exactly one table, one pile, one pallet, and at 
least one blue block and one red block such that the blocks 
are initially on the table and finally red blocks are on top of blue blocks 
in the pile. 





The inferred scope is finally represented in a learned activity schema 
as a set of key-properties. 
Summary objects are represented as (summary ?c) where ?c is a 
canonical name. Indefinite values () appear as 
 where p represents a key-property. 
schema_loop_prec shows the inferred scope of applicability 
for the activity schema of the `stack' task. 
















§ SELECTING AN APPLICABLE ACTIVITY SCHEMA FOR PROBLEM SOLVING



When an activity schema is learned for a class of problems, it can be used 
to generate a solution plan for a given task problem. 
In the previous work, the EBPDs framework lacked an automatic strategy to 
find an applicable activity schema, among several learned activity schemata, 
for solving a task problem.
Here, we extend the previous work in which an activity schema is selected 
as applicable to solving a given task problem if the task problem is 
embedded in the scope of the activity schema, i.e., the task 
problem maps onto the scope of the activity schema. 
Selecting an activity schema involves problem abstraction and 
testing the scope of applicability (i.e., embedding). 

Given the predicate abstraction hierarchy in R, the abstraction of a 
problem is achieved by transforming the concrete predicates into abstract 
predicates, which results in an abstracted task problem. 
A concrete task problem P=( t,σ,s_0,g ) is translated into an 
abstracted task problem P_a=( t,σ_a,s_0_a,g_a ), denoted by 
Abs(P), as follows:

    σ_a = {parent(p) | p∈σ},   s_0_a  = {parent(p) | p∈ s_0},   
    g_a      = {parent(p) | p∈ g}.


To see how the abstracted task problem P_a is embedded in the scope of 
an activity schema, we first convert P_a into a 2-valued structure 
[ More precisely, to represent an abstracted task problem 
P=(t,σ,s_0,g) into a 2-valued structure, we generate 
a set of key-properties K for P by wrapping the predicates 
of (σ,s_0,g) with temporal symbols static, init 
and end, and then convert K into a 2-valued structure.
] 
(as described in Section <ref>), 
and then test if the obtained 2-valued structure is embedded in the 
scope of an activity schema:



We say that a concrete structure (i.e., an abstracted task problem represented 
in a 2-valued logical structure) C=(U, ι) is embedded in an 
abstract structure (i.e., in the scope of an activity schema) =(U', ι'), 
denoted by C ⊑, if there exists a function f:U → U' 
such that f is surjective and 
for every predicate symbol p^(k) of arity k with a temporal symbol τ, 
and tuple of objects u_1,...,u_k ∈ U, one of the following conditions holds:

    [ ι(τ(p))(u_1,...,u_k) = ι'(τ(p))(f(u_1),...,f(u_k))
      or  ι'(τ(p))(f(u_1),...,f(u_k)) = . ]



Further,  represents the set of concrete 
structures embedded in it: {C | C ⊑}.



Canonical abstraction is sound  with respect to the embedding relation.
That is, C ⊑β(C) holds for every concrete structure C.



If an abstract structure =(U', ι')
is in the image of canonical abstraction, then
checking whether a concrete structure
C=(U, ι) is embedded in  
can be done in time polynomial in |U|+|U'|+|K|.



Proof sketch.
Observe that (<ref>) implies, if C is embedded in ,
then  and C have equal sets of canonical names (checkable in 
polynomial time). 
Therefore, the embedding function must be
f = { u ↦ u' |canon_C(u)=canon_(u')}.
Checking that (<ref>) holds for f takes polynomial time.



Based on the above definition, we implemented and integrated an 
Embedding function into the EBPDs system to find an 
applicable activity schema m=( h,,Ω ) 
to a task planning problem P=(t,σ,s_0,g), 
by checking whether (Abs(P)) ⊑ holds. 













§ PLANNING USING THE LEARNED ACTIVITY SCHEMATA



We have previously proposed a planning system for generating a solution 
plan to a given task problem using a learned activity schema 
<cit.>. 
Problem solving in EBPDs is achieved using a hierarchical problem solver 
which includes an abstract planner—Abstract Schema-Based Planner 
(ASBP), and a concrete planner—Schema-Based Planner (SBP).
Given an experience-based planning domain  and a task planning 
problem P, the EBPDs' planning system retrieves an applicable 
activity schema , i.e., checks 
(Abs(P)) ⊑ 
(see Section <ref>), and attempts 
to generate a solution plan to P. 

Using the abstract planning domain D_a, ASBP first 
derives an abstract solution by instantiating the enriched abstract plan 
Ω for Abs(P). This also involves extending possible 
loops in Ω for the applicable objects in Abs(P). 
To extend a loop, ASBP simultaneously generates all successors for an 
iteration of the loop and for the following enriched abstract operator 
after the loop. 
ASBP computes a cost for all generated successors based on the number of 
features of abstract operators verified with the features extracted for the 
instantiated abstract actions, and selects the best current action with the 
lowest cost during the search. 
Finally, a ground abstract plan, Π, is generated when ASBP gets the end 
of (the enriched abstract plan) Ω (where the goal must also be achieved). 

The ground abstract plan Π produced by ASBP becomes the main skeleton 
of the final solution based on which SBP, using the concrete planning domain 
D_c, produces a final solution plan to P by generating and 
substituting concrete actions for the abstract actions in Π 
(as specified in the operator abstraction hierarchy in R). 
This might also involve generating and inserting actions from the ∅ 
(nil) class (see Table <ref>). 

The specific planning algorithm and its respective implementation have been 
proposed and described in <cit.>. 












§ EMPIRICAL EVALUATION


We present the results of our experiments in different classes of problems. 




 §.§ Prototyping and implementation



We implemented a prototype of our system in SWI-Prolog, 
which is a general-purpose logic programming language for fast 
prototyping artificial intelligence techniques, and used TVLA 
as an engine for computing the scope of applicability of activity 
schemata. We performed all experiments in simulated domains and 
simulated robot platforms, e.g., PR2, on a machine 2.20GHz Intel 
Core i7 with 12G memory. 



 §.§ STACKING-BLOCKS


In our first experiment, we use the EBPD, as described 
in Section <ref> (see also Tables <ref> 
and  <ref>). 
The main objective of this experiment is to learn a set of different activity 
schemata (tasks) with the same goal but different scopes of applicability, and 
to evaluate how the scope testing (embedding) function allows the system 
to automatically find an applicable activity schema to a given task problem. 
In this paper, we described a class of `stack' problems (Section <ref>)
with an experience (Listing <ref>), a learned activity schema 
(Listing <ref>), and its scope of applicability 
(Listing <ref> and Figure <ref>(b)). 

Additionally, we define three other classes of the `stack' problems with the same 
goal but different initial configurations as follow: (i) a pile of red and 
blue blocks, with red blocks at the bottom and blue blocks on top; (ii) a 
pile of alternating red and blue blocks, with a blue block at the bottom and a red 
block on top; and (iii) a pile of alternating red and blue blocks, with a 
red block at the bottom and a blue block on top. 
In all classes of problems, the goal is to make a new pile of red and blue blocks 
with blue blocks at the bottom and red blocks on top (the same goal as in 
Section <ref>). 

To show the effectiveness of the proposed scope of applicability inference, we 
simulated an experience (containing an equal number of 20 blocks of red and 
blue colors) in each of above classes, which based on them the system generates 
three activity schemata with distinct scopes of applicability 
(see Figure <ref>). 

To evaluate the system over the learned activity schemata, we randomly generated 
60 task problems in all four classes of the `stack' tasks (15 in each class), 
ranging from 20 to 50 equal number of red and blue blocks in each problem. 
In this experiment, the system found an applicable activity schema (among 4) 
to solve given task problems in under 60ms for testing the scope of 
applicability (see Figure <ref>), and then successfully 
solved all problems. 
To show the efficiency of the system, we also evaluated and compared the performance 
of the SBP with a state-of-the-art planner, Madagascar <cit.>, 
based on four measures: time, memory, number of evaluated nodes and plan length 
(see Table <ref>). 
In this experiment, SBP was extremely efficient in terms of memory and evaluated 
nodes in the search tree. SBP was also fairly fast to solve some problems 
comparing to Madagascar.
Note that the time comparison is not accurate in this evaluation, since SBP has 
been implemented in Prolog, but, by contrast, Madagascar has 
been implemented in C++. 
Figure <ref> alternatively summarizes the performance of the 
two planners.






















 §.§ ROVER

In the second experiment, we used the domain from the 
3rd International Planning Competition (IPC-3). 
In this experiment, we adopt a different approach for evaluating 
the proposed scope inference technique. 
We randomly generated 50 problems containing exactly 1 rover 
and ranging from 1 to 3 waypoints, 5 to 30 objectives, 5 
to 10 cameras and 5 to 20 goals in each problem. 
Using the scope inference procedure, the problems are classified 
into 9 sets of problems. That is, problems that converge to the 
same 3-valued structure are put together in the same set. 
Hence, each set of problems is identified with a distinct scope 
of applicability. 
Figure <ref> shows the time required to classify 
the problems into different sets, i.e., the time required by TVLA 
to generate 3-valued structures for the problems and test 
which problems converge to the same 3-valued structure. 
Figure <ref> shows the distribution of the 
problems in the obtained sets of problems. 
In each set of problems, we simulated an experience and generated 
an activity schema for problem solving. 
Figure <ref> shows the time required to retrieve 
an applicable activity schema (among 9 activity schemata in this 
experiment) for solving given problems, i.e., the time required to 
check whether a given problem is embedded in the scope of an activity 
schema. 

SBP successfully solved all problems in each class. 












 §.§ CAFE


In order to validate the practical utility of our approach, we also applied 
it to a real-world task using a fully physically simulated PR2 in Gazebo, 
the standard simulator in ROS. 
We developed a EBPD including 14 concrete and 
4 abstract planning operators (see Table <ref>).
We use a coffee serving demonstration including two Scenarios A and B with 
different sets of instructions to teach a PR2 to serve a guest in a 
cafe environment (see Figure <ref>). 
Instructions for Scenario A is “Move to counter1, grasp mug1, move to south 
of table1, place mug1 at the right placement area of guest1 – this is a 
 task.”
Instructions for Scenario B is “Move to counter1, grasp mug1 and mug2, 
move to south of table1, place mug1 at the right placement area of guest1, 
move to north of table1, place mug2 at the left placement area of guest1 
– this is also a  task.”
In both scenarios, it is assumed that the robot knows the location of 
the guest and of the placement areas on the table. However, it does not 
know which placement area to approach for a guest. 
We used the infrastructure and simulation environment of the RACE 
project [ ] <cit.> 
for instruction-based teaching of the robot to achieve the tasks. 
Figure <ref> shows the snapshots of teaching the PR2 
a  task in Scenario A in Gazebo. 













Our system learned two activity schemata for  task with 
distinct abstract plans (i.e, different instructions sets) and distinct 
scopes of applicability. 
To validate the utility of the learned activity schemata, 
we setup two test scenarios in each class of  task 
in which the robot is asked for serving a guest sitting at .
Our system computes the solution plans for each task problem using the 
learned activity schemata in less than 1 second. 
Video of the PR2 doing  tasks in this experiment 
are available at <https://goo.gl/HJ6g2R> and 
<https://github.com/mokhtarivahid/ebpd/tree/master/demos>.

The domains, experiences, learned activity schemata and given task 
problems used in our experiments are available online by the link: 
<https://github.com/mokhtarivahid/ebpd/>.




§ CONCLUSION AND FUTURE WORK


We proposed an approach to generate a set of conditions that determines the 
scope of applicability of an activity schema in experience-based planning 
domains (EBPDs). 
The inferred scope allows an EBPD system to automatically find an applicable 
activity schema for solving a task problem, among several learned activity 
schemata for a specific task. 

We validated the utility of this work in a simulated domain and a fully 
physically simulated PR2 in Gazebo. Through our experiments, we demonstrated 
the effectiveness of the system, including loop detection and scope inference 
procedures. We showed the timing results for test problems in these experiments. 
The time required for learning activity schemata, and computing and testing 
their scopes were negligible. 
The system learned activity schemata from single examples in under seconds, 
in contrast to other machine learning techniques, addressed in the related 
work, which usually require large sets of plan traces to learn planning 
domain knowledge (e.g., HTN-Maker <cit.> uses 75 out of 100 
input problems to train the system). 

While the results show good scalability, many engineering optimizations are 
possible on our prototype implementation of the proposed algorithms. Faster 
results can be obtained from an implementation in a compiled language. Extensive 
evaluation of the proposed system on a large set of domains is also part of 
the future work.













This work is funded by  the Portuguese Foundation for Science 
and Technology (FCT) under the grant SFRH/BD/94184/2013,
and the project UID/CEC/00127/­2013.






ACM-Reference-Format


