o mesmo ambiente (por exemplo, a mesma rua) seria natural que ambos os agentes cooperassem um com o outro a fim de evitar conflitos (por exemplo, uma colis˜ao). J´a o comportamento de competi¸c˜ao poderia ser exemplificado como um cen´ario de jogo de Xadrez ou Damas, pois ambos os agentes tem o objetivo de ganhar a partida sobre o advers´ario.
Em um cen´ario onde existe o comportamento de competi¸c˜ao tamb´em pode ser empregado o com- portamento de coopera¸c˜ao, ou seja, dentre os diversos agentes que atuam sobre o ambiente, existem aqueles que est˜ao ligados cooperando em prol de um objetivo, e outros que tamb´em exercem a atividade de coopera¸c˜ao visando outro objetivo. No caso do jogo de Damas, por exemplo, poderia haver um conjunto de agentes trabalhando (cooperando) para ganhar a partida do advers´ario, que por sua vez, tamb´em poderia contar com diversos outros agentes.
Moulin e Chaib-Draa [34] evidenciam as caracter´ısticas que constituem vantagens significativas dos Sistemas Multiagente sobre um Sistema Monoagente, entre elas: maior eficiˆencia na resolu¸c˜ao de problemas; mais flexibilidade por possuir agentes de diferentes habilidades agrupados para resolver problemas; e aumento da seguran¸ca pela possibilidade de agentes assumirem responsabilidades de agentes que falham.
2.2
Aprendizagem por Refor¸co
Aprendizado por Refor¸co, ou simplesmente AR, ´e uma t´ecnica de aprendizado de m´aquina onde um agente aprende por sucessivas intera¸c˜oes em um ambiente dinˆamico [35]. Ele ´e respons´avel por selecionar poss´ıveis a¸c˜oes para uma determinada situa¸c˜ao apresentada pelo ambiente [36]. Por esse motivo os agentes da AR s˜ao caracterizados como autˆonomos.
A quest˜ao que envolve a AR ´e basicamente: como um agente autˆonomo que atua sobre um determinado ambiente pode aprender a escolher suas a¸c˜oes para alcan¸car seus objetivos? Este ´e um problema muito comum em tarefas como o controle de um robˆo remoto e aprender a jogar jogos de tabuleiros, como Damas. O agente atua sobre o ambiente recebendo sinais (refor¸co ou penalidade), atrav´es de uma fun¸c˜ao de recompensa, para definir a qualidade da sequˆencia de a¸c˜oes [37]. Por exemplo, em um jogo de tabuleiro como Damas, quando o agente consegue uma vit´oria ele receber´a uma recompensa positiva (maior que zero, por exemplo), caso perca o jogo sua recompensa ser´a negativa (menor que zero), mas se empatar sua atua¸c˜ao ser´a neutralizada (recompensa igual a zero, por exemplo) [38].
A importˆancia de se utilizar AR como t´ecnica de aprendizagem est´a diretamente ligada ao fato de se tentar obter uma pol´ıtica ´otima de a¸c˜oes. Tal pol´ıtica ´e representada pelo comportamento que o agente segue para alcan¸car o objetivo e pela maximiza¸c˜ao de alguma medida de refor¸co a longo prazo (globais) nos casos em que n˜ao se conhece, a priori, a fun¸c˜ao que modela esta pol´ıtica (fun¸c˜ao do agente-aprendiz). Um sistema t´ıpico de aprendizagem por refor¸co constitui-se, basicamente, de um agente interagindo em um ambiente via percep¸c˜ao e a¸c˜ao. O agente percebe as situa¸c˜oes dadas no ambiente (pelo menos parcialmente) e seleciona uma a¸c˜ao a ser executada
em consequˆencia de sua percep¸c˜ao. A a¸c˜ao executada muda, de alguma forma, o ambiente; e as mudan¸cas s˜ao comunicadas ao agente por um sinal de refor¸co [15].
Formalmente, o modelo de um sistema de aprendizagem por refor¸co consiste em [27]:
• um conjunto de vari´aveis de estado percebidas por um agente. As combina¸c˜oes de valores dessas vari´aveis formam o conjunto de estados discretos do agente (S);
• um conjunto de a¸c˜oes discretas, que escolhidas pelo agente mudam o estado do ambiente (A(s), onde s ǫ S);
• um conjunto de valores das transi¸c˜oes de estados (refor¸cos tipicamente entre [0,1]).
O objetivo do m´etodo de aprendizagem por refor¸co ´e fazer com que o agente escolha uma sequˆencia de a¸c˜oes que aumente a soma dos valores das transi¸c˜oes de estados, ou seja, ´e encontrar uma pol´ıtica, definida como um mapeamento de estados em a¸c˜oes que maximize as medidas de refor¸co acumuladas ao longo do tempo.
Dentre todos os algoritmos existentes para solucionar o problema da aprendizagem por refor¸co, este trabalho enfocar´a o algoritmo de Diferen¸cas Temporais (TD(λ)) de Sutton [27], descrito na subse¸c˜ao a seguir.
2.2.1 M´etodo das Diferen¸cas Temporais
As Diferen¸cas Temporais s˜ao capazes de utilizar o conhecimento pr´evio de ambientes parcialmente conhecidos para predizer o comportamento futuro. Aprender a predizer ´e uma das formas mais b´asicas e predominantes em aprendizagem. Alguns exemplos de cen´arios onde algu´em aprenderia a predizer seriam:
• avaliar se uma determinada disposi¸c˜ao de pe¸cas no tabuleiro de xadrez conduzir´a `a vit´oria; • se uma determinada forma¸c˜ao de nuvens acarretar´a em chuva;
• se para uma determinada condi¸c˜ao econˆomica de um pa´ıs, isto implicar´a em um aumento ou diminui¸c˜ao na bolsa de valores.
Os m´etodos TD(λ) s˜ao guiados pelo erro ou diferen¸ca entre predi¸c˜oes sucessivas tempor´arias de estados sequenciais experimentados por um agente em um dom´ınio, resultante de uma sequˆencia de a¸c˜oes (M0, ..., Mi−1, Mi, Mi+1, ..., Mt) que s˜ao executadas ao longo do tempo com o objetivo
de realizar uma tarefa para o qual foi projetado. Assim, o aprendizado do agente pelo m´etodo TD(λ) ´e extra´ıdo de forma incremental, diretamente da experiˆencia desse agente sobre o dom´ınio de atua¸c˜ao, atualizando as estimativas a cada passo, sem a necessidade de ter que alcan¸car o estado final de um epis´odio (um epis´odio pode ser definido como sendo um ´unico estado ou uma sequˆencia de estados de um dom´ınio) [15], [20].
2.3. Clusteriza¸c˜ao 13