Despite the extensive development of first-principles planning in recent years, planning applications are still primarily developed using knowledge-based planners which can exploit domain-specific heuristics and weaker domain models.  Hierarchical Task Network (HTN) planners capture domain-specific heuristics for more efficient search, accommodate incomplete causal models, and can be used to enforce standard operating procedures.  Unfortunately, we do not have semantics for the methods or tasks that make up HTN models, that help evaluate the correctness of methods, or to build a reliable executive for HTN plans.  This paper fills the gap by providing a well-defined semantics for the methods and plans of SHOP2, a state-of-the-art HTN planner.  The semantics are defined in terms of concurrent golog (ConGolog) and the situation calculus.  We provide a proof of equivalence between the plans generated by SHOP2 and the action sequences of the ConGolog semantics.  We show how the semantics reflects the distinction between plan-time and execution-time, and provide some simple examples showing how the semantics can support method verification.  The semantics provide an implementation-neutral specification for an executive, showing how an executive must treat the plans SHOP2 generates in order to enforce the expected behaviors.  Future directions include automated verification of method specifications, automatically generating plan monitors, and plan revision and repair.

Temporally expressive planning, an important class of temporal planning, has attracted much attention lately. Temporally expressive planning is difficult; few existing planners can solve them, as they have highly concurrent actions. We propose an optimal approach to temporally expressive planning based on a SAT formulation of the problem, finding solutions with the shortest time spans. Our experiments on several temporally expressive domains showed that our planner is able to optimally solve many instances in a reasonable amount of time, comparing favorably to existing temporally expressive planners. Our second result is a temporally expressive planning problem formulation of the Peer-to-Peer (P2P) network communications. In addition to demonstrating a better performance of our new method than the only existing temporally expressive planners on several temporally expressive problem domains, we apply our new planner to find optimal communication schedules for P2P networks. Our results will be potentially useful for designing efficient communication protocols in P2P networks.

This paper explores the use of an oft-ignored information source in heuristic search: a search-distance-to-go estimate. Operators frequently have different costs and cost-to-go is not the same as search-distance-to-go.  We evaluate two previous proposals: dynamically weighted A* and A* epsilon.  We present a revision to dynamically weighted A* that improves its performance substantially in domains where the search does not progress uniformly towards solutions, and particularly in certain temporal planning problems.  We show how to incorporate distance estimates into weighted A* and improve its performance in several domains. Both approaches lead to dramatic performance increases in popular benchmark domains.

This paper proposes an iterative improvement approach for solving the Resource Constraint Project Scheduling Problem with Time-Windows (RCPSP/max), a well-known and challenging NP-hard scheduling problem. The algorithm is based on Iterative Flattening Search (IFS), an effective heuristic strategy for solving multi-capacity optimization scheduling problems. Given an initial solution, IFS iteratively performs two-steps: a relaxation-step , that randomly removes a subset of solution constraints and a solving-step , that incrementally recomputes a new solution. At the end, the best solution found is returned. The main contribution of this paper is the extension to RCPSP/max of the IFS optimization procedures developed for solving scheduling problems without time-windows. An experimental evaluation performed on medium-large size and web-available benchmark sets confirms the effectiveness of the proposed procedures. In particular, we have improved the average quality w.r.t. the current bests, while discovering three new optimal solutions, thus demonstrating the general efficacy of IFS.

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 a generic solution to apply a mission described by a sequence of tasks on a robot while accounting for its physical constraints, without computing explicitly a reference trajectory. A naive solution to this problem would be to schedule the execution of the tasks sequentially, avoiding concurrency. This solution does not exploit fully the robot capabilities such as redundancy and have poor performance in terms of execution time or energy. Our contribution is to determine the time-optimal realization of the mission taking into account robotic constraints that may be as complex as collision avoidance. Our approach achieves more than a simple scheduling; its originality lies in maintaining the task approach in the formulated optimization of the task sequencing problem. This theory is exemplified through a complete experiment on the real HRP-2 robot.

The ability to automatically compose Web Services is critical for realising  more complex functionalities.  Several proposals to use automated planning to deal with the problem of service composition have been recently made. We present an approach, based on modelling the problem as a CSP (Constraint  Satisfaction Problem), that accommodates for the use of numeric variables, sensing and incomplete knowledge. We introduce a language for expressing extended goals, equipped with temporal constructs, maintainability properties, and an explicit distinction between sensing and achievement goals, in order to avoid undesirable situations.

Adaptive A* is an incremental version of A* that updates the h-values of the previous A* search to make them more informed and thus future A* searches more focused. In this paper, we show how the A* searches performed by Adaptive A* can reuse part of the path of the previous search and terminate before they expand a goal state, resulting in Path-Adaptive A*. We demonstrate experimentally that Path-Adaptive A* expands fewer states per search and runs faster than Adaptive A* when solving path-planning problems in initially unknown terrain.

The h m ( m = 1 ... ) family of admissible heuristics for STRIPS planning with additive costs generalise the h max heuristic, which results when m = 1. We show that the step from h 1 to h m can be made by changing the planning problem instead of the heuristic function. This furthers our understanding of the h m heuristic, and may inspire application of the same generalisation to admissible heuristics stronger than h max . As an example, we show how it applies to the additive variant of h m obtained via cost splitting.