MultiAgent
Planning
Ismênia Galvão Lourenço da Silva
[email protected]
PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
CENTRO DE INFORMÁTICA
UNIVERSIDADE FEDERAL DE PERNAMBUCO
Roteiro

Motivação

Resolução Distribuída de Problemas

Compartilhamento de Tarefas

Compartilhamento de Resultados

Planejamento Distribuído

Representações de Planos Distribuídos

Execução e Planejamento Distribuídos

Conclusões

Referências
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
2
Motivação

Lidar com problemas onde:




17.11.2003
É necessário usar recursos distribuídos concorrentemente,
dependendo do seu grau de paralelismo;
Muitas vezes é necessário empregar capacidades de vários
especialistas para chegar à uma solução;
Crenças e dados podem estar distribuídos, mas as suas
interpretações podem ser realizadas localmente;
Os resultados de sua resolução ou de seu planejamento podem
ser distribuídos para serem influenciados por outros agentes.
Tópicos Avançados em Inteligência Artificial Simbólica I
3
Resolução Distribuída de
Problemas
Introdução

Na Resolução Distribuída de Problemas (RDP), os agentes
envolvidos trabalham juntos para resolver problemas que requerem um
esforço coletivo;

Em Sistemas Abertos, os agentes não são necessariamente
cooperativos e podem ingressar e sair do sistema de maneira dinâmica;

Dentro desta segunda classificação, estão inseridos os Sistemas
Multi-agentes:

Conjunto de agentes autônomos

Possivelmente pré-existentes

17.11.2003
Solução de um problema que está além da capacidade de um único
agente.
Tópicos Avançados em Inteligência Artificial Simbólica I
5
Relação entre RDP e SMA

RDP

Ênfase na solução de um ou
mais problemas, com o esforço
de múltiplos agentes com
interesse em propriedades
extrínsecas como:

Competência de grupo

Robustez

Uso eficiente de recursos
17.11.2003
SMA
Ênfase na existência de
múltiplos agentes com
interesse em propriedades
intrínsecas como:

Revelação da verdade

Manipulação

Coerência de grupo
Tópicos Avançados em Inteligência Artificial Simbólica I
6
Resolução Distribuída de Problemas

Presume a existência de problemas que precisam ser resolvidos;

Existe uma expectativa sobre o que pode constituir soluções;

Exemplo: time de agentes para projetar um artefato



17.11.2003
A solução deve satisfazer requisitos gerais (motor, rodas, ...);
O problema já existe em alguma forma particular (um documento
com a estrutura do carro);
Cada agente do time formula soluções para os subproblemas, que
em seguida são sintetizadas para uma solução geral.
Tópicos Avançados em Inteligência Artificial Simbólica I
7
Compartilhamento
de Tarefas
Compartilhamento de tarefas

Princípio: quando um agente tiver muitas tarefas para fazer,
ele deve solicitar ajuda;

Principais passos:

Decomposição da tarefa

Alocação da tarefa

Realização da tarefa

Síntese do resultado
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
9
Exemplo 1: Figuras Escondidas
•
Problema: encontrar figuras
escondidas em uma
determinada área
1.
Decomposição: dividir a área ou
as figuras para a busca;
2.
Alocação: distribuir as subtarefas entre os agentes;
3.
Execução: cada agente deve
procurar as figuras atribuídas a
ele, ou fazer uma busca na área
destinada a ele;
4.
Síntese: cada agente apresenta as
figuras encontradas.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
10
Exemplo 2: Torres de Hanoi
•
Problema: mover todos os discos da estaca inicial para
outra estaca determinada, movendo um disco por vez e
sem colocar um disco maior sobre um menor
1.
Decomposição: se preocupa em sempre mover o maior disco para
o seu destino;
2.
Alocação: escolha randômica dos agentes;
3.
Execução: as tarefas são recursivamente decompostas até que o
estado inicial e final sejam o mesmo;
4.
Síntese: quando um agente resolve um problema, ele passa a
solução para outro, que irá utilizá-la para encontrar sua própria
solução.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
11
Compartilhamento em Sistemas
Heterogêneos

O compartilhamento em sistemas heterogêneos aplica-se
quando:

As atribuições de subproblemas para agentes não são
simples:

Os agentes podem ter diferentes habilidades;

Os subproblemas precisam de diferentes habilidades;

As decisões são baseadas em informações mais dinâmicas.

Ex: Contract Net Protocol
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
12
Compartilhamento
de Resultados
Compartilhamento de Resultados

Uma mesma tarefa pode ter resultados diferentes se executada por
agentes diferentes;

Agentes podem resolver problemas via integração de resultados locais;

O compartilhamento de resultados pode ser proativo ou reativo;

Solucionadores de problemas podem aumentar o desempenho do
grupo se combinarem as seguintes características:

Confiança

Completude

Precisão

Rapidez
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
14
Compartilhamento de Resultados

Complicações:



Os agentes devem saber o que fazer com os resultados
compartilhados !
A comunicação de um grande volume de resultados pode ser
custosa.
Técnicas:

Cooperação funcionalmente precisa

Repositórios compartilhados e busca negociada

Busca heurística para CSP distribuída (DCHS)

Estruturação organizacional
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
15
Planejamento Distribuído
- Planejamento Centralizado para Planos Distribuídos
- Planejamento Distribuído para Planos Centralizados
- Planejamento Distribuído para Planos Distribuídos
Planejamento Distribuído

Especialização da RDP, onde o problema sendo resolvido é o
projeto de planos.

Um modelo de Planejamento Distribuído (PD) deve considerar:



17.11.2003
A concorrência existente entre os agentes em um ambiente
compartilhado;
As alterações ocorridas no ambiente entre o planejamento e a
execução dos planos resultantes deste;
Possibilidades de ajustes nos planos.
Tópicos Avançados em Inteligência Artificial Simbólica I
17
Planejamento Multi-Agente (PMA)

Estende o planejamento clássico para domínios onde vários agentes
podem planejar e agir juntos;

Em ambientes multi-agentes, os agentes não são indiferentes às
intenções dos demais;

A construção de um plano eficiente é útil, mas não garante o sucesso:
os agentes precisam concordar em usar o mesmo plano;

Algumas formas de coordenação,
comunicação, são requeridas;

Suas aplicações incluem: ambientes multi-robôs, agentes cooperativos
na internet, logística, produção, tarefas militares, ...
17.11.2003
possivelmente
Tópicos Avançados em Inteligência Artificial Simbólica I
usando
18
Problema da dupla de tênis
Problema da dupla de tênis:
Dois agentes jogam tênis no mesmo time e podem estar em uma das 4 localizações:
[Left,Baseline], [Left,Net], [Right,Baseline], [Right,Net]. A bola só pode ser retornada
se exatamente um jogador estiver na posição correta.
Agents (A,B)
Init (At (A, [Left,Baseline]) ^ At (B, [Right,Net]) ^ Approaching (Ball, [Right,
Baseline])) ^ Partner (A,B) ^ Partner (B,A)
Goal (Returned(Ball) ^ At (agent, [x,Net]))
Action (Hit(agent, Ball)),
PRECOND: Approaching (Ball, [x,y]) ^At (agent, [x,y]) ^
Partner (agent, partner) ^¬ At (partner, [x,y])
EFFECT: Returned (Ball))
Action (Go (agent, [x,y]),
PRECOND: At (agent, [a,b]),
EFFECT: At (agent, [x,y]) ¬ At (agent, [a,b])
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
19
Planos conjuntos

Uma solução para um problema de PMA é o uso de planos
conjuntos, consistindo de ações para cada agente.

Um plano conjunto é uma solução se o objetivo for atingido
quando cada agente realizar as tarefas que lhe foram atribuídas.

A existência de planos conjuntos corretos não significa que
objetivo será alcançado.

Os agentes precisam de um mecanismo de coordenação e de
conhecimentos comuns para que o objetivo do plano conjunto
seja alcançado.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
20
Planos conjuntos
Plan 1:
A: [Go (A, [Right, Baseline]), Hit (A,Ball)]
B: [NoOp (B), NoOp (B)]
Plan 2:
A: [Go (A, [Left, Net]), NoOp (A)]
B: [Go (B, [Right, Baseline]), Hit (B, Ball)]

A
Início
17.11.2003

B
B
●
●
A
A1 / B1


A

A
●
B
A2 / B2
B
●
B
A
A1 / B2
Tópicos Avançados em Inteligência Artificial Simbólica I
●
A2 / B1
21
Ações conjuntas

Ações conjuntas são agrupamentos de ações concorrentes,
executadas cada uma por um único agente;

Um plano conjunto consiste de um grafo parcialmente ordenado
de ações conjuntas;

Usar POP torna-se intratável a nível de pré-condições e efeitos à
medida que aumenta o conjunto de ações possíveis;
 
 Go (A, [Left, Net]), Go (B, [Right, Baseline]) 
 NoOp(a), Hit(B, Ball) 
17.11.2003
B
A
Tópicos Avançados em Inteligência Artificial Simbólica I
●
A
●
B
22
Listas de Ações Concorrentes

Uma solução para o problema de sincronização é adicionar
listas de ações concorrentes às descrições das ações em
STRIPS ou ADL;

Essas listas descrevem as ações que podem ou não ser
executadas concorrentemente;
Action (Hit(A, Ball)),
CONCURRENT: ¬ (Hit(B, Ball))
PRECOND: Approaching (Ball, [x,y]) ^ At (A, [x,y])
EFFECT: Returned (Ball))
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
23
Listas de Ações Concorrentes

É possível criar um planejador parecido com o POP, com 3
diferenças:



17.11.2003
Além da relação de ordenação temporal A B, permite-se
A=B (concorrente) e A B (anterior ou concorrente)
Quando uma nova ação requer ações concorrentes, deve-se
instanciar essas ações usando ações novas ou já existentes
As ações concorrentes proibidas são uma fonte adicional de
restrições...
Tópicos Avançados em Inteligência Artificial Simbólica I
24
Planejamento Distribuído

Existem três classes de planejamento distribuído:

Planejamento centralizado para planos distribuídos

Planejamento distribuído para planos centralizados

Planejamento distribuído para planos distribuídos
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
25
Planejamento Centralizado para
Planos Distribuídos


Contexto:

Um problema a ser resolvido e vários agentes disponíveis;

Agente coordenador
Objetivo:

17.11.2003
Encontrar, dentro de todos os planos possíveis, aquele que
pode ser decomposto e distribuído mais eficientemente
Tópicos Avançados em Inteligência Artificial Simbólica I
26
Planejamento Centralizado para
Planos Distribuídos

Dado a descrição do objetivo, um conjunto de operadores e
um estado inicial, o coordenador deve:

Gerar um plano parcialmente ordenado

Decompor este plano em sub-planos

Restrições de ordenação devem ficar dentro e não entre os
sub-planos

Inserir sincronização

Atribuir sub-planos a agentes
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
27
Planejamento Centralizado para
Planos Distribuídos

Alocação de tarefas pode ser:



Estática: a coordenação é utilizada apenas para sincronizar os
planos
Dinâmica: a coordenação serve para sincronizar e alocar os
planos
Algumas considerações:


17.11.2003
Nem sempre o plano que pode ser mais decomposto e mais
distribuído é o melhor;
A infra-estrutura de comunicação tem grande impacto na decisão
de como os planos são decompostos e distribuídos.
Tópicos Avançados em Inteligência Artificial Simbólica I
28
Planejamento Centralizado para
Planos Distribuídos
C
D
A
B
A
B
D
C
PutDownTable (D) PutDown (A,D)
PutDownTable (C)
PutDown (B,C)
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
29
Planejamento Centralizado para
Planos Distribuídos
Pliers
PutDownTable (D)
PutOn (A,D)
PutOn (B,C)
PutDownTable (C)
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
30
Planejamento Distribuído para Planos
Centralizados

Contexto:


Tarefa muito complexa que requer o auxílio de especialistas
em cada sub-tarefa
Objetivo:

17.11.2003
Utilizar a expertise de cada agente para formular sub-planos
especializados
Tópicos Avançados em Inteligência Artificial Simbólica I
31
Planejamento Distribuído para Planos
Centralizados

O planejamento pode ser feito em uma das duas formas:


17.11.2003
Síncrona: a ordenação é feita durante o processo de
planejamento
Assíncrona: somente durante o compartilhamento de
resultados os conflitos com relação à ordem são resolvidos
Tópicos Avançados em Inteligência Artificial Simbólica I
32
Planejamento Distribuído para Planos
Centralizados

Exemplos:



17.11.2003
Manufatura: especialistas em geometria, encaixe, pintura,
etc;
Logística: especialistas em planejamento de caminho,
carregamento de veículos e despache;
Comunicação fim-a-fim: especialistas no roteamento de
mensagens.
Tópicos Avançados em Inteligência Artificial Simbólica I
33
Planejamento Distribuído para Planos
Centralizados
R1
E
B
D
A
C
F
R2
Goal R1
B
PutDownTable (B)
F
C
E
A
D
PutDownTable (A)
PutDown (C,A)
P1
Goal R1
PutDownTable (E)
17.11.2003
PutDownTable (D)
Tópicos Avançados em Inteligência Artificial Simbólica I
34
Planejamento Distribuído para Planos
Centralizados
PutDownTable (B)
PutDownTable (A)
PutDown (F,E)
P2
Goal R2
PutDownTable (E) PutDownTable (D) PutDown (E,D)
PutDownTable (B)
PutDownTable (A)
PutDown (C,A)
Goal R1
Goal R2
PutDownTable (E) PutDownTable (D) PutDown (E,D) PutDown (F,E)
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
35
Planejamento Distribuído para Planos
Distribuídos

Não existe um plano global da tarefa em nenhum ponto do
sistema, apenas planos parciais de relevância local;

Compatibilidade global entre esses planos parciais deve ser
mantida para:


Evitar conflitos durante a execução ;

Fomentar ajuda mútua.
Troca de mensagens e/ou temporização são usados para
resolver interações negativas entre os agentes.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
36
Planejamento Distribuído para Planos
Distribuídos
Delayed work
Go to cinema
Public
Transport
Go to
meeting
Car
Delayed
work
Look after
Hector
Look after
Hector
Julian
Helen
Put Hector to bed
Hector
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
37
Planejamento Distribuído para Planos
Distribuídos

Técnicas:

Fusão de planos

Construção iterativa de planos

Negociação de planejadores distribuídos
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
38
Fusão de Planos

Cada agente, individualmente, formula planos, que podem ser
executados separadamente sem conflitos;

Um agente coleta os planos individuais e analisa os planos para
descobrir que seqüências de ações podem levar a conflitos;

Consiste de três estágios:

Análise de interação

Análise de segurança

Resolução de interação
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
39
Construção Iterativa de Planos

Problema das abordagem anterior: às vezes, decisões locais
dependem das ações de outros agentes

Espaço de Planos x Plano Único

Cada agente, ao invés de propor um único passo, propõe um
conjunto de alternativas e, a cada iteração, escolhe-se a que
melhor se ajusta para o bem de todos
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
40
Busca por Combinação de planos

Dadas proposições iniciais sobre o mundo:



17.11.2003
Agentes formam estado sucessores propondo mudanças
causadas por uma ação;
É escolhido o melhor estado sucessor e esta escolha é expandida
(heurística A*);
O processo é repetido até que nenhum agente queira propor mais
mudanças.
Tópicos Avançados em Inteligência Artificial Simbólica I
41
Planejamento Distribuído Contínuo

Planejamento e execução intercalados

Um agente deve planejar continuamente quando:

Aspectos do mundo podem mudar dinamicamente;

Aspectos do mundo são revelados incrementalmente;


17.11.2003
Pressão do tempo faz com que a execução comece antes do plano
ter sido totalmente gerado;
Os objetivos podem evoluir com o tempo.
Tópicos Avançados em Inteligência Artificial Simbólica I
42
Representações de
Planos Distribuídos
Representações
de Planos Distribuídos

Planejamento e resolução de problemas distribuídos geralmente lidam
com agentes com capacidade de comunicar tarefas, soluções,
objetivos, planos, ...

Alguns protocolos de propósito geral têm sido desenvolvidos para lidar
com interação em alto-nível;

Em linguagens baseadas nos atos de fala, o envio de uma mensagem
pode ser interpretado como a invocação de um comportamento do
agente receptor;

Os agentes precisam entender não apenas o ato de fala, mas também
o conteúdo da mensagem.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
44
Representações
de Planos Distribuídos

Um plano pode ser visto como um conjunto de vários campos que
representam diferentes tipos de informações relacionadas;

Diferentes agentes necessitam acessar e modificar diferentes
combinações de campos de um plano.

Os agentes precisam:


17.11.2003
Ser capazes de encontrar as informações que querem, podendo
interpretar, modificar e executar o plano;
Saber como modificar o plano de maneira que seja interpretado
corretamente pelos demais agentes e tenha efeitos desejáveis;
Tópicos Avançados em Inteligência Artificial Simbólica I
45
Representações
de Planos Distribuídos

Todos os campos de um plano devem estar numa linguagem de
conteúdo compreensível pelos agentes que podem utilizá-lo;

Padrões para especificação de planos para agentes inteligentes:

STRIPS c/ operador

Cypress ACT

Lógica temporal

Formalismos operacionais (Redes de Petri, Graphcet)
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
46
Representações
de Planos Distribuídos

Estrutura do ACT em um formalismo Cypress:
CAMPO
DESCRIÇÃO
Name
Rótulo único para identificar o ACT
Cue
Metas que o ACT é capaz de atingir
Precondition
Características do estado do mundo que precisam ser validadas para o
ACT ser aplicável
Setting
Características do estado do mundo que são ligadas a variáveis do ACT
Resources
Recursos requeridos pelo ACT durante a sua execução
Properties
Outras propriedades associadas ao ACT
Comment
Informações de documentação
Plot
Especificação do procedimento a ser executado (seqüências parcialmente
ordenadas de objetivos/ ações)
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
47
Planejamento e Execução
Distribuídos
- Mecanismos de Coordenação
- Coordenação Pós-Planejamento
- Coordenação Pré-Planejamento
- Planejamento, Coordenação e Execução Intercalados
- Coordenação de Planos em Tempo de Execução sem Comunicação
Mecanismos de Coordenação

Uma convenção ou norma é qualquer restrição na seleção de
planos conjuntos relacionada aos padrões de comportamento
dos agentes;

Leis sociais são normas amplamente adotadas, como por
exemplo dirigir em determinado lado da rua;

Estabelecer normas prévias é um método pelo qual um grupo
de agentes pode garantir acordos entre planos conjuntos;

Comportamentos emergentes são aqueles onde não há
necessidade de que cada agente possua o plano conjunto que
modela as ações de outros agentes;
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
49
Mecanismos de Coordenação

As normas podem ser específicas ou independentes de um
determinado domínio;

Na ausência de normas aplicáveis, os agentes podem utilizar
comunicação (verbal ou não-verbal) para atingir um
conhecimento comum sobre um plano conjunto viável;

●

B
Uhuu !!!
B
●
A
A
É minha !!!
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
50
Mecanismos de Coordenação

Reconhecimento de planos é um método de coordenação que
ocorre quando uma ação (ou pequena seqüência de ações) é
suficiente para determinar um plano conjunto sem ambigüidade;

A garantia do reconhecimento de planos pode ser dada pelo
projetista ou pelos agentes em si.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
51
Planejamento e Execução Distribuídos

O produto do planejamento distribuído precisa ser executado...

Coordenar é garantir que uma seqüência de planos, com determinadas
restrições, seja atingida;

A coordenação de planejamento e execução de planos distribuídos é
um desafio da IA;

Algumas estratégias:

Coordenação Pós-Planejamento

Coordenação Pré-Planejamento

Planejamento, Coordenação e Execução Intercalados

Coordenação de Planos em Tempo de Execução sem Comunicação
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
52
Coordenação Pós-Planejamento

Durante a execução de um plano, pode ocorrer alguma falha
inesperada e o conjunto de planos coordenados pode falhar por
inteiro;

Uma solução é utilizar planos de contingência: cada agente
além de formular seus planos esperados, pode formular planos
alternativos para atender às contingências;

Esses planos com suas ramificações podem ser consolidados e
coordenados em tempo de execução, o que torna o processo
mais complicado;
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
53
Coordenação Pós-Planejamento

Outra solução é usar monitoramento e replanejamento;

Cada agente monitora a execução de seu plano, se houver
algum desvio, ele pára sua execução e repete o ciclo planejarcoordenar-executar;

Algumas estratégias podem reduzir o esforço e aumentar a
gerenciabilidade do processo:

Consertar planos anteriores;

Acessar uma biblioteca de planos reusáveis...
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
54
Coordenação Pré-Planejamento

Assumindo-se restrições de coordenação aceitáveis, os agentes
podem garantir previamente a coordenação de seus planos com os
dos outros agentes;

A estrutura organizacional pode permitir que um agente escolha seu
trabalho numa parte qualquer de um problema que se encaixe em
suas responsabilidades;

O uso de leis sociais pode auxiliar na coordenação préplanejamento uma vez que ajuda a prever estados indesejáveis.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
55
Planejamento, Coordenação e
Execução Intercalados

Tipos diferentes de coordenação podem ser realizados dependendo
do nível de abstração com que o plano é representado;

Planejamento Parcial Global (PPG) é um método que assume que
decisões de planejamento e coordenação devem ser continuamente
revistas e revisadas;

PPG permite que algumas atividades sem coordenação sejam
toleradas e submetidas;

PPG é aplicável a domínios onde a garantia de coordenação não
precisa ser feita antes de qualquer execução.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
56
Planejamento, Coordenação e
Execução Intercalados

Coordenação via PPG:



17.11.2003
Cada agente decide seus objetivos e gera planos de curto
prazo para atingí-los;
Agentes trocam informações;
Agentes alteram planos locais para melhor coordenar suas
atividades;
Tópicos Avançados em Inteligência Artificial Simbólica I
57
Planejamento, Coordenação e
Execução Intercalados

Decomposição de tarefas

Formulação de planos locais

Abstração de planos locais

Identificação de objetivos globais parciais

Ação em planos globais parciais

Modificação em andamento

Re-alocação de tarefas
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
58
Coordenação de Planos em Tempo
de Execução sem Comunicação

Em algumas aplicações, re-coordenação em tempo real precisa
ser realizada quando os agentes não podem ou não devem se
comunicar;

Coordenação sem comunicação explícita:


17.11.2003
Permitir que os agentes façam inferências dos demais planos,
baseados em observações (Coordenação de planos baseada
em observações);
Permitir que os agentes façam inferências sobre as escolhas que
os demais vão fazer, baseados em hipóteses sobre suas
racionalidades ou visão do mundo (pontos focais).
Tópicos Avançados em Inteligência Artificial Simbólica I
59
Competição

Agentes com funções de utilidade conflitantes estão em
competição uns com os outros;

Um agente em um ambiente competitivo deve:





Reconhecer a existência de outros agentes no ambiente;
Computar alguns dos possíveis planos dos outros agentes;
Computar como os planos dos outros agentes interagem com os
seus planos;
Decidir sobre a melhor ação de acordo com essas interações.
Competição requer o modelo dos planos dos outros agentes,
entretanto, não há compromisso com planos conjuntos.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
60
Taxonomia da Coordenação
COORDENAÇÃO
COOPERAÇÃO
COMPETIÇÃO
PLANEJAMENTO
PLANEJAMENTO
CENTRALIZADO
17.11.2003
NEGOCIAÇÃO
PLANEJAMENTO
DISTRIBUÍDO
Tópicos Avançados em Inteligência Artificial Simbólica I
61
Conclusões

Planejamento multi-agente é necessário quando há outros
agentes no ambiente com os quais cooperar, competir ou
coordenar;

Um dos principais desafios do planejamento distribuído é
identificar quando e como aplicá-lo;

Representações e estratégias de propósito geral para RDP
ainda são evasivas;

A coordenação é um fator vital para o funcionamento de um
SMA, mantendo os benefícios advindos da RDP.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
62
Referências
[1] An Introduction to MultiAgent Systems, M. J. Wooldridge, 2002,
John Wiley and Sons.
[2] Multiagent Systems – A Modern Approach to Distributed Artificial
Intelligence, G. Weiss, 2000, The MIT Press.
[3] Multi-Agent Systems – An Introduction to Distributed Artificial
Intelligence, J. Ferber, 1999, Addison-Wesley.
[4] Artificial Intelligence – A Modern Approach (2nd Edition), S. Russel &
P. Norvig, 2002, Prentice-Hall.
17.11.2003
Tópicos Avançados em Inteligência Artificial Simbólica I
63