Search methods based on Monte-Carlo simulation have recently led to breakthrough performance improvements in difficult game-playing domains such as Go and General Game Playing. Monte-Carlo Random Walk (MRW) planning applies Monte-Carlo ideas to deterministic classical planning. In the forward chaining planner Arvand, Monte-Carlo random walks are used to explore the local neighborhood of a search state for action selection. In contrast to the stochastic local search approach used in the recent planner Identidem, random walks yield a larger and unbiased sample of the search neighborhood, and require state evaluations only at the endpoints of each walk. On IPC-4 competition problems, the performance of Arvand is competitive with state of the art systems.

While much work on learning in planning focused on learning domain physics (i.e., action models), and search control knowledge, little attention has been paid towards learning user preferences on desirable plans. Hierarchical task networks (HTN) are known to provide an effective way to encode user prescriptions about what constitute good plans. However, manual construction of these methods is complex and error prone. In this paper, we propose a novel approach to learning probabilistic hierarchical task networks that capture user preferences by examining user-produced plans given no prior information about the methods (in contrast, most prior work on learning within the HTN framework focused on learning “method preconditions”—i.e., domain physics—assuming that the structure of the methods is given as input). We will show that this problem has close parallels to the problem of probabilistic grammar induction, and describe how grammar induction methods can be adapted to learn task networks. We will empirically demonstrate the effectiveness of our approach by showing that task networks we learn are able to generate plans with a distribution close to the distribution of the userpreferred plans.

Past approaches for solving MDPs have several weaknesses: 1) Decision-theoretic computation over the state space can yield optimal results but scales poorly. 2) Value-function approximation typically requires human-specified basis functions and has not been shown successful on nominal ("discrete") domains such as those in the ICAPS planning competitions. 3) Replanning by applying a classical planner to a determinized domain model can generate approximate policies for very large problems but has trouble handling probabilistic subtlety.  This paper presents ReTrASE, a novel MDP solver, which combines decision theory, function approximation and classical planning in a new way. ReTrASE uses classical planning to create basis functions for value-function approximation and applies expected-utility analysis to this compact space. Our algorithm is memory-efficient and fast (due to its compact, approximate representation), returns high-quality solutions (due to the decision-theoretic framework) and does not require additional knowledge from domain engineers (since we apply classical planning to automatically construct the basis functions). Experiments demonstrate that ReTrASE outperforms winners from the past three probabilistic-planning competitions on many hard problems.

Heuristic search using heuristics extracted from the delete relaxation is one of the most effective methods in planning. Since finding the optimal solution of the delete relaxation is intractable, various heuristics introduce independence assumptions, the implications of which are not yet fully understood. Here we use concepts from graph theory to show that in problems with unary action preconditions, the delete relaxation is closely related to the Steiner Tree problem, and that the independence assumption for the set of goals results in a tree-of-shortest-paths approximation. We analyze the limitations of this approximation and develop an alternative method for computing relaxed plans that addresses them. The method is used to guide a greedy best-first search, where it is shown to improve plan quality and coverage over several benchmark domains.

In many real world planning domains, some observation information is optional and useless to the execution of a plan; on the other hand, information acquisition may require some kind of cost. The problem of observation reduction for strong plans has been addressed in the literature. However, observation reduction for plans with contexts (which are more general and useful than strong plans in robotics) is still a open problem. In this paper, we present an attempt to solve the problem. Our first contribution is the definition of structured plans, which can encode sequential, conditional and iterative behaviors, and is expressive enough for dealing with incomplete observation information and internal states of the agent. A second contribution is an observation reduction algorithm for plans with contexts, which can transform a plan with contexts into a structured plan that only branches on necessary observation information.

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 ND-HTN-Maker, that exploits these properties.  We implemented ND-HTN-Maker in the recently-proposed HTN-Maker system, a goal-regression based HTN learning approach.  In our theoretical study, we show that ND-HTN-Maker 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.

This paper presents a new algorithm for plan recognition called ELEXIR (Engine for LEXicalized Intent Recognition).  ELEXIR represents the plans to be recognized with a grammatical formalism called Combinatory Categorial Grammar(CCG).  We show that representing plans with CCGs can allow us to prevent early commitment to plan goals and thereby reduce runtime.

Recent progress on external-memory MDP solvers has enabled optimal solutions to large probabilistic planning problems. However, PEMVI requires a human to manually partition the MDP before the planning algorithm can be applied — putting an added burden on the domain designer and detracting from the vision of automated planning.  This paper presents a novel partitioning scheme, which automatically subdivides the state space into blocks that respect the memory constraints. Our algorithm first applies static domain analysis to identify candidates for partitioning, and then uses heuristic search to generate a good partition.  We evaluate the usefulness of our method in the context of PEMVI across many benchmark domains, showing that it can successfully solve extremely large problems in each domain. We also compare the performance of automatic partitioning with previously reported results using human-designed partitions. Experiments show that our algorithm generates significantly superior partitions, which speed MDP solving and also yield vast memory savings.

Most planning problems have strong structures. They can be decomposed into subdomains with causal dependencies. The idea of exploiting the domain decomposition has motivated previous work such as hierarchical planning and factored planing. However, these algorithms require extensive backtracking and lead to few efficient general-purpose planners. On the other hand, heuristic search has been a successful approach to automated planning. The domain decomposition of planning problems, unfortunately, is not directly and fully exploited by heuristic search. We propose a novel and general framework to exploit domain decomposition. Based on a structure analysis on the SAS+ planning formalism, we stratify the sub-domains of a planning problem into dependency layers. By recognizing the stratification of a planning structure, we propose a space reduction method that expands only a subset of executable actions at each state. This reduction method can be combined with state-space search, allowing us to simultaneously employ the strength of domain decomposition and high-quality heuristics. We prove that the reduction preserves completeness and optimality of search and experimentally verify its effectiveness in space reduction.

Planning with temporally extended goals and uncontrollable events has recently been introduced as a formal model for system reconfiguration problems. An important application is to automatically reconfigure a real-life system in such a way that its subsequent internal evolution is consistent with a temporal goal formula. In this paper we introduce an incremental search algorithm and a search-guidance heuristic, two generic planning enhancements. An initial problem is decomposed into a series of subproblems, providing two main ways of speeding up a search. Firstly, a subproblem focuses on a part of the initial goal. Secondly, a notion of action relevance allows to explore with higher priority actions that are heuristically considered to be more relevant to the subproblem at hand. Even though our techniques are more generally applicable, we restrict our attention to planning with temporally extended goals and uncontrollable events. Our ideas are implemented on top of a successful previous system that performs online learning to better guide planning and to safely avoid potentially expensive searches. In experiments, the system speed performance is further improved by a convincing margin.