Recent developments have clarified the process of generating partially ordered, partially specified sequences of actions whose execution will achieve an agent's goal. Thus, it should be no surprise that the quest of building intelligent agents has forced AI researchers to investigate algorithms for generating appropriate actions in a timely fashion. Of course, the problem is not yet solved, but considerable progress has been made. In particular, AI researchers have developed two complementary approaches to the problem of generating these actions: (1) planning and (2) situated action. These two techniques have different strengths and weaknesses, as I illustrate later.

Khosrow Hadavi, Wen-Ling Hsu, Tony Chen, and Cheoung-Nam Lee Industrial managers, engineers, and technologists have many expectations from artificial intelligence and its application to knowledge-based systems. Although the past decade has witnessed a number of innovative applications of AI in manufacturing, the field is still in its infancy and holds even greater promise for the future. The AAAI Press book Artificial Intelligence Applications in Manufacturing, (from which the following article was selected) presents a number of articles that relate to the enhancement of planning and decision making capabilities in today's automated production environments. Scheduling problems can generally be described as allocating resources to tasks while satisfying a set of constraints (Baker 1974; Conway et al. 1967). More often than not, the constraint sets are large and diverse, the objectives conflict with each other, and the scheduling problems quickly become NPhard.

Satellite domains are becoming a fashionable area of research within the AI community due to the complexity of the problems that satellite domains need to solve. With the current U.S. and European focus on launching satellites for communication, broadcasting, or localization tasks, among others, the automatic control of these machines becomes an important problem. Many new techniques in both the planning and scheduling fields have been applied successfully, but still much work is left to be done for reliable autonomous architectures. The purpose of this article is to present CONSAT, a real application that plans and schedules the performance of nominal operations in four satellites during the course of a year for a commercial Spanish satellite company, HISPASAT. For this task, we have used an AI domain-independent planner that solves the planning and scheduling problems in the HISPASAT domain thanks to its capability of representing and handling continuous variables, coding functions to obtain the operators' variable values, and the use of control rules to prune the search.

This planning graph structure is then fed to a heuristic extractor module that is capable of extracting a variety of effective and admissible heuristics, based on our recent theory (Nguyen and Kambhampati 2000). This heuristic, along with the problem specification, and the set of ground actions in the final action level of the planning graph structure are fed to a regression state search planner. To guide a regression search in the state space, a heuristic function needs to evaluate the cost of some set S of subgoals, comprising a regression state from the initial state, in terms of the number of actions required to achieve S from the initial state. This heuristic approximates the cost of a set S as the length of a "relaxed plan" for supporting S, ignoring all the mutex relations, plus the penalty for ignoring these negative interac-88 AI MAGAZINE Yochan is the planning group directed by Subbarao Kambhampati at Arizona State University.

The planning competition has become a regular part of the biennial Artificial Intelligence Planning and Scheduling (AIPS) conferences. AIPS'98 featured the very first competition, and for AIPS'00, we built on this foundation to run the second competition. The 2000 competition featured a much larger group of participants and a wide variety of different approaches to planning. Some of these approaches were refinements of known techniques, and others were quite different from anything that had been tried before. Besides the dramatic increase in participation, the 2000 competition demonstrated that planning technology has taken a giant leap forward in performance since 1998.

He holds a B.S. degree in Mathematics from Westminster College, and M.S. and Ph.D. degrees in Computer Science from the University of Pittsburgh. His research interests include constraint-based planning and scheduling, integration of predictive and reactive decision-making, distributed problem solving, temporal reasoning, machine learning, and knowledge-based production management. He has been a principal architect of several knowledge-based scheduling systems for complex manufacturing and space applications. Claude Le Pape is a visiting researcher in the Robotics Laboratory at Stanford University. He received a Ph.D. in Computer Science from University Paris XI in 1988.

A longstanding problem in the field of automated reasoning is designing systems that can describe a set of actions (or a plan) that can be expected to allow the system to reach a desired goal. Ideally, this set of actions is then passed to a robot, a manufacturing system, or some other form of effector, which can follow the plan and produce the desired result. The design of such planners has been with AI since its earliest days, and a large number of techniques have been introduced in progressively more ambitious systems over a long period. In addition, planning research has introduced many problems to the field of AI. Some examples are the representation and the reasoning about time, causality, and intentions; physical or other constraints on suitable solutions; uncertainty in the execution of plans; sensation and perception of the real world and the holding of beliefs about it; and multiple agents who might cooperate or interfere.

This article describes a challenging, real-world planning problem within the context of a NASA mission called LADEE (Lunar Atmospheric and Dust Environment Explorer). I present the approach taken to reduce the complexity of the activity-planning task in order to perform it effectively under the time pressures imposed by the mission requirements. One key aspect of this approach is the design of the activityplanning process based on principles of problem decomposition and planning abstraction levels. The second key aspect is the mixed-initiative system developed for this task, called LASS (LADEE Activity Scheduling System).

David McAllester and David Rosenblitt's paper, "Systematic Nonlinear Planning" (published in the Proceedings of the Ninth National Conference on Artificial Intelligence [AAAI-91]), won the AAAI-10 classic paper award. This commentary by Daniel S. Weld describes the two major impacts the paper had on the field of automated planning. Initially, researchers made many simplifying assumptions, defining the classical planning problem: produce a sequence of atomic actions that will achieve a logically specified goal in a completely known world where action effects are certain. David McAllester and David Rosenblitt's paper, "Systematic Nonlinear Planning" (McAllester and Rosenblitt 1991), presented 19 years ago at the Ninth National Conference on Artificial Intelligence (AAAI-91), had two major impacts on the field: (1) an elegant algorithm and (2) endorsement of the lifting technique. The paper's biggest impact stems from its extremely clear and simple presentation of a sound and complete algorithm (known as SNLP or POP) for classical planning.

The primary revolution in automated planning in the last decade has been the very impressive scaleup in planner performance. A large part of the credit for this can be attributed squarely to the invention and deployment of powerful reachability heuristics. Most, if not all, modern reachability heuristics are based on a remarkably extensible data structure called the planning graph, which made its debut as a bit player in the success of GraphPlan, but quickly grew in prominence to occupy the center stage. Planning graphs are a cheap means to obtain informative look-ahead heuristics for search and have become ubiquitous in state-of-the-art heuristic search planners. We present the foundations of planning graph heuristics in classical planning and explain how their flexibility lets them adapt to more expressive scenarios that consider action costs, goal utility, numeric resources, time, and uncertainty. Considerable work has been done in the last 40 years on modeling a wide variety of ...