While traditionally classical planning concentrated on finding plans for solvable tasks, detecting unsolvable instances has recently attracted increasing interest. To preclude wrong results, it is desirable that the planning system provides a certificate of unsolvability that can be independently verified. We propose a rule-based proof system for unsolvability where a proof establishes a knowledge base of verifiable basic statements and applies a set of derivation rules to infer the unsolvability of the task from these statements. We argue that this approach is more flexible than a recent proposal of inductive certificates of unsolvability and show how our proof system can be used for a wide range of planning techniques.

An important problem of automated planning is validating if a plan complies with the domain model. Such validation is straightforward for classical sequential planning but until recently there was no plan validation approach for Hierarchical Task Networks (HTN). In this paper we propose a novel technique for validating HTN plans by parsing of attribute grammars with the timeline constraint.

We develop an effective computer model to simulate sensing environments that consist of natural trees. The simulated environments are random and contain full geometry of the tree foliage. While this simulated model can be used as a general platform for studying the sensing mechanism of different flying species, our ultimate goal is to build bat-inspired Quad-rotor UAVs-- UAVs that can recreate bat's flying behavior (e.g., obstacle avoidance, path planning) in dense vegetation. To this end, we also introduce a foliage echo simulator that can produce simulated echoes by mimicking bat's biosonar. In our current model, a few realistic model choices or assumptions are made.

Finding the shortest plan for a given planning problem is extremely hard. We present a domain independent approach for plan optimisation based on Genetic Programming. The algorithm is seeded with correct plans created by hand-encoded heuristic policy sets. The plans are very unlikely to be optimal but are created quickly. The suboptimal plans are then evolved using a generational algorithm towards the optimal plan. We present initial results from Blocks World and found that GP method almost always improved sub-optimal plans, often drastically.

This paper presents TPSYS, a Temporal Planning SYStem, which arises as an attempt to combine the ideas of Graphplan andTGP to solve temporal planning problems more efficiently. TPSYS is based on a three-stage process.

This paper is concerned with temporal planning relying on CSP-based functional representations. These powerful representations are today mostly restricted to the use of piecewise constant functions ranging over finite domains. We are proposing here an extension that brings a significant enhancement in the expressiveness of the representation, towards handling continuous change. This extension consists mainly in allowing piecewise linear functions over continuous domains. We have studied this extension and are currently implementing it in the IXTET planner. However this extended representation is not specific to IXTET; it can be useful to most temporal planners. We show how IXTET syntax, planning algorithm and control can be simply extended to this class of functions. We then consider the more significant modifications required in the two constraints managers for handling temporal and atemporal CSPs.

Many known planning tasks have inherent constraints concerning the best order in which to achieve the goals. A number of research efforts have been made to detect such constraints and use them for guiding search, in the hope to speed up the planning process. We go beyond the previous approaches by defining ordering constraints not only over the (top level) goals, but also over the sub-goals that will arise during planning. Landmarks are facts that must be true at some point in every valid solution plan. We show how such landmarks can be found, how their inherent ordering constraints can be approximated, and how this information can be used to decompose a given planning task into several smaller sub-tasks. Our methodology is completely domain- and planner-independent. The implementation demonstrates that the approach can yield significant performance improvements in both heuristic forward search and Graphplan-style planning.

Several real world applications require planners that deal with non-deterministic domains and with temporally extended goals. Recent research is addressing this planning problem. However, the ability of dealing in practice with large state spaces is still an open problem. In this paper we describe a planning algorithm for extended goals that makes use of BDD-based symbolic model checking techniques. We implement the algorithm in the MBP planner, evaluate its applicability experimentally, and compare it with existing tools and algorithms. The results show that, in spite of the difficulty of the problem, MBP deals in practice with domains of large size and with goals of a certain complexity.

We describe an incremental and adaptive approach to integrating hierarchical task network planning and constraint-based scheduling. The approach is grounded in the concept of approximating the'resource intensity' of planning options. A given planning problem is decomposed into a sequence of (not necessarily independent) subtasks, which are planned and then scheduled in turn. During planning, operators are rated according to a heuristic estimate of their expected resource requirements. Options are selected that best match a computed'target intensity' for planning. Feedback from the scheduler is used to adapt the target intensity after completion of each subplan, thus guiding the planner toward solutions that are tuned to resource availability.

This paper summarizes the main existing approaches to propagate resource constraints in Constraint-Based scheduling and identifies some of their limitations for using them in an integrated planning and scheduling framework. We then describe two new algorithms to propagate resource constraints on discrete resources and reservoirs. Unlike most of the classical work in scheduling, our algorithms focus on the precedence relations between activities rather than on their absolute position in time. They are efficient even when the set of activities is not completely defined and when the time window of activities is large. These features explain why our algorithms are particularly suited for integrated planning and scheduling approaches. All our algorithms are illustrated with examples. Encouraging preliminary results are reported on pure scheduling problems.