Critérios para Avaliação de Coordenação Multiagente

Critérios para Avaliação Critérios para Avaliação dede

Coordenação Coordenação

MultiagenteMultiagente Rejane Frozza

Prof. Dr. Luis Otávio Campos Alvares(orientador)

Universidade Federal do Rio Grande do SulUniversidade Federal do Rio Grande do Sul

Instituto de InformáticaInstituto de Informática

Programa de Pós-Graduação em ComputaçãoPrograma de Pós-Graduação em Computação

(Defesa de Tese de Doutorado)

SumárioSumário

2Critérios para Avaliação de Coordenação Multiagente -

Motivação

Objetivos

Problemática

Coordenação

Escopo

Proposta para Avaliação

Aplicação e Resultados

Conclusões, Contribuições e Trabalhos Futuros

Escopo do TrabalhoEscopo do Trabalho

3

Inteligência Artificial

Sistemas Multiagentes

Critérios para Avaliação de Coordenação Multiagente -

Avaliação

Coordenação

MotivaçãoMotivação

4

CoordenaçãoCoordenação

Atividades Humanas

Mas ...

Por que avaliar ?Por que avaliar ?

Para que avaliar ?Para que avaliar ?

Como avaliar ?Como avaliar ?


ProblemáticaProblemática


Qual modelo/mecanismo de coordenação

melhor se adapta para a solução de um problema

de coordenação específico ?

? ?

? ? ? ?

AvaliaçãoAvaliação

ObjetivosObjetivos

fornecer critérios que auxiliem a tomada de decisão de qual modelo de coordenação utilizarem uma aplicação multiagente;

fornecer critérios que possam avaliar ocomportamento de um sistema coordenado.

6

apresentar uma proposta de avaliação paraa coordenação, voltada aos projetistas edesenvolvedores de sistemas multiagentes;


MetodologiaMetodologia

7

Visão do conceito de coordenação Jennings [JEN 93 e 96], Malone [MAL 94], Durfee [DUR 2001] Ciancarini [CIA 2000], Huhns e Stephens [HUH 99], Ferber [FER 95]

Mecanismos de coordenação Jennings [JEN 96], Lesser [LES 98], Decker [DEC 95], Ferber [FER 95] Kuwabara [KUW 95], Nagendra [NAG 97], Ossowski [OSS 99]

Aplicações (modelos) Sheory [SHE 97], Liu [LIU 2000], Modi [MOD 2000], Jong [JON 97] Reis [REI 2001], Andrade [AND 2002], Yunpeng [YUN 2001], Goldberg [GOL 99], Tambe [TAM 99], Callantine [CAL 2003]

Avaliação de coordenação Jong [JON 99], Barber [BAH 2000], Durfee [DUR 2001], Excelente-Toledo [EXC 2002]


8


agentes necessitam informações;

recursos limitados;

otimização de custos ;

objetivos satisfeitos.


9



Capacidade dos agentes organizarem suas

ações (individuais ou coletivas) para seremexecutadas de maneira coerente no ambienteonde co-habitam, evitando conflitos, gerenciandorecursos disponíveis, explorando a tomada de decisão e chegando a resultados satisfatórios.

10

Mecanismos de CoordenaçãoMecanismos de Coordenação

Organização, Planejamento e Negociação [Ossowski, 1999]

Organização, Contrato, Planejamento e Negociação [Jennings e Nwana, 1996]

Sincronização, Planejamento, Reatividadee Regulamentação

[Ferber, 1995]


11

Modelos de CoordenaçãoModelos de Coordenação

Modelos de Coordenaçãoem algumas Aplicações

Formação de Coalizão

Look-Ahead

Pontos Focais

Comunicação de Avaliação

Matriz de Ganhos

GPGP


Quadro ComparativoQuadro Comparativo


Preditividade

AdaptabilidadeControle das açõesComunicaçãoConflitosTroca de informaçõesTipo do agenteAplicaçõesVantagens

Desvantagens

Formaçãode coalizão

Look-ahead

Pontosfocais

Comunicaçãode avaliação

Matriz deganhos

GPGP

. . .

. . .

. . .

Coordenação sem comunicação:matriz de ganhos, pontos focais,

regrasCoordenação com comunicação:informações trocadas entre os

agentesMecanismo para resoluçãode conflitos

13

Mecanismos x ModelosMecanismos x Modelos


Sincronização .

Planejamento .

Reativa .

Regulamentação .

. Look-ahead

. Formação de coalizão

. Pontos focais

. Comunicação de avaliação

. Matriz de ganhos

. GPGP

14

AvaliaçãoAvaliação

Avaliação Qualitativa

Avaliação Quantitativa

Avaliação

Critérios

tomada de decisão

grau de importância


15

Avaliação da CoordenaçãoAvaliação da Coordenação

Jong [JON 99] - problema da presa e do predador (Sinais de Avaliação -técnica de aprendizado por reforço)

Barber [BAH 2000] - flexibilidade, custo da solução de coordenação, qualidade da solução do problema

Alguns trabalhos relacionados:

Durfee [DUR 2001] - população de agentes, ambientee solução


Excelente [EXC 2002] - recompensa obtida pelo agente nas tarefas

Proposta para avaliaçãoProposta para avaliação

Análise do problema para

escolha do modelo de

coordenação(classificação)

Coordenação Multiagente

Avaliaçãoa posteriori

Características e capacidades dos

agentes

Características da aplicação

conflitos

troca de informações

ambiente da aplicação

tipo do agente

comunicação

controle das ações

adaptabilidade

preditividade

taxa de qualidade dos resultados

características da tomada de decisão

características de flexibilidade

taxa de sucesso na resolução de conflitos

(critérios)

Critérios para Avaliação de Coordenação Multiagente - 16

Análise do Problema Análise do Problema (classificação)(classificação)

Destina-se a melhorar o processo de tomadade decisão sobre a escolha de um modelo decoordenação adequado às características doproblema.

São fornecidas considerações sobre a escolha de um ou outro

modelo de coordenação.


ClassificaçãoClassificação (critérios) (critérios)

Critérios relacionados:

preditividade;

adaptabilidade;

controle das ações;

comunicação;

conflitos;

troca de informação;

tipo do agente;

ambiente da aplicação.


ClassificaçãoClassificação (questões) (questões)

Questionário:

19

Os agentes possuem /possuirão a capacidade de prever o estado futuro do ambiente ou do comportamento/ações dos outros agentes ?

( ) sim, alguns agentes

( ) não

Os agentes possuem /possuirão conhecimento das capacidades dos outros agentes ?

( ) não

( ) sim

( ) sim, todos agentes


Relação: Relação: questões - questões - coordenaçãocoordenação

Formação de Coalizão Pontos Focais

Questão 1 sim não

Questão 2 não sim, todos

Questão 3 sim sim

Questão 4 distribuído distribuído

Questão 5 cooperar/colaborar/tomada decisão não existe

Questão 6 com todos não se aplica

Questão 7 funciona bem não há / precário

Questão 8 não / sim e existe negociação não

Questão 9 sim e resolvidos não/sim e não resolvidos

Questão 10 comunicação não ocorre / ambiente

Questão 11 heterogêneos ambos

Questão 12 dinamicidade simulações

Ambientes dinâmicos - tomada de Ambientes dinâmicos - tomada de decisão rápidadecisão rápida

(Reatividade)(Reatividade)

Protocolo de comunicação, Protocolo de comunicação, decisão sobre planosdecisão sobre planos

(Planejamento)(Planejamento)




Questão 1 sim não


Questão 3 sim sim










Comunicação precária, restritaComunicação precária, restrita

(Pontos Focais, Matriz de (Pontos Focais, Matriz de Ganhos)Ganhos)


Escalonamento de tarefasEscalonamento de tarefas

(Sincronização)(Sincronização)



Questão 1 sim não


Questão 3 sim sim










Situações de ConflitoSituações de Conflito

(GPGP(GPGP, , look-aheadlook-ahead,,formação de coalizão)formação de coalizão)


Comunicação necessária-Comunicação necessária-analisar o objetivo daanalisar o objetivo da

comunicaçãocomunicação

Proposta para avaliaçãoProposta para avaliação


Análise do problema para

escolha do modelo de

coordenação(classificação)

Coordenação Multiagente

Avaliaçãoa posteriori

Características e capacidades dos

agentes

Características da aplicação

conflitos

troca de informações

ambiente da aplicação

tipo do agente

comunicação

controle das ações

adaptabilidade

preditividade

taxa de qualidade dos resultados

características da tomada de decisão

características de flexibilidade

taxa de sucesso na resolução de conflitos

(critérios)

Avaliação Avaliação a a PosterioriPosteriori

É aplicada sobre o mecanismo de coordenação escolhido e desenvolvido. Utilizam-se critérios para verificar o comportamento do sistema em relação à coordenação.


São fornecidas características e dados numéricos do comportamento

da coordenação.

Avaliação Avaliação a Posteriori a Posteriori (critérios)(critérios)

Critérios propostos:

taxa de qualidade dos resultados(taxa de resultados satisfatórios atingidos)

características da tomada de decisão pelosagentes(capacidade dos agentes decidirem sobre asações a serem realizadas em determinadassituações)

25

Taxa = (resultados satisfatórios/Taxa = (resultados satisfatórios/total de simulações)*100total de simulações)*100

Número de agentes, tempoNúmero de agentes, tempodispendido, comunicaçãodispendido, comunicação


Critérios propostos:

características de flexibilidade do modelo decoordenação(facilidade na incorporação/redução de agentes)

taxa de sucesso na resolução de conflitos(resolução dos conflitos que surgem duranteas atividades dos agentes)

26

Taxa = (conflitos resolvidos /Taxa = (conflitos resolvidos /total de conflitos)*100total de conflitos)*100

Escalabilidade do método,Escalabilidade do método,situação imprevistasituação imprevista


Avaliação Avaliação a Posteriori a Posteriori (critérios)(critérios)

Critérios Propostos x Trabalhos Critérios Propostos x Trabalhos RelacionadosRelacionados

Critérios para Avaliação de Coordenação Multiagente - 27

Frozza

Jong

Barber

Durfee

Excelente

- 6 modelos de coordenação- critérios para análise do problema- critérios a posteriori

- um único modelo de coordenação- um único critério: taxa de captura da presa- avaliação sobre o modelo de coordenação desenvolvido

- negociação, arbítrio, voto, auto-modificação (técnicas: resolução conflitos)- critérios: comunicação, mensagens trocadas entre agentes, tempo de CPU,tempo de tomada de decisão, qualidade da solução

- agentes selecionam mecanismos de coordenação- critérios: recompensa total obtida pelo agente, número de tarefas cooperativas

- não especifica modelos/mecanismos de coordenação- critérios : população de agentes (heterogeneidade, complexidade), ambiente (interações, mudanças, distributividade), solução (resultados satisfatórios)

Estudo de CasoEstudo de Caso - Robocup - Robocup


Aplicação - Time UFRGS [Bagatini, 2001]

Coordenação - Time Coordenação - Time UFRGSUFRGS

Modelos de coordenação implementados

Definição de esquemas táticos (jogadas)

Pontos Focais (sem comunicação) Com comunicação (oferecida pelo Soccerserver)

Jogada de ataque: 5 jogadores Objetivo: fazer gol

29

Classificação Classificação (questionário)(questionário)


Esquemas táticosEsquemas táticos


Esquemas Táticos - Características Esquemas Táticos - Características e Valorese Valores

31

Valores das Características e Descrição

não é individualista

longemédiapróxima

não chuta bem a golchuta bem a gol

não está marcadoestá marcado

chuta malchuta bem

é individualista

321Características

chuta de longe

marcação

individualismo

chute a gol

distância do gol

Esquema tático 1: 1,1,1,1,2 ou 3. Esquema tático 2: 2,1,2,1,1.


Coordenação - Pontos FocaisCoordenação - Pontos Focais [Fenster, 1998][Fenster, 1998]

32

Coordenação sem comunicação explícita. Pontos focais = pontos de convergência. Propriedades = raridade e extremidade.

Focal (esquema tático) = raridade(característica) + 0,5*extremidade(característica)


Coordenação – Com Coordenação – Com ComunicaçãoComunicação

33

Tomada de decisão individual para escolha do esquema tático.

Comunicação da escolha aos outros agentes.

Método do vizinho mais próximo para a decisão.

Protocolo de comunicação.


Resultados - Avaliação Resultados - Avaliação a a PosterioriPosteriori

34

critério 1: taxa de qualidade dos resultados

62%

Com comunicaçãoPontos focais

Resultados insatisfatórios

Taxa satisfatória

Resultados satisfatórios

Total simulações

31

50

19

50

26

24

52%



35

Número de gols por esquema tático

P.F. +E.T. 1

P.F. +E.T. 2

C.C. +E.T. 1

C.C. +E.T. 2

19

12

17

9

0

5

10

15

20

Número de Gols por Esquema Tático

Número de Gols



36

critério 2: características da tomada de decisão


Agentes envolvidos natomada de decisão

Total de agentes

02

05 05

01

Conhecimento esquemas táticos

esquemas táticos,próprias caract.

Comunicação sem com



37

critério 3: características de flexibilidade

não afetado


Conflitos

Tempo comunicação

Tomada de decisão

Novos agentes

sem alterações

01

podem aumentar

01

afetado

sem alterações

podem aumentar



38

critério 4: taxa de sucesso na resolução de conflitos

48%


Conflitos resolvidos

Taxa satisfatória

Conflitos surgidos (total)

Total simulações

25

50

12

50

25

09

36%



Estudo de CasoEstudo de Caso - - Gerenciamento Gerenciamento de Agendas Distribuídas de Agendas Distribuídas [SIL 2003][SIL 2003]


Modelo de Coordenação Modelo de Coordenação ((classificaçãoclassificação))

Modelo de coordenação desenvolvido

Planejamento distribuído(atividades de agendamento de compromissos)

Modelo de coordenação sugerido

GPGP(planejamento com protocolos de comunicação e negociação)


ExperimentosExperimentos

Agenda com compromissos locais individuais e conflitos internos

Primeira Simulação

Agenda com compromissos não-locais com conflitos locais

Segunda Simulação

Agenda com compromissos não-locais com conflitos globais

Terceira Simulação


Resultados - Resultados - Avaliação Avaliação a a PosterioriPosteriori

critério 1: taxa de qualidade dos resultados

Taxa de resultados satisfatórios = 100%

Resultados satisfatórios = conflitos resolvidos

Resultados insatisfatórios = compromissos cancelados



critério 2: características da tomada de decisão

Número total de agentes = variável; nas simulaçõesforam usados 1 e 4 agentes Agenda.

Agentes no processo de tomada de decisão = agentesque têm compromisso em comum.

Conhecimento da Agenda = sua estrutura interna e aspreferências do usuário.Envolve processo de negociação e comunicação.



critério 3: características de flexibilidade

Complexidade da agenda: carga de horários indisponíveis, horários com compromissos locais e não-locais de alta prioridade, solicitações de reuniões.Processo de negociação: número de mensagens trocadas, tempo de comunicação entre os agentes (até a marcação de um novo compromisso).

Conflitos tendem a aumentar.



critério 4: taxa de sucesso na resolução de conflitos

Conflitos : colisões de horários.

Taxa de conflitos resolvidos = 100%

Conflitos resolvidos : consenso de horários.

ConclusõesConclusões

46

Avaliação

Aplicabilidade da classificação e avaliação a posteriori.

Escolha de um modelo de coordenação

características desejadas para a solução do problema

visão do avaliador, objetivo da aplicação


ContribuiçõesContribuições


Proposta de avaliação (dois momentos)

Uso da abordagem GQM

Comparação entre modelos de coordenação

Integração no ciclo de desenv. de sistemas

Relação entre mecanismos e modelos

Critérios de avaliação

Avaliação: projetista/desenvolvedor de sistemas Modelos de coordenação - Time UFRGS

Trabalhos FuturosTrabalhos Futuros

48

Sistema de raciocício baseado em casos paraautomatizar a classificação


Utilizar critérios com pesos

Estudo de novos modelos de coordenação

Proposta de novos critérios

Novos estudos de caso

Documents

Critérios para Avaliação de Coordenação Multiagente