Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems.  We investigate parallel algorithms for optimal sequential planning, with an emphasis on exploiting distributed memory computing clusters.  In particular, we focus on an approach which distributes and schedules work among processors based on a hash function of the search state.  We use this approach to parallelize the A* algorithm in the optimal sequential version of the Fast Downward planner.  The scaling behavior of the algorithm is evaluated experimentally on clusters using up to 128 processors, a significant increase compared to previous work in parallelizing planners.  We show that this approach scales well, allowing us to effectively utilize the large amount of distributed memory to optimally solve problems which require hundreds of gigabytes of RAM to solve. We also show that this approach scales  well for a single, shared-memory multicore machine.

Explaining policies of Markov Decision Processes (MDPs) is complicated due to their probabilistic and sequential nature. We present a technique to explain policies for factored MDP by populating a set of domain-independent templates. We also present a mechanism to determine a minimal set of templates that, viewed together, completely justify the policy. Our explanations can be generated automatically at run-time with no additional effort required from the MDP designer. We demonstrate our technique using the problems of advising undergraduate students in their course selection and assisting people with dementia in completing the task of handwashing. We also evaluate our explanations for course-advising through a user study involving students.

Explicit abstraction heuristics, notably pattern-database and merge-and-shrink heuristics, are employed by some state-of-the-art optimal heuristic-search planners. The major limitation of these abstraction heuristics is that the size of the abstract space has to be bounded by a (large) constant. Targeting this issue, Katz and Domshlak (2008b) introduced structural, and in particular fork-decomposition, abstractions, in which the planning task is abstracted by an instance of a tractable fragment of optimal planning. At first view, however, the lunch was not free. Some of the power of the explicit abstraction heuristics comes from pre-computing the heuristic function offline, and then determine h(s) for each evaluated state s by a very fast lookup in a "database." In contrast, fork-decomposition offer a poly-time, yet far from being fast, computation.   In this contribution, we show that the time-per-node complexity bottleneck of the fork-decomposition heuristics can be successfully overcome. Specifically, we show that an equivalent of the explicit abstractions' notion of "database" exists for the fork-decomposition abstractions as well, and this despite of their exponential-size abstract spaces. Experimentally, we show that heuristic search with such "databased" fork-decomposition heuristics favorably competes with the state-of-the-art of optimal planning.

We provide a theoretical analysis of planning via Petri net unfolding, a novel technique for synthesising parallel plans. Parallel plans are generally valued for their execution flexi- bility, which manifests as alternative choices for the order- ing of operators and potentially faster plan executions. Being a relatively new approach, the flexibility properties of plans synthesised via unfolding, and even the concurrency seman- tics supported by this technique, are particularly unclear and only understood at an informal level. In this paper, we first formally characterise the concurrency semantics of planning via unfolding as a further restriction on the standard notion of independence. More importantly, we then prove that plans obtained using this approach are optimal deorderings and op- timal reorderings in terms of the number of ordering con- straints on operators and plan execution time, respectively. These results provide objective guarantees on the quality of plans obtained by the unfolding technique.

Current heuristic estimators for classical domain-independent planning are usually based on one of four ideas: delete relaxations , critical paths , abstractions , and, most recently, landmarks . Previously, these different ideas for deriving heuristic functions were largely unconnected. We prove that admissible heuristics based on these ideas are in fact very closely related. Exploiting this relationship, we introduce a new admissible heuristic called the landmark cut heuristic , which compares favourably with the state of the art in terms of heuristic accuracy and overall performance.

This paper is concerned with local search methods to solve job shop scheduling problems with uncertain durations modelled as fuzzy numbers. Based on a neighbourhood structure from the literature, a reduced set of moves and the consequent structure are defined. Theoretical results show that the proposed neighbourhood contains all the improving solutions from the original neighbourhood and provide a sufficient condition for optimality. Additionally, a makespan lower bound is proposed which can be used to discard neighbours. Experimental results illustrate the good performance of both proposals, which considerably reduce the computational load of the local search, as well as a synergy effect when they are simultaneously used.

A planning problem is k- dependent if each action has at most k pre-conditions on variables unaffected by the action. This concept is well-founded since k is a constant for all but a few of the standard planning domains, and is known to have implications for tractability. In this paper, we present several new complexity results for P ( k ), the class of k- dependent planning problems with binary variables and polytree causal graphs. The problem of plan generation for P ( k ) is equivalent to determining how many times each variable can change. Using this fact, we present a polytime plan generation algorithm for P (2) and P (3). For constant k > 3, we introduce and use the notion of a cover to find conditions under which plan generation for P ( k ) is polynomial.

Planning systems for real-world applications need the ability to handle concurrency and numeric fluents. Nevertheless, the predominant approach to cope with concurrency followed by the most successful participants in the latest International Planning Competitions (IPC) is still to find a sequential plan that is rescheduled in a post-processing step. We present Temporal Fast Downward (TFD), a planning system for temporal problems that is capable of finding low-makespan plans by performing a heuristic search in a temporal search space. We show how the context-enhanced additive heuristic can be successfully used for temporal planning and how it can be extended to numeric fluents. TFD often produces plans of high quality and, evaluated according to the rating scheme of the last IPC, outperforms all state-of-the-art temporal planning systems.

In this paper we extend dynamic controllability of temporally-flexible plans to temporally-flexible reactive programs.  We consider three reactive programming language constructs whose behavior depends on runtime observations; conditional execution, iteration, and exception handling. Temporally-flexible reactive programs are distinguished from temporally-flexible plans in that program execution is conditioned on the runtime state of the world.  In addition, exceptions are thrown and caught at runtime in response to violated timing constraints, and handled exceptions are considered successful program executions.  Dynamic controllability corresponds to a guarantee that a program will execute to completion, despite runtime constraint violations and uncertainty in runtime state.  An algorithm is developed which frames the dynamic controllability problem as an AND/OR search tree over possible program executions.  A key advantage of this approach is the ability to enumerate only a subset of possible program executions that guarantees dynamic controllability, framed as an AND/OR solution subtree.

Solving real-world problems using symbolic planning often requires a simplified formulation of the original problem, since certain subproblems cannot be represented at all or only in a way leading to inefficiency. For example, manipulation planning may appear as a subproblem in a robotic planning context or a packing problem can be part of a logistics task. In this paper we propose an extension of PDDL for specifying semantic attachments. This allows the evaluation of grounded predicates as well as the change of fluents by externally specified functions. Furthermore, we describe a general schema of integrating semantic attachments into a forward-chaining planner and report on our experience of adding this extension to the planners FF and Temporal Fast Downward. Finally, we present some preliminary experiments using semantic attachments.