Agentes Inteligentes e Sistemas
Multi-agente
(UD7 e UD10) Interacção,
Negociação e Cooperação entre
Agentes
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?
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?
Sistema multi-agente
Depêndencia dos Agentes
Aspecto importante, existe se:
Um dos agentes requer o outro para atingir os seus
objectivos
Relações de dependência:
1.
2.
3.
4.
Independência- não há dependência
Unilateral- um agente depende de outro mas não viceversa
Mútua- ambos os agentes dependêm um do outro em relação ao
mesmo objectivo
Dependência reciproca- um agente depende do outro para
atingir um dado objectivo, e o segundo depende do primeiro para
atingir um outro objectivo.
Relações acreditadas: localmente e mutuamente
Chegar a acordo: leilões, negociação,
argumentação
Agentes necessitam de interagir com outros com quem
não partilham objectivos comuns;
Normalmente é possível chegar-se a um acordo com
benefício mútuo nos assuntos de interesse comum:
Chegar a acordo é essencial!
- Negociação
- Argumentação
Como chegar a um “acordo”
Constituintes para o cenário:
•
Protocolos de negociação - regras que governam
as interacções (encontro) entre agentes
- Design mechanism
•
Estratégia dos agentes - estratégia de modo a
actuar segundo o protocolo, tendo em vista atingir os
objectivos propostos e maximizar o seu bem estar individual.
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 .
Protocolos para negociação (cont)
Propriedades de protocolos de negociação:
Estabilidade- um protocolo diz-se estável se der aos agentes um
incentivo para agirem de determinada forma atingindo uma
estabilidade na cooperação (por exemplo atingir o Equilibrio de
Nash).
Simplicidade- um protocolo diz-se simples se tornar a estratégia
apropriada de negociação óbvia – ao usá-lo o agente descobre
facilmente (tratabilidade) a estratégia óptima.
Distribuição- um protocolo diz-se distribuído se assegura que não
existe um ponto de falha (por exemplo, um só árbitro)
minimizando a comunicação entre agentes.
Leilões
Uma 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.
Leilões (2)
Variáveis que determinam o carácter dos leilões:
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.
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.
Leilão Inglês
First-price, open-cry,ascending.
Starting value: 80.000€
Leilão Holandês
Open-cry, descending.
Starting value: 280.000€
Leilões First-price sealed-bid
First-price, sealed-bid, one-shot
Lelões Vickrey
Second-price, sealed-bid, one-shot
Tipos de Leilões (4)
1) Leilão Inglês
First-price, open-cry,ascending.
Estratégia: fazer licitações sucessivas com pequenos
incrementos até atingir o nosso valor e desistir depois.
Se houver incerteza no valor do bem pode ser perigoso
oferecer mais do que os restantes agentes (winner’s
curse)
2) Leilão Holandês
Open-cry, descending.
Estratégia: Não há estratégia dominante. É susceptível à
winner’s curse
Tipos de Leilões (5)
3) Leilões First-price sealed-bid
First-price, sealed-bid, one-shot.
Estratégia: licitar um pouco abaixo do seu valor para o
agente (pensar no valor da 2º mais alta licitação). Não
há solução geral para o “pouco abaixo”.
4) Lelões Vickrey
Second-price, sealed-bid, one-shot.
Estratégia: faz com que a estratégia dominante seja licitar o
valor próprio do agente
Não é usado em leilões com humanos – interessante para a
área de Agentes
É susceptível a comportamento anti-social
Tipos de Leilões (6)
Do ponto de vista do leiloeiro:
maximizar o proveito – depende muito dos agentes
Nenhum dos tipos de leilões está imune a “concertação” entre
os agentes licitadores
– coligação de agentes que acordam entre si um preço
abaixo do valor real do bem – dividir os lucros entre si.
- Só se evita através de um protocolo que assegure que os
agentes licitadores não se conhecem
Exemplos de Aplicação: Auction
Bots
Auction Bots: Agentes que se movimentam de site em site e
participam em leilões de bens online.
Exemplos conhecidos: Kasbah
Spanish Fish Market
Exemplo 1: Kasbah (Chavez & Maes)
Sistema para a Web no qual os utilizadores podem criar
agentes que compram e vendem bens em seu nome.
• O utilizador que vende pode especificar 3 parâmetros:
- Data desejada para venda do bem
- Preço desejado para a venda
- Mínimo preço para a venda.
•
•
•
Os agentes vendedores começam por oferecer um bem a um
preço desejado e com o aproximar do deadline de venda o
preço começa a ser reduzido até ao preço mínimo.
Os utilizadores podem especificar a função de decay do
preço (linear, quadrática ou cúbica)
O utilizador confirma sempre a venda tendo direito a veto.
Exemplo 1: Kasbah (Chavez & Maes)


Os agentes compradores
Também têm um conjunto de parâmetros associados:
•
A data de compra do artigo
• O preço desejado
• E o preço máximo

O utilizador pode especificar a função de crescimento do preço.
Os agentes em Kasbah operam sob um modelo de mercado, com um
gestor que pode gerir um conjunto de leilões em paralelo.
Negociação
Como é que um grupo de agentes chega a acordo em
assuntos de interesse mútuo?
Constituintes:
• Conjunto de negociação – define o espaço das propostas
possíveis que os agentes podem fazer
•
Protocolos de negociação – define as regras que governam as
•
Estratégias – cada agente tem a sua estratégia e ela determina
interacções entre agentes – as propostas legais que os agentes podem
fazer
quais as propostas que o agente irá fazer. Normalmente as estratégias
são privadas
•
Regra de acordo final- regra que determina que se chegou a
acordo final e qual o acordo encontrado
Negociação
Em geral:
- Série de voltas
- Todos os agentes fazem propostas em
todas as voltas:
- Cada proposta:
- Depende e é definida pela estratégia dos
agentes,
-  conjunto de negociação
- legal (tal como definido pelo protocolo)
- Se se chegou a acordo (pela regra)
termina
Negociação

Várias pontos de variabilidade +
- Um atributo vs vários:
- Preço / (Preço, extras, garantia, etc.)
- Crescimento exponencial do espaço do conjunto de
negociação – impossível explicitar todo o conjunto para
determinar a proposta a efectuar
- Por vezes difícil determinar os atributos em negociação
- Número de agentes
- Um-a-um – venda de um carro
- Muitos-a-um – leilões
- Muitos-com-Muitos – n*(n-1)/2 threads
Negociação

A maior parte das propostas são para:
- Um atributo, simétricas, um-a-um
•
Negociação:
- Domínios orientados para as tarefas – discute
atribuição de tarefas
- Domínios orientados para o valor – discute
definição de planos conjuntos
- Há outros tipos de abordagens:
- Distribuída (competitiva) – ganhar-perder
- Integrativa (cooperativa) – ganhar-ganhar
- Mista
Domínio Orientado a Tarefas
Tarefa: 3 estudantes querem vir para o Tagus todos os dias da linha de Sintra (um
tem um familiar que o traz e dois têm carro). Dois vêm de Sintra e um vêm do
Cacém.
Levar um estudante num troço de trajecto – tarefa indivísivel
Os agentes podem negociar e podem melhorar a sua situação:
•
•
•
•
chegar a um acordo - por exemplo, os de Sintra irem só até
ao Cacém.
partilhados – melhora a situação actual
Não se entendem – não piora a situação actual- vêm todos
por si só.
Diferentes soluções. Por exemplo: cada dia leva um. Os de
Sintra levam até ao Cacém...O do Cacém leva até ao Tagus
somente 2 dias. ....
- COMO CHEGAR A UM ACORDO??????
Domínio Orientado a Tarefas
TOD=<T,Ag,c>
 T- conjunto finito de todas as tarefas possíveis
 Ag- conjunto finito de agentes que participa na negociação;
 c- função que define custo de executar um subconjunto de
tarefas. Domínio Ti C T. Contradomínio R+
• Restrições c:
- Monótona: T1 C T2, c(T1 )
< c(T2)
- Custo de não fazer nada é 0


“Encontro” = Coleção de tarefas, onde: Atribuição Ti aos
Agi
<T1,T2,… , Tn>
Domínio Orientado a Tarefas
Cenário um-a-um:
Encontro:
Negócio (deal):
<T1,T2>
d = <D1,D2>
- negócio ~ encontro D1U D2 = T1 U T2
- Os agentes comprometem-se a realizar as tarefas que lhe foram
atribuídas: Agente 1 compromete-se a realizar D1, e agente 2
compromete-se a realizar D2.
- Custo de negócio para o agente i
- custoi (di) = c(Di)
- Utilidade de negócio para o agente i
- utilidadei (d) = c(Ti) - custoi (d)
- c(Ti) = custo atribuição original Ti no encontro
- custoi (d) = custo tarefas atribuídas a i no negócio
- Deve ser > 0
- Se não há acordo -> faz as tarefas iniciais
- Negócio de conflito:
Q = <T1,T2>
Domínio Orientado a Tarefas
Dominância, d1 > d2 :
1.
Negócio d1 é pelo menos tão bom para todos os
agentes como d2
-
2.
Negócio d1 é melhor que d2 para pelo menos para um
agente
-

Para todos os agentes i: Utilidadei (d1) Utilidadei (d2)
Existe um agente i: Utilidadei (d1) >Utilidadei (d2)
Se um negócio domina outro então ele é melhor para
qualquer participante
Domínio Orientado a Tarefas

Um negócio domina fracamente outro se apenas a
primeira condição é verificada
-
Negócio d1 é pelo menos tão bom para todos os agentes como d2
Para todos os agentes i: Utilidadei (d1) Utilidadei (d2)


Um negócio é pareto óptimo se não é dominado por
nenhum outro (não é possível melhorar o negócio a
não ser à custa de piorar a situação de um dos outros
agentes)
Um negócio é individualmente racional se domina
fracamente o negócio de conflito Q
•
Se não é individualmente racional pelo menos um agente
fica melhor na atribuição original
Domínio Orientado a Tarefas
Utilidade para i
Quadrante que interessa –
Individualmente racional
conjunto de negociação
Linha pareto óptima
Negócio de conflito
Utilidade para j
Domínio Orientado a Tarefas
Utilidade para i
B
Quadrante que interessa –
Individualmente racional
conjunto de negociação
Linha pareto óptima
Negócio de conflito
Utilidade para j
Domínio Orientado a Tarefas
Utilidade para i
B
Quadrante que interessa –
Individualmente racional
conjunto de negociação
Linha pareto óptima
C
Negócio de conflito
Utilidade para j
Domínio Orientado a Tarefas
Utilidade para i
B
Quadrante que interessa –
Individualmente racional
conjunto de negociação
Linha pareto óptima
C
Negócio de conflito
Utilidade para j
Protocolo de concessão monótono
(Rosenschein 94)
Negociação por série de rondas, propostas de negócio dos agentes
efectuadas em simultâneo, termina sempre (com ou sem acordo)
Na primeira volta ambos os agentes propõem um negócio ( conjunto
de negociação)
Há acordo se ambos os agentes 1, 2 propõem negócios d1 d2 e:
Utilidade1 (d2) Utilidade1 (d1) OU Utilidade2 (d1) Utilidade2 (d2)
(o outro faz-nos uma proposta tão ou melhor do que a nossa)
Se há acordo, então o negócio de acordo escolhido será:
• Se ambos verificam a condição: um aleatóriamente
• Se só um verifica: o que verifica a condição
Se não há acordo: nova ronda de propostas simultaneas em que
nenhum agente pode propor um negócio menos preferido para o
outro agente que o proposto na ronda anterior
Se nenhum concede (ceder) numa determinada volta a negociação
termina com o negócio de conflito
Mas como é que os agentes devem
negociar????
Qual deverá ser a primeira proposta?
Ceder?
Não ceder?
Se ceder, quanto é que devo ceder?
Estratégia Zeuthen
- Primeira proposta?
- o nosso negócio mais preferido
Quando ceder?
Willingness to Risk Conflict: Arriscar conflito ou não?

Suppose you have conceded a lot. Then:
• Your proposal is now near the conflict deal
• In case conflict occurs, you are not much worse off
• You are more willing to risk confict

An agent will be more willing to risk conflict if the
difference in utility between its current proposal
and the conflict deal is low
Estratégia Zeuthen
- Quando ceder?
- arrisco mais se a diferença entre utilidade da
proposta de negócio corrente e a do negócio de
conflito for baixa
- risco (0-1) (ucorrente – uproposta)/ucorrente
se ~1 não tem muito a perder; arrisca mais
pelo conflito e não concede
se ~0 tem mais a perder
Estratégia Zeuthen
Quanto ceder?
o suficiente para equilibrar o risco.
se ambos têm = risco ambos devem ceder
pode não ceder – não se consegue negócio
alternativa – cara ou coroa.
Propriedades:





não garante sucesso,
Garante que se há sucesso é pareto óptimo e individualmente
racional
Não precisa de árbitro
Pode crescer exponencialmente com o número de tarefas
Está em equilibrio de Nash – é uma vantagem conhecer a
estratégia – evita conflitos
“Deception” (Engano) em Domínios orientados à
tarefa

Pode haver a situação que os agentes “enganam
outros”:
• “Phantom and Decoy tasks”
Os agentes “fingem” que têm tarefas alocadas que na
realidade não têm.
• Hidden tasks
Os agentes “fingem” que não lhes foi alocadas
tarefas, que na realidade foram.
Domínios Orientados a Valor
Negociação de planos conjuntos





WOD=<E,Ag,J, c>
E- conjunto estados do ambiente possíveis
Ag- conjunto finito de agentes que participa na
negociação;
c- função que define custo a cada plano de cada
agente
J- Planos conjuntos
Encontro =<e, W>, estado inicial, função que dado um
estado do ambiente e um agente representa o valor
do estado para o agente.
Negociação: Conclusões


By appropriately adjusting the rules
of encounter by which agents must
interact, we can influence the
private strategies that designers
build into their machines
The interaction mechanism should
ensure the efficiency of multi-agent
systems
Rules of
Encounter
Efficiency
Negociação: conclusões


To maintain efficiency over time of
dynamic multi-agent systems, the
rules must also be stable
The use of formal tools enables the
design of efficient and stable
mechanisms, and the precise
characterization of their properties
Stability
Formal
Tools
Argumentação

“Argumentação” é o processo de tentar convencer os
outros de algo….(por exemplo, “Vir às aulas”)

Importância:
Quando um agente negoceia deve ser capaz de
justificar as suas ofertas – crucial na delegação;
As nossas preferências mudam.


Argumentação
Gilbert (1994) identificou 4 modos de argumentar:
1. Logical mode (modo lógico)
“If you accept that A and that A implies B, then you must
accept that B”
2. Emotional mode (modo emocional)
“How would you feel if it happened to you?”
3. Visceral mode (modo visceral)
“Cretin!”
4. Kisceral mode (modo kisceral)
“This is against Christian teaching!”
“Logic-based Argumentation”
Basic form of logical arguments is as follows:
Database |- (Sentence, Grounds)
where:

Database is a (possibly inconsistent) set of logical
formulae

Sentence is a logical formula known as the conclusion

Grounds is a set of logical formulae such that:
1. Grounds  Database; and
2. Sentence can be proved from Grounds
Ataque e Derrota
Let (f1, G1) and (f2, G2) be arguments from some database D…
Then (f2, G2) can be defeated (attacked) in one of two ways:
 (f1, G1) rebuts (f2, G2) if f1  f2
 (f1, G1) undercuts (f2, G2) if f1  y2 for some y G2
A rebuttal or undercut is known as an attack

Há 5 tipos de argumentos:
- tautologias são os mais fortes
- argumentos que podem ser derivados são os mais fracos
- entre os dois: a classe de argumentos que não tem undercut, que não tem
rebut, etc.
Há vários tipos de diálogos de argumentos: (seq de argumentos de 2 agentes):
inquéritos (determinar sobre algo), deliberação (acção), etc.
Argumentação Abstracta


Concerned with the overall structure of the argument
(rather than internals of arguments)
Write x  y
•
“argument x attacks argument y”
“x is a counterexample of y”
• “x is an attacker of y”
where we are not actually concerned as to what x, y are
 An abstract argument system is a collection or
arguments together with a relation “” saying what
attacks what
 An argument is out if it has an undefeated attacker, and
in if all its attackers are defeated
•
Agentes a trabalhar juntos…
Como e porque é que os agentes colaboram?
 Há que distinguir entre:
• Agentes benevolentes (colegas..)
- Implicitly share a common goal and there is
no conflict between them
- Help whenever needed
- Overall objectives over individual ones
•
Agentes self-interested (alguns
colegas…)
- Cannot be assumed to share a goal
- Ultimately need to cooperate to achieve goals
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?
Coordenação das tarefas:
- Cooperação
- Negociação
Agentes Benevolentes




If we “own” the whole system, we can design agents to help each other
whenever asked
In this case, we can assume agents are benevolent: our best interest is their
best interest
Problem-solving in benevolent systems is cooperative distributed problem
solving (CDPS)
Benevolence simplifies the system design task enormously!
Self-Interested Agents




If agents represent individuals or organizations, (the more general case),
then we cannot make the benevolence assumption
Agents will be assumed to act to further their own interests, possibly at
expense of others
Potential for conflict
May complicate the design task enormously
Cooperative Distributed Problem Solving
CDPS
•
Cooperative Distributed Problem Solving
-
Em geral a solução tem 3 passos:
1. Problem Decomposition – typ. hierarchical
2. Subproblem solution – typ. share info.
3. Answer synthesis – integrated into overall solution,
hierarchical
-
Propriedades de uma solução com sucesso:
-
Coêrencia – sistema funciona como um todo (qualidade da solução,
eficiência de uso de recursos, etc)
Coordenação – sincronizados,no limite sem necessidade de
comunicação, previsiveis, sem conflitos
- “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
Task Sharing and Result Sharing
•
•
Two main modes/components of cooperative
problem solving:
task sharing:
components of a task are distributed to component
agents
-
•
Allocation problem: all same capabilities/different
capabilities, can refuse negotiation (reaching agreements)
result sharing:
information (partial results, etc.) is distributed
-
Proactively or reactively
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)
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
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.
Contract-Net – Exemplo (2)
1–O
Manager anuncia a tarefa a executar aos possíveis Contractors
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
???
Contract-Net – Exemplo (3)
3–O
Manager selecciona o agente mais apropriado à execução,
baseado na informação das propostas. A selecção é comunicada.
Contract-Net – Exemplo (4)
4–O
Contractor executa a tarefa e entrega os resultados ao Manager
The Contract Net:Fases

Assim, o Contract net tem as seguintes fases :
1. Recognition
2. Announcement
3. Bidding
4. Awarding
5. Expediting
Recognition

In this stage, an agent recognizes it has a problem it
wants help with.
Agent has a goal, and either…
• realizes it cannot achieve the goal in isolation —
does not have capability
• realizes it would prefer not to achieve the goal in
isolation (typically because of solution quality,
deadline, etc.)
Announcement

In this stage, the agent with the task sends out an
announcement of the task which includes a specification
of the task to be achieved
 Specification must encode:
• description of task itself (maybe executable)
• any constraints (e.g., deadlines, quality constraints)
• meta-task information (e.g., “bids must be submitted
by…”)
 The announcement is then broadcast
Bidding

Agents that receive the announcement decide for
themselves whether they wish to bid for the task
 Factors:
• agent must decide whether it is capable of expediting
task
• agent must determine quality constraints & price
information (if relevant)
 If they do choose to bid, then they submit a tender
Awarding & Expediting

Agent that sent task announcement must choose between
bids & decide who to “award the contract” to
 The result of this process is communicated to agents that
submitted a bid
 The successful contractor then expedites the task
 May involve generating further manager-contractor
relationships: sub-contracting
Node Issues Task Announcement
Task Announcement
Manager
Idle Node Listening to Task
Announcements
Manager
Potential
Contractor
Manager
Manager
Node Submitting a Bid
Bid
Manager
Potential
Contractor
Manager listening to bids
Bids
Potential
Contractor
Manager
Potential
Contractor
Manager Making an Award
Award
Manager
Contractor
Contract Established
Contract
Manager
Contractor
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.
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)
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.
Issues for Implementing Contract Net

How to…
• …specify tasks?
• …specify quality of service?
• …select between competing offers?
• …differentiate between offers based on multiple
criteria?
The Contract Net

An approach to distributed problem solving,
focusing on task distribution

Task distribution viewed as a kind of contract
negotiation

“Protocol” specifies content of communication,
not just form

Two-way transfer of information is natural
extension of transfer of control mechanisms
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)
Four Phases to Solution, as Seen in
Contract Net
1. Problem Decomposition
2. Sub-problem distribution
3. Sub-problem solution
4. Answer synthesis
The contract net protocol deals with
phase 2.
Cooperative Distributed Problem Solving
(CDPS)



Neither global control nor global data storage —
no agent has sufficient information to solve
entire problem
Control and data are distributed
Any unique node is a potential bottleneck
•
•
•
distribute data
distribute control
organized behavior is hard to
guarantee (since no one node has
complete picture)
Coordenação
Relações positivas ou negativas
 Abordagens
•
•
•
•
•
Coordenação a partir de planos globais parciais - DVMT
Coordenção através de intensões conjuntas: modelo do
agente + modelo dos outros (planos, goals, skills, etc) –
ARCHON+MACE
Coordenação por modelação mútua (modelo dos outros –
roles, skills, goals, plans) - MACE
Coordenação através de normas e leis sociais – leis
emergentes
Planeamento multiagente e sincronização – merge de planos
– extensão de lógicas temporais
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 ou incluem já
protocolos de negociação.

Exemplo de uma linguagem de colaboração: COOL

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
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
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
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)
)
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).
Resumo: 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?
Resumo: 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?
Conclusões


Criar sociedades para resolver problemas parece ser
um caminho a seguir.
Há ainda bastantes problemas (ferramentas e teorias)
por resolver.
Questões???
An Example Abstract Argument System