T. K. Satish Kumar
Knowledge Systems Laboratory Stanford University tksk@ksl.stanford.edu
Abstract: In continuously evolving systems (including hybrid systems), trajectory selection (diagnosis) based on limited observations is usually a difficult thing to do. Probabilistic approaches to this problem try to select hypotheses based on their posterior probabilities conditioned on the observations made. These approaches, however, try to relate parameters of a hypothesis directly to the observations made (usually under unwarranted assumptions) without respecting the complexity of the equation models according to which they may be related, hence leading to their inaccurracy. Computationally also, the number of competing hypotheses may be too large to gain tractability over a reasonably big physical system. There is also no neat way of leveraging qualitative knowledge of the system towards computational gains. In this paper, we remove all these drawbacks by first formulating the diagnosis problem as a CSP requiring simulation to perform consistency checks. We then define a cost model and describe an algorithm called QCBFS which not only avoids having to deal with too many competing hypotheses, but also provides a unifying framework to leverage any qualitative knowledge or probability estimates from previous approaches. Probability estimates imported from other sources can affect only the focusing power of QCBFS but not its accurracy.
Full Paper (PDF 111 KB)