Arquitetura de Multi-Agentes 1 / 55 Arquitetura de Multi-Agentes IA Simbólica Prof. Jacques Robin Ryan Leite Albuquerque Luiz Carlos Barboza Júnior

Arquitetura de Multi-Agentes 1 / 55

Arquitetura de Multi-Agentes

IA Simbólica

Prof. Jacques Robin

Ryan Leite AlbuquerqueLuiz Carlos Barboza Júnior


Roteiro

Arquiteturas Para Agentes Inteligentes Abstratas Concretas


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


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


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


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 !!


Arquiteturas Abstratas

Agentes Puramente Reativos

Percepção

Agentes com Estado


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


Ambiente

Agente

see action

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

Função de Decisão do Agente é decomposta em: Percepção ( see : S P ) Ação ( action : P* A )


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


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


see : S P inalterado

action : I A

next : I x P I Adicionado percepções alteram o estado interno

Ambiente

Agentesee action

next state

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



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



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


O processo de tomada de decisões é modelado através de um conjunto de regras dedutivas:

Banco de Dados de FórmulasRegras Dedutivas

Fórmula da Lógica




Fórmula da Lógica


see : S P

next : D x P D

action : D A derivado em termos de regras dedutivas

juntar com 15



Fórmula da Lógica

O Mundo do Aspirador de Pó

Funções Possíveis forward suck turn (90°)

Predicados do Domínio in(x,y) dirt(x,y) facing(d)

(0,2) (1,2) (2,2)

(0,1) (2,1)

(0,0) (1,0) (2,0)

Área suja!!



Fórmula da Lógica

O Mundo do Aspirador de Pó

A função next será decomposta em duas old() new : D x P D Assim, next(, p) = ( \ old() ) new(, p)

As regras... in(x,y) dirt(x,y) do(suck)

- Prioridade máxima 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)


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



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 Por exemplo, um robô móvel deve ter como prioridade máxima

o comportamento de evitar obstáculos Decisões baseadas em



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



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


Processo de raciocínio prático

Arquiteturas Baseadas emCrenças, Desejos e Intenções

BRF

Crenças

Gerador de Opções

Desejos

Filtros

Ações

Intenções

Sensor

Ação



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



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)



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


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


Camadas Horizontais: juntar com 31

Camadas Horizontais

Camada n

Input

...

Camada 2

Camada 1

Output


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!!


Dois passos de controle

Camadas Verticais

Output

Camada n

...

Camada 2

Camada 1

Input


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 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


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 que todos os papeis da formação estão preenchidos


Visão Geral da Arquitetura


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 gatilhos para mudança de formação

Jogadas ensaiadas, ex, escanteio


Paradigma de Comunicação

Ambiente Vários agentes, times Canal único Banda estreita Não confiável

Desafios Direcionamento e

identificação de mensagens

Robustez a interferência Múltiplas respostas

simultâneas Robustez a mensagens

perdidas Coordenação do time


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


Estado do mundo

Objeto Coordenadas de posição Confiança da coordenada

Objeto Estacionário Objeto Móvel

Coordenadas de velocidade Confiança da coordenada

Bola Jogador

Time, Número Ângulo da face Confiança no ângulo

Objeto

Objeto Estacionário

Objeto Móvel

Bola Jogador


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


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


Habilidades do agente e Modos de comportamento Traduzir

Goaltend

Localize

Face Ball

Handle Ball

Active Offense

Passive Offense

Active Defense

Auxiliary Defense

Passive Defense


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) Communicate()


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 com a

bola e companheiro)


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


Paradigma de comunicação

CMUnited <Uniform-number><Encoded-stamp><Formation-number><Formation-set-time><Position-number><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


Resultados

Resultados da estrutura do trabalho em equipe Posições flexíveis Jogadas


Resultados

Resultados da estrutura do trabalho em equipe Formação


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


Conclusões


Bibliografia

Documents

Arquitetura de Multi-Agentes 1 / 55 Arquitetura de Multi-Agentes IA Simbólica Prof. Jacques Robin Ryan Leite Albuquerque Luiz Carlos Barboza Júnior