Protocolos de Cooperação

Protocolos de Cooperação

Contract Net Systems Partial Global Planning Negociações


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 Cooperativo

DiscretoCooperaçã

o Emergente

ComunicativoNão-

Comunicativo

Deliberativo Negociador

Cooperativo x Independente

Existe a diferença entre agentes cooperativos e agentes independentes.


Sistemas Multi-Agente Independente

Os agentes individuais de um sistema multi-agente são completamente independentes e seguem suas próprias metas.


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


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


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

ComunicationsProcessor

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

Subproblem

Evaluation

Idle

Subproblem

Manager Nodes

Evaluation

Contractcompletion

Subproblem Solution

Subsolution

Invitation for bids

Application

Contract

Confirmation

Result

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 AbstractionEligibility SpecificationBid Specification

Expiration Time

all nodes

manager

task bid announcement

xx-yy-zz

<description of subproblem>

<list of minimum requirements><description of the required aplication

information>

<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

A B

A1 A2 A3

A B

A2 B1 B2

comunication

Agent 1 Agent 2

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.

Documents

Protocolos de Cooperação