Backward Reachability Analysis Based on BPNs to Model-Based Diagnosis with Relationships among Symptoms

H. Bennoui(1*), A. Chaoui(2)

(1) Computer Science Department, University of Biskra, Algeria
(2) LIRE Laboratory, Computer Science Department, University of Constantine, Algeria
(*) Corresponding author

DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)


Diagnosing multiple faults that may occur in distributed systems has received a lot of attention over the last decade. In particular, a backward reachability analysis based on Behavioral Petri Net (BPN) models has been proposed to model-based diagnosis of such systems. Nevertheless, it has been defined without tacking into account the concept of precedence relationships that may exist among fault indications or symptoms. The aim of this paper is two fold: first, to extend such analysis to handle precedence orders among symptoms at their signalization time; and second, to deal with the problem of contradictory observations which conduct to an inconsistency in the given problem. The relationships among symptoms are expressed in the net model as transitions among places denoting the corresponding symptoms. For the diagnosis process, they are captured through a novel set of backward firing rules used to construct the corresponding marking graph. In order to treat the inconsistency problems, we propose to restore the required consistency to the given problem. This is accomplished by identifying some symptoms that are known to be absent in the case under examination and when they are supposed present will explain the observed misbehavior. The paper is written in an informal style emphasizing on considerations of practical order than theoretical ones.
Copyright © 2018 Praise Worthy Prize - All rights reserved.


Behavioral Petri Nets; Model-Based Diagnosis; Reachability Analysis; Inconsistent Marking

Full Text:



Y. Koseki, Experience Learning in Model-Based Diagnostic Systems, Proceedings of the 11th Intl. Joint Conf. on Artificial Intelligence, Detroit, Morgan Kaufmann, MI(USA), pp. 1356-1362, 1989.

Anglano C., Portnale L., B-W Analysis: A Backward Reachability Analysis for Diagnostic Problem Solving Suitable to Parallel Implementation, In Application and Theory of Petri Nets, LNCS 815, Springer Verlag, pp. 39-58, 1994.

L. Portinale, Exploiting T-invariant Analysis in Diagnostic Reasoning on a Petri Net Model, In Application and Theory of Petri Nets, LNCS 691(1), Springer Verlag, pp. 339-356, 1993.

L. Portinale, Petri Net Models for Diagnostic Knowledge Representation and Reasoning, PhD Thesis, Dip. Informatica, Universita' di Torino, 1993.

L. Portinale, Improving Model-Based Diagnosis through Algebraic Analysis: the Petri Net Challenge, Proceedings of the 13th National Conference on Artificial Intelligence-AAAI'96, Portland, pp: 952-958, 1996.

S. Genç, and S. Lafortune, Distributed Diagnosis of Discrete-Event Systems Using Petri Nets, In Application and Theory of Petri Nets, LNCS 2679, Springer Verlag, pp. 316-336, 2003.

S. Genç, and S. Lafortune, A Distributed Algorithm for On-Line Diagnosis of Place-Bordred Petri Nets, IFAC, 2005.

S. Lafortune, D. Teneketzis, M. Sampath, R. Sengupta, and K. Sinnamohideen, Failure Diagnosis of Dynamic Systems: An Approach based on Discrete Event Systems, Proceedings of the American Control Conf, pp. 2058-2071, 2001.

M. Sampath, R. Sengupta, S. Lafortune, K. Sinnamohideen, and D. Teneketzis, Failure Diagnosis Using Discrete Event Models, IEEE Trans. Control Systems Technology 4, pp. 105-124, 1996.

A. Aghasaryan, E. Fabre, A. Benveniste, R. Boubour, C. Jard, Fault Detection and Diagnosis in Distributed Systems: An Approach by Partially Stochastic Petri Nets, Journal of Discrete Event Dynamical Systems, Vol. 8, n. 2, pp. 203-231, 1998.

L. Console, L. Portinale, D.T. Dupré, and P. Torasso, Combining Heuristic and Causal Reasoning in Diagnostic Problem Solving, In Second Generation Expert Systems, J.M. David, J.P. Krivine and R. Simmons editors, Springer Verlag, 1993.

Bennoui H., Maouche M., Bettaz M., An approach for fault diagnosis in networks, Proceedings of the CFIP'99 (Page: 433-445, Year of Publication: 1999 ISBN: 2-7462-0018-X).

L. Console, and P. Torasso, A Spectrum of Logical Definitions of Model-Based Diagnosis, Computational Intelligence 7(3), pp. 133-141, 1991.

B. El Ayeb, P. Marquis, and M. Rusinowitch, A New Diagnosis Approach by Deduction and Abduction, Proceedings of the International Workshop on Expert Systems in Engineering, LNAI 462, Springer Verlag, pp. 32-46, 1990.

D. Poole, Normality and Faults in Logic-Based Diagnosis, Proceedings of the 11th Intl. Joint Conf. on Artificial Intelligence, Detroit, Morgan Kaufmann, MI(USA), pp. 1304-1310, 1989.

T. Murata, Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, Vol.77, N°.4, pp. 541-580, 1989.

Bennoui H., T-invariant Analysis to Diagnose Multiple Failures in Networks, Proceedings of the 1st MICCT'99 (Page: 185-196, Year of Publication: 1999).


  • There are currently no refbacks.

Please send any question about this web site to
Copyright © 2005-2022 Praise Worthy Prize