Paper 3 - (LES) da PUC-Rio

Transcrição

José Alberto Rodrigues Pereira Sardinha
PUC-Rio - Certificação Digital Nº 0115614/CA
MAS-School e ASYNC: Um Método e um Framework para
Construção de Agentes Inteligentes
Tese de Doutorado
Tese apresentada como requisito parcial para
obtenção do título de Doutor pelo Programa de PósGraduação em Informática da PUC-Rio.
Orientadores: Ruy Luiz Milidiú
Carlos José Pereira de Lucena
Rio de Janeiro, 18 de março de 2005
2
MAS-School e ASYNC: Um Método e um Framework para
Construção de Agentes Inteligentes
Tese apresentada como requisito parcial para obtenção
do título de Doutor pelo Programa de Pós-Graduação em
Informática da PUC-Rio. Aprovada pela Comissão
Examinadora abaixo assinada.
Prof. Ruy Luiz Milidiú
Orientador
Departamento de Informática - PUC-Rio
Prof. Carlos José Pereira de Lucena
Co-Orientador
Prof. Jaime Simão Sichman
Depto. Eng. Computação e Sistemas Digitais, Escola Politécnica - USP
Prof. Ricardo Choren Noya
Depto. Engenharia de Computação - IME
Prof. Bruno Feijó
Prof. Hugo Fuks
Prof. José Eugenio Leal
Coordenador(a) Setorial do Centro Técnico Científico - PUC-Rio
Rio de Janeiro, 18 de março de 2005
3
Todos os direitos reservados. É proibida a reprodução total
ou parcial do trabalho sem autorização da universidade, do
autor e do orientador.
Ficha Catalográfica
Sardinha, José Alberto Rodrigues Pereira
MAS-School e ASYNC: um método e um framework
para construção de agentes inteligentes / José Alberto
Rodrigues Pereira Sardinha; orientadores: Ruy Luiz Milidiú,
Carlos José Pereira de Lucena. – Rio de Janeiro : PUCRio, Departamento de Informática, 2005.
152 f. ; 30 cm
Tese (doutorado) – Pontifícia Universidade Católica do
Rio de Janeiro, Departamento de Informática.
Inclui referências bibliográficas
1. Informática – Teses. 2. Sistemas multi-agente. 3.
Inteligência artificial. 4. Machine learning. 5. Engenharia de
software. I. Milidiú, Ruy Luiz. II. Lucena, Carlos José
Pereira de. III. Pontifícia Universidade Católica do Rio de
Janeiro. Departamento de Informática. IV. Título.
CDD: 004
4
À Luciana e ao meu Pai
5
Agradecimentos
Ao amigo e professor Ruy Milidiú, por toda a confiança, por todo o apoio, por
todas as oportunidades, e pelos ensinamentos.
Ao amigo e professor Carlos Lucena, por toda a confiança, por todo o apoio e pela
oportunidade de me incluir em um grupo de pesquisa tão extraordinário.
Aos alunos Patrick Paranhos e Pedro Cunha, futuros engenheiros e grandes
pesquisadores. Essa tese tem muitas contribuições de vocês. Agradeço a vocês
pelo empenho, dedicação, e trabalho.
Ao aluno Marco Molinaro, recém chegado ao nosso grupo de pesquisa, mas que já
se mostra também um grande pesquisador. Obrigado pelas contribuições.
Aos meus grandes amigos do LES e LEARN: Alessandro, Viviane Silva, Choren,
Guga, Daflon, Matheus, Fred Liporace, Fred, Laber, Arthur, Raul, Viviane
Braconi, Lorenza, Taciana, Luiz Fernando, Patrick, Pedro, Marco, Helena, João,
Chicão, Otávio, Daniel, e todos os outros que porventura eu esteja esquecendo.
Obrigado pelas contribuições e apoio.
À Vera Menezes e Lena Ururahy, pelo apoio e carinho.
À minha família e principalmente ao meu pai, professor José Carlos Sardinha, e à
sua mulher, professora Regina Lucia Sardinha, por estarem sempre ao meu lado
nos momentos mais difíceis, sempre me incentivando.
À Luciana Salles, minha esposa, por todo amor, carinho, apoio e presença durante
esses anos. Você esteve sempre do meu lado me incentivando.
Ao CNPq, pelo apoio financeiro.
6
Resumo
Sardinha, José Alberto Rodrigues Pereira. MAS-School e ASYNC: Um
Método e um Framework para Construção de Agentes Inteligentes. Rio
de Janeiro, 2005. 152p. Tese de Doutorado - Departamento de Informática,
Pontifícia Universidade Católica do Rio de Janeiro.
Agentes de Software é uma tecnologia que permite criar simuladores e
sistemas inteligentes que tomam decisões automaticamente. A primeira
contribuição dessa tese é o MAS-School, um método para modelar e implementar
agentes de software inteligentes desde as primeiras fases de desenvolvimento.
Esse método também apresenta várias orientações de como incluir aprendizado na
fase de design e implementação. O método apresenta no final uma estratégia
incremental de desenvolvimento para permitir a avaliação do desempenho das
técnicas de machine learning. A segunda contribuição dessa tese é o framework
ASYNC. O ASYNC é composto por um conjunto de ferramentas de engenharia
de software para auxiliar a construção de sistemas baseados em agentes
assíncronos, cooperativos e inteligentes. Esta tese apresenta quatro estudos de
casos complexos desenvolvidos com agentes inteligentes para exemplificar o uso
do método e framework. A primeira aplicação apresenta um sistema baseado em
agentes para criar promoções em um mercado varejista utilizando o conceito de
agregação de produtos. A segunda aplicação apresenta um mercado virtual para
compra e venda de bens. A terceira aplicação é um sistema multi-agente
distribuído para um complexo cenário de procurement em leilões simultâneos e
interdependentes. Essa aplicação participou do Trading Agent Competition em
2004 e obteve a terceira colocação. A quarta aplicação é um sistema multi-agente
para um Supply Chain Management.
Palavras-chave
Sistemas
Multi-Agente,
Engenharia de Software.
Inteligência
Artificial,
Machine
Learning,
7
Abstract
Sardinha, José Alberto Rodrigues Pereira. MAS-School e ASYNC: A
Method and a Framework for Building Intelligent Agents. Rio de
Janeiro, 2005. 152p. Doctoral Thesis - Departamento de Informática,
Pontifícia Universidade Católica do Rio de Janeiro.
The agent technology is used to develop systems that perform several
complex tasks. This thesis presents the MAS-School method for modeling and
implementing intelligent agent-based systems. The method presents a systematic
approach to support a disciplined introduction of machine learning techniques in
multi-agent systems from an early stage of design. The proposed approach
encompasses guidelines to both the design and implementation phases of an
agent-based system. It is based on an incremental development strategy that
largely relies on simulation and testing techniques. This thesis also presents the
ASYNC framework that is composed of software engineering tools for building
agent based system for asynchronous, cooperative and intelligent agents. This
thesis presents four complex applications that used the proposed method and
framework in the design and implementation phase. The first case study presents
an application that discovers the most appealing offerings for consumers in a retail
market. The second case study presents a virtual marketplace for buying and
selling goods with automatic negotiation. The third case study is a multi-agent
system for a complex procurement scenario with interdependent and simultaneous
auctions. This system achieved the third place in the 2004 TAC Classic
competition. The fourth case study is a multi-agent system for a PC manufacturer
scenario based on sourcing of components, manufacturing of PC's and sales to
customers.
Keywords
Multi-Agent Systems, Artificial Intelligence, Machine Learning, Software
Engineering.
8
Sumário
1 Introdução
15
1.1. Sistemas Multi-Agente
16
1.2. A Engenharia de Software para Agentes Inteligentes
17
1.3. Aprendizado para Agentes Inteligentes
18
1.4. A Solução Proposta
20
1.5. Avaliação Empírica
25
1.6. Organização da Tese
26
2 A Construção de Sistemas com Agentes Inteligentes
28
2.1. ANote – Uma linguagem de Modelagem Simples e Poderosa
28
2.2. Frameworks Orientados a Objetos
32
2.3. Padrões de Projeto (Design Patterns)
33
2.4. Algoritmos para Agentes Inteligentes
35
2.4.1. Inteligência Artificial
35
2.4.2. Machine Learning
36
2.4.3. Predição em Séries Temporais
40
2.4.4. Otimização Combinatória
41
2.4.5. Análise de Agrupamento
42
3 ASYNC – Um Framework para Construção de Agentes Inteligentes
45
3.1. Estudo de Caso - A Aplicação Bundles.com
45
3.1.1. Simulação e Monitoramento
51
3.1.2. Resultados da Evolução do Sistema
52
3.2. ASYNC – Um Framework Orientado a Objetos para Construção de
Agentes Distribuídos e Assíncronos
53
3.2.1. Como Instanciar uma Aplicação Baseada em Agentes com o
Framework Orientado a Objetos do ASYNC
56
3.3. Instanciando o ASYNC para a Aplicação Bundles.com
58
3.4. ASYNC-D – A Ferramenta de Distribuição dos Agentes em CPUs
9
Distintas de um Rede
60
3.5. Aplicação Babilônia
62
4 MAS-School - Um Método para Incluir Aprendizado em Sistemas MultiAgente
64
4.1. Incluindo Aprendizado em Sistemas Multi-Agente
65
4.1.1. Objetivo Sistêmico & Seleção da Medida de Performance
66
4.1.2. Seleção do Agente & Definição do Objetivo do Aprendizado no
Agente
68
4.1.3. Design do Aprendizado no Agente
68
4.1.4. Implementação Incremental & Avaliação de Performance
70
4.2. Agent Learning Pattern – Um Design para Incluir Aprendizado em
Agentes
73
4.2.1. Intenção
73
4.2.2. Contexto
73
4.2.3. Problema
74
4.2.4. Forças
74
4.2.5. Solução
74
4.2.6. Estrutura
76
4.2.7. Exemplo
77
4.2.8. Dinâmica
77
4.2.9. Implementação
78
4.2.10. Conseqüências
81
4.2.11. Usos Conhecidos
81
4.2.12. Padrões Relacionados
82
5 A Aplicação LearnAgents
84
5.1. O TAC Classic
85
5.2. Edições Anteriores do TAC
85
5.3. A arquitetura do LearnAgents
88
5.4. O TAC Classic 2004 e Resultados
96
5.5. Os Algoritmos utilizados nos Agentes do LearnAgents
98
5.5.1. Preditor
98
5.5.2. Alocador
99
10
5.5.3. Ordenador
102
5.5.4. Negociador de Hotel
103
5.6. Utilizando o MAS-School no Processo de Desenvolvimento do
LearnAgents
108
5.7. Utilizando o ASYNC na Implementação do LearnAgents
114
6 A Aplicação LearnAgentsSCM
118
6.1. O TAC Supply Chain Management
119
6.2. Evolução do TAC SCM
120
6.3. Arquitetura LearnAgentsSCM
122
6.4. A Engenharia de Algoritmos dos Agentes do LearnAgentsSCM
132
6.4.1. Gerente de Compras
132
6.4.2. Programador da Produção e Programador da Entrega
133
6.4.3. Gerente de Marketing
135
LearnAgentsSCM
136
7 Conclusões
140
8 Referências
146
11
Lista de figuras
Figura 1: A decomposição dos objetivos relacionados com o objetivo do Problema
Principal.
20
Figura 2: A arquitetura do Sistema Baseado em Agentes.
21
Figura 3: Cenário do Agente I.
22
Figura 4: Diagrama de Interação do Agente I e Agente II.
22
Figura 5: O diagrama de classes do Agente I.
23
Figura 6: A arquitetura de implementação do Sistema Multi-Agente.
24
Figura 7: A visão de objetivo do ANote.
29
Figura 8: A visão do agente do ANote.
29
Figura 9: A visão do cenário do ANote.
30
Figura 10: A visão de planejamento do ANote.
30
Figura 11: A visão de interação do ANote.
31
Figura 12: A visão de organização do ANote.
32
Figura 13: A árvore Minimax.
36
Figura 14: O Neurônio Artificial.
38
Figura 15: A decomposição dos objetivos.
46
Figura 16: apresenta a arquitetura do Bundles.com.
47
Figura 17: Diagrama de Cenários do Analista de Mercado.
47
Figura 18: Diagrama de Cenários do Comprador.
49
Figura 19: Os máximos locais e globais da função de fitness.
50
50
Figura 21: Interface da Monitoração On-line.
52
Figura 22: Energia obtida pelos Agentes por instante de tempo.
53
Figura 23: O diagrama de Classes do Framework Orientado a Objetos ASYNC. 54
Figura 24: A instanciação do Agente Vendedor na aplicação Bundles.com.
58
Figura 25: Diagrama de cenário do Vendedor.
59
Figura 26: Os agentes do ASYNC-D.
61
Figura 27: A Console de Configuração do ASYNC-D.
62
Figura 28: As classes do Agente Comprador.
63
Figura 29: O método para incluir Aprendizado em um Sistema Multi-Agente.
66
12
Figura 30: A decomposição dos objetivos relacionados com o comércio de bens.
67
Figura 31: O diagrama de Classes (UML) do Preditor de Preços.
69
Figura 32: O processo incremental de desenvolvimento.
72
Figura 33: Um diagrama de Classes de um típico Agente.
75
Figura 34: O diagrama de Classes do Agent Learning Pattern.
76
Figura 35: O diagrama de Seqüência do Agent Learning Pattern.
78
Figura 36: O diagrama de Classes do agente Preditor.
78
Figura 37: Ilustração do TAC Classic.
85
Figura 38: A arquitetura do LearnAgents.
89
90
Figura 40: Arquitetura do LearnAgents.
91
Figura 41: Diagrama de cenário dos Sensores.
92
Figura 42: Diagrama de cenário dos Preditores.
92
Figura 43: Diagrama de cenário dos Alocadores.
93
Figura 44: Diagrama de cenário do Ordenador.
94
Figura 45: Diagrama de cenário dos Negociadores.
94
Figura 46: Interface do Monitor.
95
Figura 47: Diagrama do Interação do LearnAgents.
95
Figura 48: Resultado do TAC de 2004.
97
99
104
Figura 51: A árvore Minimax (nível Maximizar) no Negociador de Hotel.
105
Figura 52: A árvore Minimax (nível Minimizar).
105
Figura 53: Gráfico dos lances enviados para leilão pelo Negociador de Hotel. 108
109
Figura 55: O Gráfico da Evolução do Benchmark do LearnAgents.
113
Figura 56: A instanciação do Agente Ordenador e Formato da Mensagem na
aplicação. LearnAgents.
114
115
Figura 58: O Jogo TAC SCM.
119
Figura 59: A Arquitetura do LearnAgentsSCM.
123
13
Figura 60: A decomposição dos objetivos relacionados com a produção, compra
de matéria prima, e comercialização de bens.
124
Figura 61: O Diagrama de Agentes do LearnAgentsSCM.
125
126
Figura 63: Cenário da Seleção dos Pedidos por Cotações.
127
Figura 64: Cenário da Decisão dos Lances.
127
Figura 65: Cenário da Programação da Produção.
128
Figura 66: Cenário da Programação da Entrega e Ordens a Cancelar.
128
Figura 67: Cenário da Decisão de Compra dos Componentes.
129
Figura 68: Cenário da Negociação dos Componentes com os Fornecedores.
129
Figura 69: Diagrama de Interação do processo de vendas.
130
Figura 70: Diagrama de Interação do Processo de Compra de Matéria Prima. 130
Figura 71: Diagrama de Interação do Processo de Produção.
131
Figura 72: Diagrama de Interação do Processo de Entrega.
131
Figura 73: Nível de Estoque por tempo.
132
Figura 74: Decisão de Compra dos Componentes.
132
Figura 75: Gráfico da Evolução do Benchmark.
139
14
Lista de tabelas
Tabela 1: A mapeamento entre subproblemas e tipos de agentes.
21
Tabela 2: Mapeamento dos Conceitos de Agentes para as Classes OO.
22
46
Tabela 4: Exemplos de centróides encontrados com o algoritmo Isodata.
48
Tabela 5: Tabela com os padrões de consumo dos nove centróides.
48
Tabela 6: Mapeamento dos Conceitos de Agentes para as Classes da Aplicação
instanciada.
57
68
Tabela 8: Resultado do TAC de 2000.
86
87
88
88
91
97
Tabela 14: Performance do Negociador de Hotel nas finais do TAC Classic de
2004.
107
Tabela 15: Benchmark das Versões do LearnAgents.
111
113
Tabela 17: Resultado da Final do TAC SCM de 2003.
120
121
125
Tabela 20: Resultados da Evolução do Benchmark.
138
15
1 Introdução
“Intelligent Agents and Artificial Intelligence:
Well, it has to do with smart programs,
so let’s get on and write some.”
Stuart Russell and Peter Norvig
"Em cinco anos, todas as empresas serão empresas da Internet ou
simplesmente não serão empresas", presidente do conselho de administração da
Intel Andy Grove (Revista Exame, n.16, 11/08/99, p 126). A revolução digital
mudou complemente a gestão dos negócios, que no passado se baseava
primordialmente em aquisição de bens físicos e átomos, e agora está se baseando
em bits e idéias. As palavras chaves desta nova administração são informação,
conhecimento e inteligência ao invés de prédios, fábricas, ou bens materiais.
Surgem a partir dessa revolução inúmeras oportunidades na área da
tecnologia da informação. O comércio eletrônico é um exemplo de tema muito
importante no mundo dos negócios relacionados com a Internet. De acordo com
Peter Drucker (Drucker, 2000), o comércio eletrônico é para a Revolução da
Informação o que a ferrovia foi para a Revolução Industrial.
As comunidades de Inteligência Artificial, Business Intelligence, Comércio
Eletrônico, e Sistemas Multi-Agente estão contribuindo com o desenvolvimento
desta área, e boa parte das tecnologias oferecidas já está sendo usada pelo mundo
corporativo (IBM Business Intelligence, 2005; Computer Associates CleverPath,
2005; Dash Optimization, 2005; Living Systems & Whitestein Technologies,
2005). O objetivo principal destas contribuições é automatizar processos e
maximizar a lucratividade das transações em meios eletrônicos.
16
1.1. Sistemas Multi-Agente
A tecnologia de agentes (Ferber, 1999; Wooldridge, 2000) permite criar
simuladores e sistemas inteligentes que tomam decisões automaticamente. Muitos
acreditam que a principal proposta desta tecnologia é bem semelhante a da
inteligência artificial: programas capazes de substituir o ser humano em tarefas
que exigem conhecimento, experiência e racionalidade. Esses programas podem
ser utilizados para simulações ou em situações reais.
A base deste enfoque está em considerar os agentes como entidades
inteligentes e isoladas. Porém, uma nova teoria que utiliza os agentes de software
acredita que a inteligência não pode ser separada do contexto social (Ferber,
1999). Desta forma, começa a surgir um novo campo de interesse que estuda
programas construídos com vários agentes – os Sistemas Multi-Agente.
Esses agentes dotados de autonomia podem executar tarefas simples ou
complexas, só que agora inseridos dentro de uma organização e um meio
ambiente. O importante nessa análise não é observar os objetivos de cada agente,
e sim o objetivo global da sociedade formada. O agente utiliza algumas
características encontradas nas sociedades para alcançar esse objetivo.
A primeira delas é Interação (Ferber, 1999). A interação ocorre quando dois
ou mais agentes são submetidos a um relacionamento dinâmico através de um
conjunto de ações recíprocas. A segunda é a Cooperação (Ferber, 1999), que é
vista dentro de um sistema multi-agente como um método para atingir o objetivo
global. Além disso, temos também as Organizações (Ferber, 1999), que são
criadas para estruturar a cooperação e interação entre os agentes. Uma
organização pode ser vista como um conjunto de relações entre agentes que
produz
uma
unidade,
com
qualidades
não
encontradas
nos
agentes
individualmente.
O desenvolvimento de um sistema multi-agente de larga escala (Lucena et
al., 2003; Garcia et al., 2003) não é uma tarefa simples. Sistemas com muitos
agentes em ambientes heterogêneos necessitam de soluções de engenharia de
software para permitir reuso e um desenvolvimento eficiente.
Uma técnica interessante para modelar um problema computacionalmente
difícil com o paradigma de agentes é dividir esse mesmo problema em
subproblemas mais simples (Sardinha et al., 2004a). Assim, cada agente se torna
17
responsável por um ou mais desses subproblemas. Esses agentes ainda podem
resolver esses subproblemas de forma assíncrona e em diferentes CPUs.
Conseqüentemente, podemos listar algumas vantagens que surgem a partir dessa
técnica de modelagem:
Escalabilidade – Problemas complexos são resolvidos de forma mais
simples, e não há limite para o número de agentes no sistema;
Versatilidade – Como cada agente ataca um subproblema, podemos
desenvolver agentes com técnicas diferentes de inteligência e combinar as
soluções com simplicidade;
Flexibilidade – É simples evoluir o sistema para incluir novos agentes, e
assim, incluir novas técnicas de inteligência.
1.2. A Engenharia de Software para Agentes Inteligentes
Muitas metodologias e linguagens de modelagem para agentes já foram
propostas para construir sistemas multi-agente. Existem também muitas
plataformas e frameworks de desenvolvimento para implementar os sistemas
baseados em agentes. Porém, pouquíssimos trabalhos propõem um mapeamento
entre modelos de design baseado em agentes e código. Esta tese propõe um
mapeamento claro entre conceitos de agentes e código, e ainda apresenta várias
aplicações complexas para demonstrar a robustez do método.
Metodologias como Gaia (Wooldridge et al., 2000; Zambonelli et al., 2003)
e MaSE (Deloach, 1999), não fornecem um guia de como implementar os
modelos propostos. Conseqüentemente, a geração de código não é um processo
trivial. Gaia é uma metodologia orientada a agentes para as fases de análise e
design. Os autores de Gaia afirmam que a metodologia não trata diretamente dos
detalhes de implementação. Em MaSE, os autores afirmam que o foco principal
da metodologia é auxiliar as fases de requisitos, análise, design, e implementação.
Porém, a metodologia não descreve como os modelos devem ser implementados
em qualquer plataforma.
Em (Do et al., 2003; Castro et al, 2001), os autores propõem um
mapeamento de conceitos i*, usados na metodologia Tropos (Giunchiglia et al.,
2002; Bresciani et al., 2004) para modelar um agente BDI (Beliefs, Desires, and
Intentions), para um ambiente de desenvolvimento chamado Jack (Howden et al.,
18
2001). Cada conceito i* é mapeado para um BDI, e consecutivamente para uma
abstração Jack. Apesar dos autores fornecerem um mapeamento, nenhum exemplo
de aplicação é apresentado. Conseqüentemente, o mapeamento de conceitos i*
para abstrações Jack não possui qualquer prova concreta. Os detalhes de como
implementar os planos não é claro, o que evidencia uma pesquisa ainda em uma
fase inicial.
A metodologia Prometheus (Padgham et al., 2002a) também propõe um
suporte do “inicio-ao-fim” entre especificação e implementação. Os autores
propõem o uso do ambiente Jack para implementar os modelos de Prometheus.
Em (Padgham et al., 2002b), o Jack Development Environment (JDE) é
apresentado como uma ferramenta para modelar detalhes de implementação dos
modelos Prometheus e implementar sistemas baseados em agentes usando Jack.
Porém, o mapeamento entre os artefatos detalhados de design e abstrações de
implementação não é apresentado. Além disso, um exemplo não é apresentado no
ambiente Jack.
Em (Huget, 2002), os autores demonstram a geração de código a partir de
diagramas de seqüência AUML. O foco dos autores é exemplificar o mapeamento
de interações de agentes para código Java. Entretanto, esse mapeamento não é
baseado em nenhuma arquitetura ou framework de agentes. Essas tecnologias
fornecem abstrações reutilizáveis para programadores implementarem sistemas
baseados em agentes. Ao fazer uma extensão ou customização a esses
frameworks, o processo de implementação se torna mais simples e mais rápido.
Nos frameworks de implementação há muito código já escrito e compilado, e o reuso é grande.
1.3.Aprendizado para Agentes Inteligentes
O processo de modelagem de um sistema multi-agente inteligente de larga
escala não é uma tarefa simples. Principalmente quando o sistema deve atuar em
ambientes onde há mudanças constantes nos cenários externos. Neste caso, o
sistema deve possuir agentes dotados de aprendizado e inteligência. Os conceitos
de aprendizado devem ser modelados já nas primeiras fases de desenvolvimento.
Em sistemas complexos e abertos, agentes precisam de aprendizado para tomar
19
decisões e se adaptar a mudanças para poder atingir os seus objetivos e o objetivo
global do sistema.
A modelagem de sistemas baseada em agentes inteligentes com aprendizado
sempre apresenta questões semelhantes, dentre as quais destacamos:
(i)
Como avaliar o objetivo do sistema como um todo?
(ii)
Como definir e avaliar o objetivo individual de cada agente?
(iii)
Como modelar o conhecimento de cada agente?
(iv)
Como projetar o mecanismo de aquisição de conhecimento para cada
agente?
(v)
Como combinar múltiplas técnicas de aprendizado e distribuir essas
técnicas para cada agente no sistema?
(vi)
Como associar abstrações de agentes com abstrações de machine
learning?
(vii)
Como especificar abstrações de machine learning nas primeiras
fases de design e permitir uma transição para a fase de
implementação?
Infelizmente, os engenheiros de software ainda utilizam a sua experiência e
intuição para resolver as questões acima. Muita pesquisa tem sido feita para criar
metodologias e frameworks de implementação para sistemas multi-agente. Porém,
nenhum desses trabalhos apresenta um guia para incluir técnicas de aprendizado já
nas fases iniciais do desenvolvimento.
Os frameworks (Howden et al., 2001; Telecom Itália-Jade, 2003) de
implementação disponibilizam muitas APIs para desenvolver sistemas multiagente, mas não orientam a estruturação do design do aprendizado de uma
maneira sistemática. Além disso, as várias metodologias orientadas a agentes
(Zambonelli et al., 2003; Deloach, 1999; Bresciani et al., 2004; Padgham et al.,
2002) são focadas em um nível muito alto de abstração, e não indicam como tratar
aprendizado desde a fase de design até a implementação.
Um tema de pesquisa importante na área de aprendizado em sistemas multiagente é denominado MAS Learning (Sem et al., 2000; Kudenko, 2003). O foco
principal dos trabalhos é desenvolver algoritmos de machine learning distribuídos
utilizando técnicas como Reinforcement Learning (Mitchell, 1997). Porém, os
trabalhos desta área não apresentam um design ou metodologia, geral o suficiente
20
para qualquer algoritmo ou domínio, que permite incluir essas técnicas de
machine learning em sistemas baseados em agentes.
1.4. A Solução Proposta
Esta tese apresenta o método MAS-School (Sardinha et al., 2004b; Sardinha
et al., 2005b) para modelar e implementar agentes de software inteligentes desde
as primeiras fases de desenvolvimento. Esse método também apresenta várias
orientações de como incluir aprendizado na fase de design e implementação. O
método apresenta no final uma estratégia incremental e iterativa de
desenvolvimento para permitir a avaliação das técnicas de machine learning.
A linguagem de modelagem ANote (Choren, 2002; Choren et al., 2004a;
Choren et al., 2004b) é utilizada para modelar os sistemas multi-agente desta tese,
pois fornece todos os diagramas necessários para as várias fases de modelagem.
Todos os nossos projetos de software utilizam a técnica orientada a
objetivos para a fase de requisitos. Esta fase utiliza o processo recursivo de
decomposição de um objetivo do problema principal em vários objetivos de
subproblemas. Essa técnica é interessante, pois permite dividir um problema
computacionalmente difícil em subproblemas mais simples. O diagrama 1
exemplifica a decomposição.
Figura 1: A decomposição dos objetivos relacionados com o objetivo do Problema
Principal.
A abstração de objetivos é central neste método. Em uma segunda etapa,
esse objetivo permite a definição de uma medida de performance para os agentes
que necessitam de aprendizado. Conseqüentemente, o processo de decomposição
dos objetivos em sub-objetivos é fundamental para o método proposto. É
importante frisar que essa modelagem de hierarquia de objetivos é uma atividade
comum nas metodologias orientada a agentes. Para esse método, os objetivos
21
funcionam como uma abstração para unificar conceitos de machine learning com
conceitos básicos de sistemas multi-agente.
A segunda fase do processo de modelagem é criar os tipos de agentes que
sejam capazes de conduzir os objetivos desses subproblemas encontrados na fase
de requisitos. Essa criação de tipos de agentes começa com um processo de
relacionamento de todos os objetivos de nível mais baixo com os tipos de agentes
criados. A tabela 1 exemplifica um mapeamento entre esses objetivos e tipos de
agentes. A figura 2 apresenta os vários tipos de agentes e seus relacionamentos.
Esta figura permite uma visão estática do projeto do nosso sistema multi-agente.
Objetivo
Agente
Objetivo do Subproblema 1
Agente I
Agente II
Figura 2: A arquitetura do Sistema Baseado em Agentes.
Após a criação dos vários tipos de agentes, cada agente deve possuir uma
especificação de cenários. Esses cenários possuem informações sobre o contexto
de como cada agente deverá atingir seus objetivos. Esses objetivos possuem ações
que o agente deve seguir para alcançar os objetivos dos subproblemas, e
conseqüentemente o objetivo do problema principal. O diagrama 3 apresenta o
digrama de cenário do Agente I.
22
Figura 3: Cenário do Agente I.
Um diagrama interessante que deriva dos diagramas de cenário é o diagrama
de interação. Esse diagrama deixa explícita a comunicação entre os agentes, e
permite uma visão dinâmica do sistema. O diagrama 4 apresenta a interação entre
o Agent I e Agente II
Figura 4: Diagrama de Interação do Agente I e Agente II.
Conceitos de Agentes
Classes do ASYNC instanciadas
O ambiente e os recursos
(i) Classe Principal para o ambiente;
(ii) Classes para os recursos.
Agente
(i) Uma classe concreta que herda de Agent, e
implementa AgentInterface;
(ii) Uma classe concreta que herda de
InteractionProtocols.
Ações internas do Agente
Métodos incluídos na classe concreta de
Agent.
Protocolos de Interação
Métodos incluídos na classe concreta de
Formato das Mensagens nos (i)
protocolos de interação
Classe
concreta
que
implementa
AgentMessage, se a troca de mensagens é
síncrona;
(ii)
Classe
concreta
AgentBlackBoardInfo,
que
se
a
implementa
troca
de
mensagens é assíncrona.
Tabela 2: Mapeamento dos Conceitos de Agentes para as Classes OO.
23
O capítulo 3 apresenta um framework chamado ASYNC (Sardinha et al.,
2003a), e um mapeamento das abstrações de agentes para abstrações OO
(Sardinha et al., 2005c). A tabela 2 resume esse mapeamento, porém o detalhe de
instanciação do framework será apresentado mais adiante nesta tese. Esse
framework é fundamental para o método proposto, pois:
(i)
Permite um mapeamento claro entre abstrações de agentes e
código OO;
(ii)
Permite re-uso de código;
(iii)
Diminui o tempo de desenvolvimento;
(iv)
Diminui a complexidade de implementar agentes de software.
Em conseqüência do uso do framework proposto, cada agente no sistema
deve possuir duas classes concretas. A figura 5 exemplifica essas classes. As
ações internas do agente, que não dependem da interação com outros agentes no
sistema, são mapeados como métodos da classe Agente I. Os protocolos de
interação, que definem como o agente deve se comunicar e interagir com outros
agentes no sistema, são mapeados como métodos da classe Agent I IP.
Figura 5: O diagrama de classes do Agente I.
Esse framework também possui uma camada de comunicação síncrona
através de troca de mensagens, e uma comunicação assíncrona através do uso de
um tuple space reflexivo e distribuído (Silva et al., 2001). Essa camada de
comunicação fornece serviços básicos (ler, escrever, e retirar), e pode ser usado
para implementar um blackboard associativo (Corkill et al., 1987). O uso dessa
infra-estrutura de comunicação é fundamental para a nossa arquitetura de
implementação. Os agentes devem executar as suas ações de forma assíncrona, e
24
compartilhar resultados através de uma base de conhecimento corporativa dentro
do tuple space. Essa estratégia é utilizada também pelo A-Teams (Talukdar et al.,
1997), um sistema que utiliza memória distribuída para resolver problemas de
forma descentralizada. A figura 6 ilustra a arquitetura de implementação.
Figura 6: A arquitetura de implementação do Sistema Multi-Agente.
A arquitetura proposta permite uma alta escalabilidade para o sistema, pois
não há limite para o número de agentes. Os resultados de ações dos agentes
podem ser compartilhados nessa base de conhecimento corporativa, e acessado
por qualquer outro agente no sistema, mesmo que este esteja fisicamente em outra
CPU. A arquitetura também fornece uma grande versatilidade, pois cada agente
ataca um objetivo do subproblema com técnicas diferentes de inteligência e
aprendizado. A combinação dos resultados dos subproblemas é feita com
simplicidade através dessa base de conhecimento corporativa. O sistema é simples
de evoluir, pois novos agentes com técnicas de inteligência podem ser inseridos a
qualquer momento. Isso fornece grande flexibilidade ao engenheiro do sistema.
Porém, ao invés de implementar o sistema multi-agente com todos os
agentes inteligentes em uma única fase, o nosso método propõe uma primeira
implementação com apenas agentes reativos (Ferber, 1999) sem nenhuma técnica
de machine learning implementada. Essa primeira versão é importante para testar
a comunicação entre os agentes e a interação com o ambiente externo.
A próxima etapa do método permite incluir disciplinadamente as técnicas de
machine learning em sistemas multi-agente. Esse método também permite em sua
fase de implementação, a integração de diferentes algoritmos de machine learning
e a avaliação da performance do sistema. O método é apresentado no capítulo 6 e
possui quatro fases distintas:
25
(i)
Objetivo Sistêmico & Seleção da Medida de Performance, onde o
objetivo do problema principal é associado a uma medida de
performance para o sistema. Essa medida de performance permite
mensurar se o objetivo sistêmico está sendo alcançado;
(ii)
Seleção do Agente & Definição do Objetivo do Aprendizado no
Agente, onde agentes com planos complexos são selecionados, e
objetivos são atribuídos para o algoritmo de aprendizado;
(iii)
Design do Aprendizado no Agente, onde o refactoring do design do
agente é definido; e
(iv)
Implementação Incremental & Avaliação de Performance, onde
uma implementação incremental é proposta com treinamento, teste
e avaliação.
O processo incremental e iterativo de implementação da fase 4 permite
verificar o quanto o objetivo do problema principal do sistema esta sendo
alcançado através da medida de performance selecionada na fase 1.
Conseqüentemente, o engenheiro de software pode projetar técnicas de machine
learning que maximizem essa medida de performance.
1.5. Avaliação Empírica
Esta tese apresenta várias aplicações desenvolvidas com agentes
inteligentes. O método e framework proposto foram concebidos através de um
desenvolvimento bottom-up. A primeira aplicação (Sardinha, 2001; Milidiú et al.,
2001) apresenta um sistema baseado em agentes para criar promoções em um
mercado varejista utilizando o conceito de agregação de produtos. A aplicação
apresenta agentes que utilizam técnicas de clustering e algoritmos evolutivos para
determinar “cestas” de produtos altamente lucrativos.
A segunda aplicação (Ribeiro, 2001; Sardinha et al., 2003a) apresenta um
mercado virtual para compra e venda de bens. Os agentes no sistema também
implementam uma negociação automática entre compradores e vendedores. Além
disso, o sistema implementa um mecanismo de certificação dos vendedores,
compradores e bens para garantir a segurança das transações.
As próximas duas aplicações implementadas utilizam integralmente o
processo de generalização que concebeu o framework e o método propostos nessa
26
tese. As aplicações também foram extremamente importantes para garantir a
robustez do processo desenvolvido, e testar a escalabilidade do método.
A terceira aplicação desenvolvida é o LearnAgents (Sardinha et al., 2004c;
Sardinha et al., 2005a), um sistema multi-agente distribuído para um complexo
cenário de procurement em leilões simultâneos e interdependentes. Os agentes
cooperam para atingir um único objetivo que é maximizar a diferença entre a
utilidade marginal dos pacotes de bens e os custos de obtenção dos bens nos
leilões. Na arquitetura proposta, cada agente ataca um subproblema do objetivo
global, e utilizam várias técnicas de inteligência e aprendizado para resolver esses
subproblemas.
Além disso, o Trading Agent Competition (TAC) foi escolhido como
ambiente para testar a arquitetura. Esse ambiente apresenta características de um
mercado competitivo e permite avaliar a performance do LearnAgents em relação
a outros sistemas para comércio eletrônico. O LearnAgents conseguiu o terceiro
lugar na competição de 2004, e permitiu confirmar a robustez do método e
framework desta tese.
A quarta aplicação é um sistema multi-agente para um Supply Chain
Management. O ambiente do TAC também foi utilizado para avaliar a
performance desse sistema. Nesse ambiente, os sistemas participantes competem
por clientes e por peças de um número limitado de fornecedores. Os participantes
também são limitados pela capacidade da fábrica, e tem que gerenciar todos os
processos de uma cadeia de suprimentos.
1.6.Organização da Tese
O Capítulo 2 apresenta as principais tecnologias de engenharia de software e
um resumo dos algoritmos utilizados para construir os sistemas multi-agente desta
tese. Essas tecnologias são fundamentais para o desenvolvimento de sistemas
multi-agente de larga escala.
O capítulo 3 apresenta o framework orientado a objetos ASYNC para
facilitar e agilizar a implementação de agentes inteligentes em ambientes
distribuídos. Este capítulo utiliza o estudo de caso Bundles.com, uma aplicação
para determinar “cestas” de produtos altamente lucrativos, para exemplificar a
utilização do framework.
27
O capítulo 4 apresenta o método MAS-School para modelar e implementar
agentes de software inteligentes desde as primeiras fases de desenvolvimento. O
capítulo 5 apresenta o LearnAgents, um sistema multi-agente distribuído para um
complexo cenário de procurement em leilões simultâneos e interdependentes. O
capítulo 6 apresenta o LearnAgentsSCM, um sistema multi-agente distribuído para
um Supply Chain Management. O capítulo 7 apresenta as conclusões e trabalhos
futuros.
28
2 A Construção de Sistemas com Agentes Inteligentes
Este capítulo apresenta as principais ferramentas de Engenharia de Software
e algoritmos utilizados nessa tese. A primeira seção apresenta uma linguagem de
modelagem orientada a agentes chamada ANote. Essa ferramenta é indispensável
para qualquer projeto de software de sistema multi-agente de larga escala. As
próximas duas seções apresentam ferramentas importantes que permitem reuso de
código e design. Essas ferramentas diminuem o tempo de desenvolvimento e
reduzem a complexidade de implementar sistemas multi-agente. A última seção
deste capítulo apresenta um resumo de vários algoritmos utilizados nessa tese.
2.1. ANote – Uma linguagem de Modelagem Simples e Poderosa
ANote (Choren, 2002; Choren et al., 2004a; Choren et al., 2004b) é uma
linguagem de modelagem que oferece um padrão para descrever conceitos
relacionados ao processo de modelagem orientado a agentes. A linguagem possui
um meta-modelo conceitual que define, em um nível mais alto, conceitos de
interação, de ambiente, e de sociedade tais como objetivos, protocolos de
interação, recursos do ambiente e organizações. Além disso, a linguagem também
define conceitos básicos para cada agente individualmente tais como ações,
comunicação e planos.
Esses conceitos definem uma variedade de aspectos ou visões, que podem
se complementar ou sobrepor na especificação do sistema. A linguagem ANote
define sete visões baseadas em seu meta-modelo conceitual: objetivo, agente,
cenário, planejamento, interação, ontologia e organização. Cada visão gera um
artefato ou diagrama, e representa uma especificação parcial do sistema. Assim, o
designer do sistema pode se concentrar em um conjunto pequeno de propriedades
a cada momento, e considerar apenas as propriedades importantes para cada
contexto.
A visão de objetivo do ANote fornece uma identificação inicial de uma
árvore de objetivos para definir as funcionalidades do sistema. Nesta visão,
29
objetivos complexos podem ser decompostos funcionalmente em outros objetivos
e fluxos, e isso fornece uma descrição das funcionalidades em termos de uma
árvore hierárquica de objetivos. A figura 7 apresenta uma ilustração da visão de
objetivo.
Figura 7: A visão de objetivo do ANote.
A visão do agente especifica as classes dos agentes na aplicação e seus
relacionamentos. Nesta visão não há detalhes sobre o comportamento dos agentes,
pois especifica apenas a estrutura do sistema. As classes de agentes especificam os
papéis que serão executados para alcançar os objetivos definidos na visão de
objetivo. Essas classes podem constituir também uma ou mais organizações.
Quando dois agentes precisam interagir no sistema, uma associação é criada para
representar um relacionamento estrutural. A figura 8 apresenta uma ilustração da
visão do agente.
Figura 8: A visão do agente do ANote.
A visão do cenário especifica o comportamento de um cenário do agente.
Esse cenário é especificado textualmente, e apresentam planos de como o agente
deve atingir os seus objetivos. Esses cenários são úteis por dois motivos: (i)
ilustrar como objetivos podem ser atingidos ou não; e (ii) mostrar as
circunstâncias em que o agente pode se adaptar, aprender, ou mostrar um
comportamento autônomo. Os cenários são gerados por um grupo de ações
normais e emergentes, que surgem de comportamentos adaptativos ou em
30
contextos excepcionais. Essas são partes de um cenário que precisam ser
especificados: agente principal, pré-requisitos, plano principal e plano variante. A
figura 9 apresenta uma ilustração da visão do cenário.
Figura 9: A visão do cenário do ANote.
A visão de planejamento apresenta as ações de planos descritas no cenário.
Essa visão utiliza uma representação de estados com ações e transições para
apresentar as ações internas e sua seqüência. As visões de cenários podem ser
mapeadas diretamente para estas visões de planejamento, e vice versa. Além
disso, uma notação de adaptação do agente é apresentada com transições
adaptativas para ações variantes ou comportamentos emergentes. Essas transições
adaptativas permitem ao designer ilustrar quando e em que circunstâncias um
agente deve modificar o seu comportamento. A figura 10 apresenta os
componentes da visão de planejamento.
Figura 10: A visão de planejamento do ANote.
31
A visão de interação é utilizada para representar um conjunto de mensagens
trocadas pelos agentes durante a execução de ações de planos. As interações são
representadas nesta visão como diagramas de conversação que descrevem o
discurso entre os agentes, por exemplo, o protocolo de mensagens e os estados da
interação. A figura 11 apresenta os componentes da visão de interação.
Figura 11: A visão de interação do ANote.
Um sistema multi-agente não é composto apenas por agentes, pois possui
também componentes que compõem o ambiente onde os agentes atuam. A visão
de ontologia é responsável por especificar os recursos do ambiente e a base de
conhecimento do agente. Em ANote, esses componentes que não representam
agentes são modelados como objetos. Conseqüentemente, um diagrama de classes
UML, podendo ser detalhado com OCL, é utilizado para representar o ambiente
do sistema.
A visão de organização modela a sociedade de agentes como uma unidade
que oferece serviços. Esses serviços possuem um conjunto de objetivos, e podem
ser acessados por uma interface através de protocolos de mensagens. As
organizações podem participar de uma relação de dependência para mostrar como
elas são organizadas no modelo cliente-servidor. Por exemplo, ilustrar como os
agentes de uma organização requisitam os serviços de agentes pertencentes a outra
organização.
32
Figura 12: A visão de organização do ANote.
2.2. Frameworks Orientados a Objetos
Frameworks orientados a objetos (Fayad et al., 1999) é uma tecnologia de
software que permite a construção rápida e fácil de um software. A demanda por
este tipo de tecnologia é cada vez mais constante. Por exemplo, uma ferramenta
de e-commerce necessita de uma tecnologia que permita mudanças constantes no
software para que possa se adequar às constantes alterações nas regras de
comércio entre as empresas. A tecnologia dos frameworks orientados a objetos
permite essas mudanças rápidas de desenvolvimento para que o software possa se
adequar às alterações necessárias.
Frameworks orientados a objetos geram aplicações instanciadas com muita
rapidez, acompanhando assim a constante necessidade de gerar serviços e
produtos inovadores. As suas principais características são:
(i)
Reutilização - A possibilidade de reutilizar código nas várias
aplicações instanciadas pelo frameworks orientados a objetos é que
permite diminuir o tempo de desenvolvimento do software. Utilizando
uma modelagem orientada a objetos reutilizável (Fayad et al., 1999),
frameworks permitem o re-uso das classes, subsistemas ou até o
sistema para a geração de novas aplicações instanciadas.
(ii)
Flexibilidade - Frameworks orientados a objetos são flexíveis
suficientes para construir variações e extensões no software. Isso
permite desenvolver uma gama de aplicações que cobrem um domínio
bem amplo.
Frameworks orientados a objetos possuem um núcleo de software, com
trechos de código já escritos, e vários pontos de flexibilização (Fayad et al., 1999),
que necessitam de desenvolvimentos futuros. Nesses pontos de flexibilização são
33
implementadas as variações e extensões necessárias para a criação da aplicação
final.
Para o desenvolvimento do núcleo é preciso que se faça, antes de qualquer
coisa, uma análise de requisitos das várias aplicações pertencentes ao domínio.
Nessa análise de requisitos são identificados os pontos em comum das aplicações
e as variações. No desenvolvimento dos frameworks orientados a objetos são
implementados os vários pontos em comum, e indicados os locais onde
implementar os vários pontos de flexibilização.
2.3. Padrões de Projeto (Design Patterns)
"Um padrão descreve um problema que ocorre inúmeras vezes em
determinado contexto, e descreve ainda a solução para esse problema, de modo
que essa solução possa ser utilizada sistematicamente em distintas situações"
(Alexander et al, 1977). Conseqüentemente, os design patterns são muito
importantes para o processo de desenvolvimento de software, especialmente nas
áreas de manutenção e reuso de código.
Os design patterns são definidos como soluções para problemas recorrentes.
Christopher Alexander apresentou em seu trabalho (Alexander et al, 1977;
Alexander, 1979) os primeiros design patterns. Ele escreveu sobre a sua
experiência em engenharia civil para resolver problemas de projetos que
apareciam de forma recorrente em construções e cidades. Esse processo de
documentação de soluções para problemas recorrentes começou na área de
desenvolvimento de software a cerca de 15 anos atrás. Os princípios de Alexander
estão presentes na criação das primeiras documentações de design patterns.
Os documentos funcionavam como um guia para desenvolver software, e
seu público alvo era programadores novatos que queriam adquirir conhecimento
com os engenheiros de software mais experientes. Um dos trabalhos mais práticos
nessa área resultou no livro do gang of four (Gamma et al., 1995) em 1995 por
Eric Gamma, Richard Helm, Ralph Johnson e John Vlissides. O livro descreve 23
padrões que surgiram a partir da experiência dos autores no desenvolvimento de
software.
34
Os principais objetivos dos padrões de projetos são (Gamma et al., 1995):
(i)
Capturar a experiência e o conhecimento de um especialista em
projeto de software;
(ii)
Especificar abstrações com um nível acima de classes, objetos
ou componentes;
(iii)
Definir um vocabulário comum para que os problemas e
soluções possam ser discutidos;
(iv)
Definir uma arquitetura de software com fácil documentação e
manutenção;
(v)
Determinar propriedade que auxiliem projetos de arquitetura;
(vi)
Auxiliar o desenvolvimento de arquiteturas complexas.
A descrição dos design patterns utiliza alguns formatos comuns, tais como
Alexandrian (Alexander, 1979), GoF (Gamma et al., 1995), e POSA (Buschmann
et al., 1996). O padrão apresentado no capítulo 4 utiliza um formato que combina
elementos do GoF e POSA. Os elementos mais importantes são:
(i)
Nome e Intenção – definem de forma sucinta a essência do
padrão; A escolha do nome é extremamente importante, pois é
incorporado ao vocabulário dos engenheiros de software;
(ii)
Contexto – descreve as situações onde o padrão deve ser
aplicado, e fornece evidências de sua generalidade;
(iii)
Problema – descreve as dificuldades de design normalmente
encontradas por engenheiros de software;
(iv)
Forças - descrevem de forma sucinta os principais objetivos;
(v)
Solução – descreve como resolver o problema de design já
definido. Essa solução define elementos ou participantes que
criam um design em termos de abstrações de um paradigma de
programação. Essa solução deve atingir todos os objetivos de
design definidos, e resolver os problemas para todas as
aplicações do contexto apresentado;
35
2.4. Algoritmos para Agentes Inteligentes
Esta seção apresenta de forma sucinta alguns algoritmos de Inteligência
Artificial, Machine Learning, Predição em Séries Temporais, Otimização
Combinatória, e Análise de Agrupamento utilizadas nesta tese. Esses algoritmos
são úteis para implementar agentes inteligentes que resolvem problemas
complexos e aprendem a se adaptar a novas experiências.
A seção 2.4.1 apresenta algumas definições de Inteligência Artificial, e
descreve o método de busca Minimax com a técnica de poda Alpha-Beta. A seção
2.4.2 apresenta uma subárea da Inteligência Artificial chamada Machine
Learning, e apresenta duas técnicas desta área: Redes Neurais e Algoritmos
Genéticos. A seção 2.4.3 apresenta algumas técnicas de Predição em Séries
Temporais: a Média Móvel e a Exponencial Suavizada. A seção 2.4.4 apresenta a
Otimização Combinatória, e a técnica de formulação de Programação Inteira. A
seção 2.4.5 apresenta a Análise de Agrupamento e um algoritmo chamado
Isodata.
2.4.1.Inteligência Artificial
Um agente racional é uma entidade que faz a coisa correta (Russell et al.,
1995). Porém, o que é fazer a coisa correta? Os autores afirmam que é equivalente
a definir o “como” e “quando” esse agente atinge o sucesso. Conseqüentemente, o
termo medida de performance é utilizado para definir esse grau de sucesso e
responder o: (i) “como” – um critério para determinar o quanto o agente é bem
sucedido, e o (ii) “quando” – o momento certo para fazer essa avaliação.
Winston (Winston, 1992) define Inteligência Artificial (IA) como “o estudo
das computações que permitem uma entidade sentir, pensar e agir”. A área possui
dois objetivos principais para o autor: (i) visão de engenharia – a IA tem o
objetivo de resolver problemas reais utilizando um ferramental de idéias sobre
representação do conhecimento, a utilização do conhecimento, e integração de
sistemas; e (ii) visão científica – a IA é utilizada para determinar quais ideais
sobre representação do conhecimento, a utilização do conhecimento, e integração
de sistemas, melhor explicam os vários tipos de inteligência.
36
2.4.1.1.Busca Minimax
O Minimax (Russell et al., 1995) é uma técnica de busca para determinar a
estratégia ótima em um cenário de jogo com dois jogadores. O objetivo dessa
estratégia ótima é decidir a melhor jogada para um dado estado do jogo. Há dois
jogadores no Minimax: o MAX e o MIN. Uma busca em profundidade é feita a
partir de uma árvore onde a raíz é a posição corrente do jogo. As folhas dessa
árvore são avaliadas pela ótica do jogador MAX, e os valores dos nós internos são
atribuídos de baixo para cima com essas avaliações. As folhas do nível minimizar
são preenchidas com o menor valor de todos os seus nós filhos, e o nível de
maximizar são preenchidos com o maior valor de todos os nós filhos. Essa técnica
é utilizada combinada com uma técnica de poda chamada Alpha-Beta (Russell et
al., 1995).
2.4.2.Machine Learning
Machine Learning é uma subárea da Inteligência Artificial que está
relacionada com os programas que aprendem com experiência (Russell et al.,
1995). As técnicas de Machine Learning são cruciais para fornecer estratégias
conhecidas aos agentes em ambiente imprevisíveis e heterogêneos como a
Internet.
A área de Machine Learning estuda as questões de como construir
programas de computadores que melhoram automaticamente com a experiência
37
(Mitchell, 1997). Essas técnicas podem ser classificadas em relação ao processo
de aprendizado que visa melhorar automaticamente a sua performance:
(i)
Aprendizado Supervisionado – O algoritmo de aprendizado é treinado com
um conjunto de entradas conhecidas e saídas corretas correspondentes. A
técnica de aprendizado adapta o conhecimento para que o erro entre a saída
atual e a saída correta seja o menor possível. Esse tipo de aprendizado se
assemelha ao aprendizado de um aluno com um professor amigo que
fornece exemplos e orientações.
(ii)
Aprendizado Não Supervisionado – O algoritmo de aprendizado é treinado
apenas com as entradas conhecidas, mas sem as saídas corretas
correspondentes.
O
algoritmo
procura
por
padrões
interessantes,
regularidades ou agrupamentos nessas entradas conhecidas. Esse tipo de
aprendizado se assemelha ao aprendizado de um aluno que procura
identificar regularidades e generalizações a partir apenas de observações
empíricas.
(iii) Aprendizado Semi-Supervisionado - O algoritmo de aprendizado é treinado
com um conjunto de dados rotulados (entradas e saídas corretas conhecidas)
e outra parte não rotulada (apenas entradas conhecidas). O conjunto não
rotulado é utilizado para incrementar a performance de modelos de
classificação
tradicionais,
baseados
no
processo
de
aprendizado
supervisionado que utilizam apenas os dados rotulados.
(iv) Aprendizado por Reforço - O algoritmo de aprendizado é treinado sem
nenhum conjunto de treinamento. O algoritmo deve adquirir o
conhecimento através de ações feitas em um ambiente. Esse ambiente
simplesmente fornece recompensas e penalidades, ou reforços, por ações
boas ou ruins executadas pelo algoritmo. Conseqüentemente, o algoritmo
deve adaptar o seu conhecimento para sugerir apenas ações boas. Esse tipo
de aprendizado se assemelha ao aprendizado de um aluno com um crítico,
que fornece apenas mensagens do tipo “muito bom” ou “péssima
alternativa”.
38
2.4.2.1. Redes Neurais
As Redes Neurais (Mitchell, 1997) são sistemas inspirados nos neurônios
biológicos e o poder de processamento paralelo do cérebro com vários neurônios.
Uma rede neural artificial é composta por várias unidades de processamento
chamadas neurônios artificiais.
Assim como o sistema nervoso é composto por bilhões de células nervosas,
a rede neural artificial também é formada por unidades que simulam o
funcionamento de um neurônio. Estes módulos devem receber e retransmitir
informações tal como um neurônio biológico.
Figura 14: O Neurônio Artificial.
Um tipo de rede neural muito popular é baseado na unidade chamada
perceptron (Rosenblatt, 1959). O perceptron (Mitchell, 1997) recebe um vetor de
entrada com números reais, calcula a combinação linear dessas entradas, e gera
uma saída igual a 1 se o valor é maior do que um mínimo estabelecido. Caso
contrário, o valor é -1. Precisamente, dadas as entradas x1 até xn , a saída o(x1, ...,
xn) é calculada da seguinte forma:
o( x1 ,..., x n ) =
1, se w0 + w1 x1 + w2 x 2 + ... + wn x n > 0
− 1, caso o contrário
Onde cada wi é uma constante de valor real, ou peso, que determina a
contribuição da entrada xi na saída do perceptron. Note que a quantidade –w0 é
um valor mínimo que a combinação w1x1 + ... + wnxn precisar atingir para que o
perceptron gere a saída 1.
O aprendizado no perceptron é um processo de escolha de valores para os
pesos w0,...,wn. Esse processo ocorre com a adaptação dos pesos a partir de um
39
conjunto de entradas conhecidas e saídas corretas correspondentes. Uma maneira
de aprender todos esses pesos é começar com valores aleatórios, e depois
iterativamente aplicar o perceptron para cada exemplo do conjunto de
treinamento, modificando os seus pesos toda vez que a saída gerada diferir da
saída esperada. A Regra do Perceptron (Rosenblatt, 1959) é um algoritmo para
atualizar os pesos do perceptron a cada passo no processo de aprendizado:
wi = wi + . (t – o).xi
Onde wi é i-ésimo peso do perceptron, xi é a i-ésima entrada do perceptron,
t é a saída esperada para o exemplo de treinamento, o é a saída gerada pelo
perceptron, e
é uma constante positiva chamada taxa de aprendizado. Essa taxa
tem o objetivo de regular o grau de mudança dos pesos a cada passo, e
normalmente é um valor pequeno como, por exemplo, 0.1.
2.4.2.2.Algoritmos Genéticos
Os algoritmos genéticos (Winston, 1992) utilizam um procedimento de
busca inspirado na evolução natural. Os passos utilizados dentro dos algoritmos
usam rotinas análogas, de uma certa forma, ao cruzamento de indivíduos,
cruzamento de cromossomos, mutação de genes, e seleção natural.
Um ponto importante a ressaltar na seleção natural é a baixa eficiência
apresentada ao utilizar mecanismos simples de seleção. Para obter resultados
melhores, o mecanismo precisa levar em consideração a diversidade entre os
indivíduos e a capacidade individual.
Nos algoritmos genéticos, a pouca diversidade apresenta um resultado
interessante: uma busca apenas de um ótimo local. Porém, o objetivo da busca não
é esse, mas sim encontrar um ótimo global. Para encontrar esse ótimo global, a
diversidade se torna um fator fundamental. Assim como na evolução natural, os
algoritmos genéticos sacrificam parte da sua população em ótimos locais para que
outros indivíduos consigam atingir o ótimo global.
Um cromossomo nesses algoritmos representa um ponto no espaço de
busca, e o objetivo é criar novos cromossomos a partir dos existentes que estejam
mais próximos do ótimo global. É importante notar que cada cromossomo:
40
(i)
possui uma lista de elementos chamados de genes;
(ii)
representa um ponto no espaço de busca com um valor associado
que representa o quão forte (fitness) esse indivíduo é;
(iii)
um novo cromossomo pode ser criado utilizando o conceito de
cruzamento de outros dois cromossomos;
(iv)
um novo cromossomo também pode ser criado utilizando o
conceito de mutação, onde esse novo cromossomo possui um
gen modificado.
O algoritmo abaixo imita a evolução natural (Winston, 1992).
(i)
crie uma população inicial de um cromossomo;
(ii)
faça a mutação de um ou mais genes utilizando um ou mais
cromossomos existentes em sua população, produzindo assim
um novo cromossomo a cada nova mutação;
(iii)
faça o cruzamento de um ou mais cromossomos;
(iv)
adicione os cromossomos novos gerados a partir da mutação e do
cruzamento à população atual;
(v)
crie uma nova geração mantendo os melhores cromossomos de
sua população, junto com alguns outros cromossomos escolhidos
aleatoriamente de sua população atual. Nessa escolha aleatória,
aumente a probabilidade de escolha para os cromossomos que
tiverem um "fitness" maior;
(vi)
volte ao passo dois até que um cromossomo de sua nova geração
tenha atingido o objetivo (maior "fitness").
2.4.3.Predição em Séries Temporais
A predição em séries temporais, ou técnicas de Forecasting (Bowerman et
al, 1993; Chopra et al., 2004), são muito utilizadas para calcular valores futuros de
demanda ou preços baseados em dados históricos. Por exemplo, os métodos de
forecasting de demanda são a base do planejamento estratégico em uma cadeia de
suprimento. O objetivo das técnicas de forecasting, na pratica, é apoiar as
decisões, tais como (i) quantos produtos devem ser produzidos esse mês? (ii) qual
41
o tamanho do lote de compra de uma determinada matéria prima? (iii) quando
efetuar esse pedido de compra de matéria prima?
Uma das técnicas de forecasting em séries temporais mais simples se chama
Média Móvel, e pode ser definida pela seguinte fórmula:
onde:
é a série histórica (N termos)
é a seqüência de n preços previstos (janela de
tamanho n)
Uma outra técnica de forecasting em séries temporais se chama Exponencial
Suavizada, e pode ser definida pela seguinte fórmula:
si = α .ai −1 + (1 − α ).si −1
onde:
é a série histórica (N termos)
{s i }in=1
é a seqüência de n preços previstos
é a constante de suavização
Observe que pela sua definição recursiva, o si pode re-escrito como:
s i = α .ai −1 + α .(1 − α ).ai − 2 + α .(1 − α ) 2 .ai −3 + ...
Essa fórmula mostra o efeito do desconto no valor da informação
introduzida por , que é usualmente escolhido no intervalo 0 <
< 1.
2.4.4. Otimização Combinatória
Um Solver, ou otimizador, (Solver.com, 2005; Wolsey, 1998) é uma
ferramenta de software que ajuda a encontrar a melhor maneira de alocar recursos.
42
Esse recursos podem ser matéria prima, homem – hora, ou qualquer coisa com um
estoque limitado. A solução ótima pode ser essa alocação que gere o maior lucro,
o menor custo, ou encontre a melhor qualidade possível. Para utilizar um solver,
um modelo precisa ser criado para especificar:
(i)
Os recursos a serem utilizados, ou variáveis de decisão;
(ii)
Os limites de recursos que podem ser utilizados, ou restrições;
(iii)
A medida de otimização, ou o objetivo.
A formulação de programação inteira é uma linguagem matemática para
criar esses modelos de otimização.
Seja:
max{ cx : Ax
b, x
0 } um programa linear.
Onde A é uma matriz de m por n elementos, c é um vetor linha de dimensão
n, b é um vetor coluna de dimensão m, e x é um vetor coluna de dimensão n com
variáveis de decisão. Na programação inteira as componentes de x são todas
variáveis inteiras. Conseqüentemente:
(i)
A Função Objetivo é definida por:
max cx
(ii)
Variáveis de decisão são definidas por:
x
(iii)
0, e x possui apenas valores inteiros.
Restrições são definidas por:
Ax
b
A tradução de um problema para esta formulação nem sempre é uma tarefa
simples. Definir variáveis e restrições para esse modelo de otimização quase
sempre requer um trabalho de engenharia de algoritmos, pois o problema de
decisão da programação inteira é NP-completo (Wolsey, 1998).
2.4.5. Análise de Agrupamento
O principal objetivo dos algoritmos de Agrupamento (Duda et al., 1973;
Lebart et al., 1997) é agrupar dados que possuem padrões semelhantes. Esses
grupos também são conhecidos por clusters ou partições. O problema de
43
agrupamento pode ser considerado também como um método de particionamento
de um espaço. O ideal é que esse particionamento organize os dados de tal
maneira que se possa tomar decisões corretas. Caso isso não seja possível, o
objetivo é obter uma probabilidade de erro bem pequena.
Os algoritmos de agrupamento se tornam muito interessantes para a área de
Inteligência de Mercado que está preocupada também em encontrar grupos de
consumidores com padrões de consumo ou hábitos semelhantes. Esses padrões
encontrados permitem criar produtos e serviços personalizados para esses grupos,
aumentando assim o foco da empresa e a satisfação dos clientes.
2.4.5.1. Algoritmo Isodata
O Isodata (Duda et al., 1973; Lebart et al., 1997) é um algoritmo de
agrupamento muito conhecido pela sua simplicidade e rapidez de processamento.
A entrada desse algoritmo é o conjunto I de n indivíduos a serem particionados,
onde cada indivíduo possui p atributos. Esse conjunto representa os dados a serem
agrupados. Suponha que o espaço Rp possui uma distância d entre os n pontosindivíduo (por exemplo, a distância euclidiana). Além disso, um limite máximo de
q classes é estabelecido para o resultado do algoritmo.
O algoritmo (Lebart et al., 1997) ilustra as etapas que determinam as
classes:
Etapa 0: Determine q centros provisórios das classes (por exemplo,
de maneira pseudo-aleatória). Os centros são:
{C10 ,..., C k0 ,..., C q0 }
Calcule uma primeira partição P0 do conjunto I em q classes:
{I 10 ,..., I k0 ,..., I q0 }
0
Um individuo i pertence a uma classe I k se ele é mais próximo a
C k0 do que a qualquer outro centro.
Etapa 1: Determine os q novos centros das classes:
{C11 ,..., C k1 ,..., C q1 }
Calculando os centros de gravidade a partir das partições:
44
{I 10 ,..., I k0 ,..., I q0 }
Esses novos centros permitem o cálculo de uma nova partição P1 de
I, utilizando a mesma regra empregada para determinar P0. A nova
partição P1 é formada pelas classes:
{I 11 ,..., I k1 ,..., I q1 }
Etapa m: Determine os q novos centros das classes:
{C1m ,..., C km ,..., C qm }
Calculando os centros de gravidades a partir das partições:
{I 1m−1 ,..., I km−1 ,..., I qm−1 }
Esses novos centros permitem o cálculo de uma nova partição Pm de
I, utilizando a mesma regra empregada para determinar P0. A nova
partição Pm é formada pelas classes:
{I 1m ,..., I km ,..., I qm }
Aos poucos o processo converge e o algoritmo pode terminar o seu
processamento quando duas iterações sucessivas apresentarem as mesmas
partições. Uma maneira para determinar se as partições são idênticas é utilizando
a medida da variância intra-classes. Muitas vezes, o algoritmo é implementado
para não esperar a sua convergência completa. Mas para isso, uma margem de
erro é definida para que seja possível determinar o ponto de parada. Essa margem
de erro permite calcular quanto que uma partição pode diferir da partição
sucessiva.
O resultado das partições é representado pelos centros ou centróides. Um
centróide pode ser considerado um indivíduo que melhor representa as
características de sua partição.
45
3 ASYNC – Um Framework para Construção de Agentes
Inteligentes
Este capítulo apresenta o Agent’s SYNergistic Cooperation (ASYNC)
framework. O ASYNC (Sardinha et al., 2003a) é um framework orientado a
objetos que permite construir agentes de software em ambientes distribuídos. O
framework proposto foi concebido através de um desenvolvimento bottom-up.
Três aplicações baseadas em agentes foram desenvolvidas para identificar o
código re-utilizável: (i) Uma ferramenta (Sardinha, 2001; Milidiú et al., 2001) que
utiliza agentes reativos e evolutivos para identificar interdependência de produtos
para promoção em um mercado varejista; (ii) Uma ferramenta (Bevilacqua et al.,
2001) baseada em agentes para criar grupos de consumo, e (iii) Uma ferramenta
(Ribeiro, 2001) de negociação entre agentes. Através desse desenvolvimento, os
pontos em comuns foram identificados e o domínio especificado.
Conseqüentemente, o domínio desse framework orientado a objetos engloba
todas as aplicações baseadas em agentes assíncronos e distribuídos. A seção 3.1
apresenta o estudo de caso Bundles.com (Sardinha, 2001; Milidiú et al., 2001). A
seção 3.2 apresenta o framework orientado a objetos ASYNC, a seção 3.3
descreve o processo de instanciação do framework, e a seção 3.3 apresenta uma
ferramenta para executar os agentes criados com o ASYNC. Uma aplicação
chamada Babilônia (Ribeiro, 2001) é apresentada de maneira resumida na seção
3.4. Esta aplicação foi implementada pela aluna de mestrado Paula Clark e
documentada em sua dissertação. Além de apresentar um exemplo de re-utilização
de código do ASYNC por uma outra pessoa, essa aplicação foi muito importante
no processo de generalização e design final do framework.
3.1. Estudo de Caso - A Aplicação Bundles.com
A primeira aplicação que utilizou o ASYNC permite a criar promoções
utilizando o conceito de agregação de produtos. A aplicação se chama
Bundles.com (Sardinha, 2001; Milidiu et al, 2001). A tarefa de criar pacotes não é
46
trivial, pois muitas vezes o que parece ter apelo de marketing pode não gerar a
receita esperada.
Esse projeto de software utiliza a técnica orientada a objetivos para a fase de
requisitos. Esta fase utiliza o processo recursivo de decomposição de um objetivo
do problema principal em vários objetivos de subproblemas mais simples.
Figura 15: A decomposição dos objetivos.
O objetivo maior do sistema é encontrar pacotes de produtos que
maximizem a margem de lucro. Porém, dois objetivos foram identificados para
encontrar essas ofertas: (i) Encontrar segmentos de mercado através de uma base
de dados e algum algoritmo de clustering, e (ii) Simular um mercado competitivo
para encontra as ofertas mais rentáveis.
sejam capazes de conduzir os objetivos da figura 15. Essa criação começa com
processo de relacionamento de todos os objetivos de nível mais baixo e tipos de
agentes. A tabela 3 apresenta um mapeamento entre esses objetivos e tipos de
Objetivo
Agente
Obter Histórico de Consumo
Analista de Mercado
Encontrar Estereótipos de
Analista de Mercado
Consumidores
Vender Produtos e Maximizar
Vendedor
Receita
Comprar Produtos para Maximizar
Comprador
a Satisfação
47
Figura 16: apresenta a arquitetura do Bundles.com.
O agente Analista de Mercado identifica os segmentos de mercado com
padrões de consumo semelhantes utilizando um algoritmo de clustering chamado
Isodata (Duda et al., 1973; Lebart et al., 1997). O resultado desse algoritmo são
centróides que representam estereótipos de consumidores. Conseqüentemente,
todos os consumidores de um mesmo segmento devem diferir muito pouco desse
estereótipo. O agente executa esse algoritmo um número N de vezes, e seleciona
apenas os estereótipos que aparecem em todas as rodadas. A figura 17 apresenta o
diagrama de cenário do agente Analista de Mercado. Este diagrama possui
informações sobre o contexto de como o agente deverá atingir seus objetivos.
Figura 17: Diagrama de Cenários do Analista de Mercado.
A tabela 4 ilustra um resultado encontrado após as várias rodadas do
algoritmo Isodata. As colunas dessa tabela representam os nove estereótipos
encontrados a partir de uma base de dados com vários consumidores e suas
transações de compras. As linhas representam a quantidade de produtos que esses
consumidores estereótipos gostam de comprar para um dado período de tempo.
48
Através dos centróides é possível descobrir também algumas informações
relevantes a respeito dos padrões de consumo dos vários consumidores dentro dos
segmentos. A tabela 5 resume esse tipo de análise feito pelo agente. Os padrões de
consumo são identificados através da relação dos segmentos com as classes de
produtos.
Classe I
Classe II
Classe III
Classe IV
Classe V
Classe VI
Classe VII
Classe VIII
Classe IX
Classe X
Classe XI
Classe XII
Classe XIII
Classe XIV
1
0
0
0
0
0
0
0
4
0
0
96
0
0
0
2
90
0
3
0
0
0
0
5
0
0
2
0
0
0
3
0
0
0
0
0
0
0
4
90
2
4
0
0
0
Segmentos
5
6
0
0
0
0
70
5
0
0
0
0
10
0
0
0
10
20
0
0
10
70
0
0
0
5
0
0
0
0
4
0
0
1
0
0
0
0
93
0
2
5
0
0
0
7
10
0
5
0
0
0
0
10
0
5
0
70
0
0
8
10
2
3
0
7
13
0
11
3
3
7
36
0
0
Tabela 4: Exemplos de centróides encontrados com o algoritmo Isodata.
Segmento
Padrão de Consumo
1
Apenas produtos da classe XI.
2
Apenas produtos da classe I.
3
Apenas produtos da classe IX.
4
Apenas produtos da a classe VIII.
5
Produtos da classe III.
6
Produtos da classe X.
7
Produtos da classe XII.
8
Produtos da classe XII.
9
Produtos da classe XI.
Tabela 5: Tabela com os padrões de consumo dos nove centróides.
O agente Comprador e agente Vendedor simulam um mercado competitivo
para encontrar ofertas de produtos com alta lucratividade. O resultado dessa
9
10
0
10
0
0
2
0
20
3
5
50
0
0
0
49
simulação permite descobrir mais três informações relevantes: o segmento alvo de
uma oferta, a receita gerada, e o preço dos produtos.
Os Compradores recebem os resultados do Analista de Mercado para
simular o comportamento de consumo. Esses agentes iniciam o processo de
simulação com uma receita para comprar pacotes de bens, e utilizam a tabela 4
para selecionar os pacotes de bens que lhe interessam. A figura 18 apresenta o
diagrama de cenários do Comprador.
Os agentes Vendedores foram modelados com características evolutivas
(Winston, 1992) para descobrir pacotes que maximizem a preferência desses
consumidores e a lucratividade. A construção de boas ofertas para um agente
Vendedor envolve um problema de otimização combinatória. Conseqüentemente,
a função de fitness desse agente pode ser medida pela receita que se consegue
obter com a venda das ofertas menos o custo das mercadorias.
O resultado da simulação não deve encontrar apenas a melhor oferta, mas o
conjunto das melhores ofertas. Conseqüentemente, o algoritmo de otimização
escolhido precisa ser capaz de obter o ótimo global, e também os vários ótimos
locais existentes. Este foi um dos motivos principais para a escolha de um
algoritmo evolutivo para o agente Vendedor. A figura 19 exemplifica uma função
de fitness com o seu ótimo global e seus vários ótimos locais.
50
Figura 19: Os máximos locais e globais da função de fitness.
A simulação desse mercado competitivo possui vários agentes vendedores
que competem entre si. O objetivo de cada um é vender o maior número possível
de ofertas para um número limitado de consumidores. Além disso, estes
consumidores são limitados em recursos financeiros. A figura 20 apresenta o
diagrama de cenários do agente Vendedor.
A simulação começa com agentes vendedores sem receita, porém com
ofertas. Os agentes consumidores possuem dinheiro em uma conta corrente, e
estão dispostos a consumir essas ofertas para maximizarem a sua satisfação. Além
disso, o agente vendedor precisa acumular receita ou “energia” para sobreviver no
sistema.
51
O agente que não consegue acumular receita após um determinado período
simplesmente morre tal como uma seleção natural. O agente passa pelos seguintes
estados em cada geração:
(i)
Estado 1 (Reprodução) - Reproduz com outros agentes;
(ii)
Estado 2 (Mutação) - Escolhe se vai criar um descendente
mutante;
(iii)
Estado 3 (Tenta obter Energia) - Tenta vender a oferta para os
consumidores. A receita gerada pela venda representa a energia
obtida em uma geração;
(iv)
Estado 4 (Decide se consegue sobreviver) – O próprio agente
verifica se é possível sobreviver para a próxima geração, dado
um parâmetro do sistema que representa o mínimo de energia
para a sobrevivência no ambiente. O agente pode não sobreviver
também caso ele tenha atingido o número máximo de gerações
permitidas no sistema. Esse parâmetro de entrada existe para
poder estabelecer um número fixo de gerações em que o agente
tenta obter a meta de energia;
(v)
Estado 5 (Decide se atingiu a meta de energia) - Decide se
obteve a meta de energia estabelecida. Essa meta é um parâmetro
de entrada no sistema;
(vi)
Estado 6 (Vida Eterna) - Quando o agente consegue atingir a
meta de energia, ele apenas permanece no sistema para que
outros agentes possam utilizá-lo para fins de reprodução;
(vii)
Estado 7 (Morte do Agente) – O agente sai do sistema, e devolve
a receita obtida aos segmentos.
3.1.1.Simulação e Monitoramento
Uma interface de monitoração on-line do sistema foi desenvolvida para
monitorar a evolução do sistema multi-agente. Esta interface permite a
configuração inicial dos parâmetros do sistema. Essa parametrização se torna
disponível para os agentes através de um espaço de memória compartilhada. As
informações on-line são recolhidas também através dessa memória compartilhada.
A interface de monitoração é apresentada na figura 21.
52
Figura 21: Interface da Monitoração On-line.
3.1.2.Resultados da Evolução do Sistema
As ofertas iniciais para os agentes vendedores são escolhidas de forma
aleatória. Os agentes vendedores passam então por todos os estados descritos na
figura 20 para tentar sobreviver no sistema. O gráfico da figura 22 apresenta um
resultado típico da energia (receita) obtida pelos agentes vendedores nos vários
instantes de tempo. As fases ilustram bem a evolução do sistema:
Fase 1 - Nessa fase há uma abundância de recursos, pois os agentes
Compradores ainda não compraram nada e possuem muito dinheiro em
conta corrente. Devido ao seu comportamento guloso, a heurística criada
permite que os segmentos aceitem qualquer oferta interessante, mesmo não
sendo a melhor.
Fase 2 - Após a fase de abundância vem um período de escassez. Na
primeira fase, os Compradores compraram muitas ofertas e suas respectivas
contas correntes diminuíram muito. É nesta fase que os Vendedores
precisam evoluir para conseguirem vender os seus produtos.
53
Fase 3 - Após um período de evolução, os Vendedores conseguem
novamente vender a sua cesta de produtos para os Compradores.
Conseqüentemente, os Compradores esgotam quase todo o dinheiro
disponível nas contas correntes. A figura 22 apresenta um gráfico da
evolução do sistema, onde o eixo horizontal representa o tempo, e o eixo
vertical representa o total de receita obtido por todos os Vendedores.
Figura 22: Energia obtida pelos Agentes por instante de tempo.
3.2. ASYNC – Um Framework Orientado a Objetos para Construção
de Agentes Distribuídos e Assíncronos
O framework orientado a objetos ASYNC foi utilizado na construção de
todas as aplicações de sistemas baseados em agentes apresentados nesta tese. O
design desse framework orientado a objetos separa duas abstrações importantes
em agentes: ações internas e protocolos de interação. As ações internas são tarefas
executadas pelo agente que não dependem da interação com outros agentes. Os
protocolos de interação definem como o agente deve se comunicar e interagir com
outros agentes no sistema. Um plano do agente pode ser composto de ações
internas e protocolos de interação. O framework orientado a objetos também
fornece uma infra-estrutura de comunicação para agentes em um ambiente
distribuído.
O framework é composto por: (i) Duas classes abstratas, Agent e
InteractionProtocols; (ii) Duas classes concretas e finais, ProcessMessageThread
54
e
AgentCommunicationLayer;
e,
(iii)
Três
interfaces,
AgentMessage,
AgentBlackBoardInfo e AgentInterface.
Figura 23: O diagrama de Classes do Framework Orientado a Objetos ASYNC.
A classe abstrata Agent fornece as funcionalidades básicas do agente: (i)
init() - iniciar o agente e obter seus recursos do ambiente, (ii) terminate() – liberar
os recursos do ambiente, (iii) stop() – parar a execução do agente, (iv) process() execução das ações do agente, e (iv) trace() – impressão de mensagens na
console. O atributo name desta classe guarda o nome do agente, e deve ser único
no sistema por questões de implementação.
A interface AgentInterface é responsável por transformar a subclasse de
Agent em uma thread. Essa subclasse deve implementar o método run(), que é
responsável pela lógica da execução das ações internas do agente ou iniciar um
protocolo de interação.
A classe abstrata InteractionProtocols define as várias maneiras como o
agente deve interagir com outros agentes no sistema. Todo código relacionado
com interação deve ser colocado na subclasse de InteractionProtocols. Essa
55
subclasse deve implementar o método processMsg(), e definir a implementação do
tratamento de toda mensagem recebida por este agente.
A classe concreta e final ProcessMessageThread é responsável por
processar as mensagens recebidas pelo agente e executar o método processMsg()
da subclasse de InteractionProtocols.
A interface AgentMessage deve ser implementada pela classe que especifica
o formato da mensagem. Por exemplo, essa classe pode especificar o formato
FIPA ACL, KQML, etc. A interface AgentBlackBoardInfo deve ser implementada
pela classe que especifica o formato das informações no espaço de tuplas do
sistema.
A classe concreta e final AgentCommunicationLayer implementa toda a
camada de comunicação do agente. Esta classe fornece uma infra-estrutura para o
agente enviar mensagens síncronas ou implementar uma arquitetura de
blackboard utilizando o espaço de tuplas distribuído. Essa classe foi
implementada
como
uma
camada
sobre
o
software
IBM
TSpaces
(http://www.almaden.ibm.com /cs/TSpaces/). O software IBM TSpaces é uma
arquitetura reflexiva de espaços de tuplas em ambientes distribuídos, e fornece
operações básicas no espaço para leitura, escrita, etc. Uma descrição resumida de
cada método da classe AgentCommunicationLayer é apresentada abaixo:
(i)
addAgentBroadcastListener() – Método para incluir um agente na lista
de broadcast;
(ii)
blockingReadBBInfo() – Esse método é utilizado para ler uma
mensagem do espaço de tuplas. Se o agente executar esse método e a
mensagem não estiver presente no espaço de tuplas, a execução do
método é bloqueada até que essa mensagem esteja presente ou até um
timeout expirar;
(iii)
blockingTakeBBInfo() - Esse método é utilizado para ler e remover
uma mensagem do espaço de tuplas. Se o agente executar esse método
e a mensagem não estiver presente no espaço de tuplas, a execução do
método é bloqueada até que essa mensagem esteja presente ou até um
timeout expirar;
(iv)
deleteAllBB() – Método utilizada para apagar todo o espaço de tuplas;
(v)
readBBInfo() – Método utilizado para ler uma mensagem do espaço de
tuplas. Se a mensagem não estiver presente, o método retorna null;
56
(vi)
removeAgentBroadcastListener() – Método que remove o agente da
lista de broadcast;
(vii)
removeBBInfo() – Método para remover uma informação do espaço de
tuplas. Se a mensagem não estiver presente, o método retorna null;
(viii) scanBBInfo() – Método para fazer uma pesquisa nas mensagens
presentes no espaço de tuplas;
(ix)
sendBBInfo() – Método para enviar uma mensagem para o espaço de
tuplas;
(x)
sendBroadcast() – Método para enviar uma mensagem para todos os
agentes cadastrados na lista de broadcast;
(xi)
sendMsg() – Método para enviar uma mensagem para um único
agente;
(xii)
stopCommunicationLayer() – Método para finalizar a camada de
comunicação.
O design de um framework orientado a objetos pode ser dividido em duas
partes (Fontoura et al., 1998): (i) um subsistema kernel ou frozen spot com o
código comum a todas as aplicações instanciadas; e (ii) um subsistema hot spot
que define as diferentes características das aplicações instanciadas. Os hot spots
do ASYNC são as classes Agent, InteractionProtocol, AgentMessage,
AgentBlackboardInfo e AgentInterface. Os frozen spots do ASYNC são as classes
AgentCommunicationLayer e ProcessMessageThread.
3.2.1.Como Instanciar uma Aplicação Baseada em Agentes com o
Framework Orientado a Objetos do ASYNC
A primeira fase do desenvolvimento de um sistema baseado em agentes é a
construção do ambiente e seus recursos. O ambiente é implementado como uma
classe principal do sistema para armazena todas as referencias para: (i) todos os
agentes, e (ii) os recursos do sistema. A tabela 6 resume o processo de
instanciação do framework orientado a objetos ASYNC.
57
Conceitos de Agentes
Classes do ASYNC instanciadas
O ambiente e os recursos
(i) Classe Principal para o ambiente;
(ii) Classes para os recursos.
Agente
(i) Uma classe concreta que herda de
Agent, e implementa AgentInterface;
(ii) Uma classe concreta que herda de
Ações internas do Agente
Métodos incluídos na classe concreta
de Agent.
Protocolos de Interação
Método incluídos na classe concreta
de InteractionProtocols.
Formato das Mensagens (i) Classe concreta que implementa
nos protocolos de interação AgentMessage,
se
a
troca
de
mensagens é síncrona;
(ii) Classe concreta que implementa
AgentBlackBoardInfo, se a troca de
mensagens é assíncrona.
Tabela 6: Mapeamento dos Conceitos de Agentes para as Classes da Aplicação
instanciada.
Cada agente no sistema deve possuir duas classes concretas. A primeira
classe a ser implementada deve herdar da classe Agent e implementar a interface
AgentInterface. Essa classe concreta deve conter métodos que representam as
ações internas dos agentes. Os métodos initialize(), run(), terminate(), e trace()
devem ser implementados nesta classe concreta.
Esse mesmo agente do sistema deve ter outra classe concreta. Essa classe
deve herdar da classe InteractionProtocols, e deve conter métodos para
implementar os protocolos de interação. O método processMsg() deve ser
implementado para processar todas as mensagens recebidas pelo agente. A
referência para o objeto AgentCommunicationLayer é utilizada para que o agente
possa utilizar a camada de comunicação.
58
3.3.Instanciando o ASYNC para a Aplicação Bundles.com
A figura 24 apresenta o diagrama de classes do agente Vendedor na
aplicação Bundles.com instanciado com o ASYNC. As classes SellerAgent e
SellerAgentIP possuem o código do agente, e esta seção apresenta os detalhes
desta implementação.
Figura 24: A instanciação do Agente Vendedor na aplicação Bundles.com.
As ações internas do Vendedor foram modeladas no diagrama de cenários
do ANote da figura 25. Essas ações do agente não dependem da interação com
outros agentes no sistema. As ações “Reprodução”, “Mutação”, “Verifica se tem
Receita suficiente para sobreviver”, e “Verifica se atingiu meta de Receita” não
dependem da interação com outros agentes. Conseqüentemente, os métodos
reproduction(), mutation(), verifyRevenue(), e verifyGoal() da classe SellerAgent
modelam as ações descritas acima.
O código Java a seguir apresenta o
mapeamento das abstrações em ANote para o framework ASYNC.
59
Figura 25: Diagrama de cenário do Vendedor.
1. public class SellerAgent extends Agent implements AgentInterface {
2.
3.
public SellerAgent(String _name, InteractionProtocols _iP) {
4.
super(_name, _iP);
5.
}
6.
7.
public void initialize() {
8.
...
9.
}
10.
11.
public void terminate() {
12.
...
13.
}
14.
15.
public void trace(String msg, int level) {
16.
...
17.
}
18.
19.
public void run() {
20.
SellerAgentIP sellerIP;
21.
sellerIP = (SellerAgentIP)getInteractionProtocols();
22.
while(true) {
23.
reproduction();
24.
mutation();
25.
sellerIP.sendProposalBuyer();
26.
waitForProposalResponse();
27.
verifyRevenue();
28.
verifyGoal();
29.
}
30.
}
31.
32.
public void reproduction() {
33.
...
34.
}
35.
36.
public void mutation() {
37.
...
38.
}
39.
40.
public void verifyRevenue() {
60
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51. }
...
}
public void verifyGoal() {
...
}
public void waitForProposalResponse() {
...
}
Os protocolos de interação do Vendedor também são modelados pelo
diagrama de cenários da figura 25. Os protocolos de interação definem como o
agente deve se comunicar e interagir com outros agentes no sistema. As ações
“Envia Proposta para Comprador sobre Oferta” e “Recebe Resposta da Proposta e
Receita”
exigem
Conseqüentemente,
uma
essas
interação
ações
com
devem
outros
ser
agentes
colocadas
no
sistema.
nos
métodos
sendProposalBuyer() e receiveProposalResponse(AgentMessage msg). O método
sendProposalBuyer() utiliza o método sendMsg() da camada de comunicação para
enviar as mensagens para os agentes Compradores.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
public class SellerAgentIP extends InteractionProtocols {
public void processMsg(AgentMessage msg) {
receiveProposalResponse((FipaACLMessage)msg);
}
public void sendProposalBuyer() {
FipaACLMessage msg = new FipaACLMessage();
getAgCommLayer().sendMsg("BuyerAgent",msg);
}
public void receiveProposalResponse(FipaACLMessage msg) {
...
}
}
3.4. ASYNC-D – A Ferramenta de Distribuição dos Agentes em CPUs
Distintas de um Rede
A ferramenta ASYNC-D auxilia o processo de execução dos agentes em um
ambiente distribuído. A ferramenta possui dois agentes de software reativos
chamados Diretor de Distribuição e Coordenador de Distribuição. Esses agentes
são responsáveis por coordenar a execução dos outros agentes no sistema. A
figura 26 apresenta os agentes da ferramenta ASYNC-D.
61
O agente Diretor da Distribuição é responsável por selecionar quais agentes
devem ser executados em cada CPU. Após essa decisão, o Diretor envia uma
mensagem para o Coordenador de Distribuição com a lista de agentes que devem
ser executados. Conseqüentemente, toda CPU deve possuir um agente
Coordenador de Distribuição rodando, e eles são responsáveis por executar e
“matar” os agentes de sua responsabilidade. O Diretor pode enviar uma
mensagem para os Coordenadores requisitando a “morte” de algum agente
também. Essa ferramenta funciona apenas com agentes de software instanciados
pelo ASYNC.
Figura 26: Os agentes do ASYNC-D.
A console de configuração da figura 27 é utilizada para definir a decisão do
Diretor de Distribuição. A console permite selecionar os agentes que devem ser
executados por cada Coordenador. Essa configuração é utilizada pelo Diretor para
62
enviar as mensagens para o Coordenador de Distribuição com a lista de agentes
que devem ser executados.
Figura 27: A Console de Configuração do ASYNC-D.
3.5.Aplicação Babilônia
Esta seção apresenta a aplicação desenvolvida pela aluna de mestrado Paula
Clark em sua dissertação (Ribeiro, 2001). A modelagem da aplicação foi feita
com Gaia (Wooldridge et al., 2000; Zambonelli et al, 2003), e na dissertação foi
proposta um mapeamento entre os modelos de Gaia e o framework ASYNC.
A aplicação Babilônia é um mercado virtual para compra e venda de bens.
Os agentes no sistema também implementam uma negociação automática entre
compradores e vendedores. Além disso, o sistema implementa um mecanismo de
certificação dos vendedores, compradores e bens para garantir a segurança das
transações.
O sistema multi-agente foi modelado utilizando uma arquitetura
organizacional de Gaia com os respectivos papeis de agentes: Comprador,
Vendedor, e Certificador. A comprador é responsável por cadastrar as
características dos bens desejados, tais como marca e modelo. Todo bem ofertado
por um Vendedor que casar com esse cadastro é enviado para o Comprador. O
Comprador então decide se começa ou não o processo de negociação. Na
negociação alguns parâmetros são utilizados por este Comprador: preço inicial de
compra, preço máximo pago pelo bem, o incremento de preço utilizado no
processo de negociação.
63
O Vendedor também possui alguns parâmetros para o processo de
negociação: preço inicial da oferta, preço mínimo que a oferta vale, e o
decremento de preço utilizado no processo de negociação. O Vendedor deve
indagar o agente Certificador se o processo de negociação necessita de alguma
certificação.
O Certificador é responsável por certificar os Vendedores, os Compradores
e os bens envolvidos no processo de negociação. Esse agente faz uma busca em
vários bancos de dados e informações de proteção ao crédito fora dos sistema para
garantir a segurança do processo.
O processo de negociação entre os agentes é totalmente automático, e para
implementar o sistema foi utilizado o framework ASYNC. A figura 28 apresenta
as classes do agente Comprador. A classe AgentBuyer especializa a classe Agent e
implementa a interface AgentInterface, e a classe AgentBuyerIP herda da classe
InteractionProtocols. Esse estudo de caso permitiu um grande re-uso de código,
uma diminuição no tempo de desenvolvimento menor, e uma menor
complexidade para implementar agentes de software.
Figura 28: As classes do Agente Comprador.
64
4 MAS-School - Um Método para Incluir Aprendizado em
Sistemas Multi-Agente
A tecnologia de agentes é utilizada em muitos simuladores e sistemas
inteligentes para auxiliar as pessoas em várias tarefas complexas. Aplicações para
o Comércio Eletrônico, Extração de Informação, e Business Intelligence também
estão utilizando esta tecnologia para resolver problemas complexos de forma
assíncrona e em ambientes distribuídos. Neste contexto, os algoritmos de Machine
Learning ou Aprendizado de Máquina são cruciais para fornecer estratégias
conhecidas para construir agentes em ambiente abertos e heterogêneos como a
Internet.
Porém, incluir essas técnicas de inteligência em sistemas multi-agente de
larga escala não é uma tarefa simples. O design e implementação de tais sistemas
inteligentes sempre apresentam questões semelhantes, dentre as quais:
(viii)
Como avaliar o objetivo do sistema como um todo?
(ix)
Como definir e avaliar o objetivo individual de cada agente?
(x)
Como modelar o conhecimento de cada agente?
(xi)
Como projetar o mecanismo de aquisição de conhecimento para cada
agente?
(xii)
Como combinar múltiplas técnicas de aprendizado e distribuir essas
técnicas para cada agente no sistema?
(xiii) Como associar abstrações de agentes com abstrações de machine
learning?
(xiv)
Como especificar abstrações de machine learning nas primeiras
fases de design e permitir uma transição para a fase de
implementação?
intuição para resolver as questões acima. Muita pesquisa tem sido feita para criar
na fase inicial de design. Os frameworks (Howden et al., 2001; Telecom Itália-
65
Jade, 2003) de implementação disponibilizam APIs para desenvolver sistemas
multi-agente, mas não orientam a estruturação do design do aprendizado de uma
maneira sistemática. Além disso, muitas metodologias (Zambonelli et al., 2003;
Deloach, 1999; Bresciani et al., 2004; Padgham et al., 2002) de desenvolvimento
orientadas a agentes são focados em um nível muito alto de abstração, e não
indicam como tratar aprendizado desde a fase de design até a implementação.
Este capítulo apresenta o método MAS-School (Sardinha et al., 2004b;
Sardinha et al., 2005b) para incluir técnicas de machine learning desde as
primeiras fases de design. Esse método apresenta várias orientações de como
incluir aprendizado na fase de design e implementação. O método apresenta no
final uma estratégia incremental de desenvolvimento para permitir a avaliação das
técnicas de machine learning.
4.1. Incluindo Aprendizado em Sistemas Multi-Agente
Mitchell (Mitchell, 1997) define machine learning como : “Diz-se que um
programa de computador aprende a partir de uma experiência E em relação a uma
classe de tarefas T e medida de performance P, se a sua performance nas tarefas T,
medida por P, melhora com a experiência E”. Conseqüentemente, as técnicas de
aprendizado são normalmente utilizadas para melhorar a performance de um
sistema.
O principal objetivo do método aqui proposto é incluir disciplinadamente as
técnicas de machine learning em sistemas multi-agente. Esse método também
permite, em sua fase de implementação, a integração de diferentes algoritmos de
machine learning e a avaliação da performance do sistema. O método possui
quatro fases distintas:
(i)
Objetivo Sistêmico & Seleção da Medida de Performance,
onde um objetivo e uma medida de performance são
selecionados para o sistema;
(ii)
Seleção do Agente & Definição do Objetivo do Aprendizado no
Agente, onde agentes são selecionados, e objetivos são
atribuídos para o algoritmo de aprendizado;
66
(iii)
Design do Aprendizado no Agente, onde o design de código é
definido; e
(iv)
Implementação Incremental & Avaliação de Performance,
onde uma implementação incremental é proposta com
treinamento, teste e avaliação.
A figura 29 apresenta as quatro fases do método. A seguir apresentamos em
detalhe cada fase do método.
Figura 29: O método para incluir Aprendizado em um Sistema Multi-Agente.
4.1.1. Objetivo Sistêmico & Seleção da Medida de Performance
O Engenheiro de Software deve definir nesta fase dois elementos centrais
que estão relacionados com aprendizado: (i) Objetivo Sistêmico, SG, e (ii) Medida
de Performance Sistêmica, SP, que mede o ganho de performance do sistema. O
Objetivo Sistêmico é o objetivo de mais alto nível do sistema, e é definido nas
67
primeiras fases de modelagem de um sistema. A Medida de Performance
Sistêmica é o mecanismo para avaliar se o objetivo está sendo atingido.
Conseqüentemente, a Medida de Performance deriva diretamente do Objetivo
Sistêmico. Por exemplo, na técnica orientada a objetivos onde se utiliza o processo
recursivo de decomposição de um objetivo do problema principal em vários
objetivos de subproblemas, o Objetivo Sistêmico, SG, é igual ao Objetivo do
Problema Principal conforme ilustra a figura 30. A Medida de Performance
Sistêmica, SP, é normalmente uma variável numérica que permite avaliar se o
objetivo sistêmico está sendo atingido. Por exemplo, se o sistema multi-agente é
responsável por gerenciar uma fábrica, a Medida de Performance Sistêmica, SP,
pode ser o lucro gerado pela fábrica.
A abstração de objetivos é central neste método, pois permite a definição de
uma medida de performance para cada agente na seção 4.1.2, e a definição do
design das técnicas de machine learning na seção 4.1.3. Conseqüentemente, o
processo de decomposição dos objetivos em sub-objetivos é fundamental para este
processo. É importante frisar que essa modelagem de hierarquia de objetivos é
uma atividade comum nas metodologias orientadas a agentes. Entretanto, o
principal objetivo é detectar e modelar objetivos específicos de aprendizado. Os
objetivos funcionam como uma abstração para unificar conceitos de aprendizado
com conceitos básicos de sistemas multi-agente.
No processo de modelagem, os tipos de agentes são criados para conduzir os
objetivos da figura 30. A tabela 7 apresenta um exemplo de mapeamento entre
esses objetivos e tipos de agentes. Na próxima fase do método, alguns desses
agentes são selecionados para utilizar técnicas de machine learning.
68
Objetivo
Agente
Agente I
Agente II
4.1.2. Seleção do Agente & Definição do Objetivo do Aprendizado no
Agente
Essa fase seleciona os agentes definidos na tabela 7 que possuem planos
com alta probabilidade de melhorar a Medida de Performance Sistêmica, SP.
Conseqüentemente, esses planos precisam utilizar técnicas de machine learning
para melhorar a performance do sistema. O objetivo é estabelecer um Problema
de Aprendizado do Agente bem definido. Conseqüentemente, três características
são definidas: (i) Objetivo do Aprendizado, G; (ii) Medida de Performance, P, que
mede a melhora da performance no agente individualmente; e, (iii) uma
Experiência de Treinamento, E, que define o processo de aquisição do
conhecimento no agente com o aprendizado.
Por exemplo, o Agente I da tabela 7 pode ser um preditor de preços de
leilões de hotéis, e quanto melhor for a sua predição melhor será o desempenho do
sistema como um todo. Assim, esse agente deve ser selecionado para utilizar uma
técnica de machine learning. O Problema de Aprendizado do Agente para o
Preditor (Agente I) pode ser definido por:
(i)
G: Prever os preços de leilões de hotéis;
(ii)
P: O erro entre o preço previsto e o preço real; e
(iii)
E: Utilizar um histórico de preços dos leilões.
4.1.3. Design do Aprendizado no Agente
Um bom design do agente permite a inclusão ou reuso de várias técnicas de
machine learning e uma boa manutenção de código. O processo de maximizar a
performance do agente, normalmente, precisa de vários algoritmos diferentes para
69
que se possa escolher o de melhor performance. A figura 31 apresenta o digrama
de Classes (UML) do Preditor. Esse design utiliza um padrão de projeto orientado
a objetos para incluir machine learning em agentes de software (Sardinha et al.,
2004d). O design permite o teste e avaliação de vários algoritmos diferentes. O
padrão de projeto será apresentado em detalhes na seção 4.2.
As classes PricePredictorAgent e PricePredictorAgentIP possuem o código
dos serviços básicos do agent, tais como: tratamento de eventos, tratamento de
mensagens, etc.
70
A classe KnowledgeRepresentattion é um classe abstrata da estrutura de
dados do conhecimento do agente. O monitoramento da performance do agente é
codificado como uma classe abstrata chamada PerformanceMeasure. O algoritmo
de machine learning é uma classe abstrata chamada LearningAlgorithm. O
gerador de exemplos definido pela “experiência de treinamento” é modelado
como uma classe abstrata chamada TrainingExperience.
As
classes
concretas
ExponentialSmoothing,
ErrorEvaluation,
LMSLearning, e BuildTrainingExamples são classes que respectivamente
implementam
as
classes
abstratas
KnowledgeRepresentation,
PerformanceMeasure, LearningAlgorithm, e TrainingExperience.
Vários eventos podem disparar o processo de aprendizado (Mitchell, 1997),
tais como: execução de uma ação interna do agente, uma exceção levantada, a
troca de mensagens entre agentes, e eventos gerados pelo ambiente externo. As
classes concretas PricePredictorAgent e PricePredictorAgentIP utilizam a classe
LearningProperty para disparar esse processo de aprendizado.
4.1.4. Implementação Incremental & Avaliação de Performance
As decisões mais importantes na fase de implementação de uma técnica de
machine learning, nos agentes selecionados na seção 4.1.2, são: (i) a
representação do conhecimento; (ii) o algoritmo de aprendizado; (iii) o conjunto
de treinamento utilizado pelo algoritmo de aprendizado.
A primeira decisão determina exatamente o tipo de conhecimento
aprendido. Esse conhecimento pode ser modelado como uma função F que recebe
um estado S e determina uma ação A, ou F: S
A. Porém, aprender esse
conhecimento é muitas vezes uma tarefa muito difícil. Normalmente, a
complexidade desse conhecimento é reduzida para aprender apenas uma
representação aproximada do conhecimento, a aproximação da função F. Essa
representação do conhecimento aproximada pode ser uma função linear com
pesos, uma coleção de regras, uma rede neural, ou uma função polinomial
quadrática. Essa decisão tem prós e contras, pois uma representação do
conhecimento aproximado “expressiva”, muito próxima da função F, requer um
conjunto de treinamento grande na fase de treinamento.
71
O conhecimento do Preditor de Preços foi modelado como uma função
chamada NextPrice. Essa função recebe preços correntes A e gera uma preço
futuro N (NextPrice: A
N ). A representação aproximada da função NextPrice
utiliza uma função para calcular o preço futuro: PredictedPrice(n+1) =
*Price(n) + (1 - )*PredictedPrice(n), onde
é um numero entre 0 e 1; e n é o
n-ésimo instante. Esta formula é codificada na classe ExponentialSmoothing da
figura 31. O algoritmo de aprendizado Least Mean Squares (LMS) é utilizado para
adaptar o : (n) = (n-1) + ß*(Price(n-1)-PredictedPrice(n-1)), onde ß é a taxa
de aprendizado. Esse algoritmo é codificado na classe LMSLearning da figura 31.
Um conjunto de treinamento é preciso para que o agente aprenda, e a
seleção de um processo para criar esse conjunto é uma decisão muito importante.
O conjunto de treinamento pode ser obtido através de uma experiência direta ou
indireta. Na experiência direta, o engenheiro deve cuidadosamente selecionar o
melhor conjunto de treinamento que leve ao bom desempenho do conhecimento
aproximado. Na experiência indireta, o conhecimento aproximado deve sugerir
ações que levem a estados conhecidos que melhorem a performance do agente.
Porém,
esse
conhecimento
aproximado
deve
também
sugerir
estados
desconhecidos para que novas experiências sejam adquiridas. No longo prazo, a
exploração é muito importante para agentes que utilizam a experiência indireta. A
classe BuildTrainingExamples da figura 31 codifica a consulta ao banco de dados
com preços de leilões que o agente já participou. A classe ErrorEvaluation da
figura 31 implementa a avaliação da performance definida na seção 4.1.2.
4.1.4.1. Desenvolvimento Incremental, Teste e Integração de Agentes
Inteligentes
Ao invés de desenvolver o sistema multi-agente com todos os agentes
inteligentes em uma única fase, esta seção apresenta uma proposta incremental
para facilitar a integração e análise da performance dos agentes de software na
fase de implementação. A primeira versão do sistema multi-agente deve possuir
apenas de agentes simples ou reativos (Ferber, 1999) sem nenhuma técnica de
machine learning implementada. Essa primeira versão é importante para testar a
comunicação entre os agentes e a interação com o ambiente externo. A figura 32
apresenta o processo de integração dos agentes selecionados na seção 4.1.2. O
72
processo deve ser usado para melhorar a Medida de Performance Sistêmica
definida na seção 4.1.1.
O desenvolvimento incremental começa com a remoção do código de um
dos agentes selecionados na seção 4.1.2. O código do agente deve ser
implementado usando o design estabelecido na seção 4.1.3, e a fase de
treinamento deve vir logo em seguida, especialmente se foi escolhido a
experiência direta para o processo de criação do conjunto de treinamento. Antes
de reintegrar o agente no sistema, um teste individual é feito para testar a melhora
de performance usando a Medida de Performance definida na seção 4.1.2. Este
teste deve ser elaborado pelo engenheiro de sistema, e normalmente são
desenvolvidos pequenos módulos de software para gerar casos de testes. Erros de
codificação dos agentes “inteligentes” são encontrados nesta etapa.
Figura 32: O processo incremental de desenvolvimento.
A reintegração do agente no sistema é feita depois que os casos de testes
confirmam que o algoritmo de machine learning está funcionando. Esses casos de
testes não são capazes de garantir a melhora na Medida de Performance Sistêmica
definida na seção 4.1.1. Conseqüentemente, um teste de performance deve ser
feito com o sistema multi-agente e novo agente inteligente. É preciso ter um
simulador do ambiente para esta fase, e uma nova versão é dada para o sistema
caso a Medida de Performance Sistêmica indicar que houve uma melhora na
performance. Quando essa melhora de performance não é obtida, o engenheiro do
sistema deve tomar uma dessas duas opções: (i) Modificar o código ou o conjunto
73
de treinamento e efetuar todos os testes novamente, ou (ii) Remodelar o design do
agente conforme a figura 29 da seção 4.1.
Às vezes, os testes demonstram um ganho de performance no sistema, mas
o novo agente inteligente começa a utilizar muitos recursos computacionais do
sistema tais como CPU e memória. O sistema começa a apresentar lentidão no
processamento, e em muitos casos pode atrasar processos que necessitam de
agilidade. Recomenda-se a distribuição desse novo agente em uma outra CPU da
rede. Após confirmar a melhora na Medida de Performance Sistêmica, uma nova
versão é atribuída ao sistema. A remoção do código de outro agente selecionado
na seção 4.1.2 é feita para que se possa repetir o processo de testes e avaliação.
4.2. Agent Learning Pattern – Um Design para Incluir Aprendizado em
Agentes
Os conceitos de aprendizado devem ser modelados já na fase de design de
um agente de software. Em sistemas complexos e abertos, agentes precisam de
aprendizado para tomar decisões e se adaptar a mudanças para poder atingir os
seus objetivos. Esta seção apresenta um design orientado a objetos utilizando a
linguagem padrão de design patterns para guiar a inclusão de algoritmos de
machine learning.
4.2.1.Intenção
O principal objetivo do Agent Learning Pattern é incluir algoritmos de
machine learning em agentes com um design orientado a objetos. O design separa
conceitos importantes de aprendizado em agentes, tais como: representação do
conhecimento, algoritmo de machine learning, avaliador de performance, e
gerador de exemplos para o aprendizado.
4.2.2.Contexto
Em ambientes complexos e abertos como a Internet, o sistema baseado em
agentes deve ser capaz de se adaptar a situações desconhecidas e atingir o objetivo
sistêmico. Técnicas de aprendizado são cruciais para sistemas multi-agente em
74
tais ambientes, pois são algoritmos que fornecem estratégias conhecidas para a
implementação de agentes adaptáveis.
Mitchell (Mitchell, 1997) define machine learning como: “Diz-se que um
programa de computador aprende a partir de uma experiência E em relação a uma
classe de tarefas T e medida de performance P, se a sua performance nas tarefas T,
medido por P, melhora com a experiência E”. Conseqüentemente, esses são os
principais aspectos de design de aprendizado em agentes: (i) uma representação
do conhecimento adquirido pelo processo de aprendizado; (ii) o algoritmo de
aprendizado; (iii) um gerador de exemplos para criar a experiência para o
aprendizado; e (iv) o avaliador de performance para medir o processo de
aprendizado.
4.2.3.Problema
O design de machine learning em arquiteturas orientada a objetos não é
direto quando se precisa de um código reutilizável e de fácil manutenção. Como
projetar um agente que utiliza vários algoritmos de machine learning? Como
projetar diferentes geradores de exemplos para a técnica de aprendizado? Como
projetar um monitor para avaliar a performance do processo de aprendizado?
4.2.4.Forças
•
O design deve poder modelar qualquer técnica de machine learning
•
Os aspectos de design de aprendizado devem ser mapeados com simplicidade
para o design orientado a objetos
•
O design deve melhorar o reuso e manutenção do código
•
Algumas técnicas de aprendizado podem precisar em seu design de classes
complementares
•
Agentes de software devem ser capazes de utilizar o conhecimento adquirido
para se adaptar as constantes mudanças em ambientes complexos e abertos.
4.2.5.Solução
Agentes de Software implementados em frameworks orientados a objetos
(Telecom Italia-Jade, 2003; Sardinha et al., 2003a) normalmente utilizam herança
75
para implementar a abstração de agentes. A classe concreta Agent é um design OO
típico de agente, e deve herdar de uma superclasse do framework orientado a
objetos. Essa classe concreta deve implementar as funções básicas de um agente,
tais como: coletar informação do ambiente, tratar eventos, processar mensagens,
etc. A classe chamada KnowledgeRepresentation implementa a estrutura de dados
do conhecimento do agente. A Figura 33 ilustra um diagrama de classes de um
agente típico.
Figura 33: Um diagrama de Classes de um típico Agente.
A figura 34 mostra como incluir um algoritmo de machine learning, um
monitor de performance, e um gerador de exemplos. O monitor de performance é
codificado em uma classe chamada PerformanceMeasure, e é utilizado no
processo de aprendizado para garantir que o agente está atingindo o seu objetivo
de treinamento. O algoritmo de aprendizado é implementado na classe
LearningAlgorithm. Essa classe é responsável por modificar a classe
KnowledgeRepresentation após o processo de aprendizado. O gerador de
exemplos
para
o
TrainingExperience.
algoritmo
de
aprendizado
é
codificado
na
classe
76
4.2.6.Estrutura
Figura 34: O diagrama de Classes do Agent Learning Pattern.
O design pattern possui quarto participantes principais e dois participantes
clientes:
Participantes Principais:
LearningProperty
Define a classe que guarda as referencias para todas as
outras classes relacionadas com o aprendizado.
PerformanceMeasure
O algoritmo que implementa regras para avaliar a
performance do aprendizado. Um gerador de experimentos
pode ser implementado nesta classe.
LearningAlgorithm
O algoritmo de machine learning.
TrainingExperience
O algoritmo que implementa o gerador de exemplos para o
algoritmo de aprendizado
77
Participantes Clientes:
Agent
Define a classe que implementa os serviços básicos de um
agente, tais como: coletar informação do ambiente, tratar de
eventos, processar mensagens, etc.
KnowledgeRepresentation
A representação do conhecimento do agente.
4.2.7.Exemplo
O agente Preditor do exemplo da seção 4.1.2 utiliza o Agent Learning
Pattern para incluir a técnica de predição de preços. As técnicas Media Móvel
(Bowerman et al, 1993), Exponencial Suavizada (Bowerman et al, 1993), e PLS
(Milidiu
et
al.,
2005)
foram
implementadas
como
subclasses
de
LearningAlgorithm. A vantagem desse design é poder reutilizar todos as outras
classes mesmo mudando o algoritmo de aprendizado.
O teste de vários
algoritmos de aprendizado é um processo comum para poder escolher a técnica
com a melhor performance.
4.2.8.Dinâmica
A figura 35 apresenta a estrutura básica da dinâmica do Agent Learning
Pattern. Vários eventos podem disparar o processo de aprendizado (Mitchell,
1997), incluindo a execução interna de uma ação, um levantamento de uma
exceção, a troca de mensagens, ou através de informações coletadas no ambiente.
A classe concreta Agent deve acessar o LearningProperty sempre que o agente
quiser disparar o processo de aprendizado.
Por exemplo, o agente Preditor tem o principal objetivo de prever preços
futuros
baseado
na
seqüência
de
preços
passadas.
O
método
buildTrainingExperience() implementa o código que gera essa seqüência de
preços. Estes preços são então utilizados como exemplos de treinamento para o
algoritmo de aprendizado. O algoritmo de machine learning é codificado no
método train(), mas é chamado pelo método execute(). Esse mesmo método
também executa o método calculatePerformance() que é responsável por calcular
78
o erro de predição após o processo de aprendizado. Se o erro da predição for
aceitável, o método adaptKnowledge() altera os atributos do conhecimento do
agente.
Figura 35: O diagrama de Seqüência do Agent Learning Pattern.
4.2.9.Implementação
A figura 36 apresenta o diagrama de classes do Preditor utilizando o
ASYNC e o Agent Learning Pattern. As classes PricePredictorAgent e
PricePredictorAgentIP são classes especializada do framework ASYNC, e
implementam os serviços básicos do agente.
Figura 36: O diagrama de Classes do agente Preditor.
79
A classe ExponentialSmoothing implementa o conhecimento do agente, e
por isso tem o KnowledgeRepresentation como superclasse. O algoritmo de
treinamento é codificado na classe LMSLearning e a sua superclasse é o
LearningAlgorithm. O conjunto de treinamento para o algoritmo LMS (Mitchell,
1997) é gerado pela classe BuildTrainingExamples. A classe TrainingExperience
é superclasse de BuildTrainingExamples. A classe ErrorEvaluation, que herda de
PerformanceMeasure, implementa a avaliação de performance do algoritmo de
aprendizado.
Abaixo apresentamos alguns trechos de código Java para facilitar o
entendimento do design pattern. A classe LearningProperty é referenciado pela
classe PricePredictorAgent para acessar todos os componentes de aprendizado
neste design. O método startTrainingProcess() (linha 9) executa o processo de
geração do conjunto de treinamento (linha 10) e o algoritmo de machine learning
(linha 11). A classe armazena em seus atributos as referencias para todas as outras
classes relacionadas com o processo de aprendizado (linhas 3 até 6).
1. public class LearningProperty {
2.
private String task;
3.
private TrainingExperience trainingExperience;
4.
private LearningAlgorithm learningAlgorithm;
5.
private KnowledgeRepresentation knowledgeRepresentation;
6.
private PerformanceMeasure performanceMeasure;
7.
// Getters and Setters
8.
…
9.
public void startTrainingProcess(){
10.
trainingExperience.buildTrainingExperience();
11.
learningAlgorithm.execute(trainingExperience);
12.
}
13. }
O conhecimento desse agente foi modelado com uma função que
implementa a técnica Exponencial Suavizada (Bowerman et al., 1993). A classe
ExponentialSmoothing é uma especialização de KnowledgeRepresentation, e
implementa a função abaixo no método predictNextPrice() (linha 5):
PredictedAskPrice(n) = *AskPrice(n-1) + (1 - )*PredictedAskPrice(n-1)
onde
é um numero entre 0 e 1,
e, n é o n-ésimo jogo.
80
1. public class ExponentialSmoothing extends KnowledgeRepresentation {
2.
private double lastPrediction;
3.
private double alpha;
4.
private double price;
5.
public double predictNextPrice(){
6.
double nextPrice = price*alpha + (1-alpha)*lastPrediction;
7.
lastPrediction = nextPrice;
8.
return(nextPrice);
9.
}
10.
public void updateParameter(double alpha){
11.
this.alpha=alpha;
12.
}
13.
public void updatePrice(double price){
14.
this.price=price;
16.
}
17. }
A
classe
BuildTrainingExamples
é
uma
especialização
de
TrainingExperience, e implementa o processo de geração do conjunto de
treinamento. O método buildTrainingExperience() (linha 3) implementa uma
consulta no banco de dado com os preços de partidas antigas. Essa seqüência de
preços é armazenada no vetor askPriceHstory (linha 2).
1. public class BuildTrainingExamples extends TrainingExperience {
2.
public Vector askPriceHistory;
3.
public void buildTrainingExperience() {
4.
// JDBC code
5.
…
6.
}
7. }
O agente Preditor utiliza o algoritmo Least Mean Squares (LMS) (Mitchell,
1997) para adaptar o valor de alfa ( ) na classe ExponentialSmoothing. A classe
que implementa esse algoritmo é o LMSLearningAlgorithm, e possui o
LearningAlgorithm como superclasse. O método train() (linha 11) codifica o
algoritmo LMS.
1. public class LMSLearning extends LearningAlgorithm {
2.
private BuildTrainingExamples bte;
3.
private ExponentialSmoothing es;
4.
private double alpha;
5.
private double lastAlpha;
6.
private double beta;
7.
private double predictedPrice;
8.
private double lastAskPrice;
9.
es.updateParameter(20);
10.
alpha=20;
11.
public void train() {
12.
for(int i=0;i<bte.askPriceHistory.size();i++){
13.
lastAskPrice=
14.
((Double)bte.askPriceHistory.elementAt(i)).doubleValue();
81
15.
16.
17.
18.
19.
}
20. }
A
es.updatePrice(lastAskPrice);
predictedPrice = es.predictNextPrice();
lastAlpha=alpha;
alpha=lastAplha+(beta*(lastAskPrice-predictedPrice));
classe
ErrorEvaluation
é
uma
especialização
da
classe
PerformanceMeasure, e a classe LeaningProperty utiliza esta classe para calcular
o erro entre o preço previsto e o preço realizado. O método calculateError() (linha
5) implementa esse cálculo.
1. public class ErrorEvaluation extends PerformanceMeasure {
2.
private double predictedPrice;
3.
private double askPrice;
4.
private double error;
5.
public void calculateError() {
6.
error = Math.abs(predictedPrice-askPrice)/askPrice;
7.
}
8.
…
9. }
4.2.10.Conseqüências
Generalidade e Uniformidade. O Learning design pattern fornece uma solução
uniforme e geral para qualquer técnica de machine learning.
Reuso. O padrão apresenta um design modular para incluir aprendizado em
agentes de software que pode ser reutilizado e refinado para diferentes contextos e
aplicações.
Uma melhor Separação de Concerns. O padrão é totalmente separado de outros
concerns de agentes, tais como interação e autonomia.
Implementação Direta. O padrão implementa abstrações de aprendizado
diretamente para classes orientados a objetos.
4.2.11.Usos Conhecidos
Um design para incluir algoritmos de machine learning é apresentado no
capítulo 1 (seção 1.2.5) do livro Machine Learning (Mitchell, 1997). Quatro
módulos são apresentados nesse design: (i) Sistema de Performance – Módulo
para resolver uma dada tarefa de performance. Esse módulo recebe a instancia de
82
um novo problema como entrada e produz um trace da solução; (ii) O Crítico –
Esse módulo recebe como entrada um histórico ou trace da solução e gera
exemplos de treinamento; (iii) O Generalizador – Esse módulo recebe como
entrada exemplos de treinamento e produz uma hipótese; (iv) Gerador de
Experimentos – Esse módulo recebe como entrada uma hipótese corrente e gera
novos problemas para o Sistema de Performance explorar. No design do ASYNC
Agent Learning Pattern, o módulo O Crítico é codificado na classe
TrainingExperience. O módulo O Generalizador é codificado na classe
LearningAlgorithm, e este módulo é responsável por armazenar a hipótese
corrente
na
Experimentos
classe
e
KnowledgeRepresentation.
Sistema
de
Performance
O
são
módulo
Gerador
codificados
na
de
classe
PerformanceMeasure.
O Agent Learning Pattern foi utilizado em cinco implementações: (i) A
aplicação Bundles.com (Sardinha, 2001); (b) A aplicação Learn Agent Player
(Sardinha et al., 2003b); (c) A aplicação LearnAgents (Sardinha et al., 2004c;
Sardinha et al., 2005a); (d) Um sistema multi-agente para gerenciar submissões de
artigos e o processo de seleção em workshops e conferências (Garcia, 2004a); e, A
aplicação LearnAgentsSCM do capítulo 4.
4.2.12.Padrões Relacionados
Learning Aspect. (Garcia et al., 2004b) Uma mesma versão do Learning
Pattern pode ser implementada como um aspecto (Kiczales et al., 1997) e
melhorar a separação de concerns (Garcia, 2004). Um aspecto pode substituir a
classe LearningProperty, conectar pontos de execução (eventos) em diferentes
classes do agente,
e identificar quando o processo de aprendizado deve ser
acionado. Algumas vantagens adicionais podem ser encontradas: (i) Transparência
– O uso de aspectos torna o código mais elegante e poderoso para incluir
aprendizado em agentes de software de uma forma mais transparente (Garcia et
al., 2004b); A descrição de que classes precisam ser alteradas pelo aprendizado
está presente no aspecto e as classes monitoradas não precisam ser modificadas;
(ii) Facilidade de evolução – Conforme o sistema multi-agente evolui, novas
classes de agentes precisam ser monitoradas e alteradas pelo processo de
83
aprendizado; Os programadores do sistema precisam apenas adicionar novos
pointcuts ao aspecto para implementar novas funcionalidades.
84
5 A Aplicação LearnAgents
Este capítulo apresenta um sistema multi-agente para um complexo cenário
de procurement, onde os agentes compram e vendem bens em leilões simultâneos
para montar pacotes de viagens para seus clientes. O sistema é utilizado em
ambientes competitivos onde os participantes competem por um número limitado
de bens.
O LearnAgents (Sardinha et al., 2004c; Sardinha et al., 2005a) é um sistema
multi-agente para o comércio automatizado em mercados eletrônicos com leilões
simultâneos e assíncronos. O sistema é utilizado em ambientes competitivos onde
os participantes competem por um número limitado de bens. A sua arquitetura
define agentes que resolvem subproblemas do comércio eletrônico de bens, e
apresenta uma técnica para combinar todas essas soluções. Os subproblemas
típicos são predição de preços, planejamento de lances, alocação de bens,
negociação, entre outros. O LearnAgents utilizou o ambiente do Trading Agent
Competition (TAC) para testar o sistema desenvolvido, pois esse ambiente simula
um ambiente competitivo e permite mensurar a performance do sistema contra um
benchmark internacional.
O Trading Agent Competition é uma competição anual para incentivar a
pesquisa e o desenvolvimento de sistemas para comércio automatizado em
mercados eletrônicos. O TAC está em sua quinta edição e atrai trabalhos das
principais instituições de pesquisa americanas, européias, e asiáticas, tais como as
universidades de Harvard, Cornell, Brown, e Michigan. O TAC Classic (Wellman
et al., 2001) é uma competição onde os participantes são donos de uma agência de
viagem, e operam em um cenário complexo de procurement, ou compra de bens,
em leilões simultâneos. Os participantes são agentes de software, e na competição
não pode haver intervenção humana em hipótese alguma.
85
5.1.O TAC Classic
Os competidores no TAC Classic operam dentro de um mercado varejista. Todos
os agentes compram e vendem bens em leilões simultâneos para montar pacotes
de viagens para seus clientes. Esses bens podem ser passagens aéreas,
hospedagens em hotéis, e ingressos para museus, parques, ou luta livre. No inicio
de cada partida, cada agente recebe uma carteira de oito clientes com as suas
respectivas preferências. A pontuação de cada agente é calculada pela diferença
da utilidade dos pacotes montados e os custos dos bens adquiridos nos leilões,
refletindo o lucro total obtido pelo agente.
Figura 37: Ilustração do TAC Classic.
A figura 37 apresenta o ambiente do TAC Classic. Cada partida permite que
oito agentes negociem bens para seus clientes. Os agentes devem atender as
preferências de oito clientes, e os bens são comprados em vinte e oito leilões
simultâneos. As interdependências são claras nesse jogo, pois um cliente só pode
viajar se tiver uma passagem de ida e outra de volta. Além disso, cada cliente
precisa de diárias num hotel durante a sua estadia.
5.2. Edições Anteriores do TAC
A primeira versão do ambiente do jogo utilizado no TAC foi projetada em 2000
por um grupo do Laboratório de Inteligência Artificial da Universidade de
Michigan (Wellman et al., 2001). As versões dos anos seguintes passaram por
86
mudanças significativas para que o ambiente simulasse um mercado competitivo,
até que em 2003, o ambiente do TAC foi re-projetado pelo Laboratório de
Sistemas Inteligentes no Instituto Sueco de Ciência da Computação (SICS) e
poucas mudanças foram feitas desde então.
A primeira edição do TAC foi sediada na cidade de Boston, Massachusetts,
EUA, em Julho de 2000 dentro da IV International Conference on Multiagent
System (ICMAS-00). Devido às regras, a estratégia predominante nos agentes
esperava comprar os bens no final da partida e utilizava lances altos com valores
iguais ao valor marginal do bem. Por esta razão, uma preocupação central dos
agentes que participaram nesta competição estava na resolução do problema de
alocação dos bens adquiridos de acordo com as preferências dos clientes. Este
problema de otimização é NP-Completo (Greenwald, 2003), e foi incorporado às
funcionalidades do TAC no segundo ano. A tabela 8 resume os resultados obtidos
da TAC’00. A pontuação é uma média dos resultados das várias partidas na
rodada final. A estratégia utilizada pelo o ATTac (Stone et al., 2001; Strone et al.,
2002), vencedor desta edição, é baseada em um modelo de programação inteira.
Posição
1
2
3
4
5
6
7
8
Agente
ATTac
RoxyBot
aster
umbctac1
ALTA
m_rajatish
RiskPro
T1
Pontuação Média
3398.26
3283.24
3068.34
3050.99
2198.01
1872.71
1569.91
1167.40
A segunda versão do TAC, em outubro de 2001, teve a sua realização dentro
da Third ACM Conference on Electronic Commerce (EC’01), em Tampa, Flórida.
As regras foram modificadas para que os agentes pudessem se beneficiar da
compra de bens no início do jogo. A tabela 9 apresenta o resultado final da
competição. O vencedor LivingAgents (Klaus, 2001) utiliza um sistema multi
agente com várias heurísticas simples, e se aproveita da mudança nas regras para
tomar a maioria das decisões bem no início de cada jogo. Esta estratégia permite
uma economia considerável na compra das passagens aéreas. Além disso, o
LivingAgents utiliza uma média dos preços de fechamento dos leilões dos hotéis
87
para calcular preços futuros, e assim poder calcular os lucros da melhor alocação
por cliente.
Posição
1
2
3
4
5
6
7
8
Agente
livingagents
ATTac
Whitebear
Urlaub01
Retsina
SouthamptonTAC
CaiserSose
TacsMan
Pontuação Média
3670.0
3621.6
3513.2
3421.2
3351.8
3253.5
3074.1
2859.3
As finais da terceira edição do TAC foram realizadas em julho de 2002 na
cidade de Edmonton no Canadá. A competição foi co-localizada com o Eighteenth
National Conference on Artificial Intelligence (AAAI-02). As regras do TAC’01
para o TAC’02 permaneceram as mesmas, o que já demonstrava um certo grau de
amadurecimento da competição. Além disso, a comunidade de pesquisa também
demonstrava uma expansão, pois mais participantes foram inscritos neste ano. A
tabela 10 apresenta os resultados do TAC’02. O agente Whitebear (Vetsikas et al.,
2003) foi o vencedor desta edição, e apresentou uma técnica gulosa para o cálculo
de alocação de bens junto com uma estratégia de lances “parciais”, onde os lances
são considerados independentes um dos outros. Esse agente calcula primeiro os
bens a serem comprados usando um algoritmo guloso, e demonstra empiricamente
que as alocações encontradas estão sempre próximas da alocação ótima. Depois, o
agente decide o valor do lance para cada bem utilizando uma estratégia de lances
adaptativa que não ultrapassa o valor marginal do bem.
88
Posição
1
2
3
4
5
6
7
8
Agente
Whitebear
SouthamptonTAC
Thalis
UMBCTAC
Walverine
Livingagents
kavayaH
Cuhk
Pontuação Média
3412.78
3385.46
3246.27
3235.56
3209.52
3180.89
3099.44
3068.77
A quarta edição do TAC foi realizada dentro da Eighteenth International
Joint Conference on Artificial Intelligence (IJCAI-03) em agosto de 2003. A
tabela 11 apresenta os resultados desta edição. Neste mesmo ano, uma nova
modalidade da competição foi criada para atender o cenário de produção e venda
de produtos. Essa modalidade se chama TAC Supply Chain Management. Os
agentes competidores agora precisam programar a compra de matéria prima, a
produção e a distribuição para poder atender a demanda dos clientes.
Posição
1
2
3
4
5
6
7
8
9
Agente
ATTac01
PackaTAC
Whitebear
Thalis
UMBCTAC
NNN
Walverine
RoxyBot
Zepp
Pontuação Média
3199.77
3162.59
3141.74
3132.61
3108.24
3070.94
3005.30
2799.02
1714.38
5.3.A arquitetura do LearnAgents
Parte do sucesso do LearnAgents advém do uso da tecnologia de agentes,
pois propiciam um novo paradigma para a concepção de sistemas inteligentes para
atuarem em complexos ambientes distribuídos, competitivos e abertos. Uma
técnica interessante para modelar um problema computacionalmente difícil com o
paradigma de agentes é dividir esse mesmo problema em subproblemas mais
simples. Assim, cada agente se torna responsável por um ou mais desses
89
subproblemas. A figura 38 apresenta a arquitetura do LearnAgents, e esta seção
descreve a modelagem do sistema multi-agente usando uma linguagem de
modelagem chamada ANote (Choren, 2002). Essa arquitetura utiliza um design
semelhante ao sistema multi-agente SIMPLE (Milidiu et al, 2003a; Milidiu et al,
2003b; Milidiu et al, 2003c), porém com mais agentes, algoritmos de machine
learning diferentes, e uma performance superior (Sardinha et al., 2004a).
Figura 38: A arquitetura do LearnAgents.
Todos os nossos projetos de software utilizam uma técnica orientada a
objetivos para a fase de requisitos. Esta fase utiliza o processo recursivo de
decomposição de um objetivo do problema principal em vários objetivos de
subproblemas mais simples. No caso do LearnAgents, esse processo recursivo
definiu todos os objetivos dos subproblemas relacionados com o comércio de bens
em um mercado competitivo.
O objetivo maior desse sistema era comprar pacotes de viagens para os
clientes e obter o maior lucro possível. Como o mercado era competitivo, a
negociação foi identificada como um dos objetivos evidentes para o processo de
compra dos pacotes de viagens. Além disso, para obter o maior lucro possível é
preciso possuir uma base de conhecimento do mercado para auxiliar o processo de
negociação. A figura 39 mostra esse processo de decomposição dos objetivos.
90
A base de conhecimento deve possuir: (i) os preços correntes dos leilões objetivo Monitorar Informações do Mercado; (ii) as preferências dos clientes -
objetivo Classificar as Preferências dos Clientes; (iii) as predições dos preços dos
leilões - objetivo Prever próximo Preços dos Leilões; e, (iii) alocações de bens
para os clientes utilizando a informação armazenada nesta base - objetivo Calcular
as melhores Alocações.
O processo de negociação requer: (i) um cenário representado pelas
alocações que permita negociações de bens com alta lucratividade e com o
mínimo de risco - objetivo Classificar as melhores Alocações; (ii) a escolha do
valor do lance para cada bem desejado - objetivo Criar Lances para Ordens; e, (iii)
envio de lances para os leilões de bens - objetivo Enviar Lances para Leilões.
sejam capazes de conduzir os objetivos da figura 39. Essa criação começa com
processo de relacionamento de todos os objetivos de nível mais baixo e com tipos
de agentes. A tabela 12 faz um mapeamento entre esses objetivos e tipos de
91
Goal
Agent
Monitor Market Information
Hotel Sensor, Flight Sensor, Ticket
Sensor
Classify Customer Information
Hotel Sensor
Predict Next Prices of Auctions
Price Predictor
Calculate Best Allocations
Allocation Master, Allocation Slave
Classify Best Allocations
Ordering
Create Bidding Orders
Ordering
Send Bids in Auctions
Hotel Negotiator, Flight Negotiator,
Ticket Negotiator
Figura 40: Arquitetura do LearnAgents.
de como cada agente deverá atingir seus objetivos. Segue abaixo, uma descrição
resumida dos agentes criados e seus cenários:
Os Sensores dos Leilões (Hotel, Vôo, e Ticket) – Esses agentes são
responsáveis por atualizar a base de conhecimento com os preços correntes dos
leilões, e enviar mensagens para outros agentes sobre eventos importantes do
ambiente externo. A figura 41 apresenta o digrama de cenário dos Sensores de
leilões.
92
Figura 41: Diagrama de cenário dos Sensores.
Preditores – Através de uma série histórica dos preços de vôos e hotéis, os
Preditores são capazes de prever para que valor o preço do leilão deve caminhar.
A figura 42 apresenta o digrama de cenário dos Preditores.
Figura 42: Diagrama de cenário dos Preditores.
Alocador Mestre e Escravos – O principal objetivo dos Alocadores é
calcular vários cenários diferentes. Esses agentes utilizam os preços previstos e
correntes para montar cenários diferentes. Todas as decisões de bens a serem
adquiridos são baseadas nesses cenários. A figura 43 apresenta o digrama de
cenário dos Alocadores.
93
Figura 43: Diagrama de cenário dos Alocadores.
Ordenador – O Ordenador assume um papel de chefe dos negociadores, e
utiliza os cenários calculados pelos Alocadores para tomar as suas decisões. De
minuto em minuto, os Negociadores recebem ordens de compras com diretivas
básicas: quantos bens devem ser comprados, e o valor máximo do lance que pode
ser dado para um determinado bem. A figura 44 apresenta o digrama de cenário
do Ordenador.
94
Negociadores – Para cada leilão há um Negociador especializado na
compra de um tipo bem. Os Negociadores só começam a operar nos leilões depois
que recebem as ordens de compra do Ordenador. A cada minuto, as ordens podem
ser alteradas se houver alguma mudança de estratégia. Os negociadores têm o
objetivo de comprar os bens seguindo as diretivas determinadas pelo Ordenador,
porém toda transação deve ser feita pelo menor preço possível. A figura 45
apresenta o digrama de cenário dos Negociadores.
Figura 45: Diagrama de cenário dos Negociadores.
Monitor – Esse agente é responsável por armazenar informações da base de
conhecimento em um banco de dados. Esses dados são utilizados por uma
ferramenta da CA (Computer Associates) chamada Forest and Trees para
monitorar a performance de cada agente individualmente e o sistema multi-agente
como um todo. Uma tela da ferramenta de monitoração pode ser vista na figura
46.
95
de interação. Esse diagrama deixa explicito a comunicação entre os agentes, e
permite uma visão dinâmica do sistema.
Figura 47: Diagrama do Interação do LearnAgents.
Na figura 47, o Sensor de Hotel recebe um evento do ambiente com novas
cotações dos leilões de hotéis. O Sensor atualiza a base de conhecimento e envia
uma mensagem para o Preditor informando que os preços foram atualizados. O
Preditor calcula as novas previsões de preços dos leilões, e armazenas essas
predições na base de conhecimento.
96
Os Alocadores calculam os diferentes cenários baseados nos preços
correntes e previstos. Esses cenários são alocações de bens de turismo, e eles são
calculados com um solver de programação inteira. O Alocador Mestre envia uma
mensagem para o Ordenador após esse calculo dos cenários.
O Ordenador recebe a mensagem e decide a quantidade necessária de bens
para atender a demanda dos clientes. Além disso, o Ordenador calcula o valor
máximo de um lance para cada bem a ser comprado. Os Negociadores recebem a
mensagem do Ordenador com os pedidos de compra e o valor máximo do lance.
Os Negociadores possuem o objetivo de comprar esses bens pelo menor preço
possível, sem exceder um lance maior do que o máximo definido pelo Ordenador.
5.4.O TAC Classic 2004 e Resultados
O TAC Classic 2004 foi a primeira participação do LearnAgents na
competição. O TAC foi escolhido como ambiente para testar a arquitetura, pois
apresenta características de um mercado competitivo e permite avaliar a
performance do LearnAgents em relação a outros sistemas para comércio
eletrônico.
Os participantes cadastram seus agentes de software no torneio pela
Internet. Esses agentes de software passam então a disputar autonomamente as
partidas via Internet, sem qualquer intervenção humana. A competição de 2004
reuniu os representantes das equipes em Nova York, dentro do Third International
Joint Conference on Autonomous Agents and Multi Agent Systems.
A competição foi disputada em três etapas. Na primeira delas, o Qualifying
Rounds, com os agentes conectados via Internet durante duas semanas, 24 horas
por dia, o LearnAgents ficou na quinta colocação dentre os 14 participantes. Na
rodada seguinte, o Seeding Rounds, o agente ficou boa parte do tempo disputando
a quarta posição. Porém, devido a uma queda na madrugada do link de
comunicação com a Internet, ele foi penalizado e caiu para a sétima posição.
Mesmo assim, o LearnAgents ainda conseguiu recuperar uma posição e encerrar
essa rodada em sexto lugar.
Na semifinal, o LearnAgents subiu então para a quarta posição. Para a final,
foram selecionados apenas os 8 melhores competidores, que disputaram 35
partidas sucessivas. O LearnAgents consegui então confirmar sua robustez em
97
ambientes fortemente competitivos e assegurar a terceira posição. A frente do
LearnAgents ficaram os agentes experientes Whitebear (Vetsikas et al., 2003) da
Cornell University, seguido do Walverine (Cheng et al., 2003) da University of
Michigan. Em sua quarta participação, o Whitebear consegui o bicampeonato, e o
Walverine foi desenvolvido pelos criadores da competição.
Os resultados da tabela 13 mostram um grande equilíbrio entre os finalistas,
e isso comprova a existência de muitas soluções robustas para esse jogo de varejo
altamente competitivo. Em todas 35 partidas disputadas o LearnAgents não obteve
qualquer resultado negativo, como mostra o gráfico da figura 48. Isso evidencia a
boa performance da nossa estratégia em ambientes competitivos de varejo, pois é
capaz de garantir lucros significativos e automatizar todos os processos de
decisão.
Posição
1
2
3
4
5
6
7
8
Agente
Whitebear04
Walverine
LearnAgents
SICS02
NNN
UMTac-04
Agent@CSE
RoxyBot
Pontuação Média
4122.11
3848.97
3736.62
3708.24
3665.97
3281.43
3262.51
2015.02
98
5.5.Os Algoritmos utilizados nos Agentes do LearnAgents
Esta seção apresenta os principais algoritmos utilizados no Preditor,
Alocadores, Ordenador, e Negociador de Hotel. O restante dos agentes utiliza uma
lógica simples que é muito parecida com o código apresentado nos cenários da
seção 5.3.
5.5.1.Preditor
O agente Preditor utiliza uma técnica chamada Média Móvel (Bowerman et
al. 1993) para calcular os preços dos leilões de hotéis. A técnica Exponencial
Suavizada (Bowerman et al. 1993) também foi testada para calcular os preços dos
leilões de hotéis, mas apresentou um erro de predição maior. Conseqüentemente, a
fórmula da Média Móvel utilizada para prever os preços de cada bem é dada por:
onde:
é a série histórica dos preços de cada bem (N
termos)
é a seqüência de n preços previstos (janela de
tamanho n)
O Preditor utiliza também uma técnica chamada Máxima Verossimilhança
(Mitchell, 1997) para prever uma variável aleatória escondida x (de uma
distribuição uniforme entre [-10,30]) escolhida para cada um dos oito leilões de
vôo. O preço inicial de cada leilão de vôo é escolhido a partir de uma distribuição
uniforme entre [250,400]. O processo que atualiza esse preço é um passeio
aleatório, e é perturbado a cada 10 segundos por um valor escolhido de uma
distribuição uniforme:
[-10, x(t)] if x(t) > 0,
[x(t), 10] if x(t) < 0,
[-10, 10] if x(t) = 0,
onde x(t) = 10 + (t / 9:00)*(x - 10)
99
Os preços dos leilões de vôos são atualizados a cada 10 segundos, porém o
Sensor de Vôo recebe essas cotações a cada 30 segundos, após três atualizações.
A variável aleatória x é prevista utilizando a máxima verossimilhança:
arg max
P (yt + yt-10 + yt-20 = s | x)
O valor de yt é o incremento do preço no tempo t, e s é a diferença entre o
preço atual da cotação e a última cotação recebida a 30 segundos atrás. A predição
do preço futuro é calculada utilizando o valor esperado E(quote) utilizando a
variável x e o processo descrito acima. A figura 49 apresenta a predição do leilão
de vôo de chegada do dia 3 no jogo 6091 (Final do TAC Classic de 2004).
5.5.2.Alocador
O Alocador utiliza um modelo de programação inteira para criar diferentes
cenários. Esse modelo recebe como entrada as preferências dos clientes, os preços
correntes, os preços previstos, e os bens já adquiridos. O solver não é executado
apenas para encontrar a melhor alocação de bens, mas o maior número de boas
alocações geradas em 25 segundos.
100
Cada alocação define o número de bens por cliente que devem ser
compradas em cada leilão com a sua respectiva utilidade. A função objetivo é
descrito pela equação abaixo:
8
Utility (client ) −
client =1
8
Cost (client ) − OtherCosts − Homogeneit yFunc
client =1
A utilidade do cliente é medida em dólares, e precisa ser um pacote de
viagem viável e um pacote de entretenimento viável. A utilidade é medida pela
equação:
Utility(client) = 1000 - travel_penalty + hotel_bonus + fun_bonus
Um pacote de viagem é viável se cada cliente tiver uma passagem aérea
para chegar e sair de TACTown, e diárias em hotéis entre o dia de chegada e o dia
de saída. Além disso, o cliente não pode trocar de tipo de hotel na viagem, e só
existem dois tipos de hotéis nesse jogo, o hotel BOM e o hotel RUIM. O agente
pode ser penalizado pelo pacote de viagem se o pacote é viável, mas não atende
exatamente a preferência do cliente. Esse cálculo da penalidade é dado pela
fórmula:
travel_penalty = 100*( |AA - PA| + |AD - PD|)
onde,
AA é o dia preferido do cliente para chegar em TACTown,
PA é o dia preferido do cliente para deixar TACTown
AD é a data que o cliente chega em TACTown,
PD é a data que o cliente deixa TACTown.
O bônus de hotel é dado para cada agente que conseguir enviar um cliente
para TACTown e hospedá-lo no hotel BOM. O cálculo é feito pela seguinte
fórmula:
hotel_bonus = GHI * HP
onde,
101
GHI é um indicador de hotel BOM (assume o valor 1 se diárias são do hotel
BOM, ou assume o valor 0 se diárias são do hotel RUIM),
HP é um premio recebido em utilidade.
O bônus para os ingressos de entretenimento é dado para o agente que
consegue comprar um ou mais ingressos num pacote de viagem viável. Um pacote
de entretenimento para cada cliente é considerado viável se houver apenas um
ingresso por dia, e o dia desses ingressos coincide com as datas da estadia. O
cálculo é feito pela seguinte fórmula:
fun_bonus = AWI*AW + API*AP + MUI * MU
onde,
AWI, API, e MUI são indicadores de ingressos (valor {0,1}) para cada tipo
(Alligator wrestling, Amusement park, Museum), e AW, AP and MU são
prêmios em utilidade recebido para cada tipo de ingresso.
O Cost(client) é a soma dos gastos por cliente com a compra das passagens
de ida e volta, diárias em hotéis, e ingressos. O OtherCosts é a soma dos gastos de
todos os bens não utilizados pelos clientes, perdas e penalidades. O
HomogeneityFunc é uma função que inclui uma penalidade extra na função
objetivo, e é dado pela seguinte equação:
4
Penalty ( hotelType , day ).ExtraRoom ( hotelType , day )
day =1
O Penalty(hotelType,day) é uma penalidade extra dada para cada diária
excedente de um dado tipo (0 = Bad Hotel, 1 = Good Hotel) e dia (1 to 4) no caso
de hotel(hotelType,day) > maxHotel(hotelType,day).
O hotel(hotelType,day) é o numero de diárias de hotéis alocadas de um dado
tipo e um dado dia, e maxHotel(hotelType,day) é um parâmetro que define um
número máximo de hotéis que não serão penalizados. Conseqüentemente:
ExtraRoom(hotelType,day)=0,
se hotel(hotelType,day) < maxHotel(hotelType,day)
102
ou
ExtraRoom(hotelType,day)=hotel(hotelType,day)-maxHotel(hotelType,day),
se hotel(hotelType,day) > maxHotel(hotelType,day)
O HomogeneityFunc modela o risco de acumular muitas diárias para um
dado dia e tipo de hotel. Essa função penaliza as alocações que possuem muitas
diárias de hotéis de um mesmo tipo e em um mesmo dia.
O Alocador também é responsável por calcular o valor máximo do lance que
pode ser dado para um determinado bem. O Ordenador decide os bens a serem
comprados, e pede para o Alocador calcular esse valor máximo do lance para cada
bem escolhido. Esse valor máximo será utilizado pelos negociadores como um
teto do lance na negociação. Seja G*(g) o resultado da função objetivo da
alocação ótima assumindo que o bem g está dentro desta alocação. Para calcular o
valor máximo do lance, o solver é executado com o preço de g igual a p’g =
e
gera o resultado G*(g)’. O valor máximo do lance para o bem g é dado pela
equação G*(g) - G*(g)’.
5.5.3.Ordenador
A alocação ótima e as alocações sub-ótimas são calculadas uma vez por
minuto pelos agentes Alocadores. O Ordenador executa uma heurística baseada
nessas alocações para definir os bens que devem ser comprados. Para cada cliente,
uma alocação contém as seguintes informações: (i) um data de chegada AA, (ii)
uma data de saída AD, (iii) um tipo de hotel hotelType, e (iv) um pacote de
ingressos de entretenimento e(day).
Seja G* a alocação ótima e G(n) as alocações sub-ótimas, onde n é o índice
das alocações sub-ótimas geradas e n assume um valor entre 1 ... N. O Ordenador
envia ordens de compra para os negociadores baseados nas seguintes regras:
i. Enviar ordem de compra para passagem de ida no dia AA para o cliente
baseado na alocação G*, se e somente se as duas condições abaixo são
verdadeiras:
a. a > p.N, onde a é o número de vezes que a passagem de ida no dia
AA aparece em G(n), e p é uma taxa.
103
b. O preço previsto indica que o preço do leilão está subindo.
ii. Enviar ordem de compra para passagem de volta no dia DD para o cliente
baseado na alocação G*, se e somente se as duas condições abaixo são
verdadeiras:
a. b > p.N, onde b é o número de vezes que a passagem de volta no
dia DD aparece em G(n), e p é uma taxa.
b. O preço previsto indica que o preço do leilão está subindo.
iii. Enviar ordem de compra para diária do tipo hotelType no dia day em G*
para cada cliente.
iv. Enviar ordem de compra para ingressos de entretenimento do tipo e(day)
em G* para cada cliente.
Essa heurística utiliza G* e G(n) para definir os bens que devem ser
comprados considerando a incerteza do mercado. Se uma passagem aérea em G*
não está presente em pelo menos p por cento das alocações em G(n), então a
decisão de compra é postergada para o próximo minuto quando os Alocadores recalculam as alocações novamente.
5.5.4.Negociador de Hotel
O Negociador de Hotel utiliza a técnica Minimax (Russell et al., 1995) e
aprendizado por reforço (Mitchell, 1997) para calcular lances de leilões de hotéis.
O Minimax é uma técnica de busca para dois jogadores, utilizada pelo Negociador
de Hotel para encontrar lances ótimos. O lance ótimo é aquele que permite a
compra do bem desejado pelo menor preço possível. Há dois jogadores no
Minimax: o MAX e o MIN. O Negociador de Hotel é modelado como o jogador
MAX, e a resposta do mercado é modelada como o jogador MIN. Uma busca em
profundidade é feita a partir de uma árvore onde a raíz é a posição corrente do
jogo. As folhas dessa árvore são avaliadas pela ótica do jogador MAX, e os
valores dos nós internos são atribuídos de baixo para cima com essas avaliações.
As folhas de o nível minimizar são preenchidas com o menor valor de todos os
seus nós filhos, e o nível de maximizar são preenchidos com o maior valor de
todos os nós filhos. Essa técnica é utilizada como uma técnica de poda chamada
Alpha-Beta (Russell et al., 1995).
104
Para construir essa árvore de decisão no Negociador de Hotel, os estados de
cada nó foram modelados com as seguintes informações:
i. AskPrice: o preço corrente do leilão;
ii. LastAskPrice: o preço do leilão do ultimo minuto;
iii. deltaAskPrice = AskPrice – LastAskPrice;
iv. Gama: uma constante;
v. Bid: o valor atual do ultimo lance;
vi. LastBid: o valor do lance enviado no ultimo minuto;
vii. t : o tempo do jogo.
A cada nó de um nível de maximizar, os nós filhos são atualizados com as
seguintes alternativas:
(i)
Bid = LastBid + 0.5*Gama*deltaAskPrice;
(ii)
Bid = LastBid + 2*Gama*deltaAskPrice;
(iii)
Bid = LastBid + 5*Gama*deltaAskPrice.
O valor de LastBid é atualizado com o último valor de Bid. Os valores de
AskPrice, LastAskPrice, Gama, e do tempo t nesses filhos de MAX são mantidos
com o mesmo valor. A figura 51 a ilustra esse processo de atualização.
105
Figura 51: A árvore Minimax (nível Maximizar) no Negociador de Hotel.
A cada nó de um nível de minimizar, os nós filhos são atualizados com as
seguintes informações:
(i)
AskPrice = AskPrice + 0.5*Gama*deltaAskPrice;
(ii)
AskPrice = AskPrice + 2*Gama*deltaAskPrice;
(iii)
AskPrice = AskPrice + 5*Gama*deltaAskPrice.
O valor de LastAskPrice é atualizado com o último valor de AskPrice. Os
valores de Bid, LastBid, e Gama nos filhos de MIN são mantidos com o mesmo
valor. O tempo t é incrementado com um minuto nesta etapa. A figura 52 ilustra
esse processo de atualização.
Figura 52: A árvore Minimax (nível Minimizar).
106
O Negociador de Hotel utiliza uma função avaliação na árvore Minimax
para avaliar estados intermediários. Essa função utiliza uma rede neural chamada
Perceptron (Mitchell, 1997) com um neurônio artificial. As entradas do
Perceptron são os estados de um nó da árvore Minimax, e a saída é um valor entre
0 e 1. Os estados avaliados com valores próximo de 1 são considerados bons
estados, e conseqüentemente representam que o lance enviado consegue adquirir o
bem desejado. O objetivo do Negociador de Hotel é adaptar os pesos do
Perceptron para que esses estados finais representem lances ótimos.
O maior problema é configurar os pesos do Perceptron para que a avaliação
leve apenas a casos de sucesso e onde o lance é ótimo. A técnica de aprendizado
utiliza reforço combinado com a regra do Perceptron para atualizar os pesos. Ao
invés do aprendizado supervisionado (Russell et al. 1995) onde um conjunto de
treinamento é apresentado ao Perceptron. O Negociador mantém um histórico de
todos os nós por onde passou para implementar essa estratégia. A regra do
Perceptron é utilizada em todos esses nós armazenados assim que o leilão fecha:
wi = wi + . ( y(t) – d(t) ) . xi (Regra do Perceptron)
onde:
wi é o i-ésimo peso do Perceptron;
xi é a i-ésima entrada do estado da arvore Minimax;
y(t) é o valor atual da saída da função avaliação;
d(t) é o valor esperado da saída da função avaliação que é calculado com o
aprendizado por reforço;
é a taxa de aprendizado.
O primeiro nó utilizado pela regra do Perceptron é a folha, que representa o
último lance enviado antes do leilão fechar. O Negociador atinge um estado bem
sucedido, se todos os bens são comprados conforme a ordem de compra enviada
pelo Ordenador e a diferença entre o valor do lance e o preço corrente do bem no
leilão não é superior a uma constante k. O estado considerado bem sucedido
recebe um d(t) = 1. Em todos os outros casos d(t) = 0.
107
Todos os estados por onde o Negociador passou também serão utilizados
pela regra do Perceptron num sentido de baixo para cima na árvore. A regra do
aprendizado por reforço usada para calcular d(t) é igual a:
d(t- t) = d(t) + ß. (reward(t) - d(t)),
No caso do nó folha ser considerado bem sucedido.
d(t- t) = d(t) + ß.d(t),
No caso do nó folha NÃO ser considerado bem sucedido
onde:
d(t) é o valor esperado de saída no instante t;
ß é a taxa do aprendizado por reforço;
reward(t) = 1 – ( Bid(t) – AskPrice(t) ) / AskPrice(t) é a recompense obtida
no instante t.
Total number of
requested hotel goods
from the Ordering Agent
Total number of hotel
goods acquired by
Hotel Negotiators
Percentage (%)
1597
1515
94,87
Tabela 14: Performance do Negociador de Hotel nas finais do TAC Classic de 2004.
O Ordenador envia ordens de compra para cada um dos Negociadores de
leilão de hotel. Essas ordens de compra possuem o numero de bens desejados e
seu respectivo lance máximo que pode ser dado. A tabela 14 apresenta a
performance da técnica implementada no Negociador de Hotel para o TAC
Classic 2004. Ordenador enviou 1597 ordens de compra nas 35 partidas da final, e
o Negociador foi bem sucedido em 94,87% dessas ordens.
108
Figura 53: Gráfico dos lances enviados para leilão pelo Negociador de Hotel.
Figura 53 apresenta um gráfico com os lances enviados para o leilão do
hotel BOM do dia 1 no jogo 6089 (finais do TAC Classic 2004). Os lances
enviados estão sempre próximos do preço valor do bem. Isso garante que o bem
esteja sendo adquirido. Porém, o lance enviado não pode exceder o valor do lance
máximo definido pelo Ordenador.
LearnAgents
Na primeira fase do MAS-School, o engenheiro de software deve definir
dois elementos centrais que estão relacionados com aprendizado: (i) Objetivo
Sistêmico, SG, e (ii) Medida de Performance Sistêmica, SP, que mede o ganho de
performance do sistema. No LearnAgents, o Objetivo Sistêmico foi definido
utilizando a técnica orientada a objetivos da figura 39. Conseqüentemente, (i) SG:
comprar pacotes de viagens para os clientes e obter o maior lucro possível, e (ii)
SP: A pontuação média representando o lucro médio obtido do sistema no
ambiente TAC.
Na segunda fase, os tipos de agentes definidos na tabela 12 são selecionados
para utilizar técnicas de machine learning. O objetivo é estabelecer um Problema
109
conhecimento no agente com o aprendizado. No LearnAgents, o Preditor de
Preços foi um dos agentes selecionados para utilizar um técnica de machine
learning. O Problema de Aprendizado do Agente para o Preditor pode ser definido
por:
(iv)
G: Prever os preços de leilões de hotéis;
(v)
P: O erro entre o preço previsto e o preço real; e
(vi)
E: Utilizar um histórico de preços dos leilões.
Na terceira fase, um bom design do agente é criado para permitir a inclusão
ou reuso de várias técnicas de machine learning. Além disso, o design deve
proporcionar uma boa manutenção de código. A figura 54 apresenta o digrama de
Classes (UML) do Preditor de Preços utilizando o padrão de projeto orientado a
objetos da seção 4.2.
110
machine learning, nos agentes selecionados são: (i) a representação do
conhecimento; (ii) o algoritmo de aprendizado; (iii) o conjunto de treinamento
utilizado pelo algoritmo de aprendizado. O conhecimento do Preditor de Preços
foi modelado como uma função chamada NextAskPrice. Essa função recebe um
preço do leilão A e gera uma preço futuro do leilão N (NextAskPrice: A
N ). A
representação aproximada da função NextAskPrice utiliza uma função para
calcular o preço futuro do leilão: PredictedAskPrice(n) = *AskPrice(n-1) + (1 )*PredictedAskPrice(n-1), onde
é um numero entre 0 e 1; e n é o n-ésimo jogo.
Esta formula é codificada na classe ExponentialSmoothing da figura 54. O
algoritmo de aprendizado Least Mean Squares (LMS) é utilizado para adaptar o :
(n) = (n-1) + ß*(AskPrice(n-1)-PredictedAskPrice(n-1)), onde ß é a taxa de
aprendizado. Esse algoritmo é codificado na classe LMSLearning da figura 54. A
classe BuildTrainingExamples da figura 54 codifica a consulta ao banco de dados
com preços de leilões que o agente já participou. A classe ErrorEvaluation da
figura 54 implementa a avaliação da performance.
inteligentes em uma única fase, a fase de implementação utiliza uma proposta
incremental para facilitar a integração e análise da performance dos agentes. A
primeira versão do LearnAgents foi desenvolvida apenas com agentes de software
reativos. O principal objetivo desta versão é testar a comunicação entre os agentes
e a execução do sistema no ambiente do TAC. A pontuação média foi medida para
poder avaliar a evolução do benchmark, mesmo sabendo que o sistema não
apresentaria boa performance. A tabela 15 mostra o benchmark feito com as
várias versões do LearnAgents.
Cada teste para avaliar a performance do sistema é feito em um simulador
da competição real contra sete jogadores chamados dummies (TAC). O sistema
joga cem partidas no benchmark para avaliar a performance média, e minimizar o
efeito da variação das preferências dos clientes. O download do simulador da
competição pode ser feito no endereço http://www.sics.se/tac.
111
Tabela 15: Benchmark das Versões do LearnAgents.
O primeiro agente selecionado foi o Alocador, versão 1.0 da tabela 15. Esse
agente calcula diferentes cenários baseados nos preços da base de conhecimento
do sistema. Esses cenários são alocações de bens para montar pacotes de viagens,
e são calculados usando um solver de programação inteira. Essa versão da
formulação calculava apenas alocações com quantidades de hotéis e passagens
aéreas. O solver não é executado apenas para encontrar a melhor alocação de
bens, mas o maior número de boas alocações geradas em 25 segundos. Cada
alocação define o número de bens por cliente que devem ser compradas em cada
leilão com a sua respectiva utilidade. Após testar o Alocador com os casos de
testes, o Ordenador também foi modificado com uma nova heurística antes de
testar o sistema no simulador. O Ordenador executa uma heurística baseada nessas
alocações para definir os bens que devem ser comprados.
O Negociador de Hotel foi o próximo agente selecionado para receber um
módulo de inteligência. O agente utiliza a técnica Minimax, uma Rede Neural e
Aprendizado por Reforço para calcular lances de leilões de hotéis. O principal
objetivo desse agente é encontrar lances ótimos e permitir a compra do bem
desejado pelo menor preço possível. O agente adapta os pesos da Rede Neural
com Aprendizado por Reforço para encontrar estados que gerem lances ótimos. A
112
versão 2.0 da agência com o Negociador de Hotel inteligente aumentou a
pontuação média para 1752.
O agente selecionado na versão 3.0 do sistema foi o Preditor. O agente
utiliza uma série histórica dos preços de hotéis para prever o futuro valor dos
preços dos leilões. O agente Preditor utiliza uma técnica chamada Exponencial
Suavizada (Bowerman et al., 1993), e permite ao Alocador usar os preços
previstos para calcular as alocações de bens. A versão 3.0 aumentou a pontuação
média para 2224.
Na versão 4.0 do sistema, o Alocador foi novamente selecionado para
alterar a formulação da programação inteira. Além de calcular a quantidade de
hotéis e passagens aéreas, o solver calcula também a quantidade de ingressos de
entretenimento. O Ordenador teve que ser alterado para tratar a compra dos
ingressos, pois nas versões anteriores os ingressos não eram negociados. O
benchmark dessa versão aumentou a pontuação para 2856, porém o sistema
começou a apresentar atrasos nas respostas com o servidor do TAC. Isso
apresentava clara evidência que os recursos computacionais da CPU estavam
baixas. Um Alocador Escravo foi criado para calcular essas alocações de
ingressos, e foi executado em outra CPU da rede. O Alocador Escravo usava a
mesma formulação de programação inteira para calcular as alocações de
ingressos.
O Alocador foi selecionado novamente na versão 5.0 do sistema para incluir
na formulação alguns parâmetros, e uma função que penaliza as alocações. Essa
função modela o risco de acumular muitas diárias para um dado dia e um dado
tipo de hotel. Essa versão aumentou a pontuação média para 3370.
O último agente selecionado foi novamente o Preditor. Esse agente foi
modificado para calcular também a predição dos preços de leilões de vôos. O
Preditor utiliza uma técnica chamada Máxima Verossimilhança para prever uma
variável aleatória escondida x do processo que atualiza os preços dos leilões de
vôos. A predição do preço futuro é calculada com o valor esperado do processo.
Nessa versão 6.0, o sistema aumentou a pontuação média para 3705.
A figura 54 apresenta um gráfico com a evolução do benchmark do
LearnAgents. Este gráfico apresenta a evolução da inteligência do sistema multiagente. Isso demonstra a eficácia do método MAS-School, pois possibilita um
113
ganho constante na performance da inteligência, com uma técnica simples de
modelar e implementar agentes inteligentes com aprendizado.
Average Score Evolution
4000
3000
2000
Average
1000
Score ($)
0
-1000
-2000
0
1
2
3
4
5
6
Versions
Figura 55: O Gráfico da Evolução do Benchmark do LearnAgents.
A tabela 16 mostra novamente o resultado do LearnAgents no TAC Classic
de 2004. Um detalhe importante sobre o resultado do benchmark no simulador é a
semelhança existente entre os resultados do melhor benchmark e o resultado da
competição. O melhor benchmark obteve uma pontuação média de 3705 e a
pontuação média da competição foi de 3736. Isso evidencia a boa performance e a
alta adaptabilidade dos nossos agentes em ambientes com jogadores diferentes.
Isso só é possível graças as técnicas de inteligência e machine learning incluídos
nos agentes do LearnAgents.
Posição
1
2
3
4
5
6
7
8
Agente
Whitebear04
Walverine
LearnAgents
SICS02
NNN
UMTac-04
Agent@CSE
RoxyBot
Pontuação Média
4122.11
3848.97
3736.62
3708.24
3665.97
3281.43
3262.51
2015.02
114
5.7.Utilizando o ASYNC na Implementação do LearnAgents
No ASYNC, cada agente no sistema deve possuir duas classes concretas. A
primeira classe a ser implementada deve herdar da classe Agent e implementar a
interface AgentInterface. Essa classe concreta deve conter métodos que
representam as ações internas dos agentes. Os métodos initialize(), run(),
terminate(), e trace() devem ser implementados nesta classe concreta.
Esse mesmo agente do sistema deve ter outra classe concreta. Essa classe
deve herdar da classe InteractionProtocols, e deve conter métodos para
implementar os protocolos de interação. O método processMsg() deve ser
implementado para processar todas as mensagens recebidas pelo agente. A
referencia para o objeto AgentCommunicationLayer é utilizada para que o agente
possa utilizar a camada de comunicação. A figura 56 ilustra a instanciação do
agente Ordenador na aplicação LearnAgents, e a instanciação do formato da
mensagem utilizando FIPA ACL (http://www.fipa.org/specs/fipa00061/).
Figura 56: A instanciação do Agente Ordenador e Formato da Mensagem na aplicação.
LearnAgents.
115
As ações internas do Ordenador foram modeladas no diagrama de cenários
da figura 57. Essas ações do agente não dependem da interação com outros
agentes no sistema. As ações “Coletar as Informações da Base de Conhecimento
Corporativa”, “Decidir os bens a serem comprados”, “Decidir as quantidades dos
bens”, e “Calcular os lances máximos” não dependem da interação com outros
agentes. Conseqüentemente, os métodos collectInfoCKB(), decideGoodsToBuy(),
decideGoodAmounts(), e calculateGoodHighPrices() da classe OrderingAgent
modelam as ações descritas acima.
O código Java a seguir apresenta o
mapeamento das abstrações em ANote para o framework ASYNC.
69.
public class OrderingAgent extends Agent implements
AgentInterface
70.
{
71.
public OrderingAgent(String name, InteractionProtocols iP){
72.
super(name, iP);
73.
}
74.
public void initialize() {
75.
...
76.
}
77.
public void terminate() {
78.
...
79.
}
80.
public void trace(String msg, int level) {
81.
...
82.
}
83.
public void run() {
84.
int NumNegotiators=3;
85.
while(true) {
86.
collectInfoCKB();
87.
for(int i=0;i<NumNegotiators;i++){
88.
decideGoodsToBuy();
89.
decideGoodAmounts();
90.
calculateGoodHighPrices();
116
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
((OrderingAgentIP)getInteractionProtocols()).
sendMessageToNegotiators();
}
}
}
public
...
}
public
...
}
public
...
}
public
...
}
}
void collectInfoCKB() {
void decideGoodsToBuy() {
void decideGoodAmounts() {
void calculateGoodHighPrices() {
Os protocolos de interação do Ordenador também são modelados pelo
diagrama de cenários da figura 57. Os protocolos de interação definem como o
agente deve se comunicar e interagir com outros agentes no sistema. A ação
“Enviar Mensagem para os Negociadores” exige uma interação com outros
agentes no sistema. Conseqüentemente, essa ação deve ser colocada no método
sendMessageToNegotiators().
sendMessageHotelNegotiator(),
Esse
método
executa
os
métodos
sendMessageTicketNegotiator(),
e
sendMessageFlightNegotiator(). Esses métodos utilizam o método sendMsg() da
camada de comunicação para enviar as mensagens para os agentes negociadores.
1. public class OrderingAgentIP extends InteractionProtocols
2. {
3.
public void processMsg(AgentMessage msg) {
4.
FipaACLMessage msgReceived = (FipaACLMessage)msg;
5.
...
6.
}
7.
public void sendMessageToNegotiators(){
8.
sendMessageFlightNegotiator();
9.
sendMessageHotelNegotiator();
10.
sendMessageTicketNegotiator();
11.
}
12.
public void sendMessageHotelNegotiator() {
13.
14.
getAgCommLayer().sendMsg("HotelNegotiator",msg);
15.
}
16.
public void sendMessageTicketNegotiator() {
17.
18.
getAgCommLayer().sendMsg("TicketNegotiator",msg);
19.
}
20.
public void sendMessageFlightNegotiator() {
21.
22.
getAgCommLayer().sendMsg("FlightNegotiator",msg);
23.
}
24.
}
117
O framework ASYNC foi fundamental para o desenvolvimento do
LearnAgents, pois ele possui um mapeamento claro entre abstrações de agentes e
código OO, permite re-uso de código e conseqüentemente uma diminuição no
tempo de desenvolvimento, e também diminui a complexidade de implementar
agentes de software.
118
6 A Aplicação LearnAgentsSCM
Supply Chain Management (SCM) é o planejamento e coordenação das
atividades de uma cadeia de suprimentos (Chopra et al., 2004). Essas atividades
podem ter vários participantes e organizações, e a coordenação desses
participantes é um ponto chave para uma cadeia eficiente. O Supply Chain não
está relacionado apenas com os produtores e fornecedores, mas também com
transportadoras, centros de distribuição, e clientes. Essa cadeia é extremamente
dinâmica e envolve um grande fluxo de informação, produtos e recursos
financeiros entre diferentes estágios.
O TAC Supply Chain Management (Arunachalam et al., 2004) foi modelado
para capturar a complexidade de uma cadeia de suprimentos dinâmica, porém com
regras simples para que muitas equipes possam participar dessa competição. O
jogo foi desenvolvido por pesquisadores do laboratório de e-Supply Chain
Management da Carnegie Mellon University e Swedish Institute of Computer
Science (SICS).
O LearnAgentsSCM é um sistema multi-agente para a gestão automatizada
de uma cadeia de suprimentos. O sistema é utilizado em ambientes competitivos
onde os participantes competem por clientes, um número limitado de peças, e
precisam gerenciar a produção com uma limitação na capacidade produtiva. A sua
arquitetura define agentes que resolvem subproblemas de gestão da cadeia de
suprimentos, e apresenta uma técnica para combinar todas essas soluções. Os
subproblemas típicos são seleção de clientes, planejamento da produção,
negociação de peças para o estoque, entre outros. O LearnAgentsSCM utilizou o
ambiente do TAC para testar o sistema desenvolvido, pois esse ambiente simula
um ambiente competitivo e permite mensurar a performance do sistema contra um
benchmark internacional.
119
6.1. O TAC Supply Chain Management
Seis agentes “produtores de PC” participam em cada jogo do TAC SCM.
Esses participantes competem por clientes com incerteza na demanda e por peças
de um numero limitado de fornecedores. Todo dia, os clientes enviam pedidos de
cotações e selecionam as melhores ofertas baseadas no preço e na data de entrega.
Os agentes são limitados pela capacidade da fabrica, e tem que gerenciar a compra
de peças de oito fornecedores. Quatro componentes são precisos para montar um
PC: CPU, Placa Mãe, Memória, e Disco Rígido. Cada componente está disponível
em diferentes modelos. A demanda dos clientes pode ser medida pelo número de
cotações de PCs. A figura 58 resume o cenário do jogo TAC SCM.
Figura 58: O Jogo TAC SCM.
O jogo começa quando um ou mais agentes se conectam ao servidor do
TAC SCM. O servidor simula o comportamento dos fornecedores e clientes, e
oferece um ambiente para cada participante com um banco para sua conta
corrente, uma fábrica, e estoques de peças e PCs. No final do jogo, o agente que
possuir o maior valor de dinheiro na conta corrente é declarado o vencedor.
120
O jogo apresenta um bom nível de complexidade, pois cada agente deve
competir em vários mercados por diferentes componentes do lado dos
fornecedores, e em mais outros mercados por diferentes tipos de PCs no lado dos
clientes. Além disso, todos esses mercados possuem interdependências e
incertezas. Esse cenário permite a criação de várias estratégias diferentes, e um
agente precisa ser adaptativo para estar pronto para vários cenários imprevisíveis.
6.2. Evolução do TAC SCM
A primeira versão do ambiente do jogo utilizado no TAC SCM foi projetada
em 2003 por um grupo do Laboratório de e-Supply Chain Management da
Carnegie Mellon University e do Swedish Institute of Computer Science (SICS). A
versão do ano seguinte passou por mudanças significativas para que o ambiente
simulasse um mercado mais competitivo.
Posição
1
2
3
4
5
6
Agente
RedAgent
deepmaize
TacTex
Botticelli
PackaTAC
whitebear
Pontuação Média
11.61 M
9.473 M
5.017 M
3.330 M
-1.680 M
-3.453 M
A primeira edição do TAC SCM foi sediada dentro da Eighteenth
International Joint Conference on Artificial Intelligence (IJCAI-03) em 2003. A
tabela 17 apresenta os resultados desta edição. A média dos três primeiros
concorrentes é de 8,7 milhões, o que representa a existência de soluções robustas
para esse complexo cenário.
As estratégias dos agentes do TAC SCM podem ser classificadas em duas
grandes categorias: (i) buy-to-build, onde o agente estoca componentes e começa
a produzir PCs sem ter necessariamente ordens para programar a produção; e (ii)
build-to-order, o agente espera receber primeiro as ordens dos clientes, e depois
produz e entrega PCs baseado nessas ordens. O agente que adota a estratégia buyto-build é mais agressivo e pode aceitar qualquer oportunidade que for altamente
lucrativa. Porém, o agente corre o risco de ter estoque encalhado, e pagar custos
121
altos de estocagem. A estratégia build-to-order é mais conservadora, pois só
aceita oportunidades que possam ser produzidos no futuro. Porém, se o cliente
enviar um pedido de cotação altamente lucrativo para ser entregue imediatamente,
o agente não pode aceitar esse tipo de oportunidade.
Em 2003, o vencedor RedAgent (Keller et al., 2004) utiliza um sistema
multi-agente com várias heurísticas simples, e utiliza uma estratégia buy-to-build
junto com o mecanismo de leilões para determinar a alocação ótima de recursos.
Nessa estratégia, a primeira preocupação do produtor é estocar componentes e
produzir PCs sem necessariamente ter ordens de clientes para cumprir. O
RedAgent se beneficiava do fato de não haver um custo de estocagem nessa versão
do jogo. Além disso, ele poderia vender seus PCs a qualquer momento, mesmo
abaixo do custo, para se ver livre do estoque. Os agentes dentro do sistema
RedAgent utilizam o mecanismo dos leilões para determinar as alocações dos
recursos. Por exemplo, o Assembler Agent é um agente de produção e ele tem que
negociar através de leilões o uso de matéria prima e ciclos de fábrica.
Posição
1
2
3
4
5
6
Agente
FreeAgent
Mr.UMBC
UMTac-04
Botticelli
deepmaize
SouthamptonSCM
Pontuação Média
10.28 M
8.652 M
6.518 M
441 711
-5.108 M
-10.41 M
A segunda versão do TAC SCM, em julho de 2004, teve a sua realização
dentro da Third International Joint Conference on Autonomous Agents and Multi
Agent Systems (AAMAS’04), na cidade de Nova York. Algumas regras foram
modificadas para aumentar a competitividade do jogo. Por exemplo, o custo de
estocagem foi incluído nesta versão. A tabela 18 apresenta o resultado final da
competição. Os agentes FreeAgent, Mr.UMBC, UMTac-04 não apresentaram, até
janeiro de 2005, qualquer relatório de pesquisa sobre as estratégias utilizadas. A
média dos três primeiros concorrentes nesse ano é de 8,48 milhões. Três agentes
novos ocuparam os três primeiros lugares em relação ao ano 2003, porém a média
desses três se manteve quase constante.
122
Os criadores do agente Botticelli (Benisch et al., 2004), quarto lugar em
2003 e 2004, modelaram o problema de responder a RFQs dos clientes como um
modelo estocástico. O agente utiliza algumas heurística e programação inteira
para decidir que RFQs aceitar. A programação da produção é feita com um
algoritmo guloso. Esse agente utiliza a estratégia mais próxima do build-to-order,
pois produz PCs baseado nas ordens atuais e ofertas (RFQs) com alta
probabilidade de se tornarem ordens.
O agente Deep Maize (Kiekintveld et al., 2004) aceita os RFQs baseado nos
estoques de PCs, disponibilidade de peças e ociosidade na produção. Ele possui
uma estratégia de sempre manter estoque de PCs prontos. A programação da
produção é feita com um horizonte de três dias, e utiliza programação linear para
escolher os PCs a serem produzidos. Esse agente utiliza a estratégia mais próxima
do buy-to-build.
6.3.Arquitetura LearnAgentsSCM
O LearnAgentsSCM também utiliza a tecnologia de agentes, e cria entidades
autônomas e inteligentes para atuarem em complexos ambientes distribuídos,
competitivos e abertos. A técnica de modelar um problema computacionalmente
difícil do LearnAgents foi utilizada também nesse novo domínio. O método de
decomposição de subproblemas foi utilizado para diminuir a complexidade do
problema. Assim, cada agente se torna responsável por um ou mais desses
subproblemas.
A figura 59 apresenta a arquitetura do LearnAgentsSCM, e esta seção
descreve a modelagem do sistema multi-agente usando uma linguagem de
modelagem chamada ANote (Choren, 2002).
123
Figura 59: A Arquitetura do LearnAgentsSCM.
Esse projeto de software também utiliza a técnica orientada a objetivos para
a fase de requisitos. Esta fase utiliza o processo recursivo de decomposição de um
objetivo do problema principal em vários objetivos de subproblemas mais
simples. No caso do LearnAgentsSCM, esse processo recursivo definiu todos os
objetivos dos subproblemas relacionados com a produção, compra de matéria
prima, e comercialização de bens.
O objetivo maior desse sistema é produzir PCs e obter o maior lucro
possível. Essa produção envolve os seguintes processos: (i) gerenciar as vendas
para o cliente, (ii) gerenciar a produção das ordens, (iii) gerenciar a compra de
matéria prima, e (iv) gerenciar a entrega dos PCs. A figura 60 mostra esse
processo de decomposição dos objetivos.
124
Figura 60: A decomposição dos objetivos relacionados com a produção, compra de
matéria prima, e comercialização de bens.
O processo de vendas pode ser decomposto em dois objetivos: (i) selecionar
os pedidos de cotações mais interessantes, por exemplo, em relação à
lucratividade ou a oportunidade de explorar um novo mercado, e (ii) escolher o
preço para as cotações selecionadas.
O processo de produção pode ser decomposto em: (i) escolher a melhor
alocação das ordens a serem produzidas no dia corrente, e (ii) decidir a produção
das ordens no futuro para poder calcular a ociosidade da fábrica.
O processo de entrega pode ser decomposto em três objetivos: (i) decidir a
entrega diária, (ii) decidir a entrega no futuro para saber quais ordens serão
canceladas, e (iii) decidir cancelar o menor número de ordens, caso seja
inevitável.
A compra da matéria prima pode ser decomposta em dois objetivos: (i)
decidir as peças a serem compradas escolhendo o tamanho ótimo do lote de
compra, e tamanho ótimo do estoque de segurança, e (ii) negociar a compra das
peças selecionadas e quantidades ordenadas.
sejam capazes de atingir os objetivos da figura 60. Essa criação começa com
processo de relacionamento de todos os objetivos de nível mais baixo com os
respectivos tipos de agentes. A tabela 19 apresenta um mapeamento entre esses
objetivos e tipos de agentes. A figura 61 apresenta os vários tipos de agentes e
125
seus relacionamentos. Esta figura permite uma visão estática do projeto do nosso
sistema multi-agente.
Goal
Agent
Select RFQs
Marketing Manager
Bid for Customer Orders
Sales Representative
Decide
Daily
Production
from Production Scheduler
Orders
Decide Future Production from Production Scheduler
Orders
Decide Daily Delivery of Orders
Delivery Scheduler
Decide Future Delivery of Orders
Delivery Scheduler
Decide Orders to Cancel
Delivery Scheduler
Decide Components to buy based Procurement Manager
on Inventory
Negotiate Components
Procurement Buyer
Figura 61: O Diagrama de Agentes do LearnAgentsSCM.
Os Sensores do ambiente não foram incluídos na figura 61 para manter a
especificação mais simples e de fácil compreensão. Os objetivo dos Sensores
nessa arquitetura são: (i) atualizar a base de conhecimento corporativa com
126
informações sobre clientes, RFQs, Ordens, informações sobre a fábrica, e
informações sobre os fornecedores; e, (ii) enviar mensagens para outros agentes
sobre eventos importantes do ambiente externo.
Os Efetuadores do ambiente também não foram incluídos na figura 61 pelo
mesmo motivo dos sensores. O objetivo dos Efetuadores nessa arquitetura é
enviar informações com respostas a RFQs, pedido de cotação aos fornecedores
para o ambiente externo. Esse agente é puramente reativo, pois envia as
informações ao ambiente externo apenas quando é solicitado por outro agente do
sistema.
Pelo mesmo motivo dos Sensores e Efetuadores, o Monitor não foi incluído
na figura 61. Esse agente é responsável por armazenar informações da base de
conhecimento corporativa em um banco de dados. Esses dados são utilizados por
uma ferramenta da CA (Computer Associates) chamada Forest and Trees para
monitorar a performance de cada agente individualmente e o sistema multi-agente
como um todo. Uma tela da ferramenta de monitoração pode ser vista na figura
62.
127
de como cada agente deverá atingir seus objetivos. Segue abaixo, uma descrição
resumida dos agentes criados e seus cenários:
Gerente de Marketing – Esse agente é responsável por selecionar quais
RFQs, ou pedido por cotações dos clientes, serão respondidos. O Gerente de
Marketing deve selecionar os RFQs lucrativos, e deve utilizar estratégias de
segmentação de mercado para melhorar a performance da escolha. A figura 63
apresenta o digrama de cenário do Gerente de Marketing.
Figura 63: Cenário da Seleção dos Pedidos por Cotações.
Vendedor – Esse agente é responsável por definir o preço dos RFQs
selecionados pelo Gerente de Marketing. O agente pode adotar diferentes
estratégias de preços dependendo do mercado. A figura 64 apresenta o digrama de
cenário do Vendedor.
Figura 64: Cenário da Decisão dos Lances.
128
Programador da Produção – Este agente decide a programação da
produção do dia corrente para todas as ordens dos clientes. O Gerente da
Produção também calcula a programação da produção para os próximos dias para
que possa ser determinada a ociosidade da fábrica. A figura 65 apresenta o
digrama de cenário do Gerente de Produção.
Figura 65: Cenário da Programação da Produção.
Programador da Entrega – Este agente é responsável por decidir quais
ordens serão entregues no dia corrente e no futuro. A decisão das ordens entregues
no futuro permite a decisão das ordens a serem canceladas. A figura 66 apresenta
o digrama de cenário do Gerente de Entrega.
Figura 66: Cenário da Programação da Entrega e Ordens a Cancelar.
129
Gerente de Compras – Este agente decide quais peças devem ser
compradas. Este decisão dever ser baseada no nível de estoque atual. A figura 67
apresenta o digrama de cenário do Gerente de Entrega.
Figura 67: Cenário da Decisão de Compra dos Componentes.
Comprador – Este agente negocia com os fornecedores as pecas definidas
pelo Gerente de Compras. Esta decisão se baseia no preço mais baixo e fidelidade
dos fornecedores em relação à entrega. A figura 68 apresenta o digrama de
cenário do Gerente de Entrega.
Figura 68: Cenário da Negociação dos Componentes com os Fornecedores.
130
de interação. Esse diagrama deixa explícita a comunicação entre os agentes, e
permite uma visão dinâmica do sistema. A figura 69 apresenta o processo de
vendas, e a interação entre o Gerente de Marketing e o Vendedor.
Figura 69: Diagrama de Interação do processo de vendas.
Figura 70: Diagrama de Interação do Processo de Compra de Matéria Prima.
A figura 70 apresenta o processo de compra da matéria prima. O Gerente de
Compras decide quais peças serão compradas, e envia para o Comprador pedidos
131
de compra. O comprador negocia a compra das peças com os fornecedores
disponíveis. O processo de produção e entrega está presente na figura 71 e 72.
Figura 71: Diagrama de Interação do Processo de Produção.
Figura 72: Diagrama de Interação do Processo de Entrega.
132
6.4.A Engenharia de Algoritmos dos Agentes do LearnAgentsSCM
Esta seção apresenta os principais algoritmos utilizados no Gerente de
Compras, Programador da Produção, Programador da Entrega, e Gerente de
Marketing. O restante dos agentes utiliza uma lógica simples que são muito
parecidas com o código apresentado nos cenários da seção 6.3.
6.4.1.Gerente de Compras
O Gerente de Compra utiliza o conceito de comprar matéria prima em lotes
(Horngren et al., 1997; Chopra et al., 2004) para satisfazer a demanda por peças.
A figura 73 mostra o gráfico da demanda por peça para uma demanda constante.
Figura 73: Nível de Estoque por tempo.
Se o fornecedor de uma peça leva um tempo T para fazer a entrega de um
pedido, então o agente deve fazer esse pedido quando o nível de estoque atingir o
valor L. Uma decisão importante é calcular esse valor L por peça:
Figura 74: Decisão de Compra dos Componentes.
133
No ambiente do TAC SCM, a demanda por peça não é constante, pois a
demanda dos clientes por PCs é um passeio aleatório. Além disso, o tempo de
entrega das peças pelos fornecedores também não é constante. Conseqüentemente,
o Gerente de Compras re-calcula a demanda por peça e o tempo médio de entrega
dos fornecedores utilizando uma média móvel. O algoritmo abaixo resume a
decisão diária do Gerente de Compras:
Para cada peça:
1. Calcular demanda d por unidade de tempo utilizando uma
média móvel.
2. Calcular o tempo médio T de entrega dos fornecedores
utilizando uma média móvel.
3. Calcular o L = d * T, representando o nível de estoque para se
fazer o pedido.
4. Se o nível atual de peças em estoque for menor que L, então
fazer o pedido para um fornecedor de tamanho B do lote.
6.4.2.Programador da Produção e Programador da Entrega
A decisão de produzir e entregar as ordens é problema de alocação de
recursos para gerar o maior lucro possível. Porém, o problema possui algumas
restrições: (i) toda ordem de cliente tem que ser produzida e entregue até uma data
limite, (ii) a fábrica possui uma capacidade limitada de ciclos de produção por dia,
e (iii) necessidade de estoques de peças para produzir os PCs. Uma descrição de
alto nível para o problema é feita abaixo:
Objetivo da Alocação de Recursos:
Maximizar o Lucro Esperado.
Entradas:
Ordens Ativas;
Capacidade da fábrica por dia;
Componentes em estoque.
134
Saídas:
As ordens produzidas em cada dia;
As entregas das ordens. Para simplificar o problema, as entregas são
sempre feitas um dia depois da produção.
Um algoritmo guloso é proposto para resolver esse problema. O algoritmo
procura por ordens que geram muita receita líquida por ciclo de fábrica e não leva
em consideração os custos de peça, pois as peças já foram compradas. Esse
algoritmo não garante uma alocação ótima, mas já produz bons resultados.
Seja:
N – número de ordens ativas
Oi – A i-ésima ordem ativa (i < N)
Onde, cada Oi possui os seguintes atributos:
Pi – Penalidades por Ordem i
TCi – Ciclos de Fábrica para produzir a Ordem i
Ri – A Receita da Ordem i
Di – Data limite para produção (depois dessa data a ordem recebe a
penalidade,
e
5
dias
depois
o
cliente
cancela
a
ordem
automaticamente)
Assim, podemos definir a Receita Líquida Média por Ciclo gerada pela
produção da ordem i, com início no dia j, como:
Cij = ( Ri – Pij ) / TCi
Então, O algoritmo procura por ordens que geram muita receita líquida por
ciclo de fábrica, e executa o algoritmo abaixo até alocar todos as ordens ativas:
1. Calcular Cij e Ci* para todos os Oi’s a serem produzidos
Pij – Penalidade por Ordem i no dia j (1
j
8) de Produção
+
Pij = ( j - Di ) . Pi
Cij – Receita por ciclo (incluindo a penalidade) por Ordem i
no dia j de Produção
135
Cij = ( Ri – Pij ) / TCi
Cij = - , se capacidade de produção na fábrica no dia j
está esgotado, ou se não há componentes em estoque
para produzir a Ordem i
Ci* = max{ Cij }, para cada Ordem i
2. Encontrar o maior Ci* correspondente a Ordem i (se Ci* < 0 então a
ordem não é alocada para a produção)
3. Produzir a Ordem i (encontrada no passo 2) no dia d
For j = ( Di + 5 ) to 0
If ( Cij
- ) and ( Cij = Ci* )
d=j
Break For
End if
End for
4. Atualizar níveis de estoque e ciclos de fábricas disponíveis
A estratégia adotado pelo algoritmo é gulosa na Receita Líquida com
agendamento no último período viável livre.
6.4.3.Gerente de Marketing
O Gerente de Marketing utiliza o algoritmo guloso da seção 6.4.2, com
algumas pequenas modificações, para decidir a quais RFQs serão enviados lances.
Os novos RFQs são considerados como Ordens Ativas. Porém, a receita das
Ordens Ativas é multiplicada por um fator k, pois Ordens Ativas “verdadeiras”
são mais importantes. Além disso, o Cij agora inclui o custo de peça para produzir
a ordem i. Conseqüentemente:
Cij – Lucro por ciclo (incluindo a penalidade) por Ordem i no dia j de
Produção
CPi – Custo de Peças para a ordem i
Cij = ( k.Ri – Pij - CPi) / TCi, se for uma Ordem Ativa
Cij = ( Ri – Pij - CPi) / TCi, se for um RFQ
Cij = - , se capacidade de produção na fábrica no dia j está esgotado,
ou se não há componentes em estoque para produzir a Ordem i
136
Depois de executar o algoritmo guloso com as modificações acima, os
RFQs selecionados para a produção são enviados para o Vendedor para que possa
enviar os lances.
6.5.Utilizando o MAS-School no Processo de Desenvolvimento do
LearnAgentsSCM
Na primeira fase do MAS-School, o engenheiro de software deve definir
dois elementos centrais que estão relacionados com aprendizado: (i) Objetivo
Sistêmico, SG, e (ii) Medida de Performance Sistêmica, SP, que mede o ganho de
performance do sistema. No LearnAgentsSCM, o Objetivo Sistêmico foi definido
utilizando a técnica orientada a objetivos da figura 60. Conseqüentemente, (i) SG:
produzir PCs e obter o maior lucro possível, e (ii) SP: A pontuação média
representando o lucro médio obtido do sistema no ambiente TAC SCM.
Na segunda fase, os tipos de agentes definidos na tabela 19 são selecionados
para utilizar técnicas de machine learning. O objetivo é estabelecer um Problema
conhecimento no agente com o aprendizado. No LearnAgentsSCM, o Gerente de
Compras foi um dos agentes selecionados para utilizar um técnica de machine
learning. O Problema de Aprendizado do Agente para o Gerente de Compras pode
ser definido por:
(vii)
G: Prever o consumo de matéria prima;
(viii) P: O erro entre a previsão da peça e o real; e
(ix)
E: Utilizar um histórico de utilização de peças.
Na terceira fase, um bom design do agente é criado para permitir a inclusão
ou reuso de várias técnicas de machine learning. Além disso, o design deve
proporcionar uma boa manutenção de código. O Gerente de Compras também
utilizou o padrão de projeto orientado a objetos da seção 4.2.
137
machine learning, nos agentes selecionados são: (i) a representação do
conhecimento; (ii) o algoritmo de aprendizado; (iii) o conjunto de treinamento
utilizado pelo algoritmo de aprendizado. O conhecimento do Gerente de Compras
foi modelado como uma função chamada ComponentRequired. Essa função
recebe uma demanda passada de matéria prima P e gera a futura demanda F
(ComponentRequired: P
ComponentRequired
utiliza
F ). A representação aproximada da função
uma
função
para
essa
demanda
futura:
ComponentRequired(n) = (1/ )*(AskPrice(n-1) + ...+ PredictedAskPrice(n- )),
onde
é o tamanho da janela da média; e n é o n-ésimo jogo. O algoritmo de
aprendizado Least Mean Squares (LMS) é utilizado para adaptar o : (n) = (n-
1) + ß*( ComponentRequired(n-1)- ComponentUsed(n-1)), onde ß é a taxa de
aprendizado.
inteligentes em uma única fase, a fase de implementação utiliza uma proposta
incremental para facilitar a integração e análise da performance dos agentes. A
primeira versão do LearnAgentsSCM foi desenvolvido apenas com agentes de
software reativos. A pontuação média foi medida para poder avaliar a evolução do
benchmark, mesmo sabendo que o sistema não apresentaria boa performance. A
tabela 20 mostra o benchmark feito com as várias versões do LearnAgentsSCM.
Cada teste para avaliar a performance do sistema era feito em um simulador da
competição real contra seis jogadores chamados dummies (TAC). O sistema
jogava dez partidas no benchmark para avaliar a performance média, e minimizar
tanto o efeito da variação da demanda dos clientes quanto à variação na produção
dos fornecedores.
138
LearnAgentsSCM
Agent Selected /
Average
Games
Version
Intelligent Module
Score
Played
0.0
---
-633.291.661
10
1.0
Procurement Manager /
-248.466.127
10
-28.901.477
10
28.865.996
10
Lot Size and
When to Order
2.0
Production Scheduler &
Delivery Scheduler /
Greedy Algorithm
Marketing Manager /
Greedy Algorithm
3.0
Procurement Manager /
Safety Inventory
Tabela 20: Resultados da Evolução do Benchmark.
A versão 1.0 do LearnAgentsSCM implementou a técnica de comprar
matéria prima em lotes e decisão ótima de quando comprar (Chopra et al., 2004)
no Gerente de Compra. Essa técnica permite uma boa redução de custos, e
conseqüentemente um prejuízo menor em relação ao primeiro benchmark. Esse
resultado gerou uma pontuação média de -248 milhões.
A versão 2.0 implementou, no Programador da Produção e Programador da
Entrega, o algoritmo guloso para programar a produção e entrega de produtos. O
Gerente de Marketing também utilizou uma versão modificada desse algoritmo
guloso para decidir quais RFQs serão aceitos. Essa técnica tornou a fábrica mais
eficiente e lucrativa, e conseqüentemente melhorou o resultado para -28 milhões.
A versão 3.0 do sistema implementou a técnica de manter estoque de
segurança (Chopra et al., 2004) e compra de matéria prima em pequenos lotes.
Essa técnica permitiu uma redução de custos ainda maior, e conseqüentemente a
pontuação média subiu para 28 milhões.
A figura 75 apresenta um gráfico com a evolução da inteligência do
LearnAgentsSCM. O ganho constante na performance da inteligência permite
constatar novamente a eficácia do método MAS-School.
139
Average Score Evolution
100.000.000
0
-100.000.000
-200.000.000
Average
-300.000.000
Score ($)
-400.000.000
-500.000.000
-600.000.000
-700.000.000
0
1
2
Versions
Figura 75: Gráfico da Evolução do Benchmark.
3
140
7 Conclusões
O desenvolvimento de um sistema multi-agente de larga escala (Lucena et
al., 2003; Garcia et al., 2003) não é uma tarefa simples. Sistemas com muitos
agentes em ambientes heterogêneos necessitam de soluções de engenharia de
software para permitir reuso e um desenvolvimento eficiente. Em sistemas
complexos e abertos, agentes precisam de aprendizado para tomar decisões e se
adaptar a mudanças para poder atingir os seus objetivos e o objetivo global do
sistema.
intuição para desenvolver sistemas complexos. Além disso, nem sempre esses
sistemas são fáceis de escalar. Muita pesquisa tem sido feita para criar
nas fases iniciais do desenvolvimento.
Nesse contexto, a tese possui como principais contribuições o método MASSchool e o framework ASYNC para construção de agentes inteligentes em
ambientes heterogêneos e abertos. Além disso, apresenta dois estudos de casos
complexos, o LearnAgents e o LearnAgentsSCM, que foram desenvolvidos com o
MAS-School e o ASYNC.
O método MAS-School (Sardinha et al., 2004b; Sardinha et al., 2005b) é
utilizado para modelar e implementar agentes de software inteligentes desde as
primeiras fases de desenvolvimento. Esse método também apresenta várias
orientações de como incluir aprendizado nas fases de design e implementação. O
método apresenta uma estratégia incremental de desenvolvimento para avaliar as
técnicas de machine learning e permitir escalar o sistema com facilidade.
141
Os pontos mais fortes do MAS-School são:
(i)
A técnica orientada a objetivos para a fase de requisitos utiliza o processo
recursivo de decomposição de um objetivo do problema principal em
vários objetivos de subproblemas. Essa técnica é interessante, pois permite
dividir um problema computacionalmente difícil em subproblemas mais
simples;
(ii)
O objetivo do problema principal é associado a uma medida de
performance para o sistema. Essa medida de performance permite
mensurar se o objetivo sistêmico está sendo alcançado;
(iii)
Os objetivos funcionam como uma abstração para unificar conceitos de
aprendizado com conceitos básicos de sistemas multi-agente;
(iv)
Um mapeamento claro é feito entre objetivos do sistema e tipos de
agentes. Conseqüentemente, os tipos de agentes são responsáveis por
conduzir os objetivos desses subproblemas encontrados na fase de
requisitos;
(v)
Tipos de agentes são selecionados, e seus objetivos são associados a uma
medida de performance. Essa medida de performance permite mensurar se
o objetivo de cada agente está sendo alcançado;
(vi)
O processo incremental e iterativo de implementação permite verificar o
quanto o objetivo do problema principal do sistema esta sendo alcançado
através da medida de performance selecionada. Conseqüentemente, o
engenheiro de software pode projetar técnicas de machine learning que
maximizem essa medida de performance.
(vii)
Esse método apresenta um processo passo-a-passo para incluir técnicas de
machine learning em sistemas multi-agente, e prevenir que sejam incluídas
técnicas de aprendizado que deteriorem o sistema. Além disso, o
engenheiro do sistema pode avaliar o ganho de performance com a
inclusão de cada técnica.
142
Os pontos fracos do MAS-School são:
(i)
O MAS-School se baseia nos diagramas do ANote para utilizar o método.
Conseqüentemente, outras linguagens de modelagem baseada em agentes
não são capazes de ilustrar todos os passos.
(ii)
O MAS-School não seleciona automaticamente o algoritmo de
aprendizado para cada agente, mas fornece apenas um mapeamento entre
as seguintes abstrações: objetivos, medida de performance, tipo de
conhecimento, algoritmo a ser utilizado, e processo de geração do conjunto
do treinamento. O processo incremental e iterativo de implementação
permite selecionar a melhor técnica de aprendizado, mas não faz essa
seleção automaticamente.
O framework ASYNC (Sardinha et al., 2003a) é utilizado para implementar
os agentes inteligentes, e apresenta um mapeamento das abstrações de agentes
para abstrações OO (Sardinha et al., 2005c). Esse framework é fundamental para o
método proposto, pois:
(i)
Permite um mapeamento claro entre abstrações geradas pelo MAS-School
e ANote para código OO.
(ii)
O mapeamento diminui a complexidade de implementar agentes de
software;
(iii)
Permite re-uso de código e diminui o tempo de desenvolvimento. A
camada de comunicação do ASYNC para ambientes distribuídos já está
implementada. Essa camada de comunicação fornece serviços para troca
de mensagens síncrona e assíncrona via um espaço de tuplas.
(iv)
O ASYNC fornece uma ferramenta para executar os agentes em um
ambiente distribuído;
(v)
A implementação de uma arquitetura baseada em agentes utilizando o
ASYNC permite criar um sistema com alta escalabilidade. Esses agentes
podem ser executados em qualquer CPU de uma rede, e por isso não há
limite para o número de agentes no sistema.
143
(vi)
Os resultados de ações dos agentes podem ser compartilhados em uma
base de conhecimento corporativa dentro do espaço de tuplas. Os agentes
podem acessar esses resultados mesmo que este esteja fisicamente em
outra CPU.
Os pontos fracos do ASYNC são:
(i)
O framework ASYNC não possui um gerador automático de código entre
os modelos de design e código. O mapeamento poderia ser feito de forma
automática através de uma ferramenta;
(ii)
O ASYNC não fornece o serviço de mobilidade para agentes;
(iii)
O mapeamento entre modelos de design e código foram testados apenas
com a metodologia Gaia (Ribeiro, 2001), Anote/MAS-School (Sardinha et
al., 2005c).
O LearnAgents é um sistema multi-agente para um complexo cenário de
procurement, onde os agentes compram e vendem bens em leilões simultâneos
para montar pacotes de viagens para seus clientes. O sistema é utilizado em
ambientes competitivos onde os participantes competem por um número limitado
de bens.
O LearnAgents utilizou a competição do Trading Agent Competition (TAC)
para testar a arquitetura, o método MAS-School, e o framework ASYNC. Esse
ambiente apresenta características de um mercado competitivo e permite avaliar a
performance do LearnAgents em relação a outros sistemas para comércio
eletrônico. O LearnAgents conseguiu o terceiro lugar na competição de 2004, e
confirmou a robustez do método e re-uso do framework propostos.
O LearnAgentsSCM é um sistema multi-agente para a gestão automatizada
de uma cadeia de suprimentos. O sistema também utilizou a competição do
Trading Agent Competition (TAC) para testar a arquitetura, o método MASSchool. A arquitetura ainda não foi testada na competição, mas já apresenta um
ganho expressivo na evolução da performance por estar sendo construída com o
método MAS-School.
144
As contribuições dessa tese apresentam uma abordagem para construir
agentes inteligentes com aprendizado desde a fase de design até implementação.
Vários benefícios são identificados pelos estudos de casos, porém alguns
aprimoramentos ainda podem ser feitos. Algumas dessas idéias são apresentadas
abaixo:
(i)
Incluir no framework ASYNC uma ferramenta para distribuir os agentes
automaticamente nas CPUs da rede. No método MAS-School, esse
processo é feito manualmente quando um agente começa a utilizar muitos
recursos computacionais do sistema tais como CPU e memória;
(ii)
Oferecer o serviço de mobilidade no framework ASYNC. Este serviço
permitiria a distribuição automática de agentes em qualquer momento na
execução dos agentes;
(iii)
Desenvolver uma ferramenta gráfica para auxiliar todo o processo de
desenvolvimento e avaliação da performance do método MAS-School.
Essa ferramenta poderia gerar automaticamente gráficos para avaliar o
ganho de performance dos agentes e do sistema;
(iv)
Utilizar o MAS-School para melhorar a performance do LearnAgents e
continuar testando a robustez do método. A aplicação precisa obter uma
melhora na performance de pelo menos 10,32% para alcançar o ganhador
do TAC 2004, o Whitebear. Novas técnicas de machine learning precisam
ser testadas para alcançar o resultado do Whitebear;
(v)
Incluir mais um agente na aplicação para fazer um tuning automático do
LearnAgents, e continuar testando a escalabilidade do método . Os agentes
Alocador e Ordenador possuem vários parâmetros que são definidos pelo
usuário do sistema. Esses parâmetros são utilizados para fazer um tuning
do sistema. Um algoritmo de machine learning poderia ser utilizado para
fazer esse tuning automático.
(vi)
Utilizar o MAS-School para melhorar a performance da aplicação
LearnAgentsSCM. O pontuaçao média no benchmark contra os dummies
precisa melhorar para tornar a aplicação mais competitiva para o TAC de
2005. Novas técnicas de machine learning precisam ser incluídas nos
agentes, e esse processo vai permitir também o teste de robustez do
método MAS-School.
145
As técnicas de inteligência e aprendizado serão vitais para construção de
sistemas que automatizem processos. A tecnologia de agentes é a mais promissora
para permitir essa automatização, pois ela permite uma integração de várias
técnicas de inteligência e possui uma alta escalabilidade. O processo de modelar
agentes inteligentes não é um processo trivial, e esta tese apresenta um método e
um framework para tornar esse processo mais simples. Essa simplicidade pode ser
constatado pelas aplicações LearnAgents e LearnAgentsSCM.
146
8 Referências
[1] ALEXANDER, C. et al.. A Pattern Language. Oxford University Press,
New York, 1977.
[2] ALEXANDER, C.. The Timeless Way of Building. Oxford University Press,
New York, 1979.
[3] ARUNACHALAM, R.; SADEH, N.. The 2003 Supply Chain Management
Trading Agent Competition. PROCEEDINGS OF THE TRADING
AGENT DESIGN AND ANALYSIS WORKSHOP AT AAMAS’04, p.2835, New York, USA, Julho 2004.
[4] BEVILACQUA, F.; SARDINHA, J.A.R.P.. Estruturas dinâmicas de
incentivos para grupos de consumo. C. J. P. Lucena and R. L. Milidiú,
editors, SISTEMAS MULTI-AGENTES, p.145-159, Papel Virtual Editora,
ISBN: 85-7493-155-1, Julho 2001.
[5] BENISCH, M.; GREENWALD, A.; GRYPARI, I.; LEDERMAN, R.;
NARODITSKIY, V.; TSCHANTZ, M.. Botticelli: A Supply Chain
Management Agent. PROCEEDINGS OF THE THIRD INTERNATIONAL
JOINT CONFERENCE ON AUTONOMOUS AGENTS AND
MULTIAGENT SYSTEMS (AAMAS’2004), p.1174-1181, New York, USA,
Julho 2004.
[6] BOWERMAN, B. L.; O'CONNELL, R. T.. Forecasting and Time Series:
An Applied Approach. Thomson Learning, 3rd edition, ASIN: 0534932517,
1993.
[7] BRESCIANI, P.; PERINI, A.; GIORGINI, P.; GIUNCHIGLIA, F.;
MYLOPOULOS, J.. Tropos: An Agent-Oriented Software Development
Methodology. AUTONOMOUS AGENTS AND MULTI-AGENT
SYSTEMS, p.203-236, Volume 8, Issue 3, Maio 2004.
[8] BUSCHMANN, F. et al.. Pattern-Oriented Software Architecture: A
System of Patterns. John Wiley & Sons, 1996.
[9] CASTRO, J.; KOLP, M.; MYLOPOULOS, J.. A Requirements-Driven
Development Methodology. PROCEEDINGS OF THE 13TH
INTERNATIONAL CONFERENCE ON ADVANCED INFORMATION
SYSTEMS ENGINEERING, p.108-123, Lecture Notes In Computer Science,
Vol. 2068, 2001.
[10] CHENG, S-F; LEUNG, E.; LOCHNER, K. M.; O'MALLEY, K.; REEVES,
D. M.; SCHVARTZMAN, L. J.; WELLMAN, M. P.. Walverine: A
Walrasian Trading Agent. PROCEEDINGS OF THE SECOND
INTERNATIONAL JOINT CONFERENCE ON AUTONOMOUS AGENTS
AND MULTI-AGENT SYSTEMS, p.465-472, Melbourne, Australia, Julho
2003.
147
[11] CHOPRA, S.; MEINDL, P.. Supply Chain Management – Strategy,
Planning, and Operations. Pearson Prentice Hall, Second Edition, ISBN 013-101028-X, 2004.
[12] CHOREN, R.. Uma Linguagem de Modelagem para Sistemas Baseados
em Agentes. Tese de Doutorado, Departamento de Informática, PUC-Rio.
Dezembro 2002.
[13] CHOREN, R.; LUCENA, C. J. P.. Modeling Multi-agent Systems with
ANote. JOURNAL ON SOFTWARE AND SYSTEMS MODELING
(SoSyM). DOI: 10.1007/s10270-004-0065-y, ISSN: 1619-1374, 2004a.
[14] CHOREN, R.; LUCENA, C. J. P.. Agent-Oriented Modeling Using ANote.
PROCEEDINGS OF THE THIRD INTERNATIONAL WORKSHOP ON
SOFTWARE ENGINEERING FOR LARGE- SCALE MULTI-AGENT
SYSTEMS (SELMAS 2004 - ICSE), pp. 74-80, The IEEE Computer Society,
2004b.
[15] COMPUTER ASSOCIATES (CA) CleverPath, http://www.ca.com/.
Acessado em 16/02/2005.
[16] CORKILL, D.; GALLAGHER, K.; JOHNSON, P.. Achieving Flexibility,
Efficiency, and Generality in Blackboard Architectures. PROCEEDINGS
OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE
(AAAI-87), pp. 18-23, Seattle, Washington, 1987.
[17] DASH OPTIMIZATION. http://www.dashoptimization.com. Acessado em
16/02/2005.
[18] DELOACH, S. A.. Multiagent Systems Engineering: a Methodology and
Language for Designing Agent Systems. PROCEEDINGS OF THE FIRST
AGENT ORIENTED INFORMATION SYSTEMS WORKSHOP, (AOIS99),
Washington, 1999.
[19] IBM BUSINESS INTELLIGENCE (BI), International Business Machines,
http://www-1.ibm.com/ businesscenter/us/solutions/solutionarea.jsp?id=6169
, Acessado em 16/02/2005.
[20] DO, T.T.; KOLP, M.; HANG HOANG, T.T.; PIROTTE, A.. A Framework
for Design Patterns for Tropos. PROCEEDINGS OF THE 17TH
BRAZILIAN SYMPOSIUM ON SOFTWARE ENGINEERING (SBES
2003), Maunas, Brazil, October 2003.
[21]
DRUCKER, P.. Além da Revolução da Informação. HSM
MANAGEMENT, Savana, ano 3, n. 18, São Paulo, janeiro-fevereiro 2000.
[22] DUDA, R. O.; HART, P. E.: Pattern Classification and Scene Analysis.
John Wiley & Sons, 1973.
[23] FAYAD, M.; SCHMIDT, D.: Building Application Frameworks: ObjectOriented Foundations of Design. First Edition, John Wiley & Sons, 1999.
[24] FERBER, J.: Multi-Agent Systems: An Introduction to Distributed
Artificial Intelligence. Addison-Wesley Pub Co, ISBN: 0201360489, 1999.
[25] FONTOURA, M.F.; HAEUSLER, E.H.; LUCENA, C.J.P. The Hot-Spot
Relationship in OO Framework Design. MCC33/98, Computer Science
Department, PUC-Rio, 1998.
148
[26] FIPA (Foundation for Intelligent Physical Agents) ACL Message Structure,
http://www.fipa.org/specs/fipa00061/.
Acessado
em
Specification,
16/02/2005.
[27] GAMMA, E.; HELM, R.; JOHNSON, R.; VLISSIDES, J.: Design Patterns:
Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.
[28] GARCIA, A; SARDINHA, J.A.R.P.; LUCENA, C.J.P.; LEITE, J.;
MILIDIÚ, R.L.; CASTRO, J.; ROMANOVSKY, A.; GRISS, M.; LEMOS,
R.; PERINI, A.. Software Engineering for Large-Scale Multi-Agent
Systems – SELMAS 2003 (Post-Workshop Report), ACM Software
Engineering Notes, Vol. 28, Number 6, p.1-1, November 2003.
[29] GARCIA, A.. From Objects to Agents: An Aspect-Oriented Approach.
Tese de Doutorado, Departamento de Informática, PUC-Rio, Rio de Janeiro,
Brazil, April 2004a.
[30] GARCIA, A.; KULESZA, U.; SARDINHA, J.A.R.P.; MILIDIÚ, R.L.;
LUCENA, C.J.P.. The Learning Aspect Pattern. THE 11TH
CONFERENCE ON PATTERN LANGUAGES OF PROGRAMS
(PLoP2004),
Allterton
Park,
Monticello,
Illinios,USA,
http://hillside.net/plop/2004/papers/agarcia0/PLoP2004_agarcia0_0.pdf,
September 8 - 12, 2004b.
[31] GIUNCHIGLIA, F.; MYLOPOULOS, J.; PERINI, A.. The tropos software
development methodology: processes, models and diagrams.
PROCEEDINGS OF
THE
FIRST
INTERNATIONAL
JOINT
CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT
SYSTEMS, p.35-36, 2002.
[32] GREENWALD, A.. The 2002 Trading Agent Competition: An Overview of
Agent Designs. AI Magazine, April 2003.
[33] HOWDEN, N.; RONNQUIST, R.; HODGSON, A.; LUCAS, A.. JACK
Intelligent Agents – Summary of an Agent Infrastructure. SECOND
INTERNATIONAL WORKSHOP ON INFRASTRUCTURE FOR
AGENTS, MAS, AND SCALABLE MAS, 5th International Conference on
Autonomous Agents, Canada, 2001.
[34] HORNGREN, C. T.; FOSTER, G.; DATAR, S. M.. Cost Accounting – A
Managerial Emphasis. Prentice Hall, Ninth Edition, ISBN: 0-13-232901-8,
1997.
[35] HUGET, M.-P.. Generating Code for Agent UML Sequence Diagrams.
PROCEEDINGS OF AGENT TECHNOLOGY AND SOFTWARE
ENGINEERING (AgeS), Bernhard Bauer, Klaus Fischer, Jorg Muller and
Bernhard Rumpe (eds.), Erfurt, Germany, October 2002.
[36] KELLER, P.W.; DUGUAY, F.-O.; PRECUP, D.: RedAgent-2003: An
autonomous, market based supply-chain management agent.
PROCEEDINGS OF THE THIRD INTERNATIONAL JOINT
CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT
SYSTEMS (AAMAS’2004), p.1182-1189, July 2004.
[37] KENDALL, E.; KRISHNA, P.; PATHAK, C.; SURESH, C.. A Framework
for Agent Systems. M. Fayad et al. (eds), IMPLEMENTING
149
APPLICATION FRAMEWORKS – OBJECT-ORIENTED FRAMEWORKS
AT WORK, John Wiley & Sons, 1999.
[38] KICZALES, G. et al.. Aspect-Oriented Programming. PROCEEDINGS
OF THE EUROPEAN CONFERENCE ON OBJECT-ORIENTED
PROGRAMMING - ECOOP’97, LNCS (1241), 1997.
[39] KIEKINTVELD, C.; WELLMAN, M. P.; SINGH, S.; SONI, V.. ValueDriven Procurement in the TAC Supply Chain Game, p.9-18, SIGecom
Exchanges, vol.4, 2004.
[40] KLAUS, D.; FRITSCHI, C.. LivingAgents Strategy Description.
Techinical White Paper, Living Systems, http://www.living-systems.com/,
2001.
[41] KUDENKO, D.; KAZAKOV, D.; ALONSO, E.. Machine Learning for
Agents and Multi-Agent Systems. Plekhanova, V. (ed.) INTELLIGENT
AGENT SOFTWARE ENGINEERING. Idea Group Publishing, 2003.
[42] LEBART, L.; MORINEAU, A.; PIRON, M.. Statistique exploratoire
multidinensionnelle, Dunod, Paris, 1997.
[43] LIVING SYSTEMS & WHITESTEIN TECHNOLOGIES web site.
http://www.livingAdvanced
software
agent
technologies.
systems.com/pages/index.html , Acessado em 16/02/2005.
[44] LUCENA, C.J.P.; SARDINHA, J.A.R.P.; GARCIA, A.F.; CASTRO, J.;
ROMANOVSKY, A.; ALENCAR, P.; COWAN, D.. Software Engineering
for Large-Scale Multi-Agent Systems – SELMAS 2003. PROCEEDINGS
OF THE IEEE/ACM INTERNATIONAL CONFERENCE ON SOFTWARE
ENGINEERING (ICSE 2003), p.771 - 772, Portland, USA, May 2003.
[45] MILIDIU, R.L.; LUCENA, C.J.P.; SARDINHA, J.A.R.P.: An objectoriented framework for creating offerings. PROCEEDINGS OF THE 2001
INTERNATIONAL CONFERENCE ON INTERNET COMPUTING
(IC'2001), p. 119-123, CSREA Press, v.1, June 2001.
[46] MILIDIU, R.; MELCOP, T.; LIPORACE, F.; LUCENA, C.: Multi-Agent
Strategy for Simultaneous and Related Auctions. ANAIS DO XXIII
CONGRESSO DA SOCIEDADE BRASILEIRA DE COMPUTAÇÃO - IV
ENIA, Campinas, SP, Brasil, pp. 597-606, 2003a.
[47] MILIDIU, R.; MELCOP, T.; LIPORACE, F.; LUCENA, C.: SIMPLE - A
Multi-Agent System for Simultaneous and Related Auctions. 2003
IEEE/WIC International Conference on Intelligent Agent Technology,
Halifax, Canada, pp. 511-515, 2003b.
[48] MILIDIU, R.; MELCOP, T.; LIPORACE, F.; LUCENA, C.. Multi-Agent
Strategy for Simultaneous and Related Auctions, pp 155-170, SCIENTIA,
vol. 14, nº 2, 2003c.
[49] MILIDIU, R. L.; RENTERÍA, R. P.. DPLS and PPLS: two PLS algorithms
for large data sets, p.125-138, COMPUTATIONAL STATISTICS & DATA
ANALYSIS, 48, 2005.
[50] MITCHELL, T. M.. Machine Learning. McGraw-Hill, ISBN: 0070428077,
1997.
150
[51] PADGHAM, L; WINIKOFF, M.. Prometheus: A Methodology for
Developing Intelligent Agents. PROCEEDINGS OF THE FIRST
INTERNATIONAL JOINT CONFERENCE ON AUTONOMOUS AGENTS
AND MULTI-AGENT SYSTEMS, p.37-38, Italy, 2002a.
[52] PADGHAM, L; WINIKOFF, M.. Prometheus: A pragmatic methodology
for engineering intelligent agents. PROCEEDINGS OF THE WORKSHOP
ON AGENT-ORIENTED METHODOLOGIES, OOPSLA, Seattle,
November 2002b.
[53] RIBEIRO, P.C.. Modelagem e Implementação OO de Sistemas MultiAgentes. Dissertação de Mestrado, Departamento de Informática, PUC-Rio,
2001.
[54] ROSENBLATT, F.. The Perceptron: a probabilistic model for
information storage and organization in the brain, p.386-408,
PSYCHOLOGICAL REVIEW, 65, 1959.
[55] RUSSELL, S.; NORVIG, P.. Artificial Intelligence. Prentice Hall, ISBN 013-103805-2, 1995.
[56] SARDINHA, J.A.R.P.. VGroups – Um framework para grupos virtuais
de consumo. Dissertação de Mestrado, Departamento de Informática – PUCRio, March 2001.
[57] SARDINHA, J.A.R.P.; RIBEIRO, P.C.; LUCENA, C.J.P; MILIDIÚ, R.L..
An Object-Oriented Framework for Building Software Agents. Journal of
Object Technology, p. 85-97, Vol. 2, No. 1, January - February 2003a.
[58] SARDINHA, J.A.R.P.; MILIDIÚ, R. L.; LUCENA, C. J. P.; PARANHOS,
P. M.. An OO Framework for building Intelligence and Learning
properties in Software Agents. PROCEEDINGS OF THE 2ND
INTERNATIONAL WORKSHOP ON SOFTWARE ENGINEERING FOR
LARGE-SCALE MULTI-AGENT SYSTEMS (ICSE 2003), p.30-36,
Portland, USA, , May 2003b.
[59] SARDINHA, J.A.R.P.; CHOREN, R.; MILIDIÚ, R.L.; LUCENA, C.J.P..
Engineering Machine Learning Techniques into Multi-Agent Systems.
Technical Report, Computer Science Department, PUC-Rio, Brazil. PUCRioInf.MCC12/04, May 2004a.
[60] SARDINHA, J.A.R.P.; GARCIA, A.F.; LUCENA, C.J.P.; MILIDIÚ, R.L..
On the Incorporation of Learning in Open Multi-Agent Systems: A
Systematic
Approach.
PROCEEDINGS
OF
THE
SIXTH
INTERNATIONAL BI-CONFERENCE WORKSHOP ON AGENT
ORIENTED INFORMATION SYSTEMS at CAiSE 2004, Riga, Latvia, p.
309-324, Jun 2004b.
[70] SARDINHA, J.A.R.P.; MILIDIÚ, R.L.; LUCENA, C.J.P.; PARANHOS,
P.M.; CUNHA, P.M.. LearnAgents - A multi-agent system for the TAC
Classic. POSTER SESSION AT THE TRADING AGENT COMPETITION
(THE THIRD INTERNATIONAL JOINT CONFERENCE ON
AUTONOMOUS AGENTS & MULTI AGENT SYSTEMS), New York,
USA, July 2004c.
151
[71] SARDINHA, J.A.R.P.; GARCIA, A.F.; MILIDIÚ, R.L.; LUCENA, C.J.P..
The Agent Learning Pattern. PROCEEDINGS OF THE FOURTH LATIN
AMERICAN CONFERENCE ON PATTERN LANGUAGES OF
PROGRAMMING,
SugarLoafPLoP'04,
Fortaleza,
Brazil,
http://sugarloafplop2004.ufc.br/acceptedPapers/index.html, August 2004d.
[72] SARDINHA, J.A.R.P.; MILIDIÚ, R.L.; PARANHOS, P.M.; CUNHA, P.M.;
LUCENA, C.J.P.. An Agent Based Architecture for Highly Competitive
Electronic Markets. THE 18TH INTERNATIONAL FLAIRS
CONFERENCE (The Florida Artificial Intelligence Research Society).
Clearwater Beach, Florida, USA, May 16-18, 2005a.
[73] SARDINHA, J.A.R.P.; GARCIA, A.F.; LUCENA, C.J.P.; MILIDIÚ, R.L.. A
Systematic Approach for Including Machine Learning in Multi-Agent
Systems. AGENT-ORIENTED INFORMATION SYSTEMS. Revised
Selected Papers from Workshop AOIS 2004. Published by Springer-Verlag,
Lecture Notes in Artificial Intelligence, May 2005b.
[74] SARDINHA, J.A.R.P.; CHOREN, R.; SILVA, V.; LUCENA, C.J.P.;
MILIDIÚ, R.L.. A Combined Specification Language and Development
Framework for Agent-based Application Engineering. Technical Report,
Computer Science Department, PUC-Rio, Brazil. PUC-RioInf.MCC05/05,
February 2005c.
[75] SEN, S.; WEISS, G.. Learning in Multiagent Systems. G. Weiss (ed.),
MULTIAGENT SYSTEMS: A MODERN APPROACH TO DISTRIBUTED
ARTIFICIAL INTELLIGENCE, The MIT Press, Second printing, 2000.
[76] SILVA, O.; GARCIA, A.; LUCENA, C.J.P.. T-Rex: A Reflective Tuple
Space Environment for Dependable Mobile Agent Systems. III WCSF at
IEEE MWCN 2001, Recife, Brasil, August 2001.
[77] SOLVER.COM - FRONTLINE SYSTEMS, Inc.. Solver Tutorial for
Optimization Users. http://www.solver.com/tutorial.htm. Acessado em
16/02/2005.
[78] STONE, P.; LITTMAN, M.; SINGH, S.; KEARNS, M.. ATTac-2000: An
Adaptative Autonomous Bidding Agent. JOURNAL OF ARTIFICIAL
INTELLIGENCE RESEARCH, p.189-206, 15, 2001.
[79] STONE, P.; SCHARPIRE, R.; CSIRIK, J.; LITTMAN, M.; MCALLESTER,
D.. ATTac-01: A learning, autonomous bidding agent. WORKSHOP ON
AGENT MEDIATED ELETRONIC COMMERCE IV: DESIGNING
MECHANISMS AND SYSTEMS, 2002.
[80] TAC web site.: http://www.sics.se/tac. Acessado em 16/02/2005.
[81] TALUKDAR, S.; SACHDEV, S.; CAMPONOGARA, E.. A Collaboration
Strategy for Autonomous, Highly Specialized Agents. PROCEEDINGS
OF THE SPIE, SYMPOSIUM ON INTELLIGENT SYSTEMS &
ADVANCED MANUFACTURING, October 1997.
[82] TELECOM ITALIA LAB JADE, Java Agent Development Framework
Programmer's
Guide.
http://sharon.cselt.it/projects/jade/doc/
programmersguide.pdf, Feb. 2003.
152
[83] TSPACES, IBM, http://www.almaden.ibm.com/cs/TSpaces/ . Acessado em
16/02/2005.
[84] VETSIKAS, I. A.; SELMAN, B.. A principled study of the design
tradeoffs for autonomous trading agents. PROCEEDINGS OF THE
SECOND INTERNATIONAL JOINT CONFERENCE ON AUTONOMOUS
AGENTS AND MULTI-AGENT SYSTEMS, p.473-480, Melbourne,
Australia, July 2003.
[85] WELLMAN, M. P.; WURMAN, P. R.; O'MALLEY, K.; BANGERA, R.;
LIN, S.; REEVES, D.; WALSH, W. E.. Designing the Market Game for a
Trading Agent Competition. IEEE Internet Computing, Vol. 5, No. 2, pp.
43-51, March/April 2001.
[86] WINSTON, P.H. Artificial Intelligence. Addison Wesley, 1992.
[87] WOOLDRIDGE, M.. Intelligent Agents. G. Weiss (ed.), MULTIAGENT
SYSTEMS: A MODERN APPROACH TO DISTRIBUTED ARTIFICIAL
INTELLIGENCE. The MIT Press, Second printing, 2000.
[88] WOOLDRIDGE, M.; JENNINGS, N. R.; KINNY, D.. The Gaia
methodology for agent-oriented analysis and design. JOURNAL DO
AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS, p.285-312,
v.3, 2000.
[89] WOLSEY, L. A.. Integer Programming. Wiley-Interscience publication.
ISBN: 0-471-28366-5. 1998.
[90] ZAMBONELLI, F.; JENNINGS, N. R.; WOOLDRIDGE, M.. Developing
multiagent systems: the Gaia Methodology. ACM TRANSACTIONS ON
SOFTWARE ENGINEERING AND METHODOLOGY, p.317-370, 12 (3),
2003.

Paper 3 - (LES) da PUC-Rio

Transcrição

Documentos relacionados

Victor Japiassú dos Santos Rêgo

programação - nirema - PUC-Rio

na PUC-Rio

Certificação do Google AdWords

Ler mais - Tecgraf - PUC-Rio

Globalização e sociedade de controle - Maxwell - PUC-Rio

Múmia de Sha-amun-em-su estudada pela equipe do Seshat

2009 – Carta para as listas – LF Cidadão do Mundo

Nara Lissia Katsuki Giraldi O Gerenciamento do Capital

Certificação e Qualidade