...with temporal and other constraints on them, for execution by some agent or agents. (1)

One motivation for automated-planning research is theoretical: planning is an important component of rational behavior--so if one objective of artificial intelligence is to grasp the computational aspects of intelligence, then certainly planning plays a critical role. Another motivation is very practical: plans are needed in many different fields of human endeavor, and in some cases it is desirable to create these plans automatically. In this regard, automated-planning research has recently achieved several notable successes such as the Mars Rovers, software to plan sheet-metal bending operations, and Bridge Baron. The Mars Rovers (see figure 1) were controlled by planning and scheduling software that was developed jointly by NASA's Jet Propulsion Laboratory and Ames Research Center (Estlin et al. 2003). Software to plan sheet-metal bending operations (Gupta et al. 1998) is bundled with Amada Corporation's sheet-metal bending machines such as the one shown in figure 2. Finally, software to plan declarer play in the game of bridge helped Bridge Baron to win the 1997 world championship of computer bridge (Smith, Nau, and Throop 1998).

The purpose of this article is to summarize the current status of automated-planning research, and some important trends and future directions. The next section includes a conceptual model for automated planning, classifies planning systems into several different types, and compares their capabilities and limitations; and the Trends section discusses directions and trends.

Conceptual Model for Planning

A conceptual model is a simple theoretical device for describing the main elements of a problem. It may fail to address several of the practical details but still can be very useful for getting a basic understanding of the problem. In this article, I'll use a conceptual model for planning that includes three primary parts (see figure 4a and 4b, which are discussed in the following sections: a state-transition system, which is a formal model of the real-world system for which we want to create plans; a controller, which performs actions that change the state of the system; and a planner, which produces the plans or policies that drive the controller.

[FIGURE 1 OMITTED]

State-Transition Systems

Formally, a state-transition system (also called a discrete-event system) is a 4-tuple [sigma] = (S, A, E, [gamma]), where

S = {[s.sub.0], [s.sub.1], [s.sub.2 ...} is a set of states;

A = {[a.sub.1], [a.sub.2] ...} is a set of actions, that is, state transitions whose occurrence is controlled by the plan executor;

E = {[e.sub.1], [e.sub.2], ...} is a set of events, that is, state transitions whose occurrence is not controlled by the plan executor;

[gamma] : S x (A u E) [right arrow] [2.sup.s] is a state-transition function.

A state-transition system may be represented by a directed graph whose nodes are the states in S (for example, see figure 5). If s' [member of] [gamma](s, e), where e [element of] A [union] E is an action or event, then the graph contains a state transition (that is, an arc) from s to s' that is labeled with the action or event e. (2)

If a is an action and [gamma] (s, a) is not empty, then action a is applicable to state s: if the plan executor executes a in state s, this will take the system to some state in [gamma] (s, a). If e is an event and [gamma] (s, e) is not empty, then e may possibly occur when the system is in state s. This event corresponds to the internal dynamics of the system, and cannot be chosen or triggered by the plan executor. Its occurrence in state s will bring the system to some state in [gamma](s, e).

Given a state-transition system [sigma], the purpose of planning is to find which actions to apply to which states in order to achieve some objective, when starting from some given situation. A plan is a structure that gives the appropriate actions. The objective can be specified in several different ways. The simplest specification consists of a goal state [s.sub.g] or a set of goal states [S.sub.g]. For example, if the objective in figure 5 is to have the container loaded onto the robot cart, then the set of goal states is [S.sub.g] = {[s.sub.4], [s.sub.5]}. In this case, the objective is achieved by any sequence of state transitions that ends at one of the goal states. More generally, the objective might be to get the system into certain states, to keep the system away from certain other states, to optimize some utility function, or to perform some collection of tasks.

[FIGURE 2 OMITTED]

Planners

The planner's input is a planning problem, which includes a description of the system [sigma], an initial situation and some objective. For example, in figure 5, a planning problem P might consist of a description of [sigma], the initial state [s.sub.0], and a single goal state [s.sub.5].

The planner's output is a plan or policy that solves the planning problem. A plan is a sequence of actions such as

.

A policy is a partial function from states into actions, such as

{([s.sub.o], take), ([s.sub.1], move1), ([s.sub.3], load), ([s.sub.4], move2)}. (3)

The aforementioned plan and policy both solve the planning problem P. Either of them, if executed starting at the initial state So, will take [sigma] through the sequence of states . (4)

In general, the planner will produce actions that are described at an abstract level. Hence it may be impossible to perform these actions without first deciding some of the details. In many planning problems, some of these details include what resources to use and what time to do the action.

What Resources to Use. Exactly what is meant by a resource depends on how the problem is specified. For example, if [sigma] contained more than one robot, then one approach would be to require the robot's name as part of the action (for example, move1 (robot) and move1 (robot2)), and another approach would be to consider the robot to be a resource whose identity will be determined later.

What Time to Do the Action. For example, in order to load the container onto the robot, we might want to start moving the crane before the robot arrives at location1, but we cannot complete the load operation until after the robot has reached location1 and has stopped moving.

[FIGURE 3 OMITTED]

In such cases, one approach is to have a separate program called a scheduler that sits in between the planner and the controller (see figure 4c), whose purpose is to determine those details. Another approach is to integrate the scheduling function directly into the planner. The latter approach can substantially increase the complexity of the planner, but on complex problems it can be much more efficient than having a separate scheduler.

Controllers

The controller's input consists of plans (or schedules, if the system includes a scheduler) and observations about the current state of the system. The controller's output consists of actions to be performed in the state-transition system.

In figure 4, notice that the controller is online....

NOTE: All illustrations and photos have been removed from this article.



More articles from AI Magazine
Report on the Third Artificial Intelligence and Interactive Digital En..., December 22, 2007
The Fourth International Conference on Informatics in Control, Automat..., December 22, 2007
Report on the Seventh International Conference on Case-Based Reasoning..., December 22, 2007
Winter calendar of AI events.(artificial intelligence)(Calendar), December 22, 2007
When robots roam the earth.(AI in the news)(Brief article), December 22, 2007

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.