Meta-level planning

Meta-level planning in dialogue distinguishes between the domain plan, and the dialogue plan whose subject is the domain plan. The domain plan is often, but not always, a plan of physical actions, whereas the dialogue plan is one that establishes the beliefs that are a precondition to some of the domain actions, or establishes the domain-level intention of the speaker so that a correct cooperative response can be given by the hearer. Litman [45] describes a planner that uses a stack of plans, with the domain plan at the bottom, and with each subsequent plan being a meta-level plan of the previous plan. The dialogue plans are constructed from a set of STRIPS schemas, which take the plan at the next level in the stack as parameters. The "continue-plan" schema is for executing the next focussed act. The "track-plan" schema is for using a dialogue act to declare the focussed act to the hearer. This helps the hearer to perform plan recognition, and provide an appropriate cooperative response. The "identify-parameter" schema is used to establish a speaker or hearer belief that is a precondition in the object plan. The "correct-plan" schema is used to introduce a new object plan when another has failed. The "introduce-plan" and "modify-plan" schemas are used to indicate a change of focus on the object plan. These are needed since otherwise, a focussed plan recogniser would discount the plan as breaking the focussing rule.

While Litman's meta-planning schemas are used to follow the structure of a domain-level plan, Ramshaw [54] uses meta-planning to also choose the domain plan. In a situation where there is an agent with limited knowledge of the domain state, and an expert user who has wide domain knowledge, the agent may need to explore several domain plans, consulting the expert about each one, and if a plan should thereby fail, it may need to backtrack and try an alternative way of constructing the plan. Ramshaw defines a "build-plan" action, which can be achieved by several different "build-subplan" actions, with backtracking over these alternatives. Ramshaw's planner backtracks because of failed preconditions. Some preconditions can be satisfied using y/n and wh- queries, named "check-pred-value" and "ask-pred-value". Some preconditions can be satisfied in many ways, for example, there may be ten different ships suitable for the agent's battle plan, each of which may be used to instantiate a parameter to a plan schema. The "ask-fillers" action is one of a family of actions used for this sort of query. Ramshaw suggests that a future direction for his planner is rather than seeking out the first workable plan, to use a quantitative comparison of competing plans in a negotiation dialogue. This suggestion is taken up in this thesis.

Smith and Hipp [69] describe a planner that is quite similar to Ramshaw's backtracking meta-planner, in that it too uses a backtracking search, controlled by a Prolog interpreter, to find a solution for a domain-level plan. Where Ramshaw's planner always uses system initiative, only allowing the expert to respond to queries, their planner allows differing levels of initiative whereby both agents can answer queries, ask queries, give unasked-for information, and introduce goals to different extents. This requires a richer model of the user than one of the passive knowledge-base used by Ramshaw. They use a model that encompasses problem solving capabilities as well as domain-state knowledge. Problem-solving knowledge is encoded as Prolog rules, with some subgoals being achieved by rules that are within the user model. The system passes control to the user whenever these subgoals are invoked. They even give an example of a clarification where the user is given control for a subgoal, and then for a further subgoal the user passes control back to the system, thereby using a deeply nested user model.