ads:
UNIVERSIDADE CATÓLICA DE PELOTAS
ESCOLA DE INFORMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA
Construção de Planos BDI a partir de
Políticas Ótimas de POMDPs, com
Aplicação na Auto-Regulação de Trocas
Sociais em Sistemas Multiagentes
por
Diego Rodrigues Pereira
Dissertação apresentada como
requisito parcial para a obtenção do grau de
Mestre em Ciência da Computação
Orientadora: Prof. Dr. Graçaliz Pereira Dimuro
Co-orientador: Prof. Dr. Antônio Carlos da Rocha Costa
Colaborador: DM-2008/1-006
Pelotas, abril de 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Dedico à Fernanda e a mim.
Por um futuro melhor para nós.
ads:
AGRADECIMENTOS
Agradeço à Fernanda por me apoiar durante todo o tempo.
Agradeço aos meus pais por terem dado um empurrão inicial.
Agradeço à minha tia Regina por ter me apoiado no início do mestrado.
Agradeço à professora Graçaliz pela grande orientação durante todo o mestrado.
Agradeço ao meu colega Luciano pela implementação do nosso sistema.
Agradeço ao Programa de Pós-graduação em Engenharia Naval e Oceânica da
UFRJ e à Petrobrás, via convênio COPPETEC/FUNDAZA, pela bolsa de apoio técnico
vinculada ao projeto "Simulação da Indústria Naval".
Conhece a ti mesmo.
— ENTRADA DO TEMPLO DE APOLO EM DELPHOS
SUMÁRIO
LISTA DE FIGURAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
LISTA DE TABELAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
LISTA DE ABREVIATURAS E SIGLAS . . . . . . . . . . . . . . . . . . . . . 10
RESUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1 O Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Auto-Regulação de Trocas Sociais em Sistemas Multiagentes . . . . . . . 15
1.4 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5 Organização do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 O MODELO DE AGENTES BDI . . . . . . . . . . . . . . . . . . . . . . . 17
2.1 Conceitos Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 Intenções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Implementando Agentes Racionais . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 O Processo de Deliberação . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Estratégias de Comprometimento . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Reconsideração de Intenções . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 PROCESSOS DE DECISÃO DE MARKOV . . . . . . . . . . . . . . . . . 24
3.1 Arquitetura Básica de um MDP . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Caráter ótimo em Problemas de Decisão Seqüencial . . . . . . . . . . . 26
3.3 Utilidades de Estados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 O Algoritmo de Iteração de Valor . . . . . . . . . . . . . . . . . . . . . . 28
3.5 Iteração de Política . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.6 Observação Parcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.6.1 O Algoritmo Witness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.7 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 UMA RELAÇÃO ENTRE OS MODELOS MDP E BDI . . . . . . . . . . . 34
4.1 Relação entre Intenções, Planos e Políticas . . . . . . . . . . . . . . . . . 35
4.2 De Políticas para I-Plans . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 EXTRAINDO PLANOS BDI DE POLÍTICAS ÓTIMAS . . . . . . . . . . 40
5.1 De Políticas Ótimas de MDPs para Planos BDIs . . . . . . . . . . . . . . 40
5.1.1 Exemplo: Navegação no Ambiente 3 × 4 . . . . . . . . . . . . . . . . . . 41
5.2 De Politicas Ótimas de POMDPs para Planos BDIs . . . . . . . . . . . . 43
5.2.1 Exemplo: O Problema do Tigre . . . . . . . . . . . . . . . . . . . . . . . 43
6 AUTO-REGULAÇÃO DE TROCAS SOCIAIS . . . . . . . . . . . . . . . . 46
6.1 Valores de Trocas Sociais . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.2 Estrutura das Trocas Sociais . . . . . . . . . . . . . . . . . . . . . . . . 47
6.3 Agentes com Personalidades . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.4 Equilíbrio Social . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.5 Processo de Decisão sobre Trocas Baseadas em Personalidades . . . . . 49
6.5.1 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7 ANÁLISE DAS SIMULAÇÕES . . . . . . . . . . . . . . . . . . . . . . . . 55
7.1 Metodologia das Simulações . . . . . . . . . . . . . . . . . . . . . . . . . 55
7.2 Personalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.2.1 Tolerante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.2.2 Fanático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.2.3 Altruísta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.2.4 Egoísta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
7.3 Simulações supervisionadas . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.4 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
8 CONCLUSÃO E TRABALHOS FUTUROS . . . . . . . . . . . . . . . . . 67
REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
ANEXO A: MODELOS POMDP . . . . . . . . . . . . . . . . . . . . . . . . . . 74
ANEXO B: MATRIZES DOS GRAFOS DE POLÍTICAS . . . . . . . . . . . . 87
ANEXO C: OUTROS EXEMPLOS DE SIMULAÇÕES . . . . . . . . . . . . . 93
LISTA DE FIGURAS
Figura 3.1 Um MDP que modela uma interação síncrona entre o agente e o am-
biente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Figura 3.2 Um POMDP com o SE (estimador de estados) e uma Política (π) . . 31
Figura 3.3 Regiões definidas pelo algoritmo Witness . . . . . . . . . . . . . . . 33
Figura 5.1 Um ambiente simples 3×4 que apresenta o agente com um problema
de decisão seqüencial . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Figura 5.2 Ilustração do modelo de transição do ambiente . . . . . . . . . . . . 42
Figura 5.3 Utilidades dos estados . . . . . . . . . . . . . . . . . . . . . . . . . 42
Figura 5.4 Política ótima obtida com o algoritmo . . . . . . . . . . . . . . . . . 42
Figura 5.5 Grafo de Políticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Figura 5.6 Exemplo de Regras . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Figura 6.1 Trocas do Tipo I e II . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Figura 6.2 Definição do POMDP (personalidade egoísta) como entrada para o
algoritmo Witness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Figura 6.3 Regra 0 e 1 para a implementação na plataforma Jason . . . . . . . . 53
Figura 6.4 Grafo de Políticas para o POMDP da Fig. 6.2 . . . . . . . . . . . . . 54
Figura 7.1 Exemplo do comportamento do agente β com traço de personalidade
tolerante em trocas não supervisionadas . . . . . . . . . . . . . . . . 57
Figura 7.2 Exemplo do comportamento de um agente β com traço de personali-
dade fanático em trocas não supervisionadas . . . . . . . . . . . . . 58
Figura 7.3 Função de observação modificada para o traço de personalidade Al-
truísta Forte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Figura 7.4 Exemplo do comportamento de um agente β com traço de personali-
dade altruísta em trocas não supervisionadas . . . . . . . . . . . . . 59
Figura 7.5 Função de observação modificada para o traço de personalidade
Egoísta Forte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Figura 7.6 Exemplo do comportamento de um agente β com traço de personali-
dade egoísta em trocas não supervisionadas . . . . . . . . . . . . . . 60
Figura 7.7 Exemplo do comportamento de um agente β com traço de personali-
dade tolerante em trocas supervisionadas . . . . . . . . . . . . . . . 62
Figura 7.8 Exemplo do comportamento de um agente β com traço de personali-
dade tolerante em trocas 50% supervisionadas, onde o balanço médio
foi de −0, 84 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Figura 7.9 Exemplo do comportamento de um agente β com traço de personali-
dade altruísta em trocas supervisionadas . . . . . . . . . . . . . . . . 63
Figura 7.10 Exemplo do comportamento de um agente β com traço de personali-
dade altruísta em trocas 90% supervisionadas . . . . . . . . . . . . . 64
Figura 7.11 Exemplo do comportamento de um agente β com traço de personali-
dade egoísta em trocas supervisionadas . . . . . . . . . . . . . . . . 64
Figura 7.12 Exemplo do comportamento de um agente β com traço de personali-
dade egoísta em trocas 90% supervisionadas . . . . . . . . . . . . . . 65
Figura 7.13 Exemplo do comportamento de um agente β com traço de personali-
dade altruísta forte em trocas supervisionadas . . . . . . . . . . . . . 65
Figura 7.14 Exemplo do comportamento de um agente β com traço de personali-
dade egoísta forte em trocas supervisionadas . . . . . . . . . . . . . 66
Figura 8.1 Definição do POMDP Tolerante para o estado E+ . . . . . . . . . . 75
Figura 8.2 Definição do POMDP Tolerante para o estado E0 . . . . . . . . . . . 76
Figura 8.3 Definição do POMDP Tolerante para o estado E− . . . . . . . . . . 77
Figura 8.4 Definição do POMDP Fanático para o estado E+ . . . . . . . . . . . 78
Figura 8.5 Definição do POMDP Fanático para o estado E0 . . . . . . . . . . . 79
Figura 8.6 Definição do POMDP Fanático para o estado E− . . . . . . . . . . . 80
Figura 8.7 Definição do POMDP Egoísta para o estado E+ . . . . . . . . . . . 81
Figura 8.8 Definição do POMDP Egoísta para o estado E0 . . . . . . . . . . . . 82
Figura 8.9 Definição do POMDP Egoísta para o estado E− . . . . . . . . . . . 83
Figura 8.10 Definição do POMDP Altruísta para o estado E+ . . . . . . . . . . . 84
Figura 8.11 Definição do POMDP Altruísta para o estado E0 . . . . . . . . . . . 85
Figura 8.12 Definição do POMDP Altruísta para o estado E− . . . . . . . . . . . 86
Figura 8.13 Exemplo do comportamento de um agente β com traço de personali-
dade tolerante em trocas 20% supervisionadas . . . . . . . . . . . . . 93
Figura 8.14 Exemplo do comportamento de um agente β com traço de personali-
dade tolerante em trocas 40% supervisionadas . . . . . . . . . . . . . 94
Figura 8.15 Exemplo do comportamento de um agente β com traço de personali-
dade tolerante em trocas 60% supervisionadas . . . . . . . . . . . . . 94
Figura 8.16 Exemplo do comportamento de um agente β com traço de personali-
dade tolerante em trocas 80% supervisionadas . . . . . . . . . . . . . 95
Figura 8.17 Exemplo do comportamento de um agente β com traço de personali-
dade altruísta em trocas 50% supervisionadas . . . . . . . . . . . . . 95
Figura 8.18 Exemplo do comportamento de um agente β com traço de personali-
dade altruísta em trocas 70% supervisionadas . . . . . . . . . . . . . 96
Figura 8.19 Exemplo do comportamento de um agente β com traço de personali-
dade egoista em trocas 50% supervisionadas . . . . . . . . . . . . . . 96
Figura 8.20 Exemplo do comportamento de um agente β com traço de personali-
dade egoista em trocas 60% supervisionadas . . . . . . . . . . . . . . 97
Figura 8.21 Exemplo do comportamento de um agente β com traço de personali-
dade egoista em trocas 80% supervisionadas . . . . . . . . . . . . . . 97
LISTA DE TABELAS
Tabela 2.1 Situações de raciocínio prático . . . . . . . . . . . . . . . . . . . . . 22
Tabela 6.1 Matriz representando o grafo de políticas do POMDP da Fig. 6.2 . . . 53
Tabela 7.1 Média das trocas geradas e recusadas em cada etapa de troca, em 20
simulações com 500 estágios de troca cada uma . . . . . . . . . . . . 61
Tabela 8.1 Regras para um agente Altruísta Fraco no estado E0 . . . . . . . . . 87
Tabela 8.2 Regras para um agente Altruísta Fraco no estado E+ . . . . . . . . . 87
Tabela 8.3 Regras para um agente Altruísta Fraco no estado E- . . . . . . . . . . 87
Tabela 8.4 Regras para um agente Altruísta Forte no estado E- . . . . . . . . . . 88
Tabela 8.5 Regras para um agente Altruísta Forte no estado E+ . . . . . . . . . . 88
Tabela 8.6 Regras para um agente Altruísta Forte no estado E0 . . . . . . . . . . 88
Tabela 8.7 Regras para um agente Egoísta Fraco no estado E0 . . . . . . . . . . 89
Tabela 8.8 Regras para um agente Egoísta Fraco no estado E- . . . . . . . . . . 89
Tabela 8.9 Regras para um agente Egoísta Fraco no estado E+ . . . . . . . . . . 89
Tabela 8.10 Regras para um agente Egoísta Forte no estado E+ . . . . . . . . . . 90
Tabela 8.11 Regras para um agente Egoísta Forte no estado E0 . . . . . . . . . . 90
Tabela 8.12 Regras para um agente Egoísta Forte no estado E- . . . . . . . . . . . 90
Tabela 8.13 Regras para um agente Fanático no estado E+ . . . . . . . . . . . . . 91
Tabela 8.14 Regras para um agente Fanático no estado E0 . . . . . . . . . . . . . 91
Tabela 8.15 Regras para um agente Fanático no estado E- . . . . . . . . . . . . . 91
Tabela 8.16 Regras para um agente Tolerante no estado E+ . . . . . . . . . . . . 91
Tabela 8.17 Regras para um agente Tolerante no estado E0 . . . . . . . . . . . . 92
Tabela 8.18 Regras para um agente Tolerante no estado E- . . . . . . . . . . . . . 92
LISTA DE ABREVIATURAS E SIGLAS
MDP Markov Decision Process
BDI Beliefs, Desires, Intentions
POMDP Partially Observable Markov Decision Process
SMA Sistemas Multi Agente
IA Inteligência Artificial
RESUMO
Agentes BDI (Beliefs, Desires, Intentions) são capazes de ações independentes e
autônomas para atingir objetivos para os quais foram projetados. De maneira geral, pode-
se dizer que são agentes que decidem por si o que fazer, dada uma situação. Observa-
se, entretanto, que esta é uma abordagem heurística, onde um agente BDI constrói um
plano para realizar uma determinada intenção, tenta executá-lo e, se falha, precisa recon-
siderar sua intenção, ou formular outro plano, e assim sucessivamente. Seu comporta-
mento é por tentativa e erro, geralmente impossibilitando um comportamento ótimo, se
comparado aos modelos de teoria da decisão. Outro fator importante que influencia seu
desempenho é o dinamismo do ambiente, que pode fazer com que o agente passe mais
tempo reconsiderando suas intenções do que fazendo ações. Este balanço entre o tempo
que o agente passa deliberando e o tempo que passa executando planos é crucial para um
bom agente BDI. Por outro lado, os Processos de Decisão de Markov Parcialmente Ob-
serváveis (POMDP) podem ser a abordagem ideal para problemas que se concentram na
coordenação de times e na existência de incerteza de ações e observações em domínios
do mundo real, embora a complexidade de se encontrar uma política ótima, em modelos
onde o espaço de estados seja muito grande, algumas vezes seja intratável. O objetivo
desta dissertação de mestrado é o desenvolvimento de um algoritmo para construção de
planos BDI baseados em políticas ótimas obtidas através de POMDPs. Esta abordagem
é aplicada a um modelo de auto-regulação de trocas sociais em sistemas multiagentes,
onde pares de agentes com personalidades distintas interagem entre si, trocando serviços
e avaliando estes serviços de acordo com seus traços de personalidades, com o objetivo
global de atingirem o equilíbrio material das trocas realizadas, sem, entretanto, inter-
romperem a continuidade das interações. O processo de decisão sobre as melhores tro-
cas que cada agente deve propor a seu parceiro para atingir o equilíbrio ou proporcionar
novas interações, foi modelado como um POMDP global para cada traço de personalida-
des. Considerou-se um conjunto básico de 4 traços de personalidades distintas (altruísmo,
egoísmo, tolerância, fanatismo). Para cada modelo de personalidade o respectivo POMDP
global foi decomposto em 3 sub-POMDPs, de acordo com o balanço material corrente das
trocas realizadas (resultado desfavorável, equilibrado ou favorável). O algoritmo proposto
policyT oBDIplans constrói uma biblioteca de planos BDI para cada modelo de person-
alidade, a serem selecionados em cada interação, de acordo com o balanço de valores dos
agentes em cada etapa de troca. Estes planos são modelados na linguagem AgentSpeak
para a plataforma de agentes Jason. Foram realizadas simulações considerando diferentes
níveis de supervisão (sem supervisão, supervisão parcial, supervisão total).
Palavras-chave: BDI, POMDP, Modelos Híbridos, Sistemas Multiagentes, Auto-
Regulação de Trocas Sociais.
ABSTRACT
TITLE: “BUILDING BDI PLANS FROM POMDP’S OPTIMAL POLICIES, WITH
AN APPLICATION TO THE SELF-REGULATION OF SOCIAL EXCHANGES IN
MULTI-AGENT SYSTEMS”
BDI agents are capable of independent and autonomous actions to reach the goals
for which they were designed. In general, they are agents that decide what to do by them-
selves, given a specific situation. However, this kind of approach is heuristic, where the
BDI agent builds a plan to reach a certain intention, try to execute it, and if the plan fails,
the agent needs to reconsider its intention, or to build another plan, and so on. Basically,
its behavior is based on trial and error, turning almost impossible to achieve an optimal
behavior, if compared to decision theory models. Other important issue that has influence
on its performance is the environment’s dynamics, which can make the agent spend more
time deliberating than executing actions. This balance between the time spent deliberat-
ing and the time spent executing plans is crucial for a good BDI agent performance. On
the other hand, the Partially Observable Markov Decision Process (POMDP) can be the
ideal approach for problems that addresses team coordination and uncertainty about ac-
tions and observations in real world domains, although the complexity to find an optimal
policy, in models in which the state space is too large, is sometimes highly intractable.
The main goal of this dissertation is the development of an algorithm for constructing BDI
plans from optimal policies obtained from POMDPs. This approach is applied to a model
of self-regulation of social exchanges in multiagent systems, where personality-based
agents interact in pairs, exchanging services and evaluating those services according to
their different personality traits, with the global goal of achieving material equilibrium of
the exchanges without, however, breaking the continuity of the interactions. The decision
process concerning the best exchanges that each agent should propose to its partner to
achieve the equilibrium or to promove new interactions was modeled as a global POMDP
for each personality trait. Considering a basic set of four different personality traits (al-
truism, egoism, tolerance, fanatism), for each personality model the respective global
POMDP was decomposed into 3 sub-POMDPs, according to the current balance of mate-
rial values of the exchanges (unfavorable, equilibrated or favorable result). The proposed
algorithm policyT oBDIplans builds a library with sets of rules for the BDI plans for
each personality model, to be selected in each interaction, according to the balance of
exchange values of the agents in each exchange stage. These plans are modeled using the
language AgentSpeak, for the Jason agent platform. Simulations were carried out consid-
ering different supervision levels (no supervision, partial supervision, total supervision).
Keywords: MDP, BDI, POMDP, MAS, IA, Hybrid Models, Self-Regulation of Social
Exchanges.
13
1 INTRODUÇÃO
Esta dissertação de Mestrado situa-se no contexto da área de Sistemas Multia-
gentes (SMA) (WOOLDRIDGE, 2002), explorando temas relacionados à arquitetura de
agentes BDI (Beliefs, Desires, Intentions) (WOOLDRIDGE, 2000; RAO; GEORGEFF,
1992) e aos Processos de Decisão de Markov Parcialmente Observáveis (POMDP) (RUS-
SELL; NORVIG, 1995; KAELBLING; LITTMAN; CASSANDRA, 1998), com o obje-
tivo geral de desenvolver um algoritmo para a extração de planos BDI a partir de políticas
ótimas de POMDPs. Esta abordagem é aplicada a um modelo de auto-regulação de trocas
sociais em SMA (DIMURO; COSTA; PALAZZO, 2005).
Nas seções a seguir, discute-se o problema que motivou esta pesquisa (Seção 1.1),
apresentam-se brevemente os trabalhos relacionados (Seção 1.2) e a aplicação pretendida
(Seção 1.3), introduz-se o objetivo desta dissertação (Seção 1.4) e descreve-se a organi-
zação do texto (Seção 1.5).
1.1 O Problema
Um agente racional deve ter algumas propriedades tais como: autonomia, pró-
atividade, reatividade e habilidade social, ou seja, ser capaz de interagir com outros
agentes.
Na área de agentes, existem arquiteturas, como, por exemplo, a BDI, que estru-
turam agentes racionais capazes de ações independentes e autônomas para atingir um
determinado objetivo, de modo a permitir que esses agentes decidam por si o que fazer,
dada uma situação.
Observa-se, entretanto, que esta é uma abordagem heurística, onde um agente
BDI constrói um plano para realizar uma determinada intenção, tenta executá-lo e, se
falha, precisa reconsiderar sua intenção, ou formular outro plano, e assim sucessivamente.
Basicamente seu comportamento é por tentativa e erro, geralmente impossibilitando um
comportamento ótimo, se comparado aos modelos de teoria da decisão.
Outro fator importante que influencia seu desempenho é o dinamismo do ambi-
ente, que pode fazer com que o agente passe mais tempo reconsiderando suas intenções
do que fazendo ações. Este balanço entre o tempo que o agente passa deliberando e o
tempo que passa executando planos é crucial para um bom agente BDI.
A abordagem BDI não possui ferramentas para análise quantitativa sistemática
(quer dizer, baseada em teoria matemática bem estabelecida) do desempenho dos agentes,
principalmente quando se trata de ambientes onde ocorre incerteza sobre os resultados das
ações e das percepções dos agentes.
14
Por outro lado, os modelos para a construção de agentes baseados em Processos
de Decisão de Markov (MDP) (PUTERMAN, 1994; RUSSELL; NORVIG, 1995; KAEL-
BLING; LITTMAN; CASSANDRA, 1998) sempre oferecem uma solução ótima para os
problemas colocados aos agentes. Salienta-se, entretanto, que a realização dos cálculos
implicados pelos seus algoritmos só apresentam desempenho adequado quando o espaço
de estados não é muito grande. Quando consideram-se modelos que representam ambi-
entes reais, que produzem usualmente um espaço de estados muito grande, o problema
torna-se intratável, devido à própria natureza dos algoritmos usados para resolver o MDP.
Modelos de agentes híbridos, como, por exemplo, um agente BDI com planos
baseados em MDPs, ou um MDP cuja política é construída a partir de planos BDI, têm
sido apontados como soluções para melhorar o desempenho de agentes BDIs ou a tra-
tabilidade de modelos MDPs, respectivamente (SIMARI; PARSONS, 2006). Existem
diversas equivalências que podem ser estabelecidas entre esses dois modelos, como, por
exemplo, uma biblioteca de planos para um agente BDI pode ser considerada uma política
MDP, ou planos BDI podem ser extraídos de políticas de MDPs. Considerando esta úl-
tima alternativa, um programador poderia especificar um MDP para servir de base para
implementação de um agente BDI, utilizando-se dos valores de utilidades de estados para
desenvolver planos para seu agente. Assim, um modelo MDP poderia ser direcionado a
um objetivo específico, dando condição ao agente BDI de seguir planos especificados por
uma política ótima para atingir tal objetivo, o que poderia lhe conferir um comportamento
com melhor desempenho, conforme (SIMARI; PARSONS, 2006).
Essa idéia de programação de agentes BDI com planos baseados em políticas
ótimas de MDPs foi explorada nesta dissertação de mestrado, considerando também
POMDPs.
1.2 Trabalhos Relacionados
Na literatura analisada, encontra-se diversos trabalhos que procuram explorar con-
juntamente os modelos BDI e MDP, para propostas de abordagens híbridas MDP-BDI.
Entre eles estão os trabalhos em (PARUCHURI et al., 2006; NAIR; TAMBE, 2005), que
desenvolveram abordagens onde planos BDI são explorados para melhorar a tratabilidade
dos POMDP e estes são utilizados para melhorar a desempenho de planos para times de
agentes BDI. Em (GUPTA et al., 2007) times de agentes que trabalham para completar
uma tarefa em comum utilizam uma abordagem híbrida BDI-POMDP para completar tal
tarefa.
Os trabalhos em (SIMARI; PARSONS, 2006; SCHUT; WOOLDRIDGE; PAR-
SONS, 2002) analisam as diversas propriedades dos dois modelos para uma tentativa de
formalização da relação entre planos BDI e políticas MDP e POMDP. Com base nestes
trabalhos, nesta dissertação de mestrado foi proposto o algoritmo policyToBDIplans
para extração de planos para agentes BDI a partir do grafo da política ótima de um modelo
POMDP que resolve o mesmo problema de decisão do agente BDI.
15
1.3 Auto-Regulação de Trocas Sociais em Sistemas Mul-
tiagentes
A aplicação que foi desenvolvida é o tratamento da auto-regulação de trocas soci-
ais em sistemas multiagentes.
A regulação de interações entre agentes com base na teoria de trocas sociais de
Piaget (PIAGET, 1995) foi proposta inicialmente em (DIMURO; COSTA; PALAZZO,
2005). Nesse trabalho, interações entre agentes são entendidas como trocas de serviços
entre cada par de agentes. Os agentes avaliam o investimento para a realização de um
serviço, assim como a satisfação associada ao recebimento de um serviço. Um sistema
está em equilíbrio material se os balanços entre os valores de investimento e satisfação
estão equilibrados para cada agente, após uma sucessão de trocas realizadas no tempo.
As trocas também geram valores de débito e crédito que garantem a continuidade das
interações.
O mecanismo de regulação de trocas sociais, baseado no conceito de supervisor
de equilíbrio centralizado com um Processo de Decisão de Markov Qualitativo Intervalar
associado, foi introduzido em (DIMURO; COSTA, 2006a,b). Este mecanismo foi esten-
dido para SMA baseados em personalidades em (DIMURO et al., 2007, 2006), entretanto
ainda de forma centralizada.
Para a auto-regulação de trocas sociais é necessário distribuir o processo de de-
cisão em cada par de agentes, ou seja, internalizar o mecanismo de regulação nos agentes,
tornando o processo de decisão parcialmente observável, pois os agentes não têm acesso
ao balanço interno de valores de trocas dos outros agentes.
Nesta dissertação, consideram-se pares de agentes com personalidades distintas
interagindo entre si, trocando serviços e avaliando estes serviços de acordo com seus
traços de personalidades, com o objetivo global de atingirem o equilíbrio material das tro-
cas realizadas, sem, entretanto, interromperem a continuidade das interações. O processo
de decisão sobre as melhores trocas que cada agente deve propor a seu parceiro para
atingir o equilíbrio ou proporcionar novas interações, foi modelado como um POMDP
global para cada traço de personalidade que o parceiro possa assumir. Considerando-se
um conjunto básico de 4 modelos de personalidades distintas, cada POMDP global foi
decomposto em 3 sub-POMDPs, de acordo com o balanço material corrente do agente
que realiza o POMDP.
O algoritmo proposto policyToBDIplans constrói uma biblioteca com con-
juntos de regras que compõem os planos BDI para cada modelo de personalidade, a serem
selecionados em cada interação, de acordo com o balanço de valores dos agente em cada
etapa de troca. Estes planos são modelados na linguagem AgentSpeak (RAO, 1996) para a
plataforma Jason
1
(BORDINI; HÜBNER; WOOLDRIGE, 2007; BORDINI; HÜBNER,
2005). Esta plataforma foi escolhida devido à familiaridade com a ferramenta e o contato
com seus desenvolvedores.
Para validar a proposta, foram realizadas simulações considerando diversos níveis
de supervisão (sem supervisão, supervisão parcial, supervisão total).
1
Jason é um interpretador para uma extensão de AgentSpeak incluindo comunicação entre agentes. Ele
é implementado em Java (portanto multi-plataforma) e é disponível como Open Source sob a licença GNU
LGPL.
16
1.4 Objetivos
O objetivo geral desta dissertação de mestrado é o desenvolvimento de um al-
goritmo para a extração de planos BDI a partir de políticas ótimas de POMDPs. Mais
especificamente, pretende-se:
• Com base na literatura, discutir a relação entre os modelos BDI e MDP de modo a
propor um algoritmo para automatizar a extração de planos BDI a partir de políticas
ótimas MDPs;
• Estender o algoritmo para modelos parcialmente observáveis (POMDPs);
• Especializar a saída do algoritmo para que as regras obtidas estejam num formato
compatível com a linguagem AgentSpeak;
• Desenvolver uma aplicação na auto-regulação de trocas sociais em SMA, imple-
mentada na plataforma Jason;
• Analisar o desempenho do modelo nesta aplicação através de simulações com difer-
entes níveis de supervisão.
1.5 Organização do Texto
Este trabalho está organizado como segue.
No Capítulo 2, apresenta-se o modelo de agentes BDI descrito
por (WOOLDRIDGE, 2000), salientando suas potencialidades e fragilidades.
No Capítulo 3, introduzem-se a abordagem MDP descrita em (RUSSELL;
NORVIG, 1995) e a abordagem POMDP segundo (KAELBLING; LITTMAN; CAS-
SANDRA, 1998), discutindo os principais algoritmos e suas principais vantagens e
desvantagens.
No Capítulo 4, é explorada a relação formal entre as abordagens BDI e MDP,
como discutido em (SIMARI; PARSONS, 2006), onde então procura-se consolidar a pos-
sibilidade da extração de planos BDI a partir de políticas ótimas de MDPs e POMSPs.
No Capítulo 5, apresenta-se uma versão computacional do algoritmo
policyToBDIplans para a extração de planos BDI a partir de políticas ótimas MDP
e POMDP, com exemplos simples de aplicações.
No Capítulo 6, com base no modelo centralizado (DIMURO et al., 2007;
DIMURO; COSTA; PALAZZO, 2005; DIMURO et al., 2006; DIMURO; COSTA,
2006b), é introduzido o modelo de auto-regulação das trocas sociais, incluindo a abor-
dagem POMDP proposta para descentralizar e internalizar o supervisor de equilíbrio de
trocas sociais, e a versão híbrida obtida com aplicação do algoritmo policyT oIplans.
Inclui-se um exemplo, com a explicação detalhada do funcionamento do algoritmo.
No Capítulo 7.3, apresentam-se as análises das simulações realizadas com a auto-
regulação de trocas sociais baseadas em personalidades. Para cada modelo de personali-
dade, são discutidos os resultados obtidos com a simulação do processo de decisão sobre
as trocas realizadas, incluindo diferentes níveis de supervisão.
No Capítulo 8 são apresentadas as conclusões do trabalho e discutem-se propostas
de trabalhos futuros.
17
2 O MODELO DE AGENTES BDI
Neste capítulo, apresenta-se uma introdução ao modelo de agentes BDI (“beliefs-
desires-intentions” ou crenças-desejos-intenções) (WOOLDRIDGE, 2000). Os agentes
BDI são capazes de ações independentes e autônomas para atingir um determinado ob-
jetivo, para o qual foi projetado. De maneira geral pode-se dizer que os agentes BDI
decidem por si o que fazer, dada uma situação. Observa-se que um agente racional deve
ter algumas propriedades tais como: autonomia, pró-atividade, reatividade e habilidade
social, ou seja, ser capaz de interagir com outros agentes.
2.1 Conceitos Iniciais
O modelo BDI tem suas raízes na tradição filosófica do entendimento do raciocínio
prático em seres humanos. Em termos simples, raciocino prático é o raciocínio voltado
para ações, ou seja, o processo de descobrir o que fazer:
“Raciocínio prático é um problema de pesar considerações conflitantes, para e
contra opções que competem umas com as outras, onde as considerações relevantes são
providas pelo que o agente deseja/dá valor/se importa e o que o agente acredita.” (BRAT-
MAN, 1990)
É importante distinguir raciocínio prático de raciocínio teórico, onde o raciocínio
teórico está focado nas crenças. Usando um exemplo antigo, tem-se o seguinte raciocínio:
"se eu acredito que todos os homens são mortais, e eu acredito que Sócrates é um homem,
então concluo que Sócrates é mortal". O processo de conclusão que Sócrates é mortal
é um processo de raciocínio teórico, pois afeta somente as crenças sobre o mundo. O
processo de decidir "pegar um ônibus"ao invés "pegar de um trem"é raciocínio prático,
pois está voltado diretamente para a ação.
O raciocínio prático humano consiste de pelo menos duas atividades distintas. A
primeira envolve decidir que “estado do mundo” se quer alcançar; o segundo processo
envolve “como” se quer alcançar este estado do mundo. O primeiro processo é conhecido
como deliberação e o segundo chama-se de raciocínio meio-fim.
O resultado final do raciocínio meio-fim é um plano ou uma receita para alcançar
o estado do mundo desejado. Após obter um plano, o agente então tentará executar seu
plano, a fim de alcançar tal estado do mundo. Se tudo der certo (se o plano for bom e o
ambiente cooperar suficientemente), então, após a execução do plano, o estado do mundo
escolhido será alcançado.
Dessa forma descrita, o raciocínio prático parece um processo direto, e num
mundo ideal seria. Mas existem diversas complicações. A primeira é que a deliberação
18
e o raciocínio meio-fim são processos computacionais. Em todos os agentes reais (e em
particular, agentes artificiais), tais processos computacionais somente acontecerão sobre
recursos limitados. Isto significa que o agente somente terá uma memória limitada e um
tempo fixo de processador para suas computações. Juntas, estas limitações de recursos
impõem um limite no tamanho das computações que podem ser feitas em um determinado
espaço de tempo. Nenhum agente real será capaz de realizar grandes computações num
tempo finito. Quase todos ambientes reais também irão operar com restrições de tempo.
Isto significa que deliberação e o raciocínio meio-fim devem ser feitos em um número
finito e fixo de ciclos de processador, com um espaço finito e fixo de memória. Desta
discussão pode-se ver que limites de recursos têm duas implicações importantes:
• Computação é um recurso valioso para agentes situados em ambientes de tempo
real. A habilidade de executar bem suas computações será determinada, pelo
menos em parte, pela habilidade de usar os recursos computacionais disponíveis
de maneira eficiente.
• Agentes não podem deliberar indefinidamente. Eles devem claramente parar de
deliberar em algum ponto, tendo escolhido tal estado do mundo, e se comprometer
a alcançar este estado.
2.1.1 Intenções
É possível distinguir diferentes tipos de intenções. Na linguagem comum, o termo
“intenção” é usado tanto para ações como para estados mentais. No que segue, intenções
serão usadas para caracterizar estados mentais. Em particular, usa-se intenções dirigidas
ao futuro – intenções que um agente tem sobre um estado futuro do mundo (ambiente).
O papel principal das intenções é que elas são pró-atitudes (BRATMAN, 1990).
Isto é, as intenções tendem a levar a ações. Se um agente possui uma intenção, espera-
se que ele faça alguma coisa para alcançar tal intenção. Isto normalmente envolve a
realização de um plano de ação que irá satisfazer tal intenção. Neste sentido, intenções
tem uma importância fundamental na produção de ações. Com o passar do tempo, uma
intenção sobre o futuro passa a ser uma intenção sobre o presente, se tornando muito
importante na produção de ações. Claro que ter uma intenção não significa ter ações.
Bratman (BRATMAN, 1990) lembra que: “intenções são muito mais influentes na
formação de ações do que outras pro-atitudes tais como desejos”.
A segunda propriedade principal das intenções é que elas persistem. Se um agente
adota uma intenção, ele deve insistir em alcançar tal intenção. Entretanto, se o agente
perceber que sua intenção nunca poderá ser alcançada, este deve abandoná-la. De maneira
similar, se a razão para se ter uma intenção deixar de existir, seria racional deixar de lado
esta intenção. Claro que se o agente falhar em alcançar sua intenção, espera-se que ele
pelo menos tente outra vez, ao invés de simplesmente deixar de lado a intenção.
A terceira propriedade da intenção é que uma vez que o agente tenha adotado uma
intenção, ela vai restringir seu raciocínio prático no futuro. Quando um agente adotar
uma intenção não se espera que ele faça ações que são incompatíveis com a sua intenção.
Esta é uma propriedade extremamente desejável do ponto de vista da implementação de
agentes racionais, pois provê um “filtro de admissibilidade”. Intenções podem ser vistas
como restrições no espaço de intenções (ações) que o agente deve considerar.
E, finalmente, intenções estão relacionadas com crenças sobre o futuro, pois se um
agente planeja sobre o futuro, ele pode assumir que uma intenção será alcançada.
19
Em resumo:
• Intenções dão direção ao raciocínio meio-fim;
• Intenções persistem;
• Intenções restringem deliberação futura; e
• Intenções influenciam crenças sobre que futuro o raciocínio prático será baseado.
Note que, a partir dessas discussões, nota-se que as intenções interagem com ou-
tros estados mentais do agente, bem como suas crenças.
2.2 Implementando Agentes Racionais
Baseado nas discussões da seção anterior pode se definir um modelo de agente
descrito pelo código (Alg. 1) extraído de (WOOLDRIDGE, 2000):
Algorithm 1 Laço de controle do Agente Versão 1
1: B := Bo; /*Bo são as crenças iniciais*/
2: while true do
3: get next percept p;
4: B := brf(B, p);
5: I := deliberate(B);
6: π := plan(B, I);
7: execute(π).
8: end while
Este algoritmo mostra algumas limitações da abordagem simples para o controle
do agente. Em particular os passos (4) e (7) assumem implicitamente que o ambiente
não mudou desde que foi observado em (3). Assumindo que o tempo que levou-se para
executar o plano é maior do que o tempo para revisar as crenças, deliberar ou planejar, a
principal preocupação é que o ambiente possa mudar enquanto o plano seja executado. O
problema é que o agente permanece comprometido com a intenção a partir de (5) até que
o plano seja executado em (7). Se o ambiente mudar depois do passo (3), então a escolha
de um plano estará baseada em suposições inválidas na hora em que o agente executá-lo.
2.2.1 O Processo de Deliberação
Nesta seção, será discutido o processo de deliberação em mais detalhes. A função
de deliberação pode ser decomposta em dois componentes funcionais:
• geração de opções - na qual o agente gera um conjunto de possíveis alternativas; e
• filtragem - em que o agente escolhe entre alternativas, e se compromete a alcançá-
las.
O laço de controle do agente explicitando a deliberação e o raciocínio meio-fim
estão descritas no código (Alg. 2) extraído de (WOOLDRIDGE, 2000). Note que desejos
são uma entrada para o processo de filtragem e intenções sua saída.
20
Algorithm 2 Laço de controle do Agente Versão 2
1: B := Bo; /*Bo são as crenças iniciais*/
2: I := Io; /Io são as intenções iniciais*/
3: while true do
4: get next percept p;
5: B := brf(B, p);
6: D := options(B, I);
7: I := filter(B, D, I);
8: π := plan(B, I);
9: execute(π).
10: end while
2.2.2 Estratégias de Comprometimento
Quando uma opção consegue passar pelo processo de filtragem, e então é esco-
lhida como intenção do agente, diz-se que o agente se comprometeu com tal opção. Com-
prometimento implica em persistência temporal – uma intenção uma vez que seja adotada
não deveria evaporar imediatamente. Um ponto crucial é quanto um agente deve se com-
prometer com suas intenções? Quando persistir e quando desistir?
O mecanismo que o agente usa para determinar como deixar de perseguir uma
intenção é conhecido como estratégia de comprometimento. As abordagens seguintes são
as mais utilizadas:
• Comprometimento Cego
Um agente comprometido cegamente irá manter sua intenção até acreditar que al-
cançou sua intenção. Comprometimento cego às vezes é chamado também de com-
prometimento fanático.
• Comprometimento Concentrado
Um agente concentrado irá manter uma intenção até acreditar que ela foi atingida
ou que não é mais possível atingí-la.
• Comprometimento Aberto
Um agente aberto irá manter sua intenção enquanto ele acreditar ser possível.
2.2.3 Reconsideração de Intenções
No algoritmo, o agente irá reconsiderar suas intenções uma vez todas as vezes que
passar pelo laço mais externo. Isto implica que uma das três condições aconteceu:
• foi executado um plano completamente para alcançar suas intenções; ou
• acredita que alcançou suas intenções atuais; ou
• acredita que suas intenções atuais não são mais possíveis.
Apesar de garantir que o agente não seja nem sub nem sobre comprometido com
suas intenções, é limitado de maneira a permitir que um agente reconsidere suas intenções.
O principal problema é que não é permitido a um agente explorar sua capacidade de
21
fazer descobertas importantes por acaso. Uma primeira tentativa de modificar o laço
de controle do agente envolveria reconsiderar suas intenções toda a vez que o agente
executa o laço interno. Entretanto é necessário equilibrar os graus de compromisso e
reconsideração para o agente. Para fazer este ajuste, modifica-se o agente para incorporar
um componente de “meta-level control”. A idéia é ter uma função booleana reconsider,
tal que reconsider(I, B) seja verdadeira caso seja o caso apropriado para que o agente
com crenças B e intenções I reconsidere suas intenções. O algoritmo (Alg. 3), onde
insere-se a função de reconsideração, foi extraído de (WOOLDRIDGE, 2000).
Algorithm 3 Laço de controle do Agente Versão 3
1: B := Bo; /*Bo são as crenças iniciais*/
2: I := Io; /Io são as intenções iniciais*/
3: while true do
4: get next percept p;
5: B := brf(B, p);
6: D := options(B, I);
7: I := filter(B, D, I);
8: π := plan(B, I);
9: while not (empty(π) or succeed(I, B) or impossible(I, B)) do
10: α := head(π);
11: execute(α);
12: π := tail(π);
13: get next percept p;
14: B := brf(B, p);
15: if reconsider(I, B) then
16: D := options(B, I);
17: I := filter(B, D, I);
18: end if
19: if not sound(pi, I, B) then
20: π := plan(B, I);
21: end if
22: end while
23: end while
Nesta versão do algoritmo, a decisão de reconsiderar recai sobre a função
reconsider(). As possíveis interações entre “meta-level control” e a deliberação são re-
sumidas na Tabela 2.1.
• na situação (1), o agente não escolheu deliberar, e como conseqüência não mudou
de intenção. Nesta situação reconsider() atua de maneira ótima;
• na situação (2), o agente escolheu não deliberar, mas se tivesse feito isso, teria
mudado suas intenções. Nesta situação reconsider() atua de maneira não ótima;
• na situação (3), o agente escolheu deliberar, mas não mudou suas intenções. Nesta
situação reconsider() atua de maneira não ótima;
• na situação (4), o agente escolheu deliberar e mudou suas intenções. Nesta situação
reconsider() atua de maneira ótima;
22
Tabela 2.1: Situações de raciocínio prático
Situação Delibera? Muda Intenções Teria mudado intenções? reconsider() é ótimo?
1 não - não sim
2 não - sim não
3 sim não - não
4 sim sim - sim
Note que existe uma importante suposição implícita nesta discussão: o custo de
se executar reconsider() é muito menor do que o custo do processo de deliberação em
si. Se não fosse desta maneira, a função reconsider poderia usar a deliberação como
reconsideração, apenas escolhendo deliberar no caso em que o processo de deliberação
mudasse de intenção.
Pode-se considerar dois tipos de estratégia de reconsideração: agentes corajosos,
que nunca param para reconsiderar suas intenções antes de seu plano atual estar comple-
tamente executado; e agentes cautelosos, que param para reconsiderar depois da execução
de cada ação. Estas características são definidas pelo grau de coragem, que especifica o
número máximo de passos de um plano que o agente executa antes de reconsiderar suas
intenções. O dinamismo do ambiente é representado pela taxa de mudança do mundo, γ.
A taxa de mudança do mundo é a razão da velocidade do laço de controle do agente à taxa
de mudança do mundo. Se γ = 1, então o mundo mudará apenas uma vez cada vez que o
agente executar o seu laço de controle. Se γ = 2 o mundo mudará duas vezes enquanto o
agente faz seu laço de controle e assim por diante. O desempenho de um agente é medido
pela razão do número de intenções que o agente alcançou pelo número de intenções que
o agente tinha. Portanto se a eficiência de um agente é 1 então o agente alcançou todas as
suas intenções, se for 0 então o agente falhou em alcançar suas intenções. Os principais
resultados medidos por (WOOLDRIDGE, 2000) são os seguintes:
• Se γ é baixo (isto é, o ambiente não muda rapidamente), então agentes corajosos tra-
balham bem comparados com agentes cautelosos. Isto acontece porque os agentes
cautelosos perdem tempo reconsiderando seus compromissos, enquanto agentes
corajosos estão ocupados trabalhando - e alcançando - suas intenções.
• Se γ é alto (isto é, o ambiente muda com freqüência), então agentes cautelosos
tendem a ser melhores que agentes corajosos. Isto acontece porque eles são capazes
de reconhecer quando intenções são impossíveis, e aproveitam novas oportunidades
quando elas aparecem.
Em resumo, diferentes ambientes requerem diferentes estratégias de reconsidera-
ção e comprometimento de agentes.
2.3 Considerações Finais
No estudo relativo ao modelo BDI, salientam-se os seguintes fatores:
• É baseado na teoria do comportamento racional em humanos;
23
• Encontram-se diversas implementações, inclusive em aplicações complexas;
• Tem uma teoria formalizada rigorosamente através da lógica BDI.
A pesquisa na área de arquiteturas para agentes BDI tem feito grandes progressos
nos últimos anos, entretanto ainda possui algumas desvantagens. Pelo fato de ser uma
abordagem heurística, ou seja, um agente BDI precisa fazer um plano, tentar executá-lo,
se falhar precisa reconsiderar suas intenções, etc. Basicamente seu comportamento é por
tentativa e erro, impossibilitando assim um comportamento ótimo (se comparado com
modelos de teoria da decisão). Outro fator importante é o dinamismo do ambiente, que
pode fazer com que o agente passe mais tempo reconsiderando do que fazendo ações.
Este balanceamento entre o tempo que um agente passa deliberando e executando planos
(ações) é crucial para um bom modelo BDI. No próximo capítulo apresentam-se os Pro-
cessos de Decisão de Markov, com suas principais características.
24
3 PROCESSOS DE DECISÃO DE MARKOV
Um problema de decisão seqüencial é essencialmente um problema de planeja-
mento. Dado um modelo completo e exato do ambiente, com seu funcionamento, e sua
estrutura de recompensa, é possível um encontrar uma forma ótima de comportamento
nesse ambiente. A maneira tradicional para abordar tais problemas é designar uma se-
qüencia de ações para um agente executar. Mas como o agente se encontra em ambi-
entes estocásticos (ou probabilísticos, onde não há certeza dos resultados das ações de um
agente em tal ambiente), raramente estas seqüências de ações terão um comportamento
ótimo. A abordagem aqui é fazer um mapeamento de todas as situações (estados) pos-
síveis em um ambiente para ações, de modo que um agente sempre saiba o que fazer, não
importando o que acontece no ambiente.
3.1 Arquitetura Básica de um MDP
Um modelo de Processo de Decisão de Markov (MDP - Markov Decision Pro-
cesses) pode ser exemplificado na Fig. 3.1, onde o agente toma como entrada o estado do
mundo e executa uma ação como saída, e esta ação afeta o estado do mundo. Apesar de
não se ter certeza sobre o resultado das ações do agente (não-determinismo), sempre se
tem certeza em qual estado do ambiente o agente se encontra.
Figura 3.1: Um MDP que modela uma interação síncrona entre o agente e o ambiente
Uma especificação das probabilidades de resultados para cada ação em cada estado
possível é chamada modelo de transição (ou somente “modelo”, sempre que isso não der
25
margem a alguma confusão). Usa-se T (s, a, s
) para denotar a probabilidade de alcançar
o estado s
se ação a for executada no estado s. Supõe-se que as transições obedecem
a propriedade de Markov no sentido de que a probabilidade de alcançar s
a partir de s
depende apenas do estado atual s, e não do histórico de estados anteriores. A função
de transição de estados T (s, a, s
) pode ser vista como uma grande tabela tridimensional
contendo probabilidades.
Para completar a definição do ambiente de tarefa, deve-se especificar a função de
utilidade para o agente. Como o problema de decisão é seqüencial, a função de utilidade
dependerá de uma seqüência de estados – um histórico de ambiente – em vez de depender
de um único estado. Mais adiante nesta seção, é investigado como tais funções de uti-
lidade podem ser especificadas em geral; por enquanto, estipula-se que, em cada estado
s, o agente recebe uma recompensa R(s, a) por ter realizado uma ação a, que pode ser
positiva ou negativa, mas deve ser limitada. A especificação de um problema de decisão
seqüencial para um ambiente completamente observável com um modelo de transição de
Markov e recompensas aditivas é chamada de processo de decisão de Markov, ou MDP.
Um MDP é definido pelos componentes a seguir:
Definição 3.1.1 Um Processo de Decisão de Markov (MDP) pode ser definido como uma
tupla (S, A, T, R, P, π), onde:
• S é o conjunto finito de estados e S
0
∈ S denota o Estado Inicial;
• A é o conjunto de ações;
• T : S × A → Π(S) é a função de transição de estados, que dada uma ação a
sobre um estado s, retorna uma distribuição de probabilidade sobre o conjunto de
estados S;
• R : S × A → R é a função de recompensa, ou seja a recompensa por realizar uma
ação a em um estado s;
• P é uma distribuição inicial de probabilidades sobre o conjunto de estados;
• π : S × A é uma política, ou seja um mapeamento estado/ação.
O conceito de P pode parecer estranho, pois o agente sempre sabe em qual estado
se encontra, portanto esta distribuição irá conter apenas o estado onde o agente se encontra
com probabilidade de 100% e os demais com 0%. Mas este conceito será estendido
quando o ambiente for parcialmente observável, onde o agente não sabe onde se encontra,
possuindo apenas uma distribuição de probabilidades sobre todos os estados, ou seja, o
agente terá uma certa probabilidade de estar em cada um dos estados do ambiente.
A próxima questão é definir qual seria a aparência de uma solução para o pro-
blema. Observe que qualquer seqüência fixa de ações não resolverá o problema, porque o
agente poderia acabar em um estado diferente da meta. Então uma solução tem de especi-
ficar o que o agente deve fazer para qualquer estado que o agente possa alcançar. Uma
solução desse tipo é chamada política. Normalmente denota-se política por π, e π(s) é a
ação recomendada pela política π para os estado s. Se o agente tiver uma política com-
pleta, então não importará o resultado de qualquer ação, o agente sempre saberá o que
fazer em seguida.
26
Toda a vez que uma dada política for executada a partir do estado inicial, a na-
tureza estocástica do ambiente levará a um histórico de ambiente diferente. A qualidade
de uma política é portanto medida pela utilidade esperada dos históricos de ambientes
possíveis gerados por esta política. Uma política ótima é uma política que produz a utili-
dade esperada mais alta. Usa-se π
∗
para denotar uma política ótima. Dado π
∗
, o agente
decide o que fazer, consultando sua percepção atual, que informa o estado e, portanto, é
uma descrição de um agente reativo, calculada a partir das informações usadas por um
agente baseado na utilidade.
A manutenção de um equilíbrio entre o risco e recompensa é uma característica
dos MDP’s que não surge em problemas de busca determinística; além disso, é uma carac-
terística de muitos problemas de decisão do mundo real. Por essa razão, os MDP’s foram
estudados em vários campos, inclusive na IA, pesquisa operacional, economia e teoria do
controle. Foram propostas dezenas de algoritmos para calcular políticas ótimas.
3.2 Caráter ótimo em Problemas de Decisão Seqüencial
Para a escolha da medida do desempenho, deve-se levar em consideração diversos
aspectos. O primeiro é se existe um horizonte finito ou um horizonte infinito para a
tomada de decisão. Um horizonte finito significa que existe um tempo fixo N depois do
qual nada mais é considerado, sendo a política ótima não estacionária. Por outro lado,
sem um limite de tempo fixo, não existe nenhuma razão para se comportar de maneira
diferente no mesmo estado em momentos distintos. Conseqüentemente, a ação ótima
depende apenas do estado atual, e a política ótima é estacionária.
O outro aspecto é o cálculo da utilidade de seqüências de estados. Pode-se vi-
sualizar isso como uma questão de teoria da utilidade multiatributo, onde cada estado s
i
é visualizado como um atributo da seqüência de estados [s
0
, s
1
, s
2
, . . .]. Para obter uma
expressão simples em termos dos atributos, deve-se fazer algum tipo de suposição de in-
dependência de preferências. A suposição mais natural é que as preferências do agente
entre seqüências de estados são estacionárias. O caráter estacionário para preferências
significa que, se duas seqüências de estados [s
1
, s
2
, s
3
, . . .] e [s
1
, s
2
, s
3
, . . .] começam com
o mesmo estado (isto é, s
1
= s
1
), então as duas seqüências devem ser ordenadas por
preferência do mesmo modo que as seqüências [s
2
, s
3
, . . .] e [s
2
, s
3
, . . .]. Sob o caráter
estacionário, existem apenas duas maneiras de atribuir utilidades a seqüências:
(a) Recompensas aditivas: a utilidade de uma seqüência de estados é:
U
k
([s
0
, s
1
, s
2
, . . .]) = R(s
0
) + R(s
1
) + R(s
2
) + . . . (3.1)
(b) Recompensas descontadas: a utilidade de uma seqüência de estados é:
U
k
([s
0
, s
1
, s
2
, . . .]) = R(s
0
) + γR(s
1
) + γ
2
R(s
2
) + . . . (3.2)
onde o fator de desconto γ é um número entre 0 e 1.
O fator de desconto descreve a preferência de um agente por recompensas atu-
ais sobre recompensas futuras. Quando γ é próximo de 0, as recompensas num futuro
distante são desconsideradas. Quando γ é 1, recompensas descontadas são exatamente
27
equivalentes a recompensas aditivas, e assim as recompensas aditivas constituem um caso
especial de recompensas descontadas.
3.3 Utilidades de Estados
A utilidade de estados é definida em termos da utilidade de seqüências de estados.
Em termos aproximados, a utilidade de um estado é a utilidade esperada das seqüências
de estados que poderiam seguí-lo. Evidentemente, as seqüências de estados dependem da
política que é executada; então, começa-se definindo a utilidade U
π
(s) com relação a uma
política específica π. Considerando-se s
t
o estado em que o agente se encontra depois de
executar π por t passos, tem-se:
U
π
(s) = E
∞
t=0
γ
t
R(s
t
)|π, s
0
= 0
. (3.3)
Dada essa definição, a utilidade verdadeira de um estado, que escreve-se como
U(s), é simplesmente U
π
∗
(s) – isto é, a soma esperada de recompensas descontadas se
o agente executa uma política ótima π
∗
. Note que U (s) e R(s) são quantidades bas-
tante diferentes; R(s) é a recompensa “a curto prazo” por estar em s, enquanto U (s) é a
recompensa total “a longo prazo” de s em diante.
A função de utilidade U(s) permite ao agente selecionar ações usando o princípio
de utilidade máxima esperada, isto é, escolher a ação que maximiza a utilidade esperada
do estado subseqüente:
π
∗
(s) = argmax
s
T (s, a, s
)U(s
). (3.4)
Agora, se a utilidade de um estado for a soma esperada de recompensas descon-
tadas desse ponto em diante, então existe um relacionamento direto entre a utilidade de
um estado e a utilidade de seus vizinhos: a utilidade de um estado é a recompensa ime-
diata correspondente a esse estado, somada à utilidade descontada esperada do próximo
estado, supondo-se que o agente escolha a ação ótima. Isto é, a utilidade de um estado é
dada por:
U(s) = R(s) + γmax
a
s
T (s, a, s
)U(s
). (3.5)
A equação (3.5 é chamada equação de Bellman, em homenagem a Richard Bell-
man (BELLMAN, 1957). As utilidades dos estados, definidas pela Equação (3.3) como
a utilidade esperada de seqüências de estados subseqüentes são soluções do conjunto de
equações de Bellman. De fato, elas são as únicas soluções, como mostram as duas próxi-
mas seções.
Na próxima seção, apresenta-se um algoritmo, chamado iteração de valor, para
calcular uma política ótima. A idéia básica é calcular a utilidade de cada estado e depois
empregar as utilidades para selecionar uma ação ótima em cada estado.
28
3.4 O Algoritmo de Iteração de Valor
A equação de Bellman (BELLMAN, 1957) é a base do algoritmo
ITERAÇÃO-DE-VALOR para resolução de MDPs. Se houver n estados possíveis, então
haverá n equações de Bellman, uma para cada estado. As n equações contém n incógnitas
– as utilidades para os estados. Então, deve-se resolver essas equações simultâneas para
encontrar as utilidades. Observa-se que as equações são não-lineares porque o operador
“max” não é um operador linear. Experimenta-se uma abordagem iterativa. Iniciando-se
com valores arbitrários para as utilidades, calcula-se o lado direito da equação e o insere-
se no lado esquerdo, atualizando a utilidade de cada estado a partir das utilidades de seus
vizinhos. Repete-se esse processo até chegar a um equilíbrio. Seja U
i
(s) o valor de uti-
lidade para o estado s na i-ésima iteração. A etapa de iteração, chamada atualização de
Bellman, é semelhante a:
U
i+1
(s) ← R(s) + γmax
a
s
T (s, a, s
)U
i
(s
) (3.6)
Ao aplicar a atualização de Bellman com freqüência infinita, tem-se a garantia de
alcançar um equilíbrio, e nesse caso os valores finais de utilidade deverão ser soluções
para as equações de Bellman. De fato, eles também são as únicas soluções, e a política
correspondente é ótima. O algoritmo ITERAÇÃO-DE-VALOR é mostrado no Alg. 4.
Algorithm 4 Algoritmo ITERAÇÃO-DE-VALOR
1: Função ITERAÇÃO-DE-VALOR (mdp, ) Retorna uma função de utilidade
2: Entradas: mdp (MDP com estados S, modelo de transição T , função de recompensa
R, desconto γ); (erro máximo permitido na utilidade de qualquer estado)
3: Variáveis: U, U
(vetores de utilidades, sendo U
inicializado com as recompensas de
cada estado); δ (mudança máxima na utilidade)
4: repeat
5: U ← U
; δ ← 0
6: for all estado s ∈ S do
7: U
[s] ← R[s] + γmax
a
s
T (s, a, s
)U[s
]
8: if |U
[s] − U[s]| > δ then
9: δ ← |U
[s] − U[s]|
10: end if
11: end for
12: until δ <
13: return U
3.5 Iteração de Política
Na seção anterior, observou-se que é possível conseguir uma política ótima até
mesmo quando a estimativa de função de utilidade é inexata. Se uma ação é claramente
melhor que todas as outras, então a magnitude exata das utilidades nos estados envolvidos
não precisa ser exata. Essa idéia sugere um caminho alternativo para encontrar políti-
cas ótimas. O algoritmo ITERAÇÃO-DE-POLÍTICA alterna as duas etapas a seguir,
começando com alguma política inicial π
0
:
29
• Avaliação de política: Dada uma política π
i
calcular U
i
= U
π
i
, a utilidade de cada
estado se π
i
tivesse de ser executada.
• Aperfeiçoamento de política: Calcular uma nova política de UME π
i+1
, utilizando
a observação antecipada de um passo baseada em U
i
.
O algoritmo termina quando a etapa de aperfeiçoamento da política não produz
nenhuma mudança nas utilidades. Nesse ponto, sabe-se que a função de utilidade U
i
é
um ponto fixo da atualização de Bellman, e, portanto ela é uma solução para as equações
de Bellman, e π
i
deve ser uma política ótima. Como existe apenas um número finito de
políticas para um espaço de estados finito e demonstra-se que cada iteração produz uma
política melhor, a iteração de políticas tem que terminar. Observa-se que, no algoritmo
ITERAÇÃO-DE-POLÍTICA (Alg. 5), existe uma etapa de aperfeiçoamento de política
realizada pela rotina AVALIAÇÃO-DE-POLÍTICA.
Algorithm 5 Algoritmo ITERAÇÃO-DE-POLÍTICA
1: Função ITERAÇÃO-DE-POLÍTICA (π, U, mdp) Retorna uma função de utilidade
2: Entradas: (mdp) (MDP com estados S, modelo de transição T , função de recom-
pensa R, desconto γ)
3: Variáveis: (U, U
) (vetores de utilidades); π (vetor de política indexado pelo estado)
4: repeat
5: U ← AVALIAÇÃO-DE-POLÍTICA(π, U, mdp)
6: inalterado? ← true
7: for all estado s ∈ S do
8: if max
a
s
T (s, a, s
)U[s
] >
s
T (s, π[s], s
)U[s
] then
9: π[s] ← argmax
a
s
T (s, a, s
)U[s
]
10: inalterado? ← false
11: end if
12: end for
13: until inalterado? = true
14: return π
Na i-ésima iteração, a política π
i
especifica a ação π
i
(s) no estado s. Isso significa
que tem-se uma versão simplificada da equação de Bellman relacionando a utilidade de s
(sob π
i
) às utilidades de seus vizinhos:
U
i
(s) = R(s) + γ
s
T (s, π(s), s
)U
i
(s
) (3.7)
O ponto importante é que essas equações são lineares, porque o operador “max”
foi removido. Para n estados, tem-se n equações lineares com n incógnitas, que podem ser
resolvidas no tempo O(n
3
) por métodos-padrão de álgebra linear. Para espaços de estados
pequenos, a avaliação de política com o uso de métodos de solução exata com freqüência
é a abordagem mais eficiente. Para os espaços de estados grandes, o tempo O(n
3
) talvez
seja proibitivo. Felizmente, não é necessário fazer a avaliação de política exata. Em
vez disso, pode-se executar algum número de etapas simplificadas de iteração de valor
(simplificadas, porque a política é fixa) para fornecer uma aproximação razoavelmente
boa das utilidades. A atualização Bellman simplificada para esse processo é:
30
U
i+1
(s) ← R(s) + γ
s
T (s, π(s), s
)U
i
(s
) (3.8)
e é repetida k vezes para produzir a próxima estimativa de utilidade. O algoritmo re-
sultante é chamado iteração de política modificada. Com freqüência, ele é muito mais
eficiente que a iteração de política padrão ou a iteração de valor.
Os algoritmos que foram descritos até agora exigem atualização da utilidade ou da
política dos estados de uma vez. Ocorre que isso não é estritamente necessário. De fato,
em cada iteração escolhe-se qualquer subconjunto de estados e aplicar-se uma ou outra
espécie de atualização (aperfeiçoamento da política ou iteração de valor simplificada) a
esse subconjunto. Esse algoritmo muito geral é chamado iteração de política assíncrona.
Dadas certas condições sobre a política inicial e sobre a função de utilidade, a iteração de
política assíncrona oferece a garantia de convergir para política ótima.
A liberdade de escolher quaisquer estados para trabalhar significa que pode-se
projetar algoritmos heurísticos muito mais eficientes – por exemplo, algoritmos que se
concentram em atualizar os valores de estados que provavelmente serão alcançados por
uma boa política.
3.6 Observação Parcial
Para processos de decisão de Markov pode-se computar a política ótima π
∗
e usá-
la para agir, simplesmente aplicando π
∗
(s) para o estado atual s. O que aconteceria se o
agente não pudesse mais determinar o estado atual com precisão? Uma solução parcial
seria o agente mapear as observações mais recentes em ações sem nenhuma lembrança do
passado (estados anteriores).
Mas resultados melhores podem ser obtidos, adicionando-se uma aleatoriedade ao
comportamento do agente: uma política pode ser mapeada a partir de observações para
distribuições de probabilidade sobre ações. A aleatoriedade efetivamente proporciona ao
agente escolher ações diferentes em estados diferentes que possuam a mesma aparência,
aumentando as suas probabilidades de escolher uma boa ação para aquele estado.
Para que o agente possa se comportar efetivamente em um mundo parcialmente
observável (BOUTILIER; DEAN; HANKS, 1999), é necessário que se use a memória
dos estados passados e de ações passadas, para ajudar na escolha de estados ambíguos
do mundo. A arquitetura de Processos de Decisão de Markov Parcialmente Observáveis
provê um método sistemático para fazer exatamente isto.
Definição 3.6.1 Um Processo de Decisão de Markov Parcialmente Observável
(POMDP) pode ser descrito como uma tupla < S, A, T, R, Ω, O, P >, onde:
• S, A, T, eR tem o mesmo significado que em um Processo de Decisão de Markov;
• Ω é um conjunto finito de observações que o agente tem do mundo;
• O : S × A → Π(Ω) é a função de observação que dá, para cada ação e estado re-
sultante, uma distribuição de probabilidade sobre possíveis observações (escreve-
se O(s
, a, o) para a probabilidade de se fazer a observação o dado que o agente
tomou a ação a e acabou no estado s
);
• P é uma distribuição inicial de probabilidades sobre o conjunto de estados.
31
Figura 3.2: Um POMDP com o SE (estimador de estados) e uma Política (π)
Um POMDP é um MDP no qual o agente não consegue saber o seu estado atual,
conhecendo apenas uma distribuição de probabilidades sobre o conjunto dos estados, de-
nominada de estado de crença. O agente então precisa fazer observações sobre o ambi-
ente, com base na ação realizada e no estado resultante, para atualizar o estado de crença.
O objetivo do agente continua sendo maximizar a recompensa descontada esperada no
futuro.
Um POMDP é então entendido como um sistema que, em qualquer instante de
tempo, pode estar em um estado, entre vários, e a mudança de um estado para outro
depende do resultado das ações realizadas no estado atual do sistema (o qual não pode
ser determinado com total certeza). POMDPs satisfazem a propriedade de Markov, na
qual a informação sobre o estado corrente torna irrelevante informações sobre o passado
na hora de fazer predições sobre o futuro. Em um POMDP, representa-se o fato de que
o conhecimento do agente não é completo por uma distribuição de probabilidades sobre
todos os estados possíveis.
A Fig. 3.2 mostra os componentes de um POMDP. Ao contrário de um MDP
discreto, o modelo POMDP possui um estimador de estado (state estimator - SE), que
controla as transições no estado de crença, baseado na última ação, na observação atual
e no estado de crença anterior. Este componente não é necessário em um MDP discreto,
pois a política do agente é baseada em estados externos que sempre refletem o estado atual
do ambiente. O estimador de estado computa um novo estado de crença, a partir da teoria
de probabilidade básica. A saída do estimador de estado é usada na função de transição
do agente, que atribui uma probabilidade de 1 para o estado de crença b
, resultado de se
executar a ação a no estado de crença b e fazer a observação o se SE(b, a, 0) = b
, e uma
probabilidade de 0, caso contrário.
Definidos os conjuntos contidos em um POMDP, este é resolvido computando
uma política ótima: uma atribuição de uma ação para cada possível estado, tal que a
soma esperada das recompensas ganhas através das possíveis trajetórias pelo espaço de
32
estados no POMDP é maximizada. Um MDP tem horizonte infinito ou finito, sendo que
o primeiro resulta em uma política com um mapeamento ação/estado e, o segundo, uma
mapeamento ação/estado/tempo. Políticas ótimas podem ser computadas aplicando-se
métodos de programação dinâmica ao POMDP, quebrando o problema em problemas de
decisão de um passo, usando as equações de Bellman (BELLMAN, 1957). Os algoritmos
mais conhecidos de programação dinâmica para solução de POMDPs são os de iteração
de valor e iteração de política.
3.6.1 O Algoritmo Witness
O algoritmo chamado Witness (KAELBLING; LITTMAN; CASSANDRA,
1998), define regiões para o vetor de valores, e procura por um ponto onde este vetor
não é dominante. Diferentemente de outras técnicas, este algoritmo seleciona apenas uma
ação de cada vez e tenta encontrar a melhor função de valor (utilidade) para cada uma
das ações separadamente. De posse destes valores, o algoritmo combina os resultados e
constrói a função de valor V
.
Outra forma de simplificar o problema, além de considerar uma ação de cada vez,
é também considerar uma observação de cada vez. Um vetor em um ponto do estado de
crença é construído a partir da seleção de um vetor transformado do vetor V para cada
observação. O algoritmo Witness (do inglês, testemunha) começa com um ponto aleatório
do estado de crença, e gera o seu vetor (de valor). Após o adiciona ao conjunto e considera
que este vetor é V
, e então tenta provar que este vetor é realmente o V
.
Na construção de um vetor, faz-se uma escolha para cada observação; esta escolha
é a seleção de um dos vetores V representando uma estratégia futura. O algoritmo então
procura pelas escolhas individuais feitas, observação por observação, para encontrar uma
escolha diferente que possua um valor maior. Após, define uma região em que a sua
escolha com certeza é a melhor. Se conseguir achar um ponto no estado de crença onde
uma estratégia diferente seria melhor, então este estado de crença serve de testemunha
(ou “witness”) para o fato de que a escolha de vetores não é o V
procurado.
As regiões definidas por este algoritmo são descritas pela intersecção de duas
regiões mais simples. A região sobre a qual o vetor atual domina sobre todos os ou-
tros vetores que foram gerados até agora. Esta região é mostrada no topo da Fig. 3.3.
Note que neste ponto nesta figura, o algoritmo gerou apenas três vetores.
Esta região reduz a procura por um ponto a uma região sobre a aproximação que
foi gerada até agora, isto é, todos os vetores gerados até este ponto. Isto permite que o
algoritmo não procure por pontos onde o melhor vetor já foi encontrado.
A segunda região define define a região sobre a qual a estratégia futura corrente
será a melhor para a observação z1. Se o algoritmo sair desta região, então pode se substi-
tuir uma seqüencia de ações para esta observação e obter melhores resultados. Quando é
considerada a estratégia para uma observação, o algoritmo ignora as outras observações.
Entretanto, se o algoritmo achar um estado de crença onde pode se substituir outra es-
tratégia futura, não se pode apenas substituir esta estratégia. Por levar em conta este
isolamento entre observações, pode ser que além de mudar esta escolha de observação,
pode se mudar a escolha para outra observação. Portanto achar um estado de crença onde
a escolha da observação pode ser mudada, é achar uma testemunha de que o valor pode ser
maior. Neste ponto é gerado o verdadeiro melhor vetor de valor (levando em conta todas
as escolhas de observações). Este processo é repetido para cada observação para obter-se
um conjunto de vetores para um ação em particular e então isto é feito para todas as ações.
33
Figura 3.3: Regiões definidas pelo algoritmo Witness
Então os vetores são combinados e os vetores onde o valor é menor são eliminados, para
alcançar o verdadeiro vetor V
.
3.7 Considerações Finais
Processos de Decisão de Markov podem ser a abordagem ideal para problemas
que se concentram na coordenação de times e na existência de incerteza de ações e obser-
vações em domínios do mundo real (BOUTILIER; DEAN; HANKS, 1999). Entretanto a
complexidade de se encontrar uma política ótima, em modelos onde o espaço de estados
é muito grande, é quase intratável. No capítulo seguinte apresenta-se a relação entre as
duas abordagens, BDI e MDP.
34
4 UMA RELAÇÃO ENTRE OS MODELOS
MDP E BDI
Processos de Decisão de Markov podem ser a abordagem ideal para a implemen-
tação de agentes inteligentes, devido o fato de poderem dar valores às utilidades de cada
estado, e probabilidades de transição entre estes estados. Com estes valores pode-se uti-
lizar algoritmos como a iteração de valor para obter uma política ótima, mapeando cada
estado para a melhor ação para aquele estado. Mas a própria natureza destes algoritmos,
em particular a enumeração do resultado de cada ação em cada estado, torna o processo de
se encontrar políticas praticamente intratável em muitos casos práticos (SIMARI; PAR-
SONS, 2006). Devido a esta alta complexidade, obtém-se apenas soluções aproximadas.
Até mesmo as melhores abordagens disponíveis não são capazes de lidar com problemas
muito complexos ou muito grandes.
Em contraste, a arquitetura BDI (Beliefs, Desires, Intentions) tem agentes cons-
truídos com um conjunto de crenças sobre o estado do mundo, e um conjunto de desejos
que, de maneira geral, identificam quais estados do mundo são objetivos para o agente.
Através da deliberação o agente formula uma ou mais intenções. Então o agente constrói
um plano para alcançar suas intenções.
Uma abordagem BDI para um problema, geralmente, tem um desempenho infe-
rior a uma abordagem MDP, desde que o problema seja tratável pelo mesmo. Entretanto
um modelo BDI pode solucionar problemas que estão além do escopo dos modelos MDP,
e pode ainda ser mais eficiente do que modelos MDP aproximados, para problemas rela-
tivamente pequenos (SIMARI; PARSONS, 2006).
Para a realização deste trabalho, faz-se necessário analisar a relação formal
entre as duas abordagens, em particular as seguintes questões, que foram discutidas
em (SIMARI; PARSONS, 2006), embora os seguintes trabalhos também tenham sido
analisados (PARUCHURI et al., 2006; NAIR; TAMBE, 2005; GUPTA et al., 2007;
SCHUT; WOOLDRIDGE; PARSONS, 2002).
• Dada uma política que é uma solução para um MDP, como extrair uma descrição
BDI que pode ser usada para aproximar uma solução para o MDP?
Nesta seção, utiliza-se a notação adotada em (SIMARI; PARSONS, 2006), que,
embora não seja padrão, simplifica as descrições BDI e MDP, de modo a estabelecer cor-
relações entre seus elementos. Primeiramente descreve-se como ações, estados e funções
de transição para um BDI e MDP podem ser relacionados, considerando os resultados
35
apresentados em (SIMARI; PARSONS, 2006). Ambas descrições consistem em um es-
paço de estados S, um conjunto de ações A, e uma funções de transição T que depende
do estado corrente e da ação a ser realizada.
Para um agente em um dado ambiente considera-se que S, A e T são os mesmos
para ambas descrições (BDI e MDP). Além disso considera-se que B e P têm a mesma
função – identificam qual o estado o agente está atualmente. Com estas equivalências
definidas, tem-se de um lado recompensas e políticas e por outro tem-se desejos, delibe-
ração, raciocínio meio-fim, e intenções. Na verdade como recompensas são meios de se
determinar políticas e desejos um passo para se determinar intenções, estes componentes
podem ser ignorados, pois recompensas indicam qual estado o agente deve atingir, da
mesma forma que desejos indicam qual intenção deve ser escolhida. Finalmente a relação
que se deve considerar com detalhes seriam políticas e intenções.
4.1 Relação entre Intenções, Planos e Políticas
Neste trabalho, intenção é o estado que o agente se comprometeu a alcançar, e
utiliza-se o termo i-plan para denotar uma seqüência de ações construídas para alcançar
um determinado estado, ou seja para alcançar uma determinada intenção.
Para resolver as questões enumeradas, i-plans são relacionados com políticas. O
objetivo é obter i-plans através da solução de um MDP. Os resultados que são apresentados
a seguir foram extraídos de (SIMARI; PARSONS, 2006).
Um i-plan será denotado como ψ , indexado por ψ
i,s
, onde i é a intenção do
agente e s seu estado atual. I-plans são seqüências de ações e ψ
i
denota a iésima ação em
ψ, enquanto s
ψ
i
denota o i-ésimo estado que o agente planeja visitar enquanto executa ψ .
Portanto, para um i-plan ψ de tamanho p, o agente começa no estado s
ψ
0
e planeja visitar
os estados s
ψ
1
, s
ψ
2
, . . . , s
ψ
p
. Se o agente precisar fazer uma reconsideração (pelos motivos
discutidos no Capítulo 2), e uma nova intenção for adotada o agente também irá precisar
de um novo i-plan.
A utilidade esperada de um i-plan pode ser obtida da mesma forma que uma
política em um MDP, estabelecendo-se um valor para cada ação em cada estado em que é
executada. A diferença é que em um i-plan considera-se apenas uma seqüência no espaço
de estados, e na avaliação de uma política considera-se as ações em todos os estados. A
princípio, o agente BDI terá a mesma abordagem para atravessar o espaço de estados.
Selecionará uma intenção, identificará um i-plan para alcançar sua intenção e executará
seu i-plan até perceber que seu i-plan não irá alcançar sua intenção ou que sua intenção
não pode ser alcançada (ou não é a melhor intenção possível). Neste momento, o agente
irá gerar um novo i-plan ou escolher uma nova intenção e gerar um i-plan para alcançá-lo
e o processo irá se repetir.
Pode-se fazer uma comparação deste processo com o de um agente MDP no
mesmo espaço de estados, no qual o agente sempre sabe, através de sua política, qual
a melhor ação a tomar. A desvantagem deste último é que calcular uma política ótima é
mais custoso do que criar um plano simples. O preço pago pelo agente BDI é que este
tem que computar o que fazer “online” enquanto o cálculo de política do agente MDP
pode ser feito “offline”, e ainda seu plano pode ser sub-ótimo pois pode haver desvio
em suas ações. Por exemplo, um agente que não tem certeza que que sua ação vai dar
certo jogando uma moeda, pois existe apenas 50% de chance de ele acertar cara ou coroa.
Mesmo que seu plano indique que a melhor ação seja apostar em coroa, existe uma boa
36
chance dele errar o seu palpite.
Apesar de suas diferenças, em (SIMARI; PARSONS, 2006) foram estabelecidas
diversas equivalências entre as duas abordagens, considerando como eles trabalham no
mesmo espaço de estados. O resultado que interessa a este trabalho em particular é que,
dada uma política, que tem uma ação para cada estado, é possível derivar um ou mais i-
plans, determinando uma trajetória através do espaço de estados. Portanto, pode-se dizer
que uma política incorpora um conjunto de i-plans.
4.2 De Políticas para I-Plans
Assume-se que uma política π é a solução para um MDP completamente especi-
ficado, e que π é ótima (esta condição é importante para os resultados que se quer obter).
Entretanto, de qualquer política é possível extrair valores de utilidade para os estados que
irão induzir π, e estes poderão ser usados para estabelecer i-plans.
Nesta seção, considera-se que π foi obtido através da convergência de um algo-
ritmo (como por exemplo o Q-Learning (SUTTON; BARTO, 1998; WATKINS, 1989))
que dá um valor a cada par estado/ação. Agentes BDI também podem mapear estados
e ações em valores. Estes valores são computados atribuindo-se um valor a cada i-plan.
Seja ψ um i-plan de tamanho p, e ψ
i
a i-ésima ação envolvida em ψ. Uma maneira de
atribuir valor a ψ é através de:
V (ψ) =
p
i=1
R(s
ψ
i−1
, ψ
i
)
i
(4.1)
onde V (ψ) é o valor do i-plan ψ, s
ψ
0
é o estado inicial de ψ, s
ψ
i
é o estado para qual
o agente espera chegar depois de executar a ação ψ
i
, e R(s
ψ
i−1
, ψ
i
) é a recompensa por
executar a ação ψ
i
no estado s
ψ
i−1
. Portanto o valor atribuído para um i-plan é a soma das
recompensas que serão alcançadas se todas as ações tiverem o efeito desejado; a divisão
da recompensa por i denota o desconto pelo tempo, pois recompensas obtidas mais cedo
são mais valiosas do que aquelas obtidas no futuro. Se todas as ações tiverem o efeito
desejado, então a intenção será alcançada. Diz-se assim que o valor de uma intenção i é o
valor o i-plan.
É importante notar que esta é apenas uma entre várias maneiras de se atribuir va-
lores a um i-plan. De maneira geral, apenas é necessário que um i-plan ψ tenha, para cada
ação adicionada ao plano, valores de custo não negativos, e que estes valores dependam
das recompensas dos estados que o agente planeja visitar. Por exemplo, em um ambiente
simples a função de recompensa poderia ser definida por:
R(s
ψ
i−1
, ψ
i
) =
1 se ψ leva diretamente ao objetivo
0 caso contrário
(4.2)
e R(s, a) = 0 para cada outro par estado/ação.
A seguir, define-se formalmente os conceitos de i-plan e tamanho de um i-plan,
bem como o que significa um i-plan obedecer a uma dada política, conforme (SIMARI;
PARSONS, 2006).
Definição 4.2.1 Uma seqüência de ações ψ
0
, ψ
1
, . . . , ψ
p
, é chamada um i-plan se as
ações ψ
i
, com 0 ≤ i ≤ p, forem selecionadas para serem executadas uma de cada vez,
37
na ordem da seqüência, para alcançar uma dada intenção.
Definição 4.2.2 Dado um i-plan ψ = ψ
0
, ψ
1
, . . . , ψ
p
, diz-se que p é o tamanho de ψ.
Definição 4.2.3 Um i-plan ψ de tamanho p obedece a uma política π se, e somente se,
∀i, 1 ≤ i ≤ p: ψ
i
= π(s
ψ
i−1
), onde s
ψ
i
é o estado para qual o agente está planejando
chegar após executar a ação ψ
i
, e s
ψ
0
é seu estado inicial.
A definição 4.2.3 simplesmente especifica que um i-plan obedece a uma política
se, e somente se, as ações prescritas pelo i-plan são as mesmas prescritas pela política
através dos estados intermediários do i-plan. Lembre que assumiu-se que os i-plans são
lineares, e que nenhuma reconsideração é feita devido a resultados inesperados de suas
ações.
A definição de obediência é seguida pela definição de conformidade:
Definição 4.2.4 Uma política π está de acordo com um i-plan ψ de tamanho p se, e
somente se, ∀i, 1 ≤ i ≤ p : π(s
ψ
i−1
) = ψ
i
, onde s
ψ
i
é o estado que resulta da execução da
ação ψ
i
no estado s
ψ
i−1
, e s
ψ
0
é o estado no qual a primeira ação é executada.
Ou seja, uma política está de acordo com um plano, se para cada ação descrita no
plano a política recomenda a mesma ação.
Desde que um i-plan seja indexado pela intenção que irá alcançar quando for
executado, pode-se estender a noção de obediência e conformidade para intenções. Uma
política π está de acordo com uma intenção i se para todos os i-plans ψ
i,s
, π está em
conformidade com ψ
i,s
, e uma intenção i obedece a uma política π se todos os i-plans ψ
i,s
obedecem à π.
No que segue, discutem-se os argumentos apresentados em (SIMARI; PARSONS,
2006) para mostrar que:
“Dado um agente BDI e um agente MDP com uma política ótima π, se o agente
BDI está no estado s
i
, então o i-plan ψ com o maior valor de utilidade será aquele que ψ
obedece a política π, começando em s
i
.”
Em geral, a afirmação acima somente se sustenta se estados com a mesma recom-
pensa são considerados os mesmos nas duas abordagens, BDI e MDP. De outra forma,
mesmo que as utilidades sejam equivalentes, as ações podem não ser exatamente as mes-
mas, pois a ordem em que os estados com a mesma recompensa são considerados pode
afetar a seleção de ações. A prova desta afirmação pode ser feita para cenários progressi-
vamente mais complexos.
Os resultados iniciais encontrados para relacionar políticas com intenções e i-plans
são estabelecidos para casos determinísticos e totalmente acessíveis:
Proposição 4.2.5 Seja < S, A, T, R, P, Π > uma descrição de um agente MDP e
π ∈ Π uma política que é ótima sob um critério de máxima utilidade esperada. Seja
< S, A, T, B, D, I, Del, M > uma descrição de um agente BDI. Considere que Del
sempre seleciona a intenção (estado que quer alcançar) com a maior recompensa e M
seleciona o i-plan com o maior valor. Se o ambiente for totalmente observável e deter-
minístico, isto é ∀s ∈ S, ∀a ∈ A : |T (s, a)| = 1, então ∀i ∈ I, ∀s ∈ S, é válido que
ψ
i,s
obedece a π, onde T (s, a) é o conjunto de estados alcançáveis a partir de s pela
realização da ação a.
38
Prova. (SIMARI; PARSONS, 2006) O resultado deriva diretamente do fato que assumiu-
se que o componente de deliberação Del é ótimo e que as ações são completamente
determinísticas no ambiente. Como π é ótima sob um critério de máxima utilidade espe-
rada, ela sempre irá selecionar ações que levam o agente para o melhor estado-objetivo
da melhor forma possível. Como Del escolhe a intenção com o maior valor, e suas ações
são determinísticas, irá selecionar a mesma intenção/objetivo que π leva seu agente a
escolher. De maneira similar, como M escolhe o i-plan com o maior valor, este irá esco-
lher um i-plan que percorre a mesma trajetória através do espaço de estados (a partir de
qualquer estado que o agente se encontre) que π. Portanto, se for assumido que estados
com recompensas iguais são considerados na mesma ordem por π e M, está claro que
i-plans gerados por M irão obedecer a π.
Se as ações não forem determinísticas, o valor de i-plans não estará claramente
definido. Ao invés de uma simples soma de recompensas através do caminho do plano,
a falha nas ações deve ser considerada. Portanto, deve-se assumir que os componentes
de deliberação e o raciocínio meio-fim são ótimos sob um critério de máxima utilidade
esperada ao contrário de serem capazes de escolher a intenção e o i-plan (respectivamente)
com os maiores valores.
Proposição 4.2.6 Seja < S, A, T, R, P, Π > uma descrição de um agente MDP e que
π ∈ Π seja uma política que é ótima sob um critério de máxima utilidade esperada.
Seja < S, A, T, B, D, I, Del, M > uma descrição de um agente BDI, onde M e Del
sejam ótimos sob um critério de máxima utilidade esperada. Se o ambiente for totalmente
observável e não-determinístico, isto é, |T (s, a)| ≥ 1, então ∀i ∈ I, ∀s ∈ S, é válido que
ψ
i,s
obedece a π.
Prova. (SIMARI; PARSONS, 2006) Pelo fato de que Del está escolhendo intenções que
são ótimas sob um critério de utilidade máxima esperada e M está construindo i-plans
que são ótimos sob um critério de utilidade máxima esperada, o mesmo argumento da
Prop. 4.2.5 diz que todo o i-plan irá obedecer a π inclusive se suas ações não forem
determinísticas.
Estes resultados mostram porque a abordagem BDI tem dificuldades para gerar
um comportamento ótimo. Nos modelos BDI clássicos a deliberação seleciona uma in-
tenção e então a análise meio-fim constrói um plano para alcançar tal intenção. Para poder
escolher um conjunto de ações ótimo (ver Prop. 4.2.6), o componente de deliberação deve
poder escolher a intenção que é ótima sob um critério de utilidade máxima esperada antes
da análise de meio-fim escolha um i-plan.
A seguir, analisa-se o caso em que o ambiente não é totalmente observável, isto é,
o agente não sabe em qual estado s ele está, e deve confiar em suas estimativas do estado
atual do ambiente (LOVEJOY, 1991). Modelos POMDP tratam este tipo de situação
estendendo o conceito de estado, como explicado no Capítulo 3 (Seção 3.6). Ao invés de
lidar com um estado s ∈ S,onde S é o espaço de estados descrevendo todos os estados
no ambiente, um estado se torna uma probabilidade de distribuição sobre todos S. Se
fosse possível enumerar todas as distribuições de probabilidades s
i
, então pode-se pensar
em políticas e i-plans que se preocupam com um novo espaço de estados S
=
i
s
i
.
Definindo S
como a contraparte parcialmente observável de S e considerando este o
novo espaço de estados onde os agentes BDI e MDP irão operar, de tal forma que ambos
B e P identificam algum estado s
∈ S
como o estado atual do agente, pode-se então
estender a Prop. 4.2.6 como:
39
Proposição 4.2.7 Seja < S, A, T, R, P, Π > um agente MDP e π ∈ Π uma política que é
ótima sob um critério de máxima utilidade esperada. Seja < S, A, T, B, D, I, Del, M >
um agente BDI, onde M e Del são ótimos sob um critério de máxima utilidade esperada.
Se o ambiente for parcialmente observável, com S
sendo a contraparte parcialmente
observável de S, e também não determinístico, isto é, |T (s, a)| ≥ 1, então ∀i ∈ I, ∀s
∈
S
, é válido que ψ
i,s
obedece a π.
Prova. (SIMARI; PARSONS, 2006) Este resultado generaliza o resultado anterior, porque
agora considera-se um ambiente parcialmente observável. Entretanto, devido ao fato de
se expandir S para S
em ambos modelos MDP e BDI, o resultado deriva diretamente da
Prop. 4.2.6.
Esta é uma formalização da relação entre políticas e i-plans, similar àquela discu-
tida na Seção 4.1. Esta correspondência é válida sob restritivas suposições, em particular,
os requisitos (política, M e Del) sejam ótimos, mas garante que os i-plans gerados re-
fletem uma política ótima. Ao relaxar a necessidade de um i-plan corresponder a uma
política ótima, pode-se criar i-plans com menos restrições. No próximo capítulo, serão
apresentados os algoritmos para a extração de planos BDI a partir de políticas MDP.
40
5 EXTRAINDO PLANOS BDI DE POLÍTI-
CAS ÓTIMAS
Apesar dos resultados formais apresentado no Capítulo 4 indicarem que é possível
extrair i-plans que obedecem a uma política, eles não dizem como fazê-lo. Neste capítulo,
introduz-se o algoritmo policyToBDIplans, em duas versões, para construção de
planos BDI a partir de políticas ótimas MDPs e POMDPs.
5.1 De Políticas Ótimas de MDPs para Planos BDIs
Pode-se obter um i-plan a partir de qualquer política através de uma simples
procura através do espaço de estados, seguindo uma política π até um máximo local ser
atingido. Este estado é então selecionado como intenção. Para selecionar uma única in-
tenção, assume-se que as ações do agente sempre têm o resultado mais provável; de outra
forma, teria-se uma árvore como resultado e não um caminho simples.
Seguindo esta estratégia, introduz-se o algoritmo policyToBDIplans em
Alg. 6.
Algorithm 6 Algoritmo para obter um i-plan a partir de uma política ótima
1: policyToBDIplan(Policy Pi, Util U, MDP m)
2: Iplan i;
3: s = getCurrentState(m);
4: g = getGoalState(s, U);
5: while not s = g do
6: i = s(m.a);
7: n = getNextState(s, Pi);
8: s = n;
9: end while
10: return i;
O algoritmo policyToBDIplans obtém um i-plan a partir de uma política
ótima MDP, da forma descrita a seguir. Em (3) o algoritmo recebe a posição atual do
agente. Em (4), baseado na posição inicial do agente e as utilidades dos estados (U),
o algoritmo retorna em g o estado com a maior utilidade. Então o laço se comporta da
seguinte maneira: enquanto o estado atual não for o estado de objetivo (5), o plano recebe
a ação (a) para aquele estado, que foi estabelecida na política (6), e atualiza o estado atual
41
com o próximo estado recomendado pela política (7, 8). Isto é feito levando em conta que
a ação executada teve o seu resultado mais provável, já que as ações do agente não são
determinísticas.
Seguindo a política desta forma obtém-se quantos i-plans forem necessários: de-
pois que alcançar o estado intenção, simplesmente continua-se seguindo a política a partir
do estado alcançado após a última intenção.
5.1.1 Exemplo: Navegação no Ambiente 3 × 4
Nesta seção, introduz-se um exemplo simples para que o funcionamento do algo-
ritmo policyToBDIplans possa ser visualizado de forma clara. O exemplo escolhido,
extraído de (RUSSELL; NORVIG, 1995), é completamente observável.
Suponha que o agente esteja no ambiente da Fig. 5.1, composto por uma matriz
3 × 4. Começando pelo estado (1, 1), ele deve escolher uma ação por instante de tempo.
A interação com o ambiente termina quando o agente atinge um dos estados finais, (2, 4)
ou (3, 4) com recompensas −1 e +1, respectivamente. Nos outros estados a recompensa é
de −0, 04. Em cada estado, as ações disponíveis são Acima, Abaixo, Esquerda e Direita.
O ambiente é completamente observável, portanto o agente sempre sabe em que estado
se encontra. O estado (2, 2) é um estado não navegável.
Apesar do ambiente ser completamente observável, suas ações não são determinís-
ticas. O modelo usado para movimento do agente está ilustrado na Fig. 5.2. Cada ação
alcança seu objetivo com probabilidade de 80%, mas no restante do tempo, a ação move
o agente em ângulos retos até a direção pretendida. Além disso, se o agente bater em uma
parede, ele permanecerá no mesmo estado. Por exemplo, a partir do estado inicial (1, 1),
a ação Acima move o agente para (2, 1) com probabilidade de 80%, mas, com probabili-
dade de 10% ele se move para esquerda e vai para (1, 2), e com probabilidade de 10% ele
se move para direita, se choca com a parede e permanece em (1, 1)
Figura 5.1: Um ambiente simples 3 × 4 que apresenta o agente com um problema de
decisão seqüencial
Para este exemplo, o algoritmo ITERAÇÃO_DE_VALOR (Alg. 4) forneceu
as utilidades para os estados como mostrado na Fig. 5.3. O algoritmo
ITERAÇÃO_DE_POLÍTICA (Alg. 5) apresentou os resultados mostrados na Fig. 5.4.
Assim, o algoritmo policyToBDIplans identifica o estado de maior utilidade como
intenção (3, 4) construindo então o seguinte i-plan: [Acima, Acima, Direita,
Direita, Direita].
42
Figura 5.2: Ilustração do modelo de transição do ambiente
Figura 5.3: Utilidades dos estados
Figura 5.4: Política ótima obtida com o algoritmo
43
5.2 De Politicas Ótimas de POMDPs para Planos BDIs
Para modelos parcialmente observáveis (POMDPs) foi desenvolvida uma versão
modificada a partir algoritmo policyToBDIplans (Alg. 6).
O algoritmo recebe a saída do algoritmo Witness (veja Seção 3.6), e, a partir do
grafo de política gerado por este algoritmo, constrói regras para serem implementadas na
plataforma Jason. A saída do algoritmo Witness é uma tabela, que é usada para construir
o grafo de política. Como este grafo possui nodos que nunca serão visitados, é necessário
ainda realizar a simplificação do grafo, para então passar para a etapa de geração de regras
na linguagem AgentSpeak (RAO, 1996).
Algorithm 7 Algoritmo para extrair planos BDI de grafos de políticas POMDP
policyToBDIplan(Policygraph pg){
Policygraphline pl
BDIplan plan
BDIrule ruleR1, ruleR2, ... ,ruleRn
set pl to firstLine(pg)
repeat
set ruleR1 to BDIrule(head={Node(pl)}, context={True}, body={act(Action(pl)), aGoal(Node(pl’))})
set ruleR1 to BDIrule(head={Node(pl’)}, context={ObsR1}, body={aGoal(R1(pl))})
set ruleR2 to BDIrule(head={Node(pl’)}, context={ObsR2}, body={aGoal(R2(pl))})
...
set ruleRn to BDIrule(head={Node(pl’)}, context={ObsRn}, body={aGoal(Rn(pl))})
addBDIrules {ruleR1, ruleR2, ... , ruleRn} to plan
advance ln
until ln beyond lastLine(pg)
return Plan
}
O algoritmo se comporta de maneira similar à versão totalmente observável, mas
com algumas diferenças:
• A entrada do algoritmo é o grafo de políticas (pi) gerado pelo algoritmo Witness;
• A saída é um conjunto de regras a serem convertidas para o formato AgentSpeak;
• Para cada linha do arquivo que contém o grafo de política é extraída uma regra
(rule) e uma ação (action), e para cada observação é extraída uma próxima regra
(nextrule).
5.2.1 Exemplo: O Problema do Tigre
O Problema do Tigre (KAELBLING; LITTMAN; CASSANDRA, 1998) consiste
de um agente em frente a duas portas. Atrás de uma existe um tigre, que irá atacá-lo e
atrás da outra existe um baú com uma grande recompensa. Em vez de abrir uma porta,
ele pode apenas escutar para obter alguma informação sobre a localização do tigre. Mas
escutar tem um preço e não é muito confiável. A descrição do POMDP é dada pela tupla
< S, A, T, R, Ω, O >, onde:
• S = {sl, sr} é o conjunto de estados, onde sl representa o tigre à esquerda, e sr à
direita;
• A = {listen, open − left, open − right} é o conjunto das ações escutar, abrir a
porta esquerda e abrir a porta direita, respectivamente;
44
• T : S × A →
(S) é a função de transição de estados, onde a ação listen não
causa transição no sistema e open − left e open − right resetam o problema;
• R : S × A → {−1, +10, −100} é a função de recompensa, onde −1 é o custo de
listen, +10 é a recompensa por abrir a porta sem tigre, e −100 quando o tigre está
atrás da porta que foi aberta;
• Ω = {tl, tr} é o conjunto de observações, onde tl indica que o agente escutou o
tigre na esquerda, e tr que o escutou na direita;
• O : S × A →
(Ω) é a função de observação que dá a probabilidade de se fazer
uma observação o dado que o agente executou a ação a e chegou no estado s.
O estado de crença do agente, no início de cada rodada, é uma distribuição de
probabilidades uniforme entre os estados, isto é, probabilidade de 0.5 para sl (tigre à
esquerda) e 0.5 para sr (tigre à direita). Se o estado é sl, existe uma probabilidade de 0.85
de ocorrer a observação tl (escutar o tigre à esquerda), e de 0.15 de ocorrer a observação
tr (escutar o tigre à direita). Se o estado é sr, existe uma probabilidade de 0.85 de ocorrer
a observação tr, e de 0.15 de ocorrer a observação tl.
A política ótima para este problema pode ser descrita pelo grafo de política simpli-
ficado apresentado na Fig. 5.5, obtido com a utilização do algoritmo “Witness” (KAEL-
BLING; LITTMAN; CASSANDRA, 1998).
O algoritmo policyToBDIplans obtém planos BDI descritos como as regras
exemplificadas na Fig. 5.6. A plataforma para implementação usada foi a Jason (BOR-
DINI; HÜBNER, 2005), que usa a linguagem AgentSpeak (RAO, 1996) para descrever o
comportamento do agente.
Considerando que o agente inicia escutando, pois não tem nenhuma certeza sobre
o estado em que o tigre se encontra, então ele navega para a regra 1, em que ele tem
uma certeza maior de que o tigre está na porta esquerda. Com ainda existe uma incerteza
acerca da posição do tigre, ele vai escutar mais uma vez, indo para a regra 2. Na regra 2
ele em vez de escutar, ele já abre a porta pois já tem a certeza da posição do tigre. Logo
após retorna para a regra 1, pois sabe que o problema foi reiniciado e que não tem mais
certeza da posição do tigre novamente. No capítulo seguinte será apresentado o contexto
das Trocas Sociais, bem como o modelo POMDP para trocas entre dois agentes.
45
Figura 5.5: Grafo de Políticas
+!State(1): True ->
act(listen),
!State(1’).
+!State(1’): obs==TL ->
!State(2).
+!State(1’): obs==TR ->
!State(3).
Figura 5.6: Exemplo de Regras
46
6 AUTO-REGULAÇÃO DE TROCAS SOCI-
AIS
Trocas Sociais é o nome dado às interações entre pequenos grupos de agentes, que
realizam serviços uns para os outros. Para avaliar este tipo de serviço, os agentes atribuem
valores à estes serviços, como por exemplo um grau de satisfação por um serviço prestado
por outro agente, ou o investimento realizado na prestação de serviços. Esta abordagem
foi introduzida pela Teoria das Trocas Sociais de Piaget (PIAGET, 1995).
Para o controle social, duas abordagens podem ser consideradas. Primeiramente,
regras sociais podem ser impostas por autoridades, que têm a capacidade de obrigar os
agentes a seguir tais regras. Ou estas regras podem ser internas aos agentes, e eles seguem
estas regras porque foram incorporadas ao seu comportamento.
6.1 Valores de Trocas Sociais
Valores de Troca (PIAGET, 1995) dão origem a uma economia qualitativa para
avaliar trocas sociais, onde os envolvidos nas trocas obtém créditos por serviços presta-
dos a outros, e débitos por serviços recebidos de outros. Os saldos destas trocas de valores
permitem aos indivíduos encontrarem um estado de equilíbrio das trocas sociais realiza-
das, e tomarem uma decisão sobre o que fazer. Valores de troca qualitativos englobam
valores econômicos de algum tipo (geralmente quantitativos) e são vistos como base para
regras sociais.
Regras sociais podem ser de vários tipos (formal ou informal, moral, econômica
etc.) e podem ser vistas como uma maneira de manter o saldo geral dos valores de troca,
a fim de alcançar um determinado estado (equilibrado, favorável para um ou mais indi-
víduos, etc.), e portanto mantendo os indivíduos motivados (ou obrigados) a continuar
participando destas trocas.
Valores de trocas materiais e virtuais são classificados por Piaget (PIAGET, 1995)
em duas categorias mais amplas: trocas imediatas e trocas futuras. Nas trocas imediatas,
os agentes trocam serviços de maneira imediata, serviço por serviço, para que seja pos-
sível avaliar tais serviços de forma imediata, enquanto os serviços estão sendo prestados,
permitindo assim, que cada agente possa regular a quantidade e a qualidade do serviço
que ele presta a outro agente (da mesma maneira que pessoas trocam bens materiais, ne-
gociando que bem irá entrar na troca). Dois tipos de valores estão associados a este tipo de
troca imediata, que correspondem ao investimento necessário para se realizar um serviço
para outro agente, e a satisfação que tal serviço proporcionou ao agente que recebeu o
47
serviço. Tais valores são chamados de valores materiais de troca.
No caso das trocas futuras existe uma separação de tempo entre os estágios de
uma troca de serviços, dando origem aos valores de troca virtuais, englobando créditos
e débitos: quando um agente executa um serviço para outro, ele recebe um crédito por
tal serviço, e o outro recebe um débito por ter recebido tal serviço deve pagar este débito
em algum futuro. O termo virtual se refere exatamente ao fato de que tal valor ainda não
existe e será pago em algum momento no futuro. Por exemplo se alguém empresta um
livro para outra pessoa, o correto seria, em princípio, esta pessoa devolver o livro para a
pessoa, em um futuro não muito distante.
6.2 Estrutura das Trocas Sociais
Uma troca social entre dois agentes, α e β, é executada em dois tipos de estágios,
ilustrados no esquema da Fig 6.1, extraída de (DIMURO; COSTA; PALAZZO, 2005).
Nos estágios do tipo I
αβ
o agente α realiza um serviço para o agente β. Os valores de
troca envolvidos neste estágio são os seguintes:
• r
I
αβ
é o valor do investimento feito por α pela realização do serviço para β. Um
valor de investimento é sempre negativo;
• s
I
βα
é o valor da satisfação de β pelo recebimento do serviço feito por α;
• t
I
βα
é o valor do débito de β, o débito é adquirido em relação a α pela satisfação do
serviço realizado por α;
• v
I
αβ
e o valor do crédito que α adquire de β pelo serviço realizado para β.
De maneira análoga são as trocas do tipo II
αβ
, onde o agente α cobra um crédito
por um serviço realizado anteriormente para β, que presta então um serviço para α em
retorno.
Um processo de trocas sociais consiste da realização de diversas dessas etapas ao
longo do tempo. Um sistema está em equilíbrio material se os balanços entre os valores
de investimento e satisfação estão equilibrados para cada agente, após uma sucessão de
trocas realizadas no tempo. Os valores de débito e crédito é que garantem a continuidade
das interações.
6.3 Agentes com Personalidades
Neste trabalho, segue-se a linha de (DIMURO et al., 2006, 2007), onde os agentes
possuem traços de personalidade (CASTELFRANCHI et al., 1997, 1998), que determi-
nam qual o comportamento que o agente adota ao realizar trocas com os outros agentes.
Como este tipo agente guarda um histórico de suas interações com o outro, pode se de-
senvolver estratégias específicas para lidar com cada tipo de personalidade.
Cada personalidade tem uma característica específica, que determina que tipo de
trocas o agente faz: por exemplo um agente egoísta, procura fazer trocas que o favoreçam,
ou seja, tenta se manter em um estado positivo na maior parte do tempo, recusando com
freqüência a prestação de serviços para outros agentes.
48
Figura 6.1: Trocas do Tipo I e II
Esses traços de personalidade também podem influenciar na valorização dos
débitos e créditos gerados nas trocas, um agente pode super-estimar seus créditos en-
quanto que outro subestima sub-estima seus débitos, por exemplo. Assim, um agente
fortemente egoísta, além de recusar com freqüência a realização de trocas que envolvam
a prestação de serviços para outros agentes, também têm tendência a supervalorizar seus
créditos e subvalorizar seus débitos.
Estas personalidades podem englobar um certo grau de obediência a um meca-
nismo de controle social que porventura exista no sistema. Enquanto um agente atende
ao mecanismo (de acordo com uma certa probabilidade) outro pode desconsiderá-las to-
talmente.
Observa-se que a modelagem de traços de personalidade de trocas introduzidas
em (DIMURO et al., 2006, 2007) seguem um padrão diferente do adotado neste trabalho.
Naquela proposta, os traços de personalidades foram definidos em termos das diferentes
valorizações realizadas pelos agentes para os serviços prestados e recebidos por eles nas
trocas realizadas. Ou seja, para um mesmo serviço, cada traço de personalidade pode pro-
ceder a uma avaliação diferente. Assim, por exemplo, um agente egoísta tende a atribuir
altos valores para suas satisfações e baixos valores para seus investimentos, buscando
assim aumentar seus resultados materiais. Também, naquele trabalho, as diferenças na
valorização de créditos e débitos foram consideradas para compor novos traços de perso-
nalidades, de forma desvinculada da modelagem dos traços de personalidades principais.
49
6.4 Equilíbrio Social
Um supervisor de equilíbrio social (DIMURO; COSTA; PALAZZO, 2005) pode
ser visto como um componente da sociedade de agentes (e possivelmente um agente), que,
com base no balanço dos valores de troca, é capaz determinar o melhor conjunto de trocas
que podem ser realizadas entre cada par de agentes, a fim de trazer o sistema social de
volta ao equilíbrio, ou manter a continuidade das interações. Este supervisor recomenda
tais ações aos agentes do sistema, mas não obriga os agentes a seguirem suas recomen-
dações: sendo autônomos, eles podem decidir se irão seguir, ou não, tal recomendação.
O mecanismo de regulação de trocas sociais, baseado no conceito de supervisor
de equilíbrio centralizado com um Processo de Decisão de Markov Qualitativo Intervalar
associado, foi introduzido em (DIMURO; COSTA, 2006a,b). Este mecanismo foi esten-
dido para SMA baseados em personalidades em (DIMURO et al., 2007, 2006), entretanto
ainda de forma centralizada, onde o supervisor avalia as trocas entre pares de agentes e
recomenda para eles que tipo de trocas cada um deve fazer para atingir o equilíbrio do
sistema, ou dar continuidade às interações. Nesta versão centralizada, o supervisor tem
acesso total aos balanços de trocas dos agentes, podendo determinar, em cada instante, o
estado do sistema.
Para a auto-regulação de trocas sociais é necessário distribuir o processo de de-
cisão em cada agente, ou seja, internalizar o mecanismo de regulação nos agentes, tor-
nando o processo de decisão parcialmente observável, pois os agentes não têm acesso ao
balanço interno de valores de trocas dos outros agentes.
Neste trabalho, introduz-se uma proposta para descentralizar este supervisor,
tornando-o interno aos agentes. Para realizar tal tarefa, o processo de auto-regulação
de trocas foi modelado como um POMDP. Neste caso, o mecanismo de regulação interno
em cada agente conhece apenas o estado deste agente, desconhecendo o estado do outro
agente (o parceiro nas trocas). Ele pode, entretanto, observar os relatos do agente parceiro
sobre seus créditos e débitos, que poderão dar um indicativo (com uma certa probabili-
dade) do estado atual do agente. Baseado no estado interno do agente supervisor (aquele
que realiza o processo de decisão) e de suas observações sobre o agente parceiro nas tro-
cas, ele faz recomendações de trocas para tentar levar o sistema para o equilíbrio, ou para
que seja mantida a continuidade das trocas.
6.5 Processo de Decisão sobre Trocas Baseadas em Per-
sonalidades
Considerando um conjunto de 6 traços personalidades (egoísmo forte e fraco, al-
truísmo forte e fraco, tolerância e fanatismo), foi definido um POMDP para cada modelo
de personalidade. Cada POMDP foi decomposto em 3 sub-POMDPs, um para cada es-
tado interno (balanço de trocas desfavorável, equilibrado ou favorável) do agente onde se
localiza o supervisor.
Seja E
s
= {E
−
s
, E
+
s
, E
0
s
} a representação dos estados internos dos agentes, onde
(E
−
s
) é um balanço desfavorável, (E
0
s
) é um balanço equilibrado e (E
+
s
) é um balanço
favorável de trocas, com relação ao ponto de equilíbrio s, determinado pela aplicação.
Definição 6.5.1 Seja α um agente com o supervisor internalizado e E
α
∈ {E
−
s
, E
+
s
, E
0
s
}
o estado corrente de α. Seja β um agente baseado em personalidade que interage com α.
50
O Processo de Decisão Parcialmente Observável para o supervisor de equilíbrio inter-
nalizado no agente α, que realiza trocas com um agente baseado em personalidades β, é
definido como uma tupla POMDP
α
= (S
β
, A
α
, T
β
, R
α
, Ω
β
, O
β
), onde:
(i) E
β
= {E
−
s
, E
+
s
, E
0
s
} é o conjunto de estados possíveis do agente β;
(ii) A
α
= {do-service, ask-service} é o conjunto de ações disponíveis para o
agente α, with do-service significa que α deve oferecer um serviço a β (estágio
de trocas tipo I
αβ
), e ask-service significa que α deve requisitar um serviço a
β (estágio de trocas tipo II
αβ
);
(iii) T
β
= E
β
× A
α
→ Π(E
β
) é a função de transição baseada no traço de personali-
dade do agente β, ou seja, dada o estado atual do agente β e a ação realizada pelo
agente α, a função indica qual a probabilidade do agente β transitar de um estado
para outro, baseado em sua personalidade (isto é, qual a probabilidade do agente
β aceitar ou não a troca proposta pelo agente α);
(iv) Ω
β
= {N, D, C}, onde N significa neutro, D débito e C crédito, é o conjunto de
observações que podem ser realizadas por α sobre os estados de β, a partir das
informações emitidas por β;
(iv) O
β
= E
β
× A
α
→ π(Ω) é a função de observação baseada no traço de personali-
dade do agente β, ou seja, dada o estado atual do agente β e a ação realizada pelo
agente α, a função indica qual a probabilidade do agente β emitir a informação de
que possui ou não débitos ou créditos, baseado em sua personalidade.
• R
α
= E
β
× A
α
→ R é a função de recompensa para as ações escolhidas pelo
agente α em cada estado de β, com maiores recompensas para ações que levem ao
estado de equilíbrio do sistema (quando ambos os agentes tem balanços equilibra-
dos);
O conjunto de ações A consiste apenas das ações do − service e ask − service,
onde o agente α faz um serviço ou pede um serviço para o agente β, respectivamente.
Após a realização da troca proporcionada por uma destas ações (troca esta que
pode não ocorrer caso o agente β não aceite a proposta realizada por α), o agente α
realiza uma observação: o agente β emite uma informação sobre seus débitos e créditos. O
conjunto de observações é composto de N (neutro ou em equilíbrio), D (débito), quando o
agente β ficou com débito para com α, e C (crédito), quando o agente β ficou com crédito
para com α. Estas observações tem uma probabilidade que dependem da personalidade
de β, ou seja, o agente β nem sempre está no estado informado.
As recompensas são modeladas de forma a trazer o equilíbrio para o sistema, ou
dar continuidade às interações. Por exemplo, se o agente α (que tem o processo de super-
visão internalizado) está em estado desfavorável e estima que o agente parceiro β está no
estado favorável, então ele terá maior recompensa se solicitar que o parceiro realize um
serviço para ele, para que o sistema possa retornar ao equilíbrio.
Com os grafos de políticas obtidos para cada POMDP assim definido, o algoritmo
policyToBDIplans (Alg. 7) extrai planos em forma de regras para serem implemen-
tadas na plataforma Jason.
51
6.5.1 Exemplo
Nesta seção e também nas simulações apresentadas no Capítulo 7.3, considera-se
apenas o ponto de equilíbrio igual a zero, com o objetivo de simplificar a análise dos
resultados. Zero significa um estado equilibrado em torno do zero. Neste trabalho o
estado equilibrado é o balanço entre [2, −2].
Nesta seção, descreve-se um exemplo detalhado do modelo do supervisor interna-
lizado em um agente α no estado de equilíbrio (E
0
), com nível de supervisão total (isto é,
o agente α sempre segue os planos que obedecem a política do POMDP), lidando com um
agente β com traço de personalidade egoísta, que tem a tendência a ficar em um estado
favorável (E
+
).
O modelo do POMDP correspondente é apresentado na Fig. 6.2, no formato
exigido para a entrada do algoritmo Witness, que fornece o grafo de política cuja descri-
ção está na Fig. 6.1. Esta entrada consiste dos seguintes elementos: um valor de desconto
(discount), os estados E0, E1 e E2 (representando, respectivamente, o estado de equi-
líbrio E0, o estado favorável E0+ e o estado desfavorável E0−), as ações possíveis, que
são fazer serviço (do-service) e pedir serviço (ask-service), e as observações
(N, D e C), conforme a Def. 6.5.1.
Logo após, na Fig. 6.2, tem-se as funções de transição e de observação, que des-
crevem o modelo de personalidade egoísta como explicado a seguir. Na linha 7, tem-se
a função de transição do agente egoísta para ação do-service. A primeira linha da
matriz (8) representa o estado de equilíbrio E0, e cada coluna representa os estados para
o qual o agente egoísta pode transitar ao receber a ação do-service (E0, E1 ou E2).
Portanto, têm-se apenas 10% de chance de que o agente egoísta receba um serviço e
continue no estado de equilíbrio. A maior probabilidade é de que ele vá para o estado
positivo (E+) com 90% de chance. Não há probabilidade do agente egoísta ir para o
estado negativo (E2) se ele receber um serviço. De maneira análoga, pode-se dizer que
quando o agente egoísta está em um estado favorável e recebe um serviço ele irá ficar
neste estado (probabilidade de 100%), como pode se notar na linha 9. Por fim, na linha
10, tem-se que, mesmo no estado negativo ao receber um serviço, o agente egoísta tem
maior probabilidade de ir para um estado positivo (70%).
No caso da função de observação, quando o agente α realiza uma ação para β,
ele recebe automaticamente uma observação sobre o estado interno de β. No exemplo da
Fig. 6.2, o agente egoísta emite informações realistas sobre o seu estado interno, configu-
rando aqui um egoísmo fraco
1
. Ou seja, se o agente egoísta está no estado de equilíbrio
(linha 18), ele tem 90% de chace de emitir uma observação N que representa que ele não
possui nem créditos nem débitos, isto, está em um estado neutro em relação às trocas
feitas com o outro agente. O mesmo padrão realista se configura para os outros estados,
isto é, se ele está no estado favorável (linha 19), ele tem 90% de chace de emitir uma
observação D que significa que ele possui nem débitos, ou, se ele está no estado desfa-
vorável (linha 20), ele tem 90% de chace de emitir uma observação C que significa que
ele possui nem créditos.
Por fim, tem-se a função de recompensa, que premia a tentativa do agente α de
levar o sistema ao equilíbrio ou, se o mesmo já está em equilíbrio, incentiva a continuidade
das trocas.
1
Um egoísmo forte caracterizaria observações de supervalorização de créditos e subvalorização de
débitos.
52
1. discount: 0.95
2. values: reward
3. states: E0 E1 E2
4. actions: do-service ask-service
5. observations: N D C
6. -------------------------
7. T:do-service
8. 0.1 0.9 0.0
9. 0.0 1.0 0.0
10. 0.2 0.7 0.1
11. -------------------------
12. T:ask-service
13. 0.9 0.0 0.1
14. 0.2 0.7 0.1
15. 0.0 0.0 1.0
16. -------------------------
17. O:do-service
18. 0.9 0.05 0.05
19. 0.05 0.9 0.05
20. 0.05 0.05 0.9
21. -------------------------
22. O:ask-service
23. 0.9 0.05 0.05
24. 0.05 0.9 0.05
25. 0.05 0.05 0.9
26. -------------------------
27. R:do-service : E0 :
*
:
*
-10
28. R:do-service : E1 :
*
:
*
-20
29. R:do-service : E2 :
*
:
*
20
30. R:ask-service : E0 :
*
:
*
10
31. R:ask-service : E1 :
*
:
*
20
32. R:ask-service : E2 :
*
:
*
-20
Figura 6.2: Definição do POMDP (personalidade egoísta) como entrada para o algoritmo
Witness
53
A descrição do grafo de política (Tab. 6.1) é dada como se segue. Na primeira
coluna, tem-se os nodos por onde o agente transita. Na segunda, tem-se o id da ação
a ser executada naquele nodo, sendo 0 para do-service e 1 para ask-service.
Em seguida, tem-se os nodos seguintes, conforme as observações realizadas pelo agente.
Portanto, as três colunas representam, respectivamente, as observações N, D e C. Por
exemplo, no nodo 0 faz-se a ação 0 (ask-service): se observar N deve-se ir para o
nodo 4, se observar D deve-se ir para o nodo 1, ou, se observar C, deve-se ir para o nodo
0. Assim, pode-se montar o grafo de política simplificado visto na Fig. 6.4.
Por fim, é necessário transformar este grafo de política em regras para a imple-
mentação na plataforma Jason. Para tanto, utiliza-se o algoritmo policyToBDIplans
introduzido na Seção 5.2. Desta forma, tem-se regras na forma descrita na Fig. 6.3. No
próximo capítulo será feita a análise das simulações realizadas.
Tabela 6.1: Matriz representando o grafo de políticas do POMDP da Fig. 6.2
Nodo Ação Obs (N) Obs (D) Obs (C)
0 0 4 1 0
1 1 4 1 0
2 1 3 1 0
3 1 0 0 0
4 1 3 0 0
+!State(0): True ->
act(do-service),
!State(0’).
+!State(0’): obs==N ->
!State(4).
+!State(0’): obs==D ->
!State(1).
+!State(0’): obs==C ->
!State(0).
+!State(1): True ->
act(ask-service),
!State(1’).
+!State(1’): obs==N ->
!State(4).
+!State(1’): obs==D ->
!State(1).
+!State(1’): obs==C ->
!State(0).
Figura 6.3: Regra 0 e 1 para a implementação na plataforma Jason
54
Figura 6.4: Grafo de Políticas para o POMDP da Fig. 6.2
55
7 ANÁLISE DAS SIMULAÇÕES
Neste capítulo, discutem-se os resultados obtidos através das simulações de trocas
supervisionadas realizadas na plataforma Jason, onde os agentes com supervisor interna-
lizado deliberam sobre planos BDI que obedecem a políticas ótimas de POMDPs para
diferentes traços de personalidades, planos estes construídos com auxílio do algoritmo de
extração de planos policytoBDIplans.
Os traços de personalidades dos agentes são caracterizadas principalmente pela
forma como se comportam perante as trocas propostas pelo parceiro. Nas análises de
trocas supervisionadas, tem-se então duas formas de realização de trocas:
• Tipo I
αβ
: O agente α com supervisor internalizado propõe ao agente β baseado em
personalidade a prestação de um serviço para β, através da ação do-service;
• Tipo II
αβ
: O agente α com supervisor internalizado solicita ao agente β baseado
em personalidade a realização de um serviço para β, através da ação ask-service.
Para análise dos modelos, além dos agentes com as personalidades descritas na
Seção 7.2, foi implementado um agente sem personalidade, denominado de agente Teste,
que utiliza uma função randômica para gerar suas ações. Este agente é utilizado para
analisar o comportamento dos agentes com personalidade em trocas não supervisionadas,
para comparação com o comportamento dos mesmos agentes em trocas supervisionadas.
O agente Teste, quando utilizado para sugerir ações, gera um padrão randômico entre as
ações de “pedir serviço” (ask-service) e “fazer serviço” (do-service), normalmente em
torno de 50% para cada ação. Quando utilizado para receber as sugestões do agente com
supervisor internalizado, ele sempre aceita o que lhe é sugerido.
Nas análises realizadas, são consideradas 500 estágios de trocas em cada simu-
lação. Cada simulação gera um gráfico, onde o eixo horizontal representa o número de
trocas realizadas e o eixo vertical indica o balanço de valores materiais do agente (so-
matório de seus valores de investimentos e satisfações). Foram efetuadas 20 simulações
para cada modelo, com a identificação de um padrão de gráfico para o balanço das trocas
realizadas e o cálculo do balanço médio das trocas. Também realiza-se uma análise das
trocas geradas e recusadas em cada etapa de troca.
7.1 Metodologia das Simulações
Os modelos dos POMDP
α
, para cada estado do agente α com supervisor inter-
nalizado e cada traço de personalidade do agente β com o qual α interage, construídos
56
segundo a Def. 6.5.1, encontram-se no Anexo A. As matrizes dos respectivos grafos de
políticas obtidos com o algoritmo Witness estão no Anexo B.
Construída a biblioteca de planos BDI (que obedecem as políticas ótimas dos mo-
delos POMDPs) obtidos com o algoritmo policyToBDIplans, foi implementado, na
plataforma Jason, um simulador de trocas supervisionadas com agentes baseados nas per-
sonalidades descritas na Seção 7.2.
A metodologia utilizada para análise das simulações realizadas pode ser descrita
da seguinte maneira, para cada traço de personalidade do agente β:
1. Realizam-se trocas entre o agente Teste e o agente com o comportamento baseado
em personalidades, para analisar o comportamento do agente com personalidade;
2. Realizam-se trocas entre o agente com supervisor internalizado α e um agente com
personalidade β, para analisar o impacto da política sobre as trocas baseadas em
personalidade;
3. Varia-se o grau de supervisão, para analisar qual grau de supervisão é necessário
para manter o sistema em torno do estado de equilíbrio, em 500 estágios de trocas;
4. Realizam-se 20 simulações, calculando-se o balanço médio e a média de propostas
de trocas geradas pelo agente α e recusadas pelo agente β.
7.2 Personalidades
7.2.1 Tolerante
O agente que possui o traço de personalidade Tolerante não possui preferência
por nenhum tipo de troca, realizando as duas igualmente com uma certa probabilidade.
Na implementação realizada, considerou-se que a probabilidade de aceitar trocas do Tipo
I
αβ
ou Tipo II
αβ
são as mesmas (90%). O agente tolerante sempre realiza avaliações
realistas de seus valores virtuais de débitos e créditos.
A Fig. 7.1 mostra um exemplo do comportamento de um agente tolerante β em
trocas não supervisionadas, através de uma simulação de 500 estágios de trocas entre o
agente Teste e o agente tolerante β. Nesta simulação o balanço médio foi de 5, 02. O
balanço material médio do agente tolerante β, em 20 simulações, foi de −67, 2. Nestas
simulações, o agente tolerante recusou em média somente 20% das propostas de trocas
do agente Teste, como pode ser visto na Tab. 7.1.
7.2.2 Fanático
O agente Fanático tem a tendência de buscar o estado de equilíbrio. Se estiver no
estado de equilíbrio, o agente fanático possui 90% de probabilidade de recusar qualquer
tipo de ação do outro agente que o leve para um estado positivo (E+) ou negativo (E−),
seja do Tipo I
αβ
ou II
αβ
. Ao contrário, se estiver em um estado positivo, então tem 90%
de chance de aceitar uma troca do Tipo II
αβ
; ou, se estiver em um estado negativo, então
tem 90% de chance de aceitar uma troca da Tipo I
αβ
. Isto faz que a continuidade das
trocas possa ser comprometida. O agente Fanático sempre realiza avaliações realistas de
seus valores virtuais de débitos e créditos.
57
Figura 7.1: Exemplo do comportamento do agente β com traço de personalidade tolerante
em trocas não supervisionadas
A Fig. 7.2 mostra um exemplo do comportamento de um agente fanático β em
trocas não supervisionadas, através de uma simulação de 500 estágios de trocas entre o
agente Teste e o agente fanático β. Nesta simulação o balanço médio foi de −0, 19. O ba-
lanço material médio do agente fanático β, em 20 simulações, foi de 0, 33,permanecendo
na zona de equilíbrio [−2, 2] na maior parte do tempo. Nestas simulações, o agente
fanático aceitou em média somente 17% das propostas de trocas do agente Teste, como
pode ser visto na Tab. 7.1.
7.2.3 Altruísta
Um agente com o traço de personalidade Altruísta prefere fazer trocas que o
levem a um estado desfavorável E−, dessa forma tendo que realizar mais serviços do
que recebê-los. Na implementação, este traço de personalidade foi modelado da seguinte
forma: ele aceita 90% das sugestões do outro agente para fazer trocas do Tipo II
αβ
e
apenas 10% das sugestões de trocas do Tipo I
αβ
. Isto significa que quando lhe é solicitado
fazer um serviço ele irá aceitar a proposta na maioria das vezes, mas, quando o outro
agente tentar fazer um serviço para ele, este dificilmente irá aceitar a troca.
Diz-se que um agente altruísta é Altruísta Fraco, se ele realiza avaliações realistas
de seus débitos e créditos. O agente Altruísta Forte é o agente altruísta que tem alta
probabilidade de supervalorizar seus débitos e subvalorizar seus créditos.
Para modelar o POMDP do traço de personalidade Altruísta Forte, que superva-
loriza seus débitos e subvaloriza seus créditos, foi feita uma modificação na função de
observação do modelo de Altruísta Fraco, nas entradas do algoritmo Witness (Fig. 8.10,
Fig. 8.11 e Fig. 8.12). Na Fig. 7.3 tem-se a função de observação modificada.
A Fig. 7.4 mostra um exemplo do comportamento de um agente altruísta β em
trocas não supervisionadas, através de uma simulação de 500 estágios de trocas entre o
agente Teste e o agente altruísta β. Nesta simulação o balanço médio foi de −328, 27.
58
Figura 7.2: Exemplo do comportamento de um agente β com traço de personalidade
fanático em trocas não supervisionadas
O:ask-service
0.1 0.9 0.0
0.0 1.0 0.0
0.01 0.98 0.01
Figura 7.3: Função de observação modificada para o traço de personalidade Altruísta
Forte
O balanço material médio do agente altruísta β, em 20 simulações, foi de −950, 49,
mostrando sua preferência por prestar serviços (aceitando em média 80, 6% das trocas
do tipo I
αβ
), em vez de aceitar serviços de α (recusando em média 70, 5% das trocas do
tipo II
αβ
), como pode ser visto na Tab. 7.1. O agente altruísta forte apresenta o mesmo
tipo de comportamento, pois suas funções de transição são iguais.
7.2.4 Egoísta
O agente com o traço de personalidade Egoísta prefere que os outros agentes
realizem serviço para ele, e, portanto, realizando mais trocas que o levem para um estado
favorável E+. A implementação deste traço de personalidade foi feita da seguinte forma:
ele aceita 85% das sugestões do outro agente para fazer trocas do Tipo I
αβ
e apenas 30%
das sugestões de trocas do Tipo II
αβ
. Durante a execução ele irá recusar a maioria das
solicitações de prestar serviço para outro agente (Tipo II
αβ
), mas quase nunca irá recusar
receber um serviço (Tipo I
αβ
) do outro agente.
Diz-se que um agente egoísta é Egoísta Fraco, se ele realiza avaliações realis-
tas de seus débitos e créditos. O agente Egoísta Forte é o agente egoísta que tem alta
probabilidade tem alta probabilidade de supervalorizar seus créditos e subvalorizar seus
débitos.
59
Figura 7.4: Exemplo do comportamento de um agente β com traço de personalidade
altruísta em trocas não supervisionadas
Para modelar o POMDP do traço de personalidade Egoísta Forte, que superva-
loriza seus créditos e subvaloriza seus débitos, foi feita uma modificação na função de
observação do modelo de Egoísta Fraco, nas entradas do algoritmo Witness (Fig. 8.7,
Fig. 8.8 e Fig. 8.9). Na Fig. 7.5 tem-se a função de observação modificada.
O:ask-service
0.1 0.0 0.9
0.0 0.0 1.0
0.05 0.05 0.9
Figura 7.5: Função de observação modificada para o traço de personalidade Egoísta Forte
A Fig. 7.6 mostra um exemplo do comportamento de um agente egoísta β em
trocas não supervisionadas, através de uma simulação de 500 estágios de trocas entre o
agente Teste e o agente egoísta β. Nesta simulação o balanço médio foi de 290, 23. O
balanço material médio do agente egoísta β, em 20 simulações, foi de 1473, 4, o que
mostra sua preferência por receber serviços se α (aceitando em média 90% trocas do tipo
I
αβ
e aceitando em média somente 11% das trocas tipo II
αβ
), como pode ser observado
na Tab. 7.1. O agente egoísta forte apresenta o mesmo tipo de comportamento, pois suas
funções de transição são iguais.
7.3 Simulações supervisionadas
Foram realizadas 20 simulações com 500 estágios de trocas cada uma, entre os
agentes α (com o supervisor de equilíbrio interno) e β, nas quais α propõe trocas do tipo
I
αβ
ou II
αβ
para β, seguindo os planos construídos a partir do POMDP
∗
αβ
, para que ambos
60
Figura 7.6: Exemplo do comportamento de um agente β com traço de personalidade
egoísta em trocas não supervisionadas
sejam levados ao estado de equilíbrio.
A Fig. 7.7 mostra um exemplo da simulações realizadas entre o agente α e o
agente tolerante β, mostrando que α foi efetivo em levar o balanço de trocas de β para
a região do equilíbrio. Nesta simulação o balanço médio de β foi −0, 33. O balanço
material médio do agente tolerante β, em 20 simulações, foi de −0, 37 (dentro da zona
de equilíbrio [−2, 2]). Nestas simulações, o agente tolerante recusou em média somente
20% das propostas de trocas do agente α, como pode ser visto na Tab. 7.1. Observa-se
que um grau de supervisão de 50% (Fig. 7.8) é suficiente para manter o balanço de β na
região de equilíbrio, com β alcançando um balanço material médio de valores de troca de
−0, 669, em 20 simulações.
A Fig. 7.9 mostra um exemplo da simulações realizadas entre o agente α e o
agente altruísta β, mostrando que α foi efetivo em levar o balanço de trocas de β para
a região do equilíbrio. Nesta simulação o balanço médio de β foi −1, 84. O balanço
material médio do agente altruísta β, em 20 simulações, foi de −1, 84 (dentro da zona de
equilíbrio [−2, 2]). Nestas simulações, α gerou mais trocas do tipo I
αβ
(em média 79%)
do que do tipo II
αβ
, para promover trocas em que β poderia aumentar os seus resultados
materiais (ver Tab. 7.1).
A Fig. 7.10 mostra o efeito de 90% de supervisão sobre o comportamento de um
agente altruísta β. Nesta simulação, em 500 iterações, o balanço médio dos valores de
troca materiais de β foi −2, 65. Em 20 simulações, o balanço médio dos valores de troca
materiais de β foi −4, 55, mostrando que graus de supervisão inferiores a 100%, embora
não consigam levar β para a zona de equilíbrio, ainda conseguem melhorar seus resultados
(neste caso, o balanço médio dos valores de troca materiais de β aumentou 99, 52%, em
comparação com as trocas não supervisionadas).
A Fig. 7.11 mostra um exemplo da simulações realizadas entre o agente α e o
agente egoísta β, mostrando que α foi efetivo em levar o balanço de trocas de β para a
61
Tabela 7.1: Média das trocas geradas e recusadas em cada etapa de troca, em 20 simu-
lações com 500 estágios de troca cada uma
Trocas Tipo I
αβ
Trocas Tipo II
αβ
Personalidade Grau de Supervisão Geradas Recusadas Geradas Recusadas Balanço médio
Tolerante 0% 246, 75 50, 25 253, 2 49, 95 −67, 2295
Tolerante 50% 246, 9 47, 9 253, 1 53, 35 −0, 669
Tolerante 100% 250, 8 51, 55 249, 2 49, 2 −0, 3715
Altruísta 0% 249, 5 175, 9 250, 5 48, 6 −950, 49
Altruísta 90% 449, 75 406, 15 50, 25 4, 9 −4, 5545
Altruísta 100% 399, 2 318, 6 95, 8 19, 6 −1, 84
Altruísta Forte 100% 409, 65 369, 4 90, 35 9, 65 −60, 6045
Egoísta 0% 246, 1 25, 75 253, 9 227, 6 1473, 398
Egoísta 90% 56, 7 5, 45 443, 3 393 3, 544
Egoísta 100% 76, 4 12, 1 423, 6 358, 35 2, 129
Egoísta Forte 100% 111, 45 23, 95 388, 55 305 7, 6195
Fanático 0% 250, 7 208, 6 249, 3 207, 05 −0, 0405
Fanático 100% 158, 95 120, 65 341, 05 302, 55 −0, 6785
região do equilíbrio. Nesta simulação o balanço médio de β foi 1, 83. O balanço material
médio do agente egoísta β, em 20 simulações, foi de 2, 13. Nestas simulações, α gerou
mais trocas do tipo II
αβ
(em média 86%) do que do tipo I
αβ
, para promover trocas em
que β poderia diminuir os seus resultados materiais (ver Tab. 7.1). A Fig 7.12 mostra um
exemplo dos resultados para um agente β egoísta com um grau de supervisão de 90%,
onde o balanço médio dos valores de trocas materiais de β foi 2, 38. Em 20 simulações,
o balanço médio dos valores de trocas materiais de β, com grau de supervisão de 90%
foi de 3, 544, representando uma diminuição de 99, 75%, em comparação com trocas não
supervisionadas.
A Fig 7.13 mostra um exemplo do comportamento de um agente β altruísta forte,
em trocas supervisionadas, mostrando que é difícil levá-lo ao equilíbrio, devido à sua
característica de não avaliar de forma realista seus resultados virtuais. Nesta simulação,
o balanço médio foi de −6, 46. Entretanto, as simulações mostraram que α teve sucesso
em aumentar balanço médio dos valores de trocas materiais de β para um valor médio de
−60, 61 (um aumento de 90, 68% comparado à trocas não supervisionadas).
Resultados análogos foram obtidos para um agente β egoísta forte, como pode ser
visto na Fig. 7.14, onde o balanço médio dos valores de trocas materiais de β foi de 7, 79.
Em 20 simulações, o balanço médio dos valores de trocas materiais foi de 7, 62 (uma
diminuição de 99, 5% em relação à trocas não supervisionadas).
No Anexo C, são apresentados exemplos de simulações realizadas com diversos
graus de supervisão para diferentes tipos de traços de personalidades.
7.4 Considerações Finais
Neste capítulo foram apresentados os resultados dos testes realizados com as
políticas calculadas pelo algoritmo Witness, transformadas em regras pelo algoritmo
policyToBDIplans e executadas na plataforma Jason. Considerando os traços de
personalidades Altruísta, Egoísta, Fanático e Tolerante, realizando trocas livres, supervi-
sionadas e semi supervisionadas, as regras obtidas mantiveram as trocas dentro de uma
faixa de equilíbrio pequena.
Entretanto, com relação aos agentes Egoísta Forte e Altruísta Forte, as regras gera-
62
Figura 7.7: Exemplo do comportamento de um agente β com traço de personalidade
tolerante em trocas supervisionadas
das tiveram dificuldade em manter os agentes dentro da mesma faixa de equilíbrio obtida
para os outros traços de personalidades. Isto se deve ao fato de que agentes Egoísta Forte
e Altruísta Forte tem alta probabilidade de “mascarar” seu estado interno, dificultando a
análise realizada pelo supervisor.
Entretanto, consideram-se satisfatórios os resultados obtidos, pois, mesmo com
a complexidade dos referidos traços de personalidades, foi possível manter os resultados
das trocas entre uma determinada faixa, evitando o aumento (no caso de Agentes Egoístas)
ou a diminuição (no caso de Agentes Altruístas) sem controle de resultados materiais. No
próximo capítulo apresenta-se as conclusões do trabalho, bem como os possíveis trabalhos
futuros.
63
Figura 7.8: Exemplo do comportamento de um agente β com traço de personalidade
tolerante em trocas 50% supervisionadas, onde o balanço médio foi de −0, 84
Figura 7.9: Exemplo do comportamento de um agente β com traço de personalidade
altruísta em trocas supervisionadas
64
Figura 7.10: Exemplo do comportamento de um agente β com traço de personalidade
altruísta em trocas 90% supervisionadas
Figura 7.11: Exemplo do comportamento de um agente β com traço de personalidade
egoísta em trocas supervisionadas
65
Figura 7.12: Exemplo do comportamento de um agente β com traço de personalidade
egoísta em trocas 90% supervisionadas
Figura 7.13: Exemplo do comportamento de um agente β com traço de personalidade
altruísta forte em trocas supervisionadas
66
Figura 7.14: Exemplo do comportamento de um agente β com traço de personalidade
egoísta forte em trocas supervisionadas
67
8 CONCLUSÃO E TRABALHOS FUTUROS
Uma arquitetura BDI consiste de agentes racionais, capazes de ações indepen-
dentes e autônomas para atingir um determinado objetivo, para o qual foi projetado.
De maneira geral pode-se dizer que são agentes que decidem por si o que fazer, dada
uma situação. Um agente racional deve ter algumas propriedades tais como: autonomia,
pró-atividade, reatividade e habilidade social, ou seja, ser capaz de interagir com outros
agentes.
Entretanto, as abordagens atuais BDI não possuem ferramentas para análise quan-
titativa de desempenho sobre ambientes com incerteza. Um outro fator a ser considerado
sobre as abordagens BDI é o de que fazer com que o agente se comporte de maneira
ótima é uma tarefa complicada, pois não há garantia de que seu componente de raciocínio
meio-fim atue de maneira ótima. Dada a própria natureza das abordagens BDI, que são
heurísticas, ou seja, através da tentativa e erro, um comportamento ótimo é quase impos-
sível de ser alcançado, se comparado com agentes da teoria da decisão.
Os MDPs se concentram na resolução de problemas de decisão, onde as transições
do sistema dependem apenas de seu atual estado (e da ação a ser tomada) em domínios
do mundo real (BOUTILIER; DEAN; HANKS, 1999). A abordagem é fazer um mapea-
mento de todas as situações possíveis em um ambiente (estados), para ações, assim um
agente sempre sabe o que fazer, não importando o que acontece no ambiente.
Em um modelo MDP, o agente toma como entrada o estado do mundo e executa
uma ação como saída, e esta ação afeta o estado do mundo. Apesar de não se ter certeza
sobre o resultado das ações do agente (não-determinismo), sempre se tem certeza em
qual estado do ambiente o agente se encontra. Uma solução para este tipo de problema é
uma política: um mapeamento de estado/ação, que diz ao agente o que fazer em qualquer
estado do sistema.
Uma das principais desvantagens deste método de resolução de problemas é a
sua complexidade. Quando o espaço de estados ou de ações é muito grande, a própria
natureza dos algoritmos usados para solucioná-los torna estes problemas intratáveis.
Quando o ambiente onde se encontra o agente não é observável pelo mesmo, tem-
se então os Processos de Decisão de Markov Parcialmente Observáveis (POMDP). Um
agente, quando se encontra neste tipo de ambiente, deve fazer observações do ambiente
para estimar sua localização. A solução neste tipo de problema também é uma política,
mas diferente de sua forma totalmente observável. Como o agente não sabe em que
estado está, em vez de um mapeamento estado ação, tem-se um grafo de política, onde
nodos representam ações e observações são os arcos entre esses nodos.
Os POMDPs também sofrem das mesmas desvantagens dos MDPs, com espaços
68
de estados muito grandes, os problemas podem se tornar intratáveis.
No trabalho de (SIMARI; PARSONS, 2006) foi visto como estabelecer a relação
entre a arquitetura BDI e o modelo MDP, estabelecendo diversas equivalências entre os
dois modelos, com o objetivo de analisar a relação entre políticas MDP e planos BDI mais
profundamente.
Nesta dissertação, analisou-se a proposta de trabalhar com uma abordagem híbrida
apresentada em (SIMARI; PARSONS, 2006), e introduziu-se um algoritmo que obtém
planos para agentes BDI a partir de uma política ótima, apresentando um exemplo ilustra-
tivo de sua aplicação. Foram mapeadas políticas para i-plans dado que i-plans derivados
de uma política ótima são aqueles adotados pelo agente BDI que seleciona o i-plan com a
maior utilidade, e uma reconsideração de estratégia ótima; além disso, apresentou-se uma
versão computacional deste mapeamento, na forma de um algoritmo de busca baseado em
seguir uma dada política através do espaço de estados.
Para modelos parcialmente observáveis (POMDPs) foi utilizada uma versão mo-
dificada do algoritmo policyToBDIplans, que recebe a saída do algoritmo Wit-
ness (KAELBLING; LITTMAN; CASSANDRA, 1998), e, a partir do grafo de política
gerado pelo algoritmo, constrói regras para serem implementadas na plataforma Jason, na
linguagem AgentSpeak.
Na abordagem de valores de trocas para interações sociais (DIMURO; COSTA;
PALAZZO, 2005), uma interação é vista como uma troca de serviço entre dois ou mais
agentes, que avaliam estes serviços, dando valores aos mesmos. Esta teoria foi proposta
por Jean Piaget (PIAGET, 1995), como um teoria não-behaviorista, onde os valores têm
um papel muito importante nas trocas sociais.
Estes agentes dessa sociedade podem ter traços de personalidades distintos, que
caracterizam seu comportamento em relação às trocas que preferem fazer uns com os
outros. Por exemplo, um agente com um traço de personalidade egoísta tende a realizar
trocas para que ele fique em um estado favorável, recusando-se a fazer trocas que o deixem
em um estado desfavorável.
O balanço geral das trocas realizadas neste sistema pode ser analisado em termos
de seu estado de equilíbrio, onde todos os agentes estão com igualdade de benefícios, ou
em desequilíbrio, onde apenas um ou um pequeno grupo de agentes está sendo benefici-
ado.
Normalmente, um agente que segue somente a sua personalidade acaba por de-
sequilibrar o sistema, pois prefere um tipo de estado a outro. Por exemplo, um agente
que prefira, através de sua personalidade, permanecer em um estado desfavorável (caso
do agente altruísta), tende a realizar mais ações (prestação de serviços) que o levem a este
estado, desequilibrando o sistema.
Um supervisor de equilíbrio social (DIMURO; COSTA; PALAZZO, 2005) é
necessário para garantir que o sistema fique em equilíbrio. Este supervisor pode ser visto
como um componente da sociedade de agentes, normalmente externo aos agentes, que,
com base no balanço dos valores de troca, é capaz determinar o melhor conjunto de tro-
cas que devem ser realizadas entre cada par de agentes, a fim de trazer o sistema social de
volta ao equilíbrio, ou manter a continuidade das interações. Este supervisor recomenda
tais ações aos agentes do sistema, mas não os obriga a seguir suas recomendações: eles
podem decidir se irão seguir, ou não, tal recomendação. Nos trabalhos estudados (por
exemplo (DIMURO et al., 2006; DIMURO; COSTA, 2006b,a; DIMURO et al., 2006,
2007)), foi apresentado um mecanismo de regulação de trocas baseado num supervisor
69
de equilíbrio centralizado, com um processo de decisão de Markov qualitativo intervalar
associado.
Nesta dissertação, este mecanismo foi descentralizado e internalizado em cada
agente, onde foi modelado um POMDP para um supervisor interno de equilíbrio que
utiliza planos BDI obtidos a partir do algoritmo desenvolvido policyToBDIplans
para tratar com agentes com personalidades distintas, a fim de trazer equilíbrio para o
sistema, mas mantendo a continuidade das interações.
Considerando um conjunto de 4 traços personalidades (egoísmo forte e fraco, al-
truísmo forte e fraco, tolerância e fanatismo), foi definido um POMDP para cada modelo
de personalidade. Cada POMDP foi decomposto em 3 sub-POMDPs, um para cada es-
tado interno (balanço de trocas desfavorável, equilibrado ou favorável) do agente onde se
localiza o supervisor.
Foi desenvolvido na plataforma Jason um simulador de trocas supervisionadas
entre agentes baseados em personalidades, onde foram realizadas as simulações, con-
siderando também diferentes níveis de supervisão. Os resultados mostraram que foi pos-
sível manter o controle sobre o equilíbrio das trocas, mesmo no caso dos traços de perso-
nalidades mais complexos, como o Altruísmo Forte e Egoísmo Forte.
Considerando que os traços de personalidades foram caracterizados de forma
diferente do proposto inicialmente em (DIMURO et al., 2007), onde o supervisor cen-
tralizado era baseado em um MDP totalmente observável, não foi possível comparar os
resultados aqui obtidos com o supervisor híbrido BDI-MDP internalizado.
Observa-se que este trabalho considerou que apenas um dos agentes envolvidos
nas trocas tem supervisor internalizado e este agente não manifesta sua personalidade. A
continuidade imediata desta dissertação seria considerar que ambos os agentes tenham su-
pervisor internalizado e manifestem suas personalidades, que seria o caso mais completo
de auto-regulação de trocas sociais.
Ainda, como trabalhos futuros, pode-se destacar a extensão do trabalho (já na
forma descrita no parágrafo anterior) para considerar situações como:
• Agentes com diferentes graus de obediência ao seu supervisor interno, agindo con-
forme a sua personalidade com uma certa probabilidade, em vez de sempre propor
as trocas que o supervisor recomenda.
• Agentes com diferentes graus de obediência ao supervisor do parceiro.
• O supervisor que incorpora uma personalidade: neste caso, o supervisor interno não
mais buscaria o equilíbrio, e sim o comportamento que a personalidade comanda.
Por exemplo, um supervisor “egoísta” recomendaria trocas para que o agente per-
manecesse em um estado favorável.
• Desenvolvimento de aplicações contextualizadas, por exemplo jogos sérios de em-
presas.
Num âmbito desvinculado desta aplicação, uma análise interessante seria o es-
tudo de abordagens híbridas para outros tipos de MDPs, tais como, por exemplo,
MMDP (BOUTILIER, 1999) (Multi-Agent Markov Decision Process), onde a política
ótima depende de coordenação entre os agentes a fim de obterem a melhor recompensa
(ou atingir um objetivo em comum), WCMDP (Weakly Coupled Markov Decision Pro-
cess - MDPs Fracamente Acoplados (PARR, 1998; MEULEAU et al., 1998; DOLGOV;
70
DURFEE, 2004)), onde espaços de estados muito grandes são decompostos em conjuntos
de estados e depois recombinados para determinar a solução, dentre outros.
71
REFERÊNCIAS
BELLMAN, R. E. Dynamic Programming. Princeton: Princeton University Press, 1957.
BORDINI, R. H.; HÜBNER, J. F. BDI Agent Programming in AgentSpeak Using Jason
(Tutorial Paper). In: TONI, F.; TORRONI, P. (Ed.). Computational Logic in Multi-
Agent Systems, 6th International Workshop, CLIMA VI, London, UK, June 27-29,
2005, Revised Selected and Invited Papers. Berlin: Springer, 2005. p.143–164. (Lecture
Notes in Computer Science, v.3900).
BORDINI, R. H.; HÜBNER, J. F.; WOOLDRIGE, M. Programming Multi-agent Sys-
tems in AgentSpeak Using Jason. Chichester: John Wiley & Sons, 2007. (Wiley Series
in Agent Technology).
BOUTILIER, C. Sequential Optimality and Coordination in Multiagent Systems. In:
INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 16.,
1999, San Francisco. Proceedings.. . Morgan Kaufmann Publishers, 1999. p.478–485.
BOUTILIER, C.; DEAN, T.; HANKS, S. Decision Theoretic Planning: Structural As-
sumptions and Computational Leverage. Journal of Artificial Intelligence Research,
Menlo Park, v.11, p.1–94, 1999.
BRATMAN, M. E. What is Intention? In: COHEN, P. R.; MORGAN, J.; POLLACK,
M. E. (Ed.). Intentions in Communication. Cambridge: MIT Press, 1990. p.15–31.
CASTELFRANCHI, C.; ROSIS, F.; FALCONE, R.; PIZZUTILO, S. A testbed for in-
vestigating personality-based multiagent cooperation. In: SYMPOSIUM ON LOGICAL
APPROACHES TO AGENT MODELING AND DESIGN, 1997, Aix-en-Provence. Pro-
ceedings. .. [S.l.: s.n.], 1997.
CASTELFRANCHI, C.; ROSIS, F.; FALCONE, R.; PIZZUTILO, S. Personality traits
and social attitudes in multiagent cooperation. Applied Artificial Intelligence, [S.l.],
v.12, p.649–675, 1998.
DIMURO, G. P.; COSTA, A. C. R. Interval-based Markov Decision Processes for Regu-
lating Interactions Between Two Agents in Multi-Agent Systems. In: DONGARRA, J.;
MADSEN, K.; WASNIEWSKI, J. (Ed.). Applied Parallel Computing: Selected Papers
of the 7th International Conference, PARA’04, Lyngby, 2004. Berlin: Springer, 2006.
p.102–111. (Lecture Notes in Computer Science, v.3732).
72
DIMURO, G. P.; COSTA, A. C. R. Exchange Values and Self-regulation of Exchanges in
Multi-agent Systems: The Provisory, Centralized Model. In: BRUECKNER, S.; SERU-
GENDO, G. D. M.; HALES, D.; ZAMBONELLI, F. (Ed.). Engineering Self-Organising
Systems. Berlin: Springer, 2006. p.75–89. (Lecture Notes in Computer Science, v.3910).
DIMURO, G. P.; COSTA, A. C. R.; GONÇALVES, L. V.; HÜBNER, A. Regulating
Social Exchanges Between Personality-Based Non-transparent Agents. In: GELBUKH,
A. F.; GARÇA, C. A. R. (Ed.). MICAI 2006: Advances in Artificial Intelligence, 5th
Mexican International Conference on Artificial Intelligence, Apizaco, Mexico, November
13-17, 2006. Berlin: Springer, 2006. p.1105–1115. (Lecture Notes in Computer Science,
v.4293).
DIMURO, G. P.; COSTA, A. C. R.; GONÇALVES, L. V.; HÜBNER, A. Centralized
Regulation of Social Exchanges Between Personality-Based Agents. In: Coordination,
Organizations, Institutions, and Norms in Agent Systems II. Berlin: Springer, 2007.
p.338–355. (Lecture Notes in Computer Science, v.4386).
DIMURO, G. P.; COSTA, A. C. R.; PALAZZO, L. A. M. Systems of Exchange Values
as Tools for Multi-Agent Organizations. Journal of the Brazilian Computer Society,
Porto Alegre, v.11, n.1, p.31–50, 2005. Special issue on Agent’s Organizations.
DOLGOV, D. A.; DURFEE, E. H. Optimal Resource Allocation and Policy Formulation
in Loosely-Coupled Markov Decision Processes. In: FOURTEENTH INTERNATIONAL
CONFERENCE ON AUTOMATED PLANNING AND SCHEDULING (ICAPS 2004),
JUNE 3-7 2004, WHISTLER, BRITISH COLUMBIA, CANADA, 2004. Proceedings.. .
AAAI, 2004. p.315–324.
GUPTA, T.; VARAKANTHAM, P.; RAUENBUSCH, T. W.; TAMBE, M. Demonstration
of teamwork in uncertain domains using hybrid BDI-POMDP systems. In: INTERNA-
TIONAL JOINT CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT
SYSTEMS (AAMAS 2007), HONOLULU, HAWAII, USA, MAY 14-18, 2007, 6., 2007.
Anais. .. IFAAMAS, 2007. p.264.
KAELBLING, L. P.; LITTMAN, M. L.; CASSANDRA, A. R. Planning and Acting in
Partially Observable Stochastic Domains. Artificial Intelligence, Amsterdam, v.101, n.1-
2, p.99–134, 1998.
LOVEJOY, W. S. A survey of algorithmic methods for Partially Observable Markov De-
cision Processes. Annals of Operations Research, Amsterdam, v.28, n.1–4, p.47–66,
apr 1991.
MEULEAU, N.; HAUSKRECHT, M.; KIM, K.-E.; PESHKIN, L.; KAELBLING, L. P.;
DEAN, T.; BOUTILIER, C. Solving Very Large Weakly Coupled Markov Decision Pro-
cesses. In: NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-98)
AND OF THE 10TH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFI-
CIAL INTELLIGENCE (IAAI-98), 15., 1998, Menlo Park. Proceedings. .. AAAI Press,
1998. p.165–172.
NAIR, R.; TAMBE, M. Hybrid BDI-POMDP Framework for Multiagent Teaming. Jour-
nal of Artificial Intelligence Research, Menlo Park, v.23, p.367–420, 2005.
73
PARR, R. Flexible Decomposition Algorithms for Weakly Coupled Markov Decision
Problems. In: CONFERENCE ON UNCERTAINTY IN ARTIFICIAL INTELLIGENCE,
MADISON, 14., 1998, San Francisco. Proceedings. .. Morgan Kaufmann, 1998. p.422–
430.
PARUCHURI, P.; BOWRING, E.; NAIR, R.; PEARCE, J.; SCHURR, N.; TAMBE,
M.; VARAKANTHAM, P. Multiagent Teamwork: Hybrid Approaches. In: Com-
puter Society of India Communications. [S.l.]: CSI, 2006. (Invited Talk, avaliable at
http://teamcore.usc.edu/publications.htm).
PIAGET, J. Sociological Studies. London: Routlege, 1995.
PUTERMAN, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Pro-
gramming. New York: John Wiley & Sons, 1994.
RAO, A. S. AgentSpeak(L): BDI Agents Speak Out in a Logical Computable Language.
In: HOE, R. van (Ed.). Seventh European Workshop on Modelling Autonomous
Agents in a Multi-Agent World. Berlin: Springer, 1996. p.42–55. (Lecture Notes in
Computer Science, v.1038).
RAO, A. S.; GEORGEFF, M. P. An Abstract Architecture for Rational Agents. In: IN-
TERNATIONAL CONFERENCE ON PRINCIPLES OF KNOWLEDGE REPRESEN-
TATION AND REASONING (KR’92), CAMBRIDGE, MA, OCTOBER 25–29, 1992,
3., 1992. Proceedings.. . Morgan Kaufmann, 1992. p.439–449.
RUSSELL, S. J.; NORVIG, P. Artificial Inteligence: A Modern Approach. Upper Saddle
River: Prentice-Hall, 1995.
SCHUT, M. C.; WOOLDRIDGE, M.; PARSONS, S. On Partially Observable MDPs and
BDI Models. In: D’INVERNO, M.; LUCK, M.; FISHER, M.; PREIST, C. (Ed.). Foun-
dations and Applications of Multi-Agent Systems, UKMAS Workshop 1996-2000,
Selected Papers. Berlin: Springer, 2002. p.243–260. (Lecture Notes in Computer Sci-
ence, v.2403).
SIMARI, G. I.; PARSONS, S. On the relationship between MDPs and the BDI archi-
tecture. In: INTERNATIONAL JOINT CONFERENCE ON AUTONOMOUS AGENTS
AND MULTIAGENT SYSTEMS (AAMAS 2006), HAKODATE, JAPAN, MAY 8-12,
2006, 5., 2006. Proceedings.. . ACM, 2006. p.1041–1048.
SUTTON, R. S.; BARTO, A. G. Reinforcement Learning: An Introduction. Cambridge,
MA: MIT Press, 1998.
WATKINS, C. J. C. H. Learning from Delayed Rewards. London: King’s College,
1989. PhD Thesis.
WOOLDRIDGE, M. Reasoning about Rational Agents. Cambridge, Massachusetts:
The MIT Press, 2000. (Intelligent Robots and Autonomous Agents).
WOOLDRIDGE, M. An Introduction to MultiAgent Systems. Chichester: Wiley, 2002.
74
ANEXO A: MODELOS POMDP
Neste anexo, são apresentadas as entradas para o algoritmo Witness (o modelo
POMDP) para cada traço de personalidade e cada estado do agente com supervisor inter-
nalizado.
75
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.1 0.9 0.0
0.0 1.0 0.0
0.5 0.3 0.2
-------------------------------
T:ask-service
0.1 0.0 0.9
0.5 0.2 0.3
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
20
R:do-service : E1 :
*
:
*
-10
R:do-service : E2 :
*
:
*
20
R:ask-service : E0 :
*
:
*
-20
R:ask-service : E1 :
*
:
*
10
R:ask-service : E2 :
*
:
*
-20
Figura 8.1: Definição do POMDP Tolerante para o estado E+
76
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.1 0.9 0.0
0.0 1.0 0.0
0.5 0.3 0.2
-------------------------------
T:ask-service
0.1 0.0 0.9
0.5 0.2 0.3
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
-10
R:do-service : E1 :
*
:
*
-20
R:do-service : E2 :
*
:
*
20
R:ask-service : E0 :
*
:
*
10
R:ask-service : E1 :
*
:
*
20
R:ask-service : E2 :
*
:
*
-20
Figura 8.2: Definição do POMDP Tolerante para o estado E0
77
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.1 0.9 0.0
0.0 1.0 0.0
0.5 0.3 0.2
-------------------------------
T:ask-service
0.1 0.0 0.9
0.5 0.2 0.3
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
-20
R:do-service : E1 :
*
:
*
-20
R:do-service : E2 :
*
:
*
10
R:ask-service : E0 :
*
:
*
20
R:ask-service : E1 :
*
:
*
20
R:ask-service : E2 :
*
:
*
-10
Figura 8.3: Definição do POMDP Tolerante para o estado E−
78
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.9 0.1 0.0
0.0 1.0 0.0
0.7 0.2 0.1
-------------------------------
T:ask-service
0.9 0.0 0.1
0.2 0.1 0.7
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
20
R:do-service : E1 :
*
:
*
-10
R:do-service : E2 :
*
:
*
20
R:ask-service : E0 :
*
:
*
-20
R:ask-service : E1 :
*
:
*
10
R:ask-service : E2 :
*
:
*
-20
Figura 8.4: Definição do POMDP Fanático para o estado E+
79
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.9 0.1 0.0
0.0 1.0 0.0
0.7 0.2 0.1
-------------------------------
T:ask-service
0.9 0.0 0.1
0.2 0.1 0.7
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
-10
R:do-service : E1 :
*
:
*
-20
R:do-service : E2 :
*
:
*
20
R:ask-service : E0 :
*
:
*
10
R:ask-service : E1 :
*
:
*
20
R:ask-service : E2 :
*
:
*
-20
Figura 8.5: Definição do POMDP Fanático para o estado E0
80
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.9 0.1 0.0
0.0 1.0 0.0
0.7 0.2 0.1
-------------------------------
T:ask-service
0.9 0.0 0.1
0.2 0.1 0.7
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
-20
R:do-service : E1 :
*
:
*
-20
R:do-service : E2 :
*
:
*
10
R:ask-service : E0 :
*
:
*
20
R:ask-service : E1 :
*
:
*
20
R:ask-service : E2 :
*
:
*
-10
Figura 8.6: Definição do POMDP Fanático para o estado E−
81
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.1 0.9 0.0
0.0 1.0 0.0
0.2 0.7 0.1
-------------------------------
T:ask-service
0.9 0.0 0.1
0.2 0.7 0.1
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
20
R:do-service : E1 :
*
:
*
-10
R:do-service : E2 :
*
:
*
20
R:ask-service : E0 :
*
:
*
-20
R:ask-service : E1 :
*
:
*
10
R:ask-service : E2 :
*
:
*
-20
Figura 8.7: Definição do POMDP Egoísta para o estado E+
82
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.1 0.9 0.0
0.0 1.0 0.0
0.2 0.7 0.1
-------------------------------
T:ask-service
0.9 0.0 0.1
0.2 0.7 0.1
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
-10
R:do-service : E1 :
*
:
*
-20
R:do-service : E2 :
*
:
*
20
R:ask-service : E0 :
*
:
*
10
R:ask-service : E1 :
*
:
*
20
R:ask-service : E2 :
*
:
*
-20
Figura 8.8: Definição do POMDP Egoísta para o estado E0
83
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.1 0.9 0.0
0.0 1.0 0.0
0.2 0.7 0.1
-------------------------------
T:ask-service
0.9 0.0 0.1
0.2 0.7 0.1
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
-20
R:do-service : E1 :
*
:
*
-20
R:do-service : E2 :
*
:
*
10
R:ask-service : E0 :
*
:
*
20
R:ask-service : E1 :
*
:
*
20
R:ask-service : E2 :
*
:
*
-10
Figura 8.9: Definição do POMDP Egoísta para o estado E−
84
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.9 0.1 0.0
0.0 1.0 0.0
0.2 0.1 0.7
-------------------------------
T:ask-service
0.1 0.0 0.9
0.2 0.1 0.7
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
20
R:do-service : E1 :
*
:
*
-10
R:do-service : E2 :
*
:
*
20
R:ask-service : E0 :
*
:
*
-20
R:ask-service : E1 :
*
:
*
10
R:ask-service : E2 :
*
:
*
-20
Figura 8.10: Definição do POMDP Altruísta para o estado E+
85
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.9 0.1 0.0
0.0 1.0 0.0
0.2 0.1 0.7
-------------------------------
T:ask-service
0.1 0.0 0.9
0.2 0.1 0.7
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
-10
R:do-service : E1 :
*
:
*
-20
R:do-service : E2 :
*
:
*
20
R:ask-service : E0 :
*
:
*
10
R:ask-service : E1 :
*
:
*
20
R:ask-service : E2 :
*
:
*
-20
Figura 8.11: Definição do POMDP Altruísta para o estado E0
86
discount: 0.95
values: reward
states: E0 E1 E2
actions: do-service ask-service
observations: N D C
-------------------------------
T:do-service
0.9 0.1 0.0
0.0 1.0 0.0
0.2 0.1 0.7
-------------------------------
T:ask-service
0.1 0.0 0.9
0.2 0.1 0.7
0.0 0.0 1.0
-------------------------------
O:do-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
O:ask-service
0.9 0.05 0.05
0.05 0.9 0.05
0.05 0.05 0.9
-------------------------------
R:do-service : E0 :
*
:
*
-20
R:do-service : E1 :
*
:
*
-20
R:do-service : E2 :
*
:
*
10
R:ask-service : E0 :
*
:
*
20
R:ask-service : E1 :
*
:
*
20
R:ask-service : E2 :
*
:
*
-10
Figura 8.12: Definição do POMDP Altruísta para o estado E−
87
ANEXO B: MATRIZES DOS GRAFOS DE POLÍTICAS
Neste anexo, apresentam-se as matrizes dos grafos de políticas para os POMDPs
introduzidos Anexo A, obtidos com o algoritmo Witness.
Tabela 8.1: Regras para um agente Altruísta Fraco no estado E0
Regra Ação Observação N Observação D Observação C
00 00 07 02 00
01 00 07 03 01
02 01 07 03 01
03 01 07 04 01
04 01 07 05 01
05 01 06 05 01
06 01 01 01 01
07 01 06 00 01
Tabela 8.2: Regras para um agente Altruísta Fraco no estado E+
Regra Ação Observação N Observação D Observação C
00 01 02 01 02
01 01 02 02 02
02 00 02 00 02
Tabela 8.3: Regras para um agente Altruísta Fraco no estado E-
Regra Ação Observação N Observação D Observação C
00 00 02 01 00
01 01 02 01 00
02 01 02 00 00
88
Tabela 8.4: Regras para um agente Altruísta Forte no estado E-
Regra Ação Observação N Observação D Observação C
00 00 09 05 00
01 00 09 06 00
02 00 09 08 00
03 00 09 09 00
04 00 12 09 00
05 00 12 11 00
06 00 12 10 00
07 01 04 00 00
08 01 04 01 00
09 01 07 01 00
10 01 07 03 00
11 01 07 02 00
12 01 09 02 00
Tabela 8.5: Regras para um agente Altruísta Forte no estado E+
Regra Ação Observação N Observação D Observação C
00 01 05 04 05
01 00 05 00 05
02 00 05 01 05
03 00 05 02 05
04 00 05 03 05
05 00 05 04 05
Tabela 8.6: Regras para um agente Altruísta Forte no estado E0
Regra Ação Observação N Observação D Observação C
00 00 06 02 00
01 00 06 03 00
02 00 06 06 00
03 00 06 05 00
04 01 06 02 00
05 01 06 00 00
06 01 02 00 00
89
Tabela 8.7: Regras para um agente Egoísta Fraco no estado E0
Regra Ação Observação N Observação D Observação C
01 00 04 02 01
02 01 05 03 01
03 01 07 03 01
04 01 08 03 01
05 01 09 03 01
06 00 04 02 03
07 01 06 03 01
08 01 06 07 01
09 01 06 06 01
Tabela 8.8: Regras para um agente Egoísta Fraco no estado E-
Regra Ação Observação N Observação D Observação C
00 00 02 02 01
01 00 02 02 02
02 01 02 02 00
Tabela 8.9: Regras para um agente Egoísta Fraco no estado E+
Regra Ação Observação N Observação D Observação C
00 01 02 00 01
01 00 02 00 01
02 00 02 00 00
90
Tabela 8.10: Regras para um agente Egoísta Forte no estado E+
Regra Ação Observação N Observação D Observação C
00 01 09 00 05
01 01 09 00 06
02 01 09 00 08
03 01 09 00 09
04 01 12 00 09
05 01 12 00 11
06 01 12 00 10
07 00 04 00 00
08 00 04 00 01
09 00 07 00 01
10 00 07 00 03
11 00 07 00 02
12 00 09 00 02
Tabela 8.11: Regras para um agente Egoísta Forte no estado E0
Regra Ação Observação N Observação D Observação C
01 00 06 03 03
02 00 03 03 03
03 01 06 03 06
04 01 07 03 01
05 01 06 03 02
06 01 06 03 05
07 01 07 03 04
Tabela 8.12: Regras para um agente Egoísta Forte no estado E-
Regra Ação Observação N Observação D Observação C
00 00 05 05 04
01 01 05 05 00
02 01 05 05 01
03 01 05 05 02
04 01 05 05 03
05 01 05 05 04
91
Tabela 8.13: Regras para um agente Fanático no estado E+
Regra Ação Observação N Observação D Observação C
00 01 02 01 02
01 01 02 02 02
02 00 02 00 02
Tabela 8.14: Regras para um agente Fanático no estado E0
Regra Ação Observação N Observação D Observação C
01 00 08 07 01
02 01 06 01 01
03 01 08 02 01
04 01 08 03 01
05 01 04 05 01
06 01 08 04 01
07 01 06 07 01
08 01 08 06 01
Tabela 8.15: Regras para um agente Fanático no estado E-
Regra Ação Observação N Observação D Observação C
00 00 06 04 02
01 00 06 04 03
02 00 06 04 04
03 01 05 02 00
04 01 05 04 00
05 01 06 05 00
06 01 07 05 00
07 01 07 05 01
Tabela 8.16: Regras para um agente Tolerante no estado E+
Regra Ação Observação N Observação D Observação C
00 01 02 00 01
01 00 02 00 01
02 00 02 00 00
92
Tabela 8.17: Regras para um agente Tolerante no estado E0
Regra Ação Observação N Observação D Observação C
00 00 04 01 00
01 01 04 01 00
02 01 03 01 00
03 01 00 00 00
04 01 03 00 00
Tabela 8.18: Regras para um agente Tolerante no estado E-
Regra Ação Observação N Observação D Observação C
00 00 02 01 00
01 01 02 01 00
02 01 02 00 00
93
ANEXO C: OUTROS EXEMPLOS DE SIMULAÇÕES
Figura 8.13: Exemplo do comportamento de um agente β com traço de personalidade
tolerante em trocas 20% supervisionadas
94
Figura 8.14: Exemplo do comportamento de um agente β com traço de personalidade
tolerante em trocas 40% supervisionadas
Figura 8.15: Exemplo do comportamento de um agente β com traço de personalidade
tolerante em trocas 60% supervisionadas
95
Figura 8.16: Exemplo do comportamento de um agente β com traço de personalidade
tolerante em trocas 80% supervisionadas
Figura 8.17: Exemplo do comportamento de um agente β com traço de personalidade
altruísta em trocas 50% supervisionadas
96
Figura 8.18: Exemplo do comportamento de um agente β com traço de personalidade
altruísta em trocas 70% supervisionadas
Figura 8.19: Exemplo do comportamento de um agente β com traço de personalidade
egoista em trocas 50% supervisionadas
97
Figura 8.20: Exemplo do comportamento de um agente β com traço de personalidade
egoista em trocas 60% supervisionadas
Figura 8.21: Exemplo do comportamento de um agente β com traço de personalidade
egoista em trocas 80% supervisionadas
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
