I was asked to give a visionary talk about the future applications of Artificial Intelligence technology; but I should warn you that I'm actually not very good as a visionary. Most of my predictions about what will happen in the industry don't come true even though they ought to. So I'm not going to tell you what the future holds; what I will do is to point out some of the technological trends that are at work. The outline of the talk is as follows: I'll start off by looking at the previous IAAI conferences and reflect on what we've learned from them. Then I'll look at what's changing in the hardware base that sets the context for all the computer applications we do. I think that will lead to interesting new viewpoints. Next I'll sketch what applications might arise from this new viewpoint. Finally, I'll discuss how the development of practical applications ought to interact with the scientific enterprise of trying to understand intelligence, in particular, human intelligence.

The Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2000) was held on 14-17 April 2000 at Breckenridge, Colorado; it was colocated with the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR2000). This conference brought together researchers working in all aspects of problems in planning, scheduling, planning and learning, and plan execution for dealing with complex problems.

In this project, we have developed the ramp activity coordination expert system (races) to solve aircraft-parking problems. races includes a knowledge-based scheduling system that assigns all daily arriving and departing flights to the gates and remote spots with domain-specific knowledge and heuristics acquired from human experts. races processes complex scheduling problems such as dynamic interrelations among the characteristics of remote spots-gates and aircraft with various other constraints, for example, customs and ground-handling factors, at an airport. By user-driven modeling for end users and near-optimal knowledge-driven scheduling acquired from human experts, races can produce parking schedules for about 400 daily flights in approximately 20 seconds; human experts normally take 4 to 5 hours to do the same. Scheduling results in the form of Gantt charts produced by races are also accepted by the domain experts. races is also designed to deal with the partial adjustment of the schedule when unexpected events occur. After daily scheduling is completed, the messages for aircraft change, and delay messages are reflected and updated into the schedule according to the knowledge of the domain experts. By analyzing the knowledge model of the domain expert, the reactive scheduling steps are effectively represented as the rules, and the scenarios of the graphic user interfaces are designed. Because the modification of the aircraft dispositions, such as aircraft changes and cancellations of flights, is reflected in the current schedule, the modification should be sent to races from the mainframe for the reactive scheduling. The adjustments of the schedule are made semiautomatically by races because there are many irregularities in dealing with the partial rescheduling.

We tackle the problem of planning in nondeterministic domains, by presenting a new approach to conformant planning. Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal despite the nondeterminism of the domain. Our approach is based on the representation of the planning domain as a finite state automaton. We use Symbolic Model Checking techniques, in particular Binary Decision Diagrams, to compactly represent and efficiently search the automaton. In this paper we make the following contributions. First, we present a general planning algorithm for conformant planning, which applies to fully nondeterministic domains, with uncertainty in the initial condition and in action effects. The algorithm is based on a breadth-first, backward search, and returns conformant plans of minimal length, if a solution to the planning problem exists, otherwise it terminates concluding that the problem admits no conformant solution. Second, we provide a symbolic representation of the search space based on Binary Decision Diagrams (BDDs), which is the basis for search techniques derived from symbolic model checking. The symbolic representation makes it possible to analyze potentially large sets of states and transitions in a single computation step, thus providing for an efficient implementation. Third, we present CMBP (Conformant Model Based Planner), an efficient implementation of the data structures and algorithm described above, directly based on BDD manipulations, which allows for a compact representation of the search layers and an efficient implementation of the search steps. Finally, we present an experimental comparison of our approach with the state-of-the-art conformant planners CGP, QBFPLAN and GPT. Our analysis includes all the planning problems from the distribution packages of these systems, plus other problems defined to stress a number of specific factors. Our approach appears to be the most effective: CMBP is strictly more expressive than QBFPLAN and CGP and, in all the problems where a comparison is possible, CMBP outperforms its competitors, sometimes by orders of magnitude.

Recently model checking representation and search techniques were shown to be efficiently applicable to planning, in particular to non-deterministic planning. Such planning approaches use Ordered Binary Decision Diagrams (OBDDs) to encode a planning domain as a non-deterministic finite automaton and then apply fast algorithms from model checking to search for a solution. OBDDs can effectively scale and can provide universal plans for complex planning domains. We are particularly interested in addressing the complexities arising in non-deterministic, multi-agent domains. In this article, we present UMOP, a new universal OBDD-based planning framework for non-deterministic, multi-agent domains. We introduce a new planning domain description language, NADL, to specify non-deterministic, multi-agent domains. The language contributes the explicit definition of controllable agents and uncontrollable environment agents. We describe the syntax and semantics of NADL and show how to build an efficient OBDD-based representation of an NADL description. The UMOP planning system uses NADL and different OBDD-based universal planning algorithms. It includes the previously developed strong and strong cyclic planning algorithms. In addition, we introduce our new optimistic planning algorithm that relaxes optimality guarantees and generates plausible universal plans in some domains where no strong nor strong cyclic solution exists. We present empirical results applying UMOP to domains ranging from deterministic and single-agent with no environment actions to non-deterministic and multi-agent with complex environment actions. UMOP is shown to be a rich and efficient planning system.

The 1998 Planning Competition at the AI Planning Systems Conference was the first of its kind. Its goal was to create planning domains that a wide variety of planning researchers could agree on to make comparison among planners more meaningful, measure overall progress in the field, and set up a framework for long-term creation of a repository of problems in a standard notation. One result of these discussions was the pddl notation for planning domains. This notation was used to set up a set of planning problems and get a modest problem repository started.

In 1998, the international planning community was invited to take part in the first planning competition, hosted by the Artificial Intelligence Planning Systems Conference, to provide a new impetus for empirical evaluation and direct comparison of automatic domain-independent planning systems. This article describes the systems that competed in the event, examines the results, and considers some of the implications for the future of the field.

The 1998 Planning Competition at the AI Planning Systems Conference was the first of its kind. Its goal was to create planning domains that a wide variety of planning researchers could agree on to make comparison among planners more meaningful, measure overall progress in the field, and set up a framework for long-term creation of a repository of problems in a standard notation. A rules committee for the competition was created in 1997 and had long discussions on how the contest should go. One result of these discussions was the pddl notation for planning domains. This notation was used to set up a set of planning problems and get a modest problem repository started. As a result, five planning systems were able to compete when the contest took place in June 1998. All these systems solved problems in the strips framework, with some slight extensions. The attempt to find domains for other forms of planning foundered because of technical and organizational problems. In spite of this problem, the competition achieved its goals partially in that it con-firmed that substantial progress had occurred in some subfields of planning, and it allowed qualitative comparison among different planning algorithms. It is urged that the competition continue to take place and to evolve.

In 1998, the international planning community was invited to take part in the first planning competition, hosted by the Artificial Intelligence Planning Systems Conference, to provide a new impetus for empirical evaluation and direct comparison of automatic domain-independent planning systems. This article describes the systems that competed in the event, examines the results, and considers some of the implications for the future of the field.

The paper addresses the problem of computing goal orderings, which is one of the longstanding issues in AI planning. It makes two new contributions. First, it formally defines and discusses two different goal orderings, which are called the reasonable and the forced ordering. Both orderings are defined for simple STRIPS operators as well as for more complex ADL operators supporting negation and conditional effects. The complexity of these orderings is investigated and their practical relevance is discussed. Secondly, two different methods to compute reasonable goal orderings are developed. One of them is based on planning graphs, while the other investigates the set of actions directly. Finally, it is shown how the ordering relations, which have been derived for a given set of goals G, can be used to compute a so-called goal agenda that divides G into an ordered set of subgoals. Any planner can then, in principle, use the goal agenda to plan for increasing sets of subgoals. This can lead to an exponential complexity reduction, as the solution to a complex planning problem is found by solving easier subproblems. Since only a polynomial overhead is caused by the goal agenda computation, a potential exists to dramatically speed up planning algorithms as we demonstrate in the empirical evaluation, where we use this method in the IPP planner.