Using action-based hierarchies for real-time diagnosis

摘要

An intelligent agent diagnoses perceived problems so that it can respond to them appropriately. Basically, the agent performs a series of tests whose results discriminate among competing hypotheses. Given a specific diagnosis, the agent performs the associated action. Using the traditional information-theoretic heuristic to order diagnostic tests in a decision tree, the agent can maximize the information obtained from each successive test and thereby minimize the average time (number of tests) required to complete a diagnosis and perform the appropriate action. However, in real-time domains, even the optimal sequence of tests cannot always be performed in the time available. Nonetheless, the agent must respond. For agents operating in real-time domains, we propose an alternative action-based approach in which: (a) each node in the diagnosis tree is augmented to include an ordered set of actions, each of which has positive utility for all of its children in the tree; and (b) the tree is structured to maximize the expected utility of the action available at each node. Upon perceiving a problem, the agent works its way through the tree, performing tests that discriminate among successively smaller subsets of potential faults. When a deadline occurs, the agent performs the best available action associated with the most specific node it has reached so far. Although the action-based approach does not minimize the time required to complete a specific diagnosis, it provides positive utility responses, with step-wise improvements in expected utility, throughout the diagnosis process. We present theoretical and empirical results contrasting the advantages and disadvantages of the information-theoretic and action-based approaches.