Modeling Planning as an Incremental, Opportunistic Process

1 . THE ERRAND-PLANNING TASK

We have focused our initial efforts on an errand-planning task. The planner begins with a list of desired errands and a map of a town in which she or he must perform the errands . The errands differ implicitly in importance and the amount of time required to perform them. The planner also has prescribed starting and finishing times and locations. Ordinarily, the available time does not permit performance of all of the errands. Given these requirements, the planner decides which errands to perform, how much time to allocate for each errand, in what order to perform the errands, and by what

routes to travel between successive errands.

* The work reported here was supported by Contract No . N00014-78-C-0039 from the office of the Director of Personnel and Training Research Programs, Psychol~gical Sciences Division, Office of Naval Research . Perry Thorndyke and Doris McClure made valuable contributions to the research reported.

In performing this task, the planner makes many decisions. These decisions exploit different kinds of knowledge and address different aspects of the planned activity. The following examples illustrate the variability in decisions a planner might make:

1. I'll go to the drug store after the bank.
2. I'm going to do all of the errands in the northeast corner of town and then the
3. errands in the southeast corner.
4. The dentist is more important than the
5. hardware store.
6. 4 . The drugstore, the dentist, and the bank are all in the same general area.
7. I'm going to try to find an errand that is on my route to the northeast corner of town.
8. 6 . I'm going to see where the errands are on the map.
9. I'm going to avoid backtracking .
10. First I'd better decide which errands are
11. the most important ones.

Planners can also vary considerably in the order in which they make these decisions. For example, a planner might begin by making very abstract decisions about the gross features of the plan (e.g., decision 2 above) and use these decisions to guide subsequent decisions about the details of the plan (e.g., decision 1 above). Alternatively, the planner might begin by making decisions about certain details of the plan before deciding upon any particular gross organization for the plan. Similarly, the planner might decide upon intended actions in the order in which she or he plans to perform them. Alternatively, the planner might decide upon intended actions in some other order.

In order to accommodate the different kinds of decisions, the different kinds of knowledge they reflect, and differences in the order in which planners make them, we built our model around the following features of the Hearsay-11 system: (a) multiple cooperating knowledge sources (referred to below as specialists); (b) incremental, opportunistic problem-solving behavior; (c) structured communication among knowledge sources via a blackboard; and (d) an intelligent scheduler to control knowledge source activity.

2. THE PLANNING MODEL

In our model, the planning process comprises the independent and asynchronous operation of many distinct specialists (knowledge sources). Each specialist makes tentative decisions for incorporation into a tentative plan. All specialists record their decisions in a common data structure, called the blackboard . They also establish linkages on the blackboard to reflect causal or logical relationships among various decisions . The blackboard enables the specialists to interact and communicate. Each specialist can retrieve decisions of interest from the blackboard regardless of which specialists recorded them. A special i st can combine earlier decisions with its own decisionmaking heuristics to generate new decisions .

We partition the blackboard into five pl anes containing conceptually different categories of decisions . Each plane contains several levels of abstraction of the planning space . Mos t specialists deal with information that occurs at only a few levels of particular planes . Fig. 1 shows the five planes of the blackboard and their constituent levels of abstraction . It also shows the activities of several illustrative specialists. We discuss these below.

Meta-plan decisions indicate what the planne r intends to do during the planning process .

This plane has four levels. Beginning at the top, the problem definition describes the planner's conception of the task . It includes descriptions of the goal, available resources, possible actions, and constraints . In the errand-planning task, for example, the problem definition would include the list of errands, contextual information, and associated instructions. The problem-solving model indicates how the planner intends to represent the problem symbolically and generate potential solutions. For example, the planner might view the errand-planning task as an instance of the familiar traveling salesman problem [2), searching for the most efficient route among the errands. Alternatively, the planner might view the task as a scheduling problem, deciding which errands to perform before deciding when to perform them . Policies specify general criteria the planner wishes to impose on his problem solution. For example, the planner might decide that the plan must be efficient or that it should m1n1m1ze certain risks. Solution evaluation criteria indicate how the planner intends to evaluate prospective plans . For example, the planner might decide to speculate on what could go wrong during execution and ensure that the plan is robust over those contingencies.

Plan decisions indicate actions the planner actually intends to take in the world . Decisions at the four levels form a potential hierarchy, with decisions at each level specifying a more refined plan than those at the next higher level. Beginning at the most abstract level, outcomes indicate what the planner intends to-accomplish by executing the finished plan . In the · errand-planning task, for example, outcomes indicate what errands the planner intends to accomplish by executing the plan . Designs characterize the general approach by which the planner intends to achieve the outcomes . For the errand-planning task, designs characterize the general route the planner intends to take to accomplish the intended errands. Procedures specify specific sequences of actions. For the errand-planning task, procedures specify sequences of errands . Operations specify sequences of more specific actions. In the errdnd-planning task, operations specify the route by which the planner will proceed from one errand to the

next.

In addition to the levels of abstraction, the plan plane has a second dimension corresponding to the time period spanned by proposed decisions . · It al so permits representation of competi ng alternative decisions and

simultaneous and event-contingent decisions.

Plan-abstraction decisions characterize desired attributes of potential plans. These abstract decisions serve as heuristic aids to the planning process suggesting potentially useful qualities of planned actions . Each level of the plan-abstraction plane characterizes types of decisions suggested for incorporation into the corresponding level of the plan plane. For example, the planner might indicate an intention to do all of the critical errands. This intention could stimulate efforts to partition the errands into critical and non­ critical sets . At a lower level, the planner might generate a scheme to fabricate a design employing gross spatial clusters of errands. This scheme might motivate a search for coherent clusters. At the next level, the planner might develop a strategy suggesting that errands in the current cluster be completed before moving on to errands in another cluster. This strategy would presumably constrain procedural sequences eventually incorporated into the plan. Finally, the planner might adopt a tactic that suggested searching for a short-cut between one errand and the next. This tactic might lead to the discovery and use of one particular short­

cut.

The knowledge base records observations and computations about relationships in the world which the planner generates while planning. This knowledge supports two types of planning functions: situation assessment, the analysis of the current state of affairs; and plan evaluation, the analysis of the likely consequences of hypothesized actions. Again, the levels of the knowledge base form a hierarchy and correspond to the levels of the plan and plan-abstraction planes . Each level of the knowledge base contains observations and computations useful in instantiating decisions at the corresponding level of the plan­ abstraction plane or generating decisions at the corresponding level of the plan plane. Thus, the levels of the knowledge base are problem-specific. At the errand level, for example, the planner might compute the time required to perform all of the currently intended errands to evaluate the plan's gross feasibility . At the layout level, the planner might observe that several errands form a convenient spa~ial cluster and, as a consequence, formulate a design organized around clusters. At the neighbor level, the planner might observe that two planned errands are near one another and, as a consequence, adopt a procedural decision to sequence those two errands. At the route level, she or he might detect a previously unnoticed short-cut

and then exploit it in an operation-level decision to establish a route between two planned errands.

Before describing the executive plane of the planning blackboard, we must discuss planning specialists. Specialists generate tentative decisions for incorporation into the plan in progress. Decisions become final only after the planner has accepted an overall plan. This ordinarily requires that she or he has formulated a complete plan and determined that it satisfies solution evaluation criteria recorded on the meta-plan plane.

Most specialists work with decisions at only two levels of the blackboard. One level contains decisions (previously generated by other specialists) that stimulate the specialist's behavior. The other is the level at which the specialist records its own modifications to the blackboard. The circle and arrow ends of the arc associated with each specialist in Fig. 1 indicate these two levels, respectively. For example, the strategist (on the plan-abstraction plane) responds to prior scheme decisions by generating strategies useful in implementing those schemes. Suppose, for example, one specialist had generated a scheme to travel around among spatial clusters of errands, doing the errands in one cluster before moving on to the next. The strategist would generate a strategy for sequencing individual errands according to this scheme. One such strategy would be to perform all pending errands in the current cluster before performing errands in any other cluster.

Note that the arcs in Fig. 1 indicate that both bottom-up and top-down processing occur and that the two levels indicated by an arc need not be adjacent or even on the same plane of the planning blackboard.

We operationalize specialists as pattern­ directed condition-action modules [15). The condition component of a specialist characterizes decisions whose occurrences on the blackboard warrant a response by the specialist. The occurrence of any of these decisions invokes the specialist. For example, the occurrence of a new scheme on the plan­ abstraction plane invokes the strategist. The action of a specialist module defines its behavior. For example, the strategist generates strategies for implementing schemes. In addition to recording new decisions, each specialist records relational linkages among the decisions with which it deals. For example, the strategist records support linkages connecting the scheme decision that invokes it to the strategies generated for implementing that scheme.

We have selected the specialists shown in Fig. 1 for illustrative purposes. The mnemonic names of the specialists and the preceding discussion of levels make most of the specialists self-explanatory, so we will not discuss them in detail here [but see 6 for elaboration].

During planning, each of the independent specialists monitors the blackboard for the occurrences of decisions specified in its condition. Invoked specialists queue up for execution, and an executive decides which will execute its action.

We have formalized executive decisions as the fifth plane of the blac~board . Decisions made at the three levels on this plane form a hierarchy, with decisions at each level potentially refining ones at the level above. Starting at the top, £!iority decisions indicate preferences for allocating processing activity to certain areas of the planning blackboard before others. For example, given a traveling salesman model, the planner might decide to determine what errand sequences he could do conveniently, rather than deciding what errands he ought to do. Focus decisions indicate what kind of decision to make at a specific point in time, given the current priorities. For example, the planner might decide to focus attention on generating an operation-level refinement of a previously generated procedure. Finally, schedule decisions indicate which of the currently invoked specialists, satisfying most of the higher-level executive decisions, to execute. If, for example, given current priorities and focus decisions, both the architect and the pattern recognizer had been invoked, the planner might decide to execute the pattern recognizer first.

Like the other planes of the planning blackboard, the executive plane includes decisions motivated by prior decisions on the same or other blackboards . For example, middle management responds to policies on the meta­ plan plane by generating appropriate priorities on the executive plane. The referee uses focus decisions in deciding which of the currently invoked specialists to schedule. The executive plane differs from the other four planes of the planning blackboard because decisions recorded there do not motivate decisions recorded on other blackboards. Instead, they determine which invoked specialists can execute their actions on their designated planes of the blackboard.

Under the control of the executive, the planning process proceeds through successive invocation and execution of the various operational specialists. The process continues until the planner has decided that the existing plan satisfies the evaluation criteria recorded on the meta-plan plane of the blackboard .

3. IMPLEMENTATION OF THE PLANNING MODEL

We have implemented a simulation of the planning model in INTERLISP. We describe the data structures, specialists, and control structure for the simulation below. We then note the main differences between the present implementation and Hearsay-!! and assess the current performance of the simulation.

Data Structures. The simulation has four global data structures: the map, the blackboard, the agenda, and the event list .

The map is an internal representation of the map our human subjects use in performing the errand-planning task. It is a two-dimensional grid, with 38 cells and 30 cells on the east­ west and north-south dimensions, respectively. Each cell contains a number indicating the object it represents. For example, all cells representing a particular street, store, park, or intersection have the same number . Thus, the system refers to an object on the map as the area covered by the corresponding number.

The blackboard contains all decisions generated during the planning process. Each decision appears as a node, residing at a particular level of abstraction on a particular plane of the blackboard (see above discussion). In addition, each node holds an arbitrary number of attribute-value pairs. Different nodes may have different attributes. However, all nodes have the TAG attribute which serves as a type designation. Once a node appears on the blackboard, its attributes may change, but it never disappears.

The following node might appear procedure level of the plan plane: at the .

This node represents a decision to create a procedure thread (an ordered sequence of errands) in which errand y follows errand x. It further specifies that this errand sequence will occur last in the plan.

The agenda contains all currently invoked specialists and complete descriptions of the nodes that triggered them. This information is used in scheduling specialists, as discussed below.

The event list provides a history of all blackboard activities. It maintains a complete description of each node creation or modification, in the order in which these changes to the blackboard occurred. We currently use the event list for tracing and debugging.

Specialists. Specialists add new nodes to the blackboard or modify the attributes of existing nodes. Each specialist has a two-part condition component and an action component, as discussed below.

The condition component of a specialist determines whether it gets invoked. It has two parts, a trigger and a test. Both are predicates which get applied to various nodes on the blackboard. They differ in complexity and time of application. A specialist gets invoked only after both its trigger and test have been satisfied.

The trigger provides a preliminary test of the specialist's relevance. Ordinarily it requires only that the focus node (the most recently added or modified node on the blackboard) reside at a particular level of the blackboard and that it have a particular TAG. The system tests all specialists' triggers for each new focus node. It adds to the agenda each specialist whose trigger has been satisfied.

The test specifies all additional prerequisites for the applicability of the specialist. It may require that the focus node have particular attributes or particular values of attributes. It may require the existence of a specific configuration of decisions on the blackboard. The system performs tests only for specialists on the agenda.

The action component of a specialist defines the modification it makes to the blackboard when executed. The actions of most specialists produce new nodes with particular attributes at particular levels of the blackboard. A few simply modify attributes of existing nodes.

The cluster recognizer illustrates the specialists in our simulation. It notices clusters of errands in the same geographic neighborhood. The trigger for the cluster recognizer requires that a node whose TAG is "location" should appear at the neighbors level of the knowledge base . Such a node indicates that the simulation has located a particular errand on the map. The cluster recognizer is relevant in this context. The test requires that two other nodes whose TAGs are "location" should also appear at the neighbors level of the knowledge base. It also requires that all three nodes have a common value (NE, NW, SE, or SW) of the attribute REGION. Satisfying both the trigger and the test of the cluster recognizer indicates that three errands are in the same neighborhood--i .e., a cluster exists . The cluster detector's action records a new node whose TAG is "cluster" at the layout level of the knowledge base . It also records MEMBERS and REGION attributes whose values are the names of the errands in the cluster and the region of the cluster, respectively.

Control Structure. Like Hearsay-11, our simulation is event-driven. On each cycle, the current focus node triggers some number of specialists, which the system adds to the agenda. At this point, the agenda contains relevant specialists whose actions the system might be able to execute. The system processes these pending specialists in three phases :

invocation, scheduling, and execution.

During the invocation phase, the system evaluates the test of all specialists on the agenda. Specialists whose tests have been satisfied are invoked. If there are no invoked specialists, the simulation terminates. If there is exactly one invoked specialist, the system executes that specialist's action. In general, however, there will be several invoked specialists and the system will have to

schedule these specialists for execution.

During the scheduling phase, the system recommends one of the invoked specialists for immediate execution. It currently bases this recommendation on two considerations: recency of invocation and the current focus decision . Other things being equal, the system will recommend a recently invoked specialist in favor of one invoked earlier in the planning process. Similarly, the system will recommend a specialist whose action would occur in an area of the blackboard currently in focus, in favor of one whose action would occur elsewhere. (Recall that decisions at the focus level of the executive plane designate areas of the blackboard as in focus . ) If more than one specialist satisfies either of these criteria, the system chooses one of them at random. (The other specialists remain on the agenda fo r possible scheduling and execution on subsequent cycles.)

During the execution phase, the system executes the action of the scheduled specialist, adding a new node or modifying an existing node on the blackboard. The system immediately evaluates the trigger of each specialist against the new focus node and adds those specialists whose triggers are satisfied to the agenda. At this point, the agenda contains all of the newly triggered specialists along with any previously triggered but unexecuted specialists. Then the next cycle begins with the invocation phase, and so forth.

Major Departures from the Hearsay-!! Framework. Our simulation differs from Hearsay-11 in several ways. Obviously, the planning model embodies different specialists (knowledge sources) and different blackboard pa r titions. Our specialists are much more molecular than the Hearsay-11 knowledge sources. While Hearsay-11 comprised about ten very powerful knowledge sources, our model will eventually comprise about fifty much simpler special i sts . In addition, we have enumerated a much larger number of levels for the planning blackboard than Hearsay-11 used for speech understanding, and we have found it useful to group these levels in conceptual planes [see also 3) . The proposed model's most important departure from the Hearsay-11 framework lies in its elaboration of executive decisionmaking . The model treats executive decis i onmaki ng as i t treats other kinds of decisionmaking wi thin the planning process. Thus, it permits a potent i al hierarchy of executive decisions, each recorded by an independent specialist [see also 6 and 11).

Performance of the Simulation. Our ma in purpose in creating this simulation is to test the sufficiency of the planning model as a psychological theory. Toward this end, we wish to use the simulation to replicate a thinking aloud protocol [10) produced by a typical subject while performing the errand-planni ng task. In its current form (with about thirty specialists), the simulation can produce the exact sequence of decisions i n the fir s t hal f of a 2000-word protocol. We expect to be able to replicate the complete protocol with the addition of about twenty more specialists to our operational set. We will then attempt to replicate other protocols produced by other subjects for other versions of the errand­ planning task .

We also want an experimental environment for evaluating different planning strategies. Accordingly, the simulation permits the user to override the executive and directly control the scheduling of invoked knowledge sources for execution. Thus, while the simulation can reproduce the exact sequence of decisions in the protocol, it can also produce other sensible decision sequences. We intend to evaluate the differences in decision sequences and resulting plans under alternative executive decisions.

4. PSYCHOLOGICAL SUPPORT FOR THE PLANNING HODEL

We have collected a variety of data which suggest that the proposed model provides a reasonable description of human planning. We summarize these data below.

General Features of Planning Behavior. We have collected thirty thinking-aloud protocols from subjects performing the errand-planning task. These protocols exhibit statements from each of the levels of abstraction of each of the five planes of the blackboard. In addition, these protocols exhibit decision sequences which do not conform to any obvious systematic pattern. Instead, the decision sequences appear fairly opportunistic--each decision is motivated by one or two immediately preceding decisions, rather than by some high-level executive program. Thus, the general features of these protocols confirm the basic assumptions of the model [see 5 for additional evidence].

Details of Planning Behavior. As discussed above, our simulation can replicate the thinking aloud protocol of one of our subjects. The protocol we chose to replicate is one of the most complex of the thirty we collected. It includes decisions at each level of abstraction on each of the five planes of the blackboard. It includes instances of both top-down and bottom-up decision sequences. It includes a considerable amount of opportunism. The ability of the simulation to replicate this protocol demonstrates the sufficiency of the model to .account for these features of planning behavior as well as for the other more general

features .

Leve ls of Abstraction . The model assumes that people !make decisions at different levels of abstraction and that the levels of abstraction have functional significance in the planning process . This assumption implies that theoretically naive subjects should recognize that various decisions made during planning represent particular levels of abstraction. In order to test this hypothesis, we drew statements from the thinking-aloud protocols described above and presented them in a random order to a second group of subjects. We asked them to group statements that communicated similar kinds of information. These subjects reliably grouped the statements to correspond to the postulated levels of abstraction.

Multi-Directional Processing. The model assumes that decisions at a given level of abstraction can influence subsequent decisions at either higher or lower levels of abstraction. We tested this assumption by effectively placing subjects in the middle of the planning process and examining their choices of subsequent decisions. We gave subjects errand-planning problems, required them to make particular prior decisions and asked them to choose one of two alternative subsequent decisions. By carefully specifying required prior decisions, we could predict which subsequent decision a subject would choose. The manipulation had comparable effects on subjects' choices regardless of whether the subsequent decisions were at higher or lower levels of abstraction than the prior

decisions .

Alternative Executive Decisions. The model assumes that subjects can make different executive decisions and that these decisions determine the order in which other kinds of decisions nrcur. For example, subjects can treat the errand-planning task as a scheduling problem or a traveling salesman problem. The former constitutes a roughly top-down approach to the task, while the latter constitutes a roughly bottom-up approach. In addition to the differences in decision order, these different approaches should introduce differences in the plans subjects form. The traveling salesman approach should produce plans for performing all of the desired errands. The scheduling approach should reduce the number of planned errands, preserving only the most important

errands.

We have been able to induce subjects to take these alternative approaches to the errand­ planning task with three different methods. In one experiment, we gave subjects explicit instructions to use one or the other approach. Host subjects followed the instructions successfully and produced plans with the expected characteristics. In another experiment we instructed subjects to adopt one or the other approach on several priming tasks and then gave them a transfer task with no instructions. In this situation, most subjects adopted the approach they used on the priming tasks. In a third experiment, we instructed subjects to use each approach on some of the priming tasks and then gave them various transfer tasks with no instructions. Most of these subjects adopted the traveling salesman approach on the transfer task. However, some subjects discriminated transfer tasks for which the scheduling approach was more appropriate (tasks with time limitations) and adopted it instead.

5. CONCLUSIONS

As discussed above, our primary goal is to develop a computationally feasible and psychologically reasonable model of planning. We believe that the current performance of our simulation and the empirical results reported above provide good support for the proposed model. Our future work will focus on experiments with the simulation to evaluate its generality over specific planning tasks and planning strategies. We will also conduct additional psychological experiments to evaluate predictions derived from the

simulation.

Our success in modeling planning also attests to the utility of the Hearsay-!! framework as a general model of cognition. Several researchers have adapted the Hearsay-!! framework to a variety of tasks, including image understanding [12), reading comprehension [13), protein-crystallographic analysis [11], add inductive inference [14]. Note, however, that all of these tasks are interpretation problems: problems which present the individual (or computer system) with the lowest level representation of the problem content (e.g., the speech signal) and require interpretation of the highest level representation (e.g., the meaning). Our application of the Hearsay-!! framework to planning takes it into a qualitatively different task domain--generation problems: problems which present the highest level representation (e.g., the goal) and require generation of the lowest level representation (e.g., the sequence of intended actions).

Interpretation and generation problems differ in important ways. For example, interpretation problems lend themselves well to initial bottom-up strategies, while generation problems lend themselves well to initial top-down strategies. Interpretation problems generally permit only one (or a small number) of solutions, while generation problems permit an arbitrary number of different solutions. Further, interpretation problems typically have correct solutions, while the correctness of solutions to generation problems varies under different evaluation criteria . Despite these differences, the Hearsay-!! framework appears robust enough to guide solution of both interpretation and generation problems.