MAC 499 - Trabalho de Formatura SupervisionadoNome do aluno: Sérgio Haruo Nakanishi Nome do supervisor: Flávio Soares Corrêa da Silva Tema da monografia: Aplicação do MMASS em jogos Tipo do trabalho: IC Aviso O documento HTML da monografia usa a codificação Unicode UTF-8 para símbolos matemáticos e pode precisar de (temporárias) mudanças de configurações do seu browser (em inglês). Nos testes em minha máquina o Firefox 1.5 reconheceu o código automaticamente, sem a necessidade de configuração manual. No Internet Explorer 6.0 não consegui configurar o browser corretamente. Se Deus quiser, o Internet Explorer 7.0 conseguirá reconher o código automaticamente. Índice
Introdução [índice]Com o avanço tecnológico (que permite o desenvolvimento de aplicações complexas) e com o amadurecimento da IA, o interesse pelos sistemas multi-agentes (MAS) cresceu nos últimos anos. MASs são sistemas compostos de vários agentes autônomos que interagirem, de forma cooperativa ou competitiva, de modo a contribuir na realização de um comportamento geral. Atualmente existem várias ferramentas para o desenvolvimento de MASs. Citando alguns exemplos temos o Jade, o TuCSoN e o Swarm. O avanço tecnológico também inclui os jogos de vídeo-games. O progresso do hardware torna possível a realização de simulações do nosso ambiente cada vez mais próximo da realidade, tanto no aspecto visual quanto no comportamento das leis da física. Um mundo representado realisticamente exige personagens com comportamento convincentes. É neste ponto que a IA atua em um jogo. Um MAS aplicado em jogos pode ajudar a gerenciar o comportamento de um grupo de agentes que devem agir como uma equipe para alcançar um objetivo (por exemplo, jogadores de futebol em busca do gol) ou para realizar um comportamento geral (por exemplo, um grupo de soldados devem marchar organizadamente) que são cenas comum em um jogo atualmente.  Agentes trabalhando em conjunto, algo comum nos jogos atuais O italiano Giuseppe Vizzari desenvolveu um framework para a construção de sistemas multiagentes chamado Multilayered Multiagent Situated System (MMASS), que foi tema de sua tese de doutorado em 2003. O objetivo do meu trabalho foi estudar, implementar e aplicar o MMASS em jogos. Mas os estudos não se limitaram ao MMASS. Para implementá-lo foi preciso conhecer C++ e principalmente aprender as bibliotecas Standard Template Library, Pthread, Boost e Ogre3D. Com exceção de C++ e da Ogre3D, nesta monografia procurei documentar todos estes assuntos estudados, principalmente o MMASS. Na seção que se segue será apresentado este sistema e na seção seguinte será discutido pontos interessantes da sua implementação. MMASS [índice]Nesta seção vamos apresentar os conceitos e dar a definição do MMASS. Note que em alguns trechos as notações apresentadas não são rigorosamente seguidas em troca de clareza. As subseções Visão geral e Definições são um resumo traduzido do capitulo 2 de [1]. Visão geral [índice]O MMASS é um framework formal e computacional para construção de sistemas multiagentes (MAS). Um MAS é formado por vários agentes autônomos que se interagem de forma a contribuir na realização de um comportamento geral. O MMASS é composto por várias camadas interconectadas (multilayered), cada uma delas podem representar diferentes aspectos do sistema que estamos modelando, como por exemplo, o espaço físico, mas também podem representar aspectos não relacionadas a noções físicas. Cada camada é um grafo conexo, os nós serão chamados de sítios, e as arestas formam o caminho por onde os agentes e campos podem se mover de um sítio para outro (veremos como mais adiante). Os agentes são posicionados sobre os sítios. Todo sítio abriga no máximo um agente (obedecendo a lei física da impenetrabilidade) e um agente ocupa apenas um nó em um dado instante (ele não é onipresente). Dois agentes são considerados adjacentes se eles ocupam sítios adjacentes (esta relação é a mesma de grafos onde dois nós são adjacentes se há uma aresta os ligando). A figura 1 ilustra os conceitos explicados até agora, temos uma camada e o agente A posicionado em um sítio.  Figura 1 Os agentes podem realizar quatro tipos de ações, a saber, acionar, caminhar, reagir e emitir campo. Apenas as duas últimas são usadas para a interação entre agentes. A reação permite que um agente interaja com um conjunto de outros agentes adjacentes a ele. Os envolvidos irão mudar de estado interno desde que todos concordem na realização desta ação, preservando a autonomia de cada agente. A emissão de campo permite a interação de agentes distantes (ou não adjacentes). Uma boa analogia para esta ação são os fenômenos naturais de emissão de ondas (por exemplo, o som). Um campo é um sinal que se espalha pela camada assumindo algum valor em cada sítio de acordo com as regras relacionadas do campo. Este sinal pode alcançar algum agente que, de acordo com seu estado e sua capacidade de percepção (que estão relacionados ao tipo do agente), pode ou não perceber o sinal. Se for percebido, o sinal pode acionar alguma ação neste agente atingido, por exemplo, emitir outro sinal. Como já foi dito, este sistema é formado por várias camadas interconectadas por interfaces. A interface regula a passagem de campos de uma camada para outra. Isso significa que um agente consegue influenciar agentes de outras camadas através da emissão de campo. Como será visto nas definições, um agente não consegue mudar de camada. A figura 2 mostra três camadas, uma sobre a outra, e entre elas há duas interfaces ligando a camada de baixo com a de cima.  Figura 2 O MMASS segue um modelo de interação indireto. Isso quer dizer que os agentes nunca mandam mensagens diretamente a outro agentes. Se eles quiserem interagir, a comunicação é feito através de um intermediário. No caso deste sistema, o intermediário é o próprio ambiente. Portanto, os agentes não são responsáveis pelo gerenciamento de suas ações, porém o ambiente deve fornecer toda a infraestrutura adequada para suportá-las. A figura 3 ilustra esta questão. Nela, o agente A notifica o ambiente da sua intenção de reagir com os agentes vizinhos, e então o ambiente é responsável em notificar os agentes vizinhos sobre a reação, além de executá-la caso seja aceita.  Figura 3 Um conceito importante neste framework é o posicionamento (situated). Todo agente ocupa um lugar específico no ambiente, que influencia o comportamento dele, por exemplo, um agente posicionado em um sítio sem campo ativo (valor diferente de nulo) pode ter um comportamento diferente se ele estivesse ocupando um sítio com vários campos ativos. O modelo de interação indireto introduz naturalmente este conceito de posicionamento. No modelo de interação direto, os agentes comunicam-se diretamente através de mensagens. Para introduzir o conceito de espaço neste caso, é necessário um certo esforço para modificar o protocolo das mensagens e o conceito seria introduzido artificialmente no sistema. Esta subseção foi um resumo geral do MMASS. Apesar de ser um pouco incompleto, ela é fácil de entender e irá facilitar a leitura da próxima subseção sobre as definições formais. Definições [índice]Uma camada do MMASS é chamada de Multiagent Situated System (MASS).
Definição 1: um MASS M é uma tripla onde EspaçoM representa o ambiente onde os agentes pertencentes ao grupo AM se posicionam, agem de forma autónoma e emitem campos pertencentes ao grupo FM.
Definição 2: um espaço S é um par onde:
O terceiro item, sobre o grafo ser conexo, parece estar errado, um contra-exemplo seria um grafo com os nós A,B,C e D, com uma aresta ligando A e B e uma aresta ligando C e D, este exemplo obedece o item em questão e mesmo assim não é conexo. Então o correto seria dizer que para qualquer par de nós, existe um caminho entre eles.
Definição 3: cada sítio p ∈ P é
uma tripla onde:
Definição 4: uma interface I(j, k) é
uma tripla onde pj ∈ Pj, pk ∈ Pk com j ≠ k. Pj e Pk relativos aos espaços MASSj e MASSk respectivamente. Em relação ao tipo de campo Fτ os sítios indicados são considerados adjacentes, ou seja, o campo do tipo Fτ ao chegar em pj será difundido nos sítios adjacentes (Ppj) e também em pk.
Definição 5: um caminho entre camadas
IPath(i, j), entre as camadas MASSi e MASSj,
é uma sequência de interfaces I(a1 , b1), ...,
I(ak , bk) tal que
Faça uma analogia com grafos. Se cada MASS for um nó, então as interfaces representam arestas. E assim, a definição 5 é a mesma definição de caminho entre dois nós de grafos.
Definição 6: um Multilayered Multiagent Situated System
(MMASS) é um par onde:
Definição 7: um tipo de campo Ft é uma
quádrupla onde:
Campos são sinais que os agentes podem emitir, eles espalham-se no ambiente assumindo algum valor em cada sítio calculado pela
função Difundirt. Um exemplo dessa função seria: A figura abaixo ilustra o comportamento de um campo. O pico do gráfico é o ponto de emissão e onde o campo tem o valor mais alto, conforme vamos nos afastando deste ponto, o valor do campo vai diminuindo.  Figura 4 Os campos podem persistir no ambiente logo após sua emissão ou desaparecer, tal comportamento é definido pela aplicação. A comunicação por campos é intrinsecamente multicast, os receptores dos sinais são desconhecidos. Dado F o conjunto de todos os campos em um MMASS, F = ∪t ∈ Τ Ft com Τ sendo o conjunto dos "rótulos" de todos os tipos de campo, e Fti ≠ Ftj quando i ≠ j.
Definição 8: um agente a ∈ A é uma tripla onde:
Definição 9: um tipo de agente τ é uma tripla onde:
Note que o coeficiente ciτ(s) é um fator de aumento da intensidade do campo, ou seja, se um agente estiver no estado s e posicionado no sítio p, e este sítio tem um campo ativo de valor fgp, então o valor percebido pelo agente será cgτ(s) • fgp. O tiτ(s) é o valor de campo mínimo que um agente conseque sentir para o tipo de campo correspondente a Fi, ou seja, se o agente sentir um campo abaixo deste valor, é como se ele não existisse. Vemos aqui que na comunicação por campos os receptores (os agentes que perceberão os campos) são determinados pelos seus tipos, estados e posições. O conjunto Açãoτ determina como que um agente do tipo τ pode mudar seu estado e posição e como interagir com agentes vizinhos e distantes. A seguir é explicado como que as ações conseguem este efeito. As próximas quatro definições são as ações que os agentes podem realizar, são eles acionar, caminhar, reagir e emitir. Acionar permite que os agentes mudem de estado, enquanto caminhar permite a mudança de posição. Reação define uma interação entre agentes vizinhos de acordo com um processo de duas etapas, primeiro os agentes devem concordar em participar da reação, depois os agentes devem estar em condições de escolher uma ação para a reação. Um agente também pode emitir um campo quando alguma condição o permitir. As definições das ações seguem a forma ação-cond-efeito. Ação é uma expressão do tipo f(x1, ..., xn), onde f é o nome da ação e xi são termos que podem aparecer em cond e/ou em efeito. Cond é a condição necessária para que esta ação possa ocorrer (mas isso não implica que esta ação seja escolhida de fato pelo agente as condições sejam satisfeitas). Efeito é o estado que o agente ou seu sítio estará depois que a ação for concretizada. Devido à autonomia, não é possível dizer a um agente algo sobre as condições de outros agentes (por exemplo, informações sobre o estado interno deles), exceto por fatos observáveis como, por exemplo, quais agentes são adjacentes ou se concordaram em participar de uma reação. Além disso, os efeitos das ações podem envolver somente uma mudança no estado do agente que está realizando a ação ou podem influenciar o ambiente por uma modificação local como, por exemplo, a emissão de um campo ou a mudança do estado de um sítio pela ação caminhar (estes efeitos serão vistos a seguir).
Definição 10: uma ação acionar é definida como:
Definição 11: uma ação caminhar é definida como:
Definição 12: uma ação emitir campo é definido como:
Definição 13: uma ação reação é definida como:
Estas foram todas as definições formais do MMASS. Essas definições não descrevem o sistema por completo. Resta mostrar o mecanismo de gerenciamento das ações. É mais conveniente descrever esse mecanismo junto com seu código e por isso será explicado na próxima subseção sobre a implementação. Implementação [índice]O trabalho do Vizzari discute sobre várias possibilidades de implementação, entre elas escolhi por fazer uma implementação multithread sincronizada. Neste caso, cada agente possui uma thread, assim como o ambiente, e cada thread possui um looping (while) onde cada iteração corresponde a um turno, então as threads ficarão sincronizadas por este turno. Mas antes de descrever a implementação, será feito uma introdução sobre as bibliotecas usadas. Bibliotecas usadasNesta seção irei mostrar alguns códigos em C++ que utilizam a Standard Template Library (STL), algumas funções de Pthread e as classes shared_ptr e weak_ptr da biblioteca Boost. Como este texto está sendo escrito para alunos de BCC do IME, suponho que os leitores não possuam experiência com estas bibliotecas, e portanto irei escrever breves introduções sobre cada uma delas. As introduções são voltadas para a prática com o objetivo de facilitar o entendimento dos códigos aqui apresentados. A parte conceitual das bibliotecas já são conhecidas pelos alunos (principalmente no caso da Pthreads, onde uso mutex e variável de condição). PthreadPthread é uma biblioteca em C que segue o padrão IEEE POSIX 1003.1c. Ele define um conjunto de tipos (structure) e funções para a criação e sincronização de threads. Sempre farei analogia com Java quando possível para facilitar a explicação. Assim como em Java, onde o comportamento de uma thread é definido no método run() da interface Runnable, em Pthread o comportamento da thread também é definido em uma função, porém, ao contrário de Java, esta função pode receber e retornar um valor do tipo void*, ou seja, qualquer tipo de valor. Uma thread é representada pela estrutura pthread_t. Podemos configurar alguns atributos dela através de uma outra estrutura do tipo pthread_attr_t. Neste trabalho o único atributo que usei foi o joinable que diz se o processo que criou a thread pode esperar pelo termino desta (como o método join() da classe Thread de Java). Para criar uma thread, usamos a função pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg), onde thread é a estrutura da thread e attr é a estrutura para configurá-la, se attr == NULL então é usado valores padrões, o terceiro parâmetro é o endereço de uma função que define o comportamento da thread e seu argumento é o parâmetro arg. Para esperar o termino de uma thread é usado a função thread_join(pthread_t thread, void **value_ptr), onde o parâmetro thread é a estrutura da thread e o retorno dela é guardada em value_ptr. Segue abaixo um exemplo simples para ilustrar seu uso:
Para passar dois ou mais argumentos para a função da thread, precisamos criar uma estrutura (ou uma classe) contendo todos os parâmetros e passá-lo como argumento na pthread_create. Para a sincronização entre as threads podemos usar a estrutura pthread_mutex_t que representa um mutex, antes de usá-lo devemos inicializar seus atributos com a função pthread_mutex_init(pthread_mutex_t *mutex, pthread_mutexattr_t *attr), onde o primeiro parâmetro é o mutex e o segundo parâmetro é uma estrutura usada para inicializar os atributos, se attr == NULL então valores padrões serão usados. Uma pthread_mutex_t é manipulada através da função pthread_mutex_lock(pthread_mutex_t *mutex). (Aqui é importante relembrar que um mutex é um semáforo binário) Quando esta função é executada por uma thread, se o valor do mutex é 1 então ela espera até que o valor do mutex mude para 0, se o valor do mutex é 0 então seu valor é mudado para 1 e a thread prossegue executando o comando seguinte, ou seja, a thread tenta "adquirir" o mutex. A função pthread_mutex_unlock(pthread_mutex_t *mutex) é usado para atribuir 0 ao mutex, ou seja, "liberar" o uso do mutex para outras threads. Portanto, seções críticas devem estar entre estas duas funções para garantir a exclusão mutua. O exemplo abaixo ilustra o uso de mutexes:
Fazendo uma analogia com Java, o uso de mutexes corresponde ao uso de blocos ou funções sincronizadas (synchronized). Então, os códigos abaixo são equivalentes.
A estrutura pthread_cond_t corresponde a uma variável de condição. Sua inicialização é feita através da função pthread_cond_init(pthread_cond_t *condition, pthread_condattr_t *attr) que é análogo à inicialização do mutex. Uma pthread_cond_t é usada em conjunto com uma pthread_mutex_t, ou seja, há sempre um mutex associado a uma variável de condição. Isso quer dizer que, antes de fazer qualquer operação sobre a variável de condição, a thread deve primeiro adquirir o mutex associado. Três funções são usadas para manipular uma pthread_cond_t. A função pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex) faz com que a thread que a executa entre em estado de espera na variável cond e faz a associação do mutex com esta variável. Sempre que uma thread entra em estado de espera em uma variável de condição, ela libera automaticamente o mutex correspondente (outros mutexes devem ser liberados manualmente antes de entrar em espera para evitar deadlock). A função pthread_cond_signal(pthread_cond_t *cond) tira alguma thread do estado de espera na variável cond. Para esta função ter o efeito esperado, primeiro deve ser adquirido o mutex corresponde à variável cond e a sinalização só tem efeito depois que o mutex é liberado. Analogamente, a função pthread_cond_broadcast(pthread_cond_t *cond) acorda todas as threads que estão em estado de espera na variável cond. O exemplo abaixo ilustra o uso dessas três funções:
Comparando com Java, o uso de variável de condição corresponde ao uso dos métodos wait(), signal() e signallAll(). Portanto, os códigos abaixo são equivalentes.
Templates e Standard Template Library (STL)Em Java, toda classe é derivada de Object, dessa forma a criação de containers genéricos é facilitada, basta que eles abriguem objetos do tipo Object. Mas em C++ as classes não possuem necessariamente um ancestral em comum e portanto não é possível adotar esta mesma solução. A criação de Templates surgiu como uma alternativa para resolver este problema [2]. Template é um modo de reutilização de código, assim como a herança, delegação e composição de classes também são. Entretanto, ele não faz parte do paradigma de programação orientada a objeto, na verdade é um mecanismo da própria linguagem C++ baseado no pré-processamento de macros da linguagem C. Ou seja, é um mecanismo realizado pelo compilador em tempo de compilação, e não pelo próprio programa em tempo de execução. O código abaixo mostra um exemplo de como criar um classe template.
O símbolo T é chamado de parâmetro do template. Note que T é indefinido (ele não é uma classe nem um tipo primitivo) e portanto não podemos utilizar esta classe (instanciar, derivar, etc) sem definir todos os seus parâmetros. O código abaixo mostra um exemplo de uso do template acima.
Quando encontra a linha (1), o compilador substitui o símbolo T por int e compila a classe. Portanto, para cada diferente parâmetro temos uma classe diferente. No código acima, Example<int> e Example<string> são duas classes distintas no sentido delas terem seus próprios códigos. Para este trabalho isso já é suficiente sobre template. Porém, ele é um mecanismo bastante flexível, é possível até realizar meta-programação, mas com certas limitações pois este não é sua finalidade. Para aprofundar neste assunto leia [2]. A STL é uma biblioteca de containers, algoritmos e iteradores. Quase todos seus componentes são templates. Neste trabalho, usei os containers set e map e a classe iterator (também usei a classe string, mas não irei explicá-la por ser parecido com Java). O set é um conjunto sem repetições e sem ordem, ou seja, inserir um objeto que já existe no set não tem nenhum efeito e os objetos não são necessariamente ordenados na ordem que são inseridos. Todos os containers são templates, no caso do set, o modo mais simples de utilizá-lo é fornecendo apenas um parâmetro que é o tipo de objeto que ele irá guardar. Segue abaixo um exemplo de utilização deste container.
O map é um conjunto de associações chave/valor sem repetições de chaves. Podemos enxergar um vetor de C como um map onde a chave é sempre um número (o número do índice). Por isso a sintaxe deste container imita o comportamento do vetor de C. A forma mais simples de declarar um map é definindo dois parâmetros para a template, o tipo da chave e o tipo do valor. O exemplo abaixo ilustra o seu uso.
Na STL, todo container possui uma classe interna chamada iterator. Como seu nome diz, esta classe serve para iterar sobre os elementos do container. Em C++, um iterator é uma generalização de apontador, ou seja, são objetos que apontam para outro objeto. Por isso, todas as operações usada em um apontador é aceita por esta classe. Neste trabalho, basicamente usei o operador ++ para avançar para o próximo elemento e o operador * para consultar o valor apontado pelo iterador (na verdade, a STL define vários conceitos de iteradores que não serão abordados aqui). Iteradores para o mesmo container podem ser comparados através dos operadores == e !=, dois iterators são iguais se eles apontam para o mesmo elemento, caso contrário são diferentes. Finalmente, para pegar um iterador que aponta para o primeiro elemento do container é usado o método begin(), para pegar um iterador que aponta para o elemento seguinte ao último elemento do container é usado o método end(), note que o valor deste último iterador não deve ser consultado, seu uso é apenas para fins de comparação. O exemplo abaixo ilustra o uso do iterator da classe set.
No map, a história é um pouco diferente. Os elementos do map são do tipo pair que é o par chave/valor, então, se temos um map<const string, int> seus elementos são do tipo pair<const string, int>. A classe pair tem dois campos públicos: first e second, onde first é a chave e second o valor. O exemplo abaixo mostra o uso de iteradores com map.
Boost: shared pointer & weak pointerA STL possui uma classe que faz o papel de um ponteiro inteligente chamada auto_ptr. Sua principal funcionalidade é tomar posse da referência para algum objeto alocado dinamicamente no heap, desse modo, quando o auto_ptr é destruído (por exemplo, por ter saído fora de escopo), a referência (nesta subseção, referência significa "o objeto apontado pelo apontador") também é destruída e sua memória liberada automaticamente (por isso se diz que o auto_ptr toma posse da referência). Esta classe foi criada para facilitar a vida de projetistas e programadores, mas algumas limitações não permitiam que ela fosse usada em muitos casos. Por isso, a biblioteca Boost incluiu extensões da classe auto_ptr tentando resolver estas limitações. A Boost foi iniciada por membros da C++ Standards Committee Library Working Group. Muitas de suas bibliotecas fazem parte do relatório técnico de bibliotecas deste comitê e são candidatas a fazer parte da STL. Neste trabalho usei as classes shared_ptr e weak_ptr. A shared_ptr toma posse da referência para algum objeto alocado dinamicamente, o que torna essa classe diferente é que ela pode dividir a posse com outros shared_ptr's. Para isso ela mantem um contador que guarda quantos shared_ptrs têm posse para a mesma referência, quando este contador chega a zero então o objeto é destruído e sua memória liberada automaticamente. Há casos em que a posse não deve ser compartilhada, por exemplo, vamos supor que um programador esteja manipulando objetos somente com apontadores inteligentes, se um objeto possuir uma auto-referência usando um shared_ptr, ele corre o risco de nunca ser destruído pois a auto-referência faz com que o contador sempre seja no mínimo 1. Neste caso devemos usar um weak_ptr que guarda uma referência para o objeto mas não toma posse dela, ou seja, ele não será contado como dono referência pelo shared_ptr. A classe shared_ptr foi projetada para ter referência de um único objeto, e não de um conjunto de objetos como os iteradores de containers. Portanto, aritmética de ponteiros não funciona nesta classe, apenas os operadores para "desreferenciar" funcionam nesta classe, ou seja, os operadores * e ->). No caso da weak_ptr, "desreferenciá-la" não seria uma operação segura pois o objeto referenciado pode ter sido destruído. Então, esta classe não serve para manipular diretamente os objetos, para isso primeiro é necessário conseguir uma shared_ptr contendo a mesma referência do weak_ptr. Esta classe possui um método justamente com esta finalizadade, o método lock. Segue abaixo um exemplo de uso das classes descritas.
Neste trabalho criei uma série de typedef's para facilitar a declaração
de apontadores inteligentes. Todo apontador que tiver esta cara: Classes do MMASSNote que as definições revelam uma parte da arquitetura do sistema, ou seja, mostram classes e suas relações. Por exemplo, podemos ver que um objeto do tipo MMASS possui um conjunto de objetos do tipo interface e do tipo MASS, e que um objeto do tipo MASS é composto de um objeto do tipo espaço e de um conjunto de objetos do tipo agente. A figura 5 mostra o diagrama de classes simplificado deste trabalho. Note que nem todas as definições tem uma classe correspondente. A classe Interface não foi implementada pois a aplicação do trabalho não aproveita a característica de multiplas camadas do MMASS.  Figura 5 Procurei implementar classes cujos os objetos não podem ser utilizados se não estiverem de acordo com suas definições. Por exemplo, um Space deve ter algum Site, e os Sites devem formar um grafo conexo. Deste exemplo, foi extraído um pedaço de código a ser comentado. Todos os códigos apresentados neste trabalho foram modificados ou para simplificá-los e melhorar sua legibilidade ou para não ter que explicar outras partes do sistema.
O código apresentado é o algoritmo de busca em profundidade (com o grafo sendo representado por uma lista de adjacência). O método checkGraph() conta quantas componentes conexas o Space possui. Sabemos que um grafo conexo possui somente uma componente conexa, portanto só precisamos detectar se o Space tem mais de uma componente para saber que não obedece à definição, como mostra a linha (1) [4]. Não há um motivo especial para ter usado a busca-em-profundidade, a busca-em-largura também funcionaria desde que os nós fossem marcados como visitados. Não explicarei a implementação de todas as classes neste texto. Porém alguns aspectos das classes Agent e Site deverão ser detalhados para um melhor entendimento do restante da seção quando o mecanismo das ações será esclarecida. A classe AgentO código abaixo mostra o trecho de código que será comentado. Trata-se de um conjunto de campos privados, cada um com seus respectivos métodos get's e set's que foram ocultados assim como o restante da classe.
O campo self é uma auto-referência. Ele faz o papel do this em conjunto com os apontadores inteligentes. Este campo está presente em quase todos as classes. Os campos mutex e cond são usados para fazer a sincronização entre as threads. A classe MMASS (que representa todo ambiente) também possui esses campos. O uso detalhado deles será visto no mecanismo de gerenciamento das ações, agora só precisamos notar que cada instância de Agent tem seu próprio mutex e variável de condição. O turn também é encontrado na classe MMASS e nas threads de agente. A sincronização do sistema é feito através do campo turn das três estruturas. Aqui é importante notar que cada objeto Agent tem seu próprio turn e cada thread de agente também tem seu próprio turn. A flag finish_thread, também encontrada na classe MMASS, indica que a thread do agente (e do ambiente no caso do MMASS) pode ser finalizada com segurança. Antes de comentar os outros campos, é necessário conhecer um pouco a finalidade de cada thread. Basicamente, as threads de agente faz com que o objeto Agent correspondente escolha uma ação, e a thread do ambiente faz o gerenciamento das ações escolhidas por cada um dos Agent's. A thread do agente, após o Agent correspondente escolher uma ação, entra em estado de espera e só é sinalizada pela thread do ambiente depois que esta ação for gerenciada, nesse instante já é possível saber se ela foi aceita ou não. Quando um Agent escolhe uma ação, ela é atribuída ao campo possibleAction, este campo guarda uma ação que ainda não foi gerenciada pelo ambiente. O campo action guarda uma ação que foi aceita pelo ambiente (e portanto já passou pela fase de gerenciamento). Então, se o estado do campo action for action != NULL, então sabemos que o Agent teve uma ação aceita, mas isso não é suficiente para cobrir outros casos, por isso esta classe tem mais duas flags auxiliares. A flag action_performed é verdadeira se a ação escolhida pelo agente no turno atual foi gerenciada, caso contrário ela é falsa. A flag action_accepted é verdadeira se a última ação que foi gerenciada deste Agent foi aceita (não importa se foi do turno anterior ou do turno atual), caso contrário é falsa. Com essas flags e os campos de ação, conseguimos saber qual a situação do agente em relação à ação escolhida (se já foi gerenciada e se foi aceita). O uso deles serão vistos mais adiante no mecanismo de gerenciamento das ações. Para as classes Action, Agent e Site, existem classes correspondentes ActionInfo, AgentInfo e SiteInfo. Estas classes guardam informações das classes originais na forma de strings. A finalidade delas é impedir com que a classe Agent tenha acesso direto a estruturas que não podem manipular diretamente (por exemplo, outros Agent's). O campo deniedActions é um conjunto de ActionInfo's das ações que não foram aceitas pelo ambiente no turno corrente. A classe SiteSegue abaixo o trecho de código a ser comentado.
O campo sitesDistances é um mapa onde a chave é o nome de um Site e o valor é a distância entre o este objeto (a própria instância de Site) e o Site cujo o nome é a chave. Ou seja, é um container que guarda as distancias entre este Site e os outros Site's da mesma camada. O campo space é uma referência para o espaço onde este Site está contido (definição 2). O campo sitesInDistanceOrder é uma fila FIFO que contém os nomes dos outros Site's em ordem crescente. Na verdade ele é um pouco mais do que isso, explicarei melhor a seguir. A definição de distância entre dois sítios é o mesmo de grafos, isto é, o tamanho do menor caminho entre ambos os sítios. Portanto uma busca-em-largura resolve o problema do calculo das distâncias. Abaixo está o código que atribui os valores para os campos apresentados acima.
O código acima é uma busca-em-largura. Durante a busca, as distâncias são calculadas e os campos comentados anteriormente são construídos. Em especial, note que o sitesInDistanceOrder é preenchido na mesma ordem da busca. Lembre-se que este campo é uma fila FIFO e portanto iteramos sobre seus elementos na ordem em que foram inseridos, portanto, por construção, esse campo guarda uma árvore geradora mínima do espaço (ou do grafo conexo), com este objeto (o próprio Site) sendo a raiz (porém, note também que a raiz não é incluso na fila). Gerenciamento das açõesA seguir será apresentado o mecanismo de gerenciamento das ações. Este mecanismo é composto por várias threads e estas tthreads são sincronizadas pelo campo turn das classes Agent, Site e da thread de agente. Threads dos agentesCada agente possui uma thread correspondente, seu código é apresentado e explicado a seguir. Esta thread é responsável pelo gerenciamento das ações do agente e pela sincronização com o ambiente, que também possui sua thread. Em geral, as funções da biblioteca Pthread podem ser ignoradas, sua função é evitar que as threads executem seções críticas simultaneamente e portanto não fazem parte do mecanismo propriamente dito, exceto as funções de espera e de sinalização que tem papel importante. Para ser mais direto, pode ignorar as funções pthread_mutex_lock e pthread_mutex_unlock, mas não ignore as funções pthread_cond_wait e pthread_cond_signal/broadcast.
Para fins comparação e esclarecimento de alguma dúvida sobre o código acima, também vou mostrar o pseudo-código do artigo do Vizzari abaixo.  Dentro do while temos os três passos que são tomados por uma thread de agente. Primeiro, toma-se conhecimento do estado local do ambiente, esta informação encontra-se dentro do objeto localContext (linha (1)). Neste objeto podemos obter os nomes dos agentes vizinhos, seus tipos, os nomes dos sítios nos quais estes agentes estão posicionados, os nomes de todos os sítios vizinhos e os campos ativos no local e na vizinhança. Todas estas informações são necessárias para escolher alguma ação de acordo com as definições 10 à 13, além disso, este objeto garante que o Agent não terá acesso direto a outros Agent. Em seguida, baseado no contexto local, o agente escolhe qual ação tomar (linha (2)). Finalmente, o ambiente é notificado da escolha, e a thread do agente espera o ambiente responder se aceitou a ação (linha (3)), caso positivo a thread avança seu turno, caso contrário repetimos os 3 passos (escolhendo outra ação na linha (2)). Há um caso onde não é esta thread que faz com que seu objeto Agent correspondente escolha uma ação. Lembre-se que uma reação só é aceita se todos concordarem em realizá-la, e então cada um dos envolvidos escolhe sua própria reação. Quando isso ocorre não é a thread do agente que faz os envolvidos escolher a reação e sim a thread do ambiente (que veremos mais adiante). Aqui é importante perceber que a thread do agente não faz parte do agente, esta thread é apenas um mecanismo para manipular os objetos Agent's. Repare que a ação só é escolhida se o if acima da linha (2) for satisfeita. As condições deste if servem para cobrir o caso da reação que acabou de ser descrito. Para explicá as condições é mais fácil pensar na negação: quando que o if não é satisfeito? Quando o possibleAction != NULL significando que o agente já escolheu uma ação e deve esperar para ser gerenciado, quando action != NULL, ou seja, uma ação já foi escolhida, gerenciada e acieta e o agente deve esperar ela ser executada, ou quando action_performed == true que ocorre quando uma ação já foi escolhida, gerenciada, aceita e concretizada. Ou seja, um agente só escolhe uma ação se ainda não escolheu uma para o turno atual. Cada thread manipula seu próprio objeto do tipo Agent, ou seja, ela lê e escreve em seu próprio espaço da memória. Neste sentido podemos enxergar as threads dos agentes e a thread do ambiente como um problema parecido com o do tipo produtor / consumidor, onde a thread do agente produz uma ação em seu buffer (o objeto Agent) e espera pelo ambiente consumí-lo. Esta espera ocorre na linha (1), e a produção ocorre na linha (2). Na linha (1) também ocorre a sincronização dos turnos, isto é, ocorre a espera pelo turno das duas threads (do agente e do ambiente) serem as mesmas. Note que o MMASS é um modelo de troca indireta de informações e o código acima torna isto explícito. Para realizar uma ação o agente envia uma mensagem para o sítio em que se encontra (linha (3)), e então ele escolhe sua ação baseado nas informações do objeto localContext, que é um conjunto de strings (linha (2)), e portanto, não há acesso direto a outros agentes, ou seja, o agente nunca manda uma mensagem diretamente para outro, o ambiente é sempre um intermediário (linhas (1) e (3)). Até aqui já é o suficiente para entender esta thread e é neste ponto que o Vizzari encerra a explicação para o caso multithread sincronizado. Porém, como este trabalho é uma implementação, irei aprofundar um pouco mais a explicação. Segue abaixo o código do método sense().
Este método recebe um Agent e o turno da thread deste agente como parâmetros e retorna o contexto do Site onde o Agent se encontra. Veja na linha (1) que este método faz com que a thread do agente entre em estado de espera se o turno dela for maior que o turno do ambiente, portanto o contexto só é criado se o turno do agente for igual ou menor ao turno do ambiente. Quando o turno do ambiente é maior (e portanto diferente) que o do agente, o contexto criado fica fora de sincronia, ou seja, o agente irá receber um contexto de um turno diferente ao esperado por ele. Apesar dessa inconsistência neste local do código, toda ação baseada em contexto errado é descartada. Há um detalhe importante neste método, ele faz com que uma thread adquira dois mutex ao mesmo tempo. Isto é perigoso pois pode provocar deadlock, para evitar isso é necessário que todas as threads adquiram os mutexes na mesma ordem. No caso da minha implementação a ordem é: primeiro o mutex do MMASS e depois o mutex do Agent. O método actionSelect é definido pelo usuário do MMASS e será explicado em outra seção. O código do método act segue abaixo.
Este método recebe um Agent e o turno da thread deste agente e retorna true caso a ação escolhida pelo Agent para este turno foi aceita ou false caso contrário. A função deste método é fazer a thread do agente esperar pela ação ser gerenciada. Um detalhe a ser notado é que this->turn refere-se ao turno do ambiente e turn_ é o turno da thread do agente. Na linha (1) temos as condições de espera, é mais fácil entender estas condições explicando suas negações (quando que a thread não espera). O caso possibleAction == NULL ou action != NULL significa que a ação foi gerenciada e ainda não foi executada, se a ela tivesse sido executada a thread do ambiente destruiria o action e teriamos que action == NULL, por isso a thread do ambiente também liga a flag actionPerformed que indica que a ação para o turno corrente foi gerenciada (independentemente se foi aceita ou não). Portanto, a thread do agente entra em estado de espera se a ação ainda não foi gerenciada. Na linha (2), depois que a ação foi gerenciada examinamos o estado de alguns campos para saber se a ação foi aceita. Se action != NULL então a ação foi aceita e não foi executada, caso a ação tenha sido aceita e executada então teriamos que action == NULL, por isso a flag actionAccepted é ligada e indica que a última ação escolhida foi aceita. Nesses casos o método retornará true, caso contrário false. Note que tanto na linha (1) quanto na linha (2) as condições que envolvem o turno não foram explicadas. Elas cuidam do caso que a thread do agente está fora de sincronia com a thread do ambiente. Caso a thread do agente esteja atrasada (seu turno é menor que o turno do ambiente), isto quer dizer que nesses turnos que se passaram foi a thread do ambiente que fez com que o objeto Agent correspondente escolhesse as ações (isso só é possível no caso de reações). E portanto, qualquer ação escolhida para um turno que já se passou deve ser ignorada (este é o mesmo caso do contexto inconsistente que já foi comentada nesta seção). Thread do ambienteCódigo da thread do ambiente é apresentado abaixo:
Segue abaixo o pseudo-código do Vizzari abaixo. Há uma diferença na minha implementação e a do pseudo-código. Atribuir true para a flag action_performed é feito dentro da função manage, e atribuir false para a flag é feito na thread do agente. Apesar dessa diferença, a função da thread do ambiente permanece inalterada.  Na linha (1) uma fila é inicializada com todos os agentes do sistema. Esta estrutura é a fila de todos os agentes que estão escolhendo alguma ação para o turno atual (acima da linha (1)). Um agente sai desta fila somente quando sua ação é aceita pela thread do ambiente (linha (4)). O ambiente só avança de turno quando todos os agentes tiveram suas ações para o turno atual aceitas (linha (2) e (8)). A parte principal desta thread é a linha (3). A função manage é responsável por gerenciar adequadamente cada tipo de ação, por exemplo, chamando a função reactionManager para gerenciar reações. A função manage também acorda as threads de agente que estavam esperando pelo ambiente aceitar ou não uma ação (lembre-se que esta espera ocorre na função act do código anterior). Apesar das ações serem aceitas na linha (3), elas não são imediatamente executadas. Há dois motivos para isso ocorrer. Primeiro, devemos preservar o estado do ambiente para o turno em andamento, pois os agentes que ainda não escolheram uma ação devem observar o contexto do turno atual. Segundo, porque os agentes que já escolheram e tiveram suas ações confirmadas podem ter que reconsiderá-las, por exemplo, no caso da reação, se um agente A escolheu e teve confirmada uma ação de emitir e um agente B pede uma reação com o agente A, talvez este descarte a emissão para reagir com o agente B. Portanto as ações são executadas assim que todos os agentes tiverem suas ações aceitas, ou seja, somente quando é possível avançar de turno. Isso quer dizer que o estado do ambiente e dos agentes só mudam (em consequência das ações) no final de cada turno (na linha (6)). O Vizzari encerra as explicações para o caso multithread e síncrono neste ponto, mas como já foi dito, continuo a explicação por se tratar de uma implementação concreta. A linha (5) destrói todos os campos ativos antes de executar as ações. Isto quer dizer que os campos não persistem no ambiente com o tempo, ou seja, se um agente decide emitir um campo no turno n, os efeitos deste campo poderão ser percebidos no turno n + 1 e desaparecerão no turno n + 2. Todo MASS (ou camada) possui um set de sítios ocupados, ela é usada pelo transportManagement, que será explicada mais adiante. Na linha (7) esta estrutura é esvaziada em todas as camadas. Note que após o avanço do turno, todas as threads que estavam esperando na variável de condição do ambiente são acordadas. Lembre-se que as threads de agente esperam nesta variável quando entram na função sense (do código anterior) e esperam pela sincronização dos turnos. Segue abaixo o código do manage.
A função recebe um Agent e sua Action escolhida para o turno turn, retorna true se a ação foi aceita e false caso contrário. Em dois casos a ação não é gerenciada: quando ela já foi gerenciada e aceita (linha (1), a condição action != NULL só é verdade se o agente já teve sua ação gerenciada e aceita) ou quando ainda não foi escolhida uma ação (linha (2)). Em qualquer outro caso a ação será gerenciada na linha (3), nesta linha a função adequada para a ação será chamada. Depois que a ação é gerenciada, a thread de agente que estava esperando por isto é acordada (linha (4)). Lembre-se que uma thread de agente espera uma ação ser gerenciada na função act. Agora vamos ver as funções de gerenciamento específicos para cada tipo de ação, começando pelo triggerManagement para a ação acionar, e o emitManagement para a ação emitir. Em seguida veremos o reactionManagement para reação e o transportManagement para caminhar. Todas essas funções recebem os mesmos parâmetros da função manage.
Essas duas funções são as mais simples das quatro. Elas são idênticas pelo fato das ações acionar e emitir nunca serem negadas, então o gerenciamento delas resume-se a mudar o estado dos campos do objeto Agent para indicar que a ação foi aceita. Na linha (1), o método peformAction é chamada sempre que uma ação é aceita, nela é atribuido ao campo action a referência à ação que foi aceita e o campo possible_action recebe o valor NULL. Nas duas linhas seguidas mudamos as flags action_performed para true, pois a ação foi gerenciada, e a flag action_accepted para true. Sempre que uma ação é aceita, os passos a serem tomados são parecidos. Portanto essas funções podem ser tomados como um modelo do que deve ser feito para aprovar uma ação, com algumas pequenas modificações dependendo da ação. A seguir vamos ver o transportManagement que faz um agente caminhar do seu sítio atual (origem) para algum sítio vizinho (destino).
Na linha (1) o set de sítios ocupados é inicializado, esta é a mesma estrutura que é esvaziada no final do turno no environmentBehaviourThread. Na primeira vez (em um dado turno) que este set é inicializado, ele possui apenas os sítios onde os agentes estão posicionados. Em seguida, na linha (2) e (3), verificamos se o sítio de destino (pra onde o agente vai se mover) está ocupado, caso esteja ocupado, a ação de caminhar deve ser negada, para isso o if da linha (3) é executado. O método notifyFailure da linha (4) é o oposto de performAction da linha (5). O notifyFailure é chamado sempre que uma ação é negada, nele o campo possible_action é destruído sem ocorrer nenhuma troca. Nas duas linhas seguintes, mudamos os estados das flags para refletir no gerenciamento (action_performed = true) e na negação da ação (action_accepted = false). Veja também que acima da linha (4), a ação é colocada no conjunto de ações negadas para o agente no turno corrente. Se a ação for aceita então os passos tomados são os mesmos do triggerManagement (onde a ação é sempre aceita) como podemos ver na linha (5) em diante, exceto a linha (6) onde adicionamos o sítio de destino no set de sítios ocupados do turno corrente. Como foi dito, a primeira vez que este set é inicializado temos somente os sítios onde os agentes estão posicionados no turno atual, nas consultas seguintes esta estrutura também terá os sítios que serão ocupados no turno seguinte. Isto é feito para evitar que dois Agent's consigam mover para um mesmo Site ao mesmo tempo. Nesta implementação, o agente que caminhar primeiro para o sítio conseguirá concretizar a ação. Agora veremos o código do reactionManagement, o mais complexo dos quatro.
O Vizzari fornece o pseudo-código deste método, mostrado na figura abaixo.  A primeira parte desta função (o primeiro laço for), na linha (1), pergunta para cada agente envolvido se ele concorda em participar da ação, caso algum não aceite participar então já sabemos que a reação não será realizada, portanto não é necessário perguntar ao restante dos agentes, em seguida é atribuído o valor falso para a variável agreed que indica se todos os agentes concordaram ou não com a reação. Depois que o primeiro laço acaba, o agreed é verificado para saber se a ação foi aceita (linha (2)) ou não (linha (5)). Caso tenha sido aceita, as passos tomados são parecidos com os da função emitManagement (onde as ações são sempre aceitas), as flags e alguns campos de cada Agent envolvido devem mudar de estado para refletir o fato da reação ter sido aceita. Na linha (3) é verificado se os agentes já tiveram alguma ação aceita neste turno, se não tiveram então a flag action_performed é ligada, caso contrário esta flag já está ligada e não é preciso modificá-la, porém, no caso da ação anterior ter sido do tipo transport (caminhar) então o conjunto de sítios ocupados deve ser atualizado para refletir o cancelamento (linha (4) em diante). Depois disso, a flag action_accepted é ligada e os valores dos campos possible_action e action são trocados através do método performAction, igual nas funções de gerenciamento anteriores quando a ação é aceita. Caso a reação não tenha sido aceita, então é executada linha (5) em diante. Dentro do for é feito operações sobre os agentes que aceitaram realizar a reação que foi negada. Para cada um desses agentes é atribuído o valor falso para o action_accepted, a flag action_performed permanece no estado que estava: verdadeiro para os que já tinham uma ação gerenciada e falso para os que não tinham, exceto para o autor da reação onde, na linha (6), essa flag deve ser ligada. Em seguida, a reação recusada é colocada no conjunto de ações negadas para cada agente e então o possible_action é destruído pelo método notifyFailure e por fim cada um dos agentes são acordados. Esta seção encerra aqui. Não pretendo descrever a implementação do sistema todo neste texto. As definições formais e o mecanismo das ações explicados já são o suficiente para entender como utilizar esta implementação do MMASS para a definição de sistemas multiagentes, este é o assunto da seção a seguir. Como utilizar [índice]Será mais fácil explicar o uso deste MMASS com o auxílio de um exemplo. Nesta seção será definido um sistema com dois agentes, um gato e um rato. O primeiro o comportamento dos agentes devem ser determinados: o gato deve perseguir o rato, o rato deve fugir do gato, se o gato alcançar o rato então o rato é capturado, se o gato não percebe a presença do rato então ele permanece parado, se o rato não percebe a presença do gato então ele permanece parado. Agora que o comportamento do sistema está claro, vamos usar o MMASS para implementá-lo. A implementação é dividido em duas fases. A primeira é a definição de classes e métodos, a segunda parte é a construção do cenário, ou seja, montar as camadas e posicionar os agentes. Na primeira fase, para saber quais classes implementar, reveja o diagrama UML do framework. Com exceção da classe Action, todas as outras classes abstratas serão estendidas (Field, Agent, State, Trigger e Reaction). No exemplo, há dois tipos de agentes, o gato e o rato, e portanto devem ser criadas duas classes do tipo Agent. Cada classe Agent deve ter sua própria classe State correspondente. Então o primeiro passo é estender a classe State. Segue o cabeçalho dela abaixo.
Esta classe é bem simples pois ela é inteiramente dependente da aplicação, inclusive a sua interface. Abaixo está o código dos estados do gato e do rato.
Uma vez definido os estados, é possível definir os agentes. Segue abaixo o cabeçalho da classe Agent.
A partir de um objeto Agent deve ser possível recuperar o seu correspondente objeto State específico (ou estendido). Uma solução poderia ser a criação de um método getState que devolve uma referência para a classe State e então o usuário faz o downcast manualmente para a classe derivada, o downcast geralmente é necessário para ter acesso à interface da classe estendida. Outra solução pode ser a que foi usada pela classe CAgent que usa templates para guardar e retornar a referência do State específico, sem a necessidade de fazer um cast. Então, para definir os agentes do sistema, a classe CAgent deve ser expandida. Repare que não é possível instanciar diretamente as classes derivadas de Agent, os dois métodos usados para isso (o construtor e o createAgent) não são públicos. A criação de objetos dessas classes é feita pela classe MASS (a camada), como será visto mais adiante. O método createAgent recebe como um de seus parâmetros o AgentFactory específico do agente a ser instanciado. Isto é necessário pois este método não tem acesso direto aos construtores das classes derivadas, este acesso é feito através do método create da classe AgentFactory. Abaixo está o código do agente gato. Note que o estado correspondente (CatState) é passado como parâmetro ao template. A classe do agente rato é análogo e por isso não será mostrado.
Pela definição formal de agente, este é composto pelo valor do estado (neste caso, o CatState assume valores verdadeiro ou falso), pelo sítio (será visto mais tarde na construção da camada) e pelo tipo do agente que é representado pelo método getTypeName. Na verdade o tipo do agente não é somente uma thread, uma explicação melhor sobre isso será dado logo mais. Agora é hora de definir os campos. Abaixo está o cabeçalho da classe Field.
Para conseguir o comportamento desejado aos agentes, o gato emitirá um campo que que espanta o rato, e este emitirá um campo que atrai o gato. Nossa camada terá uma área de 10x10 sítios (100 sítios ao todo), portanto farei os campos difundirem em um raio de 4 sítios de distância. Segue abaixo o código do campo do gato, que espanta o rato. O campo do rato é análogo.
Voltando um pouco para a classe Agent. O tipo do agente não é somente uma string (lembre-se da definição 9), nesta implementação este conceito está integrado na própria classe Agent e no mecanismo de hierarquia de classes da Orientação a Objetos. Na sua definição formal temos a função percepção que é um mapeamento do valor de estado atual para os coeficientes e limites de cada tipo de campo. Este mapeamento deve ser feito pelo usuário manualmente (pois depende da aplicação), e o local mais indicado para isso é no própio construtor. Dito isto e tendo as implementações dos campos, os códigos do construtor do CatAgent e do MouseAgent podem ser revelados.
Ainda sobre o tipo de agente, na sua definição foi dito que um agente consegue perceber um campo se e somente se Comparari (ciτ(s) • wfi, tiτ(s)) = True. Baseado nisso, foi criado o método valuePerceivedByAgent que retorna o valor do campo multiplicado pelo coeficiente correspondente se o agente conseguir sentir o campo, ou retorna zero (nulo) caso contrário. Sempre que um agente precisar consultar o valor de um campo, ele usará este método. Abaixo segue o código que foi omitido anteriormente.
Até agora não definimos nenhuma ação. A classe campo não é uma ação em si, mas é uma parte importante da emissão. Tanto a ação emitir quanto a ação caminhar não precisam ser estendidas. Mas a classe Reaction deverá ser derivada para criar a ação do gato agarrando o rato quando este for alcançado. Antes disso, será mostrado o código da classe Action, ancestral de Reaction.
Lembre-se que todo campo de uma classe tem seu respectivo métodos get e alguns tem set. A classe Action é a base para todas as ações do sistema. Segue abaixo a classe Reaction.
Parar criar uma reação é preciso estender a classe CReaction e implementar o método getIdentifier e o método act que descreve o que esta reação faz. O motivo da criação da classe CReaction é a mesma da existência da classe CAgent, a reação também precisa ter acesso à classe específica do estado (como pode ser visto no método act). Abaixo está o código da reação do gato quando alcança o rato. Esta reação muda o estado do gato para refletir sua conquista.
O rato deve ter uma reação para responder à reação do gato. Segue abaixo o código dela.
Agora o método agreeReaction dos dois agentes podem ser revelado. Este método foi visto na seção da thread do ambiente, ele é usado para perguntar aos agentes se eles aceitam participar de uma dada reação. O agente rato nunca quer reagir com um gato e portanto a resposta dada pelo gato não importa, faremos ele sempre responder negativamente para as reações pois ele deve responder algo. No caso do rato, ele é obrigado a responder positivo para a reação do gato, as reações de outros tipos de agentes serão negadas. O código do método para os dois agentes segue abaixo.
Como sabemos que só existem o gato e o rato neste exemplo, seria mais fácil o rato simplesmente aceitar qualquer reação, mas para ilustrar melhor o uso do MMASS o método foi implementado deste modo. Agora que todas as classes necessárias estão definidas, o método selectAction pode ser mostrado. Este método foi visto na seção da thread do agente, ele é usado para os agentes escolher alguma ação baseado no contexto local. Neste exemplo, o comportamento dos agentes exige que eles estejam emitindo campo continuamente ao mesmo tempo que caminham, no MMASS isso não é possível, somente uma ação por turno é realizada. Por isso faremos com que dois turnos do MMASS sejam um turno para o rato e para o gato, desse modo é possível realizar as duas ações "ao mesmo tempo". Então, em todo turno par os agentes emitem o campo, em turno impar os agentes caminham ou reagem. Segue abaixo o método do gato.
O método do rato é parecido e não será mostrado. A primeira fase (definição das classes) encerra-se aqui. A segunda fase começa com a construção das camadas. Para este exemplo, será construído apenas uma camada de 10x10 sítios. Cada sítio deve ter um nome, neste exemplo os nomes serão as coordenadas deles, por exemplo, o sítio "1x1" é um canto do mapa e o "10x10" está no canto oposto ao sítio anterior, assim como os sítios "1x10" e "10x1" também estão em cantos opostos. Antes de mostrar o código é preciso saber que existe somente uma instância da classe MMASS. Outro aspecto importante é a criação dos objetos. Em geral, um objeto A é criado pelo objeto B que contém A, por exemplo, um Space possui um conjunto de sítios, então um Site é criado pelo objeto Space e este Site pertencerá ao espaço que o criou. Veja o código da criação da camada abaixo.
Agora que a camada está construída, os agentes podem ser posicionados. Lembrando que só foi possível finalizar o espaço porque os sítios formaram um grafo conexo, caso contrário o método finish soltaria uma exceção. Agora os agentes serão colocados a uma distância de 3 sítios um do outro para conseguirem detectar suas presenças.
O MASS pôde ser finalizado porque seu espaço está finalizado e ele possui no mínimo um agente e todos eles estão posicionados em algum sítio. Resta agora finalizar e iniciar o MMASS. Veja o código abaixo.
O MMASS foi finalizado com sucesso porque todas as camadas estão finalizadas (minha implementação não aproveita a característica de multicamadas do MMASS, então a classe Interface não foi implementada e por isso o MMASS não checa se todas as camadas estão interligadas como diz a definição 6). Caso contrário método finish soltaria uma exceção. O método initiate cria e inicia todas as threads (dos agentes e do ambiente). A classe MMASS dá acesso à thread do ambiente (a estrutura pthread_t da biblioteca Pthread), e assim é possível esperar pelo encerramento dela usando o método pthread_join. Para encerrar o sistema basta ligar a flag finish_thread da classe MMASS. O usuário não precisa se preocupar com as threads dos agentes, pois a própria thread do ambiente encerra e espera pela finalização dos agentes. Aqui encerra a seção sobre o MMASS. Com o framework pronto o próximo passo é integrar este sistema com a parte gráfica, este é o assunto da próxima seção. Integração com a parte gráfica [índice]Para a parte gráfica deste projeto utilizei a Ogre, acrônimo de Object-Oriented Graphics Rendering Engine. Este renderizador é relativamente fácil de ser usado, é bem documentado, e possui uma comunidade grande e ativa de usuários, e essas características me levaram a escolhê-lo para a aplicação neste projeto. Ao contrário das outras bibliotecas usadas, não farei uma introdução sobre a Ogre aqui, pois não será necessário para entender esta seção. Até o momento em que esta monografia foi escrita. O projeto se encontrava nesta fase. A integração da parte gráfica com o MMASS expôs algumas falhas de projeto do framework, que do ponto de vista do trabalho é interessante mostrá-los. Falhas de projeto [índice]Na primeira tentativa de integrar a Ogre e o MMASS ficou claro que implementar o MMASS como um programa multithread não foi uma boa escolha. Fazendo um teste com dois agentes, totalizando quatro threads (dois do agente, um do ambiente e um do renderizador), o resultado foi que um turno demorava alguns segundos para passar (ou seja, os agentes demoravam segundos para andar de um sítio para o outro, por exemplo), e o desempenho do renderizador era afetado drasticamente (ou seja, a animação era "quebrada", ou era gerada a menos de 25 quadros por segundo). Resolver este problema foi fácil. Com a versão multithread implementada, basta modificá-la de forma a seguir a sequência esperada que as threads tomassem para que o sistema avançasse de turno. Não vou mostrar o código modificado aqui, o mais importante é entender como o mecanismo funciona e tanto a versão multithread quanto a versão sequencial seguem este mesmo mecanismo. O resultado da modificação foi o esperado. Com o mesmo exemplo de dois agentes, agora totalizando duas threads (um do renderizador e outro para todo o MMASS), o resultado foi uma animação suave e os turnos demoram bem menos para passarem. Porém, ainda há um problema relacionada com threads que será comentada mais adiante. Obs.: Até o momento que esta monografia foi escrita, o projeto se encontrava neste ponto. Os problemas comentados abaixo ainda não foram corrigidos. Outro problema é o consumo de memória. O consumo alto já era esperado e o leitor pode ter percebido isso na seção anterior. Na classe Site, foi dito que um sítio guarda a distância dele para todos os outros sítios, ou seja, se um sistema é formado por n sítios, então cada um guarda n - 1 distâncias o que nos dá um consumo de memória de ordem quadrática. Em um exemplo com um mapa de 35x35 sítios (1225 sítios), que não é um ambiente grande para um jogo, foi consumido toda minha memória (de 1024mb). Resolver este problema também não é difícil. Basta que as distâncias sejam sempre calculadas na momento que for necessário, dessa forma não é necessário guardá-las. Porém, em um sistema onde as distâncias precisam ser consultadas constantemente isso pode não ser viável e uma solução intermediária deve ser adotada, como por exemplo, guardar as distâncias calculadas temporariamente. Temos aqui o velho trade-off da eficiência vs. memória. Foi dito agora a pouco que o sistema é formado por duas threads. A thread principal é o renderizador, e este cria uma thread separada para executar o MMASS concorrentemente, o principal motivo desta decisão é que o renderizador não pode parar para esperar o MMASS atualizar os agentes. Mas sincronizar estas duas threads não é simples. O renderizador possui um looping como o pseudo-código mostrado abaixo.
Uma iteração corresponde a um quadro da animação, mas um quadro não representa um turno do MMASS, por isso este não pode ser atualizado sempre. O problema é saber quando que os agentes devem ser atualizados, e mesmo assim a thread do MMASS pode demorar a ser executada depois de ser sinalizada para atualizar. O resultado dessa dessincronização é uma ligeira pausa entre os turnos dos agentes. Outra alternativa é fazer a integração integração de forma que o programa final não seja multithread. Isso certamente causará uma queda na performance do renderizador devido às pausas de atualização, mas mesmo assim é uma alternativa a ser considerada. No link abaixo há um vídeo do resultado atual do projeto. Uma bola azul é um agente que emite um campo que espanta os outros agentes. Repare nas pausas no movimento dos agentes, fruto da falha de sincronização entre as threads. VídeoO código fonte do trabalho até o presente momento está no link abaixo. Código-fonteConclusões [índice]As definições formais são uma abstração do framework no sentido de que a partir dessas definições podemos concretizar nossa própria implementação em diferentes domínios, por exemplo, o MMASS pode ser aplicado em jogos e portanto a implementação será um programa de computador, ou o sistema pode ser aplicado para distribuir informações para computadores móveis e portanto ele não será somente um software. Além disso, as definições e os pseudo-códigos consegue descrever o MMASS com um bom nível de detalhes. Portanto, para um desenvolvedor seguindo o paradigma de programação orientada a objeto, o trabalho do Vizzari poupa bastante esforço para projetar uma implementação própria. Neste sentido o trabalho do Vizzari é ótimo, uma boa parte do trabalho discute diversas possibilidades de implementação. Porém, na minha opinião, faltou detalhar mais sobre a sincronização entre as threads (dos agentes e do ambiente) no caso síncrono. Por este motivo e pelo fato do meu trabalho ser uma implementação concreta, neste trabalho procurei mostrar com um pouco mais de detalhe como faço a sincronização. A utilização do MMASS em jogos é uma boa idéia. Neles são comum um grupo de agentes ter a necessidade de agir em conjunto para alcançar um objetivo, por exemplo, policiais agem como um time para invadir uma base de terroristas. Três fatores torna o framework adequado para este tipo de aplicação: a sua flexibilidade, a facilidade de definir o sistema multiagente, para isso basta definir os agentes e suas ações, e a separação do agente e do gerenciamento das ações. Na prática, a viabilidade de sua implementação depende da disponibilidade de alguns recursos como a quantidade de memória e do tempo de processamento (pensando no caso de um software multithread, o renderizador de um jogo deve ter prioridade sobre outras threads, então o tempo que sobra para o MMASS fazer suas operações é suficiente para atualizar os agentes e ter o resultado desejado?). Apesar do estudo de MASs ser uma área de IA, projetar um MAS é uma tarefa multidisciplinar. Neste sentido acho que este foi um ótimo trabalho de formatura, pois pude encontrar vários conceitos estudados durante todo o curso tanto na parte do estudo sobre o MMASS quanto na parte da implementação. Desafios e frustrações [índice]C++Como aluno do IME, eu me acostumei a programar em Java. No começo das atividades de programação deste trabalho foi difícil a "transição" de Java para C++. A principal dificuldade é lembrar que nem todas as variáveis são referências para um objeto, e por causa disso é preciso sempre ter em mente conceitos como bitcopy vs. inicialização, passagem de parâmetro por valor vs. passagem de parâmetro por referência, copy-constructor, etc [2]. Além disso, como C++ não tem coletor de lixo, o fato de ter que liberar memória manualmente afeta um pouco no projeto de uma classe. Se um objeto A guarda um apontador para outro objeto B, devemos decidir se o dono da referência (apontador) é o usuário da classe A ou a própria classe A, ou seja, decidir quem é responsável por liberar a memória de B depois que este não é mais necessário. (Na verdade, usei apontadores inteligentes da biblioteca Boost que resolveu o problema de liberação manual da memória, mas não resolveu o problema de decidir quem é o dono da referência.) Por outro lado, a experiência com C++ me fez refletir um pouco sobre os motivos do IME adotar Java (e o curso de POO adotar o Smalltalk). Acredito que para fins didáticos Java é mais adequado do que C++. Visual do exemplo (modelagem)Este assunto não está relacionado com o curso de computação, mas foi algo que me frustrou. Eu realmente queria fazer um exemplo mais bonito, porém a falta de conhecimento e de prática com algum programa de modelagem 3D me impediram de conseguir um exemplo vistoso. Programação concorrenteFazer a sincronização entre as threads foi difícil. Não é possível criar testes unitários para ter segurança de que o comportamento das threads será como o esperado. Também é difícil de encontrar o erro quando algo errado acontece. Neste trabalho usei muitas impressões (printfs em arquivos no formato html para facilitar a vizualização) para acompanhar o comportamento das threads. No caso síncrono (que é o caso deste trabalho) o trabalho do Vizzari não dá muitos detalhes sobre a sincronização entre as threads, o que também dificultou nesta parte da implementação. Matérias relevantes [índice]Foram muitas matérias que me ajudaram diretamente na realização deste trabalho. A começar por Inteligência Artificial, o MMASS é relacionado a esta área e os conceitos desta matéria foram importante para entender o artigo [1]. As matérias Análise de algoritmos e Linguagens formais e autômatos ajudaram a entender alguns exemplos do artigo. Programação em redes de computadores também ajudou a entender algumas colocações no artigo sobre a comunicação entre os agentes. É difícil não citar Introdução à Computação e Princípios de Desenvolvimento de Algoritmos em um trabalho que envolveu programação. Algoritmos em grafos e Programação concorrente foram importantes tanto para compreender o MMASS como para implementá-lo. Este sistema faz uso intensivo de algoritmos como busca em largura e busca em profundidade, e por se tratar de um programa multithread foi necessário garantir exclusão mútua em seções críticas e sincronização entre as threads. Laboratório de programação II por ter ensinado conceitos básicos de POO, Programação orientada a objeto por ter ensinado conceitos avançados de POO, padrões e refatoração e o curso de Engenharia de software foram disciplinas que falaram sobre assuntos relacionados a projeto de software e me ajudaram a implementar o MMASS. Laboratório de programação extrema me ajudou com algumas práticas de programação como o teste a priori, integração continua, soluções simples, etc. Para aprender C++, a matéria de Conceitos de linguagens de programação foi importante para entender o livro [2], inclusive entender que muitas decisões do projeto da linguagem C++ priorizaram o desempenho. Também usei um pouco de Algebra Linear para manipular os agentes em um abiente 3D. A quantidade de matéria envolvidas diretamente com a realização deste trabalho mostra que os conceitos aprendidos durante o curso foram fundamentais. É gratificante pensar que consegui entender um trabalho de doutorado (apesar de eu ter a impressão que o trabalho não é difícil de entender) e todos os outros assuntos estudados, e também conseguir colocá-los em prática. Considero positivo a experiência adquirida por ter feito um sistema relativamente grande, algo que não foi muito comum durante o curso de Computação. Porém esta experiência poderia ter sido melhor se não fosse realizado sozinho, algo que eu deveria ter levado em consideração antes. Para me aprofundar no que foi envolvido neste projeto, acredito que poderia seguir dois caminhos. Um seria voltado para a parte teórica e seguiria estudando IA e MASs. O outro caminho seria voltado para a prática e estudaria mais sobre matérias relacionadas a construção e projeto de softwares, como O.O., Engenharia de Software, etc, e tentaria melhorar minha implementação para disponibilizá-lo à comunidade da Ogre. Agradecimentos [índice]Gostaria de agradecer ao professor Flávio, sem sua sugetão eu não saberia o que fazer como trabalho de formatura, certamente elaborar um trabalho foi um desafio. Ele também ajudou a me organizar para a realização desta tarefa. Além disso, participar da iniciação científica foi uma experiência muito boa. Ter escrito um pequeno artigo (não relacionado a este trabalho) e apresentado em um Simpósio foi algo novo para mim e, de certa forma, emocionante (fiquei nervosíssimo para apresentar). E graças a esta iniciação eu despertei novamente o intresse em estudar e, principalmente, ir atrás de um dos assuntos que me motivou a fazer o curso de Ciência da Computação, os jogos de computadores. Agradeço também aos meus colegas de faculdade por terem me suportado por 4/5 anos e terem ajudado a tornar mais agradável todos esses anos na faculdade. Também queria agradecer aos meus amigos por serem ótimos companheiros, e por terem ajudado de alguma forma a eu chegar até aqui. Em especial, gostaria de agradecer aos meus pais por terem me dado toda as condições (afetivo e fincanceiro) para eu me formar. Certamente, o meu diploma também é deles por terem se esforçado em dar uma educação de boa qualidade. Bibliografia [índice]
topo |