September 30, 2009 at 14:30Multi-agent systems - a couple of refinements and a couple of examples
I saw a topic about multi-agent systems and decided to add something on this topic. I will focus on 2 directions: how MASs differ from classical systems (except for parallelism, which nevertheless occurs not only in MASs) and two examples, practical and abstract-theoretical.
Modern software, for example, at the enterprise level, is incredibly complex. 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 you to reduce the number of internal connections in the system (if you think about it, this can be said about almost any fairly autonomous AI system).
MAS initially appeared as distributed AI systems. In 1980, the first seminar on the topic of distributed AI problem solvers was held at MIT, which raised the issues of effective coordination of many agents and demons, the development of a blackboard system and several others. Some consider 1980 the birth of the MAC.
Obviously, multiagent systems are quite different from classical systems. And, although the initial goal was precisely parallel processing of AI tasks, now the main emphasis is on separate processing (unlike parallel FIR, agents often solve not the same tasks, including competing with each other, as is seen in the example of sim-life) and "Social" behavior of agents. Interestingly, MAS allows us to consider a person as the same agent. Profit can be derived from this when there is a gradual replacement of operators with computer agents.
Clearer definitions:
So, we learned the general principles. Now it's time to draw interesting conclusions about the qualities of the MAC:
Logistics is one of the traditional and most developed areas of multi-agent systems. This is due to great efficiency (when using MAS, costs can be reduced to several hundred percent in comparison with manual calculation). Efficiency is achieved due to the fact that in logistics there is 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 situation for the MAS “brawls for limited resources” does not occur.
Agents in logistics are divided into suppliers, consumers and couriers. The task of each courier is to optimize the load on the transport (so that the “truck” is exactly packed by the volume / load capacity, so that there are as few empty flights as possible, and better not at all) and route optimization (minimizing the path and time, although other parameters are possible for example, the quality of the road surface, the frequency of police booths, etc.). The condition for work is the full implementation of delivery orders and the ability to take a sufficient amount of resources from suppliers.
An abstract example, in order to once again show the principles of work.
Usually, production planning is a difficult and non-trivial task. It is necessary to provide all the performers (both people and machines) with the necessary number of parts on 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 (parts that were previously produced are required for work) and indirectly (several types of parts are needed to assemble the product - if there are none, then the second ones cannot be continued to be created without restraint). Manually calculating all this is hellish work, especially if the production is distributed. In the case of using multi-agent systems, everything is somewhat simplified: executing agents, courier agents (delivering products from one machine to another) are created, we set the volumes and production schedule of the products - and, in fact, that’s all. Agents first sequentially create a chain of requests (perhaps, given the level of marriage and some other features), providing each performer with tasks for the required volume and time of execution, while simultaneously waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. the level of marriage and some other peculiarities), providing each performer with tasks for the required volume and time of execution, while at the same time waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. the level of marriage and some other peculiarities), providing each performer with tasks for the required volume and time of execution, while at the same time waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. providing each performer with tasks for the required volume and time of execution, while at the same time waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. providing each performer with tasks for the required volume and time of execution, while at the same time waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products.
This does not draw conclusions, it is not a conclusion either, therefore there will be an “end".
When writing this article, I used a wonderful book on the general issues of Luger artificial intelligence systems, a little personal experience (I made a small symlife) and a lot of different related material on the problems of distributed SII. I will especially note a certain international company that is working on software to solve logistics problems using MAS (the basis for the example of “logistics” is taken from there).Seeking. As soon as there is something, I will add it here. Found sclerosis ... The company is called Magenta Technology (there is a "moderately Russian version" - click on the flag)
References:
George F. Luger Artificial Intelligence. Strategies and methods for solving complex problems. 4th edition .: Per. from English - M.: Williams Publishing House, 2003 - 846s.
Upd: I thank the reputable film academy (I don’t know why, but it’s kind of supposed to) my mother for giving birth to me and raising me and for UFOs for flying in and inviting me))
Highbrow theory
A bit of triviality and history
Modern software, for example, at the enterprise level, is incredibly complex. 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 you to reduce the number of internal connections in the system (if you think about it, this can be said about almost any fairly autonomous AI system).
MAS initially appeared as distributed AI systems. In 1980, the first seminar on the topic of distributed AI problem solvers was held at MIT, which raised the issues of effective coordination of many agents and demons, the development of a blackboard system and several others. Some consider 1980 the birth of the MAC.
General principles of work
Obviously, multiagent systems are quite different from classical systems. And, although the initial goal was precisely parallel processing of AI tasks, now the main emphasis is on separate processing (unlike parallel FIR, agents often solve not the same tasks, including competing with each other, as is seen in the example of sim-life) and "Social" behavior of agents. Interestingly, MAS allows us to consider a person as the same agent. Profit can be derived from this when there is a gradual replacement of operators with 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 it can interact (including other agents) are included in the surrounding world;
- autonomy - an agent can interact with the environment without the intervention of other agents;
- flexibility - responsiveness or prudence (depending on the situation) of the agent. Responsiveness assumes that the agent is responsive to the environment in a timely manner and acts accordingly. Prudence assumes that the agent not only reacts to environmental changes, but also prepares for them in advance, adapts, selects alternatives in various situations. Obviously, prudence is a more complex task; responsiveness is characteristic of simpler agents;
- sociality - the agent must not only solve his narrow task alone, but also interact with the agents surrounding him, solving together the more general task of the system. To do this, usually, agents (mechanisms) of interaction are built into agents that allow agents to negotiate with each other to solve problems.
Features
So, we learned the general principles. Now it's time to draw interesting conclusions about the qualities of the MAC:
- “Agent” is a more general concept than “system”. Therefore, any part of a complex system can be represented as an agent. Without affecting the appropriateness of considering the “OK” button as an agent, I note that this allows you to universally consider the system as a whole - it gives the advantage of flexibility both in time (the above example with the replacement of a human operator by a computer agent) and in the structure of the system.
- in general, agents do not need a “manager" to interact with each other. There are social protocols for this - 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 negotiate, score on him and then on the list of “responsible employee behavior”.
- agents often do not have strict responsibilities. The fact is that achieving system stability with a large number of "very executive" agents is very difficult (who does not believe - read about deadlocks when planning OS resources). For this reason, an agent can react very differently to an external request - from very fast and complete execution to ignoring - depending on its internal considerations. In order to mitigate this lack of non-guaranteed service, social protocols are used. As a result, the disadvantage turns into a huge advantage - instead of racking our brains over the most complicated scheduling algorithms for a huge number of resources, we simply give tasks, and the agents themselves disassemble it and decide for themselves what to do with it and how to allocate resources. The disadvantages of this method are some uncertainty and possibility, under heavy load, the accumulation of queues. Queues are handled 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. As a result, everything turns out very beautifully.
Two examples
Logistics
Logistics is one of the traditional and most developed areas of multi-agent systems. This is due to great efficiency (when using MAS, costs can be reduced to several hundred percent in comparison with manual calculation). Efficiency is achieved due to the fact that in logistics there is 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 situation for the MAS “brawls for limited resources” does not occur.
Agents in logistics are divided into suppliers, consumers and couriers. The task of each courier is to optimize the load on the transport (so that the “truck” is exactly packed by the volume / load capacity, so that there are as few empty flights as possible, and better not at all) and route optimization (minimizing the path and time, although other parameters are possible for example, the quality of the road surface, the frequency of police booths, etc.). The condition for work is the full implementation of delivery orders and the ability to take a sufficient amount of resources from suppliers.
Candle factory
An abstract example, in order to once again show the principles of work.
Usually, production planning is a difficult and non-trivial task. It is necessary to provide all the performers (both people and machines) with the necessary number of parts on 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 (parts that were previously produced are required for work) and indirectly (several types of parts are needed to assemble the product - if there are none, then the second ones cannot be continued to be created without restraint). Manually calculating all this is hellish work, especially if the production is distributed. In the case of using multi-agent systems, everything is somewhat simplified: executing agents, courier agents (delivering products from one machine to another) are created, we set the volumes and production schedule of the products - and, in fact, that’s all. Agents first sequentially create a chain of requests (perhaps, given the level of marriage and some other features), providing each performer with tasks for the required volume and time of execution, while simultaneously waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. the level of marriage and some other peculiarities), providing each performer with tasks for the required volume and time of execution, while at the same time waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. the level of marriage and some other peculiarities), providing each performer with tasks for the required volume and time of execution, while at the same time waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. providing each performer with tasks for the required volume and time of execution, while at the same time waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. providing each performer with tasks for the required volume and time of execution, while at the same time waiting from the performers further along the chain of execution of their orders. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. Courier parameters specify the size and number of parts transferred at a time between the performers (you can transport three small boxes at a time or one large engine - but not vice versa) In case someone breaks down, makes a marriage or some other asteroid crashes - production in the right places it is being rescheduled (with an attempt to keep the obligations of agents in force), and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products. and at some level it will not even be noticeable that somewhere something has broken. And where it will be noticeable, they will find out about this almost at the time of the breakdown, and not when there is nowhere to put the semi-finished products.
the end
This does not draw conclusions, it is not a conclusion either, therefore there will be an “end".
When writing this article, I used a wonderful book on the general issues of Luger artificial intelligence systems, a little personal experience (I made a small symlife) and a lot of different related material on the problems of distributed SII. I will especially note a certain international company that is working on software to solve logistics problems using MAS (the basis for the example of “logistics” is taken from there).
References:
George F. Luger Artificial Intelligence. Strategies and methods for solving complex problems. 4th edition .: Per. from English - M.: Williams Publishing House, 2003 - 846s.
Upd: I thank the reputable film academy (I don’t know why, but it’s kind of supposed to) my mother for giving birth to me and raising me and for UFOs for flying in and inviting me))