AND-OR graph with knowledge propagation rules as a model for Constraint Satisfaction Problems

• Autorzy: Ligęza A.

Warianty tytułu

PL

Graf AND-OR z regułami propagacji wiedzy jako model dla problemów z ograniczeniami

• Języki publikacji: EN

Abstrakty

EN

In this paper a model for Constraint Satisfaction Problems based on the concept of AND-OR graph is presented. The graph provides a structure to model search-space for alternative solutions. In order to represent auxiliary constraints it is completed with a set of rules for knowledge propagation. The rules can be used for efficient modelling of constraints for knowledge propagation and for detection of inconsistency. An example from the area of automated diagnosis is used to illustrate the application.

PL

W pracy przedstawiono koncepcję zastosowania grafu AND--OR do rozwiązywania problemów z ograniczeniami. Dla efektywnej eliminacji niepoprawnych rozwiązań zastosowano system regułowy. Jest on wykorzystywany do propagacji wiedzy. W przypadku wykrycia niespójności, potencjalne rozwiązanie jest eliminowane. Rozważania przeprowadzono na przykładzie zastosowania proponowanego podejścia do eliminacji niepoprawnych rozwiązań problemu diagnostycznego.

Słowa kluczowe

EN

constraint satisfaction problems; AND-OR graphs; rules

PL

problemy z ograniczeniami; grafy AND-OR; systemy regułowe; diagnostyka

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 411--419
• Opis fizyczny: Bibliogr. 4 poz., rys.

Twórcy

autor

Ligęza A.

• Department of Automatics, AGH University of Science and Technology, Kraków and PWSZ Tarnów, Poland

Bibliografia

• [1] Apt. K.R., Principles of Constraint Programming. Cambridge University Press, Cambridge, UK
• [2] Dechter R., Constraint Processing. Morgan Kaufmann Publishers, San Francisco, CA, 2003.
• [3] Ligęza A., Kościelny J.M., A new approach to multiple fault diagnosis, combination of diagnostic matrices, graphs, algebraic and rule-based models. The case of two-layer models. Int. J. Appl. Math. Comput. Sei., 18(4), 2008, 465-476.
• [4] Reiter R., A theory of diagnosis from first principles. Artificial Intelligence, 32, 1987, 57-95.