N-gram analysis provides a means of probabilistically predicting the next item in a sequence. Due originally to Shannon, it has proven an effective technique for word prediction in natural language processing and for gene sequence analysis. In this paper, we investigate the utility of n-gram analysis in predicting operator sequences in plans. Given a set of sample plans, we perform n-gram analysis to predict the likelihood of subsequent operators, relative to a partial plan. We identify several ways in which this information might be integrated into a planner. In this paper, we investigate one of these directions in further detail. Preliminary results demonstrate the promise of n-gram analysis as a tool for improving planning performance.

It has long been recognized that users can have complex preferences on plans.  Non-intrusive learning of such preferences by observing the plans executed by the user is an attractive idea. Unfortunately, the executed plans are often not a true representation of user preferences, as they result from the interaction between user preferences and feasibility constraints. In the travel planning scenario, a user whose true preference is to travel by a plane may well be frequently observed traveling by car because of feasibility constraints (perhaps the user is a poor graduate student). In this work, we describe a novel method for learning true user preferences obfuscated by such feasibility constraints.  Our base learner induces probabilistic hierarchical task networks (pHTNs) from sets of training plans. Our approach is to rescale the input so that it represents the user's preference distribution on plans rather than the observed distribution on plans.

This paper presents multi-goal planning for an autonomous blasthole drill used in open pit mining operations. Given a blasthole pattern to be drilled and constraints on the vehicle's motion and orientation when drilling, we wish to compute the best order in which to drill the given pattern. Blasthole pattern drilling is an asymmetric Traveling Salesman Problem with precedence constraints specifying that some holes must be drilled before others. We wish to find the minimum cost tour according to criteria that minimize the distance travelled satisfying the precedence and vehicle motion constraints. We present an iterative method for solving the blasthole sequencing problem using the combination of a Genetic Algorithm and motion planning simulations that we use to determine the true cost of travel between any two holes.

Nowadays many urban areas have been equipped with networks of surveillance cameras, which can be used for automatic localization and tracking of people. However, given the large resource demands of imaging sensors in terms of bandwidth and computing power, processing the image streams of all cameras simultaneously might not be feasible. In this paper, we consider the problem of dynamical sensor selection based on user-defined objectives, such as maximizing coverage or improved localization uncertainty.  We propose a decision-theoretic approach modeled as a POMDP, which selects k sensors to consider in the next time frame, incorporating all observations made in the past. We show how, by changing the POMDP's reward function, we can change the system's behavior in a straightforward manner, fulfilling the user's chosen objective. We successfully apply our techniques to a network of 10 cameras.

We consider real-time planning problems in which some states are unsolvable, i.e., have no path to a goal. Such problems are difficult for real-time planning algorithms such as RTA* in which all states must be solvable. We identify a property called k-safeness, in which the consequences of a bad choice become apparent within k moves after the choice is made. When k is not too large, this makes it possible to identify unsolvable states in real time. We provide a modified version of RTA* that is provably complete on all k -safe problems. We derive k -safeness conditions for real-time deterministic versions of the well-known Tireworld and Racetrack domains, and provide experimental results showing that our modified version of RTA* works quite well in these domains.

This paper considers Just-In-Time Job-Shop Scheduling, in which each activity has an earliness and a tardiness cost with respect to a due date. It proposes a constraint programming approach, which includes a novel filtering algorithm and dedicated heuristics. The filtering algorithm uses a machine relaxation to produce a lower bound that can be obtained by solving a Just-In-Time Pert problem. It also includes pruning rules which update the variable bounds and detect precedence constraints. The paper presents experimental results which demonstrate the effectiveness of the approach over a wide range of benchmarks.

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.

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.

Finite-state and memoryless controllers are simple action selection mechanisms widely used in domains such as video-games and mobile robotics.  Memoryless controllers stand for functions that map observations into actions, while finite-state controllers generalize memoryless ones with a finite amount of memory.  In contrast to the policies obtained from MDPs and POMDPs, finite-state controllers have two advantages: they are often extremely compact, involving a small number of controller states or none at all, and they are general, applying to many problems and not just one. A limitation of finite-state controllers is that they must be written by hand. In this work, we address this limitation, and develop a method for deriving finite-state controllers automatically from models. These models represent a class of contingent problems where actions are deterministic and some fluents are observable.  The problem of deriving a controller from such models is converted into a conformant planning problem that is solved using classical planners, taking advantage of a complete translation introduced recently.  The controllers derived in this way are 'general' in the sense that they do not solve the original problem only, but many variations as well, including changes in the size of the problem or in the uncertainty of the initial situation and action effects.  Experiments illustrating the derivation of such controllers are presented.