USING ACTION-BASED HIERARCHIES FOR REAL-TIME DIAGNOSIS

An intelligent agent diagnoses perceived problems so that it can respo nd to them appropriately. Basically, the agent performs a series of te sts whose results discriminate among competing hypotheses. Given a spe cific diagnosis, the agent performs the associated action. Using the t raditional information-theoretic heuristic to order diagnostic tests i n a decision tree, the agent can maximize the information obtained fro m each successive test and thereby minimize the average time (number o f tests) required to complete a diagnosis and perform the appropriate action. However, in real-time domains, even the optimal sequence of te sts cannot always be performed in the time available. Nonetheless, the agent must respond. For agents operating in real-time domains, we pro pose an alternative action-based approach in which: (a) each node in t he diagnosis tree is augmented to include an ordered set of actions, e ach 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 th e action available at each node. Upon perceiving a problem, the agent works its way through the tree, performing tests that discriminate amo ng successively smaller subsets of potential faults. When a deadline o ccurs, the agent performs the best available action associated with th e most specific node it has reached so far. Although the action-based approach does not minimize the time required to complete a specific di agnosis, it provides positive utility responses, with step-wise improv ements in expected utility, throughout the diagnosis process. We prese nt theoretical and empirical results contrasting the advantages and di sadvantages of the information-theoretic and action-based approaches.