Printer Friendly

There's More to Life Than Making Plans.

Plan Management in Dynamic, Multiagent Environments

Research on planning within AI has led to the development of computational techniques for generating a plan, or course of action, to achieve a specified goal from a specified initial state, given definitions of the available actions. Until recently, however, much of this research has been governed by a number of simplifying assumptions, notably the following: First, the planning agent is omniscient; it knows all the relevant facts about its environment. Second, the actions that the agent can perform have definite outcomes. Third, the goals presented to the agent are categorical; that is, they are either achieved or not, and there is no notion of partial satisfaction. Fourth, the agent is the only source of change in the environment: There are neither exogenous events nor other agents. Fifth, the goals presented to the agent remain unchanged throughout the process of planning and execution. Sixth, the actions that the agent can perform can be modeled as instantaneous state transducers: They have neither temporal extent nor fixed times of occurrence.

These assumptions have several key consequences. If they hold, there is no need to interleave planning and execution because the agent has all the knowledge it needs at planning time. Also, in such circumstances, a plan can always be executed successfully: Everything is guaranteed to go "according to plan," and replanning is thus unnecessary. Finally, because the goals are all known at the outset, and remain fixed throughout the planning and execution process, there is no notion of planning problems competing with one another for the planning agent's attention. In short, these assumptions preclude the need for active management of the planning process: There is no need to decide which planning or replanning tasks to attend to when or how much detail to include in a plan now and how much to defer until later.

Of course, most of these assumptions--which were introduced, after all, only to delimit a tractable domain for initial investigation --fail to hold in the kinds of realistic situation in which planning is called for. Consequently, a number of researchers in AI have explored techniques for extending the classical planning paradigm, relaxing some of its overly strong assumptions. Techniques now exist for generating conditional plans with branches whose performance is keyed to the outcome of sensing actions (Collins and Pryor 1995; Peot and Smith 1992), removing the need to assume omniscience (the first assumption). Representations of actions with probabilistic outcomes have been developed and used in systems that generate plans whose probability of success exceeds a given threshold (Kushmerick, Hanks, and Weld 1995; Goldman and Boddy 1994), eliminating the assumption of deterministic actions (the second assumption). These extensions have been combined in probabilistic, conditional planning systems (Onder and Pollack 1999; Blythe 1998; Draper, Hanks, and Weld 1994). The assumption of categorical goals (the third assumption) has been removed in utility-based and decision-theoretic planning systems, which can generate plans for goals with rich, time-dependent utility functions (Haddawy and Hanks 1998; Williamson and Hanks 1994). Work on modeling planning as a (fully or partially observable) Markov decision process (MDP) (Boutilier, Dean, and Hanks 1999) can be seen as aimed at simultaneously removing the first three assumptions.

Other recent work has addressed the assumption of a static environment (the fourth and fifth assumptions). One approach has been to rely on techniques for planning under uncertainty, folding exogenous changes into the predicted outcomes of actions (Blythe 1996; Hanks, Madigan, and Gavrin 1995); this approach is also used in the MDP framework. Another body of work, often called reactive planning or plan-execution systems (Firby 1996, 1994; Gat 1992; Georgeff and Ingrand 1989), addresses run-time system behavior and deals with the problem of dynamic environments by supplementing high-level plans, such as those produced by classical planners, with mechanisms for translating these plans into low-level behaviors that are responsive to changes in the world. For the most part, however, this work has concentrated on the effective execution of current activities but has not provided sufficient consideration to issues of managing future commitments. Work on deliberation scheduling (Horvitz 1997; Zilberstein and Russell 1996; Greenwald and Dean 1994; Dean and Boddy 1988) also gives up the fifth assumption and develops techniques for deciding which goals to attend to when. However, to date these techniques have had somewhat limited applicability, and they have not been applied specifically to questions of deciding how much detail to include in a plan or to management of the replanning process--although in principle, deliberation scheduling techniques could be applied to such problems if we could accurately model the costs and benefits of individual plan-expansion and replanning tasks. Finally, although there has been recent work on developing planners that reason about rich temporal constraints (Bacchus and Kabanza 1996), it has again focused primarily on the problem of generating plans for a fixed goal, to be subsequently executed in a static environment.

In sum, although the planning community has made significant progress on developing plan-generation mechanisms that do not require the strong assumptions made in earlier work, it has continued, for the most part, to focus on the problem of plan generation. Certain exceptions exist, as noted in the previous paragraph, but the majority of research done continues to focus on algorithms for more efficient plan generation. However, when the assumptions of classical planning are abandoned, it becomes important not only to rethink plan-generation algorithms but also to consider a wider range of reasoning processes that are involved in managing plans in dynamic, multiagent environments.

An Example

We can illustrate the types of reasoning required in plan management with a simple example of the kind of reasoning that humans seem to be capable of performing on a daily basis.

Suppose you have a class to teach next Monday morning, and sometime the week before, you decide to prepare your lecture for the class over the weekend. You don't yet decide exactly when you will prepare the lecture because your other weekend plans aren't fixed yet, but you are confident that you will find some time over the weekend for lecture preparation. On Friday, before you leave the office for the weekend, you decide on the general topic for the lecture, so that you can bring home the books you will need to do the lecture preparation. On Saturday morning, you decide to spend the day running errands and to go to a movie in the evening; you will prepare your lecture sometime Sunday. However, on Saturday afternoon, you receive a phone call from a friend, informing you that she has an extra ticket to the football game on Sunday afternoon. You are not sure whether you will be able to finish your lecture Sunday morning. You could attempt to finish the lecture and only use the football ticket if you are successful. However, you realize that this approach is unfair to your friend, who could find someone else with whom to go to the game if you let her know today. You therefore revise your plans and decide not to go to the movie; instead, you begin preparing your lecture Saturday evening. If you don't finish, you will still have Sunday morning to complete it, before going to the football game.

Although this scenario might appear frivolous, there are two important reasons for trying to understand the reasoning processes that support it and similar cases. The first is as an exercise in cognitive science: The ability to manage one's activities in a dynamic environment is an essential component of human cognitive capacity and, thus, worth exploring as part of the effort to understand the human mind. The second is as a prerequisite to designing better computational tools. It is generally agreed that intelligent autonomous agents would be extremely useful in applications ranging from military to industrial to educational. For many of these applications, the agents involved will need to be able to perform the kinds of plan-management reasoning illustrated in our example.

Let's consider the kinds of reasoning task that are involved. The intelligent agent--"you" in this story--must be capable of performing (at least) the following reasoning tasks:

Plan generation: You certainly need to be able to perform classic plan generation. In the story, for example, you need to recognize that a precondition for preparing the lecture at home is that you have the materials you need at home; therefore, you need to plan to bring them home with you.

Commitment management: Intuitively, at least, it seems that agents don't just generate new plans; they also commit to them. By committing to a plan P, an agent tends to rule out new options that would conflict with P. Having committed to teaching your class on Monday, you will in general rule out activities that preclude your teaching the class. However, commitment is not absolute: In the current story, you do abandon your commitment to go to the movies, in order to be able to attend the football game. Agents need to be able to reason about the relative strength of their commitments, to decide which, if any, they are willing to give up.

Environment monitoring: In a dynamic environment, many events can occur that either indicate a problem with your existing commitments or suggest a new opportunity. However, in general, you will not be able to attend to all these but must somehow focus on those that are potentially most relevant and significant. In the current story, you attend to the invitation to attend the football game, but there are plenty of other potential opportunities that you ignore (and that we've therefore left out of the story), such as the call from a telemarketer offering you a new credit card and the For Sale signs you see posted in front of neighborhood houses.

Alternative assessment: Once you determine that the environment presents a new opportunity, you need to be able to assess the costs and benefits of the options with which you are presented, and you need to do this taking account of the context in which these options will be performed. Going to the football game not only provides the benefit of enjoying the game but also incurs a cost because it requires you to skip the movie you had planned to see.

Plan elaboration: In dynamic environments, agents often have commitments to partially specified plans and can even begin executing these plans before they are complete. However, there are constraints on what must be elaborated when. By Friday afternoon, you need to have elaborated your lecture plan enough to determine which books and papers to carry home with you. On the other hand, you can defer your decision about exactly when to prepare your lecture. But once you receive the phone call about the football tickets, you need to make a firmer commitment to the lecture preparation time to ensure you can both complete the preparation and attend the game.

Metalevel control: For some activities, you will want to do a lot of careful planning, whereas for others, you might be willing to live with a less than optimal solution. For example, you might not bother to spend the time to determine the minimal-distance route that allows you to carry out all your errands.

Coordination with other agents: When environments have multiple agents in them, a wide range of issues arise involving the coordination of your own plans with those of the other agents. In our story, you decide not to adopt the wait-and-see plan of going to the movies and then starting your lecture preparation Sunday morning, going to the football game only if you've completed the preparations. This plan is unacceptable because it has a negative impact on your friend's plan to find someone with whom to attend the football game.

Reasoning tasks such as these have been the focus of our work in plan management. In the remainder of this article, we briefly describe the challenges posed by these tasks and survey some of the work we have done to date in addressing them. Our discussion will necessarily be informal and will rely on numerous examples; the reader can consult the papers we cite for technical details. We omit discussion of three of the plan-management tasks listed: (1) plan generation, about which a huge amount has already been written; (2) metalevel control, for which we refer the reader to Horvitz (1997), Zilberstein and Russell (1996), Greenwald and Dean (1994), Russell and Wefald (1991), and Dean and Boddy (1988); and (3) coordination issues, which are discussed in the article by Grosz, Hunsberger, and Kraus, also in this issue. After sketching our approach to individual reasoning processes, we address the question of integrating these approaches, by describing a plan-management system we are developing.

Commitment Management

Our earliest work on plan management was done a decade ago, in collaboration with Michael Bratman and David Israel. It addressed the significance of commitment for resource-bounded agents in dynamic environments (Pollack 1992; Bratman, Israel, and Pollack 1988). Building on earlier work by Bratman (1987), who had argued that commitment to future plans helps a resource-bounded agent frame its subsequent reasoning and thereby limit the amount of computational resources it requires, we developed an architecture later called IRMA (intelligent resource-bounded machine architecture), depicted in figure 1. The key idea in IRMA is that agents should, in general, bypass full-fledged deliberation about new options that conflict with their existing commitments, unless these options can easily be recognized as potentially special in some way. To achieve this balance between commitment to existing plans and sensitivity to particularly important new options, we postulated within IRMA a filtering mechanism with two components. The first checks the compatibility of a new option against existing plans, and the second checks whether the new option is prima facie important enough to warrant deliberation even under incompatibility.

[Figure 1 ILLUSTRATION OMITTED]

Note that an IRMA agent can sometimes behave suboptimally, that is, perform actions other than those it would have selected if it had engaged in full-fledged deliberation. It can also sometimes perform wasted reasoning, that is, engage in deliberation about a new option that results in a decision to maintain the status quo. Nonetheless, an IRMA agent can attain a better overall level of performance than an agent that attempts full-fledged deliberation about every option it faces, because the time costs associated with such deliberation would typically result in significant missed deadlines and opportunities.

Our initial implementation of an IRMA-based agent showed the feasibility of the concept, but our experimentation was limited to a simple, highly abstract domain (the TILEWORLD) (Pollack and Ringuette 1990). Similar results were found by other researchers (Kinny, Georgeff, and Hendler 1992; Kinny and Georgeff 1991). We later generalized the test-bed to include multiple agents, and we found preliminary evidence that the IRMA notion of filtering could also be a useful mechanism for facilitating agent coordination (Ephrati, Pollack, and Ur 1995), but again, our experiments were limited to an abstract domain. However, many of the ideas in IRMA are included in the dMARS systems developed at the Australian Artificial Intelligence Institute by Michael Georgeff and his colleagues (Rao and Georgeff 1995); dMARS has been used in a variety of real-world applications, ranging from space shuttle malfunction handling to air traffic control to air-combat simulation. We are also using a filtering mechanism in our plan-management agent (PMA), described later in this article. Although we have modified our view of the exact nature of filtering--we no longer view compatibility as an all-or-nothing property but instead reason about the compatibility of various layers of a hierarchical plan--we still subscribe to the view that it is important for resource-bounded agents in dynamic environments to maintain fairly stable sets of commitments, which guide and focus their subsequent reasoning and actions.

Environment Monitoring

The theory of filtering, as embodied in IRMA, suggests a way of screening out options that have already come to your attention. In fact, we believe that an agent's commitments play an even stronger role: They tend to restrict the range of options that the agent attends to in the first place. For example, when you wake up on a typical weekday morning, you already have a plan for the day--go to work, go to the gym, pick up the kids at school, and so on--and you do not spend a lot of time seriously considering conflicting alternatives, such as taking a spur-of-the-moment trip to Hawaii. It's not just that these options arise and then are filtered out; it's rather that in general the options don't even arise in the first place.

What's involved in monitoring "the right" features of the environment? As far back as the STRIPS planning system, researchers suggested that if an agent was engaged in plan-based behavior, the plan itself could provide guidance about what to monitor. Thus, triangle tables (Fikes, Hart, and Nilsson 1972), which map the existing state of the world to preconditions of steps in the plan, probably represent the earliest approach to execution monitoring. A more recent example is the SAGE system for information gathering, which also bases its decision of what to monitor on the structure of its current plans (Knoblock 1995).

In our own work (Veloso, Pollack, and Cox 1998), done jointly with Manuela Veloso and Michael Cox, we have argued that an agent should carefully monitor not only environmental features that affect the plans it holds but also features of the plans it has rejected during prior reasoning. More specifically, we view planning as a decision-making process, during which the rationale behind each decision should be recorded. Plan rationales will often include references to conditions that resulted in the rejection of an alternative plan, in favor of the one that was actually adopted.

For example, suppose that you plan to use frequent flier miles on an airplane ticket that costs $800. If an airline price war then erupts, and the price of the ticket drops substantially, say, to $200, you might prefer to change your plan and pay for the ticket, saving your frequent flier miles for a more expensive flight. Note that the change in price will not affect the success of your plan--you still could fly with the ticket you hold. However, the rationale for your original decision to use frequent flier miles was that the flight was expensive; this rationale now no longer holds. Rationale-based monitoring can thus not only prevent the failure of previous plans but can also lead to higher-quality plans.

Rationale-based monitoring is a three-stage process involving (1) generating monitors that represent environmental features that affect plan rationale; (2) deliberating, whenever a monitor fires, about whether to respond to the monitor; and (3) transforming the plan as warranted. In Veloso, Pollack, and Cox (1998), we described a preliminary implementation of this approach in the PRODIGY planning system (Veloso et al. 1995); more recently, with Colleen McCarthy, we adapted the idea to a partial-order causal-link planner (Pollack and McCarthy 1999).

However, approaches to monitoring that are based on the agents' existing plans are necessarily incomplete. Although, as we have suggested, agents do not attend to every feature of their environment, neither do they attend only to environmental features directly related to their previous planning episodes. You don't typically consider taking a trip to Hawaii every morning, even if your morning newspaper always carries advertisements for airlines, but once in a long while, you just might entertain this possibility--especially if you live in Pittsburgh, and it's early March. A theory of how this happens has not yet been formulated.

Alternative Assessment

Suppose that a new option has arisen, you have attended to it, and you have determined that it is worth deliberating about. To perform this deliberation, it is necessary for you to assess the costs and benefits of the option. Moreover, this assessment must be done taking account of the context of your existing commitments. In our running example, you needed to recognize that attending the football game requires you to give up the movie you planned to see. In this case, the context increases the cost of your new option, relative to its cost if done in isolation. However, context can also decrease the cost of a new option; for example, if some of the steps required for the new option can be merged with steps you already intend.

The theory of rational choice, as formulated in the economic and philosophical literature (Keeney and Raiffa 1993; Jeffrey 1983), provides a richly developed model of alternative assessment. In this theory, agents are seen as evaluating alternative actions by reference to a probability distribution over their possible outcomes together with a utility function defined on these outcomes; in the simplest case, the agent combines probability and utility into a notion of expected utility defined over actions and then chooses some action whose expected utility is maximal.

However, classical decision theory does not completely address certain challenges that arise in designing alternative-assessment procedures for agents in dynamic environments. We have been developing a framework that does (Horty and Pollack 1998), and it differs from classical decision theory in two important ways. First, where decision theory assumes that the utility of an outcome is given as part of the background setting, we observe that the overall desirability of an option presented to an agent is often not immediately apparent; we are explicitly concerned with the mechanism through which it might be discovered. In particular, we have so far concentrated on the case in which the option presented to the agent has a known benefit but requires some effort--the execution of a plan--for its achievement. To evaluate the overall desirability of the option, the agent thus has to arrive at some assessment of the cost involved in achieving it.

Second, we require that our theory accommodate the fact that agents have computational resource bounds. Toward this end, we cast it within the theoretical framework that models resource-bounded agents as always operating against the background of some current set of intentions, as discussed previously in the section on commitment management. In contrast to standard decision theory, where actions are evaluated in isolation, we develop a model in which the options presented to an agent are evaluated against a background context provided by the agent's current plans--commitments to future activities, which, at any given point, might themselves only be specified partially.

At the center of our approach is a specification of the cost of a new option in context, which we take simply to be its marginal cost. That is, the cost of carrying out a new plan P in the context of existing commitments C is simply the cost of carrying out both P and C less the cost of carrying out C alone: K(P/C) = K(P [union] C) - K(C), where K denotes the cost function, and P/C denotes P in the context of C.

To use this definition, we need to define the cost of a plan. We do this by assuming that primitive actions have specific costs and that the cost of a complete, fully scheduled plan is the sum of the costs of all the distinct steps in it. The requirement that we only count distinct steps is important because if an agent can merge steps of the same type, it only incurs the cost of a single such step. Consider the example depicted in figure 2. If while running your errands, you drive to the mall to buy a new shirt and, at the same time, drive to the mall to buy sneakers, you only incur the cost of one trip to the mall. In traditional plan generation, such a plan, with merged steps, would be produced as a result of step reuse. When a new plan is added to an existing context of commitments, explicit consideration of step merging becomes crucial. For further discussion of step merging, including algorithms for efficient merging, see Yang (1997). We associate the cost of an incomplete or unscheduled plan with the cost of the least expensive way in which it might be carried out; that is, the cost of an arbitrary plan P is the cost of the least expensive fully scheduled, complete plan Q such that Q is a refinement of P, where refinements are defined as in Kambhampati, Knoblock, and Yang (1995).

[Figure 2 ILLUSTRATION OMITTED]

Although we defined the notion of the cost of a plan as the least expensive method of executing it, we do not necessarily assume that a planning agent knows the true cost either of its background plan or of any new options under consideration. Instead, the agent might only have an estimate of the cost of its plans. We view estimates as intervals that bound the true cost of a plan; they are thus related to the interval measures of plan cost used in the decision-theoretic plan-generation literature (Goodwin and Simmons 1998; Haddawy, Doan, and Goodwin 1995; Williamson and Hanks 1994).

We have developed an algebra for reasoning about cost estimates; in particular, it specifies how to subtract estimates, so that an estimate of K(P/C) can be derived from estimates of K(P [union] C) and K(C), according to the previous definition. The derived interval estimate of cost in context is useful because in many cases, it allows an agent to accept or reject an option without calculating its specific cost, as illustrated in figure 3. Suppose that an agent with background plan C is considering a new option P with benefit [Beta](P). Suppose further that given its estimated costs (intervals) for C and P, it is able to derive an estimated cost interval for P/C. If the agent knows that the benefit of P is greater than the upper bound of this interval, then it is justified in adopting it because P's cost in context is necessarily less than its benefit; likewise, the agent is justified in rejecting P if its known benefit is less than the lower bound of the estimated interval of its cost in context. It is only when the benefit is inside the interval that the agent is forced to refine its estimates further before making a rational decision. We have developed anytime algorithms for this refinement step, which, again, we are using in PMA.

[Figure 3 ILLUSTRATION OMITTED]

Plan Elaboration

We have already seen that in dynamic environments, planning and execution will often be interleaved. Agents must therefore be able to decide how much detail to include in their plans now and when to add more detail. This question has largely been ignored in the AI literature, although Blythe's (1998) work is a notable exception. With Nilufer Onder, we have been investigating a restricted form of it (Onder 1999; Onder and Pollack 1999): Given that a large number of contingencies can arise during the execution of a plan in a dynamic, uncertain environment, which contingencies should be dealt with when the plan is initially formed, and which should be deferred and dealt with on an as-needed basis at execution time?

To address this question, we associate a contingency with the failure of an action in a plan to have its desired outcome. In our running example, you plan to write your lecture Saturday evening, but you recognize the possible failure of this action: You might not be able to complete the lecture on time. You therefore create a contingency plan, to complete it Sunday morning before the football game, if need be.

In general, when the agent determines that a generated plan includes an action that might fail, there are three approaches to improving it. Corrective repair involves planning a response if the failure should occur. Preventive repair involves enhancing the plan to include steps that lessen the likelihood of the failure. (In conformant planning, sufficiently many steps are added to guarantee that the plan will succeed, regardless of the action's outcome [Goldman 1996].) Replacement involves modifying the plan to remove the potentially problematic action and replace it with an alternative.

To decide which contingencies to focus on, we rely on two facts: First, contingencies in a plan can have unequal probability of occurrence, and second, a plan can have multiple goals, each of which has some associated value. It therefore makes sense to focus on those repairs that will have the greatest expected positive impact on the plan. To compute this, we first determine the value of all the goals that the agent will fail to achieve if some contingency C occurs and then weight this by the probability of C's occurrence. Subtracting this value from the optimal value of the plan gives us the expected value of the plan under the contingent failure. Next, we estimate the expected value of the plan that will result if we perform a certain type of repair. The difference between these two numbers gives us the expected value of performing the repair. We have developed algorithms for performing these computations, as well as for doing the actual process of generating contingent plans, and have also developed a number of heuristics to increase the efficiency of this process.

Of course, in reality, the importance of having contingency plans will also depend on the likely difficulty of replanning "on the fly" for particular contingencies; even if a contingency is relatively likely to occur and affect high-value goals, if it is extremely easy to correct during plan execution, it might not be necessary to plan in advance for it. This issue will be dealt with in later work.

Integration in PMA: The Plan-Management Agent

Each of the individual reasoning processes described previously is important, but it is also important to be able to integrate these processes with one another. To explore the challenge of integration, as well as to build a realistic platform on which to experiment with our ideas, we have been building PMA (Pollack, Tsarmardinos, and Horty 1999). PMA is an intelligent software system that is intended to aid a user in managing a potentially large and complex set of plans. It is thus related to two major classes of software systems: personal electronic calendar systems and workflow systems.

Commercially available electronic calendar systems, published by major software companies, essentially provide electronic interfaces to written calendars. They typically have advanced graphical user interfaces and provide links to contact databases and e-mail; some also provide capabilities for automated meeting scheduling. However, these systems suffer from a highly impoverished representation for activities: They can only model simple events and recurring simple events. Simple events are blocks of time with a single property--free or busy; a free activity is allowed overlap with other free activities, but a busy activity cannot overlap with other activities. Recurring simple events are simple events that recur at regular intervals, for example, every Tuesday from 4 to 5 PM. Labels and textual information can be attached to each event, but these are not used in any sophisticated way by the system; they are stored only for the human user's information.

Workflow systems (Nutt 1996; Georgakopoulos, Hornick, and Sheth 1995; Mahling, Craven, and Croft 1995) constitute another class of systems aimed at helping users manage their routine activities. In contrast to personal calendar systems, workflow systems use richly structured representations of activities (or processes) to ensure that information and tasks flow to the appropriate people in an organization in a timely fashion. Modern workflow systems support "document management, imaging, application launching, and/or human coordination, collaboration, and co-decision" (Georgak 1995, p. 121). To date, though, they tend to have limited capabilities for handling uncertainty, for replanning when a problem is detected, and for reasoning about the relative value of alternative ways to perform a given task. PMA is being designed to include just these sorts of reasoning capability, using the techniques discussed earlier.

PMA is a joint project of our research groups at the University of Pittsburgh and the University of Maryland and includes the efforts of Ioannis Tsamardinos and Carl Anderson. Other efforts to apply AI plan-generation and plan-execution technology to develop intelligent workflow-style systems include the IWCM Project at SRI International (Berry and Myers 1999) and the Enterprise Project at the Artificial Intelligence Applications Institute (Stader 1998; Drabble, Lydiard, and Tate 1998). Like PMA, the IWCM Project is relatively new, and comparisons between the projects are not yet possible. Although some of the capabilities of PMA overlap with that of the Enterprise Project, the approaches taken in the two efforts are quite different.

To illustrate the behavior of PMA and show how it includes the types of reasoning process already discussed, we describe a sample interaction with it. PMA has knowledge of the structured activities--the plans or procedures--that its user typically performs. For example, a PMA for use in a physician's office would know the steps involved in carrying out diagnostic procedures, preparing a patient for surgery, and handling insurance forms. The activity of preparing a patient for surgery might include, say, organizing a preliminary battery of tests, assembling and scheduling the surgical team, and booking the operating room. Many of these tasks would themselves decompose into structured activities: Carrying out a single test might involve scheduling the test, tracking the lab work, entering the results into the patient's record, and calling the patient for follow-up work if necessary.

Imagine that a physician (or nurse) specifies the goal of performing a particular diagnostic test on a patient. PMA immediately posts commitments to various tasks pertaining to that goal in an internal knowledge base. It also updates the graphical display that includes a calendar and a to-do list. In this example, the posted commitments might include scheduling the test, obtaining the necessary background information before the test date, and reminding the patient 48 hours before the test date. Once the user indicates that the test has been scheduled for a certain date--December 15, say--the temporal information associated with the related procedures will be updated accordingly; for example, a calendar entry will then appear, reminding the user to notify the patient on December 13. Furthermore, if this test is just one of a battery of tests, and the scheduled December 15 date places it too near another test with which it might interfere, PMA will notice this conflict and notify the user, suggesting an alternative schedule that avoids the conflict. It might also suggest to the user that an operating room should be scheduled now, even though the actual deadline for the reservation has not yet occurred, because there is limited flexibility in the schedule to handle the situation should the operating rooms become unavailable at the desired time.

This scenario illustrates the main capabilities that we are building into PMA:

First, the PMA user can commit to activities that have rich temporal and causal structure. She does not need to specify separate commitments to each component of the activity.

Second, the PMA user can make partial commitments. For example, she can commit to performing a particular activity without yet specifying the exact time at which it will occur, or she can specify that she wants to commit to a particular goal, without yet specifying exactly which plan she will use to achieve the goal.

Third, when the user extends her commitments (for example, by specifying a particular time or a particular plan for a goal), PMA propagates the new commitment to all affected parts of the activity. In the earlier example, when the user specifies that the test should be scheduled for December 15, a patient reminder is automatically scheduled for December 13.

Fourth, whenever the user attempts to form a new commitment, PMA performs temporal and causal reasoning to determine whether it is consistent with the user's previous commitments. If PMA determines that certain additional constraints are required to ensure consistency, it notifies the user of these additional constraints, which we call forced constraints. If PMA determines that there is a conflict between the new commitment and prior commitments, it suggests ways to resolve the conflict.

Fifth, PMA can assess the cost of executing a plan in the context of existing commitments and notify the user if the cost fails to exceed some specified threshold.

Sixth, as time passes, PMA monitors the execution of the user's activities and reminds the user when deadlines are approaching. It also reasons about the tightness of the schedule. For example, if there is little slack at some future periods, PMA might suggest taking early action.

The initial version of PMA has been implemented on a PENTIUM platform, using Allegro Common Lisp for WINDOWS. To date, we have implemented the first five capabilities just listed, using the methods discussed earlier in the article, but to date, they are only implemented for nonhierarchical plans. The extension of these capabilities to hierarchical activities, and the implementation of execution monitoring, is part of our ongoing effort. Our current knowledge base contains plans for an academic user. Figure 4 illustrates the user's view of PMA.

[Figure 4 ILLUSTRATION OMITTED]

Conclusions

As the strong assumptions of classical planning are being abandoned, the possibility of constructing powerful, autonomous agents is increasing. We have argued, however, that better planners, which can generate plans for dynamic, uncertain, multiagent environments, are not enough. There's more to life than plan generation! Autonomous agents in dynamic, multiagent environments also need to be able to manage the plans they generate. They need to determine which planning problems and opportunities to consider in the first place. They need to be able to weigh alternative incomplete plans and decide among competing alternatives. They need to be able to form incomplete plans now, adding detail later, and thus, they need to be able to decide how much detail to include now and when to add more detail. They need to be able to integrate plans with one another and to decide when to treat an existing plan as an inflexible commitment and when, instead, to consider modifications of it. They also need to be able to do all this in a way that comports with the inherent bounds on their computational resources.

We described some of the challenges inherent in these reasoning tasks and sketched some of the work we have done to address them. We also described PMA, a system we are developing to ground our theoretical work by providing us with a platform for integrating our techniques and exploring their value in a realistic problem. However, we have only scratched the surface, and a lot more work remains to be done on modeling and developing computational techniques for plan management in dynamic, multiagent environments.

Acknowledgments

We would like to thank our students who have participated in various aspects of the work described here: Colleen McCarthy, Nilufer Onder, and Ioannis Tsamardinos (University of Pittsburgh) and Carl Anderson (University of Maryland). We also thank our other collaborators on the papers cited here and our colleagues who provided feedback on several versions of this talk that were given in the last year. Our work has been supported by the Air Force Office of Scientific Research, contract F49620-98-1-0436 (Pollack), and the National Science Foundation, grants IRI-96 19579 (Pollack) and IRI-96 19562 (Horty).

References

Bacchus, F., and Kabanza, F. 1996. Planning for Temporally Extended Goals. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, 1215-1222. Menlo Park, Calif.: American Association for Artificial Intelligence.

Berry, P. M., and Myers, K. L. 1999. Adaptive Process Management: An AI Perspective, Technical Report, Artificial Intelligence Center, SRI International, Menlo Park, California.

Blythe, J. 1998. Planning under Uncertainty in Dynamic Domains. Ph.D. dissertation, Department of Computer Science, Carnegie Mellon University.

Blythe, J. 1996. Event-Based Decompositions for Reasoning about External Change in Planners. In Proceedings of the Third International Conference on AI Planning Systems, 27-34. Menlo Park, Calif.: AAAI Press.

Boutilier, C.; Dean, T.; and Hanks, S. 1999. Decision-Theoretic Planning: Structural Assumptions and Computational Leverage. Journal of Artificial Intelligence Research 11:1-94.

Bratman, M. E. 1987. Intention, Plans, and Practical Reason. Cambridge, Mass.: Harvard University Press.

Bratman, M. E.; Israel, D. J.; and Pollack, M. E. 1988. Plans and Resource-Bounded Practical Reasoning. Computational Intelligence 4(4): 349-355.

Collins, G., and Pryor, L. 1995. Planning under Uncertainty: Some Key Issues. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1567-1573. Menlo Park, Calif.: International Joint Conferences on Artificial Intelligence.

Dean, T., and Boddy, M. 1988. An Analysis of Time-Dependent Planning. In Proceedings of the Seventh National Conference on Artificial Intelligence, 49-54. Menlo Park, Calif.: American Association for Artificial Intelligence.

Drabble, B.; Lydiard, T.; and Tate, A. 1998. Workflow Support in the Air-Campaign Planning Process. Paper presented at the Workshop on Interactive and Collaborative Planning, Fourth International Conference on AI Planning Systems, 7-10 June, Pittsburgh, Pennsylvania.

Draper, D.; Hanks, S.; and Weld, D. 1994. A Probabilistic Model of Action for Least Commitment Planning with Information Gathering. In Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence, 178-186. San Francisco, Calif.: Morgan Kaufmann.

Ephrati, E.; Pollack, M. E.; and Ur, S. 1995. Deriving Multiagent Coordination through Filtering Strategies. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 679-685. Menlo Park, Calif.: International Joint Conferences on Artificial Intelligence.

Fikes, R. E.; Hart, P. E.; and Nilsson, N. J. 1972. Learning and Executing Generalized Robot Plans. Artificial Intelligence 3(4): 251-288.

Firby, R. J. 1996. Modularity Issues in Reactive Planning. In Proceedings of the Third International Conference on AI Planning Systems, 78-85. Menlo Park, Calif.: AAAI Press.

Firby, R. J. 1994. Task Networks for Controlling Continuous Processes: Issues in Reactive Planning. In Proceedings of the Second International Conference on AI Planning Systems, 49-54. Menlo Park, Calif.: AAAI Press.

Gat, E. 1992. Integrating Planning and Reacting in a Heterogeneous Asynchronous Architecture for Controlling Real-World Mobile Robots. In Proceedings of the Tenth National Conference on Artificial Intelligence, 802-815. Menlo Park, Calif.: American Association for Artificial Intelligence.

Georgakopoulos, D.; Hornick, M.; and Sheth, A. 1995. An Overview of Workflow Management: From Process Modeling to Work-Flow Autonomation Infrastructure. Distributed and Parallel Databases 3(1): 19-153.

Georgeff, M. P., and Ingrand, F. F. 1989. Decision Making in an Embedded Reasoning System. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, 972-978. Menlo Park, Calif.: International Joint Conferences on Artificial Intelligence.

Goldman, R. P., and Boddy, M. S. 1996. Expressive Planning and Explicit Knowledge. In Proceedings of the Third International Conference on AI Planning Systems, 110-117. Menlo Park, Calif.: AAAI Press.

Goldman, R., and Boddy, M. 1994. Epsilon-Safe Planning. In Proceedings of the Tenth International Conference on Uncertainty in Artificial Intelligence, 253-261. San Francisco, Calif.: Morgan Kaufmann.

Goodwin, R., and Simmons, R. 1998. Search Control of Plan Generation in Decision-Theoretic Planners. In Proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems, 94-101. Menlo Park, Calif.: AAAI Press.

Greenwald, L., and Dean, T. 1994. Solving Time-Critical Decision-Making Problems with Predictable Computational Demands. In Proceedings of the Second International Conference on AI Planning Systems, 25-30. Menlo Park, Calif.: AAAI Press.

Haddawy, P., and Hanks, S. 1998. Utility Models for Goal-Directed Decision-Theoretic Planners. Computational Intelligence 14(3): 392-429.

Haddawy, P.; Doan, A.; and Goodwin, R. 1995. Efficient Decision-Theoretic Planning: Techniques and Empirical Analysis. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, 229-236. San Francisco, Calif.: Morgan Kaufmann.

Hanks, S.; Madigan, P.; and Gavrin, J. 1995. Probabilistic Temporal Reasoning with Endogenous Change. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, 245-254. San Francisco, Calif.: Morgan Kaufmann.

Horty, J. F., and Pollack, M. E. 1998. Option Evaluation in Context. Paper presented at the Seventh Conference on Theoretical Aspects of Rationality and Knowledge, 24-28 July, Evanston, Illinois.

Horvitz, E. J. 1997. Models of Continual Computation. In Proceedings of the Fourteenth National Conference on Artificial Intelligence, 286-293. Menlo Park, California: American Association for Artificial Intelligence.

Jeffrey, R. 1983. The Logic of Decision. 2d ed. Chicago: University of Chicago Press.

Kambhampati, S.; Knoblock, C. A.; and Yang, Q. 1995. Planning as Refinement Search: A Unified Framework for Evaluating Design Trade-Offs in Partial-Order Planning. Artificial Intelligence 76(1-2):167-238.

Keeney, R. L., and Raiffa, H. 1993. Decisions with Multiple Objectives: Preferences and Value Trade-Offs. New York: Cambridge University Press.

Kinny, D. N., and Georgeff, M. P. 1991. Commitment and Effectiveness of Situated Agents. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, 82-88. Menlo Park, Calif.: International Joint Conferences on Artificial Intelligence.

Kinny, D. N.; Georgeff, M. P.; and Hendler, J. 1992. Experiments in Optimal Sensing for Situated Agents. In Proceedings of the Second Pacific Rim International Conferences on Artificial Intelligence, 1176-1182. Seoul, Korea: Korea Information Science Society.

Knoblock, C. A. 1995. Planning, Executing, Sensing, and Replanning for Information Gathering. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1686-1693. Menlo Park, Calif.: International Joint Conferences on Artificial Intelligence.

Kushmerick, N.; Hanks, S.; and Weld, D. 1995. An Algorithm for Probabilistic Planning. Artificial Intelligence 76(1-2):239-286.

Mahling, D.; Craven, N.; and Croft, W. B. 1995. From Office Automation to Intelligent Workflow Systems. IEEE Expert 10(3): 41-47.

Nutt, G. J. 1996. The Evolution toward Flexible Workflow Systems. Distributed Systems Engineering 3:276-294.

Onder, N. 1999. Contingency Selection in Plan Generation. Ph.D. dissertation, Department of Computer Science, University of Pittsburgh.

Onder, N., and Pollack, M. E. 1999. Conditional, Probabilistic Planning: A Unifying Algorithm and Effective Search-Control Mechanisms. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, 577-584. Menlo Park, Calif.: American Association for Artificial Intelligence.

Peot, M., and Smith, D. E. 1992. Conditional Nonlinear Planning. In Proceedings of the First International Conference on AI Planning Systems, 189-197. San Francisco, Calif.: Morgan Kaufmann.

Pollack, M. E. 1992. The Uses of Plans. Artificial Intelligence 57(1):43-68.

Pollack, M. E., and McCarthy, C. 1999. Toward Focused Plan Monitoring: A Technique and an Application to Mobile Robots, Paper presented at the IEEE International Symposium on Computational Intelligence in Robotics and Automation, 8-9 November, Monterey, California.

Pollack, M. E., and Ringuette, M. 1990. Introducing the TILEWORLD: Experimentally Evaluating Agent Architectures. In Proceedings of the Eighth National Conference on Artificial Intelligence, 183-189. Menlo Park, Calif.: American Association for Artificial Intelligence.

Pollack, M. E.; Tsamardinos, I.; and Horty, J. F. 1999. Adjustable Autonomy for a PlanManagement Agent. Paper presented at the AAAI Spring Symposium on Agents with Adjustable Autonomy, 22-24 March, Stanford, California.

Rao, A. S., and Georgeff, M. P. 1995. BDI Agents: From Theory to Practice. In Proceedings of the First International Conference on Multiagent Systems, 312-319. Menlo Park, Calif.: AAAI Press.

Russell, S. J., and Wefald, E. H. 1991. Do the Right Thing. Cambridge, Mass.: MIT Press.

Stader, J., and Jarvis, P. 1998. Intelligent Support for Enterprise Modeling. Technical Report AIAI-TR-220, Artificial Intelligence Applications Institute, Edinburgh, Scotland.

Veloso, M. M.; Pollack, M. E.; and Cox, M. T. 1998. Rationale-Based Monitoring for Planning in Dynamic Environments. In Proceedings of the Fourth International Conference on AI Planning Systems, 171-179. Menlo Park, Calif.: AAAI Press.

Veloso, M. M.; Carbonell, J.; Perez, M. A.; Borrajo, D.; Fink, E.; and Blythe, J. 1995. Integrating Planning and Learning: The PRODIGY Architecture. Journal of Experimental and Theoretical Artificial Intelligence 7(1): 81-120.

Williamson, M., and Hanks, S. 1994. Optimal Planning with a Goal-Directed Utility Model. In Proceedings of the Second International Conference on Artificial Intelligence Planning Systems, 176-181. Menlo Park, Calif.: AAAI Press.

Yang, Q. 1997. Intelligent Planning: A Decomposition- and Abstraction-Based Approach. New York: Springer-Verlag.

Zilberstein, S., and Russell, S. 1996. Optimal Composition of Real-Time Systems. Artificial Intelligence 83(1-2): 181-213.

Martha E. Pollack is professor of computer science and professor and director of the Intelligent Systems Program at the University of Pittsburgh. She was previously a senior computer scientist at the AI Center at SRI International, having received her Ph.D. from the University of Pennsylvania. Her primary research interests are in planning, intelligent workflow and plan management, agent architectures, and computational models of rationality. She is a fellow of the American Association for Artificial Intelligence and a past recipient of the Computers and Thought Award. Her e-mail address is pollack@cs.pitt.edu.

John F. Horty is a professor in the Philosophy Department and the Institute for Advanced Computer Studies at the University of Maryland. He received his Ph.D. in philosophy from the University of Pittsburgh and has worked in a number of areas of philosophical logic and AI, including nonmonotonic reasoning, deontic logic, the logic of action, decision theory, and the foundations of planning and practical reasoning. His e-mail address is horty@umiacs.umd.edu.
COPYRIGHT 1999 American Association for Artificial Intelligence
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1999 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Pollack, Martha E.; Horty, John F.
Publication:AI Magazine
Geographic Code:1USA
Date:Dec 22, 1999
Words:8052
Previous Article:The Benefits of Arguing in a Team.
Next Article:A Survey of Research in Distributed, Continual Planning.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters