This paper describes the Dynamic Execution Order Scheduling (DEOS) system that has been developed to handle highly dynamic and interactive scheduling domains. Unlike typical scheduling problems which have a static task list, DEOS is able to handle dynamic task lists in which tasks are added, deleted and modified "on the fly" DEOS is also able to handle tasks with uncertain and/or probabilistic outcomes. DEOS extends the current scheduling paradigm to allow tasking in dynamic and uncertain environments by viewing the planning and scheduling tasks as being integrated and evolving entities. DEOS has been successfully applied to the domains of Air Campaign Planning (ACP) and Intelligence, Surveillance and Reconnaissance (ISR) management. The paper provides an overview of the dynamic task model and the "penalty box" scheduling algorithm which was developed to provide robust solutions to over constrained scheduling problems. The basic algorithm is described together with extensions to handle flexible time constraints.

Many real world planning problems require goals with deadlines anddurative actions that consume resources. In this paper, we present Sapa, a domain-independent heuristic forward chaining planner thatcan handle durative actions, metric resource constraints, and deadlinegoals. The main innovation of Sapa is the set of distance basedheuristics it employs to control its search. We consider bothoptimizing and satisficing search. For the former, we identifyadmissible heuristics for objective functions based on makespan andslack. For satisficing search, our heuristics are aimed at scalabilitywith reasonable plan quality. Our heuristics are derived from the relaxed temporal planning graph'' structure, which is ageneralization of planning graphs to temporal domains. We also providetechniques for adjusting the heuristic values to account for resourceconstraints. Our experimental results indicate that Sapa returnsgood quality solutions for complex planning problems in reasonabletime.

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.

Low-level direct commanding of space robots can be time consuming or impractical for complex systems with many degrees of freedom. My research will adaptively raise the level of interaction between the operator and the robot by (1) allowing the robot to learn implicit plans by detecting patterns in the interaction history, and (2) enabling the human to demonstrate continuous motions through teleoperation. Learned tasks and plans are recorded for future use. I introduce a novel representation of continuous actions called parameterized probabilistic flow tubes that I hypothesize will more closely encode a human's intended motions and provide flexibility during execution in new situations. I also introduce the use of planning for plan recognition in the domain of hybrid tasks.

Automated planning is a major topic of research in artificial intelligence, and enjoys a long and distinguished history. The classical paradigm assumes a distinguished initial state, comprised of a set of facts, and is defined over a set of actions which change that state in one way or another. Planning in many real-world settings, however, is much more involved: an agent's knowledge is almost never simply a set of facts that are true, and actions that the agent intends to execute never operate the way they are supposed to. Thus, probabilistic planning attempts to incorporate stochastic models directly into the planning process. In this article, we briefly report on probabilistic planning through the lens of probabilistic programming: a programming paradigm that aims to ease the specification of structured probability distributions. In particular, we provide an overview of the features of two systems, HYPE and ALLEGRO, which emphasise different strengths of probabilistic programming that are particularly useful for complex modelling issues raised in probabilistic planning.

Plan recognition is one of the fundamental problems of AI, applicable to many domains, from user interfaces to cyber security. We focus on a class of algorithms that use plan libraries as input to the recognition process. Despite the prevalence of these approaches, they lack a standard representation, and have not been compared to each other on common test bed. This paper directly addresses this gap by providing a standard plan library representation and evaluation criteria to consider. Our representation is comprehensive enough to describe a variety of known plan recognition problems, yet it can be easily applied to existing algorithms, which can be evaluated using our defined criteria. We demonstrate this technique on two known algorithms, SBR and PHATT. We provide meaningful insights both about the differences and abilities of the algorithms. We show that SBR is superior to PHATT both in terms of computation time and space, but at the expense of functionality and compact representation. We also show that depth is the single feature of a plan library that increases the complexity of the recognition, regardless of the algorithm used.

Plan- and Goal Recognition (PGR) is the task of inferring the goals and plans of an agent based on its actions. A few years ago, an approach has been introduced that successfully exploits the performance of planning systems to solve it. That way, no specialized solvers are needed and PGR benefits from present and future research in planning. The approach uses classical planning systems and needs to plan (at least) once for every possible goal. However, models in PGR are often structured in a hierarchical way, similar to Hierarchical Task Networks (HTNs). These models are strictly more expressive than those in classical planning and can describe partially ordered sets of tasks or multiple goals with interleaving plans. We present the approach PGR as HTN Planning that enables the recognition of complex agent behavior by using unmodified, off-the-shelf HTN planners. Planning is thereby needed only once, regardless of how many possible goals there are. Our evaluation shows that current planning systems are able to handle large models with thousands of possible goals and that the approach results in high recognition rates.

An important problem of automated planning is validating if a plan complies with the planning domain model. Such validation is straightforward for classical sequential planning but until recently there was no such validation approach for Hierarchical Task Networks (HTN) planning. In this paper we propose a novel technique for validating HTN plans that is based on representing the HTN model as an attribute grammar and using a special parsing algorithm to verify if the plan can be generated by the grammar.

Low-level motion planning techniques must be combined with high-level task planning formalisms in order to generate realistic plans that can be carried out by humans and robots. Previous attempts to integrate these two planning formalisms mostly used either Classical Planning or HTN Planning. Recently, we developed Hierarchical Goal Networks (HGNs), a new hierarchical planning formalism that combines the advantages of HTN and Classical planning, while mitigating some of the disadvantages of each individual formalism. In this paper, we describe our ongoing research on designing a planning formalism and algorithm that exploits the unique features of HGNs to better integrate task and motion planning. We also describe how the proposed planning framework can be instantiated to solve assembly planning problems involving human-robot teams.

In order for robots to interact with humans in the world around them, it is important that they are not just aware of the presence of people, but also able to understand what those people are doing. In particular, interaction involves multiple agents which requires some form of coordination, and this cannot be achieved by acting blindly. The field of plan recognition (PR) studies methods for identifying an observed agent's task or goal given her action sequence. This is often regarded as the inverse of planning which, given a set of goal conditions, aims to derive a sequence of actions that will achieve the goals when performed from a given initial state. Ram ırez and Geffner (2009; 2010) proposed a simple transformation of PR problems into classical planning problems for which off-the-shelf software is available for quick and efficient implementations. However, there is a reliance on the observed agent's optimality which makes this PR technique most useful as a post-processing step when some of the final actions are observed.