DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Review of Machine Learning for Automated Planning
---
paper_title: Using temporal logics to express search control knowledge for planning

paper_content:

Over the years increasingly sophisticated planning algorithms have been developed. These have made for more efficient planners, but unfortunately these planners still suffer from combinatorial complexity even in simple domains. Theoretical results demonstrate that planning is in the worst case intractable. Nevertheless, planning in particular domains can often be made tractable by utilizing additional domain structure. In fact, it has long been acknowledged that domain independent planners need domain dependent information to help them plan effectively. In this work we present an approach for representing and utilizing domain specific control knowledge. In particular, we show how domain dependent search control knowledge can be represented in a temporal logic, and then utilized to effectively control a forward-chaining planner. There are a number of advantages to our approach, including a declarative semantics for the search control knowledge; a high degree of modularity (new search control knowledge can be added without affecting previous control knowledge); and an independence of this knowledge from the details of the planning algorithm. We have implemented our ideas in the TLPLAN system, and have been able to demonstrate its remarkable effectiveness in a wide range of planning domains.
---
paper_title: Learning-Assisted Automated Planning: Looking Back, Taking Stock, Going Forward

paper_content:

This article reports on an extensive survey and analysis of research work related to machine learning as it applies to automated planning over the past 30 years. Major research contributions are broadly characterized by learning method and then descriptive subcategories. Survey results reveal learning techniques that have extensively been applied and a number that have received scant attention. We extend the survey analysis to suggest promising avenues for future research in learning based on both previous experience and current needs in the planning community.
---
paper_title: STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving

paper_content:

We describe a new problem solver called STRIPS that attempts to find a sequence of operators in a space of world models to transform a given initial world model into a model in which a given goal formula can be proven to be true. STRIPS represents a world model as an arbi trary collection of first-order predicate calculus formulas and is designed to work with models consisting of large numbers of formulas. It employs a resolution theorem prover to answer (juestions of particular models and uses means-ends analysis to guide it to the desired goal-satisfying model.
---
paper_title: SHOP2: An HTN Planning System

paper_content:

The SHOP2 planning system received one of the awards for distinguished performance in the 2002 International Planning Competition. This paper describes the features of SHOP2 which enabled it to excel in the competition, especially those aspects of SHOP2 that deal with temporal and metric planning domains.
---
paper_title: The Computational Complexity of Propositional STRIPS Planning

paper_content:

Abstract I present several computational complexity results for propositional STRIPS planning, i.e., STRIPS planning restricted to ground formulas. Different planning problems can be defined by restricting the type of formulas, placing limits on the number of pre-and postconditions, by restricting negation in pre- and postconditions, and by requiring optimal plans. For these types of restrictions, I show when planning is tractable (polynomial) and intractable (NP-hard). In general, it is PSPACE-complete to determine if a given planning instance has any solutions. Extremely severe restrictions on both the operators and the formulas are required to guarantee polynomial time or even NP-completeness. For example, when only ground literals are permitted, determining plan existence is PSPACE-complete even if operators are limited to two preconditions and two postconditions. When definite Horn ground formulas are permitted, determining plan existence is PSPACE-complete even if operators are limited to zero preconditions and one postcondition. One of the interesting tractable problems is if each operator is restricted to positive preconditions and one postcondition (only ground literals). The blocks-world problem, slightly modified, is a subproblem of this restricted planning problem. These results in combination with previous analyses are not encouraging for domain-independent planning.
---
paper_title: Robotics in Remote and Hostile Environments

paper_content:

In our continuing quest for knowledge, robots are powerful tools for accessing environments too dangerous or too remote for human exploration. Early systems functioned under close human supervision, effectively limited to executing preprogrammed tasks. However, as exploration moves to regions where communication is ineffective or unviable, robots will need to carry out complex tasks without human supervision. To enable such capabilities, robots are being enhanced by advances ranging from new sensor development to automated mission planning software, distributed robotic control, and more efficient power systems. As robotics technology becomes simultaneously more capable and economically viable, individual robots operated at large expense by teams of experts are increasingly supplemented by teams of robots used cooperatively under minimal human supervision.
---
paper_title: Reinforcement Learning: A Survey

paper_content:

This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning.
---
paper_title: Planning as Heuristic Search

paper_content:

In the AIPS98 Planning Contest, the HSP planner showed that heuristic search planners can be competitive with state-of-the-art Graphplan and SAT planners. Heuristic search planners like HSP transform planning problems into problems of heuristic search by automatically extracting heuristics from Strips encodings. They differ from specialized problem solvers such as those developed for the 24-Puzzle and Rubik’s Cube in that they use a general declarative language for stating problems and a general mechanism for extracting heuristics from these representations. In this paper, we study a family of heuristic search planners that are based on a simple and general heuristic that assumes that action preconditions are independent. The heuristic is then used in the context of best-first and hill-climbing search algorithms, and is tested over a large collection of domains. We then consider variations and extensions such as reversing the direction of the search for speeding node evaluation, and extracting information about propositional invariants for avoiding dead-ends. We analyze the resulting planners, evaluate their performance, and explain when they do best. We also compare the performance of these planners with two state-of-the-art planners, and show that the simplest planner based on a pure best-first search yields the most solid performance over a large set of problems. We also discuss the strengths and limitations of this approach, establish a correspondence between heuristic search planning and Graphplan, and briefly survey recent ideas that can reduce the current gap in performance between general heuristic search planners and specialized solvers.  2001 Elsevier Science B.V. All rights reserved.
---
paper_title: Symbolic pattern databases in heuristic search panning

paper_content:

This paper invents symbolic pattern databases (SPDB) to combine two influencing aspects for recent progress in domain-independent action planning, namely heuristic search and model checking. SPDBs are off-line computed dictionaries, generated in symbolic backward traversals of automatically inferred planning space abstractions. ::: ::: The entries of SPDBs serve as heuristic estimates to accelerate explicit and symbolic, approximate and optimal heuristic search planners. Selected experiments highlight that the symbolic representation yields much larger and more accurate pattern databases than the ones generated with explicit methods.
---
paper_title: Fast Planning Through Planning Graph Analysis

paper_content:

Abstract We introduce a new approach to planning in STRIPS-like domains based on constructing and analyzing a compact structure we call a planning graph. We describe a new planner, Graphplan, that uses this paradigm. Graphplan always returns a shortest possible partial-order plan, or states that no valid plan exists. We provide empirical evidence in favor of this approach, showing that Graphplan outperforms the total-order planner, Prodigy and the partial-order planner, UCPOP, on a variety of interesting natural and artificial planning problems. We also give empirical evidence that the plans produced by Graphplan are quite sensible. Since searches made by this approach are fundamentally different from the searches of other common planning methods, they provide a new perspective on the planning problem.
---
paper_title: The FF Planning System: Fast Plan Generation Through Heuristic Search

paper_content:

We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP's heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.
---
paper_title: Ordered Landmarks in Planning

paper_content:

Many known planning tasks have inherent constraints concerning the best order in which to achieve the goals. A number of research efiorts have been made to detect such constraints and to use them for guiding search, in the hope of speeding up the planning process. ::: ::: We go beyond the previous approaches by considering ordering constraints not only over the (top-level) goals, but also over the sub-goals that will necessarily arise during planning. Landmarks are facts that must be true at some point in every valid solution plan. We extend Koehler and Hoffmann's definition of reasonable orders between top level goals to the more general case of landmarks. We show how landmarks can be found, how their reasonable orders can be approximated, and how this information can be used to decompose a given planning task into several smaller sub-tasks. Our methodology is completely domain- and planner-independent. The implementation demonstrates that the approach can yield significant runtime performance improvements when used as a control loop around state-of-the-art sub-optimal planning systems, as exemplified by FF and LPG.
---
paper_title: Mixed-Initiative Activity Planning for Mars Rovers

paper_content:

One of the ground tools used to operate the Mars Exploration Rovers is a mixed-initiative planning system called MAPGEN. The role of the system is to assist operators building daily plans for each of the rovers, maximizing science return, while maintaining rover safety and abiding by science and engineering constraints. ::: ::: In this paper, we describe the MAPGEN system, focusing on the mixed-initiative planning aspect. We note important challenges, both in terms of human interaction and in terms of automated reasoning requirements. We then describe the approaches taken in MAPGEN, focusing on the novel methods developed by our team.
---
paper_title: Adaptive Control for Autonomous Underwater Vehicles

paper_content:

We describe a novel integration of Planning with Probabilistic State Estimation and Execution. The resulting system is a unified representational and computational framework based on declarative models and constraint-based temporal plans. The work is motivated by the need to explore the oceans more cost-effectively through the use of Autonomous Underwater Vehicles (AUV), requiring them to be goal-directed, perceptive, adaptive and robust in the context of dynamic and uncertain conditions. The novelty of our approach is in integrating deliberation and reaction over different temporal and functional scopes within a single model, and in breaking new ground in oceanography by allowing for precise sampling within a feature of interest using an autonomous robot. The system is general-purpose and adaptable to other ocean going and terrestrial platforms.
---
paper_title: Searching for Planning Operators with Context-Dependent and Probabilistic Effects

paper_content:

Providing a complete and accurate domain model for an agent situated in a complex environment can be an extremely difficult task. Actions may have different effects depending on the context in which they are taken, and actions mayor may not induce their intended effects, with the probability of success again depending on context. We present an algorithm for automatically learning planning operators with context-dependent and probabilistic effects in environments where exogenous events change the state of the world. Empirical results show that the algorithm successfully finds operators that capture the true structure of an agent's interactions with its environment, and avoids spurious associations between actions and exogenous events.
---
paper_title: Rule Creation and Rule Learning Through Environmental Exploration

paper_content:

The task of learning from environment is specified. It requires the learner to infer the laws of the environment in terms of its percepts and actions, and use the laws to solve problems. Based on research on problem space creation and discrimination learning, this paper reports an approach in which exploration, rule creation and rule learning are coordinated in a single framework. With this approach, the system LIVE creates STRIPS-Iike rules by noticing the changes in the environment when actions are taken, and later refines the rules by explaining the failures of their predictions. Unlike many other learning systems, since LIVE treats learning and problem solving as interleaved activities, no training instance nor any concept hierarchy is necessary to start learning. Furthermore, the approach is capable of discovering hidden features from the environment when normal discrimination process fails to make any progress.
---
paper_title: Learning Partially Observable Deterministic Action Models

paper_content:

We present the first tractable, exact solution for the problem of identifying actions' effects in partially observable STRIPS domains. Our algorithms resemble Version Spaces and Logical Filtering, and they identify all the models that are consistent with observations. They apply in other deterministic domains (e.g., with conditional effects), but are inexact (may return false positives) or inefficient (we could not bound the representation size). Our experiments verify the theoretical guarantees, and show that we learn STRIPS actions efficiently, with time that is significantly better than approaches for HMMs and Reinforcement Learning (which are inexact). Our results are especially surprising because of the inherent intractability of the general deterministic case. These results have been applied to an autonomous agent in a virtual world, facilitating decision making, diagnosis, and exploration.
---
paper_title: Acquisition of object-centred domain models from planning examples

paper_content:

The problem of formulating knowledge bases containing action schema is a central concern in knowledge engineering for AI Planning. This paper describes LOCM, a system which carries out the automated induction of action schema from sets of example plans. Each plan is assumed to be a sound sequence of actions; each action in a plan is stated as a name and a list of objects that the action refers to. LOCM exploits the assumption that actions change the state of objects, and require objects to be in a certain state before they can be executed. The novelty of LOCM is that it can induce action schema without being provided with any information about predicates or initial, goal or intermediate state descriptions for the example action sequences. In this paper we describe the implemented LOCM algorithm, and analyse its performance by its application to the induction of domain models for several domains. To evaluate the algorithm, we used random action sequences from existing models of domains, as well as solutions to past IPC problems.
---
paper_title: Acquiring domain knowledge for planning by experimentation

paper_content:

In order for autonomous systems to interact with their environment in an intelligent way, they must be given the ability to adapt and learn incrementally and deliberately. It is virtually impossible to devise and hand code all potentially relevant domain knowledge for complex dynamic tasks. This thesis describes a framework to acquire domain knowledge for planning by failure-driven experimentation with the environment. The initial domain knowledge in the system is an approximate model for planning in the environment, defining the system's expectations. The framework exploits the characteristics of planning domains in order to search the space of plausible hypotheses without the need for additional background knowledge to build causal explanations for expectation failures. Plans are executed while the external environment is monitored, and differences between the internal state and external observations are detected by various methods each correlated with a typical cause for the expectation failure. The methods also construct a set of concrete hypotheses to repair the knowledge deficit. After being heuristically filtered, each hypothesis is tested in turn with an experiment. After the experiment is designed, a plan is constructed to achieve the situation required to carry out the experiment. The experiment plan must meet constraints such as minimizing plan length and negative interference with the main goals. The thesis describes a set of domain-independent constraints for experiments and their incorporation in the planning search space. After the execution of the plan and the experiment, observations are collected to conclude if the experiment was successful or not. Upon success, the hypothesis is confirmed and the domain knowledge is adjusted. Upon failure, the experimentation process is iterated on the remaining hypotheses until success or until no more hypotheses are left to be considered. This framework has shown to be an effective way to address incomplete planning knowledge and is demonstrated in a system called EXPO, implemented on the scPRODIGY planning architecture. The effectiveness and efficiency of EXPO's methods is empirically demonstrated in several domains, including a large-scale process planning task, where the planner can recover from situations missing up to 50% of domain knowledge through repeated experimentation.
---
paper_title: Learning Action Models for Reactive Autonomous Agents

paper_content:

To be maximally effective, autonomous agents such as robots must be able both to react appropriately in dynamic environments and to plan new courses of action in novel situations. Reliable planning requires accurate models of the effects of actions--models which are often more appropriately learned through experience than design. This thesis describes TRAIL (Teleo-Reactive Agent with Inductive Learning), an integrated agent architecture which learns models of actions based on experiences in the environment. These action models are then used to create plans that combine both goal-directed and reactive behaviors. ::: Previous work on action-model learning has focused on domains that contain only deterministic, atomic action models that explicitly describe all changes that can occur in the environment. The thesis extends this previous work to cover domains that contain durative actions, continuous variables, nondeterministic action effects, and actions taken by other agents. Results have been demonstrated in several robot simulation environments and the Silicon Graphics, Inc. flight simulator. ::: The main emphasis in this thesis is on the action-model learning process within TRAIL. The content begins the learning process by recording experiences in its environment either by observing a trainer or by executing a plan. Second, the agent identifies instances of action success or failure during these experiences using a new analysis demonstrating nine possible causes of action failure. Finally, a variant of the Inductive Logic Programming algorithm DINUS is used to induce action models based on the action instances. As the action models are learned, they can be used for constructing plans whose execution contributes to additional learning experiences. Diminishing reliance on the teacher signals successful convergence of the learning process.
---
paper_title: Using kernel perceptrons to learn action effects for planning

paper_content:

We investigate the problem of learning action effects in STRIPS and ADL planning domains. Our approach is based on a kernel perceptron learning model, where action and state information is encoded in a compact vector representation as input to the learning mechanism, and resulting state changes are produced as output. Empirical results of our approach indicate efficient training and prediction times, with low average error rates (< 3%) when tested on STRIPS and ADL versions of an object manipulation scenario. This work is part of a project to integrate machine learning techniques with a planning system, as part of a larger cognitive architecture linking a high- level reasoning component with a low-level robot/vision system.
---
paper_title: Learning Symbolic Models of Stochastic Domains

paper_content:

In this article, we work towards the goal of developing agents that can learn to act in complex worlds. We develop a probabilistic, relational planning rule representation that compactly models noisy, nondeterministic action effects, and show how such rules can be effectively learned. Through experiments in simple planning domains and a 3D simulated blocks world with realistic physics, we demonstrate that this learning algorithm allows agents to effectively model world dynamics.
---
paper_title: Deterministic planning in the fifth international planning competition: Pddl3 and experimental evaluation of the planners

paper_content:

The international planning competition (IPC) is an important driver for planning research. The general goals of the IPC include pushing the state of the art in planning technology by posing new scientific challenges, encouraging direct comparison of planning systems and techniques, developing and improving a common planning domain definition language, and designing new planning domains and problems for the research community. This paper focuses on the deterministic part of the fifth international planning competition (IPC5), presenting the language and benchmark domains that we developed for the competition, as well as a detailed experimental evaluation of the deterministic planners that entered IPC5, which helps to understand the state of the art in the field. We present an extension of pddl, called pddl3, allowing the user to express strong and soft constraints about the structure of the desired plans, as well as strong and soft problem goals. We discuss the expressive power of the new language focusing on the restricted version that was used in IPC5, for which we give some basic results about its compilability into pddl2. Moreover, we study the relative performance of the IPC5 planners in terms of solved problems, CPU time, and plan quality; we analyse their behaviour with respect to the winners of the previous competition; and we evaluate them in terms of their capability of dealing with soft goals and constraints, and of finding good quality plans in general. Overall, the results indicate significant progress in the field, but they also reveal that some important issues remain open and require further research, such as dealing with strong constraints and computing high quality plans in metric-time domains and domains involving soft goals or constraints.
---
paper_title: PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains

paper_content:

In recent years research in the planning community has moved increasingly toward s application of planners to realistic problems involving both time and many typ es of resources. For example, interest in planning demonstrated by the space res earch community has inspired work in observation scheduling, planetary rover ex ploration and spacecraft control domains. Other temporal and resource-intensive domains including logistics planning, plant control and manufacturing have also helped to focus the community on the modelling and reasoning issues that must be confronted to make planning technology meet the challenges of application. The International Planning Competitions have acted as an important motivating fo rce behind the progress that has been made in planning since 1998. The third com petition (held in 2002) set the planning community the challenge of handling tim e and numeric resources. This necessitated the development of a modelling langua ge capable of expressing temporal and numeric properties of planning domains. In this paper we describe the language, PDDL2.1, that was used in the competition. We describe the syntax of the language, its formal semantics and the validation of concurrent plans. We observe that PDDL2.1 has considerable modelling power --- exceeding the capabilities of current planning technology --- and presents a number of important challenges to the research community.
---
paper_title: Using genetic programming to learn and improve control knowledge

paper_content:

The purpose of this article is to present a multi-strategy approach to learn heuristics for planning. This multi-strategy system, called HAMLET-EvoCK, combines a learning algorithm specialized in planning (HAMLET) and a genetic programming (GP) based system (EVOCK: Evolution of Control Knowledge). Both systems are able to learn heuristics for planning on their own, but both of them have weaknesses. Based on previous experience and some experiments performed in this article, it is hypothesized that HAMLET handicaps are due to its example-driven operators and not having a way to evaluate the usefulness of its control knowledge. It is also hypothesized that even if HAMLET control knowledge is sometimes incorrect, it might be easily correctable. For this purpose, a GP-based stage is added, because of its complementary biases: GP genetic operators are not example-driven and it can use a fitness function to evaluate control knowledge. HAMLET and EVOCK are combined by seeding EVOCK initial population with HAMLET control knowledge. It is also useful for EVOCK to start from a knowledge-rich population instead of a random one. By adding the GP stage to HAMLET, the number of solved problems increases from 58% to 85% in the blocks world and from 50% to 87% in the logistics domain (0% to 38% and 0% to 42% for the hardest instances of problems considered).
---
paper_title: Learning Decision Lists

paper_content:

This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples. More precisely, this result is established for k-;DL – the set of decision lists with conjunctive clauses of size k at each decision. Since k-DL properly includes other well-known techniques for representing Boolean functions such as k-CNF (formulae in conjunctive normal form with at most k literals per clause), k-DNF (formulae in disjunctive normal form with at most k literals per term), and decision trees of depth k, our result strictly increases the set of functions that are known to be polynomially learnable, in the sense of Valiant (1984). Our proof is constructive: we present an algorithm that can efficiently construct an element of k-DL consistent with a given set of examples, if one exists.
---
paper_title: Searching for Planning Operators with Context-Dependent and Probabilistic Effects

paper_content:

Providing a complete and accurate domain model for an agent situated in a complex environment can be an extremely difficult task. Actions may have different effects depending on the context in which they are taken, and actions mayor may not induce their intended effects, with the probability of success again depending on context. We present an algorithm for automatically learning planning operators with context-dependent and probabilistic effects in environments where exogenous events change the state of the world. Empirical results show that the algorithm successfully finds operators that capture the true structure of an agent's interactions with its environment, and avoids spurious associations between actions and exogenous events.
---
paper_title: Efficient learning of action schemas and web-service descriptions

paper_content:

This work addresses the problem of efficiently learning action schemas using a bounded number of samples (interactions with the environment). We consider schemas in two languages--traditional STRIPS, and a new language STRIPS+WS that extends STRIPS to allow for the creation of new objects when an action is executed. This modification allows STRIPS+WS to model web services and can be used to describe web-service composition (planning) problems. We show that general STRIPS operators cannot be efficiently learned through raw experience, though restricting the size of action preconditions yields a positive result. We then show that efficient learning is possible without this restriction if an agent has access to a "teacher" that can provide solution traces on demand. We adapt this learning algorithm to efficiently learn web-service descriptions in STRIPS+WS.
---
paper_title: Rule Creation and Rule Learning Through Environmental Exploration

paper_content:

The task of learning from environment is specified. It requires the learner to infer the laws of the environment in terms of its percepts and actions, and use the laws to solve problems. Based on research on problem space creation and discrimination learning, this paper reports an approach in which exploration, rule creation and rule learning are coordinated in a single framework. With this approach, the system LIVE creates STRIPS-Iike rules by noticing the changes in the environment when actions are taken, and later refines the rules by explaining the failures of their predictions. Unlike many other learning systems, since LIVE treats learning and problem solving as interleaved activities, no training instance nor any concept hierarchy is necessary to start learning. Furthermore, the approach is capable of discovering hidden features from the environment when normal discrimination process fails to make any progress.
---
paper_title: CaMeL: Learning method preconditions for HTN planning

paper_content:

A great challenge in using any planning system to solve real-world problems is the difficulty of acquiring the domain knowledge that the system will need. We present away to address part of this problem, in the context of Hierarchical Task Network (HTN) planning, by having the planning system incrementally learn conditions for HTN methods under expert supervision. We present a general formal framework for learning HTN methods, and a supervised learning algorithm, named CaMeL, based on this formalism. We present theoretical results about CaMeL's soundness, completeness, and convergence properties. We also report experimental results about its speed of convergence under different conditions. The experimental results suggest that CaMeL has the potential to be useful in real-world applications.
---
paper_title: Learning Partially Observable Deterministic Action Models

paper_content:

We present the first tractable, exact solution for the problem of identifying actions' effects in partially observable STRIPS domains. Our algorithms resemble Version Spaces and Logical Filtering, and they identify all the models that are consistent with observations. They apply in other deterministic domains (e.g., with conditional effects), but are inexact (may return false positives) or inefficient (we could not bound the representation size). Our experiments verify the theoretical guarantees, and show that we learn STRIPS actions efficiently, with time that is significantly better than approaches for HMMs and Reinforcement Learning (which are inexact). Our results are especially surprising because of the inherent intractability of the general deterministic case. These results have been applied to an autonomous agent in a virtual world, facilitating decision making, diagnosis, and exploration.
---
paper_title: Acquiring Search-Control Knowledge via Static Analysis

paper_content:

Abstract Explanation-based learning (EBL) is a widely-used technique for acquiring search-control knowledge. Prieditis, van Harmelen, and Bundy pointed to the similarity between partial evaluation (PE) and EBL. However, EBL utilizes training examples whereas PE does not. It is natural to inquire, therefore, whether PE can be used to acquire search-control knowledge and, if so, at what cost? This paper answers these questions by means of a case study comparing prodigy/ebl , a state-of-the-art EBL system, and static , a PE-based analyzer of problem space definitions. When tested in prodigy/ebl 's benchmark problem spaces, static generated search-control knowledge that was up to three times as effective as the knowledge learned by prodigy/ebl , and did so from twenty-six to seventy-seven times faster. The paper describes static 's algorithms, compares its performance to prodigy/ebl 's, noting when static 's superior performance will scale up and when it will not. The paper concludes with several lessons for the design of EBL systems, suggesting hybrid PE/EBL systems as a promising direction for future research.
---
paper_title: Acquisition of object-centred domain models from planning examples

paper_content:

The problem of formulating knowledge bases containing action schema is a central concern in knowledge engineering for AI Planning. This paper describes LOCM, a system which carries out the automated induction of action schema from sets of example plans. Each plan is assumed to be a sound sequence of actions; each action in a plan is stated as a name and a list of objects that the action refers to. LOCM exploits the assumption that actions change the state of objects, and require objects to be in a certain state before they can be executed. The novelty of LOCM is that it can induce action schema without being provided with any information about predicates or initial, goal or intermediate state descriptions for the example action sequences. In this paper we describe the implemented LOCM algorithm, and analyse its performance by its application to the induction of domain models for several domains. To evaluate the algorithm, we used random action sequences from existing models of domains, as well as solutions to past IPC problems.
---
paper_title: Using cases utility for heuristic planning improvement

paper_content:

Current efficient planners employ an informed search guided by a heuristic function that is quite expensive to compute. Thus, ordering nodes in the search tree becomes a key issue, in order to select efficiently nodes to evaluate from the successors of the current search node. In a previous work, we successfully applied a CBR approach to order nodes for evaluation, thus reducing the number of calls to the heuristic function. However, once cases were learned, they were not modified according to their utility on solving planning problems. We present in this work a scheme for learning case quality based on its utility during a validation phase. The qualities obtained determine the way in which these cases are preferred in the retrieval and replay processes. Then, the paper shows some experimental results for several benchmarks taken from the International Planning Competition (IPC). These results show the planning performance improvement when case utilities are used.
---
paper_title: Lazy Incremental Learning of Control Knowledge for Efficiently Obtaining Quality Plans

paper_content:

General-purpose generative planners use domain-independent search heuristics to generate solutions for problems in a variety of domains. However, in some situations these heuristics force the planner to perform inefficiently or obtain solutions of poor quality. Learning from experience can help to identify the particular situations for which the domain-independent heuristics need to be overridden. Most of the past learning approaches are fully deductive and eagerly acquire correct control knowledge from a necessarily complete domain theory and a few examples to focus their scope. These learning strategies are hard to generalize in the case of nonlinear planning, where it is difficult to capture correct explanations of the interactions among goals, multiple planning operator choices, and situational data. In this article, we present a lazy learning method that combines a deductive and an inductive strategy to efficiently learn control knowledge incrementally with experience. We present hamlet, a system we developed that learns control knowledge to improve both search efficiency and the quality of the solutions generated by a nonlinear planner, namely prodigy4.0. We have identified three lazy aspects of our approach from which we believe hamlet greatly benefits: lazy explanation of successes, incremental refinement of acquired knowledge, and lazy learning to override only the default behavior of the problem solver. We show empirical results that support the effectiveness of this overall lazy learning approach, in terms of improving the efficiency of the problem solver and the quality of the solutions produced.
---
paper_title: Learning Action Models with Quantified Conditional Effects for Software Requirement Specification

paper_content:

Software requirement specification (SRS) is an important step in software engineering. Extracting requirement specification from an application field is a difficult task. In this paper, we consider software requirement as a problem to be solved by intelligent planning. To do this, one of the difficult things is how to represent the domain, since the software requirement has a feature of changeability. Thus, we divide the work into two tasks: the first one is to describe an incomplete domain of software requirement using PDDL(Planning Domains Definition Language) [7]; the second one is to complete the domain by learning from plan samples which is extracted from business processes. We modify the tool of [9] to learn action models with quantified conditional effects, which is the second task. In this way, people only need to do the first task and extract plan samples, which means the efforts of human beings are saved. At the end of the paper, we give our experiment result to show the efficiency of our method.
---
paper_title: Acquiring domain knowledge for planning by experimentation

paper_content:

In order for autonomous systems to interact with their environment in an intelligent way, they must be given the ability to adapt and learn incrementally and deliberately. It is virtually impossible to devise and hand code all potentially relevant domain knowledge for complex dynamic tasks. This thesis describes a framework to acquire domain knowledge for planning by failure-driven experimentation with the environment. The initial domain knowledge in the system is an approximate model for planning in the environment, defining the system's expectations. The framework exploits the characteristics of planning domains in order to search the space of plausible hypotheses without the need for additional background knowledge to build causal explanations for expectation failures. Plans are executed while the external environment is monitored, and differences between the internal state and external observations are detected by various methods each correlated with a typical cause for the expectation failure. The methods also construct a set of concrete hypotheses to repair the knowledge deficit. After being heuristically filtered, each hypothesis is tested in turn with an experiment. After the experiment is designed, a plan is constructed to achieve the situation required to carry out the experiment. The experiment plan must meet constraints such as minimizing plan length and negative interference with the main goals. The thesis describes a set of domain-independent constraints for experiments and their incorporation in the planning search space. After the execution of the plan and the experiment, observations are collected to conclude if the experiment was successful or not. Upon success, the hypothesis is confirmed and the domain knowledge is adjusted. Upon failure, the experimentation process is iterated on the remaining hypotheses until success or until no more hypotheses are left to be considered. This framework has shown to be an effective way to address incomplete planning knowledge and is demonstrated in a system called EXPO, implemented on the scPRODIGY planning architecture. The effectiveness and efficiency of EXPO's methods is empirically demonstrated in several domains, including a large-scale process planning task, where the planner can recover from situations missing up to 50% of domain knowledge through repeated experimentation.
---
paper_title: Top-Down Induction of First-Order Logical Decision Trees

paper_content:

Although topddown induction of decision trees is a very popular induction method, up till now it has mainly been used for propositional learnings relational decision tree learners are scarce. This dissertation discusses the application domain of decision tree learning and extends it towards the first order logic context of Inductive Logic Programming.
---
paper_title: Learning approximate preconditions for methods in hierarchical plans

paper_content:

A significant challenge in developing planning systems for practical applications is the difficulty of acquiring the domain knowledge needed by such systems. One method for acquiring this knowledge is to learn it from plan traces, but this method typically requires a huge number of plan traces to converge. In this paper, we show that the problem with slow convergence can be circumvented by having the learner generate solution plans even before the planning domain is completely learned. Our empirical results show that these improvements reduce the size of the training set that is needed to find correct answers to a large percentage of planning problems in the test set.
---
paper_title: Hybrid Learning of Search Control for Partial-order planning

paper_content:

This paper presents results on applying a version of the Dolphin search-control learning system to speed up a partial-order planner. Dolphin integrates explanation-based and inductive learning techniques to acquire e ective clause-selection rules for Prolog programs. A version of the UCPOP partial-order planning algorithm has been implemented as a Prolog program and Dolphin used to automatically learn domain-speci c search control rules that help eliminate backtracking. The resulting system is shown to produce signi cant speedup in several planning domains.
---
paper_title: The FF Planning System: Fast Plan Generation Through Heuristic Search

paper_content:

We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP's heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.
---
paper_title: Learning Action Models for Reactive Autonomous Agents

paper_content:

To be maximally effective, autonomous agents such as robots must be able both to react appropriately in dynamic environments and to plan new courses of action in novel situations. Reliable planning requires accurate models of the effects of actions--models which are often more appropriately learned through experience than design. This thesis describes TRAIL (Teleo-Reactive Agent with Inductive Learning), an integrated agent architecture which learns models of actions based on experiences in the environment. These action models are then used to create plans that combine both goal-directed and reactive behaviors. ::: Previous work on action-model learning has focused on domains that contain only deterministic, atomic action models that explicitly describe all changes that can occur in the environment. The thesis extends this previous work to cover domains that contain durative actions, continuous variables, nondeterministic action effects, and actions taken by other agents. Results have been demonstrated in several robot simulation environments and the Silicon Graphics, Inc. flight simulator. ::: The main emphasis in this thesis is on the action-model learning process within TRAIL. The content begins the learning process by recording experiences in its environment either by observing a trainer or by executing a plan. Second, the agent identifies instances of action success or failure during these experiences using a new analysis demonstrating nine possible causes of action failure. Finally, a variant of the Inductive Logic Programming algorithm DINUS is used to induce action models based on the action instances. As the action models are learned, they can be used for constructing plans whose execution contributes to additional learning experiences. Diminishing reliance on the teacher signals successful convergence of the learning process.
---
paper_title: Derivational Analogy in PRODIGY: Automating Case Acquisition, Storage, and Utilization

paper_content:

Expertise consists of rapid selection and application of compiled experience. Robust reasoning, however, requires adaptation to new contingencies and intelligent modification of past experience. And novel or creative reasoning, by its real nature, necessitates general problem-solving abilities unconstrained by past behavior. This article presents a comprehensive computational model of analogical (case-based) reasoning that transitions smoothly between case replay, case adaptation, and general problem solving, exploiting and modifying past experience when available and resorting to general problem-solving methods when required. Learning occurs by accumulation of new cases, especially in situations that required extensive problem solving, and by tuning the indexing structure of the memory model to retrieve progressively more appropriate cases. The derivational replay mechanism is discussed in some detail, and extensive results of the first full implementation are presented. These results show up to a large performance improvement in a simple transportation domain for structurally similar problems, and smaller improvements when less strict similarity metrics are used for problems that share partial structure in a process-job planning domain and in an extended version of the strips robot domain.
---
paper_title: U.: HTN-MAKER: Learning HTNs with minimal additional knowledge engineering required

paper_content:

We describe HTN-MAKER, an algorithm for learning hierarchical planning knowledge in the form of decomposition methods for Hierarchical Task Networks (HTNs). HTN-MAKER takes as input the initial states from a set of classical planning problems in a planning domain and solutions to those problems, as well as a set of semantically-annotated tasks to be accomplished. The algorithm analyzes this semantic information in order to determine which portions of the input plans accomplish a particular task and constructs HTN methods based on those analyses. ::: ::: Our theoretical results show that HTN-MAKER is sound and complete. We also present a formalism for a class of planning problems that are more expressive than classical planning. These planning problems can be represented as HTN planning problems. We show that the methods learned by HTN-MAKER enable an HTN planner to solve those problems. Our experiments confirm the theoretical results and demonstrate convergence in three well-known planning domains toward a set of HTN methods that can be used to solve nearly any problem expressible as a classical planning problem in that domain, relative to a set of goals.
---
paper_title: Learning to do htn planning

paper_content:

We describe HDL, an algorithm that learns HTN domain descriptions by examining plan traces produced by an expert problem-solver. Prior work on learning HTN methods requires that all the methods' information except for their preconditions be given in advance so that the learner can learn the preconditions. In contrast, HDL has no prior information about the methods. In our experiments, in most cases HDL converged fully with no more than about 200 plan traces. Furthermore, even when HDL was given only half the plan traces it required to fully converge, it usually was able to produce HTN methods that were sufficient to solve more than 3/4 of the planning problems in the test set.
---
paper_title: Learning Planning Operators by Observation and Practice

paper_content:

The work described in this paper addresses learning planning operators by observing expert agents and subsequent knowledge refinement in a learning-by-doing paradigm. The observations of the expert agent consist of: 1) the sequence of actions being executed, 2) the state in which each action is executed, and 3) the state resulting from the execution of each action. Planning operators are learned from these observation sequences in an incremental fashion utilizing a conservative specific-to-general inductive generalization process. In order to refine the new operators to make them correct and complete, the system uses the new operators to solve practice problems, analyzing and learning from the execution traces of the resulting solutions or execution failures. We describe techniques for planning and plan repair with incorrect and incomplete domain knowledge, and for operator refinement through a process which integrates planning, execution, and plan repair. Our learning method is implemented on top of the PRODIGY architecture(Carbonell, Knoblock, & Minton 1990; Carbonell et al. 1992) and is demonstrated in the extended-strips domain(Minton 1988) and a subset the process planning domain(Gil 1991).
---
paper_title: Using kernel perceptrons to learn action effects for planning

paper_content:

We investigate the problem of learning action effects in STRIPS and ADL planning domains. Our approach is based on a kernel perceptron learning model, where action and state information is encoded in a compact vector representation as input to the learning mechanism, and resulting state changes are produced as output. Empirical results of our approach indicate efficient training and prediction times, with low average error rates (< 3%) when tested on STRIPS and ADL versions of an object manipulation scenario. This work is part of a project to integrate machine learning techniques with a planning system, as part of a larger cognitive architecture linking a high- level reasoning component with a low-level robot/vision system.
---
paper_title: Combining FOIL and EBG to Speed-up Logic Programs

paper_content:

This paper presents an algorithm that combines traditional EBL techniques and recent developments in inductive logic programming to learn effective clause selection rules for Prolog programs. When these control rules are incorporated into the original program, significant speed-up may be achieved. The algorithm is shown to be an improvement over competing EBL approaches in several domains. Additionally, the algorithm is capable of automatically transforming some intractable algorithms into ones that run in polynomial time.
---
paper_title: Learning action durations from executions

paper_content:

Accurate action models are essential for efficiently solving automated planning tasks. An accurate action model allow the planner to precisely foresee the consequences of executing actions in a given environment and therefore tofind robust and good quality plans. But when addressing planning tasks in the real world, even hand-coding a simple STRIPS action model is complex, thus defining action models capturing further features, like the execution duration or costs, becomes more difficult. Moreover, if these features can be captured at a given instant they may vary over time. In this paper we automatically model the duration of action execution as relational regression trees learned from observing plan executions. And we show how planners find better plans after incorporating these models to their domain definition.
---
paper_title: Learning search control rules for planning: an inductive approach

paper_content:

The computational complexity of planning has motivated significant efforts in machine learning. However, much of this work has concentrated on explanation-based learning techniques. An alternative approach is to use inductive learning. An inductive approach does not require a complete and tractable domain theory to be encoded and has the potential to create more effective rules by learning from more than one example at a time. In this paper, we describe an inductive system for learning search control rules and compare it with an existing explanation-based learning system.
---
paper_title: Learning relational decision trees for guiding heuristic planning

paper_content:

The current evaluation functions for heuristic planning are expensive to compute. In numerous domains these functions give good guidance on the solution, so it worths the computation effort. On the contrary, where this is not true, heuristics planners compute loads of useless node evaluations that make them scale-up poorly. In this paper we present a novel approach for boosting the scalability of heuristic planners based on automatically learning domain-specific search control knowledge in the form of relational decision trees. Particularly, we define the learning of planning search control as a standard classification process. Then, we use an off-the-shelf relational classifier to build domain-specific relational decision trees that capture the preferred action in the different planning contexts of a planning domain. These contexts are defined by the set of helpful actions extracted from the relaxed planning graph of a given state, the goals remaining to be achieved, and the static predicates of the planning task. Additionally, we show two methods for guiding the search of a heuristic planner with relational decision trees. The first one consists of using the resulting decision trees as an action policy. The second one consists of ordering the node evaluation of the Enforced Hill Climbing algorithm with the learned decision trees. Experiments over a variety of domains from the IPC test-benchmarks reveal that in both cases the use of the learned decision trees increase the number of problems solved together with a reduction of the time spent.
---
paper_title: Learning Symbolic Models of Stochastic Domains

paper_content:

In this article, we work towards the goal of developing agents that can learn to act in complex worlds. We develop a probabilistic, relational planning rule representation that compactly models noisy, nondeterministic action effects, and show how such rules can be effectively learned. Through experiments in simple planning domains and a 3D simulated blocks world with realistic physics, we demonstrate that this learning algorithm allows agents to effectively model world dynamics.
---
paper_title: Kernel functions for case-based planning

paper_content:

Case-based planning can take advantage of former problem-solving experiences by storing in a plan library previously generated plans that can be reused to solve similar planning problems in the future. Although comparative worst-case complexity analyses of plan generation and reuse techniques reveal that it is not possible to achieve provable efficiency gain of reuse over generation, we show that the case-based planning approach can be an effective alternative to plan generation when similar reuse candidates can be chosen. In this paper we describe an innovative case-based planning system, called OAKplan, which can efficiently retrieve planning cases from plan libraries containing more than ten thousand cases, choose heuristically a suitable candidate and adapt it to provide a good quality solution plan which is similar to the one retrieved from the case library. Given a planning problem we encode it as a compact graph structure, that we call Planning Encoding Graph, which gives us a detailed description of the topology of the planning problem. By using this graph representation, we examine an approximate retrieval procedure based on kernel functions that effectively match planning instances, achieving extremely good performance in standard benchmark domains. The experimental results point out the effect of the case base size and the importance of accurate matching functions for global system performance. Overall, we show that OAKplan is competitive with state-of-the-art plan generation systems in terms of number of problems solved, CPU time, plan difference values and plan quality when cases similar to the current planning problem are available in the plan library.
---
paper_title: Discriminative Learning of Beam-Search Heuristics for Planning

paper_content:

We consider the problem of learning heuristics for controlling forward state-space beam search in AI planning domains. We draw on a recent framework for "structured output classification" (e.g. syntactic parsing) known as learning as search optimization (LaSO). The LaSO approach uses discriminative learning to optimize heuristic functions for search-based computation of structured outputs and has shown promising results in a number of domains. However, the search problems that arise in AI planning tend to be qualitatively very different from those considered in structured classification, which raises a number of potential difficulties in directly applying LaSO to planning. In this paper, we discuss these issues and describe a LaSO-based approach for discriminative learning of beam-search heuristics in AI planning domains. We give convergence results for this approach and present experiments in several benchmark domains. The results show that the discriminatively trained heuristic can outperform the one used by the planner FF and another recent non-discriminative learning approach.
---
paper_title: PARIS: Flexible Plan Adaptation by Abstraction and Refinement

paper_content:

Paris (Plan Abstraction and Refinement in an Integrated System) [4, 2] is a domain independent case-based planning system which allows the flexible reuse of planning cases by abstraction and refinement. This approach is mainly inspired by the observation that reuse of plans must not be restricted to a single description level. In domains with a high variation in the problems, the reuse of past solutions must be achieved at various levels of abstraction.
---
paper_title: The first probabilistic track of the international planning competition

paper_content:

The 2004 International Planning Competition, IPC-4, included a probabilistic planning track for the first time. We describe the new domain specification language we created for the track, our evaluation methodology, the competition domains we developed, and the results of the participating teams.
---
paper_title: PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains

paper_content:

In recent years research in the planning community has moved increasingly toward s application of planners to realistic problems involving both time and many typ es of resources. For example, interest in planning demonstrated by the space res earch community has inspired work in observation scheduling, planetary rover ex ploration and spacecraft control domains. Other temporal and resource-intensive domains including logistics planning, plant control and manufacturing have also helped to focus the community on the modelling and reasoning issues that must be confronted to make planning technology meet the challenges of application. The International Planning Competitions have acted as an important motivating fo rce behind the progress that has been made in planning since 1998. The third com petition (held in 2002) set the planning community the challenge of handling tim e and numeric resources. This necessitated the development of a modelling langua ge capable of expressing temporal and numeric properties of planning domains. In this paper we describe the language, PDDL2.1, that was used in the competition. We describe the syntax of the language, its formal semantics and the validation of concurrent plans. We observe that PDDL2.1 has considerable modelling power --- exceeding the capabilities of current planning technology --- and presents a number of important challenges to the research community.
---
paper_title: Parameter Estimation in Stochastic Logic Programs

paper_content:

Stochastic logic programs (SLPs) are logic programs with parameterised clauses which define a log-linear distribution over refutations of goals. The log-linear distribution provides, by marginalisation, a distribution over variable bindings, allowing SLPs to compactly represent quite complex distributions.We analyse the fundamental statistical properties of SLPs addressing issues concerning infinite derivations, 'unnormalised’ SLPs and impure SLPs. After detailing existing approaches to parameter estimation for log-linear models and their application to SLPs, we present a new algorithm called failure-adjusted maximisation (FAM). FAM is an instance of the EM algorithm that applies specifically to normalised SLPs and provides a closed-form for computing parameter updates within an iterative maximisation approach. We empirically show that FAM works on some small examples and discuss methods for applying it to bigger problems.
---
paper_title: Relational Bayesian Networks

paper_content:

A new method is developed to represent probabilistic relations on multiple random events. Where previously knowledge bases containing probabilistic rules were used for this purpose, here a probability distribution over the relations is directly represented by a Bayesian network. By using a powerful way of specifying conditional probability distributions in these networks, the resulting formalism is more expressive than the previous ones. Particularly, it provides for constraints on equalities of events, and it allows to define complex, nested combination functions.
---
paper_title: Learning partial-order macros from solutions

paper_content:

Despite recent progress in AI planning, many problems remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present an automated method that learns relevant information from previous experience in a domain and uses it to solve new problem instances. Our approach produces a small set of useful macro-operators as a result of a training process. For each training problem, a structure called a solution graph is built based on the problem solution. Macro-operators with partial ordering of moves are extracted from the solution graph. A filtering and ranking procedure selects the most useful macro-operators, which will be used in future searches. We introduce a heuristic technique that uses only the most promising instantiations of a selected macro for node expansion. Our results indicate an impressive reduction of the search effort in complex domains where structure information can be inferred.
---
paper_title: Integrating Guidance into Relational Reinforcement Learning

paper_content:

Reinforcement learning, and Q-learning in particular, encounter two major problems when dealing with large state spaces. First, learning the Q-function in tabular form may be infeasible because of the excessive amount of memory needed to store the table, and because the Q-function only converges after each state has been visited multiple times. Second, rewards in the state space may be so sparse that with random exploration they will only be discovered extremely slowly. The first problem is often solved by learning a generalization of the encountered examples (e.g., using a neural net or decision tree). Relational reinforcement learning (RRL) is such an approachs it makes Q-learning feasible in structural domains by incorporating a relational learner into Q-learning. The problem of sparse rewards has not been addressed for RRL. This paper presents a solution based on the use of “reasonable policies” to provide guidance. Different types of policies and different strategies to supply guidance through these policies are discussed and evaluated experimentally in several relational domains to show the merits of the approach.
---
paper_title: Using temporal logics to express search control knowledge for planning

paper_content:

Over the years increasingly sophisticated planning algorithms have been developed. These have made for more efficient planners, but unfortunately these planners still suffer from combinatorial complexity even in simple domains. Theoretical results demonstrate that planning is in the worst case intractable. Nevertheless, planning in particular domains can often be made tractable by utilizing additional domain structure. In fact, it has long been acknowledged that domain independent planners need domain dependent information to help them plan effectively. In this work we present an approach for representing and utilizing domain specific control knowledge. In particular, we show how domain dependent search control knowledge can be represented in a temporal logic, and then utilized to effectively control a forward-chaining planner. There are a number of advantages to our approach, including a declarative semantics for the search control knowledge; a high degree of modularity (new search control knowledge can be added without affecting previous control knowledge); and an independence of this knowledge from the details of the planning algorithm. We have implemented our ideas in the TLPLAN system, and have been able to demonstrate its remarkable effectiveness in a wide range of planning domains.
---
paper_title: Online Learning and Exploiting Relational Models in Reinforcement Learning

paper_content:

In recent years, there has been a growing interest in using rich representations such as relational languages for reinforcement learning. However, while expressive languages have many advantages in terms of generalization and reasoning, extending existing approaches to such a relational setting is a non-trivial problem. In this paper, we present a first step towards the online learning and exploitation of relational models. We propose a representation for the transition and reward function that can be learned online and present a method that exploits thesemodels by augmenting Relational Reinforcement Learning algorithms with planning techniques. The benefits and robustness of our approach are evaluated experimentally.
---
paper_title: fermi: A flexible expert reasoner with multi-domain inferencing

paper_content:

Expert reasoning combines voluminous domain-specific knowledge with more general factual and strategic knowledge. Whereas expert system builders have recognized the need for specificity and problem-solving researchers the need for generality, few attempts have been made to develop expert reasoning engines combining different kinds of knowledge at different levels of generality. This paper reports on the FERMI project, a computer-implemented expert reasoner in the natural sciences that encodes factual and strategic knowledge in separate semantic hierarchies. The principled decomposition of knowledge according to type and level of specificity yields both power and cross-doman generality, as demonstrated in FERMI's ability to apply the same principles of invariance and decomposition to solve problems in fluid statics, DC-circuits, and centroid location. Hierarchical knowledge representation and problem-solving principles are discussed, and illustrative problem-solving traces are presented.
---
paper_title: A theoretical analysis of Model-Based Interval Estimation

paper_content:

Several algorithms for learning near-optimal policies in Markov Decision Processes have been analyzed and proven efficient. Empirical results have suggested that Model-based Interval Estimation (MBIE) learns efficiently in practice, effectively balancing exploration and exploitation. This paper presents the first theoretical analysis of MBIE, proving its efficiency even under worst-case conditions. The paper also introduces a new performance metric, average loss, and relates it to its less "online" cousins from the literature.
---
paper_title: Learning generalized plans using abstract counting

paper_content:

Given the complexity of planning, it is often beneficial to create plans that work for a wide class of problems. This facilitates reuse of existing plans for different instances drawn from the same problem or from an infinite family of similar problems. We define a class of such planning problems called generalized planning problems and present a novel approach for transforming classical plans into generalized plans. These algorithm-like plans include loops and work for problem instances having varying numbers of objects that must be manipulated to reach the goal. Our approach takes as input a classical plan for a certain problem instance. It outputs a generalized plan along with a classification of the problem instances where it is guaranteed to work. We illustrate the utility of our approach through results of a working implementation on various practical examples.
---
paper_title: Learning relational options for inductive transfer in relational reinforcement learning

paper_content:

In reinforcement learning problems, an agent has the task of learning a good or optimal strategy from interaction with his environment. At the start of the learning task, the agent usually has very little information. Therefore, when faced with complex problems that have a large state space, learning a good strategy might be infeasible or too slow to work in practice. One way to overcome this problem, is the use of guidance to supply the agent with traces of "reasonable policies". However, in a lot of cases it will be hard for the user to supply such a policy. In this paper, we will investigate the use of transfer learning in Relational Reinforcement Learning. The goal of transfer learning is to accelerate learning on a target task after training on a different, but related, source task. More specifically, we introduce an extension of the options framework to the relational setting and show how one can learn skills that can be transferred across similar, but different domains. We present experiments showing the possible benefits of using relational options for transfer learning.
---
paper_title: Exploiting Competitive Planner Performance

paper_content:

To date, no one planner has demonstrated clearly superior performance. Although researchers have hypothesized that this should be the case, no one has performed a large study to test its limits. In this research, we tested performance of a set of planners to determine which is best on what types of problems. The study included six planners and over 200 problems. We found that performance, as measured by number of problems solved and computation time, varied with no one planner solving all the problems or being consistently fastest. Analysis of the data also showed that most planners either fail or succeed quickly and that performance depends at least in part on some easily observable problem/domain features. Based on these results, we implemented a meta-planner that interleaves execution of six planners on a problem until one of them solves it. The control strategy for ordering the planners and allocating time is derived from the performance study data. We found that our meta-planner is able to solve more problems than any single planner, but at the expense of computation time.
---
paper_title: An automatically configurable portfolio-based planner with macroactions: PbP

paper_content:

While several powerful domain-independent planners have recently been developed, no one of these clearly outperforms all the others in every known benchmark domain. We present PbP, a multi-planner which automatically configures a portfolio of planners by (i) computing some sets of macro-actions for every planner in the portfolio, (ii) selecting a promising combination of planners in the portfolio and relative useful macro-actions, and (iii) defining some running time slots for their round-robin scheduling during planning. The configuration relies on some knowledge about the performance of the planners in the portfolio and relative macro-actions which is automatically generated from a training problem set. PbP entered the learning track of IPC-2008 and was the overall winner of this competition track. An experimental study confirms the effectiveness of PbP, and shows that the learned configuration knowledge is useful for PbP.
---
paper_title: Acquiring Recursive and Iterative Concepts with Explanation-Based Learning

paper_content:

In explanation-based learning, a specific problem's solution is generalized into a form that can be later used to solve conceptually similar problems. Most research in explanation-based learning involves relaxing constraints on the variables in the explanation of a specific example, rather than generalizing the graphical structure of the explanation itself. However, this precludes the acquisition of concepts where an iterative or recursive process is implicitly represented in the explanation by a fixed number of applications. This paper presents an algorithm that generalizes explanation structures and reports empirical results that demonstrate the value of acquiring recursive and iterative concepts. The BAGGER2 algorithm learns recursive and iterative concepts, integrates results from multiple examples, and extracts useful subconcepts during generalization. On problems where learning a recursive rule is not appropriate, the system produces the same result as standard explanation-based methods. Applying the learned recursive rules only requires a minor extension to a PROLOG-like problem solver, namely, the ability to explicitly call a specific rule. Empirical studies demonstrate that generalizing the structure of explanations helps avoid the recently reported negative effects of learning.
---
paper_title: Nonlinear Planning with Parallel Resource Allocation

paper_content:

Most nonlinear problem solvers use a leastcommitment search strategy, reasoning about partially ordered plans. Although partial orders are useful for exploiting parallelism in execution, leastcommitment is NP-hard for complex domain descriptions with conditional effects. Instead, a casual-commitment strategy is developed, as a natural framework to reason and learn about control decisions in planning. This paper describes how NOLIMIT reasons about totally ordered plans using a casual-commitment strategy, how it generates a partially ordered solution from a totally ordered one by analyzing the dependencies among the plan steps, and finally how resources are allocated by exploiting the parallelism embedded in the partial order. We illustrate our claims with the implemented algorithms and several examples. This work has been done in the context of the PRODIGY architecture that incorporates NOLIMIT, a nonlinear problem solver.
---
paper_title: Model-lite Planning for the Web Age Masses: The Challenges of Planning with Incomplete and Evolving Domain Models

paper_content:

The automated planning community has traditionally focused on the efficient synthesis of plans given a complete domain theory. In the past several years, this line of work met with significant successes, and the future course of the community seems to be set on efficient planning with even richer models. While this line of research has its applications, there are also many domains and scenarios where the first bottleneck is getting the domain model at any level of completeness. In these scenarios, the modeling burden automatically renders the planning technology unusable. To counter this, I will motivate model-lite planning technology aimed at reducing the domain-modeling burden (possibly at the expense of reduced functionality), and outline the research challenges that need to be addressed to realize it.
---
paper_title: Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators

paper_content:

Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present and compare two automated methods that learn relevant information from previous experience in a domain and use it to solve new problem instances. Our methods share a common four-step strategy. First, a domain is analyzed and structural information is extracted, then macro-operators are generated based on the previously discovered structure. A filtering and ranking procedure selects the most useful macro-operators. Finally, the selected macros are used to speed up future searches. ::: ::: We have successfully used such an approach in the fourth international planning competition IPC-4. Our system, Macro-FF, extends Hoffmann's state-of-the-art planner FF 2.3 with support for two kinds of macro-operators, and with engineering enhancements. We demonstrate the effectiveness of our ideas on benchmarks from international planning competitions. Our results indicate a large reduction in search effort in those complex domains where structural information can be inferred.
---
paper_title: Macro-operators: a weak method for learning

paper_content:

Abstract This article explores the idea of learning efficient strategies for solving problems by searching for macro-operators . A macro-operator, or macro for short, is simply a sequence of operators chosen from the primitive operators of a problem. The technique is particularly useful for problems with non-serializable subgoals, such as Rubik's Cube, for which other weak methods fail. Both a problem-solving program and a learning program are described in detail. The performance of these programs is analyzed in terms of the number of macros required to solve all problem instances, the length of the resulting solutions (expressed as the number of primitive moves), and the amount of time necessary to learn the macros. In addition, a theory of why the method works, and a characterization of the range of problems for which it is useful are presented. The theory introduces a new type of problem structure called operator decomposability . Finally, it is concluded that the macro technique is a new kind of weak method, a method for learning as opposed to problem solving.
---
paper_title: Using cases utility for heuristic planning improvement

paper_content:

Current efficient planners employ an informed search guided by a heuristic function that is quite expensive to compute. Thus, ordering nodes in the search tree becomes a key issue, in order to select efficiently nodes to evaluate from the successors of the current search node. In a previous work, we successfully applied a CBR approach to order nodes for evaluation, thus reducing the number of calls to the heuristic function. However, once cases were learned, they were not modified according to their utility on solving planning problems. We present in this work a scheme for learning case quality based on its utility during a validation phase. The qualities obtained determine the way in which these cases are preferred in the retrieval and replay processes. Then, the paper shows some experimental results for several benchmarks taken from the International Planning Competition (IPC). These results show the planning performance improvement when case utilities are used.
---
paper_title: Lazy Incremental Learning of Control Knowledge for Efficiently Obtaining Quality Plans

paper_content:

General-purpose generative planners use domain-independent search heuristics to generate solutions for problems in a variety of domains. However, in some situations these heuristics force the planner to perform inefficiently or obtain solutions of poor quality. Learning from experience can help to identify the particular situations for which the domain-independent heuristics need to be overridden. Most of the past learning approaches are fully deductive and eagerly acquire correct control knowledge from a necessarily complete domain theory and a few examples to focus their scope. These learning strategies are hard to generalize in the case of nonlinear planning, where it is difficult to capture correct explanations of the interactions among goals, multiple planning operator choices, and situational data. In this article, we present a lazy learning method that combines a deductive and an inductive strategy to efficiently learn control knowledge incrementally with experience. We present hamlet, a system we developed that learns control knowledge to improve both search efficiency and the quality of the solutions generated by a nonlinear planner, namely prodigy4.0. We have identified three lazy aspects of our approach from which we believe hamlet greatly benefits: lazy explanation of successes, incremental refinement of acquired knowledge, and lazy learning to override only the default behavior of the problem solver. We show empirical results that support the effectiveness of this overall lazy learning approach, in terms of improving the efficiency of the problem solver and the quality of the solutions produced.
---
paper_title: Learning macro-actions for arbitrary planner and domains

paper_content:

Many complex domains and even larger problems in simple domains remain challenging in spite of the recent progress in planning. Besides developing and improving planning technologies, re-engineering a domain by utilising acquired knowledge opens up a potential avenue for further research. Moreover, macro-actions, when added to the domain as additional actions, provide a promising means by which to convey such knowledge. A macro-action, or macro in short, is a group of actions selected for application as a single choice. Most existing work on macros exploits properties explicitly specific to the planners or the domains. However, such properties are not likely to be common with arbitrary planners or domains. Therefore, a macro learning method that does not exploit any structural knowledge about planners or domains explicitly is of immense interest. This paper presents an offline macro learning method that works with arbitrarily chosen planners and domains. Given a planner, a domain, and a number of example problems, the learning method generates macros from plans of some of the given problems under the guidance of a genetic algorithm. It represents macros like regular actions, evaluates them individually by solving the remaining given problems, and suggests individual macros that are to be added to the domain permanently. Genetic algorithms are automatic learning methods that can capture inherent features of a system using no explicit knowledge about it. Our method thus does not strive to discover or utilise any structural properties specific to a planner or a domain.
---
paper_title: Marvin: A Heuristic Search Planner with Online Macro-Action Learning

paper_content:

This paper describes Marvin, a planner that competed in the Fourth International Planning Competition (IPC 4). Marvin uses action-sequence-memoisation techniques to generate macro-actions, which are then used during search for a solution plan. We provide an overview of its architecture and search behaviour, detailing the algorithms used. We also empirically demonstrate the effectiveness of its features in various planning domains; in particular, the effects on performance due to the use of macro-actions, the novel features of its search behaviour, and the native support of ADL and Derived Predicates.
---
paper_title: Learning relational decision trees for guiding heuristic planning

paper_content:

The current evaluation functions for heuristic planning are expensive to compute. In numerous domains these functions give good guidance on the solution, so it worths the computation effort. On the contrary, where this is not true, heuristics planners compute loads of useless node evaluations that make them scale-up poorly. In this paper we present a novel approach for boosting the scalability of heuristic planners based on automatically learning domain-specific search control knowledge in the form of relational decision trees. Particularly, we define the learning of planning search control as a standard classification process. Then, we use an off-the-shelf relational classifier to build domain-specific relational decision trees that capture the preferred action in the different planning contexts of a planning domain. These contexts are defined by the set of helpful actions extracted from the relaxed planning graph of a given state, the goals remaining to be achieved, and the static predicates of the planning task. Additionally, we show two methods for guiding the search of a heuristic planner with relational decision trees. The first one consists of using the resulting decision trees as an action policy. The second one consists of ordering the node evaluation of the Enforced Hill Climbing algorithm with the learned decision trees. Experiments over a variety of domains from the IPC test-benchmarks reveal that in both cases the use of the learned decision trees increase the number of problems solved together with a reduction of the time spent.
---
paper_title: Discriminative Learning of Beam-Search Heuristics for Planning

paper_content:

We consider the problem of learning heuristics for controlling forward state-space beam search in AI planning domains. We draw on a recent framework for "structured output classification" (e.g. syntactic parsing) known as learning as search optimization (LaSO). The LaSO approach uses discriminative learning to optimize heuristic functions for search-based computation of structured outputs and has shown promising results in a number of domains. However, the search problems that arise in AI planning tend to be qualitatively very different from those considered in structured classification, which raises a number of potential difficulties in directly applying LaSO to planning. In this paper, we discuss these issues and describe a LaSO-based approach for discriminative learning of beam-search heuristics in AI planning domains. We give convergence results for this approach and present experiments in several benchmark domains. The results show that the discriminatively trained heuristic can outperform the one used by the planner FF and another recent non-discriminative learning approach.
---
paper_title: CaMeL: Learning method preconditions for HTN planning

paper_content:

A great challenge in using any planning system to solve real-world problems is the difficulty of acquiring the domain knowledge that the system will need. We present away to address part of this problem, in the context of Hierarchical Task Network (HTN) planning, by having the planning system incrementally learn conditions for HTN methods under expert supervision. We present a general formal framework for learning HTN methods, and a supervised learning algorithm, named CaMeL, based on this formalism. We present theoretical results about CaMeL's soundness, completeness, and convergence properties. We also report experimental results about its speed of convergence under different conditions. The experimental results suggest that CaMeL has the potential to be useful in real-world applications.
---
paper_title: U.: HTN-MAKER: Learning HTNs with minimal additional knowledge engineering required

paper_content:

We describe HTN-MAKER, an algorithm for learning hierarchical planning knowledge in the form of decomposition methods for Hierarchical Task Networks (HTNs). HTN-MAKER takes as input the initial states from a set of classical planning problems in a planning domain and solutions to those problems, as well as a set of semantically-annotated tasks to be accomplished. The algorithm analyzes this semantic information in order to determine which portions of the input plans accomplish a particular task and constructs HTN methods based on those analyses. ::: ::: Our theoretical results show that HTN-MAKER is sound and complete. We also present a formalism for a class of planning problems that are more expressive than classical planning. These planning problems can be represented as HTN planning problems. We show that the methods learned by HTN-MAKER enable an HTN planner to solve those problems. Our experiments confirm the theoretical results and demonstrate convergence in three well-known planning domains toward a set of HTN methods that can be used to solve nearly any problem expressible as a classical planning problem in that domain, relative to a set of goals.
---
paper_title: Learning to do htn planning

paper_content:

We describe HDL, an algorithm that learns HTN domain descriptions by examining plan traces produced by an expert problem-solver. Prior work on learning HTN methods requires that all the methods' information except for their preconditions be given in advance so that the learner can learn the preconditions. In contrast, HDL has no prior information about the methods. In our experiments, in most cases HDL converged fully with no more than about 200 plan traces. Furthermore, even when HDL was given only half the plan traces it required to fully converge, it usually was able to produce HTN methods that were sufficient to solve more than 3/4 of the planning problems in the test set.
---
paper_title: Fast Planning with Iterative Macros

paper_content:

Research on macro-operators has a long history in planning and other search applications. There has been a revival of interest in this topic, leading to systems that successfully combine macrooperators with current state-of-the-art planning approaches based on heuristic search. However, research is still necessary to make macros become a standard, widely-used enhancement of search algorithms. This article introduces sequences of macro-actions, called iterative macros. Iterative macros exhibit both the potential advantages (e.g., travel fast towards goal) and the potential limitations (e.g., utility problem) of classical macros, only on a much larger scale. A family of techniques are introduced to balance this trade-off in favor of faster planning. Experiments on a collection of planning benchmarks show that, when compared to low-level search and even to search with classical macro-operators, iterative macros can achieve an impressive speed-up in search.
---
paper_title: Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators

paper_content:

Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present and compare two automated methods that learn relevant information from previous experience in a domain and use it to solve new problem instances. Our methods share a common four-step strategy. First, a domain is analyzed and structural information is extracted, then macro-operators are generated based on the previously discovered structure. A filtering and ranking procedure selects the most useful macro-operators. Finally, the selected macros are used to speed up future searches. ::: ::: We have successfully used such an approach in the fourth international planning competition IPC-4. Our system, Macro-FF, extends Hoffmann's state-of-the-art planner FF 2.3 with support for two kinds of macro-operators, and with engineering enhancements. We demonstrate the effectiveness of our ideas on benchmarks from international planning competitions. Our results indicate a large reduction in search effort in those complex domains where structural information can be inferred.
---
paper_title: Exploiting N-gram Analysis to Predict Operator Sequences ∗

paper_content:

N-gram analysis provides a means of probabilistically predicting the next item in a sequence. Due originally to Shannon, it has proven an effective technique for word prediction in natural language processing and for gene sequence analysis. In this paper, we investigate the utility of n-gram analysis in predicting operator sequences in plans. Given a set of sample plans, we perform n-gram analysis to predict the likelihood of subsequent operators, relative to a partial plan. We identify several ways in which this information might be integrated into a planner. In this paper, we investigate one of these directions in further detail. Preliminary results demonstrate the promise of n-gram analysis as a tool for improving planning performance.
---
paper_title: Macro-operators: a weak method for learning

paper_content:

Abstract This article explores the idea of learning efficient strategies for solving problems by searching for macro-operators . A macro-operator, or macro for short, is simply a sequence of operators chosen from the primitive operators of a problem. The technique is particularly useful for problems with non-serializable subgoals, such as Rubik's Cube, for which other weak methods fail. Both a problem-solving program and a learning program are described in detail. The performance of these programs is analyzed in terms of the number of macros required to solve all problem instances, the length of the resulting solutions (expressed as the number of primitive moves), and the amount of time necessary to learn the macros. In addition, a theory of why the method works, and a characterization of the range of problems for which it is useful are presented. The theory introduces a new type of problem structure called operator decomposability . Finally, it is concluded that the macro technique is a new kind of weak method, a method for learning as opposed to problem solving.
---
paper_title: Combining Weak Learning Heuristics in General Problem Solvers

paper_content:

This paper is concerned with state space problem solvers that achieve generality by learning strong heuristics through experience in a particular domain. We specifically consider two ways of learning by analysing past solutions that can improve future problem solving: creating macros and the chunks. A method of learning search heuristics is specified which is related to 'chunking' but which complements the use of macros within a goal directed system. An example of the creation and combined use of macros and chunks, taken from an implemented system, is described.
---
paper_title: Learning macro-actions for arbitrary planner and domains

paper_content:

Many complex domains and even larger problems in simple domains remain challenging in spite of the recent progress in planning. Besides developing and improving planning technologies, re-engineering a domain by utilising acquired knowledge opens up a potential avenue for further research. Moreover, macro-actions, when added to the domain as additional actions, provide a promising means by which to convey such knowledge. A macro-action, or macro in short, is a group of actions selected for application as a single choice. Most existing work on macros exploits properties explicitly specific to the planners or the domains. However, such properties are not likely to be common with arbitrary planners or domains. Therefore, a macro learning method that does not exploit any structural knowledge about planners or domains explicitly is of immense interest. This paper presents an offline macro learning method that works with arbitrarily chosen planners and domains. Given a planner, a domain, and a number of example problems, the learning method generates macros from plans of some of the given problems under the guidance of a genetic algorithm. It represents macros like regular actions, evaluates them individually by solving the remaining given problems, and suggests individual macros that are to be added to the domain permanently. Genetic algorithms are automatic learning methods that can capture inherent features of a system using no explicit knowledge about it. Our method thus does not strive to discover or utilise any structural properties specific to a planner or a domain.
---
paper_title: Marvin: A Heuristic Search Planner with Online Macro-Action Learning

paper_content:

This paper describes Marvin, a planner that competed in the Fourth International Planning Competition (IPC 4). Marvin uses action-sequence-memoisation techniques to generate macro-actions, which are then used during search for a solution plan. We provide an overview of its architecture and search behaviour, detailing the algorithms used. We also empirically demonstrate the effectiveness of its features in various planning domains; in particular, the effects on performance due to the use of macro-actions, the novel features of its search behaviour, and the native support of ADL and Derived Predicates.
---
paper_title: Using temporal logics to express search control knowledge for planning

paper_content:

Over the years increasingly sophisticated planning algorithms have been developed. These have made for more efficient planners, but unfortunately these planners still suffer from combinatorial complexity even in simple domains. Theoretical results demonstrate that planning is in the worst case intractable. Nevertheless, planning in particular domains can often be made tractable by utilizing additional domain structure. In fact, it has long been acknowledged that domain independent planners need domain dependent information to help them plan effectively. In this work we present an approach for representing and utilizing domain specific control knowledge. In particular, we show how domain dependent search control knowledge can be represented in a temporal logic, and then utilized to effectively control a forward-chaining planner. There are a number of advantages to our approach, including a declarative semantics for the search control knowledge; a high degree of modularity (new search control knowledge can be added without affecting previous control knowledge); and an independence of this knowledge from the details of the planning algorithm. We have implemented our ideas in the TLPLAN system, and have been able to demonstrate its remarkable effectiveness in a wide range of planning domains.
---
paper_title: Learning Control Knowledge for Forward Search Planning

paper_content:

A number of today's state-of-the-art planners are based on forward state-space search. The impressive performance can be attributed to progress in computing domain independent heuristics that perform well across many domains. However, it is easy to find domains where such heuristics provide poor guidance, leading to planning failure. Motivated by such failures, the focus of this paper is to investigate mechanisms for learning domain-specific knowledge to better control forward search in a given domain. While there has been a large body of work on inductive learning of control knowledge for AI planning, there is a void of work aimed at forward-state-space search. One reason for this may be that it is challenging to specify a knowledge representation for compactly representing important concepts across a wide range of domains. One of the main contributions of this work is to introduce a novel feature space for representing such control knowledge. The key idea is to define features in terms of information computed via relaxed plan extraction, which has been a major source of success for non-learning planners. This gives a new way of leveraging relaxed planning techniques in the context of learning. Using this feature space, we describe three forms of control knowledge---reactive policies (decision list rules and measures of progress) and linear heuristics---and show how to learn them and incorporate them into forward state-space search. Our empirical results show that our approaches are able to surpass state-of-the-art non-learning planners across a wide range of planning competition domains.
---
paper_title: Learning relational decision trees for guiding heuristic planning

paper_content:

The current evaluation functions for heuristic planning are expensive to compute. In numerous domains these functions give good guidance on the solution, so it worths the computation effort. On the contrary, where this is not true, heuristics planners compute loads of useless node evaluations that make them scale-up poorly. In this paper we present a novel approach for boosting the scalability of heuristic planners based on automatically learning domain-specific search control knowledge in the form of relational decision trees. Particularly, we define the learning of planning search control as a standard classification process. Then, we use an off-the-shelf relational classifier to build domain-specific relational decision trees that capture the preferred action in the different planning contexts of a planning domain. These contexts are defined by the set of helpful actions extracted from the relaxed planning graph of a given state, the goals remaining to be achieved, and the static predicates of the planning task. Additionally, we show two methods for guiding the search of a heuristic planner with relational decision trees. The first one consists of using the resulting decision trees as an action policy. The second one consists of ordering the node evaluation of the Enforced Hill Climbing algorithm with the learned decision trees. Experiments over a variety of domains from the IPC test-benchmarks reveal that in both cases the use of the learned decision trees increase the number of problems solved together with a reduction of the time spent.
---
paper_title: Taxonomic syntax for first order inference

paper_content:

A new polynomial time decidable fragment of first order logic is identified, and a general method for using polynomial time inference procedures in knowledge representation systems is presented. The results shown in this paper indicate that a nonstandard “taxonomic” syntax is essential in constructing natural and powerful polynomial time inference procedures. The central role of taxonomic syntax in the polynomial time inference procedures provides technical support for the often-expressed intuition that knowledge is better represented in terms of taxonomic relationships than classical first order formulas. To use the procedures in a knowledge representation system, a “Socratic proof system” is defined, which is complete for first order inference and which can be used as a semi-automated interface to a first order knowledge base.
---
paper_title: On the Complexity of Domain-Independent Planning

paper_content:

In this paper, we examine how the complexity of domain-independent planning with STRIPS-style operators depends on the nature of the planning operators. We show how the time complexity varies depending on a wide variety of conditions: • whether or not delete lists are allowed; • whether or not negative preconditions are allowed; • whether or not the predicates are restricted to be propositions (i.e., 0-ary); • whether the planning operators are given as part of the input to the planning problem, or instead are fixed in advance.
---
paper_title: Control Strategies in HTN Planning: Theory Versus Practice

paper_content:

AI planning techniques are beginning to find use in a number of practical planning domains. However, the backward-chaining and partial-order-planning control strategies traditionally used in AI planning systems are not necessarily the best ones to use for practical planning problems. In this paper, we discuss some of the difficulties that can result from the use of backward chaining and partial-order planning, and we describe how these difficulties can be overcome by adapting Hierarchical Task-Network (HTN) planning to use a total-order control strategy that generates the steps of a plan in the same order that those steps will be executed. We also examine how introducing the total-order restriction into HTN planning affects its expressive power, and propose a way to relax the total-order restriction to increase its expressive power and range of applicability.
---
paper_title: SHOP2: An HTN Planning System

paper_content:

The SHOP2 planning system received one of the awards for distinguished performance in the 2002 International Planning Competition. This paper describes the features of SHOP2 which enabled it to excel in the competition, especially those aspects of SHOP2 that deal with temporal and metric planning domains.
---
paper_title: Approximate Planning in POMDPs with Macro-Actions

paper_content:

Recent research has demonstrated that useful POMDP solutions do not require consideration of the entire belief space. We extend this idea with the notion of temporal abstraction. We present and explore a new reinforcement learning algorithm over grid-points in belief space, which uses macro-actions and Monte Carlo updates of the Q-values. We apply the algorithm to a large scale robot navigation task and demonstrate that with temporal abstraction we can consider an even smaller part of the belief space, we can learn POMDP policies faster, and we can do information gathering more efficiently.
---
paper_title: Learning Hierarchical Task Networks for Nondeterministic Planning Domains

paper_content:

This paper describes how to learn Hierarchical Task Networks (HTNs) in nondeterministic planning domains, where actions may have multiple possible outcomes. We discuss several desired properties that guarantee that the resulting HTNs will correctly handle the nondeterminism in the domain. We developed a new learning algorithm, called HTN-MAKERND, that exploits these properties. We implemented HTN-MAKERND in the recently-proposed HTN-MAKER system, a goal-regression based HTN learning approach. In our theoretical study, we show that HTN-MAKERND soundly produces HTN planning knowledge in low-order polynomial times, despite the nondeterminism. In our experiments with two nondeterministic planning domains, ND-SHOP2, a well-known HTN planning algorithm for nondeterministic domains, significantly outperformed (in some cases, by about 3 orders of magnitude) the well-known planner MBP using the learned HTNs.
---
paper_title: Inductive Policy Selection for First-Order MDPs

paper_content:

We select policies for large Markov Decision Processes (MDPs) with compact first-order representations. We find policies that generalize well as the number of objects in the domain grows, potentially without bound. Existing dynamic-programming approaches based on flat, propositional, or first-order representations either are impractical here or do not naturally scale as the number of objects grows without bound. We implement and evaluate an alternative approach that induces first-order policies using training data constructed by solving small problem instances using PGraphplan (Blurn & Langford, 1999). Our policies are represented as ensembles of decision lists, using a taxonomic concept language. This approach extends the work of Martin and Geffner (2000) to stochastic domains, ensemble learning, and a wider variety of problems. Empirically, we find "good" policies for several stochastic first-order MDPs that are beyond the scope of previous approaches. We also discuss the application of this work to the relational reinforcement-learning problem.
---
paper_title: Exploiting First-Order Regression in Inductive Policy Selection

paper_content:

We consider the problem of computing optimal generalised policies for relational Markov decision processes. We describe an approach combining some of the benefits of purely inductive techniques with those of symbolic dynamic programming methods. The latter reason about the optimal value function using first-order decision-theoretic regression and formula rewriting, while the former, when provided with a suitable hypotheses language, are capable of generalising value functions or policies for small instances. Our idea is to use reasoning and in particular classical first-order regression to automatically generate a hypotheses language dedicated to the domain at hand, which is then used as input by an inductive solver. This approach avoids the more complex reasoning of symbolic dynamic programming while focusing the inductive solver's attention on concepts that are specifically relevant to the optimal value function for the domain considered.
---
paper_title: Reinforcement Learning: A Survey

paper_content:

This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning.
---
paper_title: Learning in Real-Time Search: A Unifying Framework

paper_content:

Real-time search methods are suited for tasks in which the agent is interacting with an initially unknown environment in real time. In such simultaneous planning and learning problems, the agent has to select its actions in a limited amount of time, while sensing only a local part of the environment centered at the agent's current location. Real-time heuristic search agents select actions using a limited lookahead search and evaluating the frontier states with a heuristic function. Over repeated experiences, they refine heuristic values of states to avoid infinite loops and to converge to better solutions. The wide spread of such settings in autonomous software and hardware agents has led to an explosion of real-time search algorithms over the last two decades. Not only is a potential user confronted with a hodgepodge of algorithms, but he also faces the choice of control parameters they use. In this paper we address both problems. The first contribution is an introduction of a simple three-parameter framework (named LRTS) which extracts the core ideas behind many existing algorithms. We then prove that LRTA*, E-LRTA* , SLA*, and γ-Trap algorithms are special cases of our framework. Thus, they are unified and extended with additional features. Second, we prove completeness and convergence of any algorithm covered by the LRTS framework. Third, we prove several upper-bounds relating the control parameters and solution quality. Finally, we analyze the influence of the three control parameters empirically in the realistic scalable domains of real-time navigation on initially unknown maps from a commercial role-playing game as well as routing in ad hoc sensor networks.
---
paper_title: Improving LRTA*(k)

paper_content:

We identify some weak points of the LRTA*(k) algorithm in the propagation of heuristic changes. To solve them, we present a new algorithm, LRTA*LS(k), that is based on the selection and updating of the interior states of a local space around the current state. It keeps the good theoretical properties of LRTA*(k), while improving substantially its performance. It is related with a lookahead depth greater than 1. We provide experimental evidence of the benefits of the new algorithm on real-time benchmarks with respect to existing approaches.
---
paper_title: Monte Carlo Matrix Inversion and Reinforcement Learning

paper_content:

We describe the relationship between certain reinforcement learning (RL) methods based on dynamic programming (DP) and a class of unorthodox Monte Carlo methods for solving systems of linear equations proposed in the 1950's. These methods recast the solution of the linear system as the expected value of a statistic suitably defined over sample paths of a Markov chain. The significance of our observations lies in arguments (Curtiss, 1954) that these Monte Carlo methods scale better with respect to state-space size than do standard, iterative techniques for solving systems of linear equations. This analysis also establishes convergence rate estimates. Because methods used in RL systems for approximating the evaluation function of a fixed control policy also approximate solutions to systems of linear equations, the connection to these Monte Carlo methods establishes that algorithms very similar to TD algorithms (Sutton, 1988) are asymptotically more efficient in a precise sense than other methods for evaluating policies. Further, all DP-based RL methods have some of the properties of these Monte Carlo algorithms, which suggests that although RL is often perceived to be slow, for sufficiently large problems, it may in fact be more efficient than other known classes of methods capable of producing the same results.
---
paper_title: Symbolic Dynamic Programming for First-order POMDPs

paper_content:

Partially-observable Markov decision processes (POMDPs) provide a powerful model for sequential decision-making problems with partially-observed state and are known to have (approximately) optimal dynamic programming solutions. Much work in recent years has focused on improving the efficiency of these dynamic programming algorithms by exploiting symmetries and factored or relational representations. In this work, we show that it is also possible to exploit the full expressive power of first-order quantification to achieve state, action, and observation abstraction in a dynamic programming solution to relationally specified POMDPs. Among the advantages of this approach are the ability to maintain compact value function representations, abstract over the space of potentially optimal actions, and automatically derive compact conditional policy trees that minimally partition relational observation spaces according to distinctions that have an impact on policy values. This is the first lifted relational POMDP solution that can optimally accommodate actions with a potentially infinite relational space of observation outcomes.
---
paper_title: Cross-domain transfer for reinforcement learning

paper_content:

A typical goal for transfer learning algorithms is to utilize knowledge gained in a source task to learn a target task faster. Recently introduced transfer methods in reinforcement learning settings have shown considerable promise, but they typically transfer between pairs of very similar tasks. This work introduces Rule Transfer, a transfer algorithm that first learns rules to summarize a source task policy and then leverages those rules to learn faster in a target task. This paper demonstrates that Rule Transfer can effectively speed up learning in Keepaway, a benchmark RL problem in the robot soccer domain, based on experience from source tasks in the gridworld domain. We empirically show, through the use of three distinct transfer metrics, that Rule Transfer is effective across these domains.
---
paper_title: Symbolic Dynamic Programming for First-Order MDPs

paper_content:

We present a dynamic programming approach for the solution of first-order Markov decisions processes. This technique uses an MDP whose dynamics is represented in a variant of the situation calculus allowing for stochastic actions. It produces a logical description of the optimal value function and policy by constructing a set of first-order formulae that minimally partition state space according to distinctions made by the value function and policy. This is achieved through the use of an operation known as decision-theoretic regression. In effect, our algorithm performs value iteration without explicit enumeration of either the state or action spaces of the MDP. This allows problems involving relational fluents and quantification to be solved without requiring explicit state space enumeration or conversion to propositional form.
---
paper_title: First Order Decision Diagrams for Relational MDPs

paper_content:

Markov decision processes capture sequential decision making under uncertainty, where an agent must choose actions so as to optimize long term reward. The paper studies efficient reasoning mechanisms for Relational Markov Decision Processes (RMDP) where world states have an internal relational structure that can be naturally described in terms of objects and relations among them. Two contributions are presented. First, the paper develops First Order Decision Diagrams (FODD), a new compact representation for functions over relational structures, together with a set of operators to combine FODDs, and novel reduction techniques to keep the representation small. Second, the paper shows how FODDs can be used to develop solutions for RMDPs, where reasoning is performed at the abstract level and the resulting optimal policy is independent of domain size (number of objects) or instantiation. In particular, a variant of the value iteration algorithm is developed by using special operations over FODDs, and the algorithm is shown to converge to the optimal policy.
---
paper_title: Transfer in variable-reward hierarchical reinforcement learning

paper_content:

Transfer learning seeks to leverage previously learned tasks to achieve faster learning in a new task. In this paper, we consider transfer learning in the context of related but distinct Reinforcement Learning (RL) problems. In particular, our RL problems are derived from Semi-Markov Decision Processes (SMDPs) that share the same transition dynamics but have different reward functions that are linear in a set of reward features. We formally define the transfer learning problem in the context of RL as learning an efficient algorithm to solve any SMDP drawn from a fixed distribution after experiencing a finite number of them. Furthermore, we introduce an online algorithm to solve this problem, Variable-Reward Reinforcement Learning (VRRL), that compactly stores the optimal value functions for several SMDPs, and uses them to optimally initialize the value function for a new SMDP. We generalize our method to a hierarchical RL setting where the different SMDPs share the same task hierarchy. Our experimental results in a simplified real-time strategy domain show that significant transfer learning occurs in both flat and hierarchical settings. Transfer is especially effective in the hierarchical setting where the overall value functions are decomposed into subtask value functions which are more widely amenable to transfer across different SMDPs.
---
paper_title: Learning action effects in partially observable domains

paper_content:

We investigate the problem of learning action effects in partially observable STRIPS planning domains. Our approach is based on a voted kernel perceptron learning model, where action and state information is encoded in a compact vector representation as input to the learning mechanism, and resulting state changes are produced as output. Our approach relies on deictic features that assume an attentional mechanism that reduces the size of the representation. We evaluate our approach on a number of partially observable planning domains, and show that it can quickly learn the dynamics of such domains, with low average error rates. We show that our approach handles noisy domains, conditional effects, and that it scales independently of the number of objects in a domain.
---
paper_title: Acquisition of object-centred domain models from planning examples

paper_content:

The problem of formulating knowledge bases containing action schema is a central concern in knowledge engineering for AI Planning. This paper describes LOCM, a system which carries out the automated induction of action schema from sets of example plans. Each plan is assumed to be a sound sequence of actions; each action in a plan is stated as a name and a list of objects that the action refers to. LOCM exploits the assumption that actions change the state of objects, and require objects to be in a certain state before they can be executed. The novelty of LOCM is that it can induce action schema without being provided with any information about predicates or initial, goal or intermediate state descriptions for the example action sequences. In this paper we describe the implemented LOCM algorithm, and analyse its performance by its application to the induction of domain models for several domains. To evaluate the algorithm, we used random action sequences from existing models of domains, as well as solutions to past IPC problems.
---
paper_title: Concise finite-domain representations for PDDL planning tasks

paper_content:

We introduce an efficient method for translating planning tasks specified in the standard PDDL formalism into a concise grounded representation that uses finite-domain state variables instead of the straight-forward propositional encoding. Translation is performed in four stages. Firstly, we transform the input task into an equivalent normal form expressed in a restricted fragment of PDDL. Secondly, we synthesize invariants of the planning task that identify groups of mutually exclusive propositions which can be represented by a single finite-domain variable. Thirdly, we perform an efficient relaxed reachability analysis using logic programming techniques to obtain a grounded representation of the input. Finally, we combine the results of the third and fourth stage to generate the final grounded finite-domain representation. The presented approach has originally been implemented as part of the Fast Downward planning system for the 4th International Planning Competition (IPC4). Since then, it has been used in a number of other contexts with considerable success, and the use of concise finite-domain representations has become a common feature of state-of-the-art planners.
---
paper_title: Combining classifiers: A theoretical framework

paper_content:

The problem of classifier combination is considered in the context of the two main fusion scenarios: fusion of opinions based on identical and on distinct representations. We develop a theoretical framework for classifier combination for these two scenarios. For multiple experts using distinct representations we argue that many existing schemes such as the product rule, sum rule, min rule, max rule, majority voting, and weighted combination, can be considered as special cases of compound classification. We then consider the effect of classifier combination in the case of multiple experts using a shared representation where the aim of fusion is to obtain a better estimate of the appropriatea posteriori class probabilities. We also show that the two theoretical frameworks can be used for devising fusion strategies when the individual experts use features some of which are shared and the remaining ones distinct. We show that in both cases (distinct and shared representations), the expert fusion involves the computation of a linear or nonlinear function of thea posteriori class probabilities estimated by the individual experts. Classifier combination can therefore be viewed as a multistage classification process whereby thea posteriori class probabilities generated by the individual classifiers are considered as features for a second stage classification scheme. Most importantly, when the linear or nonlinear combination functions are obtained by training, the distinctions between the two scenarios fade away, and one can view classifier fusion in a unified way.
---
paper_title: Improving Control-Knowledge Acquisition for Planning by Active Learning

paper_content:

Automatically acquiring control-knowledge for planning, as it is the case for Machine Learning in general, strongly depends on the training examples. In the case of planning, examples are usually extracted from the search tree generated when solving problems. Therefore, examples depend on the problems used for training. Traditionally, these problems are randomly generated by selecting some difficulty parameters. In this paper, we discuss several active learning schemes that improve the relationship between the number of problems generated and planning results in another test set of problems. Results show that these schemes are quite useful for increasing the number of solved problems.
---
paper_title: Plan Recognition as Planning

paper_content:

In this work we aim to narrow the gap between plan recognition and planning by exploiting the power and generality of recent planning algorithms for recognizing the set G* of goals G that explain a sequence of observations given a domain theory. After providing a crisp definition of this set, we show by means of a suitable problem transformation that a goal G belongs to G* if there is an action sequence π that is an optimal plan for both the goal G and the goal G extended with extra goals representing the observations. Exploiting this result, we show how the set G* can be computed exactly and approximately by minor modifications of existing optimal and suboptimal planning algorithms, and existing polynomial heuristics. Experiments over several domains show that the suboptimal planning algorithms and the polynomial heuristics provide good approximations of the optimal goal set G* while scaling up as well as state-of-the-art planning algorithms and heuristics.
---
paper_title: Learning Control Knowledge for Forward Search Planning

paper_content:

A number of today's state-of-the-art planners are based on forward state-space search. The impressive performance can be attributed to progress in computing domain independent heuristics that perform well across many domains. However, it is easy to find domains where such heuristics provide poor guidance, leading to planning failure. Motivated by such failures, the focus of this paper is to investigate mechanisms for learning domain-specific knowledge to better control forward search in a given domain. While there has been a large body of work on inductive learning of control knowledge for AI planning, there is a void of work aimed at forward-state-space search. One reason for this may be that it is challenging to specify a knowledge representation for compactly representing important concepts across a wide range of domains. One of the main contributions of this work is to introduce a novel feature space for representing such control knowledge. The key idea is to define features in terms of information computed via relaxed plan extraction, which has been a major source of success for non-learning planners. This gives a new way of leveraging relaxed planning techniques in the context of learning. Using this feature space, we describe three forms of control knowledge---reactive policies (decision list rules and measures of progress) and linear heuristics---and show how to learn them and incorporate them into forward state-space search. Our empirical results show that our approaches are able to surpass state-of-the-art non-learning planners across a wide range of planning competition domains.
---
paper_title: Learning Domain-Specific Control Knowledge from Random Walks

paper_content:

We describe and evaluate a system for learning domain-specific control knowledge. In particular, given a planning domain, the goal is to output a control policy that performs well on "long random walk" problem distributions. The system is based on viewing planning domains as very large Markov decision processes and then applying a recent variant of approximate policy iteration that is bootstrapped with a new technique based on random walks. We evaluate the system on the AIPS-2000 planning domains (among others) and show that often the learned policies perform well on problems drawn from the long–random-walk distribution. In addition, we show that these policies often perform well on the original problem distributions from the domains involved. Our evaluation also uncovers limitations of our current system that point to future challenges.
---
paper_title: Evaluating Mixed-Initiative Systems : An Experimental Approach

paper_content:

Mixed-Initiative approaches to Planning and Scheduling are being applied in different real world domains. While several recent successful examples of such tools encourage a wider use of this solving paradigm, research in mixed-initiative interaction is still at an early stage and many important issues need to be addressed. In particular, most of the work has been dedicated to designing working prototypes and identifying relevant features of the mixed-initiative interaction, while much less attention has been given to the problem of evaluating the approach as a whole. This article is aimed at addressing some of the many diverse aspects involved in Mixed-Initiative Planning and Scheduling system evaluation, highlighting the need for a methodology to provide effective evaluation studies for this class of tools. ::: ::: In this paper we consider an established research methodology in experimental psychology, and adopt it to investigate specific aspects of mixed-initiative interaction. Specifically, the experiments described in this article shed some light on three aspects: (a) understanding users' attitude when choosing between automated and mixed-initiative problem solving, (b) investigating recourse to explanation services as a means to foster the users' involvement in the solving process, and (c) investigating possible individual differences (e.g., experts vs. non-experts) in the choice of resolution strategy or access to explanation.
---
paper_title: Kernel functions for case-based planning

paper_content:

Case-based planning can take advantage of former problem-solving experiences by storing in a plan library previously generated plans that can be reused to solve similar planning problems in the future. Although comparative worst-case complexity analyses of plan generation and reuse techniques reveal that it is not possible to achieve provable efficiency gain of reuse over generation, we show that the case-based planning approach can be an effective alternative to plan generation when similar reuse candidates can be chosen. In this paper we describe an innovative case-based planning system, called OAKplan, which can efficiently retrieve planning cases from plan libraries containing more than ten thousand cases, choose heuristically a suitable candidate and adapt it to provide a good quality solution plan which is similar to the one retrieved from the case library. Given a planning problem we encode it as a compact graph structure, that we call Planning Encoding Graph, which gives us a detailed description of the topology of the planning problem. By using this graph representation, we examine an approximate retrieval procedure based on kernel functions that effectively match planning instances, achieving extremely good performance in standard benchmark domains. The experimental results point out the effect of the case base size and the importance of accurate matching functions for global system performance. Overall, we show that OAKplan is competitive with state-of-the-art plan generation systems in terms of number of problems solved, CPU time, plan difference values and plan quality when cases similar to the current planning problem are available in the plan library.
---
paper_title: Probabilistic plan recognition using off-the-shelf classical planners

paper_content:

Plan recognition is the problem of inferring the goals and plans of an agent after observing its behavior. Recently, it has been shown that this problem can be solved efficiently, without the need of a plan library, using slightly modified planning algorithms. In this work, we extend this approach to the more general problem of probabilistic plan recognition where a probability distribution over the set of goals is sought under the assumptions that actions have deterministic effects and both agent and observer have complete information about the initial state. We show that this problem can be solved efficiently using classical planners provided that the probability of a partially observed execution given a goal is defined in terms of the cost difference of achieving the goal under two conditions: complying with the observations, and not complying with them. This cost, and hence the posterior goal probabilities, are computed by means of two calls to a classical planner that no longer has to be modified in any way. A number of examples is considered to illustrate the quality, flexibility, and scalability of the approach.
---
paper_title: Mixed-Initiative Activity Planning for Mars Rovers

paper_content:

One of the ground tools used to operate the Mars Exploration Rovers is a mixed-initiative planning system called MAPGEN. The role of the system is to assist operators building daily plans for each of the rovers, maximizing science return, while maintaining rover safety and abiding by science and engineering constraints. ::: ::: In this paper, we describe the MAPGEN system, focusing on the mixed-initiative planning aspect. We note important challenges, both in terms of human interaction and in terms of automated reasoning requirements. We then describe the approaches taken in MAPGEN, focusing on the novel methods developed by our team.
---
paper_title: A Bayesian model of plan recognition

paper_content:

Abstract We argue that the problem of plan recognition, inferring an agent's plan from observations, is largely a problem of inference under conditions of uncertainty. We present an approach to the plan recognition problem that is based on Bayesian probability theory. In attempting to solve a plan recognition problem we first retrieve candidate explanations. These explanations (sometimes only the most promising ones) are assembled into a plan recognition Bayesian network , which is a representation of a probability distribution over the set of possible explanations. We perform Bayesian updating to choose the most likely interpretation for the set of observed actions. This approach has been implemented in the Wimp3 system for natural language story understanding.
---
paper_title: TRAINS-95: Towards a Mixed-Initiative Planning Assistant

paper_content:

We have been examining mixed-initiative planning systems in the context of command and control or logistical overview situations. In such environments, the human and the computer must work together in a very tightly coupled way to solve problems that neither alone could manage. In this paper, we describe our implementation of a prototype version of such a system, TRAINS-95, which helps a manager solve routing problems in a simple transportation domain. Interestingly perhaps, traditional planning technology does not play a major role in the system, and in fact it is difficult to see how such components might fit into a mixed-initiative system. We describe some of these issues, and present our agenda for future research into mixed-initiative plan reasoning. At this writing, the TRAINS-95 system has been used by more than 100 people to solve simple problems at various conferences and workshops, and in our experiments.
---

Title: A Review of Machine Learning for Automated Planning

Section 1: Introduction
Description 1: This section provides an overview of Automated Planning (AP) and its challenges, along with the significance of Machine Learning (ML) in addressing these challenges.

Section 2: Background
Description 2: This section provides an overview of the area under study, Automated Planning, and presents criteria for reviewing the planning and learning systems.

Section 3: Machine Learning
Description 3: This section discusses common issues when using ML to improve automated processes, including knowledge representation, extraction of experience, learning algorithms, and exploitation of learned knowledge.

Section 4: Learning Planning Action Models
Description 4: This section reviews ML techniques for the automatic definition of action models in AP, categorized by deterministic and stochastic effects, and state observability.

Section 5: Learning Deterministic Models in Fully Observable Environments
Description 5: This subsection discusses ML for AP where planning actions present deterministic effects and state observations are complete and accurate.

Section 6: Learning Deterministic Models in Partially Observable Environments
Description 6: This subsection reviews scenarios where actions present deterministic effects, but the state of the environment is not fully observable, requiring different learning approaches.

Section 7: Learning Stochastic Models in Fully Observable Environments
Description 7: This subsection covers scenarios where observations of the state are perfect, but actions present stochastic effects, requiring probabilistic models.

Section 8: Learning Stochastic Models in Partially Observable Environments
Description 8: This subsection addresses learning in environments where actions present stochastic effects and observations may be incomplete or incorrect.

Section 9: Learning Planning Search Control Knowledge
Description 9: This section examines the learning of knowledge to improve the speed and quality of planning processes, covering different approaches such as macro-actions, generalized policies, heuristic functions, and hierarchical decomposition methods.

Section 10: Learning Planning Search Control in Domains with Uncertainty
Description 10: This section reviews techniques for planning under uncertainty and how ML can aid scalability and performance.

Section 11: Reinforcement Learning
Description 11: This section discusses how Reinforcement Learning (RL) agents interact with the environment to optimize policies, including both model-based and model-free approaches.

Section 12: Model-Based and Model-Free RL
Description 12: This subsection differentiates between Model-Based RL, which requires an environment model, and Model-Free RL, which relies on action-value functions.

Section 13: Relational Reinforcement Learning
Description 13: This subsection focuses on Relational Reinforcement Learning (RRL), where states and actions are represented using relational models similar to predicate logic in AP.

Section 14: Conclusions
Description 14: This section summarizes the paper contents, the identified open issues in learning for AP, and future research directions.

Section 15: Summary
Description 15: This subsection provides a concise synopsis of the paper, highlighting key insights on ML's role in AP and the challenges in learning effective action models and search control knowledge.

Section 16: Open Issues
Description 16: This subsection lists and discusses future avenues and unresolved challenges in ML for AP.