Protocolos de Cooperação
Contract Net Systems
 Partial Global Planning
 Negociações

Protocolos de Cooperação

Protocolos Específico de Cooperação e
Estratégias.

Definir os tipos de cooperação.

Existem várias categorias e formas de
cooperação.
Tipologia de Cooperação
Sistemas Multi-Agentes
Independente
Discreto
Cooperação
Emergente
Deliberativo
Cooperativo
Comunicativo
Negociador
NãoComunicativo
Cooperativo x Independente

Existe a diferença entre agentes cooperativos
e agentes independentes.
Tipologia de Cooperação

Sistemas Multi-Agente Independente
Os agentes individuais de um sistema multiagente são completamente independentes e
seguem suas próprias metas.
Tipologia de Cooperação

Sistemas Multi-Agentes Discretos
Se os agentes agindo independentemente
também têm suas metas não-correlacionadas.
 Exemplo: Um agente busca informação e um
outro dá suporte ao usuário para adquirir
produtos
Tipologia de Cooperação
Sistemas Multi-Agente de Cooperação
Emergente:
Agentes independentes seguem suas próprias
metas, mas um observador externo tem a
aparência de uma cooperação.
 Exemplo: Diversos agentes seguindo uma
mesma meta, podem dar ao observador
externo a impressão de uma metodologia de
cooperação.

Sistemas Cooperativos




Têm mecanismos explícitos de cooperação.
Ao agentes são construídos de modo que eles podem
cooperar com outros agentes e alcançar sua metas.
Cooperação pode proceder de modo comunicativo ou
não-comunicativo.
Na Cooperação comunicativa, agentes usam
protocolos de comunicação e procedimentos de
cooperação com outros agentes. Por exemplo, enviam
mensagens com performativas KQML.
Cooperação Não-Comunicativa




A cooperação não-comunicativa toma lugar
indiretamente usando o ambiente.
Um agente observa seu ambiente e deste modo nota
as mudanças causadas por outros agentes.
Sua resposta a essas mudanças, por sua vez, causa
uma resposta para outros agentes, observando o
ambiente.
Uma cooperação indireta ocorre.
Agentes Cooperativos
Comunicativos

Podem ser divididos em sistemas
deliberativos e sistemas de negociação..

Protocolos de Cooperação:
- Contract Net Systems e
- Partial Global Planning
Protocolos de Cooperação

Contact Net Systems:
- Metodologia Orientada à Negociação

Partial Global Planning:
- Provê um exemplo de protocolo
deliberativo.
Contract Net Systems

Pode ser usado para estabelecer os
mecanismos de coordenação entre agentes
integrados em um sistema multi-agente.

O trabalho de um Contract Net Systems
começa após o problema completo a ser
resolvido ter sido dividido em subproblemas.
Contract Net Systems

O protocolo de contract net que forma a base
do Contract Net Systems define uma
linguagem comum inter-nodos que deve ser
entendida por todos os agentes.

A comunicação entre os agentes é sempre
realizada com base no formato de mensagem
apropriado do protocolo de cooperação.
Estrutura de um Contract Net Node
Task Processor
Local Data Base
Contract Processor
Comunications
Processor
Network
Local Data Base

Contém a base de conhecimento do nodo
associado e também informação sobre o
status corrente das negociações da
cooperação e o processo de resolver o
problema. Os três outros componentes usam a
base de conhecimento local para realizar suas
tarefas.
Contract Processor

Tem a tarefa de observar as tarefas oferecidas
como ofertas, o envio de aplicações e a
finalização dos contratos.

Realiza a coordenação de todos os nodos.

É responsável pelo processamento real e
solução da tarefa atribuído ao nodo.
Task Processor

Recebe o problema para ser resolvido do
Contract Processor, para determinar a
solução.

Faz uso da Local Data Base tem a tarefa de
determinar a solução e passar esta ao
Contract Processor.
Manager

Um nodo especial chamado Manager é adicionado ao
contexto dos outros módulos e tem a tarefa de
atribuição de subproblemas aos nodos (agente) na
rede.

O exemplo que segue mostra as funções do Manager,
no contexto de um processo de negociação de
contrato.
Processo de Negociação de Contrato
Manager
Nodes
Invitation for bids
Subproblem
Application
Evaluation
Contract
Confirmation
Idle
Contract
completion
Subproblem
Solution
Result
Subproblem
Evaluation
Subsolution
Ofertas

O Manager oferece publicamente ofertas
como um contrato para todo subproblema
pendente que é para ser resolvido.

Para este propósito ele usa a estrutura de
mensagem definida pelo protocolo de
contrato.
Mensagem de Publicação de Ofertas
To:
FROM:
TYPE:
ContractID:
Task Abstraction
Eligibility Specification
Bid Specification
all nodes
manager
task bid announcement
xx-yy-zz
<description of subproblem>
<list of minimum requirements>
<description of the required aplication
information>
Expiration Time
<latest possible application time>
Processo de Negociação

Ao oferecimento de ofertas é aberto a todos
os agentes e é avaliado pelo seu Contract
Processor associado.

O Contract Processor faz uso da Local Data
Base para avaliar os recursos disponíveis no
momento e o conhecimento dos agentes.
Contract Processor

O Contract Processor decide se uma
aplicação deve ser feita para a tarefa
anunciada.

Se ele chega a um resultado positivo, ele pode
informar ao Manager, de acordo com a
seguinte mensagem:
Fazendo a aplicação
TO:
FROM:
TYPE:
ContractID:
Node Abstraction:
manager
node X
application
xx-yy-zz
<description of the node’s
capability>
Manager escolhe aplicação

O Manager deve selecionar o nodo (contendo
um agente) que ele considera mais adequado,
de todas as aplicações recebidas para um
contrato específico.

Ele tem acesso ao conhecimento de avaliação
e métodos com os quais ele pode avaliar toda
aplicação.
Seleção de Aplicação

O Manager seleciona a aplicação com a
avaliação mais alta e dá a tarefa a um nodo X
para resolver o subproblema associado com o
contrato.

O Manager atribui o contrato na forma de um
mensagem de contrato:
Mensagem do Manager para um node X
TO:
FROM:
TYPE:
ContractID:
Task Specification
node X
manager
contract
xx-yy-zz
<description of
subproblem>
Confirmação de Aceitação do Contrato



O nodo X envia uma confirmação ao Manager
indicando a aceitação do contrato na forma
especificada.
Ao término da fase de resolução do problema,
o problema resolvido é transferido ao
Manager.
O node X não recebe qualquer informação
sobre o estado corrente dos outros nodos.
Excedendo os recursos



Se posteriormente um nodo X determina que a tarefa
atribuída a ele, excede sua capacidade ou recursos, é
permitido a ele subdividir o problema em então atribuir
subcontratos a outros nodos.
Neste caso, ele adota o papel do Manager e oferece
os subproblemas para ofertas aos outros agentes nos
nodos da rede.
Contract Net Systems constituem uma pura
distribuição de tarefas.
Partial Global Planning
Partial Global Planning (PGP)



Provê um exemplo de protocolo de
cooperação para sistemas multi-agente
deliberativo.
A todo agente de um sistema multi-agente é
dado a capacidade durante seu trabalho de
obter informação do estado corrente e metas
alcançadas dos outros agentes.
O agente usa este conhecimento para otimizar
sua própria tarefa.
PGP



PGP provê a coordenação de unidades
resolvendo um problema distribuído.
A condição básica para uso de PGP é que
diversos agentes distribuídos trabalham sobre
a solução de um problema completo.
Um agente, como parte do PGP, pode
observar as ações e relacionamentos entre um
grupo de outros agentes e então formar
conclusões para seu próprio trabalho.
PGP

Este conhecimento é chamado o Partial Global
Plan (Plano Global Parcial) porque reflete o
conhecimento parcial do plano deterninado
pelo agente para resolver um problema global.
Processamento PGP
comunication
A
A1
B
A2
Agent 1
B
A
A3
A2
B1
Agent 2
B2
Processamento PGP



Dois agentes trabalham sobre dois
subproblemas (A e B) de um problema.
Estes próprios subproblemas A e B consistem
de outros subproblemas (A1 à A3) e (B1 à B2).
Todo agente passa informação sobre seu
estado corrente ao seu parceiro.
Processamento PGP




No exemplo, o agente 1 comunica ao agente 2 que ele
está trabalhando sobre o subproblema ª
Similarmente, o agente 2 informa ao agente1 o seu
trabalho sobre o subproblema B.
Todo agente pode usar esta informação com relação a
situação do parceiro para o seu trabalho.
Se o agente 1 reconhece que o seu subproblema A2 é
dependente do subproblema B no agente 2, ele pode
informar o agente2 sobre tal dependência.
Processamento PGP

Em alguns casos, pode acontecer que o
subproblema A2 do agente 1 é transferido
completamente para o agente 2, porque ele
teria que processar o subproblema como parte
da solução de B.
Processo PGP

O processo PGP é subdividido em quatro
etapas consecutivas:
1. Criação dos Planos Locais para todo
agente;
2. Comunicação e troca de Planos entre
agentes;
3. Criação dos PGPs;
4. Modificação e Otimização dos PGPs.
Negociações
Negociações


Sistemas Multi-Agentes manipulam o
significado de negociações em vários modos.
Ao passo que um modo descreve as
atribuições de subproblemas e recursos como
negociação, um outro modo relaciona a
negociação direta um-a-um entre dois agentes.
Negociações


O objetivo de toda negociação é permitir uma
cooperação construtiva dentro de um grupo de
agentes independentes que têm suas próprias metas.
O protocolo de negociação provê as regras básicas
para as possíveis formas de negociação, a forma do
processo de negociação e a estratégia de negociação,
dependem da implementação específica de cada
agente.
Negociações

Embora o desenvolvedor de um agente possa
provê diferentes graus de complexidade das
capacidades de negociação, cuidado deve ser
tomado para garantir que a estratégia de
negociação e o protocolo de negociação sejam
compatíveis, isto é a estratégia selecionada
possa ser utilizada com o protocolo disponível.