Arquitetura de
Multi-Agentes
IA Simbólica
Prof. Jacques Robin
Ryan Leite Albuquerque
Luiz Carlos Barboza Júnior
Arquitetura de Multi-Agentes
1 / 55
Roteiro
 Arquiteturas Para Agentes Inteligentes
 Abstratas

Concretas
Arquitetura de Multi-Agentes
2 / 55
Arquiteturas para Agentes Inteligentes
 Introdução
 Arquiteturas Abstratas
 Agentes Puramente Reativos

Agentes com Estado
 Arquiteturas Concretas
 Arquiteturas Baseadas em Lógica

Arquiteturas Reativas

Arquiteturas Baseadas em Crenças, Desejos e Intenções

Arquiteturas Baseadas em Camadas
Arquitetura de Multi-Agentes
3 / 55
Ambientes, estados e ações
 Formalização da abstração de agentes
 S = {s1, s2, ...}
// environment states

A = {a1, a2, ...}
// actions
 Agente Padrão:
 action : S*  A
 Ambiente:
 env : S x A  (S)

Determinístico: se (S) é unitário

Não Determinístico
Arquitetura de Multi-Agentes
4 / 55
Históricos
 Agente x Ambiente (History)
 h : s0 (a0) s1 (a1) … (au-1) su (au) ...

History (Ag,Env)
- au é a ação escolhida, dados todos os estados do ambiente
até su
- su é um dos estados retornados pela aplicação de au-1 ao
estado atual do ambiente (su-1)
 Comportamento característico de um agente em um
ambiente é o conjunto de todas os históricos que
satisfazem action e env
Arquitetura de Multi-Agentes
5 / 55
Introdução
 Se uma propriedade p é válida para todos os históricos,
ela é chamada de propriedade invariante do agente
naquele ambiente
 Equivalência de comportamento:
 hist(ag1, env) = hist(ag2, env)
- …com relação a um ambiente env

hist(ag1, _) = hist(ag2, _)
- …com relação a todos os ambientes
 Estamos interessados em históricos infinitos
 A interação (agente x ambiente) não tem fim !!
Arquitetura de Multi-Agentes
6 / 55
Arquiteturas Abstratas
Agentes Puramente Reativos
Percepção
Agentes com Estado
Arquitetura de Multi-Agentes
7 / 55
Agentes Puramente Reativos
 Não fazem referência a um histórico
 Baseam suas tomadas de decisão somente no presente
 action : S  A

Agentes Puramente Reativos x Agente Padrão
 Exemplo de Agente Puramente Reativo:
 A função de ação de um termostato:
heater off, if s = temperature OK

action(s) =
heater on, otherwise
Arquitetura de Multi-Agentes
8 / 55
Percepção
 Como implementar action ??
 Refinamento do modelo abstrato de agentes
 Dividir em subsistemas

Decisões de projeto
- Estruturas de Dados e
- Estruturas de Controle
see
action
Agente
 Função de Decisão do Agente é decomposta
em:
 Percepção ( see : S  P )

Ação ( action : P*  A )
Arquitetura de Multi-Agentes
Ambiente
9 / 55
Percepção
 Observações interessantes
 Suponha s1,s2  S e s1 != s2, mas see(s1) = see(s2)
- O agente recebe a mesma percepção para dois estados
diferentes do ambiente
Conjunto de estados indistinguíveis
 Seja s1,s2  S. s1  s2 se see(s1) = see(s2)

- A relação de equivalência divide S em conjuntos de estados
mutuamente indistinguíveis
- Quanto mais grosseira é essa equivalência, menos eficiente
será a percepção do agente

Se |  | = |S|, o agente poderá distinguir todos os estados

Se |  | = 1, o agente não tem habilidade de percepção
Arquitetura de Multi-Agentes
10 / 55
Agentes com Estado
 Temos pensado em agentes que têm seu processo de
tomada de decisão baseado em históricos

Não intuitivo
 Estamos tratando agora de agentes que detêm uma
estrutura de dados interna que armazenam:

Estados do ambiente

Históricos
 ... onde é baseado, pelo menos em parte, o processo de
tomada de decisão
Arquitetura de Multi-Agentes
11 / 55
Agentes com Estado
 see : S  P
 inalterado
 action : I  A
Agente
see
action
next
state
Ambiente
 next : I x P  I
 Adicionado

percepções alteram o estado interno
Arquitetura de Multi-Agentes
12 / 55
Arquiteturas Concretas
Arquiteturas Baseadas em Lógica
Arquiteturas Reativas
Arquiteturas Baseadas em Crenças, Desejos e Intenções
Arquiteturas Baseadas em Camadas
Arquitetura de Multi-Agentes
13 / 55
Arquiteturas Baseadas em Lógica
 De acordo com a IA Simbólica, o comportamento
inteligente pode ser gerado em um sistema, quando é
dado a ele :

Uma representação simbólica do ambiente;

Uma representação simbólica dos comportamentos
desejáveis

Uma manipulação sintática dessas representações
 Representação Simbólica
 Fórmulas da Lógica
 Manipulação Sintática
 Dedução e Prova de Teoremas
Arquitetura de Multi-Agentes
14 / 55
Arquiteturas Baseadas em Lógica
 Um conjunto de teorias sobre uma agência que explica
como os agentes devem se comportar, podem ser vistas
como especificações
 Essas especificações são refinadas até poderem ser
implementadas
 Na visão de agentes como provadores de teoremas,
essas teorias são planos executáveis
 Agentes Deliberativos
 O estado interno é um banco de dados D de fórmulas da
lógica clássica de primeira ordem
Arquitetura de Multi-Agentes
15 / 55
Arquiteturas Baseadas em Lógica
 O processo de tomada de decisões é modelado através
de um conjunto de regras dedutivas:
D |-r f
Banco de Dados de Fórmulas
Fórmula da Lógica
Regras Dedutivas
Arquitetura de Multi-Agentes
16 / 55
Arquiteturas Baseadas em Lógica
 see : S  P
 next : D x P  D
 action : D  A
 derivado em termos de regras dedutivas
Banco de Dados de Fórmulas
 juntar com 15
Fórmula da Lógica
Regras Dedutivas
Arquitetura de Multi-Agentes
17 / 55
O Mundo do Aspirador de Pó
 Funções Possíveis
 forward

suck

turn (90°)
Área suja!!
(0,2)
 Predicados do Domínio
 in(x,y)
(0,1)
dirt(x,y)

facing(d)
(2,2)
(2,1)
Fórmula da Lógica
Banco de Dados de Fórmulas

(1,2)
(0,0)
Arquitetura de Multi-Agentes
(1,0)
(2,0)
Regras Dedutivas
18 / 55
O Mundo do Aspirador de Pó
 A função next será decomposta em duas
 old(D)

new : D x P  D

Assim, next(D, p) = ( D \ old(D) )  new(D, p)
 As regras...
 in(x,y)  dirt(x,y)  do(suck)
Banco de Dados de Fórmulas
- Prioridade máxima
Fórmula da Lógica
Regras Dedutivas

in(0,0)  facing(north)  !dirt(0,0)  do(forward)

in(0,1)  facing(north)  !dirt(0,1)  do(forward)

in(0,2)  facing(north)  !dirt(0,2)  do(turn)

in(0,2)  facing(east)  do(forward)
Arquitetura de Multi-Agentes
19 / 55
Voltando...
 Fazer agentes dessa maneira é quase impraticável
 Ambiente não-determinístico
- Não podemos garantir a otimalidade das ações escolhidas

Representação lógica de percepções do ambiente pode
ser não trivial ex,

Representação de propriedades dinâmicas de ambientes
reais também é não trivial ex,

Lógica freqüentemente inadequada para:
- representar percepções (ex, extraída de câmera)
- raciocinar em tempo real
Arquitetura de Multi-Agentes
20 / 55
Arquiteturas Reativas
 Abordagens alternativas
 Comportamental: Desenvolver e combinar
comportamentos individuais
 Situado: agentes estão realmente situados em algum
ambiente
 Reativo: não raciocina sobre o ambiente, só reage a ele
 hierarquia de comportamentos
 Comportamento de realização de tarefas
 Cada comportamento é como uma função de ação
separada
 Vários comportamentos podem estar rodando
simultaneamente
 Inibição de comportamentos por níveis de prioridade 

Arquitetura
de Multi-Agentes
Por exemplo, um
robô
móvel deve ter como prioridade21 / 55
Arquiteturas Reativas
 A função see permanece inalterada
 Função action = conjunto de comportamentos +
relação de inibição
 Comportamento = (c,a)
 c é um conjunto de percepções (condições)
 a é uma ação
 dispara quando: o ambiente está no estado s e see(s) 
c
 exceto se existe outro comportamento disparável com
maior prioridade
Arquitetura de Multi-Agentes
22 / 55
Arquiteturas Reativas
 Exemplo: Comportamento instintivo das formigas

adicionar transparência sobre o exemplo das formigas
 Vantagens

Simplicidade, Economia, Tratável Computacionalmente,
Robustez Contra Falhas
 Problemas ainda não resolvidos




Visão limitada ao ambiente local
Aprendizado com experiências (performance)
Desenvolvimento puramente empírico sem princípios
metodológicos
O comportamento global emana de interações entre agentes e
o ambiente complica o entendimento profundo do
funcionamento do sistema
Arquitetura de Multi-Agentes
23 / 55
Arquiteturas Baseadas em
Crenças, Desejos e Intenções
 Processo de raciocínio
prático
BRF
Sensor
Crenças
Gerador de Opções
Desejos
Filtros
Intenções
Ações
Arquitetura de Multi-Agentes
Ação
24 / 55
Arquiteturas Baseadas em
Crenças, Desejos e Intenções
 Processo de Decisão
 Análise das opções de ações disponíveis

Opções selecionadas tornam-se intenções
 Intenções
 Guiam o raciocínio Meios-Fins para escolher ações
 Relacionadas com crenças sobre o futuro
 Persistem
- suficientemente para alcançar algum objetivo (saber
perseverar)
- não eternamente (saber desistir)
- duas razões para abandonar intenção:

objetivo inalcançável

objetivo tornou-se irrelevante
Arquitetura de Multi-Agentes
25 / 55
Arquiteturas Baseadas em
Crenças, Desejos e Intenções
 Quando reconsiderar suas intenções (parar para
pensar)?

Balanceamento de comportamentos pro-ativos
(direcionado a objetivo) e reativos (dirigidos a eventos)
 Agentes arrojados
 Nunca param para reconsiderar

Próprios para ambientes que não mudam rapidamente
 Agentes prudentes
 Para constantemente para reconsiderar

Próprios para ambientes que exigem a habilidade de
identificar quando as intenções estão condenadas
(ambientes com taxa de mudança muito alta)
Arquitetura de Multi-Agentes
26 / 55
Arquiteturas Baseadas em
Crenças, Desejos e Intenções
 Vantagens
 Intuitiva
- Decisão do que fazer
- Decisão de como fazer
- Noções de crenças, desejos e intenções

Decomposição funcional em subsistemas
 Desvantagem
 Dificuldade de saber como implementar eficientemente
essas funções ou subsistemas
Arquitetura de Multi-Agentes
27 / 55
Arquiteturas Baseadas em Camadas
 É atualmente a mais popular classe de arquiteturas de
agentes disponível !!
 Para que um agente tenha comportamentos reativos e
pró-ativos, devemos criar dois subsistemas para tratar
cada um
 Os subsistemas são arrumados em camadas que
interagem entre si
 No mínimo 2 camadas (reativos + pró-ativos)
 Fluxo de Control
 Camadas Horizontais
 Camadas Verticais
Arquitetura de Multi-Agentes
28 / 55
Camadas Horizontais: juntar com 31
 Camadas Horizontais
Camada n
...
Input
Output
Camada 2
Camada 1
Arquitetura de Multi-Agentes
29 / 55
Camadas Horizontais
 Cada camada está conectada com…
 Sensores (entrada)
 Ações (saída)
 Conceitualmente simples
 Uma camada para cada comportamento desejado
 Problema
 Concorrência de camadas confundir o agente que gerará
ações globais as vezes não coerente
 Solução
- Mediador: camada de controle por tempo
- Gargalo!!
Arquitetura de Multi-Agentes
30 / 55
Camadas Verticais
 Dois passos de controle
Camada n
...
Camada 2
Camada 1
Input
Arquitetura de Multi-Agentes
Output
31 / 55
Camadas Verticais
 Entrada e saída estão conectadas a no máximo uma
camada cada
 Dois passos de controle
 Modelo hierárquico de organizações
- Informações 
- Comandos 

Ex.: Jörg Müller’s INTERRAP
Arquitetura de Multi-Agentes
32 / 55
Arquitetura CMUnited-98
 Ambiente com sincronização periódica entre membros
de times de agentes
 Visão Geral da Arquitetura
 Estrutura do Trabalho em Equipe
 Paradigma de Comunicação
 Implementação
 Resultados
Arquitetura de Multi-Agentes
33 / 55
Periodic Team Synchronization (PTS)
 Ambientes com
 Colaboração entre agentes para alcançar um objetivo
 Sincronização com comunicação confiável disponível por
períodos limitados
 Resto do tempo, comunicação não confiável e com
largura de banda limitada
 Tempo-real
 Desafios
 Representação dos “acordos de vestiário”
 Determinar o momento de troca de papeis e/ou de
formação
 Assegurar que todos os agentes estejam na mesma
formação
 Assegurar queArquitetura
todosdeos
papeis da formação estão
Multi-Agentes
34 / 55
Visão Geral da Arquitetura
Arquitetura de Multi-Agentes
35 / 55
Estrutura do Trabalho em Equipe
 Papel
 Define exatamente ou parcialmente comportamentos do
agente

ex, meio-campista
 Formações
 Coleção de papeis, ex, 4-3-3, 4-4-2

Pode ser decomposta em sub-formação, ex, zaga, ataque
 Acordo de vestiário define:
 formações iniciais

gatilhos para re-alocação de papeis dentro de uma
formação
- ex, ponta direita passa pela esquerda e vice-versa

Arquitetura de Multi-Agentes
gatilhos para mudança de formação
36 / 55
Paradigma de Comunicação
 Ambiente
 Vários agentes, times
 Desafios
 Direcionamento e

Canal único
identificação de mensagens

Banda estreita

Robustez a interferência

Não confiável

Múltiplas respostas
simultâneas

Robustez a mensagens
perdidas

Arquitetura de Multi-Agentes
Coordenação do time
37 / 55
Implementação
 Sincronização das ações
 Estado do mundo
 Atualizando o estado do mundo
 Habilidades do agente
 Modos de comportamento
 Instanciação de domínio de papeis e formações
 Troca dinâmica de formações
 Posições flexíveis
 Jogadas pré-planejadas
 Paradigma de comunicação
Arquitetura de Multi-Agentes
38 / 55
Estado do mundo
 Objeto


Coordenadas de posição
Confiança da coordenada
Objeto
 Objeto Estacionário
 Objeto Móvel


Coordenadas de velocidade
Confiança da coordenada
 Bola
Objeto
Estacionário
Objeto
Móvel
 Jogador



Time, Número
Ângulo da face
Confiança no ângulo
Arquitetura de Multi-Agentes
Bola
Jogador
39 / 55
Atualizando o estado do mundo
 O próprio agente
 SE chegou nova informação visual
- A posição absoluta do agente pode ser calculada a partir de
coordenadas relativa e objetos estacionários (landmarks)

SE não chegou informação visual
- Atualizar a velocidade e previsão dos efeitos da última ação
- Prever a nova posição e velocidade a partir dos valores
anteriores
Se disponível, atualizar a velocidade do agente a partir
das sensações corpóreas (própriocepção)
 Atualizar a stamina do agente a a partir das sensações
corpóreas ou de previsões de efeitos de ações

Arquitetura de Multi-Agentes
40 / 55
Atualizando o estado do mundo
 A bola
 SE chegou nova informação visual
- Determinar a posição absoluta da bola a partir da posição
absoluta do agente e da posição relativa da bola

SE informação sobre a velocidade foi dada
- Atualizar a velocidade

SE não chegou informação visual
- Estimar velocidade e posição

SE a bola deveria estar no campo de visão, mas não esta
- zerar a confiança para 0
 Companheiros e adversários
Arquitetura de Multi-Agentes
41 / 55
Habilidades do agente e
Modos de comportamento Traduzir
 Goaltend
 Localize
 Face Ball
 Handle Ball
 Active Offense
 Passive Offense
 Active Defense
 Auxiliary Defense
 Passive Defense
Arquitetura de Multi-Agentes
42 / 55
Instanciação de domínio
de papeis e formações
 Ball Lost  Face Ball()
 If (Ball know  Chasing)
Handle Ball(args1)
 If (Ball know AND Not Chasing) Passive Offense(args1)
 If (Communicate Flag Set)
Arquitetura de Multi-Agentes
Communicate()
43 / 55
Posições flexíveis
 Antecipação



Marcação do oponente (explicar)
Posicionamento dependente da bola (explicar)
Posicionamento estratégico usando atração e repulsão
(SPAR)
 SPAR (Strategic Position by Attraction and Repulsion): heurística
composta baseadas nas seguintes prioridades:
 1. Maximizar a distância a cada oponente (sair da marcação)
 2. Maximizar a distância a cada companheiro (ocupação do
campo)
 3. Minimizar a distância à bola
 4. Minimizar a distância ao gol
 5. Ficar próximo à posição de base do papel (home position)

6. Ficar dentro dos limites do campo

7. Evitar posição de impedimento

8. Fica “livre” para
receber
o passe (não tem adversário entre jogador
Arquitetura
de Multi-Agentes
44 / 55
Jogadas pré-planejadas
 Alocação de papel em jogadas ensaiadas:
 escolher para para P jogador J cuja posição de base é a
mais próxima da posição inicial da jogada ensaiada
Arquitetura de Multi-Agentes
45 / 55
Paradigma de comunicação
 CMUnited <Uniform-number><Encoded-stamp>
<Formation-number><Formation-set-time><Positionnumber><target><Message-type>[<Message-data>]
 Tipos de Mensagens
 Perguntar/responder a localização da bola
 Perguntar/responder a localização do companheiro
 Informar destino do passe
 Informar que esta indo para bola
 Informar que esta assumindo/deixando uma posição
Arquitetura de Multi-Agentes
46 / 55
Resultados
 Resultados da estrutura do trabalho em equipe
 Posições flexíveis

Jogadas
Arquitetura de Multi-Agentes
47 / 55
Resultados
 Resultados da estrutura do trabalho em equipe
 Formação
Arquitetura de Multi-Agentes
48 / 55
Resultados
 Resultados do Paradigma de comunicação
 Robustez a interferência
-
73msg/5min falsas -> Todas identificadas como falsas
-
Apenas uma de um companheiro identificada
incorretamente como falsa

Manipulando respostas múltiplas

Coordenação do time
Arquitetura de Multi-Agentes
49 / 55
Conclusões
Arquitetura de Multi-Agentes
50 / 55
Bibliografia
Arquitetura de Multi-Agentes
51 / 55