Learning Hierarchical Task Models from Input Traces

We describe HTN‐MAKER , an algorithm for learning hierarchical planning knowledge in the form of task‐reduction methods for hierarchical task networks (HTNs). HTN‐MAKER takes as input a set of planning states from a classical planning domain and plans that are applicable to those states, as well as a set of semantically annotated tasks to be accomplished. The algorithm analyzes this semantic information to determine which portion of the input plans accomplishes a particular task and constructs task‐reduction methods based on those analyses. We present theoretical results showing that HTN‐MAKER is sound and complete. Our experiments in five well‐known planning domains confirm the theoretical results and demonstrate convergence toward a set of HTN methods that can be used to solve any problem expressible as a classical planning problem in that domain, relative to a set of goal types for which tasks have been defined. In three of the five domains, HTN planning with the learned methods scales much better than a modern classical planner.     

Planning to see: A hierarchical approach to planning visual actions on a robot using POMDPs

Flexible, general-purpose robots need to autonomously tailor their sensing and information processing to the task at hand. We pose this challenge as the task of planning under uncertainty. In our domain, the goal is to plan a sequence of visual operators to apply on regions of interest (ROIs) in images of a scene, so that a human and a robot can jointly manipulate and converse about objects on a tabletop. We pose visual processing management as an instance of probabilistic sequential decision making, and specifically as a Partially Observable Markov Decision Process (POMDP). The POMDP formulation uses models that quantitatively capture the unreliability of the operators and enable a robot to reason precisely about the trade-offs between plan reliability and plan execution time. Since planning in practical-sized POMDPs is intractable, we partially ameliorate this intractability for visual processing by defining a novel hierarchical POMDP based on the cognitive requirements of the corresponding planning task. We compare our hierarchical POMDP planning system (HiPPo) with a non-hierarchical POMDP formulation and the Continual Planning (CP) framework that handles uncertainty in a qualitative manner. We show empirically that HiPPo and CP outperform the naive application of all visual operators on all ROIs. The key result is that the POMDP methods produce more robust plans than CP or the naive visual processing. In summary, visual processing problems represent a challenging domain for planning techniques and our hierarchical POMDP-based approach for visual processing management opens up a promising new line of research.     

Planning in the Real World

In this article, we describe how real world planning problems can be solved by employing Artificial Intelligence planning techniques. We introduce the paradigm of hybrid planning, which is particularly suited for applications where plans are not intended to be automatically executed by systems, but are made for humans. Hybrid planning combines hierarchical planning – the stepwise refinement of complex tasks – with explicit reasoning about causal dependencies between actions, thereby reflecting exactly the kinds of reasoning humans perform when developing plans. We show how plans are generated and how failed plans are repaired in a way that guarantees stability. Our illustrating examples are taken from a domain model for disaster relief missions enforced upon extensive floods. Finally, we present a tool to support the challenging task of constructing planning domain models.     

Learning second and subsequent programming languages: A problem of transfer

Learning second and subsequent programming languages is easier than learning a first programming language because many concepts and constructs are shared. However, it is still a hard task. In this protocol analysis of moderately experienced programmers transferring to a new programming language, we classified episodes by whether they involved the syntactic, semantic, or planning level of programming knowledge. We discovered that most episodes involve planning and that in solving a given subproblem there are typically many cycles of language‐independent tactical planning followed by language‐dependent implementation planning. On the other hand, programmers have relatively minor problems with the syntax and semantics of a new language. Our subjects’ protocols and their final programs revealed that the plans they develop are strongly influenced by their knowledge of what would be convenient and appropriate in other languages they know. This prevents them from taking full advantage of the capabilities of the new language.     

Model transformations in simulation and planning: behaviorpreserving model simplifications

Reasoning tasks such as simulation and planning involve deriving behavior of a system from a model of the system. The information needed to solve such problems can be represented as model behavior pairs (MBPs). The problem can be stated as one or more incomplete MBPs. The problem-solving method can be expressed as a sequence of MBP completions and comparisons. A language for representing and manipulating models, behaviors, and MBPs is presented. It is independent of any specific modeling domain. An important class of model transformation operators is the behavior-preserving model transformation operators. Because they preserve behavior, they can be used to simplify a model without compromising its value for problem solving. This sort of operator can speed up computations significantly. It can be used either to select an appropriate sub-model for a specific problem or to decompose a problem into a sequence of subproblems. A behavior-preserving pruning operator is presented and shown to work in three modeling domains: discrete event simulation (DES), planning, and qualitative physics (QP). The significance of this work lies in the domain independence of the language and operators. It provides a representation midway between the computer-oriented concepts of programming languages (and knowledge representation schemes) and the problem oriented concepts of the real world. The benefits that can result from such a representation are easy mapping of problem-to-solution method, easy communication between solution methods (when more than one reasoning technique is required to solve a problem) and efficient solution of problems     

Planning in the Real World

In this article, we describe how real world planning problems can be solved by employing Artificial Intelligence planning techniques. We introduce the paradigm of hybrid planning, which is particularly suited for applications where plans are not intended to be automatically executed by systems, but are made for humans. Hybrid planning combines hierarchical planning ?C the stepwise refinement of complex tasks ?C with explicit reasoning about causal dependencies between actions, thereby reflecting exactly the kinds of reasoning humans perform when developing plans. We show how plans are generated and how failed plans are repaired in a way that guarantees stability. Our illustrating examples are taken from a domain model for disaster relief missions enforced upon extensive floods. Finally, we present a tool to support the challenging task of constructing planning domain models. The article ends with an overview of a wide varity of actual planning applications and outlines further such in the area of cognitive technical systems.     

A case-based approach to heuristic planning

Most of the great success of heuristic search as an approach to AI Planning is due to the right design of domain-independent heuristics. Although many heuristic planners perform reasonably well, the computational cost of computing the heuristic function in every search node is very high, causing the planner to scale poorly when increasing the size of the planning tasks. For tackling this problem, planners can incorporate additional domain-dependent heuristics in order to improve their performance. Learning-based planners try to automatically acquire these domain-dependent heuristics using previous solved problems. In this work, we present a case-based reasoning approach that learns abstracted state transitions that serve as domain control knowledge for improving the planning process. The recommendations from the retrieved cases are used as guidance for pruning or ordering nodes in different heuristic search algorithms applied to planning tasks. We show that the CBR guidance is appropriate for a considerable number of planning benchmarks.     

On the interaction between plan recognition and intelligent interfaces

Plan recognition is an active research area in automatic reasoning, as well as a promising approach to engineering interfaces that can exploit models of user's plans and goals. Much research in the field has focused on the development of plan recognition algorithms to support particular user/system interactions, such as found in naturally occurring dialogues. However, two questions have typically remained unexamined: 1) exactly what kind of interface tasks can knowledge of a user's plans be used to support across communication modalities, and 2) how can such tasks in turn constrain development of plan recognition algorithms? In this paper we present a concrete exploration of these issues. In particular, we provide an assessment of plan recognition, with respect to the use of plan recognition in enhancing user interfaces. We clarify how use of a user model containing plans makes interfaces more intelligent and interactive (by providing an intelligent assistant that supports such tasks as advice generation, task completion, context-sensitive responses, error detection and recovery). We then show how interface tasks in turn provide constraints that must be satisfied in order for any plan recognizer to construct and represent a plan in ways that efficiently support these tasks. Finally, we survey how interfaces are fundamentally limited by current plan recognition approaches, and use these limitations to identify and motivate current research. Our research is developed in the context of CHECS, a plan-based design interface.     

Functional Maps Representation On Product Manifolds

We consider the tasks of representing, analysing and manipulating maps between shapes. We model maps as densities over the product manifold of the input shapes; these densities can be treated as scalar functions and therefore are manipulable using the language of signal processing on manifolds. Being a manifold itself, the product space endows the set of maps with a geometry of its own, which we exploit to define map operations in the spectral domain; we also derive relationships with other existing representations (soft maps and functional maps). To apply these ideas in practice, we discretize product manifolds and their Laplace–Beltrami operators, and we introduce localized spectral analysis of the product manifold as a novel tool for map processing. Our framework applies to maps defined between and across 2D and 3D shapes without requiring special adjustment, and it can be implemented efficiently with simple operations on sparse matrices.     

Relational Reinforcement Learning

Relational reinforcement learning is presented, a learning technique that combines reinforcement learning with relational learning or inductive logic programming. Due to the use of a more expressive representation language to represent states, actions and Q-functions, relational reinforcement learning can be potentially applied to a new range of learning tasks. One such task that we investigate is planning in the blocks world, where it is assumed that the effects of the actions are unknown to the agent and the agent has to learn a policy. Within this simple domain we show that relational reinforcement learning solves some existing problems with reinforcement learning. In particular, relational reinforcement learning allows us to employ structural representations, to abstract from specific goals pursued and to exploit the results of previous learning phases when addressing new (more complex) situations.     

Planning and execution through variable resolution planning

Generating sequences of actions–plans–for robots using Automated Planning in stochastic and dynamic environments has been shown to be a difficult task with high computational complexity. These plans are composed of actions whose execution might fail due to different reasons. In many cases, if the execution of an action fails, it prevents the execution of some (or all) of the remainder actions in the plan. Therefore, in most real-world scenarios computing a complete and sound (valid) plan at each (re-)planning step is not worth the computational resources and time required to generate the plan. This is specially true given the high probability of plan execution failure. Besides, in many real-world environments, plans must be generated fast, both at the start of the execution and after every execution failure. In this paper, we present Variable Resolution Planning which uses Automated Planning to quickly compute a reasonable (not necessarily sound) plan. Our approach computes an abstract representation–removing some information from the planning task–which is used once a search depth of $k$ steps has been reached. Thus, our approach generates a plan where the first $k$ actions are applicable if the domain is stationary and deterministic, while the rest of the plan might not be necessarily applicable. The advantages of this approach are that it: is faster than regular full-fledged planning (both in the probabilistic or deterministic settings); does not spend much time on the far future actions that probably will not be executed, since in most cases it will need to replan before executing the end of the plan; and takes into account some information of the far future, as an improvement over pure reactive systems. We present experimental results on different robotics domains that simulate tasks on stochastic environments.