Yu.A. Slobodchikova1, A.V. Molchanov2, A.V. Zonova3, A.I. Lyalin4,  A.N. Nardid5, Yu.E. Gapanyuk6

1–6 Bauman Moscow State Technical University (Moscow, Russia)

Currently, the metagraph model is one of the most well-known and developing models of complex graphs. The metagraph model allows you to describe data, knowledge and processes, and changes in the model are made thanks to a rule-based metagraph agent. In this article, a metagraph model is understood as an “annotated metagraph model”, the main concept of which is the concept of a metavertex. A metavertex can include a nested fragment of a metagraph with nested vertices, metavertices, and edges.

The presence of metavertices of their own attributes and edges with other vertices is an important feature of metagraphs. This corresponds to the principle of emergence, that is, giving the concept a new quality, the irreducibility of the concept to the sum of its constituent parts. In fact, as soon as a new concept is introduced in the form of a metavertex, it “gets the right” to its own properties, edges, etc., since, in accordance with the principle of emergence, a new concept has a new quality and cannot be reduced to a subgraph of basic concepts.

The production model used in the metagraph agent is one of the most common models of knowledge representation. At the same time, if the knowledge base contains a large number of rules, then the task of effectively selecting rules for their implementation by the solver becomes urgent. An effective algorithm should select candidate rules for the next step of the solver's work, based on the results of the previous step of the solver's work. The criterion of effectiveness is to minimize the number of selected rules. The most well-known algorithms for solving this problem are the RETE, Treat and Leaps algorithms, while the Treat and Leaps algorithms are improvements of the basic RETE algorithm.

In the current version of the work, the RETE algorithm was implemented for the metagraph model in the basic version. The studies of the RETE algorithm have shown that the alpha network can be naturally represented using metagraph structures, which simplifies the implementation of a rule-based metagraph agent.

Slobodchikova Yu.A., Molchanov A.V., Zonova A.V., Lyalin A.I., Nardid A.N., Gapanyuk Yu.E. Features of the implementation of metagraph agents based on the production approach. Dynamics of complex systems. 2023. V. 17. № 3. P. 78−84. DOI: 10.18127/ j19997493-202303-11 (in Russian).

1. Gapanyuk Yu.E. Etapy razvitiya metagrafovoj modeli dannyh i znanij. Integrirovannye modeli i myagkie vychisleniya v iskusstvennom intellekte: Sbornik nauchnyh trudov X Mezhdunar. nauch.-tekhn. konf. IMMV-2021. V 2-h tomah. Smolensk: Universum. 2021. T. 1. S. 190–200 (in Russian).
2. Basu A., Blanning R.W. Metagraphs and Their Applications: Integrated Series in Information Systems (ISIS). New York: Springer, 2007. V. 15. № VIII. 172 p. DOI 10.1007/978-0-387-37234-1.
3. Myshenkov K.S., Nekula H. Ispol'zovanie metodov mashinnogo obucheniya dlya prognozirovaniya nevrologicheskih zabolevanij. Dinamika slozhnyh sistem – XXI vek. 2022. T. 16. № 1. S. 66–74. DOI 10.18127/j19997493-202201-07 (in Russian).
4. Massel' L.V., An G.V., Pesterev D.V. Realizaciya logicheskogo vyvoda v produkcionnoj ekspertnoj sisteme s ispol'zovaniem RETE-seti i relyacionnoj BD. Programmnye produkty i sistemy. 2020. № 4. S. 582–590 (in Russian).
5. CLIPS. A Tool for Building Expert Systems. URL: https://www.clipsrules.net (data obrashcheniya: 26.06.2023).
6. SWI-Prolog official site. URL: https://www.swi-prolog.org (data obrashcheniya: 26.06.2023).
7. Forgy C. Rete: a fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence. V. 19. № 1. P. 17–37. DOI 10.1016/0004-3702(82)90020-0.  
8. Doorenbos R.B. Production Matching for Large Learning Systems. USA, PA, Pittsburgh: Carnegie Mellon University, 1995. 208 p.
9. Wang Yu-W., Hanson E.N. A performance comparison of the Rete and TREAT algorithms for testing database rule conditions. Eighth International Conference on Data Engineering. USA, AZ, Tempe: IEEE. 1992. № 4286289. P. 88–97. DOI 10.1109/ICDE.1992.213202.
10. Batory D. The leaps algorithms: Technical report. USA, TX, Austin: University of Texas at Austin. 1994. 15 p.
11. Semenchenko I.I., Gapanyuk Yu.E., Revunkov G.I., Eliseev G.B. Realizaciya obrabotki metagrafov s ispol'zovaniem aktornogo podhoda. Dinamika slozhnyh sistem – XXI vek. 2019. T. 13. № 4. S. 36–45. DOI 10.18127/j19997493-201904-06 (in Russian).