Exemplos de Sistemas-Multi-Agente
Professor
Edson Emílio Scalabrin
PUCPR / PPGIA
e-mail: [email protected]
Origem dos Sistemas Multi-Agente
• EUA
• Explorava-se essencialmente a relação
existente entre arquitetura e modo de
raciocínio
• Deu origem a dois tipos de controle :
– quadro negro [Erman et al. 1980],
– BEINGS e CyC [Lenat & Guha 1990],
Atores [Hewitt 1977],
Open System [Hewitt 1991]
PUCPR/PPGIA/Edson Emílio
Scalabrin
2
Exemplo de Sistema Multi-Agente
DVMT (Distributed Vehicule Monitoring Test)
– Projeto :
Massachusetts [Lesser e Corkill 1983]
a percepção e o reconhecimento de situações/configurações
distribuídas ;
– Funcionamento :
vários sensores enviam informações aos agentes de
processamento, implementados sob a forma de quadro negro ;
– Problema :
obter, através dos agentes, um estado coerente de uma situação
de tráfego rodoviário e então identificar e monitorar os veículos a
partir das informações -- redundantes, contraditórios e ruidosas -vindas dos sensores.
PUCPR/PPGIA/Edson Emílio
Scalabrin
3
Exemplo de ...
continuação
– Contribuições do projeto DVMT:
• examinou-se um grande número de configurações
envolvendo sensores e agentes de processamento
• analisou-se a problemática do planejamento multi-agente
a partir de planos parciais
• definiu-se as bases dos mecanismos de cooperação e
negociação
– Influência :
• puramente norte americana
PUCPR/PPGIA/Edson Emílio
Scalabrin
4
Exemplo de Plataforma Multi-Agente
MACE
[Gasser et al. 1987]
– 1a plataforma multi-agente genérica
– 1a explicação clara a respeito de :
• como implementar um sistema de Inteligência
Artificial Distribuída, e
• quais são os componentes essenciais de uma
plataforma genérica.
PUCPR/PPGIA/Edson Emílio
Scalabrin
5
Exemplo de Plataforma ...
continuação
Introdução das trocas de mensagens dos
atores mostrou que :
– é possível implementar um sistema multi-agente
a partir da noção de troca de mensagens
– a troca de mensagens não é suficiente
– uma organização social não pode-se reduzir a um
simples mecanismo de comunicação
– é necessário uma representação dos outros, de
tal modo que um agente possa raciocinar sobre
suas competências e suas crenças
PUCPR/PPGIA/Edson Emílio
Scalabrin
6
Exemplo de Plataforma ...
continuação
Introdução das diferenças entre :
 competência efetiva
(i.e. qualidade de quem é capaz de fazer uma determinada coisa)
 habilidade diretamente aplicável
(i.e. qualidade de hábil)
 conhecimento que um agente tem sobre sua
própria competência.
Todas as plataformas de desenvolvimento de SMA
são descendentes diretamente ou indiretamente de MACE.
PUCPR/PPGIA/Edson Emílio
Scalabrin
7
Exemplo de Protocolo de Negociação
Contract-Net
[Smith 1980]
Metáfora
Trata-se de um sistema oportunista de
alocação de tarefas baseado no princípio da
negociação de contrato do tipo mercado público, e a
seleção mútua das partes envolvidas.
PUCPR/PPGIA/Edson Emílio
Scalabrin
8
Exemplo de Protocolo ...
continuação
Origem :
– o protocolo CNET foi inicialmente aplicado a uma
rede de sensores acústicos distribuídos
– os agentes eram inteiramente cooperativos
– a seleção dos eventuais contratantes era baseada
essencialmente :
• na capacidade de processamento (cálculo) e
• na carga atual de um agente
PUCPR/PPGIA/Edson Emílio
Scalabrin
9
Exemplo de Protocolo ...
continuação
Natureza
– o protocolo CNET organiza o controle de
execução entre um programa :
• emissor de uma mensagem (agente “manager”) e
• um ou vários receptores (agentes “contractors”)
– procedural call  contract net  data driven
programming
O CNET é um dos paradigmas mais importante já desenvolvido
em IAD para a alocação dinâmica de tarefas.
PUCPR/PPGIA/Edson Emílio
Scalabrin
10
Exemplo de Protocolo ...
Chama de
ofertas
continuação
Envio de
propostas
Fases da
Negociação
Análise e
Seleção de
proposta
Fechamento
do contrato
PUCPR/PPGIA/Edson Emílio
Scalabrin
11
Exemplo de Protocolo ...
continuação
Mensagem: ChamaDeOfertas
Mensagem: Proposta
Para : *
De : Explorador-25
Contrato : Perfurar-25-234
DescriçãoDeTarefa :
TipoDeTarefa : Perfurar
QualidadesRequeridas :
DeveTer : SistemaPerfuração
DevePoder : PerfurarSoloMole
FormatoDaProposta :
Posição: <Lat, Long>
QualidadesPerfuração:
{TipoDeSolo : Performance}
DataExpiração :
20 junho 2193 13:06:46
Fim ChamaDeOfertas
Para : Explorador-25
De : Perfurador-18
Contrato : Perfurar-25-234
DescriçãoProposta :
Posição: <47N, 17W>
QualidadesPerfuração :
{areia : 0,5 argila : 0,3 Xisto : 0,8}
Fim Proposta
PUCPR/PPGIA/Edson Emílio
Scalabrin
12
Exemplo de Protocolo ...
continuação
Interpretação dos tipos de mensagens :
– chamada de ofertas : o agente manager tenta "comprar”
serviços de outros agentes a um preço (freqüentemente um
restrição de tempo) no máximo igual o especificado na
chamada de ofertas.
– propostas : os agentes contratantes potenciais tentam
"vender" seus serviços.
– alocação de um contrato (a escolha da melhor proposta) :
o agente manager está "comprando" os serviços dos
contratantes potenciais.
– aceitação do engajamento : o(s) contratante(s) vendeu(ram)
efetivamente seu(s) serviço(s).
PUCPR/PPGIA/Edson Emílio
Scalabrin
13
Exemplo de Protocolo ...
continuação
Comentários ...
– O CNET é uma generalização da abordagem
cliente/servidor
– O CNET resolve o problema de distribuição de
tarefas :
• sem utilizar uma zona de memória comum e
• sem a necessidade de identificar precisamente o
destinatário da mensagem como por exemplo nos
sistemas baseados em atores
Se nenhum agente satisfaz os critérios da chamada de oferta,
o contrato não é alocado.
PUCPR/PPGIA/Edson Emílio
Scalabrin
14
Exemplo de Protocolo ...
continuação
Limites
– O CNET não apresenta um modelo que permite
levar em conta de modo eficiente a relocação de
tarefas, seja no caso :
• de falha de sistema ou
• de problema de estrangulamento.
PUCPR/PPGIA/Edson Emílio
Scalabrin
15
Sistemas Multi-agente :
Domínios de Aplicação
Resolução distribuída
de problemas
Sistemas
multi-agente
Resolução de
problemas
Resolução de
problemas distribuídos
Simulação
multi-agente
Técnicas distribuídas
de Resolução de
problemas
Construção de
mundos hipotéticos
Robótica distribuída
Concepção kénética
de programas
PUCPR/PPGIA/Edson Emílio
Scalabrin
16
Sistemas Multi-Agente :
Resolução distribuída de problemas
Características :
– é possível efetuar uma tarefa complexa através de
um conjunto de especialistas que dispõem de
competências complementares
– é a expertise ou o modo de resolução que é
distribuído, sem que o domínio o seja
Exemplos :
– Construção de um carro de corrida, especialistas :
• Motores, escolha e teste de pneumáticos, chassis e
suspensão, combustível, gestão da corrida + interface com
o piloto.
PUCPR/PPGIA/Edson Emílio
Scalabrin
17
Exemplo de Resolução distribuída ...
Sistema CONDOR:
[Iffenecker & Ferber 1992]
– envolvendo especialistas em concepção, montagem,
materiais, planejamento, marketing, etc.
– os especialistas são representados sob a forma de um
conjunto de agentes
– os agentes possuem sua própria expertise e intervêm
em diferentes momentos durante a realização do
produto
PUCPR/PPGIA/Edson Emílio
Scalabrin
18
Exemplo de Resolução distribuída ...
continuação
Organização do CONDOR :
– o sistema assume a forma de uma arquitetura de quadro
negro ;
– representa grupos de trabalhos :
• o grupo “qualidade” ;
• o grupo “decisão” ;
• o grupo “laboratório de pesquisa” ;
– cada grupo trabalha utilizando seu próprio protocolo de
automatização de fluxo de informação, igual o “work
flow” atual.
PUCPR/PPGIA/Edson Emílio
Scalabrin
19
Exemplo de Resolução distribuída ...
continuação
KBS-SHIP :
– um sistema dedicado ao monitoramento e manutenção de
equipamentos de um navio comercial.
– o sistema integra vários sistemas especialistas :
• pilotagem, carregamento de frete, manutenção dos
equipamentos eletrônicos, diagnóstico de falhas, etc.
• eles operam sobre uma arquitetura SMA, controlado por
um Expert encarregado da gestão das comunicações via
uma rede Ethernet e da resolução de conflitos entre os
agentes.
PUCPR/PPGIA/Edson Emílio
Scalabrin
20
Exemplo de Resolução distribuída ...
continuação
Flavors Paint Shop :
– um sistema de controle de processos industrial utilizado
para pintar caminhões.
– Problema : na saída de uma linha de montagem
• os caminhões devem ser pintados de uma dada cor e
em função dos desejos dos clientes
• o número de postos de pintura é inferior ao número de
cores disponíveis
• a mudança de configuração dos postos eleva o
consumo de matéria e de tempo
PUCPR/PPGIA/Edson Emílio
Scalabrin
21
Exemplo de Resolução distribuída ...
continuação
Características do sistema Flavors Paint Shop :
– cada posto de pintura é um agente
– quando um posto está livre, ele aceita um novo caminhão para ser
pintado (os caminhões são colocados em uma fila de espera)
– regras de escolha:
• pegar o primeiro caminhão da fila que requer a mesma cor que está
disponível no momento
• se não há caminhão desta cor, pegar o caminhão mais prioritário e
alocar ao posto a cor requerida
• se não há caminhão prioritário, pegar o próximo da fila e alocar ao
posto a cor requerida
PUCPR/PPGIA/Edson Emílio
Scalabrin
22
Exemplo de Resolução distribuída ...
continuação
Resultados do sistema Flavors Paint Shop :
–
–
–
–
redução drástica do custo de manutenção do sistema
redução (50%) das operações de troca de pintura
economia de um milhão de dólares por ano
o sistema pode levar em conta, sem maiores problemas,
as falhas de postos de pintura
PUCPR/PPGIA/Edson Emílio
Scalabrin
23
Sistemas Multi-Agente :
Resolução distribuída de problemas distribuídos
Características:
– o domínio é distribuído
– os agentes podem ter competências parecidas
Exemplos :
– monitoramento de redes de energia ou de
telecomunicações,
• a supervisão é dsitribuída sobre cada um dos nós
– a percepção distribuída (ex. DVMT)
PUCPR/PPGIA/Edson Emílio
Scalabrin
24
Exemplo de resolução distribuída de problemas ...
continuação
Sistema IDEAL
[Onera e Alcatel-Alsthom]
– um sistema SMA dedicado ao monitoramento e
diagnóstico de redes de telecomunicações
– IDEAL compreende três tipos de agentes :
• supervisor, encarregado de localizar e diagnosticar falhas
• acompanhamento, encarregado de manter a coerência entre
o estado real da rede e a visão dos agentes
• operador de manutenção, encarregado de executar testes e
reparar elementos da rede
PUCPR/PPGIA/Edson Emílio
Scalabrin
25
Exemplo de resolução distribuída de problemas ...
continuação
Características dos agentes do IDEAL :
– apresentam uma arquitetura de quadro negro
– cada agente tem um conjunto de módulos:
• comunicação, que gerencia os protocolos de comunicação
• expert, que contem os conhecimentos relativos a supervisão da rede
• cooperação, que gerencia as tabelas de conhecidos (acquaintance),
a representação de si e os modelos de diálogo
• visualizador, que permite ao usuário, através de uma interface
gráfica, acompanhar o funcionamento do agente e intervir se
necessário
• controle, que gerencia o conjunto de atividades dos agentes
PUCPR/PPGIA/Edson Emílio
Scalabrin
26
Sistemas Multi-Agente :
Resolução por coordenação
Problema :
– Encontrar uma solução para um problema cujo
enunciado é bem definido e o conjunto de
informações é inteiramente disponível.
PUCPR/PPGIA/Edson Emílio
Scalabrin
27
Exemplo de resolução ...
• determinar uma alocação de tarefas para uma
máquina
• definir a agenda de um colega
• dar a seqüência de ações a ser executada para sair
de um labirinto ou para disparar um míssil
• resolver quebra-cabeça ou demonstrar um teorema
• empilhar cubos ou componentes mecânicos
PUCPR/PPGIA/Edson Emílio
Scalabrin
28
Exemplo de resolução ...
continuação
Eco-Resolução
– Problema : empilhamento de cubos
– Iniciativa : o problema é visto como um SMA
• cada cubo é um agente
• os agentes buscam incessantemente satisfazer seus
objetivos
• as relações são restrições que os agentes devem
respeitar
PUCPR/PPGIA/Edson Emílio
Scalabrin
29
Sistemas Multi-Agente :
Simulação multi-agente
Características e Utilização
– utiliza-se a simulação para tentar explicar e prever
fenômenos naturais :
•
•
•
•
física, química,
biologia, ecologia,
geografia e
ciências sociais
– os modelos são dados sob a forma de relações
matemáticas entre variáveis que representam grandezas
físicas mesuráveis no mundo real.
PUCPR/PPGIA/Edson Emílio
Scalabrin
30
Exemplo simulação ...
continuação
Presa-Predador
• dN1 = r1N1 - PN1N2
dt
• P:
• N1 e N2 :
• a:
• r1 :
• d2 :
dN2 = aPN1N2 - d2N2
dt
coeficiente de destruição (predador)
as números de presa e predadores
eficiência que os predadores convertem
os alimentos em descendentes
determina a fecundidade das presas
a taxa de mortalidade dos predadores
PUCPR/PPGIA/Edson Emílio
Scalabrin
31
Exemplo simulação ...
continuação
Problemas da simulação apenas numérica
– os modelos matemáticos ligam unicamente parâmetros
que se situam todos ao mesmo nível de análise.
– Ex. é impossível ligar o tamanho do efetivo as tomadas de
decisões efetuadas pelos indivíduos
Pode-se dizer, que estes níveis de análise são isolados, à medida que
é impossível fazer corresponder os comportamentos efetuados a um
nível micro as variáveis globais mesuráveis a um nível macro.
PUCPR/PPGIA/Edson Emílio
Scalabrin
32
Exemplo simulação ...
continuação
Complexidade e realismo dos parâmetros na
simulação apenas numérica
– para ser utilizável e corresponder a realidade, as equações
comportam um grande número de parâmetros difíceis a
estimar e sem realismo
– o coeficiente de eficiência a é bastante pobre
Não é considerado o conjunto de comportamentos
complexos que podem ter um impacto direto sobre a
fecundidade :
• hierarquia e dominação, estratégia sexual,
• utilização do território e construção de abrigos.
PUCPR/PPGIA/Edson Emílio
Scalabrin
33
Exemplo simulação ...
continuação
Dificuldade em modelar as ações
– como levar em conta as ações dos indivíduos, bem
como as modificações efetivas do ambiente
decorrente de seus comportamentos ?
Em particular sabendo que,
os fenômenos coletivos resultam de um conjunto de
tomadas de decisões individuais, que lavam em conta
os comportamentos dos outros atores do sistema
PUCPR/PPGIA/Edson Emílio
Scalabrin
34
Exemplo simulação ...
continuação
Qual é o interesse da simulação multi-agente?
É poder levar em conta
– tanto os parâmetros quantitativos
• parâmetros numéricos
– quanto as informações qualitativas
• comportamentos individuais, recorrendo
eventualmente à estratégias de raciocínio
PUCPR/PPGIA/Edson Emílio
Scalabrin
35
Exemplo simulação ...
continuação
Vantagens da modelagem multi-agente
– é possível integrar na mesma modelagem, equações
diferencias e comportamentos baseados em regras
simbólicas
– é fácil integrar modificações, onde cada enriquecimento
do modelo é realizado pela adição de novas regras de
comportamento, agindo a nível de indivíduo
– os indivíduos guardam suas identidades
– é possível acrescentar novos tipos de agentes, dispondo
de seus próprios modelos de comportamento, que irão
interagir com os agentes já definidos.
PUCPR/PPGIA/Edson Emílio
Scalabrin
36
Exemplo simulação ...
continuação
Exemplo: modelagem de uma floresta.
– pode-se introduzir novas espécies animais ou vegetais e
analisar suas interações com aquelas já modeladas.
PUCPR/PPGIA/Edson Emílio
Scalabrin
37
Exemplo simulação ...
continuação
Projeto SIMDELTA
[Cambier et al. 1992]
– um simulador para sintetizar os conhecimentos de um
conjunto de especialistas em :
• ecologia, biologia, antropologia, etc.
– conhecimentos adquiridos após vários anos de estudos
sobre sistema de pesca do delta central do Nigéria.
Objetivo do projeto : modelar informações :
• quantitativas (a evolução das enchentes)
• qualitativas (as técnicas de pesca praticadas)
PUCPR/PPGIA/Edson Emílio
Scalabrin
38
Exemplo simulação ...
continuação
Características do SIMDELTA :
– Permite simular, em mesmo tempo, a dinâmica da
população de peixes, incluindo :
• fatores biológicos e topologicos na dinâmica da
população ;
OBS : estes fatores afetam a evolução da população e a tomada
de decisão dos pescadores.
• Os agentes são:
– baldes de peixes
– pescadores
PUCPR/PPGIA/Edson Emílio
Scalabrin
39
Exemplo simulação ...
continuação
Definição dos agentes SIMDELTA
– os biotipos
• representam porções do ambiente
– os peixes
• possuem um comportamento bastante reativo
– os pescadores
• comportamento de agentes cognitivos
PUCPR/PPGIA/Edson Emílio
Scalabrin
40
Exemplo simulação ...
continuação
Ambiente = Biotipos
Conexões entre biótipos mudam
em função do nível das águas
PUCPR/PPGIA/Edson Emílio
Scalabrin
41
Exemplo simulação ...
continuação
Para cada biotipo :
– uma função de recurso, indica a quantidade de
alimento disponível para uma população de
peixes em função do tempo
Baldes de peixes (agentes):
– representam conjuntos de peixes
– parâmetros estratégicos para a adaptação:
• tamanho e número de ovos, processo de
migração, regime, etc.
PUCPR/PPGIA/Edson Emílio
Scalabrin
42
Exemplo simulação ...
continuação
Cada pescador
– é representado por um agente cognitivo
– seu comportamento é descrito por um sistema
baseado em conhecimentos, envolvendo:
• uma base de dados, que contem suas crenças e sua
memória de pescador
• um sistema de regras, que representa sua estratégia
cognitiva para explorar os biotipos
PUCPR/PPGIA/Edson Emílio
Scalabrin
43
Exemplo simulação ...
continuação
Testes feitos sobre SIMDELTA
• estudo sobre a dinâmica de uma população de peixes em
função de um esforço de pesca cada vez maior.
• dados para a simulação :
– o comportamento de peixes de água doce e
– os conhecimentos dos biologistas a respeito da
reprodução, crescimento, migração e mortalidade
dos peixes
PUCPR/PPGIA/Edson Emílio
Scalabrin
44
Exemplo simulação ...
continuação
Projeto SIMPOP
[Bura et al. 1993]
Objetivo :
– modelar a dinâmica de evolução de um sistema de
cidades, em particular :
 a gênese (formação dos seres) e
 o desenvolvimento e a concentração das funções urbanas
em diferentes níveis, durante um período de tempo
(+/- 2000 anos)
PUCPR/PPGIA/Edson Emílio
Scalabrin
45
Exemplo simulação ...
continuação
Características do SIMPOP
– o ambiente é representado por um conjunto de “lugares” de
tamanhos e formas variadas (essencialmente quadradas e
hexagonais).
– estes elementos são caracterizados :
• pela sua natureza : planícies, montanhas, mares, pântanos ;
• pelos seus recursos naturais : agricultura, pesca, minerais ;
• pelas vias de comunicação : rios, estradas, etc.
– os recursos correspondem o potencial que uma população
tem para explorar a produtividade levando em conta as
possibilidades técnicas ou as atividades de um povoado vizinho
PUCPR/PPGIA/Edson Emílio
Scalabrin
46
Exemplo simulação ...
continuação
Agentes do SIMPOP
– cada lugar é representado por um agente
“cidade”, que pode ser um povoado ou uma
metrópole
– as características das cidades
• número de habitantes,
• riqueza econômica e
• funções (agricultura, economia, indústria,
administração).
PUCPR/PPGIA/Edson Emílio
Scalabrin
47
Exemplo simulação ...
continuação
Comportamento de um agente cidade
• é dado pela soma dos comportamentos de seus
habitantes
• os habitantes são representados por funções
econômicas, correspondendo aos principais grupos
econômicos
– Ex. em um povoado a maior parte de sua população é
associada a função agrícola.
PUCPR/PPGIA/Edson Emílio
Scalabrin
48
Exemplo simulação ...
continuação
Comentários
• as principais entidades do sistema são os agentes “cidade”
• os agentes “cidade” são imóveis
• as interações entre estes agentes se dão através de
transferências de:
– bens, valores monetários, serviços e habitantes ;
– as transferências se exprimem sob a forma de mecanismos de
ofertas e demandas entre as cidades ;
– certas cidades tendem a crescer e vários fenômenos locais vão
reforçar as diferenças entre elas, de tal maneira, a formar uma
espécie de “hierarquia” de cidades (seu tamanho e sua riqueza).
PUCPR/PPGIA/Edson Emílio
Scalabrin
49