Agentes Autónomos e Sistemas
Multi-agente
(UD3 e 4) Agentes Reactivos e
Híbridos
IST- 2004/2005
Críticas aos Agentes Deliberativos

Rapidez na resposta em tempo real <->
representação simbólica e processo de decisão
(manipulação sintática)
Nova abordagem: Ideias base

Comportamento racional está ligado ao ambiente do
agente e à interacção do agente com o ambiente

Os agentes não devem ser vistos sem as suas
restrições corporais e de local onde o agente se
encontra

Comportamento inteligente não deve ser programado
mas deve emergir da interacção de comportamentos
simples.
Designações

Comportamental – combinar comportamentos
individuais (evitar obstáculos, explorar o mundo, etc.)

Situada – agentes estão situados no ambiente

Reactiva – reagir ao ambiente sem raciocínio sobre
ele
Agentes puramente reactivos

Alguns tipos de agentes decidem o que fazer sem qualquer
referência ao seu historial. As suas decisões são situadas
no ambiente e dependem simplesmente do presente.
- São chamados agentes “puramente reactivos”

Do ponto de vista formal um agente puramente reactivo
pode ser visto como uma função:
Ag : E -> Ac
(ou seja em vez de RE o agente decide simplesmente baseando-se
em E).
Percepção/Acção
see : E -> Per
Action : Per* -> Ac
See
Action
Agente
Ambiente
“Elephants don’t play chess”Rodney Brooks

Recusa da hipótese do sistema simbólico

Ideia: “O mundo é o meu melhor modelo”
- Observar a evolução das formas de vida
na terra:
- no início comportamentos simples.
- gradualmente vão sendo acrescentados
novos comportamentos cada vez mais
sofisticados.
Arquitectura de “Subsumpção” de
Brooks
Teses:
1.
2.
3.
Comportamento inteligente pode ser gerado sem
representações explícitas e sem recorrer a IA
simbólica
Comportamento inteligente pode ser gerado sem
qualquer tipo de raciocínio abstracto usado em IA
clássica
A “inteligência” é uma propriedade emergente de
certos sistemas complexos.
Arquitectura de “Subsumpção” de
Brooks
Requisitos:
1.
2.
3.
Lidam com múltiplos objectivos (ir para + evitar
obstáculos, etc.)
Múltiplos sensores (errados, conflitos)
Robustos (falhas, mudanças no ambiente)
Ideias

Situado no mundo e não em sistemas não situados
como sistemas de raciocínio (“theorem provers”) ou
periciais

Inteligência é característica emergente da interacção
com o ambiente
Ideia 1
Situação  Acção
•
•
O processo de decisão é baseado num
conjunto de comportamentos de realização de
tarefas que recebem percepções e os mapeiam
numa acção
Cada módulo faz uma determinada tarefa, sem
representação simbólica – regras (s,a)
Ideia 2
Vários comportamentos podem
disparar simultâneamente

Têm de existir mecanismos de selecção entre
diferentes acções - camadas
Arquitectura de Brooks
Cam a da de c om por tam e ntos
EXPLORAR
S e n sore s
Efe ctore s
VAGUEAR
EVITAR
P olític a de controle

Construir mapas, monitorizar mudanças, identificar objectos, planear mudanças,
raciocinar sobre o comportamento de objectos, etc.
Arquitectura de Brooks

Reflecte não uma decomposição funcional das suas
componentes mas sim uma decomposição de
comportamentos
A estratégia de construção:
ir dotando incrementalmente os agentes de mais
comportamentos. Em cada passo de construção
obtém-se um sistema mais ou menos completo
(baseado numa máquina de estados finita).
Desenvolvimento de Sistemas
usando a arquitectura de Brooks
1.
Cria-se um módulo relativamente a uma actividade
em particular. Este módulo deverá ligar a percepção à
acção e o sistema resultante funcionar por si.
2.
Acrescentar mais componentes, cada um deles
ligando a percepção à acção. Por cada componente
junta, ajustar as prioridades dos comportamentos.
3.
As camadas de baixo podem impedir as camadas de
cima de tentar controlar o comportamento, suprimindo
inputs e inibindo outputs (maior prioridade)
Modelo


see – o input do sensor não é “tratado” - não se tenta representação
simbólica
action –
• processo de decisão = conjunto de comportamentos + função de
inibição
•
comportamento (c, a)
- c é conj. de percepções (condição)
- a é uma acção
- Dispara quando no estado s, see(s)  c
•
•
Beh é um conjunto de comportamentos
Relação binária de inibição, < C RXR (relação de
ordem total e estrita)
r1< r2 < r3 < r4 < r5
(r1 tem prioridade)
Action selection na
arquitectura de Brooks
function: Action Selection in the Subsumption
Architecture
function action (p:P):A
var fired: p(R)
var selected: A
Begin
fired <- {(c,a) | (c,a)  R and p  c}
for each (c,a)  fired do
if  ( (c’,a’)  fired such that (c’,a’) <
(c,a)) then
return a
end-if
end-for
return null
end function action
Exemplo: O explorador
de Marte de L. Steels



Explorar planeta distante e colher amostras de uma
rocha preciosa particular que não se sabe onde se
encontra.
Vários veículos autonomos, não há mapa
Uso de 2 conceitos:
• o campo de gradiente,- para os agentes saberem
em que direcção a nave deles se encontra;
enfraquece com a distância
• Comunicação entre agentes – não há
comunicação directa!
• Mas podem deixar migalhas radioactivas e
apanhá-las. E conseguem detectá-las.
“Behaviours”
if detect an obstacle then change direction
if carrying samples and at the base then drop samples
if carrying samples and not at the base then travel up gradient
if detect a sample then pick sample up
if true then move randomly
1< 2 < 3 < 4 < 5
Mas se as amostras tendem a estar numa mesma localização?
NOTA: não há comunicação directa!
(1)
(2)
(3)
(4)
(5)
“Behaviours”
Mas se as amostras tendem a estar numa mesma localização?
Deixar rasto!! (como as formigas)
if detect an obstacle then change direction
(1)
if carrying samples and at the base then drop samples
(2)
if carrying samples and not at the base then drop 2 crumbs and travel
up gradient
(3)
if detect a sample then pick sample up
(4)
if sense crumbs then pick 1 crumb and travel down gradient
(5)
if true then move randomly
(6)
Exemplo: Robot Genghis


Robot com seis pernas com aproximadamente 1 Kg.
Anda em terreno usando 12 motores, 12 sensores de força, e
vários outros sensores.

Não existe sistema central de controlo nem memória (o controlo
das pernas é feito cada uma por si... E portanto programada
cada uma por si...)

Video.
Exemplos:

Vários robots foram feitos no grupo de R. Brooks segundo
sempre a mesma aproximação.

Exemplo mais recente: Kismet
<<<< VIDEOS de Kismet >>>>>
Outros trabalhos



PENGI – Agre& Chapman
- A maior parte das nossas acções são de rotina – não
requerem raciocínio abstracto – podem ser
codificadas nas camadas inferiores da estrutura e só
são actualizadas para atacar problemas mais
complexos
GAPPS
- Primeiro estudo formal (rep declarativa), depois
compilado numa máquina digital que segue a
especificação
Maes –
- Modulos+rede de activação - activação sucessiva dos
módulos ligados através das pré-condições e das
pós-condições (estilo STRIPS)
Limitações dos
agentes reactivos

Alcance bastante limitado.
 Como os agentes não usam modelos do ambiente,
devem poder obter suficiente informação a cada
instante para conseguirem determinar a melhor
acção.
 Não conseguem ter comportamentos orientados aos
objectivos – não suportam raciocínio explícito
São agentes difíceis de construir porque com
pequenos comportamentos e regras que os
relacionam é difícil prever o que vai resultar (ad-hoc).
 Não é claro a sua escalabilidade, difícil predizer ou
explicar
 Não se consegue estudar propriedades formais

Motivação para as arquitecturas
Híbridas

Os agentes necessitam de:
•
•
•
Realizar tarefas complexas
Tomar atenção às mudanças (esperadas e não)
que ocorrem no ambiente e reagir em tempo real;
Ter em conta os seus recursos limitados (pelo que
necessitam da colaboração de outros agentes para
a execução das tarefas)
Assim, se por um lado os agentes têm que
necessariamente permanecer reactivos para
sobreviver, por outro lado têm que tomar decisões
estratégicas complexas e que a maioria das vezes
são orientadas aos objectivos.
Arquitecturas Híbridas: Requisitos

Comportamento situado: os agentes devem reconhecer
os eventos e reajir em tempo apropriadamente.

Comportamento orientado aos objectivos: os
agentes devem seleccionar as suas acções baseando-se nos
fins que desejam alcançar e os meios disponíveis para o fazer.

Eficiência- as tarefas devem ser executadas eficientemente ,
mesmo com constrangimentos de ordem temporal.

Coordenação: os agentes devem ser capazes de coordenar
as suas actividades com os outros agentes.
Arquitecturas Híbridas com níveis

As arquitecturas híbridas têm normalmente
associados níveis:
•
Servem para estruturar as tarefas ou
comportamentos dos agentes
• Estão organizados hierarquicamente
• Interagem uns com os outros de forma a atingir um
comportamento geral do agente mais coerente
Normalmente: níveis deliberativos e reactivos
> pelo menos 2!!
Arquitecturas Híbridas com níveis

Horizontal
- Cada camada “é como um agente”
- Vantagens: Simplicidade
- Desvantagens: comportamento global pode não ser
coerente >
- mediador que decide qual a camada que controla o agente
num dado instante
- dificil de construir mn interacções, m= acções, n=níveis
- bottleneck
P input
action
Arquitecturas Híbridas com níveis

Vertical (1 passo)
Vertical (2 passos – como as organizações –
info+comandos)
action
P input
P input
action
Arquitecturas Híbridas com níveis

Mais simples (m2 (n-1)) mas mais inflexivel
- – tem de passar por todas as camadas para haver uma decisão
– não é tolerante a faltas!!
action
P input
P input
action
Touring Machines

De Innes Fergunson em 1994
 3 Níveis: nível reactivo; nível de planeamento e nível
de modelação

Os três níveis operam concurrentemente e cada um
deles está ligado ao subsistema sensorial do agente,
do qual recebe informação, bem como ao subsistema
de acção ao qual é possível enviar comandos de
acção.
 Qualquer nível pode comunicar com os restantes
Touring Machines: Arquitectura
Modelling layer
Perception Subsystem
Planning layer
Action Subsystem
Reactive layer
Clock
Context Activated Control-rules
TM: Nível Reactivo



O Nível reactivo (R) foi desenhado para executar acções que
são respostas específicas ao domínio e aos estímulos do
ambiente.
Implementada como os Behaviours = conj regras (c,a)
Regras só podem referir o estado corrente do agente
Rule-1: kerb-avoidance
if is-in-front(kerb, observer) and
speed(observer) > 0 and
separation(kerb, observer) < kerb-threshhold
then

change-orientation(kerb-avoidance-angle)
Este nível dá ao agente a capacidade de reagir rapidamente em
situações não planeadas pelos níveis superiores.
TM: Nível de Planeamento

É responsável pelo comportamento proactivo (decide
o que fazer): por gerar, executar e dinamicamente
readaptar planos parciais da biblioteca
 Estes planos destinam-se a atingir uma alocação de
tarefas que o agente tem que executar a longo prazo.
 Os planos são guardados como planos parciais
hierárquicos, numa biblioteca de planos.
TM: Nível de Modelação
Representa conhecimento sobre entidades do mundo
inc. agente
O nível de modelação contém a representação do
mundo sob a forma de 4-tuplos <C,B,D,I> indexados
a unidades de tempo.
 C- configuração, descreve a localização do objecto,
sua velocidade, aceleração etc. das entidades do
ambiente;
 B- conjunto de crenças atribuídas à entidade;
 D- desejos, representados através de uma lista de
objectivos e suas prioridades
 I- um plano hierárquico que forma a estrutura de
intenções.
TM: Controlo das regras
Decide quais as camadas que devem controlar o agente
Composta por um conjunto de regras de controlo
As regras de controlo (suppressor e censor) são
construídas pelo programador, tal que:
-
Pelo menos uma dispare numa dada situação
(bottleneck)
Pelo menos uma acção deve permanecer no
subsistema de acção.
TM: Regras Censor


Parte condicional: conjunções de expressões que testam a
presença de objectos sensoriais particulares.
Parte de acção: é composta por operações para fazer com que
objectos sensoriais não sejam colocados como input aos níveis
de controlo.
Regra censor-rule-1:
if entity(obstacle-6) in perception-buffer
then
remove-sensory-entity(layer-R,
entity(obstacle-6))
Embora a camada reactiva seja apropriada para evitar obstáculos há
alguns obst que é melhor serem tratados noutras camadas
TM: Regras Suppressor


Parte condicional: com expressões que testam a presença de
determinados comandos (acções do agente)
Parte da acção: é composta por operações que restringem a que
certos comandos sejam executados pelos effectors do agente.
rule suppressor-rule-3 :
if action-command(layer-R, rule-6, change-orientation())
in action-buffer
and current-intention(start-overtake)
then
remove-action-command(layer-R, change-orientation())
and remove-action-command(layer-M, _).
Aplicação da arquitectura TM



Em situações de simulação de robots com
obstáculos: Touring world.
Foi desenvolvida uma ferramenta que permite a
criação de certas configurações de agentes
A dinâmica do mundo é obtida através da utilização
de um simulador de eventos, que incorpora um
actualizador de mundos possíveis
InteRRap




Estende um conjunto de aproximações de construção
de agentes por níveis introduzindo um nível de
cooperação.
Dá ao desenhador dos agentes a possibilidade de
construir níveis com comportamento reactivo e
deliberativo, tal como a arquitectura apresentada
anteriormente.
Tem uma arquitectura vertical de 2 passos
O modelo do agente em InterRaP é definido por um
conjunto de níveis funcionais ligados por uma
estrutura de controlo e partilhando uma base de
conhecimentos hierárquica.
InteRRap: Arquitectura
Cooperation
Component CC
Plan-based
Component PBC
Behaviour Based
Component BBC
World Interface
Action Communication Perception
ENVIRONMENT
Cooperation
Knowledge
Local
Plans
World
Model
Componentes da Arquitectura





WIF (World Interface) – contém as facilidades de percepção,
acção e comunicação.
BBC- (Behaviour- Based Component) executa e controla o
comportamento reactivo básico. Este comportamento é baseado
em “patterns of behaviour”
PBC (Plan Based Component): contém um mecanismo de
planeamento que permite o agente ter planos locais. Estes
planos são baseados em esqueletos hierárquicos em que os nós
podem ser sub-planos ou patterns of behaviour. Ou seja o PBC
pode activar “patterns of behaviour” para atingir um determinado
objectivo.
KB (Knowledge Base)- é uma estrutura hierarquicamente
estruturada e é composta por quatro níveis, que básicamente
correspondem à estrutura de controlo dos agentes. Kb´s
representação do mundo apropriada a cada nível
CC (Cooperation Component): permite a cooperação entre
agentes – interacção social.
Knowledge Base

Nível de Cooperação – conhecimento sobre os outros agentes,
objectivos conjuntos, intensões conjuntas, estado de planos conjuntos

Nível de Planos Locais – conhecimento sobre si mesmo incluindo sobre
os planos, intensões, acções etc. do próprio agente

Nível Modelo do Mundo – informação “pura” sobre o ambiente

A divisão/organização hierárquica da KB distingue InteRRaP da
TouringMachines
InteRRap: Componente Baseada
no Comportamento (BBC)

Objectivos
•
•
Incorporar as actividades reactivas do agente que
permitem lidar com situações de emergência e de
tempo real.
Dar ao agente conhecimento procedimental que
lhe permite executar tarefas de rotina.
InteRRap: Patterns of Behaviour:
Tipos
Ligar situações a acções




Reactors: são activadas por eventos externos que causam a
execução de uma acção por parte do agente (ex. Parar)
Control modifiers- extendem o controlo do planeador, fazendo
uma chamada para cima para o PBC (ex. Treat_order)
Knowledge modifiers- mudam o estado interno do agente e são
activadas por alterações do mundo detectadas pelo agente.
Procedures- executam acções especificadas pelo planeador.
InteRRap: Aspectos da BBC





Tem que reconhecer situações de emergência e
responder rápidamente a essas situações.
A parte da base de conhecimento acessível à BBC é
o modelo do mundo
O número de situações a serem reconhecidas neste
nível é bastante limitado
Situações que não emparelham com nenhum padrão
de comportamento causam um pedido ao PBC
Os compromissos feitos pelo PBC para executar
procedimentos causam a activação de procedimentos
no BBC.
Aplicação: the Loading Dock
Aplicação: conflictos
Aplicação: criação de Plans of
Behaviour (PoBs)
Aplicação: criação de PoBs
InteRRap: Componente de
Planeamento
Incorpora as capacidades de planeamento do agente
Funções principais são: (1) a obtenção de um plano
para um dado objectivo e (2) controlar a execução
desse plano.
Componentes
• PBC-control- faz a interface com BBC recebendo e
enviando mensagens aos outros níveis.
• Plan-generator- gera planos através da selecção
de um conjunto de planos da biblioteca.
• Plan-evaluator- é usado para seleccionar os
melhores planos gerados.
InteRRap: Interacção entre
camadas
Activação bottom-up/top-down execution

As percepções começam a ser tratadas na camada
reactiva. Se esta não a conseguir tratar vai passando
essa informação para cima até que ela possa ser
tratada.

Depois as acções vão sendo enviadas das camadas
mais altas para as mais baixas
InteRRap: Geral camadas
Qualquer camada define duas funções:
1- situation recognition & goal activation
(KBL, current goals) > new goals
2- planning and scheduling
(current plans, goals, KBL > plan to execute
Aplicação: robots
Vantagens das arquitecturas
Híbridas




Abordagem mais em voga neste momento
Consegue responder em tempo real sem deixar de ter
comportamento orientado aos objectivos.
A reactividade do agente pode ser privilegiada enquanto em
deliberação, ou seja o nível reactivo pode continuar a monitorar
o mundo.
Se há tipos diferentes de partições do conhecimento do mundo é
possível restringir a quantidade de conhecimento que cada nível
requer individualmente.
Desvantagens das arquitecturas
Híbridas

Falta a clareza semântica e conceptual das abordagens em
camadas.

As interacções entre camadas: podemos ter de analisar todas as
possíveis interacções entre camadas para produzir o
comportamento final/resultante
Bibliografia da Aula




An Introduction to Multi-agent Systems, M. Wooldridge, John Wiley &
Sons, 2002
A Mente e o Mundo lá Fora, H. Coelho e A. Paiva.
Designing Autonomous Agents: Theory and Practice from Biology to
Engineering and Back, Ed. P. Maes, MIT Press, 1990.
The Design of Intelligent Agents: a Layered Approach, Jörg Müller,
Springer, 1996.
World Interface
World Interface
Acções que o agente pode executar
Knowledge Base
InteRRap: “Patterns of Behaviour”
InteRRap: Controlo
Aplicação: the Loading Dock