Planning--the ability to synthesize a course of action to achieve desired goals--is an important part of intelligent agency and has thus received significant attention within AI for more than 30 years. Work on efficient planning algorithms still continues to be a hot topic for research in AI and has led to several exciting developments in the past few years. This article provides a tutorial introduction to all the algorithms and approaches to the planning problem in AI. To fulfill this ambitious objective, I introduce a generalized approach to plan synthesis called refinement planning and show that in its various guises, refinement planning subsumes most of the algorithms that have been, or are being, developed. It is hoped that this unifying overview provides the reader with a brand-name-free appreciation of the essential issues in planning.

A prerequisite for intelligent behavior is the ability to reason about actions and their effects. This ability is the essence of the classical AI planning problem in which plans are constructed by reasoning about how available actions can be applied to achieve various goals. For this reasoning process to occur, the planner must be aware of its available actions, the situations in which they are applicable, and the changes affected in the world by their execution. Classical AI planners typically use a highlevel, symbolic representation of actions (for example, well-formed formulas from predicate calculus). Although this type of representational scheme is attractive from a computational standpoint, it cannot adequately represent the intricacies of a domain that includes complex actions, such as robotic assembly (consider, for example, that any geometric configuration of the robotic manipulator is a rather complex function of six joint angles).

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. Competitors were invited to come and compete on a collection of domains and associated problems, sight unseen, using whatever planning technology they wanted. (Anderson and Weld 1998). Another important problem was anticipating the demands of the competition domains.

The staff scheduling problem is a critical problem in the call center (or, more generally, customer contact center) industry. Even the simplest variations of this problem are known to be NPcomplete (Garey and Johnson 1978). Although staff scheduling has long been an important operations research problem, scheduling has recently become an important component of an emerging class of business software applications known as workforce management software. The need for effective workforce management systems has been driven primarily by the recent, rapid growth of the call center--customer contact center industry, in which efficient deployment of human resources is of crucial, strategic importance. Traditionally, in this industry, staff scheduling has been performed using ad hoc methods and operations research techniques (Cleveland and Mayben 1997).

The Modified Antarctic Mapping Mission (MAMM) was conducted from September to November 2000 onboard RADARSAT. The mission plan consisted of more than 2400 synthetic aperture radar data acquisitions of Antarctica that achieved the scientific objectives and obeyed RADARSAT's resource and operational constraints. Mission planning is a time-and knowledge-intensive effort. It required over a workyear to manually develop a comparable plan for AMM-1, the precursor mission to MAMM. This article describes the design and use of the automated mission planning system for MAMM, which dramatically reduced mission-planning costs to just a few workweeks and enabled rapid generation of what-if scenarios for evaluating alternative mission designs.

FF. Readers interested in these The 1 sink can only be reached by following the edges labeled 1 from A and B; thus, the represented Boolean function (A, B) evaluates to true if and only if A and B are true. The characteristic function can be identified with the set itself. It seems worthwhile to spend some effort on finding a "good" encoding, which is where the preprocessing of The corresponding BDDs are illustrated in figure 2. Bin We were able to reformulate the initial and final situations as BDDs. As an end in itself, this representation does not help too much. We are interested in a sequence of actions (or transitions) that transforms an initial state into one that satisfies the goal condition.

The Second International Workshop on User Modeling was held March 30-April 1, 1990 in Honolulu, Hawaii. The general chairperson was Dr. Wolfgang Wahlster of the University of Saarbrucken; the program and local arrangements chairperson was Dr. David Chin of the University of Hawaii at Manoa. The workshop was sponsored by AAAI and the University of Hawaii, with AAAI providing eight travel stipends for students. An excellent response to the call for papers and participants resulted in 46 high quality submissions, of which 24 were selected for presentation and discussion led by invited commentators. Whereas the first user modeling workshop, held in Maria Laach, West Germany in 1986, focused on user modeling in natural language dialogue systems, the 1990 workshop covered a broader range of topics, including user modeling in tutoring systems and psychological foundations of user modeling.

SHOP's preconditions can include logical inferences, SHOP's expressive power can be used to create Here, we summarize the SHOP algorithm's primary SHOP algorithm is shown in figure 1. S is a state, T is a list of tasks, and D is the knowledge base (methods, operators, and Horn-clause axioms). As long as the procedure for inferring m's preconditions from S is a sound and complete inference procedure (such as Horn-clause theorem proving), the For example, the Horn clauses can include calls to attached procedures for numeric computations (for example, "distance(UofMD,BWI) 50" in the previous example), or (in some of the implementations) any other procedure calls defined by the user. In our experiments (Nau et al. 1999), SHOP generated SHOP's higher level of expressivity made PLAN and SHOP was not too different. We intend to make more optimizations in the near future. HICAP is shown in figure 4. HICAP (Aha and Breslow 1997).

We report on the staging of the first competition on knowledge engineering for AI planning and scheduling systems, held in Monterey, California, in colocation with the ICAPS 2005 conference. The background and motivation is discussed, together with the relationship of this new competition with the current international planning competition. We report on the new competition's format, its outcome, and the benefits we hope it will bring to the research area. Further, the IPC has facilitated the sharing of benchmark domain models, tasks, and planning tools through the use of PDDL. However, the narrow focus and limiting assumptions of the IPC are controversial--it encourages rapid development, but in the narrow area of fully autonomous plan generation.

To construct a perpetual self-aware cognitive agent that can continuously operate with independence, an introspective machine must be produced. To assemble such an agent, it is necessary to perform a full integration of cognition (planning, understanding, and learning) and metacognition (control and monitoring of cognition) with intelligent behaviors. The failure to do this completely is why similar, more limited efforts have not succeeded in the past. I outline some key computational requirements of metacognition by describing a multistrategy learning system called Meta-AQUA and then discuss an integration of Meta-AQUA with a nonlinear state-space planning agent. I show how the resultant system, INTRO, can independently generate its own goals, and I relate this work to the general issue of self-awareness by machine.