Organização em Sistemas
Multiagentes
Raquel de Miranda Barbosa
[email protected]
Estrutura da Apresentação
 Organização em SMA
 Paradigmas Organizacionais
 Modelos Organizacionais
Motivação
 Características coletivas do SMA
– Interação entre agentes
– Ambiente
– Organização
 Perguntas
– O que é uma organização exatamente?
– O que a constitui?
– Que aspectos são relevantes e devem ser modelados?
– Onde esta descrição é armazenada?
Organização em SMA
 Noção intuitiva (Hubner, 03)
– Mesa de trabalho
– Formigueiro
– Time de futebol
– Seres vivos
 Propósito nos sistemas
– Fazer com que sua finalidade seja facilmente mantida
Por que organizar um SMA?
 Se os agentes são autônomos (autonomia de
funcionamento, objetivos, etc.), como o sistema vai
atingir um objetivo global?
 A autonomia precisa ser “limitada”.
 Exemplo
– “todos nós somos autônomos, mas quando assumimos o
papel de aluno, já não podemos mais fazer certas coisas e
podemos fazer outras”.
 Na sociedade humana, a noção de papel é muito
utilizada para representar direitos e obrigações que,
de certa forma, controlam nossa autonomia.
Organizações de Agentes
Uma organização consiste em um
conjunto de restrições (regras de conduta)
adotadas por um grupo de agentes para que
possam atingir seus objetivos coletivos.
 Daí... Temos sempre...
– Os agentes
– Os papéis
 Que estabelecem relações (de autoridade ou não) entre os agentes
– Uma organização (o todo)
 TODOS os sistemas tem alguma forma de
Organização!
Organizações de Agentes
 Organização
– Coletivo de agentes organizado
– Conjunto de padrões regulares e flexíveis que moldam ou
restringem a atividade conjunta dentro de um grupo de
agentes
Dois pontos de vista de
organização
Tipos de Organização
centrado na
organização
centrado nos
agentes
agentes sem conhecimento
da organização
agentes com conhecimento
da organização
Tipos de Organização
centrado na
organização
centrado nos
agentes
agentes sem conhecimento
da organização
agentes com conhecimento
da organização
Tipos de Organização
centrado na
organização
centrado nos
agentes
agentes sem conhecimento
da organização
agentes com conhecimento
da organização
Tipos de Organização
centrado na
organização
centrado nos
agentes
agentes sem conhecimento
da organização
agentes com conhecimento
da organização
O que é uma organização?
A organização de um SMA é um conjunto de restrições
ao comportamento dos agentes a fim de conduzi-los
a uma finalidade comum.
 Estas restrições podem estar explícitas ou não e os agentes
podem ser ou não conscientes delas.
 No caso onde se deseja explicitar a organização (observada ou
institucionalizada), como descrevê-la?
 Que noções utilizar (grupos, papéis, tarefas, missões, autoridade,
etc.)?
 Qual o significado destas noções?
– Modelos Organizacionais
Paradigmas Organizacionais
Introdução
 Organizações de agentes
– Guiam interações entre agentes
 Pode influenciar relações de autoridade, fluxos de dados, alocação de
recursos, padrões de coordenação ou outras características do sistema.
 A forma, tamanho e características da estrutura
organizacional pode afetar o comportamento do
sistema.
Hierarquias
 Primeiro exemplo de projeto estruturado de SMA
 Estrutura de árvores
– nível mais alto: visão global
– interação: nodos conectados
Agente1
Controle
Informação
Agente
2
Agente
4
Agente
3
…
Agente
n
Hierarquias
 Autoridade: concentrada em um único agente (ou
grupo) em cada nível da hierarquia
 Tipo mais simples – hierarquia de dois níveis.
 Hierarquias
– Simples: o indivíduo na raiz tem total autoridade
– Uniformes: autoridade distribuída (exército); as decisões são
tomadas por quem tem o poder e a informação.
– Hierarquias múltiplas: esquema de departamentos.
Hierarquias
 Problemas:
– organização excessivamente rígida ou frágil, propensa a um
ponto de falha com conseqüências globais
 Ex. se o agente raiz falhar, toda a coesão da estrutura poderá ficar
comprometida
– gargalo
 Ex. se o agente raiz receber todos os dados produzidos por um grande
grupo abaixo dele
Holarquias
 Semelhantes às hierarquias, mas as unidades podem ser
agrupamentos que por sua vez, têm relações hierárquicas
 Os agrupamentos encapsulam a forma de executar tarefas,
o que facilita adaptação
 É possível acrescentar comunicação entre holons da
mesma organização, o que resulta numa estrutura mais
horizontal.
Coalisões
 Coalisão: aliança/acordo/união
 Subgrupos da sociedade de agentes
que se formam para atingir um objetivo
temporário.
 Tipicamente possuem estruturas horizontais
 Um agente pode participar de mais de uma coalisão
ao mesmo tempo.
 Às vezes tem um representante, que negocia
objetivos/tarefas com outras coalisões.
Coalisões
 Cada agente tenta maximizar a sua própria utilidade
 Não possui característica hierárquica
– mas é possível aninhando um grupo dentro do outro
 Obstáculos
– gerar estrutura de coalisões
– como resolver o objetivo apresentado para a coalisão
– recompensa incerta
– agentes “egoístas”
Times
 Consistem de um número de agentes
cooperativos que trabalham por um
objetivo comum (maximizar a utilidade do
time)
 Cada agente assume um ou mais papéis.
 Agentes coordenam-se para que suas
ações individuais sejam consistentes com
os objetivos do time
Times
 Normalmente contam com representações explícitas
de objetivos, crenças e planos do time.
 Construção do time:
– off-line (no design do sistema)
– agentes podem ser dinamicamente descobertos e avaliados para
pertencer ao time (através do uso de técnicas – Ex. redes de
contrato)
 Desafios:
– determinar alocação dos agentes
– manter consistência entre estes agentes durante a execução
– revisão do time quando ocorrem mudanças
Congregações
 Grupos de indivíduos que unem-se em uma
organização para extrair benefícios adicionais
– Ex. limitar interações
 Formadas a partir de interesses/habilidades comuns.
 Formações de longo prazo.
 Outras abordagens conhecidas na literatura podem
acabar resultando em congregações também.
Congregações
 Agentes precisam tirar vantagens da congregação
– tempo e energia investida na formação do grupo < benefícios
 Comunicação
– somente entre agentes da mesma congregação
Sociedades
 Sistemas abertos, flexíveis
– agentes heterogêneos entram e saem do grupo.
 Agentes:
– diferentes objetivos
– variados níveis de racionalidade
– capacidade heterogênea
– podem estar sub-organizados dentro
de outras organizações

 

Sociedades
 Impõem uma série de restrições ao comportamento,
chamadas de leis sociais.
– Limitam protocolos de comunicação
– Limitam comportamentos aceitáveis.
 Tratam reputação e confiança, para reforçar o
emprego das normas sociais.
 Agentes formalizam suas interações através de
contratos, que são verificados pela sociedade.
Federações
 Grupo de agentes coordenados por um
delegado (facilitador/mediador)
 Membros do grupo interagem somente
com o mediador
– atua como intermediário entre o grupo e o
mundo
 comunicando-se com os delegados de outros grupos
 O delegado pode também servir como
“alocador” de tarefas.
delegado
Mercados
 Semelhantes às federações, contando
com mediadores.
 Mercados podem ser usados para
alocar tarefas, negociar valores, etc…
 Mecanismo de Leilão é muito usado.
vendedores
compradores
Mercados
 Relação produtor/consumidor
– Compradores: ofertar, dar um lance
– Vendedores (leiloeiros): processam os lances e determinam
o vencedor
 Agentes são competitivos
– competição por tarefas, recursos, serviços ou produtos
Considerações
 Não existe um modelo que seja aplicável para todos
os sistemas multiagentes
– todos têm diferentes características mais adequadas para
alguns problemas e menos para outros
Modelos Organizacionais
Modelo Organizacional
 Pode ser entendido como uma linguagem de
modelagem utilizada para se criar especificações de
organizações de agentes que irão compor um SMA
(Coutinho, 09)
– Provê aos projetistas um arcabouço conceitual e uma ou
mais sintaxes
Níveis da Organização
 Estrutura Organizacional
– Persiste quando os componentes ou indivíduos entram ou
saem da organização
 Organização Concreta
– Possível instanciação de uma estrutura organizacional
Dimensões de Modelagem
(Coutinho, 09)
 Funcional
– Especificação de metas (objetivos, tarefas) e decomposição
de metas (planos conjuntos, inter-relacionamento de metas)
 Estrutural
– Especificação de papéis, grupos e relacionamentos entre eles
 Dialógica
– Especificação de estruturas de interação direta entre papéis
por troca de mensagens
Dimensões de Modelagem
(Coutinho, 09)
 Normativa
– Definição de normas (permissões, obrigações, etc) que interrelacionam e regulamentam elementos funcionais, estruturais
e dialógicos
 Ontológica
– Definição de estruturas conceituais compartilhadas
(ontologias de domínio)
TÆMS
(Decker, 1998)
TOVE
(Fox et al., 1998)
 Definição mais detalhada para organizações no
contexto empresarial
– Várias divisões e subdivisões
– Conjunto de agentes alocados nestas divisões
– Conjunto de papéis que os agentes assumem
– Conjunto de metas
TOVE
(Fox et al., 1998)
AALAADIN
(Ferber e Gutknecht, 1998)
 Organização é um conjunto de grupos com uma
determinada estrutura
 Cada grupo contém um conjunto de papéis
necessários ao seu funcionamento e agentes
membros
 Os papéis são representações abstratas para as
funções que os agentes disponibilizam
 Nenhuma restrição é feita quanto à arquitetura interna
dos agentes
AALAADIN
(Ferber e Gutknecht, 1998)
Grupo
assume
é membro
Agente
contém
Papel
AGR
(Ferber et al., 2003)
AGR
Cheeseboard Diagram
AGR
Reviewing Process of papers
AGR
AGR
Modelo Moise+ (Hubner, 03)
Estrutura: o que os agentes podem fazer
Modelo Moise+
Funcionamento: como os agentes podem fazer
Modelo Moise+
Deôntica: o que os agentes devem fazer
Especificação Estrutural
(Moise+)
Exemplo 1
Especificação Funcional (Moise+)
Plano
aceito
docPrazo(Dt)
m1
docOk
m2
m4
.7
aprovado
m1
insSub .85
m1
temDoc
m1
m1
m5
formPree
projAval
m1
temOri subEle subCor
m3
reuniaoOk
m1
m5
m4
relatorOk
missão
meta
taxa de sucesso
Especificação Deôntica
(Moise+)
 A relação entre estrutura e funcionamento é
estabelecida no nível individual:
– papel  missão
 tipo: permissão ou obrigação
 restrições temporais
perm(p,m,tc)
obl(p,m,tc)
Especificação Deôntica (Moise+)
Papel
Relação Deôntica
Missão
Restrições
Temporais
presidente
per
schingresso.m4
[feb/02 feb/28]
secretário
per
schingresso.m2
Any
secretário
per
schingresso.m3
Any
membro
per
schingresso.m5
Any
candidato
per
schingresso.m1
Any
aluno
obl
schprova1.m43
Any
professor
obl
schprova1.m42
Periodic 3
funcionamento
estrutura
esquemas
papéis
missões
relações deônticas
grType
scType
instância de
grupo
papel
instanciado
instância de
esquema
missão
instanciada
agRole
agMis
agentes
finalidade
entidade
organizacional
grupos
especificação
organizacional
Entidade Organizacional
(Moise+)
ISLANDER
(Esteva et al., 02)
 Baseado em instituições eletrônicas
 Instituições definem os papéis participantes, as
interações válidas entre os participantes e as normas
que irão governá-las.
 Composta por:
– Framework de Diálogos
– Cenas
– Estrutura Performativa
– Normas
Modelo PopOrg
(Costa e Dimuro, 07)
 Analisa 2 aspectos de SMA:
– População
 conjunto de agentes que o habitam, juntamente com o conjunto de todos
os comportamentos que eles são capazes de executar e o conjunto de
todos os processos de interação que eles podem estabelecer entre si
– Organização
 composta por papéis organizacionais e links organizacionais
 Níveis micro e macro-organizacionais
– Nível micro: onde ocorrem as interações organizacionais em caráter
individual (constituído por trocas entre papéis individualizados)
– Nível macro: o nível das interações de caráter coletivo (trocas entre
grupos de papéis)
Modelo PopOrg
(Costa e Dimuro, 07)
 Baseado na distinção entre aspectos intencionais e
extensionais de um sistema
– Intencionais: funcionamento interno do sistema (representado
através de normas, valores, etc)
– Extensionais: aspectos externos do sistema, ou seja, o que
pode ser observado do ponto de vista externo ao sistema
(ações executadas, objetos trocados, etc)
 O modelo PopOrg concentra-se na representação dos
aspectos extencionais
Modelo PopOrg
(Costa e Dimuro, 07)
PopOrg = (Pop, Org, imp)
Pop = (Ag, Act, Bh, Ep, bc, ec)
Org = (Org , Org )
Org = (R, L, lc)
Org = (G, L)
Modelo PopOrg
(Costa e Dimuro, 07)
Pop = (Ag, Act, Bh, Ep, bc, ec)
 Ag é o conjunto de agentes chamado de população;
 Act é o conjunto de todas as ações (ações de comunicação e
ações sobre objetos concretos);

Bh  [T (Act)] é o conjunto de todos os comportamentos
(seqüências de ações que os agentes são capazes de realizar);
 Ep  [T (Act)  (Act)] é o conjunto de todos os processos
de troca que quaisquer dois agentes podem realizar;
 bc : Ag (Bh) é uma função de capacidade comportamental;
 ec : Ag  Ag (Ep) é uma função de capacidade de troca
Modelo PopOrg
(Costa e Dimuro, 07)
Org = (R, L, lc)
 R (Bh), é o conjunto de papéis que os agentes podem
desempenhar no sistema multiagente;
 L  R  R  Ep é o conjunto de micro-ligações que podem ser
estabelecidas entre papéis, cada micro-ligação especificando um
processo de troca que os agentes que desempenham os papéis
ligados pela micro-ligação podem ter de realizar;
 lc : R  R (L) é a capacidade de micro-ligação dos pares
de papéis, ou seja, o conjunto de micro-ligações que cada par de
papéis pode estabelecer entre si;
Modelo PopOrg
(Costa e Dimuro, 07)
Org = (G, L)
 G  (R)  (L) é o conjunto de grupos sociais do sistema
multiagente, cada grupo social G = (R,L)  G sendo não-vazio e
fechado para a sua estrutura micro-organizacional
 L  G  G  (L) é o conjunto de macro-ligações que podem
ser estabelecidas entre os grupos sociais da estrutura macroorganizacional, cada macro-ligação (G0,G1,LG0,G1)  L
respeitando a estrutura micro-organizacional dos grupos sociais
que a constituem
Modelo PopOrg
(Costa e Dimuro, 07)
 Notação baseada em teoria dos conjuntos
 Modelo mínimo de organização
AGR
MOISE+
Modelo PopOrg
(Costa e Dimuro, 07)
 Notação baseada em teoria dos conjuntos
 Modelo mínimo de organização
AGR
MOISE+
PopOrg
Considerações
 A organização de um SMA é um conjunto de
restrições ao comportamento dos agentes a fim de
conduzí-los a uma finalidade comum.
 Organização observada
 Organização institucionalizada, descrita a partir de
modelos
 Os agentes podem ou não ter capacidade de
raciocinar sobre sua organização.
Exercício
 N agentes
 Dinheiro global: R$ 600,00
 Objetivo:
– Terminar as compras o mais rápido possível (quantidade de
ciclos utilizada até que o último item seja comprado)
 A cada ciclo cada agente pode se movimentar uma
casa na horizontal ou vertical
 Cada passo custa R$ 1,50
 Só podem trocar dinheiro quando se encontrarem
Exercício
Item
Quant.
Valor
Loja 1 Loja 2 Loja 3 Loja 4 Loja 5 Loja 6 Loja 7 Loja 8 Loja 9 Loja 10
Livro
1
40
CD
1
25
Calça
1
80
x
Flores
1
20
x
Óculos escuros
1
70
x
x
Bermuda de
surfista
1
40
x
x
Game
1
70
Panela
1
55
TOTAL
400
x
x
x
x
x
x
x
x
x
Exercício
(x,y)
1
1
Entrada
2
3
4
5
6
7
8
9
10
2
11
12
13
14
Loja 9
3
Loja 5
Loja 10
4
5
6
7
Loja 7
Loja 3
8
Loja 1
9
10
11
Loja 4
12
13
14
15
15
Loja 2
Loja 8
Loja 6