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.
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 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.
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.
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.
(GEOGRAPHIC-LOCATION KOREA)) )
( (FORCE 21ST-DIVISIONREADYBRIGADE)
(GEOGRAPHIC-LOCATION KOREA)) )
( (FORCE HAWK-BATTALION)
(GEOGRAPHIC-LOCATION KOREA)) )
( (GEOGRAPHIC-LOCATION KOREA)
(AIRCRAFT-TYPE A-10A)) ) )
Figure 2. Prodigy goal tree
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.
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). 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>)).
(params <obj> <loc>)
( (<loc> location) (<obj> airport)
(<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>)) )
((add (secure-at <loc> <obj>)))) )
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).
(if (and (candidate-operator <OP1>)
(is-ancestor-op-of-p <OP1> <OP2>)))
(then prefer operator <OP1> <OP2>) )
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.
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
(if (and (candidate-goal <G1>)
(solves-precondition-of-p <G1> <G2>)))
(then prefer goal <G1> <G2>) )
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.
(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>))
The success of these control rules in managing the variety of goal types
provided to Prodigy by the ForMAT user has been established during trials with
the military agencies (see Veloso et al., 1996). Our prototype has been
validated in real-time usage across the internet with Prodigy/Analogy operating
from CMU in Pittsburgh and ForMAT from Boston. Military planners have used the
system in a limited fashion, but one that combines all three situations
This research is sponsored as part of the DARPA/RL Knowledge Based Planning and
Scheduling Initiative under grant number F30602-95-1-0018. The authors thank
Eugene Fink and Gary Pelton for comments and suggestions on earlier drafts of
Ferguson, G., Allen, J. F., & Miller, B. (1996). TRAINS-95: Towards a mixed-initiative planning assistant. In Proceedings of the 3rd International Conference on AI Planning Systems.
Fink, E, & Yang, Q. (in press). Automatically selecting and using primary effects in planning: Theory and experiments. Art. Intel.
Hayes-Roth, B., & Hayes-Roth, F. (1979). A cognitive model of planning. Cognitive Science.
McDermott, D. (1978). Planning and acting. Cognitive Science, 2(2), 71-109.
Myers, K. L. (1996). Strategic advice for hierarchical planners. In Proceeding of the Fifth International Conference on Principles of Knowledge Representation and Reasoning. San Francisco: Morgan Kaufmann.
Mulvehill, A. (1996). Building, remembering, and revising force deployment plans, In A. Tate (Ed.), Technological Achievements of the ARPA/Rome Laboratory Planning Initiative. Menlo Park, CA: AAAI Press.
Mulvehill, A., & Christey, S. (1995). ForMAT - a force management and analysis tool. Bedford, MA: The MITRE Corporation.
Pollack, M. E. (1990). Plans as complex mental attitudes. In P. R. Cohen, J. Morgan & M. E. Pollack (Eds.), Intentions in communication (pp. 77-104). Cambridge, MA: MIT Press.
Veloso, M. M. (1994). Planning and learning by analogical reasoning. New York: Springer-Verlag.
Veloso, M. M. (1996). Towards Mixed-Initiative Rationale-Supported Planning. In A. Tate (Ed.), Advanced planning technology. Menlo Park, CA: AAAI Press.
Veloso, M., Carbonell, J., Pérez, A., Borrajo, D., Fink, E., & Blythe, J. (1995). Integrating planning and learning: The PRODIGY architecture. Journal of Experimental and Theoretical Artificial Intelligence, 7(1), 81-120.
Veloso, M., Mulvehill, A., & Cox, M. (1996). Rationale-supported mixed-initiative case-based planning. Submitted.
Wilkins, D., & Desimone, R. (1994). Applying an AI planner to military operations planning. In M. Zweben & M. Fox (Eds.), Intelligent scheduling (pp. 685-709). San Mateo: M. Kaufmann.