Recently, universal planning has become feasible through the use of efficient symbolic methods for plan generation and representation based on reduced ordered binary decision diagrams (OBDDs). In this paper, we address adversarial universal planning for multi-agent domains in which a set of uncontrollable agents may be adversarial to us (as in e.g.

The operational traffic control problem comes up in a number of different contexts. It involves the coordinated movement of a set of vehicles and has by and large the flavor of a scheduling problem. In trying to apply scheduling techniques to the problem, one notes that this is a job-shop scheduling problem with blocking, a type of scheduling problem that is quite unusual. In particular, we will highlight a condition necessary to guarantee that job-shop schedules can be executed in the presences of the blocking constraint. Based on the insight that the traffic problem is a scheduling problem, we can derive the computational complexity of the operational traffic control problem and can design some algorithms to deal with this problem. In particular, we will specify a very simple method that works well in fast-time simulation contexts.

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.