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.

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.

This paper considers the execution of a Multi-Agent Plan in a partially observable environment, and faces the problem of recovering from action failures.  The paper formalizes a local plan repair strategy, where each agent in the system is responsible for controlling (monitoring and diagnosing) the actions it executes, and for autonomously repairing its own plan when an action failure is detected.  The paper describes also how to mitigate the impact of an action failure on the plans of other agents when the local recovery strategy fails.

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.

Recently, Richter et al. [2008] proposed a novel some point in every solution plan. Previous work way of using a set of landmarks as a pseudo-heuristic within has very successfully exploited planning landmarks a satisficing heuristic search. This technique allowed both in satisficing (non-optimal) planning. We propose a reducing the length of the generated plans, as well as improving methodology for deriving admissible heuristic estimates success rate both with respect to the iterative approach for cost-optimal planning from a set of planning of Hoffmann et al., and with respect to other stateof-the-art landmarks. The resulting heuristics fall into a satisficing planners. In particular, the LAMA planner novel class of multi-path dependent heuristics, and by Richter and Westphal utilizing such a landmarks-based we present a simple best-first search procedure exploiting heuristic search was the clear winner of the Sequential Satisficing such heuristics.

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.

Detecting abnormal activities from sensor readings is an important research problem in activity recognition. A number of different algorithms have been proposed in the past to tackle this problem. Many of the previous state-based approaches suffer from the problem of failing to decide the appropriate number of states, which are difficult to find through a trial and-error approach, in real-world applications. In this paper, we propose an accurate and flexible framework for abnormal activity recognition from sensor readings that involves less human tuning of model parameters. Our approach first applies a Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM), which supports an infinite number of states, to automatically find an appropriate number of states. We incorporate a Fisher Kernel into the One-Class Support Vector Machine (OCSVM) model to filter out the activities that are likely to be normal. Finally, we derive an abnormal activity model from the normal activity models to reduce false positive rate in an unsupervised manner. Our main contribution is that our proposed HDP-HMM models can decide the appropriate number of states automatically, and that by incorporating a Fisher Kernel into the OCSVM model, we can combine the advantages from generative model and discriminative model. We demonstrate the effectiveness of our approach by using several real-world datasets to test our algorithm’s performance.

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.