Programação Orientada a Agentes
e
Sistemas Multiagentes
1
Conteúdo
•
•
•
•
•
•
•
•
•
Motivação
Exemplos de sistemas multiagentes
Sistemas multiagentes estritamente cooperativos
Sistemas multiagentes intermediários
Sistemas multiagentes estritamente não-cooperativos
Aplicações
Balanço geral
Conclusão
Referências
2
O que é um procedimento/função?
• Um procedimento é uma abstração de um comando e é
caracterizado por:
– realizar operações que modificam o estado do sistema;
• Uma função é uma abstração e uma expressão e é
caracterizada por:
– Realizar alguma operações sobre ‘valores’ e devolver um
‘resultado’
• Ambos são metáforas de modelagem
3
O que significa dizer que um sistema é
estruturado? Como reconhecemos um sistema
estruturado?
• Utiliza como metáfora de modelagem procedimentos e
funções
• Utiliza metodologia de desenvolvimento estruturada
• Utiliza ferramentas implementação estruturadas
4
O que é um objeto?
• É uma entidade de abstração caracterizada por:
– Encapsulamento/information hidding;
– Capacidade de relacionamentos com outros objetos de
herança/agregação
– Comunica-se através do envio de mensagens
• É uma junção das abstrações de comando, expressão e
declaração
5
O que significa dizer que um sistema é orientado a
objetos? Como reconhecemos um sistema
orientado a objetos?
• Utiliza objetos como metáfora de modelagem
• Utiliza metodologia de desenvolvimento orientada à objetos;
• Utiliza ferramentas implementação orientadas à objetos
6
Um sistema concebido de forma orientada a
objetos pode ser também concebido de forma
estruturada?
Um sistema concebido de forma orientada a
objetos pode ser implementado de forma
estruturada?
7
O que é um agente?
• É uma entidade de abstração caracterizada por:
–
–
–
–
–
–
Autonomia;
Racionalidade (busca sempre atingir seus objetivos);
Capacidade social (interação com outros agentes);
Reatividade;
Pro-atividade;
Mobilidade;
8
O que significa dizer que um sistema é “orientado
a agentes”? Como reconhecemos um sistema
“orientado a agentes”?
• Utiliza o agente como metáfora de modelagem
• Utiliza metodologia de desenvolvimento orientada à agentes
9
Caracterização de um sistema
• Linguagem de Implementação?
• Abstração utilizada na modelagem?
• Metodologia de desenvolvimento?
10
POO X POA
POO
Unidade básica Objeto
Parâmetros
Nenhum
definindo o
estado da
unidade básica
Processo
Envio de
computacional mensagens e
resposta a
métodos
Tipo de
Sem restrições
mensagem
Restrição nos
métodos
Nenhuma
POA
Agente
Crenças,
compromissos,
capacidades,...
Envio de
mensagens e
resposta a
métodos
Com restrições
(informar,
requerer,
perguntar,...)
Consistência
11
Desenvolvimento orientado a objetos
• Busca:
–
–
–
–
Definição das entidades que serão representadas no sistema;
Definição das funcionalidades que estão associadas a cada entidade;
Definição dos objetos e relacionamentos de agregação e herança;
Definição de atributos e métodos.
12
Desenvolvimento orientado a agentes
• Busca:
–
–
–
–
Definição das entidades que serão representadas no sistema (domínio);
Definição das percepções e ações que cada agente pode realizar;
Definição de crenças e objetivos.
Definição dos relacionamentos de comunicação entre os agentes
(estabelecer protocolos);
13
Sistemas Multi-Agentes
Inteligência solitária ou coletiva?
14
Porque Distribuir a IA?
Razões segundo as comunidades...
• De Ciências humanas: As capacidades intelectuais provêm
– disposições genéticas, interações com os semelhantes e com o ambiente
• Da psicologia: O ser humano
– faz raciocínios em paralelo, tem mais de uma opinião ou ponto de vista
sobre uma coisa
• De IA:
– adicionar a dimensão sociológica à psicológica já existente
• Da resolução de problemas
– há problemas funcionalmente ou espacialmente distribuídos e há
problemas complexos demais
• Da indústria
– poder trabalhar com vários especialistas com pontos de vista diferentes
• De informática
– extensão da noção de (multi)objetos
15
Sendo assim, temos...
Metáfora para modelagem
Objeto
Desenvolvimento OO
Sistema “Multiobjetos”
Agente
Desenvolvimento OA
Sistema “Multiagentes”
Agente = Objeto com intencionalidade
16
Exemplo de sistema
• Sistema de Fornecimento de Água para Caldeiras - Resolução
Distribuída de Problemas
– O importante é atingir o objetivo global;
– As tarefas são pré-definidas
– A ênfase é dada na modelagem de cada agente
– Usualmente não existe grande comunicação entre os agentes;
– Existe um controle global
Data
Acquisition
Agent
Tracking
Agent
Monitoring
Agent
Knowledge
broker
HCI
Agent
Diagnostic
Agent
Information
Repository
Verification
Agent
17
Exemplo de sistemas
• Formigueiro - Sistema Multiagentes Reativo
– O mais importante é o problema;
– O problema é resolvidos por nós individuais que interagem entre si;
– Existe um grande número de nós;
– Os nós são normalmente são idênticos e possuem conhecimento
limitado;
– Cada nós não tem consciência do problema geral;
– Os nós ‘cooperam’ entre si;
– A solução ‘surge’ através das interações entre os nós.
18
Exemplo de sistemas
• Time de Futebol - Sistema Multiagentes Cognitivo Cooperativo
– Cada jogador possui um conhecimento individual e limitado;
– Cada jogador não pode resolver o problema sozinho;
– Cada jogador pode ter características diferentes dos demais;
– Cada jogador age de forma autônoma e assíncrona;
– Existe um objetivo global que é de conhecimento de todos os indivíduos;
– Este objetivo global está acima dos objetivos individuais de cada agente;
– Não existe um controle global;
– A junção das capacidades individuais resolve o problema.
19
Exemplo de sistemas
• Negociação trabalhista - Sistema Multiagentes Cognitivo NãoCooperativo
– Os objetivos de cada parte são usualmente contrapostos;
– A informação de cada parte é incompleta;
– Existe um objetivo global desejado, mas que não é mais importante que
os objetivos individuais;
– Cada parte procura convencer seu oponente para que ele ceda (ocorre
um processo de negociação);
– Não da para ter certeza sobre o que a outra parte vai fazer;
– Não existe um controle centralizado do processo;
20
Historicamente
• Existe uma diferenciação entre um sistema desenvolvido como um
DPS e como um MAS.
• Alguns pesquisadores consideravam que DSP é uma sub-área de
MAS, e outros consideravam o inverso.
• Nos dias atuais existe um tendência a considerar tudo como MAS
• A diferença entre os sistemas agora está:
– Na distribuição do conhecimento;
– Na existência ou não de um objetivo global;
– Se o objetivo global existir, qual o grau de compromisso que que cada
agente tem com ele, quando confrontado com os seus objetivos
individuais?
22
Taxonomia Anterior
IA
IA convencional
IA Distribuída
DPS
Outros
MAS
Reativo
Cognitivo
Não-cooperativo
Cooperativo
23
Taxonomia ‘Moderna’
IA
IA convencional
IA Distribuída
Outros
MAS
Classificações Intermediárias
Estritamente Cooperativo
Estritamente Não- Cooperativo
24
Problemas dos MAS
•
•
•
•
•
•
Como descrever e alocar as entidades de um problema em tre os agentes do
sistema?
Como habilitar os agentes para se comunicar e interagir? Que linguagem de
comunicação utilizar?
Como garantir que os agentes vão agir de forma coerente, sem provocar
efeitos indesejáveis? (Dilema do prisioneiro)
Como habilitar os agentes para representar e raciocinar sobre as ações de
outros agentes para conseguir se coordenar com eles?
Como gerenciar a limitação de recursos de cada agente?
Como construir um MAS de forma efetiva? Como definir plataformas
tecnológicas e metodologias de desenvolvimento?
25
Processo de Desenvolvimento de um MAS
• Similar a divisão-e-conquista;
• Busca-se definir:
– Quem são os agentes
– Protocolo de comunicação entre os agentes (redes de contrato)
– Regras de funcionamento de cada agente (Relações entre: crenças,
percepções e ações)
Ask(agent(ID), product(nome(“CD”), autor(“Chico Buarque”) ))
Products(Autor(“Chico Buarque”), [CD(...),CD(...)])
26
Jogos dos 8 Números
•
•
H
E
A
B
F
D
C
G
Objetivo: Colocar as letras em ordem alfabética no menor tempo
possível
Este problema é np-completo
27
Jogos dos 8 Números
• Considerando cada agente como uma peça, temos que:
–
–
–
–
Cada agente tem como objetivo ir para a sua posição;
Cada agente sabe a sua posição atual e pode estar ou não ativo;
Apenas um agente está ativo de cada vez (A, em seguida B, etc.)
Cada agente pode:
•
•
•
•
‘Atacar’ um outro agente;
Fugir quando for atacado;
A fuga só pode ocorrer quando o agente não estiver bloqueado;
Percorrer o caminho padrão, mesmo estando em sua posição.
28
Jogos dos 8 Números
• O protocolo de comunicação é:
–
–
–
–
Ataque: ataque (atacante(...), posição_atacado(...))
Fuga: Fugir (posição_fuga(...))
Bloqueado: Block (atacante(...))
PercorrerCaminhoPadrão();
29
Jogos dos 8 Números
E
B
A
F
C
H
D
G
Bloqueado
Ativo
30
Jogos dos 8 Números
E
B
A
F
C
H
D
G
Bloqueado
Ativo
31
Jogos dos 8 Números
B
C
E
A
H
F
D
G
Ativo
32
Jogos dos 8 Números
B
C
A
E
H
G
F
D
Ativo
33
Jogos dos 8 Números
A
E
Bloqueado
Ativo
B
C
G
H
F
D
Resultados Obtidos com MAS: 30X30
Resultados com técnicas normais: 5X5
34
Task Allocation Problem
• Objetiva minimizar a interdependência de tarefas
– Diminuir o overhead de comunicação
– Aumentar as chances de se encontrar uma solução consistente
• Este foi um dos primeiros problemas atacados pela IA distribuída com
o Contract Net Protocol (CNP).
35
Task Allocation Problem
- Contract Net Protocol • Cada agente pode assumir dois papéis
– Gerente
– Contratante
• Dada uma tarefa, o agente (contratante) determina se esta pode ser
quebrada em sub-tarefas concorrentes.
• Ele usa o protocolo para anunciar as sub-tarefas para os outros
agentes (Gerentes) e esperar por ofertas.
• O contratante recebe as ofertas feitas, escolhe a melhor e anuncia o
vencedor;
• O vencedor pode então, se quiser, ver se esta tarefa pode ser
subdividida, e se tornar um Contratante.
36
Task Allocation Problem
1
2
3
4
5
Objetivo: Levar o conjunto de blocos para o ponto 5 na mesma ordem.
Regras: - Só se pode mover um bloco de cada vez;
- Cada bloco só pode se mover para o posição imediatamente
ao lado
37
Task Allocation Problem
•
•
Cada agente pode assumir a tarefa de levar um número x de blocos, e, se não
conseguir, ele pode subdividir esta tarefa e esperar ‘ofertas’.
Tomando um conjunto de n agentes e de 3 problemas, temos:
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
38
Task Allocation Problem
•
Como existem vários problemas paralelos:
– Cada agente precisa ver se pode ou não assumir uma tarefa;
– Decidir que tipo de tarefa ela vai poder assumir (número de blocos)
– Decidir se deve ou não subdividir a tarefa que recebeu;
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
39
Aplicações
• PDA (Personal Digital Assistant);
– Assistentes para análise de e-mails;
– Assistentes para organização de agenda de horários;
•
•
•
•
•
•
•
Controle de tráfego aéreo;
Comércio eletrônico;
Jogos com Personagens;
Histórias Interativas;
Busca na Internet;
Sistemas de Controle (tempo real);
Sistemas de Telefonia
40
Balanço geral
• Vantagens
– Robustez;
– Eficiência;
– Possibilidade de resolver problemas mais complexos;
• Desvantagens
– Falta uma metodologia de desenvolvimento bem definida;
– Sobrecarga de comunicação;
– Maior complexidade do “paradigma” de desenvolvimento
41
Concluindo
O que significa dizer que um determinado problema
pode ser melhor resolvido com uma abordagem
multiagentes?
42
Quando usar...
• Problema complexo
– divide and conquer
– ex. jogo dos 8 números, ordenação, etc.
• Problema intrinsecamente distribuído
– ex. jogos com personagens, administração de sistemas, controle de
tráfego, etc.
• Problemas exigindo rápido tempo de resposta
– processamento paralelo
– ex. busca na internet, grupo musical, etc.
• Problema com domínios de conhecimento ou tarefas
– um agente para cada tipo de conhecimento/tarefa
– ex. usina nuclear
43
Depois de descobrir que deve usar, o que
fazer?
• Utilizando linguagens OO convencionais + Bibliotecas adicionais
– Para comunicação: JATLite (KQML), FIPA;
– Para raciocínio
• Motores de inferência lógica: JEOPS, ABE, JESS, CLIPS
• Motores de inferência bayesiana: Hugin, MSBN;
• Redes neurais;
– Para mobilidade: Aglets, Telescript, etc.
• Utilizar ambientes de desenvolvimento
– Agent Builder
• Utilizar linguagens orientadas a agentes:
– Agents0, Jackal, etc.
44
FIM
45