Tech Report CS-90-11

Classifying and Detecting Plan-Based Misconceptions for Robust Plans

Randall J. Calistri

May 1990

Abstract:

In order to maintain a truly cooperative dialogue, an intelligent natural language interface must be able to recognize misconceptions in the user's plans. This involves solving two problems: determining what sorts of mistakes people make when they reason about plans, and figuring out how to recognize these mistakes when they occur.

There are sixteen distinct ways that a plan can be improperly constructed. Each of these corresponds to one type of plan-based misconceptions. But is not necessary to consider all sixteen classes; the classification can be simplified to ten categories of detectable, distinguishable plan-based misconceptions. This classification can be used to develop a robust plan recognition algorithm that is capable of recognizing both correct plans and plans that contain misconceptions. Probabilistic methods can be used to handle the three main difficulties of robust plan recognition: dealing with the `hard' classes of misconceptions, controlling the combinatorial explosion that results from the ambiguity inherent in faulty plans, and selecting the most likely plan among multiple competing explanations.

The theory that is developed here is implemented in a program called Pathfinder, which is a probability-based plan recognition system based on the {\bf A*} best-first search algorithm that has been extended to recognize novel plan failures in an intelligent interface environment.

(complete text in pdf)