Universidade Federal do Rio Grande do Sul
Instituto de Informática
Programa de Pós-Graduação em Computação
Critérios para Avaliação de
Coordenação Multiagente
Rejane Frozza
Prof. Dr. Luis Otávio Campos Alvares
(orientador)
(Defesa de Tese de Doutorado)
Sumário
 Escopo
 Motivação
 Problemática
 Objetivos
 Coordenação
 Proposta para Avaliação
 Aplicação e Resultados
 Conclusões, Contribuições e Trabalhos Futuros
Critérios para Avaliação de Coordenação Multiagente -
2
Escopo do Trabalho
Inteligência Artificial
Sistemas Multiagentes
Coordenação
Avaliação
Critérios para Avaliação de Coordenação Multiagente -
3
Motivação
Atividades Humanas
Coordenação
Por que avaliar ?
Para que avaliar ?
Mas ...
Como avaliar ?
Critérios para Avaliação de Coordenação Multiagente -
4
Problemática
Qual modelo/mecanismo de coordenação
melhor se adapta para a solução de um problema
de coordenação específico ?
?
?
? ?
? ?
Avaliação
Critérios para Avaliação de Coordenação Multiagente -
5
Objetivos
 apresentar uma proposta de avaliação para
a coordenação, voltada aos projetistas e
desenvolvedores de sistemas multiagentes;
 fornecer critérios que auxiliem a tomada de
decisão de qual modelo de coordenação utilizar
em uma aplicação multiagente;
 fornecer critérios que possam avaliar o
comportamento de um sistema coordenado.
Critérios para Avaliação de Coordenação Multiagente -
6
Metodologia
 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 -
7
Coordenação
 agentes necessitam informações;
 recursos limitados;
 otimização de custos ;
 objetivos satisfeitos.
Critérios para Avaliação de Coordenação Multiagente -
8
Coordenação
Capacidade dos agentes organizarem suas
ações (individuais ou coletivas) para serem
executadas de maneira coerente no ambiente
onde co-habitam, evitando conflitos, gerenciando
recursos disponíveis, explorando a tomada de
decisão e chegando a resultados satisfatórios.
Critérios para Avaliação de Coordenação Multiagente -
9
Mecanismos 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, Reatividade
e Regulamentação
[Ferber, 1995]
Critérios para Avaliação de Coordenação Multiagente - 10
Modelos de Coordenação
Modelos de Coordenação
em 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 - 11
Quadro Comparativo
Formação Look- Pontos Comunicação Matriz de GPGP
de coalizão ahead focais de avaliação ganhos
Preditividade
Adaptabilidade
Controle das ações
Comunicação
Conflitos
Troca de informações
Tipo do agente
Aplicações
Vantagens
Desvantagens
...
Coordenação sem comunicação:
matriz de ganhos, pontos focais,
regras
Coordenação
com comunicação:
. . . trocadas entre os
informações
Mecanismo
para resolução
agentes
de conflitos
...
Critérios para Avaliação de Coordenação Multiagente -
12
Mecanismos x Modelos
. Look-ahead
Sincronização .
. Formação de coalizão
Planejamento .
Reativa .
Regulamentação .
. Pontos focais
. Comunicação de avaliação
. Matriz de ganhos
. GPGP
Critérios para Avaliação de Coordenação Multiagente -
13
Avaliação
Avaliação Qualitativa
Avaliação Quantitativa
Avaliação
tomada de decisão
Critérios
grau de importância
Critérios para Avaliação de Coordenação Multiagente -
14
Avaliação da Coordenação
Alguns trabalhos relacionados:
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
Durfee [DUR 2001] - população de agentes, ambiente
e solução
Excelente [EXC 2002] - recompensa obtida pelo agente
nas tarefas
Critérios para Avaliação de Coordenação Multiagente -
15
Proposta para avaliação
preditividade
adaptabilidade
Características e
capacidades dos
agentes
Análise do
problema para
escolha do
modelo de
coordenação
(classificação)
Coordenação
Multiagente
controle das ações
comunicação
conflitos
troca de informações
tipo do agente
Características da
aplicação
ambiente da aplicação
taxa de qualidade dos resultados
características da tomada de decisão
Avaliação
a posteriori
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 (classificação)
Destina-se a melhorar o processo de tomada
de decisão sobre a escolha de um modelo de
coordenação adequado às características do
problema.
São fornecidas considerações
sobre a escolha de um ou outro
modelo de coordenação.
Critérios para Avaliação de Coordenação Multiagente -
17
Classificação (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.
Critérios para Avaliação de Coordenação Multiagente -
18
Classificação (questões)
Questionário:
Os agentes possuem /possuirão conhecimento das capacidades dos
outros agentes ?
( ) não
( ) sim
Os agentes possuem /possuirão a capacidade de prever o estado futuro
do ambiente ou do comportamento/ações dos outros agentes ?
( ) não
( ) sim, alguns agentes
( ) sim, todos agentes
Critérios para Avaliação de Coordenação Multiagente -
19
Relação: questões - coordenaçã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
Ambientes dinâmicos - tomada de
decisão rápida
(Reatividade)
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
Protocolo de comunicação,
decisão sobre planos
(Planejamento)
Critérios para Avaliação de Coordenação Multiagente -
20
Relação: questões - coordenaçã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
Comunicação precária, restrita
(Pontos Focais, Matriz de
Ganhos)
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
Escalonamento de tarefas
(Sincronização)
Critérios para Avaliação de Coordenação Multiagente -
21
Relação: questões - coordenaçã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
Situações de Conflito
(GPGP, look-ahead,
formação de coalizã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 necessáriaanalisar o objetivo da
comunicação
Critérios para Avaliação de Coordenação Multiagente -
22
Proposta para avaliação
preditividade
adaptabilidade
Características e
capacidades dos
agentes
Análise do
problema para
escolha do
modelo de
coordenação
(classificação)
Coordenação
Multiagente
controle das ações
comunicação
conflitos
troca de informações
tipo do agente
Características da
aplicação
ambiente da aplicação
taxa de qualidade dos resultados
características da tomada de decisão
Avaliação
a posteriori
características de flexibilidade
taxa de sucesso na resolução de conflitos
(critérios)
Critérios para Avaliação de Coordenação Multiagente -
23
Avaliação a Posteriori
É 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.
Critérios para Avaliação de Coordenação Multiagente -
24
Avaliação a Posteriori (critérios)
Critérios propostos:
Taxa = (resultados satisfatórios/
total de simulações)*100
 taxa de qualidade dos resultados
(taxa de resultados satisfatórios atingidos)
 características da tomada de decisão pelos
agentes
Número de agentes, tempo
dispendido,
(capacidade dos agentes decidirem
sobre comunicação
as
ações a serem realizadas em determinadas
situações)
Critérios para Avaliação de Coordenação Multiagente -
25
Avaliação a Posteriori (critérios)
Critérios propostos:
Escalabilidade do método,
situação imprevista
 características de flexibilidade do modelo de
coordenação
(facilidade na incorporação/redução de agentes)
Taxa de
= (conflitos
conflitosresolvidos /
 taxa de sucesso na resolução
total de conflitos)*100
(resolução dos conflitos que surgem
durante
as atividades dos agentes)
Critérios para Avaliação de Coordenação Multiagente -
26
Critérios Propostos x Trabalhos
Relacionados
Frozza
- 6 modelos de coordenação
- critérios para análise do problema
- critérios a posteriori
Jong
- um único modelo de coordenação
- um único critério: taxa de captura da presa
- avaliação sobre o modelo de coordenação desenvolvido
Barber
- 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
Durfee
- 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)
Excelente - agentes selecionam mecanismos de coordenação
- critérios: recompensa total obtida pelo agente, número de tarefas cooperativas
Critérios para Avaliação de Coordenação Multiagente -
27
Estudo de Caso - Robocup
Aplicação - Time UFRGS [Bagatini, 2001]
Critérios para Avaliação de Coordenação Multiagente -
28
Coordenação - Time UFRGS
 Modelos de coordenação
Classificação
implementados
(questionário)
Pontos Focais (sem comunicação)
Com comunicação (oferecida pelo Soccerserver)
 Definição de esquemas táticos (jogadas)
Jogada de ataque: 5 jogadores
Objetivo: fazer gol
Critérios para Avaliação de Coordenação Multiagente -
29
Esquemas táticos
Critérios para Avaliação de Coordenação Multiagente -
30
Esquemas Táticos - Características
e Valores
Características
chuta de longe
marcação
individualismo
chute a gol
distância do gol


Valores das Características e Descrição
2
1
3
chuta bem
chuta mal
não está marcado
está marcado
é individualista não é individualista
chuta bem a gol não chuta bem a gol
próxima
média
longe
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 -
31
Coordenação - Pontos Focais [Fenster, 1998]
 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 -
32
Coordenação – Com Comunicação
 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 -
33
Resultados - Avaliação a Posteriori
 critério 1: taxa de qualidade dos resultados
Pontos focais
Com comunicação
Total simulações
50
50
Resultados satisfatórios
31
26
19
62%
24
52%
Resultados insatisfatórios
Taxa satisfatória
Critérios para Avaliação de Coordenação Multiagente -
34
Resultados - Avaliação a Posteriori
 Número de gols por esquema tático
Número de Gols por Esquema Tático
20
19
17
15
12
10
9
5
0
P.F. +
E.T. 1
P.F. +
E.T. 2
C.C. +
E.T. 1
C.C. +
E.T. 2
Número de Gols
Critérios para Avaliação de Coordenação Multiagente -
35
Resultados - Avaliação a Posteriori
 critério 2: características da tomada de decisão
Total de agentes
Agentes envolvidos na
tomada de decisão
Pontos focais
Com comunicação
05
05
02
01
Conhecimento
esquemas táticos
Comunicação
sem
esquemas táticos,
próprias caract.
com
Critérios para Avaliação de Coordenação Multiagente -
36
Resultados - Avaliação a Posteriori
 critério 3: características de flexibilidade
Pontos focais
Com comunicação
Novos agentes
01
01
Tomada de decisão
sem alterações
sem alterações
Conflitos
podem aumentar
não afetado
podem aumentar
afetado
Tempo comunicação
Critérios para Avaliação de Coordenação Multiagente -
37
Resultados - Avaliação a Posteriori
 critério 4: taxa de sucesso na resolução de conflitos
Pontos focais
Com comunicação
Total simulações
50
50
Conflitos surgidos (total)
25
25
12
48%
09
36%
Conflitos resolvidos
Taxa satisfatória
Critérios para Avaliação de Coordenação Multiagente -
38
Estudo de Caso - Gerenciamento de Agendas
Distribuídas [SIL 2003]
Critérios para Avaliação de Coordenação Multiagente -
39
Modelo de Coordenação (classificaçã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)
Critérios para Avaliação de Coordenação Multiagente -
40
Experimentos
 Primeira Simulação
Agenda com compromissos locais individuais e
conflitos internos
 Segunda Simulação
Agenda com compromissos não-locais com conflitos
locais
 Terceira Simulação
Agenda com compromissos não-locais com conflitos
globais
Critérios para Avaliação de Coordenação Multiagente -
41
Resultados - Avaliação a Posteriori
 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érios para Avaliação de Coordenação Multiagente -
42
Resultados - Avaliação a Posteriori
 critério 2: características da tomada de decisão
Número total de agentes = variável; nas simulações
foram usados 1 e 4 agentes Agenda.
Agentes no processo de tomada de decisão = agentes
que têm compromisso em comum.
Conhecimento da Agenda = sua estrutura interna e as
preferências do usuário.
Envolve processo de negociação e comunicação.
Critérios para Avaliação de Coordenação Multiagente -
43
Resultados - Avaliação a Posteriori
 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érios para Avaliação de Coordenação Multiagente -
44
Resultados - Avaliação a Posteriori
critério 4: taxa de sucesso na resolução de conflitos
Taxa de conflitos resolvidos = 100%
Conflitos : colisões de horários.
Conflitos resolvidos : consenso de horários.
Critérios para Avaliação de Coordenação Multiagente -
45
Conclusões
 Escolha de um modelo de coordenação
características desejadas para a solução
do problema
 Avaliação
visão do avaliador, objetivo da aplicação
 Aplicabilidade da classificação e avaliação
a posteriori.
Critérios para Avaliação de Coordenação Multiagente -
46
Contribuições
 Comparação entre modelos de coordenação




Relação entre mecanismos e modelos
Proposta de avaliação (dois momentos)
Critérios de avaliação
Integração no ciclo de desenv. de sistemas
 Uso da abordagem GQM
 Avaliação: projetista/desenvolvedor de sistemas
 Modelos de coordenação - Time UFRGS
Critérios para Avaliação de Coordenação Multiagente -
47
Trabalhos Futuros
 Sistema de raciocício baseado em casos para
automatizar a classificação
 Utilizar critérios com pesos
 Estudo de novos modelos de coordenação
 Proposta de novos critérios
 Novos estudos de caso
Critérios para Avaliação de Coordenação Multiagente -
48