Upload
internet
View
103
Download
0
Embed Size (px)
Citation preview
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 ?
Critérios para Avaliação de Coordenação Multiagente -
ProblemáticaProblemática
5Critérios para Avaliação de Coordenação Multiagente -
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;
Critérios para Avaliação de Coordenação Multiagente -
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]
Critérios para Avaliação de Coordenação Multiagente -
8
CoordenaçãoCoordenação
agentes necessitam informações;
recursos limitados;
otimização de custos ;
objetivos satisfeitos.
Critérios para Avaliação de Coordenação Multiagente -
9
CoordenaçãoCoordenação
Critérios para Avaliação de Coordenação Multiagente -
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]
Critérios para Avaliação de Coordenação Multiagente -
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
Critérios para Avaliação de Coordenação Multiagente -
Quadro ComparativoQuadro Comparativo
12Critérios para Avaliação de Coordenação Multiagente -
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
Critérios para Avaliação de Coordenação Multiagente -
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
Critérios para Avaliação de Coordenação Multiagente -
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
Critérios para Avaliação de Coordenação Multiagente -
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.
17Critérios para Avaliação de Coordenação Multiagente -
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.
18Critérios para Avaliação de Coordenação Multiagente -
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
Critérios para Avaliação de Coordenação Multiagente -
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)
20Critérios para Avaliação de Coordenação Multiagente -
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
Comunicação precária, restritaComunicação precária, restrita
(Pontos Focais, Matriz de (Pontos Focais, Matriz de Ganhos)Ganhos)
21Critérios para Avaliação de Coordenação Multiagente -
Escalonamento de tarefasEscalonamento de tarefas
(Sincronização)(Sincronização)
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
Situações de ConflitoSituações de Conflito
(GPGP(GPGP, , look-aheadlook-ahead,,formação de coalizão)formação de coalizão)
22Critérios para Avaliação de Coordenação Multiagente -
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
23Critérios para Avaliação de Coordenação Multiagente -
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.
24Critérios para Avaliação de Coordenação Multiagente -
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 para Avaliação de Coordenação Multiagente -
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
Critérios para Avaliação de Coordenação Multiagente -
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
28Critérios para Avaliação de Coordenação Multiagente -
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)
Critérios para Avaliação de Coordenação Multiagente -
Esquemas táticosEsquemas táticos
30Critérios para Avaliação de Coordenação Multiagente -
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.
Critérios para Avaliação de Coordenação Multiagente -
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)
Critérios para Avaliação de Coordenação Multiagente -
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.
Critérios para Avaliação de Coordenação Multiagente -
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%
Critérios para Avaliação de Coordenação Multiagente -
Resultados - Avaliação Resultados - Avaliação a a PosterioriPosteriori
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
Critérios para Avaliação de Coordenação Multiagente -
Resultados - Avaliação Resultados - Avaliação a a PosterioriPosteriori
36
critério 2: características da tomada de decisão
Com comunicaçãoPontos focais
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
Critérios para Avaliação de Coordenação Multiagente -
Resultados - Avaliação Resultados - Avaliação a a PosterioriPosteriori
37
critério 3: características de flexibilidade
não afetado
Com comunicaçãoPontos focais
Conflitos
Tempo comunicação
Tomada de decisão
Novos agentes
sem alterações
01
podem aumentar
01
afetado
sem alterações
podem aumentar
Critérios para Avaliação de Coordenação Multiagente -
Resultados - Avaliação Resultados - Avaliação a a PosterioriPosteriori
38
critério 4: taxa de sucesso na resolução de conflitos
48%
Com comunicaçãoPontos focais
Conflitos resolvidos
Taxa satisfatória
Conflitos surgidos (total)
Total simulações
25
50
12
50
25
09
36%
Critérios para Avaliação de Coordenação Multiagente -
39Critérios para Avaliação de Coordenação Multiagente -
Estudo de CasoEstudo de Caso - - Gerenciamento Gerenciamento de Agendas Distribuídas de Agendas Distribuídas [SIL 2003][SIL 2003]
40Critérios para Avaliação de Coordenação Multiagente -
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)
41Critérios para Avaliação de Coordenação Multiagente -
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
42Critérios para Avaliação de Coordenação Multiagente -
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
43Critérios para Avaliação de Coordenação Multiagente -
Resultados - Resultados - Avaliação Avaliação a a PosterioriPosteriori
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.
44Critérios para Avaliação de Coordenação Multiagente -
Resultados - Resultados - Avaliação Avaliação a a PosterioriPosteriori
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.
45Critérios para Avaliação de Coordenação Multiagente -
Resultados - Resultados - Avaliação Avaliação a a PosterioriPosteriori
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
Critérios para Avaliação de Coordenação Multiagente -
ContribuiçõesContribuições
47Critérios para Avaliação de Coordenação Multiagente -
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
Critérios para Avaliação de Coordenação Multiagente -
Utilizar critérios com pesos
Estudo de novos modelos de coordenação
Proposta de novos critérios
Novos estudos de caso