Agentes Inteligentes e Sistemas
Multi-agente
Cooperação entre Agentes
IST- 2003/2004
Ana Paiva
Problemas a resolver
Problema dos comportamentos sociais e individuais
• Como especificar os comportamentos sociais dos agentes?
• Como é que os comportamentos dos outros e da sociedade
influenciam o comportamento individual?
Problema da estrutura da organização
• Como organizar uma sociedade de agentes para que no
global, esta execute a tarefa desejada?
• Qual o tipo de estrutura mais adequada para a tarefa em
causa?
• Como definir os aspectos do comportamento individual para
que sejam integrados na sociedade levando a um
comportamento global desejado?
• Que tipos de mecanismos há que levem ao surgimento e
desaparecimento de sociedades?
A. Paiva
Problemas a resolver


Problema da comunicação entre agentes
• Que tipo de comunicação entre agentes é a mais adequada à
estrutura escolhida?
• Que linguagens de comunicação existem e podem ser
usadas para a comunicação entre agentes numa sociedade
de agentes?
• Que conceitos (ontologias) são necessários ser partilhados
para que os elementos da sociedade consigam interpretar as
mensagens recebidas?
Cooperação, colaboração e negociação
• Que mecanismos de cooperação são necessários para que
os agentes executem cooperativamente uma dada tarefa?
• Que estruturas de organização são as mais adequadas para
determinados tipos de cooperação?
• Que linguagens existem que podem ser usadas para permitir
a cooperação e negociação entre agentes numa sociedade?
A. Paiva
Sistema multi-agente
A. Paiva
Como estudar as interações entre agentes?
Noção de “encontro”





Os agentes na sociedade escolhem que acção executar.
Como resultado das acções escolhidas, haverá um resultado R
No entanto, o resultado final dependerá da combinação das
diversas acções dos diversos agentes
Vamos assumir que os agentes têm dois tipos de acção: C
(cooperar) e D (não cooperar)
O comportamento do ambiente é dado por uma função de
transformação de estado:
τ : Aci
A. Paiva
x
Acj
-> R
Utilidades e Preferências



Os agentes decidem que acção executar baseando-se em utilidades e
preferências
Agentes têm interesses próprios ditados pelos seus desejos (levando a
utilidades e preferências.
Uma função de utilidade é uma função dos resultados (estados do
mundo) em valores reais (que dão os valores de uma dada acção).
A. Paiva
Exemplos de Funções de
Transformação dos estados
1. τ(D,D) = ω1 τ(D,C) = ω2 τ(C,D) = ω3 τ(C,C) = ω4
(o ambiente reage às acções de ambos os agentes)
2. τ(D,D) = ω1 τ(D,C) = ω1 τ(C,D) = ω1 τ(C,C) = ω1
(o ambiente não reage às acções de nenhum dos agentes)
3. τ(D,D) = ω1 τ(D,C) = ω2 τ(C,D) = ω1 τ(C,C) = ω2
(o ambiente reage às acções do agente j sendo controlado por
ele)
A. Paiva
Acções Racionais
Cada um dos agentes decide o que fazer tendo em conta as suas funções
de utilidade.


ui(ω1 ) = 1 ui(ω2 ) = 1 ui(ω3) = 4 ui(ω4 ) = 4
uj(ω1 ) = 1 uj(ω2 ) = 4 uj(ω3) = 1 uj(ω4 ) = 4
Considerando que:


ui(D,D) = 1 ui(D,C) = 1
uj(D,D) = 1 uj(D,C) = 4
ui(C,D) = 4 ui(C,C) = 4
uj(C,D) = 1 uj(C,C) = 4
Ou seja o agente i tem as seguintes preferências:
C,C ≿i C,D ≿i D,C ≿i D,D
A. Paiva
Que acção escolher se fossemos o agente i?
E se as utilidades fossem?

ui(D,D) = 4 ui(D,C) = 4
ui(C,D) = 1 ui(C,C) = 1

uj(D,D) =4 uj(D,C) = 1
uj(C,D) = 4 uj(C,C) = 1
As preferências do agente são:
D,D ≿i D,C ≿i C,D ≿i C,C
i defects
i cooperates
4
1
j defects
4
4
4
1
j cooperates
1
A. Paiva
1
Payoff matrix
Estratégias Dominantes
Dominância
•
Dois conjuntos Ω1 e Ω2. Diz-se que Ω1 domina Ω2 se cada
resultado de Ω1 é preferido por i sobre cada resultado de Ω2.
•
Ω = {ω1, ω2, ω3, ω4}
•
ω1
•
Ω1 = {ω1, ω2}
•
Ω2 = {ω3, ω4}
A. Paiva
≿i ω2 ≿i ω3 ≿i ω4
Nash Equilibrium
Duas estratégias s1 e s2 estão em equilíbrio de Nash se:
•
Se o agente i segue s1, o agente j não pode fazer melhor do que
seguir a estratégia s2
• Se o agente j segue a estratégia s2 o agente i não pode fazer
melhor do que seguir a estratégia s1.

Esta forma de equilibrio é importante na medida que garante que os agentes se
agrupam em torno de um conjunto de estratégias, e nenhum dos agentes deve
querer afastar-se do ponto de equilibrio.

No entanto:
•
•
Nem todos os cenários de interação entre agentes tem um equilibrio
Algumas interações levam a mais do que um ponto de equilibrio.
A. Paiva
O Dilema do Prisioneiro
Duas pessoas foram acusadas de cometer um crime e
estão mantidas presas separadas sem poderem
comunicar entre si. É dito a ambos que:
1. Se um deles confessa o crime e o outro não, o
que confessou é libertado, e o outro é preso por 3
anos.
2. Se ambos confessam o crime, então cada um
deles é preso por 2 anos.
3. Se nenhum confessar eles só ficam presos por 1
ano.
A. Paiva
O Dilema do Prisioneiro (2)

Defects: confessar e Cooperate: não confessar
Utilidades:
Libertado: 5
Um ano de prisão: 3
Dois anos de prisão: 2
Três anos de prisão: 0


ui(D,D) = 2 ui(D,C) = 5 ui(C,D) = 0 ui(C,C) = 3
uj(D,D) =2 uj(D,C) = 0 uj(C,D) = 5 uj(C,C) = 3
D,C ≻i C,C ≻i D,D ≻i C,D
C,D ≻j C,C ≻j D,D ≻j D,C
A. Paiva
O Dilema do Prisioneiro
i defects
i cooperates
2
0
j defects
2
5
5
3
j cooperates
0
3
O que deve o prisioneiro fazer?
A. Paiva
O Dilema do Prisioneiro
Pensar como um prisioneiro
Suponhamos que coopero. Se j também cooperar, temos um ganho de
3. Se o j não cooperar então eu tenho um ganho de 0. Ou seja, o
melhor valor que eu tenho garantido é 0.
2. Suponhamos que eu não coopero. Se o j cooperar, então eu tenho um
ganho de 5. Se j nao cooperar, tenho um ganho de 2. Ou seja, o melhor
valor que eu tenho garantido é 2.
1.
A. Paiva
Depêndencia dos Agentes em SMA
Como é que os agentes dependem uns dos outros?
Factores que influenciam:
 A organização dos agentes.
 Tipo de agentes (tipo de autonomia dos agentes)
 Tipo de comunicação possível
Relações de dependência:
Independência- não há dependência
2. Unilateral- um agente depende de outro mas não viceversa
3. Mutual- ambos os agentes dependêm um do outro em relação ao
mesmo objectivo
4. Dependência reciproca- um agente depende do outro para atingir um
dado objectivo, e o segundo depende do primeiro para atingir um outro
objectivo.
1.
A. Paiva
Resolução de Problemas distribuída
Como é que um grupo de agentes chega a acordo e
consegue resolver um problema ou executar uma
tarefa de forma cooperativa?
Cooperação
- Negociação
-
A. Paiva
Cooperação

É fundamental, sendo a razão principal para a existência de um
ambiente multi-agente. [Nwana]

Capacidade que os agentes têm de “trabalharem em conjunto de
forma a concluírem tarefas de interesse comum”.

Tal como os humanos, os agentes têm de combinar os seus
esforços de forma a atingir objectivos comuns que não podem ser
atingidos individualmente.

O agente deve ser dotado de habilidade social, capacitando-o a
interagir com outros agentes, possivelmente humanos, através de
alguma linguagem de comunicação.
A. Paiva
Coordenação
“Acto
de trabalhar em grupo de forma harmoniosa no
sentido de atingir um acordo ou objectivo comum.”

Necessidade de coordenar agentes:
•
Existem dependências nas acções dos agentes
•
Existe necessidade que o conjunto de agente respeite
restrições globais
•
Nenhum agente individualmente tem recursos, informação ou
capacidade suficiente para executar a tarefa ou resolver o
problema completo
A. Paiva
Formas de Coordenação
Coordenação
Cooperação
Competição
Planeamento
Negociação
Planeamento
Distribuído
A. Paiva
Planeamento
Centralizado
Coordenação de Agentes Competitivos

Self-interested

Negociação
•
•
•
Permitir a modificação dos planos locais de agentes
autónomos
Identificar situações onde são possíveis interacções entre
agentes.
Efectuar alocação de tarefas e recursos, resolução de
conflitos…
A. Paiva
Resolução de Conflitos


Conflitos:
• Competição por recursos escassos
• Tempo escasso
• Problemas de comunicação
Formas de resolver:
• Competição
• Colaboração (ganha-ganha)
• Compromisso
• Acomodação
A. Paiva
Negociação

Constituintes
•
Protocolos de negociação - regras que governam as
interacções entre agentes
•
Objectos de negociação - conjunto de atributos sobre os
quais se pretende chegar a acordo, p.ex. preço
•
Modelos da tomada de decisão do agente ferramentas de tomada de decisão de modo a actuar segundo o
protocolo, tendo em vista atingir os objectivos propostos.

Tipos de negociação
•
•
•
Distribuída (competitiva) – ganhar-perder
Integrativa (cooperativa) – ganhar-ganhar
Mista
A. Paiva
Esquema Genérico -Negociação Electrónica

Início – cada agente tem uma porção de espaço, no qual tenta fazer acordos.
•
Cada agente tem uma forma de avaliar os pontos no seu espaço
A3
A2
A1
A. Paiva
Esquema Genérico -Negociação Electrónica

Negociação prossegue – participantes sugerem pontos específicos, ou
regiões, como sendo potencialmente aceitáveis.
A3
A2
A1
A. Paiva
Esquema Genérico -Negociação Electrónica

Fim – quando os agentes encontram um ponto mútuo aceitável
no espaço de acordos ou quando, o protocolo determina que a
pesquisa deve ser terminada.
A3
A2
A1
A. Paiva
Coordenação de Agentes Cooperativos

Forma como conjuntos de agentes se podem
coordenar de forma a realizar trabalho cooperativo de
equipa.

São totalmente cooperativos tentando auxiliar-se
mutuamente nem que isso provoque alguns custos
individuais.

Sem coordenação a comunidade de agentes pode
degenerar numa colecção caótica e incoerente de
agentes individuais.

Para além da negociação, existem outras
metodologias.
A. Paiva
Protocolos para negociação
Propriedades de protocolos de negociação:
Sucesso garantido- o protocolo garante que há sucesso na negociação.
Maximização do bem social- o protocolo maximiza o bem social garantindo que o
resultado maximiza a soma das utilidades dos participantes na negociação.
Pareto efficiency- O resultado da negociação é Pareto efficient se não há outro
resultado possível que coloque pelo menos um agente em melhor situação sem
que coloque outro agente em pior situação.
Individual Rationality – um protocolo é fundamentado em racionalidade individual
se garantir os interesses dos participantes na negociação.
Estabilidade- um protocolo diz-se estável se der aos agentes um incentivo para
agirem em determinada forma que atinge uma estabilidade na cooperação (por
exemplo atingir o Equilibrio de Nash).
A. Paiva
Protocolo Contract-NetCoordenação por Partilha de Tarefas

Problema: Contratação de tarefas

Inspirado no mundo dos negócios

Pretende resolver o connection problem (encontrar um agente
apropriado para a tarefa em questão)
A. Paiva
Contract-Net - Papéis

Manager – responsável pela monotorização da
execução da tarefa e no processamento dos
resultados da execução

Contractor – responsável pela actual execução da
tarefa

Um agente pode tomar os ambos papéis
dinamicamente durante a execução da solução
A. Paiva
Contract-Net – Exemplo (1)

Vamos supor que temos um urso faminto que quer provar uma
especialidade do pólo norte, mas como não é um urso polar tem
de pedir ajuda na preparação do prato.
A. Paiva
Contract-Net – Exemplo (2)
1–O
Manager anuncia a tarefa a executar aos possíveis Contractors
A. Paiva
Contract-Net – Exemplo (2)
2–
Os agentes contactados fazem uma avaliação ao anúncio e
ponderam as suas capacidades para executarem a tarefa em
questão e fazem uma proposta ao Manager
???
A. Paiva
Contract-Net – Exemplo (3)
3–O
Manager selecciona o agente mais apropriado à execução,
baseado na informação das propostas. A selecção é comunicada.
A. Paiva
Contract-Net – Exemplo (4)
4–O
Contractor executa a tarefa e entrega os resultados ao Manager
A. Paiva
Mensagens necessárias para o contract-net

Request-for-bids(T,X) é a mensagem do Manager para os potenciais
contractors pedindo ao contractor para lhe enviar uma proposta para a
execução da tarefa T

Propose(T,O) é a resposta positiva de um Contractor relativamente ao
pedido para a execução da tarefa T. A proposta contém a especificação
da oferta feita O.

Not-interested(T,Y) é uma resposta negativa de um contractor
dizendo que não está interessado em executar T.

Award(T,C,X) é a mensagem do Manager (X) para o contractor (C)
informado-o que lhe foi oferecida a execução da tarefa T.

Accept(T,X) é a resposta positiva do contractor Y em resposta à oferta
do Manager para a execução da tarefa.

Refuse(T,Y) é a resposta negativa do contractor à oferta do Manager
para a execução da tarefa.
A. Paiva
Contract-Net – Conteúdo do Anúncio

A mensagem que anuncia a tarefa a realizar tem a seguinte
composição:
•
•
•
•
•
Addressee – contém o endereço do(s) destinatário(s)
Eligibility Specification – condições que é necessário um
agente ter para poder, eventualmente, ser o contractor
Task Abstraction – breve descrição da tarefa a realizar
Bid Specification – especifica o que deve conter uma
resposta para que esta possa ser considerada
Expiration Time – prazo para serem dadas as propostas ao
anúncio (no entanto, o manager pode não ser obrigado a
esperar todo o tempo e as respostas recebidas depois de
expirado o tempo até podem resultar numa selecção
subópitma de contractors)
A. Paiva
Contract-Net – Resposta Imediata

Pode acontecer o caso em que o manager não recebe
nenhuma proposta, isto pode acontecer essencialmente por dois
motivos, primeiro, todos os agentes elegíveis estão ocupados ou
têm uma melhor proposta em mãos, segundo, não existem
agentes elegíveis.

A solução encontrada para este problema foi criar uma classe de
propostas a Immediate Response Bids as quais requerem
uma de três respostas possíveis, BUSY, INELIGIBLE, LOW
RANKING, ou uma sub-classe destas (ex: respond if eligible, but
busy).

Assim o manager pode tomar medidas para resolver o problema
como tentar mais tarde ou fazer uma proposta mais aliciante.
A. Paiva
Contract-Net - Conclusões
+
+
-
Boa solução para o connection problem
Bastante adequado a problemas de estrutura hierárquica
Uma tarefa pode não ser atribuída ao agente mais qualificado se
este estiver ocupado
Para um número grande de agentes gera um grande tráfego de
mensagens (mas o campo eligibility specification reduz as
mensagens de resposta ao anúncio)
A. Paiva
Leilões
Uma outra forma de resolver problemas de alocação de tarefas e de venda
de serviços é através de leilões.
Um leilão ocorre entre um leiloeiro e um conjunto de agentes que
fazem ofertas (bidders). O objectivo do leilão é o leiloeiro alocar o
bem ou serviço a um dos bidders por um determinado valor.
Aspectos dos leilões:
-
Existe um bem ou serviço a leiloar.
Se esse bem ou serviço tem um valor conhecido diz-se que esse é o
valor publico (comum)
Cada agente pode atribuir ao bem ou serviço um valor privado.
Por vezes os valores têm também um valor correlacionado que
envolve o valor privado mais aspectos de sociedade como a
possibilidade de vender o valor futuramente.
A. Paiva
Leilões (2)
Dimensões em que os leilões variam:
1) Determinação do vencedor: ou quem ganha o bem ou serviço.
a)
first-price: o agente que fez a oferta mais alta ganha o bem ou
serviço.
b)
second-price: o agente que fez a oferta mais alta ganha o bem
ou serviço mas paga o valor da segundfa oferta.
2) Ofertas conhecidas ou não pelos outros agentes
a)
Open cry: as apostas/ofertas são conhecidas por todos (common
knowledge)
b)
Sealed-bid : as ofertas são seladas
3) Procedimento de oferta :
a)
one-shot: só existe uma sessão de oferta.
b)
ascending: o valor começa baixo (reservation price) e vai
subindo com as ofertas até não haver mais nenhuma oferta
c)
descending: o valor começa alto e vai descendo.
A. Paiva
Tipos de Leilões (3)
1) Leilão Inglês
First-price, open-cry,ascending.
2) Leilão Holandês
Open-cry, descending.
3) Leilões First-price sealed-bid
First-price, sealed-bid, one-shot.
4) Lelões Vickrey
Second-price, sealed-bid, one-shot.
A. Paiva
Linguagens específicas para
cooperação



Tal como com o contract-net outros protocolos necessitam de
linguagens específicas para a cooperação.
Alguns ambientes (FIPA-OS) já permitem a utilização de performatives
especificas para negociação.
Exemplo de uma linguagem destas: COOL
A. Paiva
COOL (COOrdination Language)



Baseada em KQML
Coordenação de agentes é definida por autómatos finitos.
COOL tem as seguintes componentes:
• Máquina de estados
• Mensagens (performativas)
• Regras de conversação
• Regras para recuperação de erro
• Regras de continuação
• Classes de conversação
• Conversações actuais
A. Paiva
COOL - performativas

Para além das performativas disponibilizadas por KQML ainda são admitidas:
• Propose – usado para propôr um objectivo
•
•
•
•
•
Counter-Propose – segue-se a um propose para propôr outro
objectivo, desde que satisfaça o anterior
Accept e Reject – usados para assinalar aceitação ou
rejeição de uma proposta ou contra-proposta
Cancel – cancela uma proposta ou contra-proposta
previamente aceite
Satisfy – anuncia o cumprimento de um objectivo que lhe foi
pedido
Fail – anuncia a impossibilidade em cumprir um objectivo que
aceitou
A. Paiva
COOL –Máquina de Estados

A máquina de estados define os estados em que se pode encontrar a tarefa
(ex: ponto de vista do receptor)
1
6
propose/
7
/satisfy
2
/fail
/accept
3
/counter
/reject
5
A. Paiva
accept/accept
counter/
4
/reject
COOL – regras de conversação

As regras de conversação dizem-nos como passamos de um
estado para outro da máquina de estados.
(def-conversation-rule
r1
:current-state 2
:received
‘(propose
:sender ?initiator
:content (produce (?what ?amount)
:conversation ?conv
:such-that
‘(achievable (produce ?what ?amount))
:next-state 3
:transmit
‘(accept
:content (produce(?what ?amount))
:conversation ?conv)
)
A. Paiva
Aspectos de Implementação
As ferramentas de construção de agentes já incluem um
conjunto de aspectos para a construção de
sociedades, nomeadamente:
- Linguagens para comunicação e cooperação
- Possibilidade de definir estruturas organizacionais
(definindo “roles” na estrutura)
- Protocolos pre-definidos para resolver aspectos de
negociação (contract-net e leilões).
A. Paiva
Conclusões


Criar sociedades para resolver problemas parece ser
um caminho a seguir.
Há ainda bastantes problemas (ferramentas e teorias)
por resolver.
A. Paiva
Mais bibliografia


Livro do M. Wooldridge
Livro de J. Ferber
A. Paiva