Realistic and complex planning situations require a mixed-initiative planning framework in which human and automated planners interact to mutually construct a desired plan. Ideally, this joint cooperation has the potential of achieving better plans than either the human or the machine can create alone. Our current research examines the computational problems and benefits associated with the interaction between the human planner and automated planning algorithms. We have taken three approaches in this investigation. First, we have developed an extensive graphical user-interface to the Prodigy/CBMIP planning and learning architecture that enables the human planner to examine the decision processes, to inspect the full data structures supporting planning decisions, and to visualize the plan as it unfolds. Second, we have relaxed the restrictiveness placed upon goal expressions by the classical AI planning paradigm. The user can express goals as actions as well as states, can represent goals along a continuum of specificity, and can interleave top-level goals and constraining subgoals in the input. Third, we have developed a novel approach to replanning in the face of dynamically acquired information at planning time. Instead of replanning only by the adaptation of a current plan, we allow both the user and the planning system to shift planning objectives in a space of goal transformations. Taken together, this research provides novel means for automating the production of plans, but with human guidance.
Although humans plan in a seemingly effortless fashion, planning is computationally a very difficult and intractable search problem. The graphical user interface (GUI) to the PRODIGY planning and learning architecture is an application that facilitates the process of planning (and research on planning) in three ways (Cox & Veloso, 1997b, 1997c). First, it allows the user to control the planning process. The user can switch between a generative, hierarchical and case-based approaches to planning as desired. The user can also make any of the planning decisions that the system would normally make itself. Second, the GUI supports graphical and mouse-sensitive visualization and inspection of the plan, the planning goals and plan rationale, including all data structures that represent each of these in the system. Finally, the GUI also allows the user to control the presentation of information in order to addresses the variance in the experience of the user to both the planning domain and the planning technology.
We have also integrated the Prodigy/CBMIP system with a military force deployment planner called ForMAT2 from BBN and a case management/server called Parka from the University of Maryland. The resulting system is called JADE (Joint Assistant for Deployment and Execution) (Veloso, Mulvehill, & Cox, 1997).* In JADE, PRODIGY provides adaptation guidance to the human deployment planner operating ForMAT2. The user forms deployment and employment goals which are passed to PRODIGY. In turn, PRODIGY provides suggestions for case (past plan) retrieval, modification and reuse. However, users often insist on providing goals with structure that is at variance with classical state-space search formalisms. Instead of imposing classical formalisms on the user, we provided a new formalism to expand the expressibility of planning goals.
We analyzed 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 (Cox & Veloso, 1997a). Users specify goals in terms of actions instead of states, provide goals along a continuum of specificity instead of ground literals, and mix both top-level and subordinate goals with the input. To manage this variety, we designed a preprocessor that transforms actions back into the equivalent state targets while remembering the user-desired action. We also created a theoretical formalism for goal ascendancy and used it as a basis for control information that chooses the most specific operator for non-grounded goals when given a choice. Finally, we developed a formalization of goal subordination that is used for controlling the selection of the top most goal given input goals that would occur along different depths in the goal tree.
Finally, our research encompasses the larger context of continuous planning in dynamic environments. In this area we have developed novel algorithms that adapt and replan. Although replanning is a matter of adjusting to the world as new information is discovered, the adjustment that planners classically perform under plan failure is change with regard to the knowledge of the planner concerning the current state of the world and, in response, adaptation of the current plan. Our observation, however, is that often it makes sense to adjust the goals of the planner rather than the plans themselves.
To detect these conditions, the planner must watch the environment for change during planning and execution time. A rationale-based sensing monitor is narrowly focussed by the planning decisions so that not all possible change is monitored. When change occurs, the planning algorithm or the user is able to not only adapt the plan in order to continue, but we have specified a set of goal transformations that can minimally adapt the objectives of planning when a goal becomes obsolete or sufficient resources do not exist to create a valid plan. We have shown empirically that replanning without goal transformations is less productive than planning with them (Cox & Veloso, 1998) and that rationale-based sensing is more effective than classical replanning (Veloso, Pollack, & Cox, 1997).
The area of mixed-initiative planning is a growing new subfield that promises much progress in the near future. Many avenues are open for exploration using applied, theoretical and empirical methods of computer science. Moreover, the issues are diverse and therefore are well suited to interdisciplinary research between computer scientists, engineers, human factors specialists, and cognitive scientists. In particular, our concept of replanning through goal transformations and the role of the human user in such adaptation is just now being examined fully. Future research has a superb chance of extending the results to produce planning systems that scale in natural domains. The key is to leverage the experience of the user and to adapt to change, rather than to engineer a complete and consistent domain theory.
Cox, M. T., & Veloso, M. M. (1997a). Controlling for unexpected goals when planning in a mixed-initiative setting. In E. Costa & A. Cardoso (Eds.), Progress in Artificial Intelligence: Eighth Portuguese Conference on Artificial Intelligence (pp. 309-318). Berlin: Springer.
Cox, M. T., & Veloso, M. M. (1997b). Supporting combined human and machine planning: An interface for planning by analogical reasoning. In D. B. Leake & E. Plaza (Eds.), Case-Based Reasoning Research and Development: Second International Conference on Case-Based Reasoning (pp. 531-540). Berlin: Springer-Verlag.
Cox, M. T., & Veloso, M. M. (1997c). Supporting combined human and machine planning: The Prodigy 4.0 User Interface Version 2.0 (Tech, Rep. No. CMU-CS-97-174). Pittsburgh: Carnegie Mellon University, Computer Science Department.
Cox, M. T., & Veloso, M. M. (in press). Goal Transformations in Continuous Planning. In M. desJardins (Ed.), Proceedings of the 1998 AAAI Fall Symposium on Distributed Continual Planning. Menlo Park, CA: AAAI Press / The MIT Press.
Veloso, M. M., Mulvehill, A. M., & Cox, M. T. (1997). Rationale-supported mixed-initiative case-based planning. In Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference (pp. 1072-1077). Menlo Park, CA: AAAI Press / The MIT Press.
Veloso, M. M., Pollack, M. E., & Cox, M. T. (1998). Rationale-based monitoring for continuous planning in dynamic environments. In R. Simmons, M. Veloso, & S. Smith (Eds.), Proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems (pp. 171-179). Menlo Park, AAAI Press.
Last Edited: August 13, 1998