Partial order reduction is a state space pruning approach that has been originally introduced in computer aided verification. Recently, various partial order reduction techniques have also been proposed for planning. Despite very similar underlying ideas, the relevant literature from computer aided verification has hardly been analyzed in the planning area so far, and it is unclear how these techniques are formally related. We provide an analysis of existing partial order reduction techniques and their relationships. We show that recently proposed approaches in planning are instances of general partial order reduction approaches from computer aided verification. Our analysis reveals a hierarchy of dominance relationships and shows that there is still room for improvement for partial order reduction techniques in planning. Overall, we provide a first step towards a better understanding and a unifying theory of partial order reduction techniques from different areas.

Many important problems are too difficult to solve optimally. A traditional approach to such problems is bounded suboptimal search, which guarantees solution costs within a user-specified factor of optimal. Recently, a complementary approach has been proposed: bounded-cost search, where solution cost is required to be below a user-specified absolute bound. In this paper, we show how bounded-cost search can incorporate inadmissible estimates of solution cost and solution length. This information has previously been shown to improve bounded suboptimal search and, in an empirical evaluation over five benchmark domains, we find that our new algorithms surpass the state-of-the-art in bounded-cost search as well, particularly for domains where action costs differ.

The RW-LS planner Arvand-LS is described Most successful current satisficing planners combine several next, followed by a section about the generation and selection complementary search algorithms. Examples range from of harder problems from existing IPC domains for portfolio planners such as Fast Downward Stone Soup which scalable problem generators are available. The experimental (Helmert, Röger, and Karpas 2011) and loosely coupled parallel results for Arvand-LS show strong improvements planners such as ArvandHerd (Valenzano et al. 2011) to over the state of the art in both coverage and plan quality for systems which alternate several search strategies, such as FF hard problems from several IPC domains. The paper concludes (Hoffmann and Nebel 2001), FD (Helmert 2006), and ArvandHerd, with a discussion of possible future work, including and dual queue search algorithms as in LAMA perspectives for a portfolio system containing Arvand-LS. (Richter and Westphal 2010).

Portfolio planners and parameter tuning are two ideas that have recently attracted significant attention in the domain-independent planning community. We combine these two ideas and present a portfolio planner that runs automatically configured planners. We let the automatic parameter tuning framework ParamILS find fast configurations of the Fast Downward planning system for a number of planning domains. Afterwards we learn a portfolio of those planner configurations. Evaluation of our portfolio planner on the IPC 2011 domains shows that it has a significantly higher IPC score than the winner of the sequential satisficing track.

Optimal plans of delete-free planning tasks are interesting both in domains that have no delete effects and as the relaxation heuristic h+ in general planning. Many heuristics for optimal and satisficing planning approximate the h+ heuristic, which is well-informed and admissible but intractable to compute. In this work, branch-and-bound and IDA* search are used in a search space tailored to delete-free planning together with an incrementally computed version of the LM-cut heuristic. The resulting algorithm for optimal delete-free planning exceeds the performance of A* with the LM-cut heuristic in the state-of-the-art planner Fast Downward.

Partial-order plans (POPs) are attractive because of their least commitment nature, providing enhanced plan flexibility at execution time relative to sequential plans. Despite the appeal of POPs, most of the recent research on automated plan generation has focused on sequential plans. In this paper we examine the task of POP generation by relaxing or modifying the action orderings of a plan to optimize for plan criteria that promotes flexibility in the POP. Our approach relies on a novel partial weighted MaxSAT encoding of a plan that supports the minimization of deordering or reordering of actions. We further extend the classical least commitment criterion for a POP to consider the number of actions in a solution, and provide an encoding to achieve least commitment plans with respect to this criterion. We compare the effectiveness of our approach to a previous approach for POP generation via sequential-plan relaxation. Our results show that while the previous approach is proficient at heuristically finding the optimal deordering of a plan, our approach gains greater flexibility with the optimal reordering .

We present a simple and efficient algorithm to solve delete-free planning problems optimally and calculate the h+ heuristic. The algorithm efficiently computes a minimum-cost hitting set for a complete set of disjunctive action landmarks generated on the fly. Unlike other recent approaches, the landmarks it generates are guaranteed to be set-inclusion minimal. In almost all delete-relaxed IPC domains, this leads to a significant coverage and runtime improvement.

The paper illustrates a novel approach to conformant planning using classical planners. The approach relies on two core ideas developed to deal with incomplete information in the initial situation: the use of a classical planner to solve non-classical planning problems, and the reduction of the size of the initial belief state. Differently from previous uses of classical planners to solve non-classical planning problems, the approach proposed in this paper creates a valid plan from a possible plan---by inserting actions into the possible plan and maintaining only one level of non-deterministic choice (i.e., the initial plan being modified). The algorithm can be instantiated with different classical planners---the paper presents the GC[LAMA] implementation, whose classical planner is LAMA. We investigate properties of the approach, including conditions for completeness. GC[LAMA] is empirically evaluated against state-of-the-art conformant planners, using benchmarks from the literature. The experimental results show that GC[LAMA] is superior to other planners, in both performance and scalability. GC[LAMA] is the only planner that can solve the largest instances from several domains. The paper investigates the reasons behind the good performance and the challenges encountered in GC[LAMA].

The problem of automated planning is known to be intractable in general. Moreover, it has been proven that in some cases finding an optimal solution is much harder than finding any solution. Existing techniques have to compromise between speed of the planning process and quality of solutions. For example, techniques based on greedy search often are able to obtain solutions quickly, but the quality of the solutions is usually low. Similarly, adding macro-operators to planning domains often enables planning speed-up, but solution sequences are typically longer. In this paper, we propose a method for optimizing plans with respect to their length, by post-planning analysis. The method is based on analyzing action dependencies and independencies by which we are able to identify redundant actions or non-optimal sub-plans. To evaluate the process we provide preliminary empirical evidence using benchmark domains.

We consider the problem of on-line continual planning, in whichadditional goals may arrive while plans for previous goals are stillexecuting and plan quality depends on how quickly goals are achieved.This is a challenging problem even in domains with deterministicactions. One common and straightforward approach is reactive planning,in which plans are synthesized when a new goal arrives. In this paper,we adapt the technique of hindsight optimization from on-line schedulingand probabilistic planning to create an anticipatory on-line planningalgorithm. Using an estimate of the goal arrival distribution, wesample possible futures and use a deterministic planner to estimate thevalue of taking possible actions at each time step. Results in twobenchmark domains based on unmanned aerial vehicle planning andmanufacturing suggest that an anticipatory approach yields a superiorplanner that is sensitive not only to which action should be executed,but when.