Partial states are states in which the truth value of one or more propositions is unknown. Such states are usually generated in regression and represent not a single state but rather a set of states. Because of this, a new partial state can be a subset of another existent partial state, phenomenon known as subsumption of states. Subsumed states can be pruned as if they were a duplicate. However, regular duplicate detection methods cannot detect such cases. Furthermore, subsumption of states also occurs when forward and backward search algorithms are integrated into a bidirectional planner. In these cases, the forward frontier contains only complete states and the backward frontier will often contain partial states. In this work, we analyze the impact that subsumption of states has on search and propose methods for duplicate detection and detection of collision of frontiers.

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. Experimental results from an air operations domain validate the effectiveness of the approach relative to typical waterfall models of planner/scheduler integration.

In this paper we introduce a planning problem termed as Q-Blocks Relocation Problem, which pursues to retrieve a subset of blocks located in a warehouse by minimizing the number of relocation movements. We formalize the problem by means of a Mixed Integer Linear Programming model. However, the high computational burden required by the model encourages us to develop a heuristic algorithm for tackling it. The rationale behind the proposed heuristic is both to retrieve the requested blocks as soon as possible while reducing the number of blocks placed above another one with a higher priority. The computational results indicate that the heuristic reports near-optimal solutions for realistic instances by short computational times, which makes it attractive to be applied by management systems.

Planning under uncertainty faces a scalability problem when considering multi-robot teams, as the information space scales exponentially with the number of robots. To address this issue, this paper proposes to decentralize multi-robot Partially Observable Markov Decision Processes (POMDPs) while maintaining cooperation between robots by using POMDP policy auctions. Auctions provide a flexible way of coordinating individual policies modeled by POMDPs and have low communication requirements. Additionally, communication models in the multi-agent POMDP literature severely mismatch with real inter-robot communication. We address this issue by exploiting a decentralized data fusion method in order to efficiently maintain a joint belief state among the robots. The paper presents results in two different applications: environmental monitoring with Unmanned Aerial Vehicles (UAVs); and cooperative tracking, in which several robots have to jointly track a moving target of interest.

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. The first stage, a preprocessing stage, facilitates the management of constraints on duration of actions. The second stage expands a temporal graph and obtains the set of temporal levels at which propositions and actions appear. The third stage, the plan extraction, obtains the plan of minimal duration by finding a proper flow of actions.

A general and important problem of search-based planning techniques is the state explosion problem, which is usually tackled with approaches to reduce the branching factor of the planning task. Such approaches often implicitly exploit the observation that the number of available operators is higher than the number of operators that are actually needed to find a plan. In this paper, we propose a simple, but general under-approximation refinement framework for satisficing planning that explicitly exploits this observation. Our approach iteratively searches for plans with operator subsets , which are refined if necessary by adding operators that appear to be needed. Our evaluation shows that even a straight-forward instantiation of this framework yields a competitive planner that often finds plans with small operator sets.

A growing interest in the industrial sector for autonomous ground vehicles has prompted significant investment in fleet management systems. Such systems need to accommodate on-line externally imposed temporal and spatial requirements, and to adhere to them even in the presence of contingencies. Moreover, a fleet management system should ensure correctness, i.e., refuse to commit to requirements that cannot be satisfied. We present an approach to obtain sets of alternative execution patterns (called trajectory envelopes) which provide these guarantees. The approach relies on a constraint-based representation shared among multiple solvers, each of which progressively refines trajectory envelopes following a least commitment principle.

This volume contains the papers accepted for presentation at ECP 2001, the Sixth European Conference on Planning, held in Toledo, Spain, on September 12-14, 2001. ECP continued the traditional high standards of AIPS and ECP as an archival forum for new research in the field of automated planning and scheduling. ECP conferences were first organized in 1991.

The papers in this proceedings present the latest advances in the field of automated planning and scheduling, ranging in scope from theoretical analyses of planning and scheduling problems and processes, to new algorithms for planning and scheduling under various constraints and assumptions, and the empirical evaluation of planning and scheduling techniques. They reflect recent research trends in subareas such as optimal planning, probabilistic and nondeterministic planning, path planning, multiagent planning, and new developments in heuristics and their analysis for planning algorithms.

Proof planning considers mathematical theorem proving as a planning problem. It has enabled the derivation of mathematical theorems that lay outside the scope of traditional logic-based theorem proving systems. One of its strengths comes from heuristic mathematical knowledge that restricts the search space and thereby facilitates the proving process for problems whose proofs belong in the restricted search space. But this may exclude solutions or restrict the kinds of proofs that can be found for a given problem. We take a different perspective and investigate problem classes for which little or no heuristic control knowledge is available and test the usage of randomization and restart techniques. Our approach to control in those mathematical domains is based on investigations on so-called heavy-tailed distributions (Gomes et al. 2000; 1998; 1998). Because of the non-standard nature of heavy-tailed cost distributions the controlled introduction of randomization into the search procedure and quick restarts of the randomized procedure can eliminate heavy-tailed behavior and can take advantage of short runs. To apply these techniques to the complicated domains of proof planning, the first task was to find problem classes for which proof planning exhibits an unpredictable run time behavior, i.e., with heavy-tailed cost distributions. Secondly, the experiments provided the basis for determining suitable cutoff values, i.e., the time interval after which a running proof attempt is interrupted and a new attempt is started. Finally, we designed a new control strategy which dramatically boosts the performance of our proof planner for a class of problems for which proof planning exhibits heavy-tailed cost behavior.