Search Control Rules

PRODIGY4.0 provides a method for creating search control rules that reduce the number of choices at each decision point in Table 2 by pruning the search space or suggesting a course of action while expanding the plan. In particular, control rules can select, prefer or reject a particular goal or action in a particular situation. Control rules can be used to focus planning on particular goals and towards desirable plans.

Each time PRODIGY4.0 examines the set of unsolved pending goals, it fires its search control rules to decide which goal to expand. ROGUE interacts with PRODIGY4.0 by providing the set of control rules used to constrain PRODIGY4.0's decisions. Table 3 shows ROGUE's goal selection control rule that calls two functions, forcing PRODIGY4.0 to select the goals with high priority as well as the goals that can be opportunistically achieved (without compromising the main high-priority goal).

 

Table 3: Goal selection search control rule.

The function (ancestor-is-top-prioritygoal) calculates whether the goal is required to solve a high-priority goal. ROGUE prioritizes goals according to a modifiable metric. For example, in the current implementation, this metric involves looking at the user's position in the department, the type of request and the deadline: Priority = PersonRank + TaskRank + DeadlineRank, where DeadlineRank is defined as shown in Figure 6. (When the deadline is reached, the goal is removed from PRODIGY4.0's pending goals list; otherwise even a task of priority 0 would eventually be attempted after all other pending tasks have been completed.) This function could easily be replaced with alternatives (e.g. [Williamson & Hanks1994]).

 

Figure 6:Calculating the priority rank of the deadline.

The function (compatible-with-top-priority-goal) allows ROGUE to determine when different goals have similar features so that it can opportunistically achieve lower priority goals while achieving higher priority ones. For example, if multiple people whose offices are all in the same hallway asked for their mail to be picked up and brought to them, ROGUE would do all the requests in the same episode, rather than only bringing the mail for the most important person. Compatibility is defined by physical proximity (``on the path of'') with a fixed threshold for being too far out of the way.

It is possible that these rules will select too many compatible tasks, become ``side-tracked,'' and therefore fail on the high-priority task. A preset threshold would serve as a pragmatic solution to this problem. We also do not deal with the issue of thrashing, i.e., receiving successively more important tasks resulting in no forward progress, because it has not been an issue in practice.

PRODIGY4.0 also uses a search control rule to select a good execution order of the applicable actions. It makes the choice based on an execution-driven heuristic which minimizes the expected total traveled distance from the current location.