2.1. Automated planning

AP aims to produce solvers that are effective when faced with different classes of problems. AP produces solvers that exploit environment dynamics models to reason on different tasks in different environments. An AP task is defined by two elements:

• • The domain, that consists of the set of states of the environment S together with the set of actions A that indicates the transitions between these states.

• • The problem, that consists of the set of facts s ₀ ∈ S that indicates the initial state of the environment and the set of facts G ⊆ S that indicates the goals of the AP task.

A solution to an AP task is a sequence of actions a ₁, …, a_n. This sequence of actions corresponds to a sequence of state transitions s ₀, …, s_n such that a_i is applicable in state s_{i− 1} and produces state s_i, s_n is a goal state; that is G ⊆ S_n. The cost of the solution is the sum of the action costs. A solution is considered optimal when it minimizes the expression $\mathop{\sum}\sidelimits_{i\, = \,1}^n \,cost({{a}_i})$.

Specifying accurate action models to address AP tasks in the real world is a complex exercise. Even in traditionally easy-to-code planning domains—like Blocksworld—it is hard to specify the actions’ potential outcomes when the environment is non-deterministic. In extreme cases, like planning for the autonomous control of a Mars Rover (Bresina et al., Reference Bresina, Jansson, Morris and Rajan2005) or an underwater vehicle (McGann et al., Reference McGann, Py, Rajan, Ryan and Henthorn2008), this knowledge cannot be specified because it is as of yet unknown. In these situations, the success of the AP systems fully depends on the skills of the experts who define the action model. With the aim of assisting experts, the planning community is developing systems for the acquisition, validation and maintenance of AP models. ML seems to be a useful tool for these systems to automate the extraction and organization of knowledge from examples of plans, execution traces or user preferences.

When the AP task is accurately defined, it looks like it should be easy to tackle by searching for a path in a state transition graph, a well-studied problem. However, in AP this state transition graph often becomes so large that search is intractable. The complexity of the algorithms to solve this type of problems grows with the number of states, which is exponential in the number of problem variables (number of objects and predicates of the problem). Prior to the mid 1990s, planners were unable to synthesize plans with more than 10 actions in an acceptable amount of time.

In the late 1990s, a significant scale-up in planning took place due to the appearance of the reachability planning graph (Blum & Furst, Reference Blum and Furst1995). This discovery allowed for the development of powerful domain-independent heuristics (Bonet & Geffner, Reference Bonet and Geffner2001; Hoffmann & Nebel, Reference Hoffmann and Nebel2001a) that were computable in polynomial time. Recent discoveries—such as the automatic extraction of search landmarks (Porteous & Sebastia, Reference Porteous and Sebastia2004) and the automatic construction of symbolic pattern databases (Edelkamp, Reference Edelkamp2002)—improve planners’ speed and quality performance. Planners using these advances can often synthesize one-hundred action plans in seconds, yet scalability limitations are still present in AP and even well-studied domains—like the Blocksworld—become challenging for planners when there is a relatively large number of objects. On the one hand, current domain-independent heuristics are expensive to compute. This effect is more evident in domains where heuristics are misleading. In these domains planners spend most of their planning time computing useless node evaluations. On the other hand, given that these domain-independent techniques are based on action grounding, the planners’ search trees become intractable when the number of problem objects and/or action parameters reaches a certain size. These problems make domain-independent planners’ application to various real problems difficult. Logistics applications need to handle hundreds of objects at the same time as hundreds of vehicles and locations (Florez et al., Reference Florez, Garca, Torralba, Linares, Garca-Olaya and Borrajo2010), which makes computing evaluation functions in every search node unfeasible. In this case, ML has a role to play in capturing useful control knowledge skipped by the domain-independent techniques.

2.2. Machine learning

According to Mitchell (Reference Mitchell1997), there is a set of issues in common when using ML to improve an automatic process. The review of the planning and learning systems completed in this paper is carried out in relation to them:

1. 1. Knowledge representation. First, the type of knowledge that the ML process will learn must be defined. In this paper we consider two different targets of ML for AP, action models to feed planners and search control to guide the planners’ search for solutions. Second, how to represent the learned knowledge must be decided. In this case, two representation decisions must be made:

   1. (a) Representation language. The kind of notation used to encode the target concept and the experience. Because AP tasks are normally described in predicate logic, this is the most often used representation language for encoding AP concepts. That said, other languages like description logic or temporal logic are also used, although to a lesser extent.

   2. (b) Feature space. The set of features that the ML algorithm considers to learn the target concept. In AP, these features are normally the domain predicates used to define the AP task's actions, states and goals.

2. 2. Extraction of experience. How learning examples are collected? In the case of AP, learning examples can be autonomously collected by the planning system or provided by an external agent, such as a human expert. Implementing a mechanism to autonomously collect learning examples is a complex process. Using a planner to collect experience is an open issue mainly because guaranteeing an AP problem's solvability with a given domain model is just as hard as the original AP task. Random explorations frequently undersample AP tasks’ state and action spaces. AP actions typically present preconditions that can only be satisfied by specific sequences of actions that have low probability of being chosen by chance.

3. 3. Learning algorithm. How to capture patterns from the collected experience? Different approaches can extract these patterns. Inductive Learning builds patterns by generalizing from observed examples. Analytical Learning uses prior knowledge and deductive reasoning to build patterns that explain the information from the learning examples. Hybrid Inductive–Analytical Learning combines the two previous learning techniques to obtain the benefits of both: a better accuracy in generalization when prior knowledge is available and use of observed learning data to overcome the shortcomings in the prior knowledge. When designing learning algorithms for AP, inductive learning is the most commonly used technique, but analytical and hybrid approaches have also used based on the domain definition of the AP task to build explanations of the collected learning examples.

4. 4. Exploitation of learned knowledge. How the automatic system benefits from the learned knowledge? The decisions made on each one of the previous three issues will affect the learned knowledge. If the learned knowledge is imperfect, it must be applied via a mechanism that guarantees a robust exploitation. In the case of AP, the imperfect knowledge could be the result of several circumstances: some representation choices may not be expressive enough to capture relevant knowledge for a given domain; the strategy for collecting the learning experience may miss significant examples of the target knowledge; or the learning algorithm may get stuck in local minima or not be able to capture patterns of the target knowledge within reasonable time and memory requirements. In these situations, a direct use of the learned knowledge may damage the planning process. Planning and learning systems need to be equipped with mechanisms that allow them to plan as robustly as possible despite flaws in the learned knowledge.

3.1 Learning deterministic models in fully observable environments

This is the simplest scenario and corresponds to the classical planning task, where planning actions present deterministic effects and observations of the states are correct and complete. To offer an example of the modeled actions, Figure 3 shows the application of the unstack(B, A) action from the Blocksworld in a fully observable and deterministic environment. The Blocksworld is a classic domain in AP that consists of a set of blocks, a table and a robot hand: the blocks can be on top of other blocks or on the table; a block that has nothing on it is clear; and the robot hand can hold one block or be empty. The unstack(B, A) action makes the robot hand unstack block B from block A.

Figure 3

Example of application of the unstack action in a fully observable and deterministic Blocksworld

3.1.1 The learning task

1. 1. Knowledge representation. In terms of AP, the suitable languages for representing deterministic actions are the languages defined for classical planning. The Planning Domain Definition Language (PDDL; Fox & Long, Reference Fox and Long2003; Thiébaux et al., Reference Thiébaux, Hoffmann and Nebel2005; Gerevini et al., Reference Gerevini, Haslum, Long, Saetti and Dimopoulos2009b) is the standard representation language for classical planning. It was created as the planning input language for the IPCFootnote ¹ to standardize the planning representation languages and facilitating comparative analysis of diverse planning systems. Although several of the systems reviewed in this paper use other representation languages, we have used PDDL to illustrate our examples. A PDDL action a consists of a tuple 〈head(a),pre(a),eff(a)〉 where,

2. •head(a) is the head of action a containing the action name and the list of typed parameters;

3. •pre(a) is the set of action preconditions. This set represents the facts that needs to be true for the application of action a and;

4. •eff(a) is the set of action effects. This set includes the facts that are no longer true after the application of action a (known as del effects and represented by del(a)) and the facts made true by the application of action a (known as add effects and represented by add(a)). In PDDL, the del effects are preceded by the logical connective not.

Figure 4 shows the PDDL representation for action unstack from the Blocksworld as an example.

Figure 4

Planning Domain Definition Language representation for action unstack from the Blocksworld

1. 2. Learning examples. Learning examples consist of tuples 〈s_{i −1}, a_i, s_i〉 where a_i is the action applied at state s_{i −1}, that is, the pre-state and s_i is the state produced by applying the action, that is, the post-state.

2. 3. Learning algorithm. When actions present deterministic effects and the environment states are fully observable, the dynamics of a given action are captured from the lifted literals of the pre-state and the post-state of action executions. Learning the action preconditions is accomplished by lifting the literals from a set of pre-states. Learning the effects of a given action is completed by lifting the set of literals that is different in the pre-states and post-states of action executions. This set of literals is called the delta-state and is formally defined as $ {\rm{\rDelta }}({{s}_{i - 1}},{{s}_i})\, = \,({{s}_{i - 1}}\backslash {{s}_i})\bigcup\nolimits} ({{s}_i}\backslash {{s}_{i - 1}}) $. The first term of the delta-state captures the del effects of action a_i and the second term captures its add effects. In both learning steps—learning the action preconditions and learning the action effects—the lifting process substitutes each grounded object with a variable. The type for each variable is given by the most specific type in the type hierarchy of the substituted object.

3. 4. Exploitation of the learned knowledge. In this scenario, the learned models may present unnecessary preconditions or missing effects. These model flaws can be eliminated by observing more executions of the action but collecting a good observation sample of planning actions is still an open issue. Random applications of AP actions may leave actions unexplored. Normally AP actions present preconditions that can only be satisfied by specific sequences of actions which have a low probability of being chosen by chance. A planner may also fail to provide solutions with intermediate learned models. Considering any literal of the pre-state of an action as a real precondition of that action leads to very restrictive models that fail to solve problems known to be solvable. An alternative approach is to rely on an external source of experience that collects these extra observations of actions, a teacher for instance.

3.2 Learning deterministic models in partially observable environments

In this scenario actions also present deterministic effects, but the state is not fully observable. As a consequence, the current state is described by the set of possible states called belief state. This scenario corresponds to the conformant planning task, when the current state is non-observable, and to the contingent planning task when the current state can be partially observed. As an example of the actions modeled in this scenario, Figure 5 shows the application of the unstack(B, A) action in a deterministic and non-observable Blocksworld. In the example, there are two blocks, A and B. The current state is uncertain and is described by a belief state b ₀ that represents the disjunction of five possible states. The result of applying action unstack(B, A) is a belief state b ₁ which represents the disjunction of four possible states. State 1 in b ₀ generates state 3 in b ₁, while the action applied to the rest of states in b ₀ has no effect, so they are still probable in b ₁.

Figure 5

Example of application of the unstack (B, A) action in a non-observable two-blocks Blocksworld

3.2.1 The learning task

1. 1. Knowledge representation. Because in this scenario actions are deterministic, a classical planning representation language, such as PDDL, provides a suitable representation. Figure 4 shows the PDDL representation for action unstack from the Blocksworld.

2. 2. Learning examples. Learning examples consist of tuples 〈b_{i −1}, a_i, b_i〉 where b_{i −1} is a belief state corresponding to the partial observation of the pre-state, a_i is the action applied at the pre-state and b_i is the belief state corresponding to the partial observation of the post-state.

3. 3. Learning algorithm. In this scenario, lifting the pre-state and delta-state of observations does not define the preconditions and effects of an action. Given that the states of the environment are not completely known, a given observation of a pre-state cannot be associated with an action's preconditions. Likewise, changes of a given set of literals cannot be directly associated to the application of a specific action. In this scenario two approaches can be used:

   • • Inference. Inference can be used to obtain action models that satisfy the collected learning examples. This task is closely related to the Boolean satisfiability (SAT) problem that determines whether the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate as true. The action modeling task in this scenario can be defined as the satisfaction of a logic formula for every action in the domain. This formula is the disjunction of the possible conjunctions of pre-states and post-states observed for the action. Figure 6 shows an example of the formula for obtaining models for the action unstack(X,Y) that satisfy the observation in Figure 5.

     Figure 6

     Example of a logic formulae for modeling action unstack from a two-blocks Blocksworld

     

   • • Induction. One can search the space of possible action models to find the best fit for the observed learning examples. This task is closely related to the Inductive Logic Programming (ILP) task that searches the space of the Logic Programs Footnote ² to find the best fit for a set of observed facts. Action modeling in this scenario can be defined as the induction of two logic programs for every action in the domain. Figure 7 shows the two logic programs that model action unstack from the Blocksworld.

     Figure 7

     Representation of action unstack from the Blocksworld as two logic programs

     

     The first logic program captures the preconditions of the action. The head of this one-clause logic program consists of the action name and parameters, and the body is the subset of literals from the observed pre-states that best fits the learning examples. This learning process can be implemented as a heuristic search guided by the number of observed pre-states of the action covered and not covered by the different potential programs. The second program captures the effects of the actions. The head of this logic program is comprised of the action name and parameters, and the body consists of the subsets of literals from the observed delta-states that best fits the learning examples. This process can also be implemented as a heuristic search guided in this case by the coverage of the observed delta-states.

4. 4. Exploitation of the learned knowledge. An action model that is built satisfying/covering a given set of examples does not guarantee that it will present the exact set of preconditions and effects. Like in the previous scenario, the learned models may present unnecessary preconditions. In this scenario the learned effects may also capture invalid changes in the state caused by the partial observability of the pre- and post-states. As a consequence, planning with this kind of models may fail to address AP problems known to be solvable.

3.2.2 Implementations

The ARMS system (Yang et al., Reference Yang, Wu and Jiang2007) learns PDDL planning operators from examples consisting of tuples 〈s ₀, s_n, p〉; where s ₀ is an initial state, s_n is a goal state and p = (a ₁, a ₂, …, a_n) is a plan corresponding to a sequence of state transitions (s ₀, s ₁, …, s_n). ARMS proceeds in two phases. In the first phase, ARMS extracts frequent action sets from plans that share a common set of parameters. ARMS also finds some frequent literal-action pairs with the help of the initial state and the goal state that provide an initial guess on the actions preconditions, and effects. In the second phase, ARMS uses the frequent action sets and literal-action pairs to define a set of weighted constraints that must hold in order to make the plans correct. Then, ARMS solves the resulting weighted MAX-SAT problem and produces action models from the solution of the SAT problem. This process iterates until all actions are modeled. For a complex planning domain that involves hundreds of literals and actions, the corresponding weighted MAX-SAT representation is likely to be too large to be solved efficiently as the number of clauses can reach up to tens of thousands. For that reason ARMS implements a hill-climbing method that models the actions approximately. Consequently, the ARMS output is a model which may be inconsistent with the examples.

Amir and Chang (Reference Amir and Chang2008) introduced an algorithm that tractably generates all the STRIPS-like models that could have lead to a set of observations. Given a formula representing the initial belief state, a sequence of executed actions (a ₁, a ₂, …, a_n) and the corresponding observed states (s ₁, …, s_n) (where partial observations of states are given), it builds a complete explanation of observations by models of actions through a Conjunctive Normal Form (CNF) formula. By linking the possible states of fluents to the effect propositions in the action models, the complexity of the CNF encoding can be controlled to find exact solutions efficiently in some circumstances. The learning algorithm updates the formula of the belief state with every action and observation in the sequence. This update makes sure that the new formula represents all the transition relations consistent with the actions and observations. The formula returned at the end includes all consistent models, which can then be retrieved with additional processing.

Unlike the previous approaches, the one described in Mourão et al. (Reference Mourão, Petrick and Steedman2008) deals with both missing and noisy predicates in the observations. For each action in a given domain, they use kernel perceptrons to learn predictions of the domain properties that change because of the action execution. LOCM (Cresswell et al., Reference Cresswell, McCluskey and West2009) induces action schemas without being provided with any information about initial, goal or intermediate state descriptions for the example action sequences. LOCM receives descriptions of plans or plan fragments, uses them to create states machines for the different domain objects and extracts the action schemas from these state machines.

3.3 Learning stochastic models in fully observable environments

In this scenario the observations of the state of the environment are perfect, but actions present stochastic effects. This scenario corresponds to the probabilistic planning task. Figure 8 shows an example of the unstack(B, A) action being applied in a fully observable and stochastic version of the Blocksworld. In the example, the action produces three different alternative outcomes with probabilities of 0.5, 0.3 and 0.2, respectively.

Figure 8

Example of application of the unstack (B, A) action in a fully observable and stochastic Blocksworld

3.3.1 The learning task

1. 1. Knowledge representation. Languages for probabilistic planning support the representation of AP models with stochastic state transitions. The Probabilistic Planning Domain Definition Language (PPDDL; Younes et al., Reference Younes, Littman, Weissman and Asmuth2005) is the current standard representation language defined for the IPC's probabilistic planning track. PPDDL is essentially an extension of PDDL2.1 (Fox & Long, Reference Fox and Long2003) that supports actions with probabilistic effects. The syntax for probabilistic effects in PPDDL is formally defined as follows:

$$ (probabilistic\;{{p}_1}{{o}_1}\;{{p}_2}\;{{o}_2}\; \ldots \;{{p}_k}\;{{o}_k}) $$

where outcome o_i of the action occurs with probability p_i. It is required that 1 ⩾ p_i ⩾ 0 and $ \mathop{\sum}_{i\, = \,1}^k {{p}_i}\, = \,1 $. Figure 9 shows the PPDDL representation for the action unstack from the probabilistic version of the Blocksworld defined at IPC-2004. The probabilistic effects of this action indicate that with probability 0.5 the robot hand will successfully unstack block ?top from block ?bottom, with probability 0.3 the block ?top will fall down on the table and that with probability 0.2 the blocks will not be moved.

Figure 9

Probabilistic Planning Domain Definition Language representation for the action unstack from the Blocksworld

1. 2. Learning examples. Learning examples consist of tuples 〈s_{i −1}, a_i, s_i〉 where a_i is the action applied at state s_{i −1}, the pre-state and s_i is the post-state. Given that action effects are stochastic, pairs (pre-state, action) may have different associated post-states.

2. 3. Learning algorithm. Because the environment is fully observable, action preconditions are captured by lifting the pre-state of the learning examples. Nevertheless, learning stochastic action effects is more complex because of the overlapping post-states; that is, given an action transition defined by the tuple (pre-state, action, post-state), several action effects could describe the transition. This aspect of overlapping examples is also present in the induction of stochastic logic models such as Stochastic Logic Programs (Muggleton, Reference Muggleton1995; Cussens, Reference Cussens2001), Bayesian Logic Programs (Jaeger, Reference Jaeger1997; Kersting & Raedt, Reference Kersting and Raedt2001) or Markov Logic Networks (Richardson & Domingos, Reference Richardson and Domingos2006). These techniques share a two-step strategy for implementing the model learning task:

   1. (a) Structural Learning. At this step, ILP algorithms are used to induce first-order logic formulas that generalize the relations from the ground facts of the learning examples.

   2. (b) Parameter Estimation. This step estimates the probabilities associated with the induced logic formulas. The output of the Structural Learning step is frequently a set of rules of the form C→P, where P is the prediction of the rule and C is the set of conditions under which the prediction is true. In this case, the Parameter Estimation step consists of computing the conditional probability prob(P|C). When the induced rules are disjunctive, this probability is directly extracted from the frequency of the learning examples but when rules overlap, estimating this conditional probability requires more complex approaches:

      1. i. Bayesian Estimation (BE). This approach estimates the conditional probability following the Bayes Theorem,

         $$ prob(P|C)\, = \,prob(C|P)\frac{{prob(P)}}{{prob(C)}} $$

      2. ii. Maximum Likelihood Estimation (MLE). This approach assumes that the examples follow a known probability distribution and iteratively tunes the distribution's parameters to achieve a good fit.

Accordingly, modeling an action's stochastic effects can be defined as learning a Stochastic Logic Program where each clause in the program represents one probabilistic effect of the action. The heads of the clauses of the logic program consist of the action name and action parameters, and the bodies consist of the subsets of literals from the observed delta-states that best fit the learning examples for this effect. Figure 10 shows an example of stochastic logic program for the effects of action unstack from the Blocksworld.

Figure 10

Representation of the effects of action unstack from the Blocksworld as a Stochastic Logic Program

1. 4. Exploitation of the learned knowledge. The on-line modeling of actions with stochastic effects is an open issue. Actions may present outcomes that result in dead-end states which complicates the environment's exploration. It is also not enough to detect causal flaws in the learned model. It is necessary to detect flaws in the probabilities associated with the models. There are no mechanisms to refine stochastic actions when states that do not fit the model are observed.

3.3.2 Implementations

In Oates and Cohen (Reference Oates and Cohen1996), the authors induced propositional rules corresponding to conditional probabilistic effects of actions. Their approach explores a given AP domain by taking random actions and observing their execution. For each execution, they register an observation in the form of o_i = 〈s_i, a_i, s_{i + 1}〉, where a_i is the action executed in s_i, and s_{i + 1} is the resulting state of executing a_i in s_i. Then they induce the effects of a given action by performing a general-to-specific Best-First Search in the space of the action's possible conditional effects. For each action, this search is guided by the frequency of observations covered by the action's possible conditional effects and terminates when a user-specified number of search nodes are explored.

The TRAIL system (Benson, Reference Benson1997) learns relational models of probabilistic actions. TRAIL explores a given AP domain as follows: first it tries to solve a problem with the current action model. When this model is too bare to solve the problem, it asks an external expert a solution plan, it observes the plan's execution and it learns a new model from these observations. If the current action model makes TRAIL generate a plan for the problem, TRAIL executes that plan and observes its execution to refine the action model. TRAIL action models are an extended version of Horn clauses so TRAIL straight off uses standard ILP tools for learning.

The LOPE system (García-Martínez & Borrajo, Reference García-Martínez and Borrajo2000) learns planning operators with an associated probability of success. At the beginning, the system has no knowledge. It perceives the initial state, and selects a random action to execute in the environment. Then it loops by (1) executing an action, (2) perceiving the resulting state and its utility, (3) learning a model from the perception and (4) planning for further interaction with the environment (if the execution of the plan is completed, or the system has observed a disparity between the predicted situation and the situation perceived). The LOPE's planning component does not explicitly receive a goal input given that LOPE creates its own goals from the highest utility situations.

In Pasula et al. (Reference Pasula, Zettlemoyer and Kaelbling2007), the authors learn probabilistic action models from externally provided observations, which again consist of tuples o_i = 〈s_i, a_i, s_{i + 1}〉. The induced action models are probabilistic STRIPS operators extended in two ways: (1) they can refer to objects not mentioned in the action parameters, and (2) for each action, they add a noise outcome that groups the set of possible outcomes that are the least probable for the action. The action modeling algorithm has three learning layers:

1. 1. Learning the action structure. At this layer a greedy search process is performed in the space of action sets to select the action preconditions and outcomes that best fit the learning examples. An evaluation function guides the search favoring rule sets that assign high likelihood to the learning examples and penalizing model complexity (number of preconditions plus number of outcomes).

2. 2. Learning the action outcomes. Given an action and a set of learning examples, greedy search is used to decide the best set of outcomes and their corresponding parameters for the action. This learning is performed every time a new rule is constructed in the previous layer.

3. 3. Parameter estimation. Given an action, the learning examples are used to estimate a distribution over action outcomes. This work estimates the outcomes parameters implementing a MLE with the conditional gradient method. The MLE is performed for each set of outcomes considered in the previous layer.

The PELA system (Jiménez et al., Reference Jiménez, Fernández and Borrajo2008) automatically upgrades a STRIPS action model with situation-dependent probabilities learned from plan executions. These probabilities are captured using the TILDE tool for the automatic induction of first-order decision trees (Blockeel & De Raedt, Reference Blockeel and De Raedt1998).

3.4 Learning stochastic models in partially observable environments

In this scenario actions present stochastic effects and the observations of the world state may be incomplete and/or incorrect. Action modeling in stochastic and partially observable environments has been poorly studied and currently, there is no general strategy for addressing this modeling task. Preliminary work (Yoon & Kambhampati, Reference Yoon and Kambhampati2007) addresses this problem using Weighted Maximum Satisfiability techniques for finding the action model that best explains the collected observations. Specifically, in order to learn the preconditions of every action a, this approach enumerates all the possible axioms of the form a(x,y) : −p(x,y), with all the available predicates and variable matchings. Then, it updates the weights associated to the axioms according to a set of learning examples. Axioms corresponding to wrong predicates or unnecessary predicates would get close to zero weight after enough learning examples, and axioms corresponding to necessary predicates would get close to one. Likewise, for learning the effects of every action a, this approach enumerates all the possible effects of the form a(x,y) : −e(x,y) and then updates the corresponding associated weights in a similar way.

4.1 Macro-actions

Macro-actions were among the first attempts to speed-up planning processes. They are extra actions resulting from assembling actions that are frequently used together. Macro-actions reduce the depth of the planning algorithm's search tree. Their benefit decreases with the number of new macro-actions as they enlarge the search tree's branching factor causing the utility problem. Addressing this trade-off is the key issue at stake when attempting to make macro-actions work. Figure 12 shows an example of the macro-action unstack-putdown for the Blocksworld domain. This macro-action is the result of assembling actions unstack and putdown.

Figure 12

Macro-action unstack-putdown for the Blocksworld domain

4.2 Generalized policies

A generalized policy is a mapping of planning contexts (sometimes also called meta-states) into the preferred actions to apply in the context. A planning context typically consists of the current state as well as with the set of goals. An accurate generalized policy is able to solve any problem from a given domain without any search having to be done, by repeatedly applying the preferred action for each planning context. Figure 13 shows an example of a generalized policy in the form of a decision list (ordered set of decision rules) for the Blocksworld domain. This generalized policy stacks block TOP on block BOTTOM when TOP should be on BOTTOM, BOTTOM is clear and BOTTOM is already well placed Footnote ³. In all other cases the policy unstacks all blocks and puts them down on the table so they can be placed in their final position.

Figure 13

A generalized policy in the form of a decision list for the Blocksworld domain

4.2.1 Learning generalized policies

• • Knowledge representation. A key issue when representing planning contexts is selecting the feature space. The feature space is the set of predicates considered for the learning process. This set must be general enough to capture the domain's relevant knowledge and specific enough to make the learning tractable. In AP the feature space has usually consisted of predicates for describing the current state and the goals of the planning task. The PRODIGY system enriched the feature space with extra predicates, called metapredicates (Minton, Reference Minton1988). Metapredicates capture useful knowledge about the planning context, like the current applicable operators or the goals that still need to be achieved. Recent works on learning generalized policies have extended the definition of metapredicates to include concepts from heuristic planning, like metapredicates for capturing the actions of the relaxed plan in the current state (Yoon et al., Reference Yoon, Fern and Givan2008) or for capturing the set of helpful actions in the current state (de la Rosa et al., Reference de la Rosa, Jiménez and Borrajo2008).

  There have been two main approaches for representing generalized policies. A generalized policy can be represented as a set of rules that capture the preferred action to apply in a given planning context. In this case, the generalized policy is formally defined as a tuple π = 〈L, R〉 where

  • – L the set of literals used to describe the different planning contexts. It defines the feature space used during learning.

  • – R is a set of rules, where the rule's Head is the action to apply and the Body is the set of predicates that describes the planning context under which the action should be applied.

  A generalized policy can also be represented as a set of decision instances with a distance metric to retrieve similar instances. This is the representation approach that CBR (Case-Based Reasoning) planners follow. Even if this representation is able to capture more specific domain regularities, it has the serious drawback of requiring an appropriate similarity metric. Utility is also a problem when handling large collections of decision instances, because, as a collection gets larger, the time it takes to search for similar instances also increases. This second representation for generalized policies is formally defined as a tuple π = 〈L, I, D〉, where:

  • – L the set of literals used to describe the planning contexts. It defines the feature space.

  • – I is a set of tuples, i = 〈c_i, a_i〉, where c_i is an instantiated planning context and a_i is the instantiated action applied in c_i.

  • – D is a distance metric that computes the distance between two different planning contexts. Given a new planning context c, the policy decides the action a_i to execute in c by computing the closest tuple in I and returning its associated action a_i, as shown in,

    $$\pi (c)\, = \,{\arg }_{{{a}_i}} \,\mathop {\min }\limits_{( \lt {{c}_i},{{a}_i} \gt \in I)} \,D(c,{{c}_i})$$

Both approaches usually represent planning contexts in predicate logic because it is a natural encoding for the AP tasks. Predicate logic provides mechanisms to define extra predicates that enrich planning contexts. As an example of these extra predicates, Figure 14 shows the definition of the wellplaced (Block) predicate for the Blocksworld (Khardon, Reference Khardon1999). This concept is not in the Blocksworld domain's original coding, but it is useful to define a compact generalized policy as is shown in the example of Figure 13.

Figure 14

Representation of the wellplaced (Block) concept for the Blocksworld domain in predicate logic

Learning these kinds of predicates in predicate logic is still an open issue so they have to be hand-coded. Planning systems have used other representation languages that succeed in learning these concepts. Languages for describing object classes have been shown to provide a useful bias for learning these concepts. These languages include concept language (Martin & Geffner, Reference Martin and Geffner2000) and taxonomic Syntax (Mcallester & Givan, Reference Mcallester and Givan1989), which provide operators to define recursive concepts over predicates, like the * operator. In the Blocksworld domain, for example, the useful concept of well-placed block can be defined in a very compact way using these languages (Figure 15).

Figure 15

Well-placed concept for the Blocksworld domain expressed in concept language

Expressing planning knowledge in temporal logic has also been shown to be useful. This is the case of TLPLAN (Bacchus & Kabanza, Reference Bacchus and Kabanza2000). Unfortunately, learning planning knowledge in temporal logic has not been resolved.

• • Learning examples. Learning examples are extracted from solutions to training problems. The learning examples consist of tuples 〈c_i, a_{i +1}〉 where c_i is a planning context and a_{i +1} is the action applied at context c_i.

• • Learning algorithm. When the policy consists of a set of rules, the learning task is very much related to the ILP task. Learning a generalized policy can be defined as the induction of a logic program for every action in the domain. This logic program captures when to apply the action. The head of the rules in this logic program consists of the action name and parameters, and the body is the subset of literals from the planning context that best covers the learning examples. This learning task can be implemented as a heuristic search guided by the coverage of learning examples. When the policy consists of a set of relevant instances, the learning task stores and manages the set of instances. In this case, learning a large number of instances can actually be counterproductive because it is hard to store and manage them and because of the difficulty involved in determining which instance to use to solve a particular problem. A solution to this problem is to post-process the stored instances to only manage the most relevant ones. Examples are REPLICA (García-Durán et al., Reference García-Durán, Fernández and Borrajo2012), which extracts a set of prototypes from the instances, or DISTILL (Winner & Veloso, Reference Winner and Veloso2003), which builds a highly compressed instances library by generalizing and merging solution plans.

• • Exploitation of the learned knowledge. A generalized policy can be used to directly select which action to apply for a given planning context. When a learned generalized policy is imperfect, however, its application may fail to solve problems like in the case of the early systems in this category. These systems learned control-rules to guide the exploration of planning search trees. A control-rule is an IF–THEN rule that proposes node selection, pruning or ordering during tree exploration. A set of control rules can be viewed as a partial generalized policy since they do not provide action recommendation for all possible planning contexts. When a given control-rule recommendation was imperfect, it often prevented the planner from finding a solution plan. To exploit generalized policies more robustly, recent works have exploited the learned policy as an evaluation function within search algorithms like Beam-Search or Limited Discrepancy Search. These search algorithms allow planning to combine the guidance provided by the learned knowledge with other sources of advice like domain-independent heuristics.

4.2.2 Implementations

There are a group of systems that inductively learn control rules. Among them Inductive Learning Programming is the most popular learning technique. The GRASSHOPPER system (Leckie & Zukerman, Reference Leckie and Zukerman1991) used FOIL (Quinlan & Cameron-Jones, Reference Quinlan and Cameron-Jones1995) to learn control rules that guide the PRODIGY planner. There are also analytical systems: PRODIGY/EBL (Explanation Based Learning) module (Minton, Reference Minton1988) learned search control rules for the PRODIGY planner from a few examples of right and wrong decisions. STATIC (Etzioni, Reference Etzioni1993) obtains control rules without solving any problems. It simply uses EBL to analyze the relations between actions preconditions and effects. With the aim of overcoming the limitations of purely inductive and purely analytical approaches some researchers tried to combine them: the pioneering systems based on this principle are LEX-2 (Mitchell et al., Reference Mitchell, Utgoff and Banerji1982) and META-LEX (Keller, Reference Keller1987). AXA-EBL (Cohen, Reference Cohen1990) combined EBL and induction. It first learns control rules with EBL and then refines them with learning examples. DOLPHIN (Zelle & Mooney, Reference Zelle and Mooney1993; Estlin & Mooney, Reference Estlin and Mooney1996) was an extension of AxA-EBL that used FOIL as the inductive learning module. The HAMLET (Borrajo & Veloso, Reference Borrajo and Veloso1997) system combines deduction and induction incrementally. First it learns control rules with EBL that usually are too specific or general and then uses induction to generalize and specialize the rules. EvoCK (Aler et al., Reference Aler, Borrajo and Isasi2002) uses Genetic Programming to evolve the rules learned by Hamlet and yield more effective search control.

The problem of learning generalized policies was first studied by Roni Khardon. Khardon's L2Act (Khardon, Reference Khardon1999) induced generalized policies for both the Blocksworld and the Logistics domain by extending the decision list learning algorithm (Rivest, Reference Rivest1987) to the relational setting. This first approach presented two important weaknesses: (1) it relied on human-defined background knowledge that expressed key features of the domain, for example, the predicates above (block1, block2) or in_place (block) for the Blocksworld, and (2) the learned policies did not generalize well when the size of the problems increases. Martin and Geffner solved these limitations in the Blocksworld domain by changing the representation language of the generalized policies from predicate logic to concept language to learn recursive concepts (Martin & Geffner, Reference Martin and Geffner2000).

Recently the scope of generalized policy learning has increased over a variety of domains making this approach competitive with state-of-the-art planners. This achievement is due to two new ideas: (1) the policy representation language is enriched with extra predicates that capture more effective domain-specific knowledge; and (2) the learned policies are applied not greedily but within the framework of heuristic search algorithms. A prominent example is the OBTUSEWEDGE system (Yoon et al., Reference Yoon, Fern and Givan2007), the best learner of the IPC-2008 learning track. This system enriches the knowledge of the current state with the relaxed planning graph and uses the learned policies to generate look-ahead states within a Best-First Search. ROLLER (de la Rosa et al., Reference de la Rosa, Jiménez and Borrajo2008) defined the problem of learning generalized policies as a two-step standard classification process. In the first step a classifier captures the preferred operator to be applied in the different planning contexts. In the second one, another classifier captures the preferred bindings for each operator in a given domain's different planning contexts. These contexts are defined by the set of helpful actions extracted from a given state's relaxed planning graph, the goals still unachieved, and the the planning task's static predicates.

Systems also exist that represent generalized policies through collections of planning instances, as CBR systems for AP. Instance-based AP systems are not usually competitive in a variety of domains because they present the drawback of having to define an appropriate similarity metric that works well in different kinds of domains. The PRIAR system (Kambhampati & Hendler, Reference Kambhampati and Hendler1992) proposed integrating the modification of plans with generative planning. PRODIGY/ANALOGY (Veloso & Carbonell, Reference Veloso and Carbonell1993) introduced the application of derivational analogy to planning. It stored planning traces to avoid failure paths in future problem solving episodes. To retrieve similar planning traces, PRODIGY/ANALOGY indexed them using the minimum preconditions to reach a set of goals. The case-based planning system PARIS (Bergmann & Wilke, Reference Bergmann and Wilke1996) proposed the introduction of abstraction techniques to store the cases organized in a hierarchical memory. This technique improves the flexibility of the cases adaptation, thus increasing the coverage of a single case. DISTILL (Winner & Veloso, Reference Winner and Veloso2003) incorporates example plans into a structure called dsPlanner. DISTILL converts the plan into a parameterized if-statement and searches through each of the if-statements already stored in the dsPlanner to merge them. If the learned dsPlanner is accurate, it can be used directly to solve any problem from the domain without search. CABALA (de la Rosa et al., Reference de la Rosa, García-Olaya and Borrajo2007) uses object centered solution plans, called typed sequences, for node ordering during the plan search in heuristic planning. Another instance-based learner, REPLICA, implemented a Nearest Prototype Learning (García-Durán et al., Reference García-Durán, Fernández and Borrajo2012) using a relational distance inspired by the metrics used in relational data-mining. OAKPlan (Serina, Reference Serina2010) uses a compact graph structure to encode planning problems. This structure provides a detailed description of the planning problem's topology and allows the learner to define an effective retrieval procedure based on kernel functions.

In de la Rosa et al. (Reference de la Rosa, Jiménez, García-Durán, Fernández, García-Olaya and Borrajo2009) a planning system was recently described that was able to benefit from generalized policies represented in any of the two approaches (rules or instances). This system queries the policies for fixing the flaws of relaxed plans, and then it uses the resulting relaxed plans as grounded macro-actions in a Best-First Search.

4.3 Generalized heuristic functions

Heuristic functions are used in AP to focus the search of a solution plan on the search nodes that seem the most promising. Heuristic functions for AP compute an estimate of the distance from a given search node to a node in which goals are satisfied. Domain-independent heuristic functions for AP can be directly derived from the cost of the solutions to a relaxed task. The most common relaxation of the AP task consists of ignoring the delete effects of actions. Most of today's heuristic planners rely on this idea to implement their heuristics. Since this approach is domain independent, it fails to capture planning domains singularities. This section describes how to obtain AP heuristics that capture domain-specific knowledge with ML. It focuses on heuristics for the most popular search approach in AP, the forward state-space search.

4.3.2 Implementations

In Yoon et al. (Reference Yoon, Fern and Givan2006), the authors build a generalized heuristic function through linear regression. They learn domain-specific corrections $ {\rm{\rDelta }}(s;A;G)\, = \,\mathop{\sum}\limits_i {{w}_i} * {{f}_i}(s;A;G) $ to the relaxed plan heuristic RPH (s; A; G) introduced by the FF planner (Hoffmann & Nebel, Reference Hoffmann and Nebel2001b). These corrections are expressed as a weighted linear combination of features, where w_i are the weights and f_i represent the different features of the planning context. The regression examples consist of observations of the true distance to the goals from different states obtained with the FF planner. The resulting heuristic function,

$$ H(s;A;G)\, = \,RPH(s;A;G)\, + \,{\rm{\rDelta }}(s;A;G) $$

provides more accurate estimates that capture domain-specific regularities.

The previous approach ignores the actual performance of the heuristic when used in a search algorithm. It may attempt to learn corrections for the heuristic even if it provides good guidance during search. In Xu et al. (Reference Xu, Fern and Yoon2007), they present an alternative approach that only considers learning when the heuristic misleads in a given search strategy. The heuristic learned by this approach,

$$ H(s;A;G)\, = \,\mathop{\sum}\limits_i {{w}_i} * {{f}_i}(s;A;G) $$

only attempts to discriminate between good and bad states well enough to find the goals within a Beam-Search procedure, rather than attempting to model the distance to the goals precisely. This approach implements the following weight learning strategy. For each state s_j in the solution to a learning problem, if s_j is not contained in the search's beam_j, there is a search error. In this case, weights are updated like the Perceptron's weights, so that state s_j will be preferred by the heuristic, remaining in the beam_j in future search episodes.

4.4 Hierarchical decomposition methods

An extended strategy for coping with problem's complexity is to decompose problems into simpler sub-problems. When an effective decomposition is found, the sum of the costs of addressing the sub-problems is smaller than the cost of directly addressing the original problem. Hierarchical Task Networks (HTN) is one of the best studied approaches for modeling AP task decomposition. The HTN approach combines hierarchical domain-specific representations of the planning task and domain-independent search strategies for problem solving.

The input to a HTN planner includes an action model that encodes a set of primitive actions similar to the STRIPS actions used in classical planning and a task model. The task model defines a set of methods which describes how tasks should be decomposed into subtasks in a particular domain. The job of the HTN planner consists of exploiting the task model to decompose a given planning task into simpler subtasks until a sequence of primitive actions is generated. Figure 17 shows the primitive action unstack and the method for the task move-block from a HTN description of the Blocksworld domain. This method moves a block to its final position by defining two subtasks: moving-x-from-y-to-z that unstacks block x from y, in order to stack x on z, and moving-x-from-table-to-z that picks-up block x from the table and stacks it on z. In both subtasks, the method checks that the block x can be directly moved to its final position (primitive actions check, check2 and check3) and makes sure that x will not be moved in the future.

Figure 17

Examples of operator and method for Hierarchical Task Network planning in the Blocksworld domain

Current HTN planners, such as SHOP2 Nau-shop2-jair03, can outperform state-of-the-art domain-independent planners and provide a natural modeling framework for many real-world applications like fire extinction (Castillo et al., Reference Castillo, Fdez-Olivares, García-Pérez and Palao2006), evacuation planning (Muñoz-Avila et al., Reference Muñoz-Avila, Aha, Breslow and Nau1999) or game playing (Nau et al., Reference Nau, Smith and Erol1998). Defining effective decomposition methods is still complex because these methods reflect deep knowledge of the domain. The operator and method shown in Figure 17 belong to a HTN representation of the block-stacking algorithm (Erol et al., Reference Erol, Nau and Subrahmanian1992). Below we review some learning approaches to automatically define decomposition methods within the HTN planning paradigm.

4.4.1 Learning hierarchical decomposition methods

1. 1. Knowledge representation. A HTN method is a procedure that describes how to decompose a non-primitive task into primitive tasks or simpler non-primitive tasks. A method m is formally defined by a triple m = 〈head, preconds, subtasks〉, where head represents the name and parameters of the task to decompose, preconds is a logical formula denoting the method preconditions, and subtasks is a partially ordered sequence of subtasks. A method m is applicable to a state s and task t if head(m) matches t and the preconds(m) are satisfied in s. The result of applying a method m to a state s and task t is the sequence of subtasks subtasks(m).

2. 2. Learning examples. Learning examples consist of a set of planning problems, that is a set of pairs 〈s ₀, G〉 where s ₀ is an initial state and G is a set of goals, together with the corresponding solution plans p = (a ₁, a ₂, …, a_n). These solution plans can be human provided or generated by a classical planner.

3. 3. Learning algorithm. The algorithms reviewed in Section 3 to learn the action model preconditions can also be applied to learn the HTN method preconditions. A reduced version of the HTN method decompositions can be induced by using hierarchical layers of macros. Decompositions induced following this approach do not exploit the HTNs full expressive power that includes definitions of alternative decompositions, recursive concepts or loops. At this point, there is no completely automatic algorithm for learning subtask decompositions that benefits from HTNs full expressiveness. Some algorithms need to start from decomposition methods partially specified by humans, others need hierarchical plans (which implies previously specified methods) and some others need certain tasks called annotated tasks specified that define the equivalence of the HTN tasks and the set of goals G in a classical version of the AP problem.

4. 4. Exploitation of the learned knowledge. The generality level of the learned knowledge is the key issue to make a given HTN description effective. Learning decomposition methods that are too general may produce infinite recursion when problem solving, decreasing the advantages of HTN planning over classical planning. On the other hand, learning too specific HTN methods is less likely to be effective in decomposing new problems. Current methods to address this trade-off are based on measuring the performance of the learned model against a set of test problems.

4.4.2 Implementations

CAMEL (Ilghami et al., Reference Ilghami, Nau and Muñoz-Avila2002) learns the preconditions of HTN decomposition methods from observations of plan traces, using the version space algorithm (Mitchell, Reference Mitchell1997). CAMEL is designed for domains where the planner receives multiple methods per task, but not their preconditions. The structure of the hierarchy here is known in advance and the learning task tries to identify under which conditions the different hierarchies are applicable. This approach requires many plan traces to completely converge (completely determine the preconditions of all methods). CAMEL++ (Ilghami et al., Reference Ilghami, Muñoz-Avila, Nau and Aha2005) enables the planner to start planning before the method preconditions are fully learned. By doing so, the planner can start solving planning problems with a smaller number of training examples. Both CAMEL and CAMEL++ require each input plan trace needs to contain extra information so that the learner could acquire the models. At each decomposition point in a plan trace, the learner needs to have all the applicable method instances, not just the one that was actually used.

The HTN Domain Learning (HDL) algorithm (Ilghami et al., Reference Ilghami, Nau and Muñoz-Avila2006) starts with no prior information about the methods. It examines hierarchical plan traces produced by an expert problem-solver. For each decomposition point in the traces, HDL checks to see if the responsible method is already present. If not, HDL creates a new method and initializes a new version space to capture its preconditions. The method that was actually used to decompose the corresponding task serves as a positive example and the methods that matched that task but whose preconditions failed, serve as negative examples for the corresponding version space.

HTN-Maker (Hogg et al., Reference Hogg, Muñoz-Avila and Kuter2008) generates an HTN domain model from a STRIPS domain model, a collection of plans p generated by a STRIPS planner, and a collection of annotated tasks. An annotated task is a triple (n, Pre, Effects) where n is a task, Pre is a set of atoms known as the preconditions, and Eff is a set of atoms known as the effects. HTN-Maker first generates the list of states S = (s ₀, …, s_n) by applying the actions in the plan p starting from the initial state s ₀. Then, it traverses these states, and if there is an annotated task whose effects match the state s_{i + n} and whose preconditions match the state s_i, it regresses the effects of the annotated task through (1) previously learned methods or (2) a primitive task if there are no previously learned methods.

4.5 Learning planning search control in domains with uncertainty

When planning in domains with uncertainty, the combinatorial explosion problem becomes even more acute. Partial observability of the environment and non-deterministic outcomes of actions multiply the number of states that can be reached, and increase the complexity of the search processes. Search control knowledge can help reduce this complexity but as mentioned before, hand-coding this knowledge is difficult and requires expertise on the domain and the planner. There is a review of techniques for Planning Under Uncertainty (PUU) that improve their own scalability through ML. These techniques preserve the representation formalisms and learning algorithms reviewed in the section but adapt the mechanisms to generate the learning examples and apply the learned knowledge to the PUU framework:

• • Macro-actions. In Theocharous and Kaelbling (Reference Theocharous and Kaelbling2003), the authors solve large Partially Observable Markov Decision Processes (POMDP) by using a dynamically created finite-grid approximation of the belief space and then applying dynamic programming to compute a value function at the grid points. This work exploits macro-actions to visit a significantly smaller part of the belief space of the POMDP than with simple primitive actions. Macro-actions also make the convergence of the dynamic programming faster because the agent can look further into the future.

• • Generalized policies. Given a set of small probabilistic planning problems, the work presented in Yoon et al. (Reference Yoon, Fern and Givan2002) uses the probabilistic planner PGraphplan to synthesize solution plans p = (a ₁, a ₂, …, a_n) corresponding to a sequence of state transitions (s ₀, s ₁, …, s_n) such that s_i results from executing action a_i in the state s_{i −1} and s_n is a goal state. The execution of plans p are simulated one action at a time. If the state resulting from simulating a_i is different from s_i, then a new plan is computed to attain the goals in the new state. This process is repeated until a goal state is reached or a limit of simulations is exceeded. A generalized policy is then learned from the pairs (state,action) traversed in the simulations. In many domains, solutions to small problems do not capture the singularities of larger problems. As an alternative, in Fern et al. (Reference Fern, Yoon and Givan2006) the authors learn the generalized policy from pairs (state, action) generated following the Approximate Policy Iteration algorithm (Bertsekas & Tsitsiklis, Reference Bertsekas and Tsitsiklis1996).

• • Generalized evaluation functions. Given a set of small probabilistic planning problems, the approach presented in Gretton and Thiébaux (Reference Gretton and Thiébaux2004) computes the optimal policies for the problems with a MDP solver. Then, it uses first-order regression to generalize a first-order value function over the values of optimal policies. In Sanner and Boutilier (Reference Sanner and Boutilier2005, Reference Sanner and Boutilier2006) the authors solve First Order MDPs (FOMDPs) by representing the value function linearly with respect to a set of first-order basis functions and computing suitable weights by casting the corresponding optimization as a first-order linear program.

• • Decomposition methods. In Hogg et al. (Reference Hogg, Kuter and Muñoz-Avila2009), the HTN-Maker algorithm has been adapted to non-deterministic planning domains, where actions may have multiple possible outcomes.

5.1. Model-based and model-free reinforcement learning

RL was primarily concerned with obtaining optimal policies when the model of the environment is unknown but actually, there are two ways to proceed. Model-Based RL requires a environment's model consisting of a transition and a reward model. Model-Based RL typically relies on standard dynamic programming algorithms (Bellman & Kalaba, Reference Bellman and Kalaba1965; Bertsekas, Reference Bertsekas1995) to find a value/heuristic function that provides optimal policies. Learning in Model-Based RL is understood as in Real-Time Heuristic search (Korf, Reference Korf1990; Bulitko & Lee, Reference Bulitko and Lee2006; Hernández & Meseguer, Reference Hernández and Meseguer2007), that is, as local updates of the value/heuristic function with information obtained from simulation.

Model-Free RL does not require a model of the environment. Below, there are two different approaches for the Model-Free RL task:

• • Combining learning action models with Model-Based RL. This approach learns a transition model of the environment and applies standard dynamic programming algorithms to find a good policy.

• • Pure Model-free RL. In domains with large uncertainty learning to achieve goals is easier than learning a model of the environment. Pure Model-free RL algorithms do not model the decision-making as a function of the state, like value/heuristic functions, but with a function of pairs 〈state, action〉 called action-value functions. The Q-function, which provides a measure of the expected reward for taking action a at state s, is an example of an action-value function. Q-learning (Watkins, Reference Watkins1989), a well-known Pure Model-free RL algorithm, updates the Q-function with every observed tuple 〈s, a, s′, r〉 (s′ represents the new state and r represents the obtained reward). Q-learning completes the update of the Q-function using the following formula:

  $$ {{Q}_{t\, + \,1}}(s,a):\, = \,{{Q}_t}(s,a)\, + \,\alpha (r(s,a)\, + \,\gamma \mathop {\,\max \,}\limits_{a^{\prime}} Q(s^{\prime},a^{\prime})\, \minus \,{{Q}_t}(s,a)) $$

  where α is the learning rate that determines to what extent the newly acquired information overrides the old information. When α = 0 the agent does not learn anything, while when α = 1 the agent only considers the most recent information. γ is the discount factor which determines the importance of future rewards. A factor of γ = 0 makes the agent greedy (the agent only considers current rewards), while a factor approaching 1 makes the agent strive for a long-term high reward. Pure model-free RL also includes Monte Carlo methods (Barto & Duff, Reference Barto and Duff1994). Most of pure model-free RL methods guarantee to find optimal policies and use very little computation time per observation. However, they typically make inefficient use of the collected observations and require extensive experience to achieve good performance.

5.2 Relational reinforcement learning

This section reviews Relational Reinforcement Learning (RRL) (Dzeroski et al., Reference Dzeroski, Raedt and Driessens2001; Otterlo, Reference Otterlo2009) given that RRL uses a knowledge representation similar to one used in learning for AP. The section focuses on pure model-free RRL since techniques for learning relational action models were already discussed in Section 3. Further explanations on model-based RRL can be found in Boutilier et al. (Reference Boutilier, Reiter and Price2001), Wang et al. (Reference Wang, Joshi and Khardon2007) and Sanner and Kersting (Reference Sanner and Kersting2010) also referenced as Relational, Symbolic or First Order Dynamic Programming.

1. 1. Knowledge representation. The learned knowledge is represented in the form of a First Order policy π: S→A that maps relational states—coded in predicate logic—into the preferred action to apply next for achieving a set of First Order goals. Unlike generalized policies for AP (Section 4), RRL policies do not include information on different goals. RRL policies only capture how to solve a particular task or a particular set of tasks, like the same task with different number of objects. RRL requires consequently learning from scratch or at least, some kind of transfer learning (Taylor & Stone, Reference Taylor and Stone2007; Mehta et al., Reference Mehta, Natarajan, Tadepalli and Fern2008) when the nature of goals change. Transfer learning is defined as exploiting data from one or more source tasks to improve learning performance in a different target task.

   A First Order policy can be implicitly represented as a First Order Q-function Q(〈S,A〉) = R that maps pairs state-action S−A into their expected reward R. This representation is closely related to the concept of heuristic function used in AP that maps states into an estimate of the cost to pay (negative reward) for achieving the goals. In AP this cost estimate can be automatically extracted from the problem representation by ignoring the delete effects of actions.

2. 2. Learning examples. Learning examples consist of tuples 〈s_i, a_i, s_{i + 1}, r_i〉 where a_i is the action applied at state s_i, s_{i + 1} is the resulting state and r_i is the obtained reward. Learning examples in RRL are typically generated from random exploration.

3. 3. Learning algorithm. There are different approaches for model-free RRL:

   • • Relational learning of the q-value function. This approach uses relational regression to generalize the value function. Figure 18 shows a relational regression tree that captures the q-values of action move(Block,Block) when solving the set of tasks on(Block,Block) in a three blocks Blocksworld.

     Figure 18

     Relational regression tree for the goals on (X,Y) in a three blocks Blocksworkd

     

   • • Relational learning of the optimal policy. An alternative approach is to directly learn the policy. This approach requires relational classification instead of relational regression. The advantage of this approach is that, usually, it is easier to understand policies than to understand value functions for structured domains. Figure 19 shows a RRL policy that captures when the selection of action move(Block,Block) is optimal for solving the set of tasks on(Block,Block) in a three blocks Blocksworld domain.

     Figure 19

     Relational Reinforcement Learning policy for the goals on (X,Y) in a three blocks Blocksworkd

     

5.3 Implementations

With regard to learning a relational Q-function, different relational regression algorithms have been tried:

• • Relational regression trees (Dzeroski et al., Reference Dzeroski, Raedt and Driessens2001). For each pair (action, relational-goal), a regression tree is built from a set of examples with the form (state,q-value). Leaf nodes of the tree represent the predictions of the q-value. Test nodes of the tree represent the facts that have to hold for the predictions to come true.

• • Instance-based algorithms with relational distance (Driessens & Ramon, Reference Driessens and Ramon2003). This work implements a k-nearest neighbor prediction. The prediction computes a weighted average for the q-values of the collected examples. Weights used for the prediction are inversely proportional to the distance to the examples. The used distance copes with relational representations for states and actions.

• • Relational Kernels methods (Gartner et al., Reference Gartner, Driessens and Ramon2003). These methods use the incrementally learnable Gaussian processes for Bayesian-regression to build mappings of (state,action) pairs into q-values. Graph kernels are used as the covariance function between state-action pairs to employ Gaussian processes in the relational setting.

With regard to directly learning a relational policy (Dzeroski et al., Reference Dzeroski, Raedt and Driessens2001) uses relational decision trees to determine which actions are optimal in the different environment's states when achieving a particular task.