Copyright © 1999 Massachusetts Institute of Technology
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.
Early work in cognitive science sought to create general domain-independent problem solvers that exhibited some of the characteristics observed in human problem solving. The most influential early example was the General Problem Solver (GPS) proposed in 1959 (Newell and Simon 1963). It introduced techniques still in regular use today: means-ends analysis or goal directed problem solving, and finding "differences" between goal and current states.
This work was combined with search methods being studied in operations research (e.g., branch-and-bound methods), and with research on representation and reasoning from predicate logic in various theorem proving methods (e.g., Green 1969), so that by the end of the 1960s some long-lasting methods were emerging (see HEURISTIC SEARCH and SITUATION CALCULUS).
In 1969, the Stanford Research Institute Problem Solver, or STRIPS, (Fikes, Hart, and Nilsson 1971) represented application domain states in first-order logic, introduced a way to represent the actions of the domain in terms of changes to the world state, used means-end analysis to identify goals and subgoals that needed to be solved as stepping stones to a solution, searched through a space of possible solutions, and employed a simple but effective representation of the actions possible in the domain -- as STRIPS operators. Many of these techniques form the basis for later work in planning.
Many planning techniques are formulated as search problems. Early planning approaches, including STRIPS, used a search technique in which the nodes of the search represented application domain states directly and the search arcs were the domain actions that could transform those states. This is termed "application state space" or "situation space." For example, the node state might represent the position of a robot waiter and the items on various tables:
and the action arcs might represent the movement of a robot waiter, or a pickup action of the robot:
STRIPS operators represent an action as having preconditions that have to be satisfied in the state in which the action is performed, and a delete list and add list of effects that represent changes made to the state following the performance of the action.
Later approaches have concentrated on searching through a different space -- that of partially defined plans. A search space node is a partial plan and an arc is a partial plan modification operator (PMO). For example, a PMO might ensure the satisfaction of a condition on some activity in the partial plan. Each node of the search space defines an entire set of possible plan elaborations that fit within the constraints in the partial-plan. This method therefore can support "constraint posting" or "least commitment planning" in which decisions are postponed rather than a selection being made arbitrarily.
The integration of powerful constraint management techniques alongside planning methods is possible within this framework (e.g., as in MOLGEN (Stefik 1981) for plan object constraints, Deviser (Vere 1981) and FORBIN (Dean, Firby, and Miller 1990) for temporal constraints, and SIPE (Wilkins 1988) for resource constraints). This means that planning and scheduling techniques can be intermixed (see TEMPORAL REASONING).
Partial-plan search spaces lend themselves very well to "refinement planning" approaches (Kambhampati, Knoblock, and Yang 1996), where an outline plan is refined to address outstanding flaws or issues. However, it also lends itself to refining existing partial descriptions of a solution to a problem, to instantiating previously created generic plans, or to adapting plans drawn from case libraries (see CASE-BASED REASONING AND ANALOGY).
In the mid-1970s, NOAH (for Net of Action Hierarchies) (Sacerdoti 1977), and then "Nonlin" (the nonlinear planner built by Austin Tate) (Tate 1977), began to allow plans to be represented as partial orders on the actions contained within them, rather than insisting on the activities within plans being fully ordered. (Unfortunately, the terminology of the time led to partially ordered plans also being called "nonlinear" plans, which caused confusion with the "linear" and "nonlinear" planning approaches to the order in which goals and sub goals were solved in planners.) Some problems that had caused difficulty for earlier planners such as STRIPS were more easily addressed when a partially ordered plan representation was used, but it became more difficult to ensure that conditions on actions in the plan were satisfied from the effects of earlier actions. Potential interactions with parallel actions had to be resolved in a valid plan. Means to "protect" the condition establishment had to be added to planners (as introduced in HACKER; Sussman 1975). The "Nonlin" planner's question answering procedure (Tate 1977) included means to decide whether a specified condition was already satisfied at a given point in a partially ordered network of actions and, if necessary, could propose orderings to be added to the plan to satisfy such a condition. This provides information that can support the protection of the plan's causal structure (also called "goal structure" or "teleology"). This work was later used as the basis for the formalization of the "modal truth criterion" (Chapman 1991) used at the heart of later planners for condition establishment and protection.
Partially ordered planning (POP) algorithms are the basis for a number of modern planners such as SIPE (Wilkins 1988), O-Plan (Currie and Tate 1991), and UCPOP (Penberthy and Weld 1992).
The hierarchical organization of action descriptions is an important technique that may reduce complexity and signifi cantly increase the scale of plans that can be generated in some domains. Most practical planners employ "hierarchical planning" methods. A library of action descriptions is maintained, some of which have a decomposition into a number of subactions at a more detailed level, and some of which are considered "primitive." For example, in the robot waiter domain, a high-level "Cleartable" action may be decomposed into primitive subactions to move to a table, pick up an item on the table, move to the counter, and put down the item held in the robot hand. A higher-level action in the plan can then be replaced with some suitable decomposition into more detailed actions. This is sometimes referred to as "hierarchical task network" (HTN) planning.
HTN planning lends itself to the refinement planning model. An initial plan can incorporate the task specification, assumptions about the situation in which the plan is to be executed, and perhaps a partial solution. This can then be refined through the hierarchy into greater levels of detail while also addressing outstanding issues and flaws in the plan.
Researchers and technologists in the planning field have added many extra features to the basic STRIPS action representation over the years. These have included:
The expressiveness of a planner's action representation is a major contributor to the effectiveness of a planning system, but can also lead to very large search spaces if used in uncontrolled ways (see COMPUTATIONAL COMPLEXITY).
Techniques from knowledge engineering and knowledge acquisition are beginning to be used to improve the modeling and capture of information about planning domains. In common with experience in KNOWLEDGE-BASED SYSTEMS, the use of richer models of the application domain have been found to be beneficial, such as in search space pruning and guidance.
Planning as a field has branched out in recent years to include a wide range of research topics related to reasoning about activities. One important area of investigation involves planning for activities that take place in environments where the outcome of actions is uncertain. For example, the robot waiter "Pickup" action may fail if an object is too heavy. Some of the techniques used in "classical" AI planning assume "perfect" information about the outcomes of actions. However, there is also a great deal of work on coping with uncertainty during the planning process or during the execution of plans.
Conditional or "contingency" branches may be included in a plan to allow for the most likely scenarios. "Reactive planning" techniques can be used to select activities at execution time on the basis of the situation that a system finds itself in. Uncertainty has also been addressed by general-purpose algorithms for solving planning problems cast as Markov decision processes (Dean et. al. 1995; see also MULTIAGENT SYSTEMS).
The volume Readings in Planning (Allen, Hendler, and Tate 1990) collects together many seminal papers that have documented the main advances in the field of planning. It presents a historical perspective to the work undertaken in this field. Several overviews in the Readings volume from different perspectives serve as an introduction to research on planning.
Allen, J. F., J. Hendler, and A. Tate. (1990). Readings in Planning. San Francisco: Kaufmann.
Chapman, D. (1991). Planning for conjunctive goals. Artificial Intelligence 32:333-377.
Currie, K. W., and A. Tate. (1991). O-Plan: The Open Planning Architecture. Artificial Intelligence 52(1):49-86.
Dean, T., J. Firby, and D. Miller. (1990). Hierarchical planning involving deadlines, travel time and resources. Computational Intelligence 4(4):381-398.
Dean, T., L. Kaebling, J. Kirman, and A. Nicholson. (1995). Planning under time constraints in stochastic domains. Artificial Intelligence 76 (1-2): 35 - 74.
Fikes, R. E., P. E. Hart, and N. J. Nilsson. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 3(4):251-288.
Green, C. (1969). Application of theorem proving to problem solving. Proceedings of the First International Joint Conference on Artificial Intelligence (IJCAI-69). Washington, DC: IJCAII, pp. 219-239.
Kambhampati, S., C. Knoblock, and Q. Yang. (1995). Planning as refinement search: A unified framework for evaluating design tradeoffs in partial order planning. Artificial Intelligence 76:167-238.
Newell, A., and H. A. Simon. (1963). GPS, a program that simulates human thought. In E. A. Fiegenbaum and J. Feldman, Eds., Computers and Thought. New York: McGraw Hill, pp. 279-293.
Penberthy, J. S., and D. S. Weld. (1992). UCPOP: A sound, complete, partial order planner for ADL. Proceedings of Knowledge Representation 1992 (KR-92) pp. 103-114.
Sacerdoti, E. D. (1974). Planning in a hierarchy of abstraction spaces. Artificial Intelligence 5(2):115-135.
Sacerdoti, E. D. (1977). A Structure for Plans and Behavior. Amsterdam: Elsevier.
Stefik, M. J. (1981). Planning with constraints. Artificial Intelligence 16:111-140.
Sussman, G. J. (1975). A Computer Model of Skill Acquisition. Elsevier/North-Holland.
Tate, A. (1977). Generating project networks. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-77) San Francisco: Kaufmann.
Vere, S. (1981). Planning in time: Windows and durations for activities and goals. In IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 5. Los Alamitos, CA: IEEE Press.
Wilkins, D. (1988). Practical Planning. San Francisco: Morgan Kaufmann.
Drabble, B. (1996). Proceedings of the Third International Conference on Artificial Intelligence Planning Systems. Menlo Park, CA: AAAI Press.
Georgeff, M. P., and A. L. Lansky. (1986). Reasoning about actions and plans. In Proceedings of the 1986 Workshop, Timberline, Oregon. San Francisco: Morgan Kaufmann.
Kambhampati, S., and D. S. Nau. (1996). On the nature and role of modal truth criteria in planning. AIJ 82:129-155.
McAllister, D., and D. Rosenblitt. (1991). Systematic non-linear planning. In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91), vol. 2. Anahiem, CA: AAAI Press, pp. 634-639.
Russell, S. J., and P. Norvig. (1995). Artificial Intelligence: A Modern Approach. Englewood, NJ: Prentice-Hall.
Simmons, R., and M. Veloso. (1998). Proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems. Menlo Park, CA: AAAI Press.
Tate, A., Ed. (1996). Advanced Planning Technology -- The Technological Achievements of the ARPA/Rome Laboratory Planning Initiative. Menlo Park, CA: AAAI Press.
Weld, D. (1994). An introduction to least-commitment planning. Artificial Intelligence 15:27-61.
Zweben, M., and M. E. Fox, Eds. (1995). Intelligent Scheduling. San Francisco: Kaufmann.
Copyright © 1999 Massachusetts Institute of Technology