Controlling for Unexpected Goals when Planning in a Mixed-Initiative Setting

Michael T. Cox
Manuela M. Veloso

Computer Science Department
Carnegie Mellon University
Pittsburgh, PA 15213-3891

{mcox;mmv}@cs.cmu.edu

Abstract
In a mixed-initiative setting where both human and machine are intimately involved in the planning process, a number of challenges exist for traditional planning frameworks. In this paper we will examine the types of unexpected goals that may be given to the underlying planning system and thereby how humans change the way planning must be performed. Users may want to achieve goals in terms of actions as well as states, they may specify goals that vary along a dimension of abstraction and specificity, and they may mix both top-level goals and subgoals when describing what they want a plan to do. We show how the Prodigy planning system has met these challenges when integrated with a force deployment tool called ForMAT and describe what opportunities this poses for a generative planning framework.

THIS IS AN OLDER DRAFT. FOR LATEST COPY SEE

Postscript Version

Introduction

The objective of mixed-initiative planning is to fully engage the user in automated planning processes. In successful mixed-initiative settings, joint cooperation has the potential of achieving better plans than either the human or machine can create alone (Ferguson, Allen, & Miller, 1996). Yet producing harmony after throwing humans into the loop adds many unexpected challenges for current technologies. Incorporation of the user into an existing automated planner is not accomplished by simply presenting to the user an option of making any decision the system would otherwise make itself because some decisions a machine might consider may not be appropriate for or understandable to a human user. For instance, the formalism of operator postconditions and preconditions may not be natural to the user and the relationship of these conditions to goals and subgoals may not be obvious. So it is not realistic to assume that the user will either be familiar with the planning formalisms or willing to learn them. Moreover, the planning system may actually be embedded as an unobtrusive subcomponent of a larger system whose task is only obliquely relevant to planning, so the user's awareness of the planning facility may be marginal. Therefore, a user view must be presented that abstracts the details of the underlying planner. The focus should be upon what the user sees (the interface) and what the user does (the task). But given such user-centered objectives, the user will inevitably violate the implicit assumptions and expectations of the planner. To compensate, the planner will have to be smarter and more robust.

Simply obtaining input from the user can prove to be a challenge. Normally the goals given to a planning system by a knowledgeable and sympathetic user are in a well-structured format. But goals provided by an unrestrained user present at least three problems to traditional planning systems: (1) input goals may actually be specified as actions rather than states; (2) they may be abstract rather than grounded; and (3) they may include subgoals along with top-level goals. This paper will describe the control exerted by the planner to manage such problems. The second section will introduce the mixed-initiative planning system from which we extrapolate our experience. The subsequent sections describe the three problems encountered and our solutions. The paper concludes with a brief discussion.

Prodigy/Analogy -- ForMAT Integration

ForMAT (Mulvehill, 1996; Mulvehill & Christey, 1995) is a case-based tool for human users. It supports military deployment planning through the acquisition of user-built deployment cases (plans), query-driven browsing of past plans, and a rich variety of functional analysis primitives for evaluating new plans. However, human performance in the task of creating force deployment plans varies as a function of the military experience of the user. This variance appears to be due to ForMAT's lack of automated support for adapting similar past plans in the context of new planning problems. The more experienced user can accomplish the adaptation task manually, whereas the novice cannot as easily. A technology integration experiment was established between ForMAT and Prodigy/Analogy (Veloso et al., 1995; Veloso, 1994) in order to explore mixed-initiative plan development and adaptation support for force deployment users (see Veloso, Mulvehill, & Cox, 1996, for details).

Prodigy/Analogy is a fully-automated planner that combines generative and case-based planning. Based on defined planning actions (operators), it creates plans, interprets and stores planning episodes, and retrieves and reuses multiple past plans that are found similar to new problems. Stored plans are annotated with plan rationale, and reuse involves adaptation driven by the plan rationale. Research to integrate Prodigy/Analogy and ForMAT has investigated sophisticated methods for providing plan modification guidance to the ForMAT user. Guidance from Prodigy suggests to the user how to modify the elements of a past plan to fit the current situation. The sequence of events is as follows.

A ForMAT user receives the description of a new mission. Selecting attributes from the mission description to serve as probes into memory, the user queries ForMAT's database of past plans in search of relevant exemplars with which to build a plan. While browsing, the user refines the mission statement in terms of specific objectives (i.e., goals to be achieved) utilizing a domain-specific goal language. Using past plans as a template, the user edits the old case, substituting new features and values for old, deleting irrelevant old plan steps, and adding necessary new ones. As plan construction proceeds, the user can perform consistency checks on specific aspects of the plan to ensure plan integrity. During these actions, ForMAT sends messages to Prodigy/Analogy, capturing the history of the user actions.

When the mission goals are entered by the user, ForMAT reports this information to Prodigy/Analogy. Given the mission goals, Prodigy retrieves similar past solutions from its own database of plans (a mirror of the ForMAT database in a state-space representation) or creates a new plan generatively given an empty retrieval. It then identifies useful modifications for the past plans as a function of the new and past missions' rationale. Suggestions are sent to the ForMAT user that specify relevant past plans, additional retrieval probes, and potential modifications that the user should perform when building the plan.

Goal Specification

One of the obstacles to integrating ForMAT and Prodigy was that ForMAT's user goals were implicit in textual mission statements provided by commanders. State-space planners, such as Prodigy however, need well-defined goals and an initial state description from which to create plans. The goals describe the desired world in an unambiguous manner, specifying the states of the world that must be true after an agent executes the steps of the plan starting with those conditions present in the initial state. Plan creation is accomplished by some combination of forward chaining from the initial state and/or backward chaining from the goal state using operators and inference rules present in the domain theory. To provide Prodigy with goal input we required that ForMAT be modified to explicitly represent the user goals and that these goals be passed to Prodigy. In response, a goal editor was added to ForMAT. Nonetheless, unrestrained users will still specify goals in surprising ways.

A ForMAT user is given a planning problem in the form of a commander's mission statement. This statement is a description of a military objective along with guidance towards its achievement.

Need a Hawk unit and the 21st Division Ready Brigade to send to Korea to secure an airport. Also want to provide security police to keep the airbase secure so that a squadron of A-10As can be forward deployed there.

The ForMAT user represents these statements in the system's goal editor. The goals specify the military planning objectives and may or may not bear close resemblance to the kind of goals Prodigy expects. When the user saves the goals from the editor, the goals are automatically sent to Prodigy in the representation shown by Figure 1.

  (:GOALS
     (g-146 :SEND-SECURITY-POLICE 
		(GEOGRAPHIC-LOCATION KOREA))   )
     (g-145 :SEND-BRIGADE 
	(	(FORCE 21ST-DIVISIONREADYBRIGADE) 
		(GEOGRAPHIC-LOCATION KOREA))   )
     (g-144 :SEND-HAWK 
	(	(FORCE HAWK-BATTALION) 
		(GEOGRAPHIC-LOCATION KOREA))   )
     (g-143 :DEPLOY-A10A 
	(	(GEOGRAPHIC-LOCATION KOREA) 
		(AIRCRAFT-TYPE A-10A)) )   )

Figure 1. ForMAT output to Prodigy

For a generative planner, this input presents a number of problems. First, the goals are represented as actions to accomplish, rather than as states to achieve. For example, the input includes goals to send units to Korea, rather than to achieve the state of such units' locations being in Korea. Second, some goals pertain to particular unit instances (e.g., the 21st Division Ready Brigade); whereas, others pertain to unspecified units of a particular combat type (e.g., a Hawk anti-aircraft unit). Third, both top-level goals and subgoals are sent simultaneously without discretion. In Figure 1, deploying the squadron of A-10A aircraft is the top most goal, while all other goals are in support of this objective. The underlying subgoal structure to a resulting plan in Prodigy is partially shown in Figure 2.

Figure 2. Prodigy goal tree

Goals as Actions

Initially, the impulse was to convince military planners that goals should be represented as desired states of the world, and attempted to provide examples. We claimed that ``to send'' was an action corresponding to a planning operator that resulted in effects on the world. An operator effect constituted a proper goal. It became apparent, however, that such change would be resisted by users accustomed to thinking in terms of actions and that insisting on such changes might jeopardize the willingness of users to use the system. So the solution was to bypass such a conflict altogether and to build a preprocessor instead that made the transformation to a state representation automatically and in the background.

The preprocessor simply parses each ForMAT goal and obtains the corresponding Prodigy operator from a table. The primary effect of such operators then become the translated goal. To some extent, this solution finesses the more general problem of understanding user intent and desire (Pollack, 1990). For example, the translation heuristic assumes that the user does not wish the action to be accomplished due to a side-effect the operator can produce. However, for the purposes of the integration experiment and within the limited domain for which it is used, this solution proves sufficient.

A larger open question exists as to whether humans plan better in terms of actions or states (cf., McDermott, 1978). Some hierarchical planners support task level specification of goals. See, for example, Wilkins & Desimone (1994) for an application of hierarchical planning in a mixed-initiative setting for military operations planning. Nevertheless, in the military domain, the key notion of objective is important in high level planning, and this concept is often cast in terms of state. In either case, an automated planning component should allow humans to express goals in natural and familiar terms consistent with their language of manual planning.

Goal and Operator Hierarchies

In a traditional state-space planner, goals are represented as literals that have a predicate and an arbitrary number of arguments. Thus goal g-145 from Figure 1 can be represented as the literal (is-deployed 21st-DivisionReadyBrigade Korea). However, the FORCE argument of g-144 is a type identifier rather than an instance. In the Prodigy system, this is easily represented by specifying an existentially quantified goal such as (exists ((<hwk> hawk-battalion)) (is-deployed <hwk> Korea)). The goal is solved if some unit that is an element of the class hawk-battalion is deployed in Korea.

However given a hierarchy of types, a difficulty is that different operators may apply to goals up and down the abstraction hierarchy. For instance, the operator SECURE-AIRPORT is used to make secure a specific airport (see Figure 3); whereas a more general SECURE operator is used to make secure objects such as hills for which no specialized operators exist. The difference between the two is that the second operator does not have an <air-defense> variable (nor the precondition associated with it) and the variable <obj> is of type OBJECT, rather than a more specific type AIRPORT (and thus the effect and preconditions are more abstract).[1] The first operator can be used to achieve (secure-at Korea Airport2), while the second is appropriate when achieving either a literal such as (secure-at Korea Hill21) or an existentially quantified goal such as (exists ((<obj> OBJECT)) (secure-at Korea <obj>)).

  (OPERATOR SECURE-AIRPORT
     (params <obj> <loc>)
     (preconds
	( 	(<loc> location) 	(<obj> airport)
		(<internal-security> police-force-module)
		(<external-security> (and troops 
			(diff <internal-security> <external-security>)))
		(<air-defense> (and anti-air-module
			(diff <internal-security> <air-defense>)
			(diff <air-defense> <external-security>))))
	(and (loc-at <obj> <loc>) 
		(is-deployed <internal-security> <obj>)
		(is-deployed <air-defense> <obj>)
		(is-deployed <external-security> <obj>)) )
     (effects ()
	((add (secure-at <loc> <obj>)))) )

Figure 3. Secure operator

The advantage with such an operator hierarchy is that when achieving novel goals, the more general operator can be applied when no specialized operator is available.[2] However, when the user wants to secure Airport2, both operators are now licensed because Airport2 is a member of the class AIRPORT, but is also a member by transitivity of the class OBJECT. Thus, the effect of either operator will unify with the goal and so both are applicable. But clearly the planner should choose the more specific operator.

Thus it is useful to think of an existing hierarchy of operators that depends on the semantics of their effects. To formalize this notion, consider that one goal may be an ancestor of another goal. We have already mentioned that both literal and quantified goals exist in the Prodigy framework. But in more general terms we want to argue for the notion that the goal (is-deployed HAWK-BATTALION Korea) is more specific than (i.e., is a descendent of) the goal (is-deployed ANTI-AIR-MODULE COUNTRY), given that the first goal is a short-hand notation for the existential goal introduced earlier.

So knowing this property, the planner can control its choice of operator when solving goals in a hierarchy. Given a goal such that two or more operators apply to the goal, if one operator is an ancestor of another, then Prodigy should prefer the more specific operator. Control rule Prefer-More-Specific-Op in Figure 4 implements this preference. Two operators to be compared are bound to the rule using the standard meta-predicate candidate-operator (Carbonell et al., 1992). The function is-ancestor-op-of-p is a user defined meta-predicate that returns t iff the primary effect (Fink & Yang, in press) of both operators are not equal and the primary effect of the first operator is an ancestor of the primary effect of the second operator (as defined above by the ``>'' relation).

  (CONTROL-RULE Prefer-More-Specific-Op
       (if (and (candidate-operator <OP1>)
	(candidate-operator <OP2>)
	(is-ancestor-op-of-p <OP1> <OP2>)))
       (then prefer operator <OP1> <OP2>) )

Figure 4. Given two applicable operators from which to choose, prefer the more specific one

Top-level Goals Versus Subgoals

Finally, the goal information ForMAT sends to Prodigy always contains a mix of top-level goals and lower level constraining information. Myers (1996) considers such information to be constraint advice, although in the context of state-space planning, we view this advice as simply a subgoal specification. Given that the user provides both subgoals and top-level goals within an agenda, two decisions need to be addressed by a mixed-initiative system. First, for which class of goals should the system plan first? Should it proceed bottom up or top down and why? Second, given that it goes top down, how should the system serendipitously take advantage of the existing information the subgoals provide?

Order of planning

Given two goals such as G-143 = (is-deployed A-10A Korea) and its subordinate goal G-145 = (is-deployed 21st-Division-Ready-Brigade Korea), a planner will first plan for one and then the other. If the subordinate goal is achieved first, thus establishing the brigade in Korea, then the precondition of operator SECURE-AIRPORT having <external-security> in <loc> will already be true when planing for the superodinate goal (review Figures 2 and 3).

The problem with this approach, however, is twofold: First, we want to make sure that if more than one way exists to achieve the subordinate goal, then the plan chosen is consistent with the goals above it in the goal tree so that backtracking is avoided and the plan remains consistent. The top-level goals need to provide guidance to their subgoals.

Second, in this domain, the user should view the planning process and the evolving plan in an understandable, top-down way, rather than in a disjoint fashion as subgoals are randomly assembled. Hayes-Roth and Hayes-Roth (1979) contend that successive-refinement planning is appropriate in domains that exhibit hierarchical structure, when time is a scarce resource, and when reliable abstract plans exist in the domain. So given a choice of goals to achieve, we want to choose the one highest in the subgoal tree. That is, Prodigy should choose the one that is a supergoal of the other.

In the case of n=1, a single operator, OP, exists whose effects includes the effect e is an element of eff(OP) that unifies with G1 under the simple substitution, sigma, and whose preconditions includes p is an element of pre(OP) that unifies with G2 also under sigma.

Given definition2, control rule Prefer-Top-Most-Goal in Figure 5 can choose goals bound to supergoal <G1> over any of its subgoals bound to <G2> when the meta-predicate solves-precondition-of-p returns t. This occurs when some operator in Prodigy's subgoal tree for <G1> also achieves <G2> earlier in the plan.

  (CONTROL-RULE Prefer-Top-Most-Goal
     (if (and (candidate-goal <G1>)
	 (candidate-goal <G2>)
	 (solves-precondition-of-p <G1> <G2>)))
     (then prefer goal <G1> <G2>) )

Figure 5.Given two goals, prefer one if making the other true solves one of the preconditions for an operator that results in the preferred one

In a large domain, a direct implementation of this control rule will result in inefficiency because when two goals are independent, the metapredicate must search the entire space of plans for both goals. To alleviate exponential search, a heuristic can be incorporated into the metapredicate that either places a bound on, n (the number of operators in the chain specified in condition 1 of Definition 2), or it can refer to a cache table maintained during past planning episodes that map goal-subgoal relations.

Opportunistic planning

The policy established by Prefer-Top-Most-Goal creates another problem. If a top level goal is established first, such as G-143, then no guarantee exists that bindings established in plan operators such as SECURE-AIRPORT will agree with deferred subgoals. In the plan for deploying the A-10A, external security may be established by binding <external-security> with an instance of type TROOPS other than the 21st Division Ready Brigade.

Figure 6 shows a control rule that watches for propitious opportunities to optimize a plan by preferring bindings that also achieve additional pending goals. Given candidate bindings for the current operator in the search tree, meta-predicate match-constraining-goals identifies pending subgoals that unify with preconditions of the current operator. New bindings are then generated that satisfy this goal. Out of the candidate bindings, therefore, the control rule distinguishes ones that are consistent and are not consistent with such pending goals, preferring the former to the latter.

  (CONTROL-RULE Prefer-Bindings-Opportunistically
     (if (and
	(current-operator <OP>)
	(candidate-bindings <CB>)
	(match-constraining-goals <G> <OP>)
	(generate-new-bindings <NB> <G> <OP>)
	(identify-worse-bindings <CB> <NB> <WB><OP>)
	(identify-better-bindings <CB> <NB> <BB><OP>)))
     (then prefer bindings <BB> <WB>))

Figure 6. Given current operator and candidate set of bindings, prefer bindings that opportunistically solve another pending goal.