Diagnosis of discrete-event systems using satisfiability algorithms

Alban Grastien; Anbulagan; Jussi Rintanen; Elena Kelareva

Diagnosis of discrete-event systems using satisfiability algorithms

Alban Grastien^*, Anbulagan, Jussi Rintanen, Elena Kelareva

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

52 Citations (Scopus)

Abstract

The diagnosis of a discrete-event system is the problem of computing possible behaviors of the system given observations of the actual behavior, and testing whether the behaviors are normal or faulty. We show how the diagnosis problems can be translated into the propositional satisfiability problem (SAT) and solved by algorithms for SAT. Our experiments demonstrate that current SAT algorithms can solve much bigger diagnosis problems than traditional diagnosis algorithms can.

Original language	English
Title of host publication	AAAI-07/IAAI-07 Proceedings
Subtitle of host publication	22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference
Pages	305-310
Number of pages	6
Publication status	Published - 2007
Event	AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference - Vancouver, BC, Canada Duration: 22 Jul 2007 → 26 Jul 2007

Publication series

Name	Proceedings of the National Conference on Artificial Intelligence
Volume	1

Conference

Conference	AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference
Country/Territory	Canada
City	Vancouver, BC
Period	22/07/07 → 26/07/07

Cite this

Grastien, A., Anbulagan, Rintanen, J., & Kelareva, E. (2007). Diagnosis of discrete-event systems using satisfiability algorithms. In AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference (pp. 305-310). (Proceedings of the National Conference on Artificial Intelligence; Vol. 1).

@inproceedings{a5f6b92be3b34e6db6ec82122209b090,

title = "Diagnosis of discrete-event systems using satisfiability algorithms",

abstract = "The diagnosis of a discrete-event system is the problem of computing possible behaviors of the system given observations of the actual behavior, and testing whether the behaviors are normal or faulty. We show how the diagnosis problems can be translated into the propositional satisfiability problem (SAT) and solved by algorithms for SAT. Our experiments demonstrate that current SAT algorithms can solve much bigger diagnosis problems than traditional diagnosis algorithms can.",

author = "Alban Grastien and Anbulagan and Jussi Rintanen and Elena Kelareva",

year = "2007",

language = "English",

isbn = "1577353234",

series = "Proceedings of the National Conference on Artificial Intelligence",

pages = "305--310",

booktitle = "AAAI-07/IAAI-07 Proceedings",

note = "AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference ; Conference date: 22-07-2007 Through 26-07-2007",

}

Grastien, A, Anbulagan, Rintanen, J & Kelareva, E 2007, Diagnosis of discrete-event systems using satisfiability algorithms. in AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference. Proceedings of the National Conference on Artificial Intelligence, vol. 1, pp. 305-310, AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference, Vancouver, BC, Canada, 22/07/07.

Diagnosis of discrete-event systems using satisfiability algorithms. / Grastien, Alban; Anbulagan; Rintanen, Jussi et al.
AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference. 2007. p. 305-310 (Proceedings of the National Conference on Artificial Intelligence; Vol. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Diagnosis of discrete-event systems using satisfiability algorithms

AU - Grastien, Alban

AU - Anbulagan,

AU - Rintanen, Jussi

AU - Kelareva, Elena

PY - 2007

Y1 - 2007

N2 - The diagnosis of a discrete-event system is the problem of computing possible behaviors of the system given observations of the actual behavior, and testing whether the behaviors are normal or faulty. We show how the diagnosis problems can be translated into the propositional satisfiability problem (SAT) and solved by algorithms for SAT. Our experiments demonstrate that current SAT algorithms can solve much bigger diagnosis problems than traditional diagnosis algorithms can.

AB - The diagnosis of a discrete-event system is the problem of computing possible behaviors of the system given observations of the actual behavior, and testing whether the behaviors are normal or faulty. We show how the diagnosis problems can be translated into the propositional satisfiability problem (SAT) and solved by algorithms for SAT. Our experiments demonstrate that current SAT algorithms can solve much bigger diagnosis problems than traditional diagnosis algorithms can.

UR - http://www.scopus.com/inward/record.url?scp=36349021952&partnerID=8YFLogxK

M3 - Conference contribution

SN - 1577353234

SN - 9781577353232

T3 - Proceedings of the National Conference on Artificial Intelligence

SP - 305

EP - 310

BT - AAAI-07/IAAI-07 Proceedings

T2 - AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference

Y2 - 22 July 2007 through 26 July 2007

ER -

Diagnosis of discrete-event systems using satisfiability algorithms

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this