Using ROBDDs for troubleshooting

Nielsen, Thomas

Wuillemin, Pierre-Henri
LIP6 - Pôle IA
Université Paris 6
8, rue du capitaine Scott F-75015 Paris, France
email: pierre-henri.wuillemin@lip6.fr   home: www-desir.lip6.fr/~phw

Jensen, Finn

Kjaerulf, Uffe

Nielsen, Thomas and Wuillemin, Pierre-Henri and Jensen, Finn and Kjaerulf, Uffe (2000) "Using ROBDDs for troubleshooting". In Kathryn B. Laskey and Henri Prade (eds), Proceedings of the 15th conference on Uncertainty in Artificial Intelligence, pp. 426--435.

When building a Bayesian network model it frequently happens that a large part of the model is deterministic. This happens particularly when modelling the behavior of man-made machinery. Then the situation is that we have a deterministic kernel with surrounding chance variables, and it seems excessive to use standard junction tree algorithms for belief updating. First of all, the calculations in the deterministic kernel are integer calculations and double precision calculations are unnecessary complex. However, there may be room for further improvements. If the deterministic part of the model is represented as a Boolean function, we may exploit contemporary advances in calculation of Boolean functions. A major advance in Boolean calculation is Binary Decision Diagrams, particularly Reduced Ordered Binary Decision Diagrams, ROBDDs. An ROBDD is a DAG representation of a Boolean function. The representation is tailored for fast calculation of values, but the representation can also be used for fast calculation of the number of satisfying configurations given an instantiation of a subset of the variables.

@InProceedings{,
  author = {Nielsen, Thomas and Wuillemin, Pierre-Henri and Jensen, Finn and Kjaerulf, Uffe},
  title = {Using ROBDDs for troubleshooting},
  booktitle = {Proceedings of the 15th conference on Uncertainty in Artificial Intelligence},
  year = {2000},
  editor = {Kathryn B. Laskey and Henri Prade},
  pages = {426--435}
}