Max-product algorithms for the generalized multiple-fault diagnosis problem
Hadjicostis, Christoforos N.
SourceIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Google Scholar check
MetadataShow full item record
In this paper, we study the application of the max-product algorithm (MPA) to the generalized multiple-fault diagnosis (GMFD) problem, which consists of components (to be diagnosed) and alarms/connections that can be unreliable. The MPA and the improved sequential MPA (SMPA) that we develop in this paper are local-message-passing algorithms that operate on the bipartite diagnosis graph (BDG) associated with the GMFD problem and converge to the maximum a posteriori probability (MAP) solution if this graph is acyclic (in addition, the MPA requires the MAP solution to be unique). Our simulations suggest that both the MPA and the SMPA perform well in more general systems that may exhibit cycles in the associated BDGs (the SMPA also appears to outperform the MPA in these more general systems). In this paper, we provide analytical results for acyclic BDGs and also assess the performance of both algorithms under particular patterns of alarm observations in general graphs; this allows us to obtain analytical bounds on the probability of making erroneous diagnosis with respect to the MAP solution. We also evaluate the performance of the MPA and the SMPA algorithms via simulations, and provide comparisons with previously developed heuristics for this type of diagnosis problems. We conclude that the MPA and the SMPA perform well under reasonable computational complexity when the underlying diagnosis graph is sparse. © 2007 IEEE.
Showing items related by title, author, creator and subject.
Le, T.; Hadjicostis, Christoforos N. (Institute of Electrical and Electronics Engineers Inc., 2007)In this paper, we analyze the performance of algorithms that use belief propagation max-product iterations to solve the generalized multiple fault diagnosis (GMFD) problem. The GMFD problem is described by a bipartite ...
Le, T.; Hadjicostis, Christoforos N. (2008)In this paper, we propose low-complexity max-product algorithms for the problem of multiple fault diagnosis (MFD). The MFD problem is described by a bipartite diagnosis graph (BDG) which consists of a set of components, a ...
Improved performance bounds on max-product algorithms for multiple fault diagnosis in graphs with loops Le, T.; Hadjicostis, Christoforos N. (2008)In this paper, we analyze the performance of belief propagation max-product algorithms when used to solve the multiple fault diagnosis (MFD) problem. The MFD problem is described by a bipartite diagnosis graph (BDG) which ...