Reference: Ash, D. Diagnosis using Action-Based Hierarchies for Optimal Real-Time Performance. Ph.D. Thesis, Stanford University, 1993.
Abstract: to respond effectively in real time, an agent needs to be able to deal effectively with differing availability of information. in particular, although the agent ideally would like to be able to diagnose one or more particular faults that may be present at a given time, a deadline may prevent it from doing so because prior to the deadline it is required to act or face a catastrophic outcome. thus, an agent should have available to it a set of actions some of which are appropriate, but not optimal, for large classes of faults and some of which are appropriate for specific faults. tests are available to help the agent diagnose a fault; given this framework decision trees would provide one possible approach to this diagnosis problem. however this work shows that the information-theoretic heuristic commonly used to structure decision trees is not ideal in a real time domain because it concerns itself with reaching a leaf node as fast as possible, not with the value of the actions it might obtain along the way. my thesis presents an alternative heuristic, the action-based heuristic, which may be used to structure a decision tree; the resulting structure together with the actions themselves is called an action-based hierarchy. the approach is validated in several ways. first a complexity analysis is undertaken to show that the complexity of the structuring algorithm is not prohibitive. then some theoretical results are given; this is followed by experiments both with abstract inputs and inputs from a real-time domain, surgical intensive care unit patient monitoring. the thesis concludes with a description of an implementation of these ideas in a system known as react.
Notes: December STAN-CS-93-1498.