METHODS FOR ACCELERATING COMBINATORIAL SEARCH BASED ON MATRIX REPRESENTATION OF QUALITATIVE RELATIONSHIPS IN CONSTRAINT SATISFACTION PROBLEMS

PURPOSE. The relevance of the presented studies is determined by the importance of modeling of poorly formalized subject domains, the knowledge of which is heterogeneous and has both quantitative and qualitative nature. With the advent of constraint programming technology the conditions for unifying the joint processing of heterogeneous constraints of the subject domain have emerged. However, today qualitative dependencies are not processed effectively enough. The article is devoted to the development of methods for economical representation of non-numerical constraints, as well as effective methods for their satisfaction. The research is aimed at acceleration of the combinatorial search procedures when solving constraint satisfaction problems in poorly formalized subject domains. METHODS. The methods proposed in the article develop the constraint satisfaction theory in the part of representing and improving the efficiency of joint processing of quantitative and qualitative relationships of a poorly formalized subject domain. Presentation and processing of non-numerical (qualitative) constraints of the subject domain is proposed to perform with the use of specialized matrix-like structures ( C- and D- systems). The reasoning on these structures should be implemented in the form of constraint satisfaction procedures. RESULTS AND THEIR DISCUSSION. Two theorems on the properties of matrix-like structures and their corollaries are formulated. Together with the proposed reduction rules they can successfully propagate non-numerical constraints: identify the subspaces of legal and illegal assignments in the search space by checking only a part of the values from the variable domain. Based on the corollaries of the theorems mentioned above, the modifications are developed to the known methods of constraint propagation, which provide node and arc consistency for the case of non-numerical constraints. Unlike most analogs these modifications allow the CSP to be effectively reduced, even if it was not originally represented by a set of unary and binary constraints only. CONCLUSIONS. The paper offers a complex approach to the representation and processing of qualitative dependencies in poorly formalized subject domains, which allows to provide an acceptable computational speed in the study of subject domains with complicated multiple relationships.

constraint satisfaction theory, constraint propagation, matrix-like structures, non-numerical constraints, consistency algorithms, non-numeric constraints over finite domains

1. Bartak R. Constraint Programming: In Pursuit of the Holy Grail: Proceedings of the Week of Doctoral Students (WDS99). Prague: MatFyzPress. 1999. Vol. IV. P. 555-564.

2. Russel S., Norvig P. Artificial Intelligence: A Modern Approach. 3nd ed. Pearson Education. (2010).

3. Кулик Б.А. Зуенко А.А., Фридман А.Я. Алгебраический подход к интеллектуальной обработке данных и знаний. СПб.: Изд-во Политехнического ун-та. 2010. 235 с.

4. Zakrevskij A. Integrated Model of Inductive-Deductive Inference Based on Finite Predicates and Implicative Regularities // In Diagnostic Test Approaches to Machine Learning and Commonsense Reasoning Systems. IGI Global. 2013. P. 1-12. DOI:10.4018/978-1-4666-1900-5.ch001

5. Mackworth A.K. Consistency in Networks of Relations // Artificial Intelligence. 1977. Vol. 8. No. 1. P. 99-118.

6. Mackworth A.K. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems // Artificial Intelligence. 1997. Vol. 8. P. 99-118.

7. Bessiere C. Using constraint metaknowledge to reduce arc consistency computation // Artificial Intelligence. 1994. Vol. 65. P. 179-190.

8. Régin J-C. A Filtering Algorithm for constraints of difference in CSPs. Proceedings AAAI-94. Seattle. Washington. 1994. P. 362-367.

9. Ruttkay Zs. Constraint satisfaction a survey // CWI Quarterly. 1998. Vol. 11. P. 163-214.

10. Régin J-C. Generalized arc consistency for global cardinality constraint. Proceedings of the Thirteenth National Conference on Artificial Intelligence. Portland. 1996. P. 209-215.

11. Rossi F., van Beek P. & Walsh T. Constraint Programming. In F. van Harmelen, V. Lifschitz, B. Porter (Eds.). Foundations of Artificial Intelligence. Handbook of Knowledge Representation. 2008. Vol. 3. P. 181-211.

12. Зуенко А.А. Вывод на ограничениях с применением матричного представления конечных предикатов // Искусственный интеллект и принятие решений. 2014. Вып. 3. С. 21-31.

13. Зуенко А.А., Очинская А.А. Эвристический метод удовлетворения ограничений на основе их матричного представления // Открытые семантические технологии проектирования интеллектуальных систем: материалы IV Междунар. научн.-техн. конф. (Минск, 19-21 февраля 2015 г.). Минск: Изд-во БГУИР. 2015. С. 297-302.