Performance analysis of sum-product algorithms for multiple fault diagnosis applications

In this paper, we study the application of sum-product algorithms (SPAs) to multiple fault diagnosis (MFD) problems in order to diagnose the most likely state of each component given the status of alarms. SPAs are heuristic algorithms of polynomial complexity that are known to converge to the marginal solutions in settings where the underlying interconnection graph has a tree structure. To determine SPA performance on more general MFD graphs (with cycles), we use properties of the dynamic range measure for SPA beliefs and take advantage of the bipartite nature of MFD graphs. This leads to the establishment of bounds on the true marginal of each component with respect to the beliefs provided by the SPAs. We show via examples and simulations that these bounds are very tight and significantly improve existing results. We also show that fault diagnosis based on SPA beliefs (using them as suboptimal solutions to the marginal problems) can enable the detection of multiple faults with very high accuracy.