• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedUser profile (HSE staff only)SearchMenu

Studies and development of algorithms of solving distribution optimization tasks based on the multi-agent system theory

2009
Head: Kozyrev, Oleg
Department: Faculty of Business Informatics

This research is aimed at providing a means to solve a wide range of problems in the area of efficient management and decision-making theory based on the paradigm of the multi-agent system and the principles of distributed constraints satisfaction. In this field of knowledge, there is a great number of relevant optimization problems with complex multi-level distribution structures and the interaction of a large number of autonomous or dependent actors. At the same time, there are various sources and information consumers with their own purposes, world views and ways of interpreting semantic information.

The target of the research is models of complex distributed decision making processes and management in the form of multi-agent and service-oriented program systems.

The purpose of the work is to develop both theory and practice for solving distributed constraints satisfaction and optimization problems using a combination of a formal concept of the subject field, the constraints and rules of corporate security and software architecture in the form of ontologies as well as advanced software tools of multi-agent technologies.

During the research, we have analyzed algorithms of knowledge representation, methods of solving logistic timetable problems; developed methods of multi-agent optimization and formal verification of business processes based on formalisms of relational logics.

In the research work, we have demonstrated that the search for efficient ways of processing users’ preferences while taking into account the distributed nature of the problem using multi-agent technologies and subject ontologies is a relevant field of study. Analysis of existing methods of multi-agent optimization and planning showed that the most interesting field is further development of algorithms based on the paradigm of dynamic meeting schedule planning for multiple participants. This is an area which has not been studied before.

The mathematic model built in this work, based on multi-agent interactions and constraints, is the foundation for the practical realization of distributed algorithms for constructing school/university timetables and solving other classes of logistical problems. For declarative description of the DSCP structure we used an ontology of constrains that determines the formal specification of the structure and behavior of multi-agent system in terms of proposed CACS computer model. Software realization of algorithms of XML specification transformation into JAVA software class samples facilitates the automated transformation of the formed ontology into the specification of distributed algorithms of constraint satisfaction.

As part of this research work, we have analyzed a promising area of building multi-agent systems based on service-oriented architecture. To solve the problems of integration automation and increased security, we proposed a method of business process formal verification using subject ontology and analyzed it using a practical example.

As the main conclusion of our research work, we note the high potential viability of using a specialized formal logics dialect of Relation Logic and specific realization of Alloy Analyzer for determining corporate security policies in distributed systems.

As a result of the research, we have developed a new computer model and software system architecture for resolving constraints in multi-agent systems in solving optimization problems as well as new methods of semantic composition of services using knowledge in the form of ontologies and taking into account corporate security rules.

We have realized software prototypes for the proposed computer model and architecture of multi-agent system to solve decision making support problems in a specific class of logistical problems (timetable construction). We have successfully tested the proposed methods of semantic service integration using real business processes as an example. We have developed formal ontologies for specifying optimization problems and business process management.