Multiagent System - Appunti

Multiagent Systems

January 2023
Prof. Francesco Amigoni
Appunti di Simone Tognocchi

01 Introduction

An agent has the following properties:

• Autonomy: It can work without human help.
• Reactivity: It can react to everything that happens in the environment.
• Pro-activeness: It must be able to take initiative to achieve the predefined objectives, also without external stimuli.
• Sociality: It must be able to interact with other agents, or with human beings.

A rational agent: It must be able to choose the action that maximizes the expected value of its performance measure, given its knowledge up to that moment, for every possible sequence of perceptions. It’s not omniscient, clairvoyant, and can explore to acquire new information and can learn. An agent chooses the action in order to reach a goal or maximize the performances, like utility.

An Environment can be:

• Completely (chess) or partial (poker) observable.
• Static (changes only when the agent acts) or dynamic (changes even if the agent is thinking).
• Discrete (described by discrete time, or variables) or continuous (described with continuous time or variables).
• Single agent or multiagent.

The Action made by the agent can be deterministic (if I know what will happen after my action, like for chess), or stochastic (if I don’t know what will happen after my action).

The Performance measure is the criterion for evaluating the success of the behavior of an agent and it’s defined by the designer.

We can implement an agent in three ways:

• Rules: If something happens, do something. Can be written by the designer or can learn.
• Plans: You imagine performing different actions and then you perform the ones that maximize the performances or that make you reach the goal.
• Policies: The agent decides what action to perform based on its reasoning on the current state and on its goals.

There exist 4 types of agent architectures (in the pictures the blue box represents processing and the yellow knowledge):

• Simple reflex agents: Like NN or the first version of Roomba. They perceive the environment, process the perceptions, and decide what to do according to if-then statements and then they do it.
• Reflex agents with state: Like the Dyson 360 Eye. They keep track of the environment’s states.
• Goal-based agents: Like robots with a goal, or game solvers, like Tris. They imagine what will happen if they perform some actions (every state is seen as good if it takes you to the goal or bad if it doesn’t).
• Utility-based agents: Like autonomous cars. They imagine possible sequences of actions and use the utility to evaluate (with a real number) every state.

All these agents can improve their performances with learning. Every component of the decisional process can be modified in order to perform better.

Multiagent systems: Systems that can interact with each other or with the environment. They are divided into two classes:

• Cooperative systems (benevolent agents)
• Competitive systems (selfish agents)

Other types of interactions are coordination, negotiation, elections, task allocation, distributed optimization, emerging behavior, etc.

Coordination: Selecting actions that do not interact with negative effects. They can be of 3 types:

• Pre-programmed: Like in space satellites that know where everyone goes.
• Convention-based: If the agent has to follow some rules, like cars that have to give the priority to the ones on their right.
• Communication-based: Agents communicate between them to work together.

Coordination also can be divided into:

• Centralized: When there is a supervisor that decides for everyone and communicates to them what to do, in order to find an optimal solution.
• Distributed: The agents talk only with their neighbors, it’s not possible to find an optimal solution.

Problems can be:

• Micro problem: How to design individual agents able to act autonomously in order to reach a goal.
• Macro problem: How to design systems in which more agents interact in a useful way.

The agent architecture can be reactive (reacts to the environment, without maintaining any internal representation of the world), deliberative (agents maintain an internal representation of the world and plan actions based on that) or hybrid. The interaction mechanisms between agents can be: planning, coordination, matchmaking, auctions, negotiations, strategies, etc.

02 Agent Architectures

In this part, we focus on the micro problem. We want to build agents that enjoy the properties of autonomy, reactiveness, pro-activeness, and social ability.

The agent architecture can be defined as: the agent can be decomposed into the construction of a set of component modules and how these modules should be made to interact. They have to provide an answer to the question of how the sensor data and the current internal state of the agent determine the actions and future internal state of the agent.

Reasoning agents: We see agents as knowledge-based systems. This paradigm is known as symbolic AI. A deliberative agent is the one that contains an explicitly represented, symbolic model for the world and makes decisions (what action to perform) via symbolic reasoning.

To get the deliberative agent to realize some theory, we have to give him the representation of this theory in rules, or symbolic knowledge. Then there are two important problems to solve:

• Transduction problem: Translate the real world into an accurate, adequate symbolic description (solved working on vision, learning, speech understanding, etc).
• Representation/reasoning problem: How to symbolically represent information about complex real-world entities and processes and how to get agents to reason with this information in time for the results to be useful.

These kinds of problems seem to be trivial, but are extremely difficult: many search-based symbol manipulation algorithms are intractable.

Planning agents: Is the design of a course of actions (the plan) that will achieve some desired goal (e.g., Shakey the robot or moving block algorithm). The reasoning is complex, so it’s not scalable.

Reactive architectures: These architectures have been created believing that the assumptions made in mainstream AI were wrong. Brooks' theses are:

• Intelligent behavior can be generated without explicit representations proposed by symbolic AI.
• Intelligent behavior can be generated without explicit abstract reasoning proposed by symbolic AI.
• Intelligence is an emergent property of certain complex systems.

He had two key ideas:

• Situatedness and embodiment: Real intelligence is situated in the world, so agents must be situated in the real world.
• Intelligence and emergence: Intelligent behaviors arise as a result of an agent’s interaction with its environment, it’s not one of its innate properties.

Brooks built a subsumption architecture, which is a hierarchy of task-accomplishing behaviors. Each behavior is a rather simple rule-like structure and competes with others to exercise control over the agent. The lower layers are more primitive kinds of behaviors, like avoiding obstacles, and have precedence over the further up in the hierarchy. These kinds of systems are computationally extremely simple.

Steels created a Mars explorer system using the subsumption architecture, which had the objective to explore a distant planet and to collect a precious rock. It doesn’t know the location of the samples but knows that they are clustered. Its behavior was:

• Obstacle avoidance (lowest layer).
• Path attraction: if you see a heavily trodden path, follow it away from the spaceship.
• Explore movement: if I have no samples, move away from the spaceship.
• Return movement: if I have samples and I can’t see any denser concentration, then head towards the spaceship.

Markov Decision Processes:

We can use search to solve problems only in deterministic domains (e.g., A* doesn’t work in stochastic environments). So we introduce MDPs for encoding problems in stochastic environments. An MDP is an architecture that is a mix between planning and reactive.

An MDP can be defined formally as M = (S, A, T, R) where:

• S is the state set.
• A is the action set.
• T: S x A x S -> R is the transition function: the probability of going from s to s’ when executing action a (the sum for a state s to go to all the states s’ of S is 1).
• R: S x A -> R is the reward function.

The goal is to perform actions in order to maximize the future rewards. The strategy of the agent is called policy.

A policy can be:

• Deterministic: π(s): S --> A the agent will always perform the same action from a given state.
• Stochastic: π(s,a): S x A --> R the agent selects an action to execute by drawing from a probability distribution encoded by the policy.

In MDP we use the Markov assumptions, so X depends only on X_t and not on X_t-1, X_t-2, etc.

Expecting future rewards:

The problem with this formulation is that it can grow to infinity. Two possible solutions are: if gamma is 0 we are looking only to the next reward, if it’s close to 1 we are looking very far.

Value function V(s): Is the expected discounted reward that an agent expects to gain if he acts optimally starting from state s. The game plan is:

1. Calculate the optimal value function.
2. Calculate the optimal policy from the optimal value function.

In order to calculate the optimal value function, we use value iteration. Let’s focus on the update rule: this is the Bellman Equation (the equation is written without the i because it’s not an update rule). It can be proven that this V will converge to the optimal value.

Value iteration is a slow method: O(S² A) per iteration, the max rarely changes at each state and the policy converges after a long time. Another formulation of the Bellman Equation is the one used in the example: now we have to understand when we stop the algorithm. We will stop when the maximum of all the values is very little, so:

This is called the Termination Condition. We use this formula because it can be proven that when we stop the error that we have will be:

So the values that we have found are approximately the same as the optimal. Of course, if we choose a little epsilon we will find better values, but the convergence will be slower. So we set epsilon doing a trade-off between the quality of the solution and time. The more gamma is small, the easier it is to converge.

Given the optimal value function V* we can calculate the optimal policy:

If we don’t know V*(s_i) we can calculate them by making a system that has n equations and n unknown variables. The problem is that the equations are not linear because they contain the max function, so we have to make assumptions to solve it (assume that one equation is greater than another one). Then we have to verify that the assumptions were correct and if they were not, we have to change them.

Game Theory

The basic model for games is the Normal Form Representation: (N, A, U), where N are the players, A the actions, and U the utilities.

The two players zero-sum games are games with 2 players and the sum of the utilities equal to 0 for each couple of actions (in the picture Rock-Paper-Scissor modeled as a 0-sum game). This kind of games are solvable with linear programming.

Another type of games, more general, is the two players general-sum game (in the picture the Bach or Stravinsky concert game, with two players and the utilities that are not 0-sum). When we have more than 2 players, it has no sense to have a 0-sum game.

To solve this kind of problem we use strategies: G_i: A_i --> [0,1] that represents the probability that every action will be played.

For example, we can have a mixed strategy: in Rock-Paper-Scissor we have 1/3 for every action (we are randomizing the strategy). Or we can also have a pure strategy, for example in Rock-Paper-Scissor we can have 1 for Paper and 0 for the other two. Of course, the sum of the probabilities for all the actions must be 1.

Then we can compute the expected utility of agents playing the actions: E[U_i] = p₁ * u₁ + … + p_n * u_n. For example, for the mixed strategy of the R-P-S with p = 1/3 against the pure strategy with G_i = (1, 0, 0), the expected utility is: E = 1/3 * 0 + 1/3 * 1 + 1/3 * (-1) = 0.

The goal of the players is the maximization of the expected utility.

The best response is the best action that a player can play, given the strategy of the other players (G_-i).

In the Bach/Stravinsky game, the best response of the players is: B for player 1 and S for player 2. The states SB and BS are not stable (in SB p1 wants to go to BB and p2 to SS; in BS p1 wants to change to SS and p2 to BB), instead, the state BB and SS are stable from unilateral deviation (players don’t want to change unilaterally the game to BS or SB).

Nash Equilibrium: (G₁*, G₂*, …, G_n*) is Nash Equilibrium if ∀i G_i* ⊆ BR_i(G_-i*) for every finite