Lecture 23 min.
A multi-agent system (MAS) is a system formed by several interacting intelligent agents. Multi-agent systems can be used to solve problems that are difficult or impossible to solve with a single agent or a monolithic system. Examples of such tasks are online trading, disaster response, and the modeling of social structures.
Intelligent multi-agent systems are one of the new and promising directions of artificial intelligence, which took shape on the basis of research results in the field of distributed computer systems, network problem-solving technologies and parallel computing. Multi-agent technologies are built on the principle of autonomy of the individual parts of a program that operate jointly within a distributed system in which many interrelated processes run at the same time. Such programs are called agents.
Examples of tasks solved with the help of a MAS are:
An agent is an autonomous artificial object, usually a computer program, that possesses active motivated behavior and is capable of interacting with other objects in dynamic virtual environments. Each agent can receive messages, interpret their content and compose new messages, which are either placed in a common database or sent to other agents.
Intelligent agents have the following basic properties:
· autonomy — the ability to function without intervention on the part of its owner and to control its own actions and internal state;
Other qualities are sometimes added to this list, including:
Classification of agents
Two main criteria are used to classify agent programs: 1) the degree of development of the internal representation of the external world; 2) the method of decision making.
The simplest kind of agent is the simple reflex agent. Agents of this kind choose actions on the basis of the current perception of the state of the environment, ignoring all the rest of the perception history. Simple reflex agents are extremely simple, but they possess limited intelligence.
Figure 11.1 – Structure of a simple reflex agent.
Under conditions of partial observability, the agent must keep track of changes in the environment. This means that the agent must possess a set of internal states whose transitions depend on the perception history.
Figure 11.2 shows the structure of an agent that acts with allowance for its internal state. The current perception is combined with the previous internal state, as a result of which actions are performed and the internal state changes.
Figure 11.2 – An agent that acts with allowance for its internal state.
Knowledge of the current state of the environment is not always sufficient for decision making. In that case the agent needs not only a description of the current state, but also information about the goal, which describes the desired situations. The structure of a goal-based agent is shown in Figure 11.3. It monitors the state of the environment as well as the set of goals it is trying to achieve, and selects an action directed at achieving those goals.
Figure 11.3 – Structure of a goal-based agent.
Situations often arise in which information about goals alone is not sufficient for decision making. First, when there are conflicting goals such that only some of them can be achieved (for example, either speed or safety). Second, when there are several goals that the agent may pursue, but each of them can be achieved only with a certain probability of success. In this case a utility function is introduced into the agent program, which assigns to the states of the agent a real number expressing the expected utility of the given state. The agent selects the action that leads to the best expected utility.
Figure 11.4 – Structure of a model-based, utility-based agent.
Learning agents are singled out as a special class. Learning has an important advantage: it allows an agent to function in variants of the environment that were initially unknown to it and to become more competent than its initial knowledge alone would have permitted.
The structure of a learning agent is divided into four conceptual components, as shown in Figure 11.5. The performance component may be any of the agent-program structures considered earlier. The learning component uses feedback information from the critic about how the agent is acting and determines how the performance component should be modified so that it will act more successfully in the future.
Figure 11.5 – Structure of a learning agent.
The critic tells the learning component how well the agent is acting with respect to a fixed performance standard, since the percepts themselves give no indication of whether the agent is acting successfully. This standard must be regarded as entirely external to the agent, because the agent must not be able to modify it. For example, a chess program may receive percepts indicating that it has checkmated its opponent, but it needs a performance standard that would allow it to determine that this is a good outcome, since the percept data themselves say nothing about that.
The last component of a learning agent is the problem generator. Its task is to suggest actions that should lead to new and informative experience. The point is that if the performance component is left to itself, it will go on performing the actions that are best according to what it knows. But if the agent is prepared to experiment a little and to perform actions in the short term that may turn out to be less than optimal, it may discover better actions in the long run.
Interaction between agents is the main feature of MAS that distinguishes them from other intelligent systems. The principal characteristics of any interaction are its orientation, selectivity, intensity and dynamism. In the context of MAS these notions may be interpreted as follows:
The basic types of interaction between agents are:
Interaction between agents is driven by a number of causes, the most important of which are the following.
Compatibility of goals (a common goal). This cause usually gives rise to interaction of the cooperative, or collaborative, type. Here one should determine whether the interaction reduces the viability of individual agents. Incompatibility of goals or beliefs usually gives rise to conflicts, whose positive role lies in stimulating processes of development. The well-known predator-prey model is an example of simultaneous interaction of two types at once, cooperation and confrontation.
Shared resources. By resources we shall mean any means used by agents to achieve their goals. The scarcity of resources used by many agents usually gives rise to conflicts. One of the simplest and most effective ways of resolving such conflicts is the right of the strong: a strong agent takes resources away from weaker ones. Subtler ways of resolving conflicts are provided by negotiations aimed at reaching compromises in which the interests of all agents are taken into account. The problems of allocating market shares, costs and profits of joint ventures can be regarded as examples of interaction driven by shared resources.
The need to draw on expertise that is lacking. Every agent possesses only a limited body of knowledge required to fulfill its own goals and common goals. For this reason it has to interact with other agents. Various situations are possible here: a) the agent is able to perform the task on its own; b) the agent can manage without outside help, but cooperation will allow the task to be solved more efficiently; c) the agent is unable to solve the task alone. Depending on the situation, agents choose the type of interaction and may display different degrees of interest in collaboration.
Mutual obligations. Obligations are one of the instruments that make it possible to bring order to the chaotic interactions of agents. They make it possible to anticipate the behavior of other agents, to forecast the future and to plan one's own actions. The following groups of obligations can be distinguished: a) obligations to other agents; b) obligations of an agent to a group; c) obligations of a group to an agent; d) obligations of an agent to itself. The formal representation of goals, obligations, desires and intentions, as well as of all the other characteristics, forms the basis of the mental model of an intelligent agent, which provides for its motivated behavior in autonomous mode.
In various combinations, the causes listed above can lead to different forms of interaction between agents, for example:
Modeling the collective work of agents raises a host of problems:
A distinctive feature of the collective behavior of agents is that their interaction while solving particular tasks (or one common task) gives rise to a new quality in the solution of these tasks. Models of agent behavior coordination rely on the following main ideas:
1. Abandoning the search for the best solution in favor of a "good" one, which leads to a shift from a procedure of strict optimization to the search for an acceptable compromise that implements one or another principle of coordination.
2. Using self-organization as a robust mechanism for forming collective behavior.
3. Applying randomization (a random-probabilistic way of choosing solutions) in coordination mechanisms in order to resolve conflicts.
4. Implementing reflexive control, the essence of which is to make a subject deliberately submit to outside influence, that is, to form in it such desires and intentions as coincide with the requirements of its environment.
The best-known models of agent behavior coordination are: game-theoretic models, models of the collective behavior of automata, models of collective behavior planning, models based on BDI architectures (Belief — Desire — Intention), and models of behavior coordination based on competition.
Game-theoretic models.The subject of game theory is the problem of choosing decisions under conditions of uncertainty and conflict. The presence of a conflict presupposes the existence of at least two participants, who are called players. The set of decisions available for each player to choose from is called a strategy.Equilibrium points of a game (optimal solutions) are states in which it is not advantageous for any of the players to change position. The notion of equilibrium has proved to be very useful in the theory of MAS, since the mechanism for finding equilibrium situations can be used as a means of self-organizing the collective behavior of agents. A consequence of such an interpretation is an approach in which the required attributes of collective agent behavior are provided by designing the rules of the game. In addition, on the basis of developments in game theory, attempts are being made in the field of MAS to build efficient, robust, fully distributed negotiation protocols aimed at coordinating the collective behavior of agents.
Models of the collective behavior of automata. These are based on the ideas of randomization, self-organization and full distribution. Models of this type are suitable for building negotiation protocols in tasks characterized by a large number of very simple interactions with unknown characteristics.
Models of collective behavior planning. Planning may be centralized, partially centralized or distributed. In the last case the agents themselves decide which actions to choose in the course of coordinating their individual plans, which raises questions about rational decentralization, about the possibility of changing goals when conflicts arise, and also problems of computational complexity.
Models based on BDI architectures. Models of this class employ the axiomatic methods of game theory and the logical paradigm of artificial intelligence. The emphasis is on describing substantive notions such as beliefs, desires and intentions. The problem of coordinating agent behavior is solved by reconciling the results of logical inference in the knowledge bases of the individual agents, obtained for the current state of the external environment in which the agents operate. Inference is carried out directly while the agents are running, which leads to high model complexity, computational difficulties and problems associated with the axiomatic description of non-trivial situations, for example when an agent faces a choice between solving its own task and fulfilling its obligations toward its partners.
Models based on competition. Models of this class use the notion of an auction as a mechanism for coordinating agent behavior. The use of the auction mechanism rests on the assumption that "utility" can be explicitly transferred from one agent to another or to an auctioneer agent, and this utility usually has the meaning of money.
Auctions are conventionally divided into open and sealed ones. In the first case the prices offered are announced to all participants. In a sealed auction only the auctioneer knows the prices offered. Open auctions differ in the way they are conducted. In so-called English auctions a starting price is usually set, which the participants may raise in the course of the bidding. The winner is the one who offers the highest price. A Dutch auction begins with a high price that is gradually lowered. The winner is the one who offers the highest current price. Sealed auctions are divided into first-price and second-price auctions. In first-price auctions the winner is the one who has offered the highest price, known only to the auctioneer. In second-price auctions the winner is determined in the same way, but pays for the goods not the price it offered but the second-highest one.
The auction mechanism in itself does not prescribe how the participants make their decisions. Decisions may be made on the basis of some reasoning model, which may draw on various types of knowledge available to the agents and on a variety of ways of processing that knowledge.
An auction must always terminate. To ensure this, the strategy for conducting it must provide means for resolving possible conflicts (for example, when there are several winners). One of the simplest ways of resolving conflicts is randomization, in which a random selection mechanism is applied.
Let us consider practical examples of organizing interaction in multi-agent systems using various mechanisms for coordinating behavior.
Electronic store.Consider a typical e-commerce problem involving seller agents and buyer agents. Trading takes place in an electronic store, which is a program hosted on a server. Its main purpose is to organize interaction between agents whose interests coincide. The agents act on behalf of their individual users. Seller agents seek to sell their goods at the highest possible price, while buyer agents seek to buy the goods they need at the lowest price. Both kinds of agents act autonomously and have no cooperative goals. The electronic store registers the appearance and disappearance of agents and arranges contacts between them, making them "visible" to one another.
Figure 11.6 – Diagram of an electronic store.
The behavior of a seller agent is characterized by the following parameters:
The buyer agent has "symmetrical" parameters:
Bidding follows the scheme of a first-price sealed-bid auction. The behavior of the agents is described by a simple model that uses neither knowledge nor reasoning. Having received information from the electronic store about potential buyers of its goods, the seller agent polls them all in turn in order to decide whether a deal can be made. The deal is concluded with the first buyer agent that is willing to pay the asking price for the goods. The seller cannot contact any buyer a second time until it has polled all the potential buyers. At each contact the seller agent negotiates, offering an initial price or lowering it. The buyer agent behaves in a similar way, seeking out sellers of the goods it needs and offering them its purchase price, which it may raise during the negotiations. Any deal is completed only if it is approved by the agent's user.
This negotiation scheme is the simplest case of interaction between autonomous agents acting reactively. Nevertheless, the resulting behavior of the system is quite adequate to reality.
Virtual enterprise.The creation of virtual enterprises is one of the modern directions in business, stimulated to a considerable extent by the rapid growth of information resources and services available on the Internet. In addition, the emergence of virtual enterprises is encouraged by the shortening life cycle of the products being created and by their increasing complexity, since this gives rise to a need to combine manufacturing, technological and intellectual resources promptly. Another important reason is intensifying competition in commodity markets, which prompts enterprises to join forces in order to survive.
A virtual enterprise can be defined as a cooperation of legally independent enterprises, organizations and individuals that produce goods or services within a common business process. To the outside world a virtual enterprise appears as a single organization employing management and administration methods based on information and telecommunication technologies. The purpose of creating a virtual enterprise is to combine manufacturing, technological, intellectual and investment resources in order to bring new goods and services to market.
Since each real enterprise within a virtual one performs only part of the work in the overall technological chain, two main problems are solved when a virtual enterprise is created. The first is the decomposition of the overall business process into components (sub-processes). The second problem consists in selecting a rational set of real partner enterprises that will carry out the technological process. The first problem is solved using systems analysis methods, while multi-agent technologies can be applied to the second.
The problem of optimally distributing a set of jobs (sub-processes) among a set of workers (real enterprises) is formulated in operations research as the assignment problem. Its solution begins with forming the sets of sub-processes and of potential participating enterprises. Possible mappings from the set of participants onto the set of sub-processes are then constructed, and the most acceptable mapping is selected, corresponding to specific assignments of enterprises to business processes. An auction mechanism can be used for this. Figure 7.2 shows the scheme of an auction for creating a virtual enterprise, in which the business processes A, B, C, D, E have been identified and four enterprises take part: P1, P2, P5, P4, competing to implement them. Each of the enterprises is represented by an intelligent agent, one of them (Px) acting as the initiator (auctioneer).
Figure 11.7 – Scheme for creating a virtual enterprise.
Before the auction begins, the auctioneer (manager) builds a database and a knowledge base about the auction participants. It then puts individual business processes up for sale; the information about them is given by a starting price and by requirements on a specified set of indicators. Each competitor puts forward its own proposals for the parameters it is able to provide, together with its price. Having collected and processed these proposals, the auctioneer uses some reasoning model to rank the potential competitors, taking into account its own information about them. After that it decides on the choice of assignments, or rejects them and puts forward new proposals.
It should be noted that the problem of creating a virtual enterprise can be classed among the problems of structural synthesis of complex systems that satisfy given requirements.
MAS also belong to the class of self-organizing systems, since they search for the optimal solution to a problem without external intervention. By an optimal solution is meant a solution on which the least amount of energy has been expended under conditions of limited resources.
The main advantage of MAS is flexibility. A multi-agent system can be extended and modified without rewriting a significant part of the program. These systems are also capable of self-healing and are resilient to failures, thanks to a sufficient reserve of components and to self-organization.
Multi-agent systems are used in our everyday life in graphics applications, for example in computer games. Agent systems have also been used in films. MAS theory is used in composite defense systems. MAS are also applied in transport, logistics, computer graphics, geographic information systems, robotics and many other fields. Multi-agent systems have proven themselves well in the field of network and mobile technologies, for providing automatic and dynamic load balancing, scalability and the capacity for self-healing.
Comments