SIMULAÇÃO DE
PARCERIAS ENTRE
AGENTES
Uma extensão do sistema PART-NET
Dissertação de Mestrado
Aluno: Júlio de Lima do Rêgo Monteiro
Orientador: Prof. Dr. Jaime Simão Sichman
Escola Politécnica da Universidade de São Paulo
Programa de Pós-graduação em Engenharia Elétrica
Área de Concentração: Sistemas Digitais
Junho de 2004
1
Organização da Apresentação
1.
2.
3.
4.
5.
6.
7.
8.
9.
Introdução
Simulação Baseada em Multiagentes
Teoria da Dependência
Sistema PART-NET
Extensões Operacionais: PartNET+
Extensões Funcionais: PartNET++
Algoritmo para Múltiplos Agentes
Resultados Obtidos
Conclusões
2
1. Introdução
Escopo
IA
SMA
MABS
Simulação
de parcerias
PartNET++
3
1. Introdução
Objetivos



Desenvolver uma ferramenta de simulação
de parcerias entre múltiplos agentes;
Implementar um novo algoritmo para o
cálculo de parcerias entre múltiplos agentes
utilizando hipergrafos;
Estudar o efeito de graus de liberdade
introduzidos com o novo modelo.
4
1. Introdução
Metodologia
1.
2.
3.
4.
Partir do sistema PART-NET [Conte98], que
suporta parcerias entre duplas de agentes;
Reescrever o sistema, para torná-lo mais
extensível, gerando o PartNET+;
Implementar Planos e Grafos de
Dependência, dando suporte a parcerias
entre múltiplos agentes, gerando o
PartNET++;
Comparar os resultados com o PART-NET.
5
2. MABS
Sistemas Multiagentes

A Inteligência Artificial Distribuída (IAD) se
subdivide em [Durfee94]:

Resolução Distribuída de Problemas (RDP):



Agentes resolvem um problema;
Sistemas fechados.
Sistemas Multiagentes (SMA):


Agentes autônomos, objetivos próprios;
Sistemas abertos.
6
2. MABS
Agentes

Sistema de software dotados das seguintes
capacidades: [Wooldridge’94]




autonomia – capacidade de funcionar sem a
intervenção externa;
reatividade – capacidade de perceber e reagir ao
meio ao redor;
interação social – alguma forma de linguagem
ou comunicação;
pró-atividade – presença de objetivos
individuais, planejamento e iniciativa.
7
2. MABS
Simulação
PROBLEMA
Observação
Validação
MODELO
DADOS
Implementação
Execução
SIMULADOR
[Gilbert99]
8
2. MABS
Ferramentas x Ambientes

Ambientes de Simulação




voltados para uma área determinada;
permite alterações no modelo, através de
programação;
configuração complexa.
Ferramentas de Simulação:



voltadas para problemas específicos;
modelo determinado;
configuração simples.
9
3. Teoria da Dependência
Fundamentos

Proposta em [Castelfranchi90], introduz os
seguintes conceitos:


dependência social: quando um agente não tem
a capacidade de realizar uma ação, torna-se
dependente de um outro que é capaz de realizála para ele;
poder social: um agente exerce um certo poder
social sobre um outro que dependa socialmente
dele.
10
3. Teoria da Dependência
Parcerias

No caso de dependência bilateral:


cooperação: mesmo objetivo, os agentes
se ajudam realizando ações
complementares;
escambo: objetivos diferentes, os agentes
trocam ações necessárias para cada um
deles.
11
3. Teoria da Dependência
Redes de Dependência
Exemplo de rede de dependência [Sichman02]
12
3. Teoria da Dependência
Tipos de Dependência

OR-dependence:

AND-dependence:

PLAN-dependence:

GOAL-dependence:
13
3. Teoria da Dependência
Grafo de Dependência
Exemplo de grafo de dependência, baseado em [Sichman02]
14
4. Sistema PART-NET
Objetivos



Uso da simulação para mostrar a importância
de diferentes estratégias de agentes na
formação de parcerias entre duplas de
agentes;
Comprovar certas hipóteses a respeito do
comportamento das citadas estratégias;
Enfatizar o potencial da simulação
computacional em ciências sociais para
melhorar teorias existentes e para
desenvolver novas teorias.
15
4. Sistema PART-NET
Arquitetura

Os agentes são compostos de:




conjunto de ações:
 tipo
 custo
 usado (0 ou 1)
conjunto de objetivos:
 tipo
 prioridade
 usado (0 ou 1)
estratégia (substancialista, utilitário ou avaro)
conhecimento de todas as relações de dependência da
sociedade.
16
4. Sistema PART-NET
Descrição

Uma ferramenta em MABS para simular parcerias
entre duplas de agentes seguindo as estratégias:
 Substancialistas: priorizam objetivos mais
importantes, sem se preocupar com custos;
 Utilitaristas: analisam a relação custo-benefício,
maximizando a função utilidade;
 Avaros: minimizam os gastos, não se importando
com o valor dos objetivos.
17
4. Sistema PART-NET
Algoritmo
Sociedade
de agentes
cada
agente
ordena
PML
estratégia
EML
parcerias
recíprocas
conflitos
Agentes
usados
apenas uma ação por ciclo
18
4. Sistema PART-NET
Hipóteses
H1. Em sociedades homogêneas, o benefício dos utilitários é maior do que
o dos substancialistas, que é maior do que o dos avaros.
Bu > Bs > Ba
H2. Em sociedades homogêneas, os substancialistas têm um resultado
melhor quando há mais objetivos por agente.
Bs1 > Bs2 se |Gs1| > |Gs2|
H3. Em sociedades heterogêneas, os substancialistas acabam superando
os utilitários em termos de ganho líquido acumulado.
Bis > Biu
H4. O benefício líquido dos mistos é maior do que a média dos benefícios
líquidos em sociedades homogêneas
Bm > (Bu + Bs + Ba)/3
19
4. Sistema PART-NET
Resultados
Gráfico da Hipótese H4 [Conte98]
20
4. Sistema PART-NET
Interface Gráfica
21
4. Sistema PART-NET
Limitações
Interface com o usuário pouco
desenvolvida;
 Trata apenas de parcerias entre duplas
de agentes;
 Falta de especificação apropriada;
 Dificuldades para reutilização.

22
5. Extensões Operacionais
Sistema PartNET+





reengenharia do software;
aprimoramento da interface gráfica;
resultados gráficos;
gerador randômico de sociedades;
leitura e gravação da simulação em XML.
23
5. Extensões Operacionais
Interface Gráfica
24
[Monteiro 03]
5. Extensões Operacionais
Resultados Gráficos
[Monteiro 03]
25
5. Extensões Operacionais
Arquivos XML
<society>
<agent name="a0S" strategy="substantialist"
gross_benefit="0" total_cost="0"
objectives_reached="0">
<goal name="g1" type="1" priority="1144"
status="false" />
<action name="a0" type="0" cost="187"
status="false" />
</agent>
......
26
6. Extensões Funcionais
Sistema PartNET++



formalismo de planos;
grafos de dependência;
algoritmo de busca de parcerias entre
múltiplos agentes.
27
6. Extensões Funcionais
Planos



Um plano é um conjunto de ações que
devem ser realizadas para atingir um
determinado objetivo;
Permite parcerias entre múltiplos agentes;
Requer um novo algoritmo.
28
6. Extensões Funcionais
Grafos de Sociedade




Notação mais flexível e simples de visualizar;
Extensão da rede de dependência, que
permite expressar uma sociedade ao invés
de um único agente;
Para representar arestas do tipo AND, foi
necessário utilizar hipergrafos [Gallo92];
Os hipergrafos utilizados são 4-partite, com
partições para agente, objetivo, plano e ação.
29
7. Algoritmo
O Problema
“Localizar
o
hiperciclo de menor
custo em um
hipergrafo 4-partite
direcionado e
ponderado”.
Valores
positivos
são ganhos e
negativos são
custos.
O
que está em
vermelho é um
hiperciclo.
30
7. Algoritmo
Parâmetros








número de ações na sociedade (NAS);
número de objetivos na sociedade (NGS);
quantidade de ações por agente (APA);
quantidade de objetivos por agente (GPA).
quantidade de planos por objetivo (PPG);
quantidade de ações por plano (APP);
estratificação social (STR);
intolerância social (INT).
31
7. Algoritmo
Passo a Passo
Sociedade Ampulheta
ag1 é utilitarista, os outros
são substancialistas.
estratificação =1
Intolerância = 1
ordem sorteada: ag1, ag3,
ag4, ag2, ag5
32
7. Algoritmo
Passo 1
Montar Rede de Dependência
agente primário: ag1
Note que a rede não está ordenada.
33
7. Algoritmo
Passo 2
Ordenar Rede de Dependência
A rede é ordenada de acordo com a
estratégia.
BM(p111) = 1300 – 90 – 99 = 1111
BM(p121) = 1200 – 43 – 85 = 1072
Como a estratégia de ag1 é utilitarista,
ele prefere p111 (maior custobenefício)
34
7. Algoritmo
Passo 3
Ordenar AND-dependences
Dentro de uma PLAN-dependence,
existem AND-dependences.
Utiliza-se os critérios:
•
menor custo
•
menos OR-dependences
Nesse exemplo não se aplica.
35
7. Algoritmo
Passo 4
Fechar as OR-matches
A primeira AND-dependence
da rede é escolhida.
(esquerda)
Partindo de cada agente da
ponta, tenta-se chegar no
agente primário.
Respeita-se o parâmetro
estratificação.
36
7. Algoritmo
Passo 5
Remoção de
OR-dependences
problemáticos
As OR-dependeces que não
atingirem o primário são
removidas.
Se a AND-dependence tornarse impossível, também é
removida.
Nesse exemplo não se aplica.
37
7. Algoritmo
Passo 6
Fechamento da AND-match
Se todas as OR-dependences
encontrarem o agente
principal, fecha-se a ANDmatch (em vermelho)
38
7. Algoritmo
Passo 7
Execução da AND-match
A AND-match fechada é
executada, computando
custos e ganhos para
todos os participantes.
ag1 ganho 1300 / gasto 189
benefício líquido: 1111
ag2 ganho 1225 / gasto 62
benefício líquido: 1163
ag3 ganho 1100 / gasto 118
benefício líquido: 982
39
7. Algoritmo
Passo 8
Verificação de Término
Se NENHUM agente puder
realizar mais parcerias, a
simulação termina
Caso contrário a vez passa
para o próximo da lista,
voltando para o Passo 1.
A vez passa para ag3, que
nada pode fazer, e então
para ag4.
40
7. Algoritmo
Passo 1
Montar Rede de Dependência
agente primário: ag4
O agente ag4 só tem uma opção.
Como nada precisa ser ordenado, os
passos 2 e 3 passam sem efeito.
41
7. Algoritmo
Passo 4
Fechar as OR-matches
A única OR-dependence se
fecha.
Os passos 5 e 6 passam
sem efeito.
42
7. Algoritmo
Passo 7
Execução da AND-match
ag4 ganho 1113 / gasto 94
benefício líquido: 1019
ag1 ganho 0 / gasto 85
benefício líquido: 1026
Note a ação da intolerância
sobre ag1.
43
7. Algoritmo
Passo 8
Verificação de Término
A vez passa para ag2, que
nada pode fazer, e então
para ag5.
44
7. Algoritmo
Passo 1
Montar Rede de Dependência
agente primário: ag5
O agente ag5 só tem uma opção.
Como nada precisa ser ordenado, os
passos 2 e 3 passam sem efeito.
45
7. Algoritmo
Passo 4
Fechar as OR-matches
A única OR-dependence se
fecha.
Os passos 5 e 6 passam
sem efeito.
46
7. Algoritmo
Passo 7
Execução da AND-match
ag5 ganho 1100 / gasto 57
benefício líquido: 1043
ag1 ganho 1200 / gasto 43
benefício líquido: 2183
Dessa vez ag1 consegue
completar o seu plano.
47
7. Algoritmo
Passo 8
Verificação de Término
Nenhum agente pode realizar
mais nenhuma parceria.
A simulação termina.
48
8. Algoritmo
Resultados
Agente (estratégia)
Benefício/
total
Custos
Benefício
líquido
Objetivos
atingidos
ag1 (utilitário)
2500/2500
317
2183
2/2
ag2 (substancialista)
1255/1255
62
1163
1/1
ag3 (substancialista)
1100/1100
118
982
1/1
ag4 (substancialista)
1113/1113
94
1019
1/1
ag5 (substancialista)
1100/1100
57
1043
1/1
49
8. Resultados Obtidos
Validação das Estratégias
Avaros
Substancialista
Utilitaristas
50
8. Resultados Obtidos
Testes de Simulação



Foram desenvolvidos 16 experimentos, cada um
com 4 sociedades de 30 ou 60 agentes. Cada
sociedade foi simulada 100 vezes, para um total de
mais de 6400 execuções do simulador;
A partir dos dados dos 16 experimentos, as 4
hipóteses experimentais sugeridas no sistema
PART-NET foram verificadas;
Com os mesmos dados foi possível observar
indicativos da influência dos novos parâmetros
introduzidos no modelo.
51
8. Resultados Obtidos
Experimento E12
#
nU
nS
nA
NAS
NGS
APA
GPA
S1
-
60
-
20
20
5
10
S2
-
60
-
20
20
5
5
• hipótese experimental H2 no PartNET+;
• a sociedade S1 (com mais GPA) obtém um benefício líquido
acumulado por parcerias (BP) maior do que S2.
BP1 = 2.223,7 (±46,4)
BP2 = 2.071,3 (±50,7)
T(BP1,BP2) = 22,17
BP1 > BP2 com erro de 0,001%
52
8. Resultados Obtidos
Experimento E12
53
8. Resultados Obtidos
Experimento E23
#
nU
nS
nA
NAS
APA
GPA
PPG
APP
STR
INT
S1
20
20
20
20
5
10
1
1
1
1
• mostra a hipótese experimental H3 no PartNET++;
• na sociedade heterogênea S1, os substancialistas superam os
utilitaristas em termos de benefício líquido acumulado.
Bu = 99.565,0 (±4.237,7)
Bs = 102.201,2 (±4.235,0)
Ba = 89.535,3 (±4.938,0)
T(Bs,Bu) = 4,38
Bs > Bu com erro de 0,01%
54
8. Resultados Obtidos
Experimento E23
55
9. Conclusões
Dificuldades Encontradas



Muito pouco do software original pode ser
utilizado;
A depuração do novo algoritmo, utilizando
hipergrafos, foi um processo não trivial;
Dificuldade em localizar uma biblioteca para
a representação e visualização de grafos em
Java.
56
9. Conclusões
Tempo de Simulação



O novo algoritmo é NP-completo, como o
antecessor;
O tempo de simulação não chegou a ser
problemático a ponto de impedir a execução
dos experimentos com os parâmetros
utilizados;
Uma análise matemática seria útil para
otimizar o algoritmo.
57
9. Conclusões
Trabalhos Futuros





Agentes com conhecimento parcial das
relações de dependência, e introdução do
conceito de “Broker”;
Inclusão de um modelo de reputação entre os
agentes;
Modelagem de um ambiente que possa
limitar a interação entre os agentes;
Permitir a definição de estratégias através de
um editor de estratégias;
Implementar o parâmetro de intolerância
social.
58
Publicação Associada
[Monteiro03] MONTEIRO, J. L. R.;SICHMAN, J. S.
PartNet+: Simulando parcerias entre múltiplos
agentes. In Anais do 4o. Encontro Nacional
de Inteligência Artificial (ENIA'03), Campinas,
2003.
59
Bibliografia
[Castelfranchi90] CASTELFRANCHI, C. Social power a point missed
in multi-agent, DAI and HCI. In Y. Demazeau e J.P. Muller, editores,
Decentralised AI., p. 49--62. Elsevier Science Publishers, 1990.
[Conte98] CONTE, R.; PEDONE,R. Finding the Best Partner: The
PART-NET System, in: Proc. First International Workshop
(MABS’98), Lecture Notes in Artificial Intelligence, Vol. 1534,
Springer-Verlag, 1998 p. 156-168, Paris, França, julho 1998.
[Durfee94] DURFEE, E.; ROSENSCHEIN, J. Distributed Problem
Solving and Multi-Agent Systems: Comparisons and Examples,
in Proceedings of the Thirteenth International Distributed Artificial
Intelligence Workshop, p. 94-104, julho 1994.
[Gallo92] GALLO, G. et al. Directed Hypergraphs and Applications,
in Discrete Aplied Mathematics, p. 177-201, 1992.
60
Bibliografia
[Gilbert90] GILBERT, N. Models, Processes and Algorithms: Towards a
Simulation Toolkit, in Dagstuhl Seminar on Social Science
Microsimulation, maio de 1997.
[Sichman02] SICHMAN, J.; CONTE, R. Multi-Agent Dependence by
Dependence Graphs. In AAMAS 2002. First International Joint
Conference on Autonomous Agents and Multi-Agent Systems, Itália,
junho 2002.
[Wooldridge94] WOOLDRIDGE, M.; JENNINGS, N. Intelligent
Agents: Theory and Practice. In Knowledge Engineering Review,
outubro 1994, revisado em janeiro de 1995.
61