"...an artificial intelligence system was placed on board to plan and execute spacecraft activities. In contrast to remote control, this sophisticated set of computer programs acts as an agent of the operations team on board the remote spacecraft. Rather than have humans do the detailed planning necessary to carry out desired tasks, remote agent will formulate its own plans, using high level goals provided by the operations team....Remote agent, like the other high-risk technologies that have now been tested on DS1, promises to make space exploration of the future more productive and more exciting while staying within NASA's limited budget." - from NASA's site about REMOTE AGENT

Good Places to Start

Planning and Scheduling. A very clear presentation from NASA offered as part of its site about Deep Space 1's Remote Agent.

Planning and Scheduling Artificial Intelligence Group at JPL (NASA's Jet Propulsion Laboratory). "The Artificial Intelligence Group performs basic research in the areas of Artificial Intelligence Planning and Scheduling, with applications to science analysis, spacecraft commanding, deep space network operations, and space transportation systems."

• A bibliography is also provided at this site.

Planning. Entry by Austin Tate in the MIT Encyclopedia of Cognitive Science. "Planning is the process of generating (possibly partial) representations of future behavior prior to the use of such plans to constrain or control that behavior. The outcome is usually a set of actions, with temporal and other constraints on them, for execution by some agent or agents. As a core aspect of human intelligence, planning has been studied since the earliest days of AI and cognitive science. Planning research has led to many useful tools for real-world applications, and has yielded significant insights into the organization of behavior and the nature of reasoning about actions."

AI Planning: Systems and Techniques. By James Hendler, Austin Tate, Mark Drummond. AI Magazine 11(2): 61-77 (Summer 1990). "This article reviews research in the development of plan generation systems. Our goal is to familiarize the reader with some of the important problems that have arisen in the design of planning systems and to discuss some of the many solutions that have been developed in the over 30 years of research in this area. In this article, we broadly cover the major ideas in the field of AI planning and show the direction in which some current research is going. We define some of the terms commonly used in the planning literature, describe some of the basic issues coming from the design of planning systems, and survey results in the area. Because such tasks are virtually never ending, and thus, any finite document must be incomplete, we provide references to connect each idea to the appropriate literature and allow readers access to the work most relevant to their own research or applications." Some of the terms and planners covered are: application domanin, operator schemata, primitive action, STRIPS, HACKER, NOAH, NONLIN, NASL, OPM,ISIS-II, MOLGEN, SIPE, DEVISER and FORBIN.

Planning articles appearing in the Fall 2001 issue of AI Magazine, 22(3):

• The AIPS '00 Planning Competition
• FF: The Fast-Forward Planning System
• The GRT Planner
• MIPS: The Model-Checking Integrated Planning System
• A Planner Called R
• Heuristic Search Planner 2.0
• STAN4: A Hybrid Planning Strategy Based on Subproblem Abstraction;
• Tokenplan
• AltAlt: Combining Graphplan and Heuristic State Search
• The Shop Planning System
• TALPlanner: A Temporal Logic-Based Planner
• Planning in the Fluent Calculus Using Binary Decision Diagrams

Planning and Scheduling. In CRC Handbook of Computer Science and Engineering. (1996) By Thomas Dean and Subbarao Kambhampati. "In this chapter, we use the generic term planning to encompass both planning and scheduling problems, and the terms planner or planning system to refer to software for planning or scheduling. Planning is concerned with reasoning about the consequences of acting in order to choose from among a set of possible courses of action. In the simplest case, a planner might enumerate a set of possible courses of action, consider their consequences in turn, and choose one particular course of action that satisfies a given set of requirements. ... To distinguish between planning and scheduling we note that scheduling is primarily concerned with figuring out when to carry out actions while planning is concerned with what actions need to be carried out. In practice this distinction often blurs and many real-world problems involve figuring out both what and when." (Postscript version available from the Brown University Artificial Intelligence Group collection of publications.)

Recent Advances in AI Planning: A Unified View. Tutorials from Subbarao Kambhampati.

Planning. A summary by Patrick Doyle. "Planning is a problem solving technique. Planning is reasoning about future events in order to verify the existence of a reasonable series of actions to take in order to accomplish a goal. There are three major benefits of planning: reducing search, resolving goal conflicts, and providing a basis for error recovery."

Planning and Scheduling Materials from The Computational Intelligence Research Laboratory (CIRL) of the University of Oregon:

• "In industry in general, the term planning has been used to describe a wide variety of problems, including problems referred to by the artificial intelligence community as scheduling or bin packing. In AI, the term planning is used to describe the construction of a sequence of formally-described world-states, as follows: A planning domain consists of a set of operators or action types. Each operator may be executed only in some particular set of world states (its preconditions), and has some particular set of effects on its world state (its effects). A planning problem consists of a planning domain together with an initial state of the world, and a desired goal state (or set of goal states) of the world. A planner solves a planning problem by producing a sequence of actions (operator instances), each of which is legal in its starting world state, which takes the initial state to a goal state. ... An often cited example of a planning domain is the infamous blocks world, a model of stacks of blocks on an infinite table."
• "Scheduling is the problem of assigning a set of tasks to a set of resources subject to a set of constraints. Examples of scheduling constraints include deadlines (e.g., job i must be completed by time t), resource capacities (e.g., there are only four drills), precedence constraints on the order of tasks (e.g., a piece must be sanded before it is painted), and priorities on tasks (e.g., finish job j as soon as possible while meeting the other deadlines). Examples of scheduling domains include classical job-shop scheduling, manufacturing scheduling, and transportation scheduling." In addition to papers and articles, their page offers links to application programs.

Readings Online

Planning and Scheduling Publications. From the University of Salford. An extensive collection of papers available online.

The Fifth International Conference on Artificial Intelligence Planning and Scheduling. By Anthony Barrett and Steve Chien. AI Magazine 21(4): 111-115 (Winter 2000).

POMDPs for Dummies. By Tony Cassandra, Brown University's Computer Science Department. "This is a tutorial aimed at trying to build up the intuition behind solution procedures for partially observable Markov decision processes (POMDPs). It sacrifices completeness for clarity. It tries to present the main problems geometrically, rather than with a series of formulas. In fact, we avoid the actual formulas altogether, try to keep notation to a minimum and rely on pictures to build up the intuition. We try to keep the required background to a minimum and provide some brief mini-tutorials on the required background material."

Planning Under Uncertainty. A collection of related publications co-authored by Thomas Dean, Professor of Computer Science, Brown University.

Why you should buy an emotional planner. By Jonathan Gratch. In Proceedings of the Agents'99 Workshop on Emotion-based Agent Architectures.

Multiagent Systems: A Survey from a Machine Learning Perspective. By Peter Stone and Manuela Veloso, Computer Science Department, Carnegie Mellon University. "Another example of a domain that requires MAS is hospital scheduling as presented in [20]. This domain from an actual case study requires different agents to represent the interests of different people within the hospital. Hospital employees have different interests, from nurses who want to minimize the patient's time in the hospital, to x-ray operators who want to maximize the throughput on their machines. Since different people evaluate candidate schedules with different criteria, they must be represented by separate agents if their interests are to be justly considered." - Multiagent Systems

Related Web Sites

AI on the Web: Planning. A resource companion to Stuart Russell and Peter Norvig's "Artificial Intelligence: A Modern Approach." that provides links to reference material, people, research groups, software, companies and much more.

AI Planning Resources. Maintained by Rob St. Amant. "This is a list of AI planners and where they were developed, or where implementations are currently accessible."

AIG, the Artificial Intelligence Group at NASA's Jet Propulsion Laboratory, California Institute of Technology, "performs basic research in the areas of Artificial Intelligence Planning and Scheduling, with applications to science analysis, spacecraft commanding, deep space network operations, and space transportation systems."

Intelligent Coordination and Logistics Laboratory (ICLL) at the Carnegie Mellon University Robotics Institute. One of the projects you'll find there is Integrated Planning and Scheduling: "In collaboration with the researchers at SRI, we are investigating the development of techniques for tighter integration of planning and scheduling processes. Starting from pre-existing planning and scheduling technologies (SRI's CHIP HTN Planner and CMU's ACS scheduler), we have developed a joint planner/scheduler for air operations planning."

"The International Conference on Automated Planning and Scheduling (ICAPS) is the premier forum for researchers and practitioners in planning and scheduling - two technologies critical to manufacturing, space systems, software engineering, robotics, education, and entertainment. The ICAPS conference resulted from merging two bi-annual conferences, namely the International Conference on Artificial Intelligence Planning and Scheduling (AIPS) and the European Conference on Planning (ECP)."

MAPGEN: Advanced mission planning - MAPGEN handles routine plan generation process. From NASA's Computational Sciences Division. "Almost 30 years have passed since the Viking missions of the mid-1970s, the last successful science-driven NASA mission to land on Mars. Indeed, NASA is hoping for a large scientific return with the 2003 Mars Exploration Rover (MER) Mission that is under way. ... NASA is working to develop software that will give rovers more autonomy so that missions can conduct more science. MAPGEN (Mixed Initiative Activity Planning Generator) is a ground-based decision support system for MER mission operations and science teams that begins to give content to the notion of autonomous planetary exploration."

• Learn more about MAPGEN.

PLANET: European Network of Excellence in AI Planning. "PLANET is a coordinating organisation for European research and development in the field of Artificial Intelligence Planning and Scheduling and in particular aims to promote the transfer of this leading-edge technology into European industry." Be sure to check out their collection of resources.

POMDP information page. From Michael Littman. "A POMDP is a partially observable Markov decision process. It is a model, originating in the operations research (OR) literature, for describing planning tasks in which the decision maker does not have complete information as to its current state. The POMDP model provides a convenient way of reasoning about tradeoffs between actions to gain reward and actions to gain information."

• also see: POMDP Symposium Home Page - 1998 American Association for Artificial Intelligence Fall Symposium Planning with Partially Observable Markov Decision Processes.

Research in Planning Systems. Computer Science and Engineering, University of Washington. Scroll down their page to find descriptions of several projects, with links to papers and related web sites.

More Readings

Reinforcement Learning Repository at University of Massachusetts, Amherst.

• Topics > Planning: "The issue of planning is one that is common to Artificial Intelligence methods: an agent must devise a sequence of actions that leads from an initial state to a goal state. However, in the context of RL, planning is often required to be done under uncertainty."
• Technical Publications on Reinforcement Learning > Industrial Applications & Planning.