Multi-agent systems - a couple of updates and a couple of examples.
I saw a topic about a multi-agent system and decided to add something on this topic. I’ll focus on 2 directions: how do the MAS differ from the classical systems (except parallelism, which nevertheless occurs not only in the MAS) and in two examples, practical and abstract-theoretical.
Modern software, for example, corporate level, incredibly difficult. The “scale factor” aggravates the matter - the larger the system, the faster its complexity grows as the number of connections between the parts grows.
MAS is one of the ways to simplify the system, as it allows to reduce the number of internal connections in the system (if you think about it, it can be said about almost any sufficiently autonomous AI system).
Originally, MAS appeared as distributed AI systems. In 1980, MIT hosted the first seminar on distributed AI problem solvers, which raised issues of effective coordination of many agents and demons, the development of a blackboard system, and a number of others. Some consider 1980 the year of birth of the MAS.
It is obvious that multi-agent systems are quite different from the classical systems. And, although the initial goal was exactly parallel processing of AI tasks, now the main focus is on separate processing (as opposed to parallel FIC, agents more often solve not identical tasks, including competing with each other, as can be seen from the example of sim-life) and "Social" behavior of agents. Interestingly, the MAS allow a person to be considered the same agent. Profit can be extracted from this when operators are gradually replaced by computer agents.
Clearer definitions:
So, learn the general principles. Now it's time to draw interesting conclusions about the qualities of MAS:
')
Logistics is one of the traditional and most developed areas of multi-agent systems. This is due to high efficiency (when using MAS, costs can be reduced up to several hundred percent compared to manual calculation). Efficiency is achieved due to the fact that in logistics there are a sufficiently large number of suppliers of goods and a sufficiently large number of consumers and, at the same time, they are ready to supply more than they consume. Consequently, the most dangerous for the MAS situation “dragon for limited resources” does not occur.
Agents in logistics are divided into suppliers, consumers and couriers. The task of each courier is the optimal load on the transport (so that the “truck” is exactly clogged by the volume / carrying capacity, so that empty flights are as small as possible, and better not at all) and route optimization (minimizing the route and time, although other parameters are possible). For example, the quality of the road surface, the frequency of police booths, etc.). The condition of work is the complete fulfillment of orders for delivery and the ability to take a sufficient amount of resources from suppliers.
Abstract example, in order to once again show the principles of work.
Usually, production planning is a complex and non-trivial task. It is necessary to provide all performers (both people and machines) with the necessary number of parts in time so that they can work in the most optimal way. At the same time, the result of the work of some performers affects the work of others directly (for work we need parts made earlier) and indirectly (for assembly of the product several types of parts are needed - if not one, the latter also cannot be continued to create uncontrollably). Manually counting all this is a hell of a job, especially if production is distributed. In the case of the use of multi-agent systems, everything is somewhat simplified: executing agents, courier agents (delivering products from one machine to another) are created, we specify the volumes and production schedule of products - and, in fact, everything. Agents first create successively chains of requests (perhaps, taking into account the level of marriage and some other features), providing each executor with tasks for the required volume and execution time, simultaneously expecting from the performers further along the chain of execution of their orders. Courier parameters set the size and number of parts transferred between performers at a time (you can carry three small items boxes or one big engine at a time - but not vice versa) In case someone broke, started a marriage or some other asteroid fell - production in the right places rescheduled (with an attempt to keep the obligations of the agents in force), and at some level it will not even be noticeable that something has broken somewhere. And there, where it will be noticeable, they will know about it almost at the time of the breakdown, and not when there will be no place to put semi-finished products.
It does not draw conclusions, the conclusion is also not, therefore there will be an “end”.
When writing this article, we used a wonderful book on the general issues of the Luger artificial intelligence systems, a little personal experience (did a small symLife) and a lot of different related material on distributed FIC. I would especially note a certain international company that is working on software for solving logistics problems with the help of MAS (from there, the basis for the example “logistics” is taken).Seeking. As soon as there is something - add here. Found it, sclerotic ... The company is called Magenta Technology (there is a “moderately Russian version” - click on the checkbox)
Literature:
George F. Luger Artificial Intelligence. Strategies and methods for solving complex problems. 4th edition .: Trans. from English - M .: Publishing house "Williams", 2003 - 846s.
Upd: I thank the respected film academy (I don’t know why, but it seems that way) my mother for having given birth to me and for UFOs because she flew in and gave me an invite))
High theory
A bit of banalism and history
Modern software, for example, corporate level, incredibly difficult. The “scale factor” aggravates the matter - the larger the system, the faster its complexity grows as the number of connections between the parts grows.
MAS is one of the ways to simplify the system, as it allows to reduce the number of internal connections in the system (if you think about it, it can be said about almost any sufficiently autonomous AI system).
Originally, MAS appeared as distributed AI systems. In 1980, MIT hosted the first seminar on distributed AI problem solvers, which raised issues of effective coordination of many agents and demons, the development of a blackboard system, and a number of others. Some consider 1980 the year of birth of the MAS.
General principles of work
It is obvious that multi-agent systems are quite different from the classical systems. And, although the initial goal was exactly parallel processing of AI tasks, now the main focus is on separate processing (as opposed to parallel FIC, agents more often solve not identical tasks, including competing with each other, as can be seen from the example of sim-life) and "Social" behavior of agents. Interestingly, the MAS allow a person to be considered the same agent. Profit can be extracted from this when operators are gradually replaced by computer agents.
Clearer definitions:
- situationality - means that the agent perceives the environment and can somehow change it. Everything that the agent can “feel” and everything with which he can interact (including other agents) is included in the surrounding world;
- autonomy - the agent can interact with the environment without the intervention of other agents;
- flexibility - responsiveness or forethought (depending on the situation) of the agent. Responsiveness implies that the agent responds to the environment in a timely manner and acts accordingly. Forethought assumes that the agent not only responds to changes in the environment, but also prepares for them in advance, adapts, chooses alternatives in various situations. Obviously, forethought is a more difficult task; responsiveness is characteristic of simpler agents;
- sociality - the agent must not only solve his narrow task alone, but also interact with the agents around him, solving together the more general task of the system. To do this, usually, agents build in interaction mechanisms (protocols) that allow agents to negotiate with each other to solve problems.
Features
So, learn the general principles. Now it's time to draw interesting conclusions about the qualities of MAS:
- “Agent” is a more general concept than “system”. Consequently, any part of a complex system can be represented as an agent. Without affecting the feasibility of considering the “Ok” button as an agent, I note that this makes it possible to universally consider the system as a whole — this gives the advantage of flexibility both in time (the example above replacing a human operator with a computer agent) and in the structure of the system.
- in general, agents do not need a “manager” to interact with each other. For this there are social protocols - they allow you to agree and organize the exchange of resources and data. However, this does not make it impossible to create an agent manager, with whom, as an IRL, you can reach an agreement, score on him and further on the list of “responsible employee behavior”.
- agents often do not have strict duties. The fact is that it is very difficult to achieve system stability with a large number of “very executive” agents (those who don’t believe — read about deadlocks when planning OS resources). For this reason, an agent can react to external requests in very different ways - from very fast and complete execution, to ignoring - depending on their internal considerations. In order to smooth out this lack of non-guaranteed service, social protocols are used. As a result, the disadvantage turns into a huge advantage - instead of breaking the head over the most complicated dispatching algorithms of a huge number of resources, we just give tasks, and the agents disassemble it themselves and decide how to deal with it and how to allocate resources. The disadvantages of this method are some uncertainty and the possibility, with a large load, the accumulation of queues. Queues are dealt with at the level of satisfying the needs of the system as a whole, and uncertainty is simply the other side of the fact that everything is decided between agents. In the end, everything turns out very beautiful.
Two examples
')
Logistics
Logistics is one of the traditional and most developed areas of multi-agent systems. This is due to high efficiency (when using MAS, costs can be reduced up to several hundred percent compared to manual calculation). Efficiency is achieved due to the fact that in logistics there are a sufficiently large number of suppliers of goods and a sufficiently large number of consumers and, at the same time, they are ready to supply more than they consume. Consequently, the most dangerous for the MAS situation “dragon for limited resources” does not occur.
Agents in logistics are divided into suppliers, consumers and couriers. The task of each courier is the optimal load on the transport (so that the “truck” is exactly clogged by the volume / carrying capacity, so that empty flights are as small as possible, and better not at all) and route optimization (minimizing the route and time, although other parameters are possible). For example, the quality of the road surface, the frequency of police booths, etc.). The condition of work is the complete fulfillment of orders for delivery and the ability to take a sufficient amount of resources from suppliers.
Candle Factory
Abstract example, in order to once again show the principles of work.
Usually, production planning is a complex and non-trivial task. It is necessary to provide all performers (both people and machines) with the necessary number of parts in time so that they can work in the most optimal way. At the same time, the result of the work of some performers affects the work of others directly (for work we need parts made earlier) and indirectly (for assembly of the product several types of parts are needed - if not one, the latter also cannot be continued to create uncontrollably). Manually counting all this is a hell of a job, especially if production is distributed. In the case of the use of multi-agent systems, everything is somewhat simplified: executing agents, courier agents (delivering products from one machine to another) are created, we specify the volumes and production schedule of products - and, in fact, everything. Agents first create successively chains of requests (perhaps, taking into account the level of marriage and some other features), providing each executor with tasks for the required volume and execution time, simultaneously expecting from the performers further along the chain of execution of their orders. Courier parameters set the size and number of parts transferred between performers at a time (you can carry three small items boxes or one big engine at a time - but not vice versa) In case someone broke, started a marriage or some other asteroid fell - production in the right places rescheduled (with an attempt to keep the obligations of the agents in force), and at some level it will not even be noticeable that something has broken somewhere. And there, where it will be noticeable, they will know about it almost at the time of the breakdown, and not when there will be no place to put semi-finished products.
the end
It does not draw conclusions, the conclusion is also not, therefore there will be an “end”.
When writing this article, we used a wonderful book on the general issues of the Luger artificial intelligence systems, a little personal experience (did a small symLife) and a lot of different related material on distributed FIC. I would especially note a certain international company that is working on software for solving logistics problems with the help of MAS (from there, the basis for the example “logistics” is taken).
Literature:
George F. Luger Artificial Intelligence. Strategies and methods for solving complex problems. 4th edition .: Trans. from English - M .: Publishing house "Williams", 2003 - 846s.
Upd: I thank the respected film academy (I don’t know why, but it seems that way) my mother for having given birth to me and for UFOs because she flew in and gave me an invite))
Source: https://habr.com/ru/post/71055/
All Articles