Desenvolvimento

Geração de labirinto aleatório

Inicialmente foi realizada uma busca para entender como um labirinto poderia ser gerado de forma completamente aleatória e coerente, desta pesquisa foi encontrada o método de busca em profundidade, onde é implementado um algoritmo de busca que visita todos os possíveis estados dentro do labirinto, ao se visitar a primeira vez um estado o algoritmo cria paredes ao redor deste estado, deixando livre apenas um caminho, caso o estado já tenha sido visitado nada ocorre, o programa roda até que todos os estados já tenham sido visitados, o algoritmo tem por precaução nunca formar um loop de caminhos abertos, pois isso pode fazer com que o labirinto acabe virando apenas um bloco em branco sem paredes. Nesta pesquisa foi encontrado um algoritmo em python que realizava a criação deste labirinto de forma coerente e mostrava a imagem do labirinto em arte ascII.

É visível  que o código gera +- para representar paredes horizontais e  |  para representar as paredes verticais, assim como usa espaços vazios para representar os caminhos livres, era necessário chegar em um formato onde o labirinto fosse formado por uma matriz onde 0 representava parede e 1 representava caminho livre, para isso foi necessário se aprofundar mais neste algoritmo de geração. Nos testes feitos pode ser observado que durante o processo de geração era criada uma matriz vis que continha a informação de quais células foram visitadas (0 se não visitada e 1 se visitada), e a função walk que fazia a varredura no labirinto até que todas as células tenham sido visitadas (matriz vis = matriz de uns), eram geradas também duas listas, uma com os parâmetros das paredes verticais e outro com os parâmetros das paredes horizontais (ver e hor no código), e durante a montagem da imagem essas duas listas eram dispostas de forma intercalada, algo que é visível também na imagem apresentada, com isso em mente foi iniciado a alteração do código para gerar o labirinto no formato necessário, inicialmente era preciso fazer com que as paredes se transformassem em zeros e os caminhos livres em uns, para isso bastou alterar os caracteres de entrada dentro do próprio código base, e, foi necessário criar dois inputs para que o usuário fosse capaz de escolher a dimensão do labirinto, como os dados de dimensão eram w e h inicialmente, e eles estavam acessíveis, foi fácil realizar a mudança para os inputs de altura e largura, vale ressaltar que o código fonte gerava uma matriz com o dobro do tamanho descrito por w e h, por isso a altura e a largura foram divididas por 2, como resultado temos o algoritmo abaixo:

A imagem acima representa o que era necessário se obter, entretanto, o algoritmo não gera uma matriz, e sim uma lista hor após uma lista ver várias vezes, apenas colocando uma quebra de linha entre elas, para o próximo passo era preciso tornar esta resposta uma matriz, então o processo realizado foi o de separar cada caractere dentro das listas e concatená-los de forma que formassem as colunas da matriz, e de forma similar foi feito um processo em que ao se chegar ao final de uma lista, usa-se a  função append para reiniciar o processo dos caracteres em uma nova linha dentro da matriz, este processo é feito de forma intercalada entre hor e ver até que se chegue ao final da matriz, um problema que ocorreu ao dividir os valores de dimensões da matriz por 2, foi acabar removendo a última coluna zerada da matriz, para resolver este problema foi acionado uma borda forçada que é visível na imagem abaixo e utilizada posteriormente.

Outro problema relacionado ao fato do valor da entrada ter que ser dividido por 2 para gerar o tamanho ideal de matriz para o usuário, foi a questão do somente ser possível gerar matriz com dimensões ímpares, por exemplo 7x7, fazendo com que quando o usuário tentar alocar uma matriz de dimensão 8x8 o código irá gerar uma matriz 9x9.

Este código gerador de labirintos gera nativamente apenas um único caminho entre a entrada e a saída do labirinto, idealmente para uma boa análise do agente deve-se ter no mínimo dois possíveis caminhos até a saída, para que desta forma o agente tenha a possibilidade de encontrar o melhor caminho até a saída ao invés de apenas a saída do labirinto. Para tornar possível a existência de, no mínimo, um caminho alternativo até a saída foi implementado um algoritmo onde se era visitado uma posição aleatória do labirinto, e caso esta posição se constituí como parede, e atendesse a alguns critério (para evitar a criação de salões vazios no labirinto), esta parede seria quebrada. O número de paredes que serão quebradas no labirinto varia com a dimensão do labirinto, e o algoritmo que constitui esta parte está abaixo.

Com a parcela do código vinculada à geração de labirintos já implementada, ao utilizar uma biblioteca conhecida como matplotlib, que serve para trabalhar com gráficos, podemos realizar uma visualização 2D da matriz, considerando uma cor para parede e outra para caminho livre, desta forma, a matriz "binária", pode ser visualizada de forma a se parecer de fato com um labirinto em duas dimensões (a célula em azul representa o início do labirinto e em verde o final do mesmo):

Desenvolvimento de funções auxiliares

Uma função de suma importância para o funcionamento é a função que efetua a ação de ler os sensores do agente, isso é feito observando as posições ao redor do agente. Para observar as posições o código verifica se as colunas laterais (D, E) são compostas por parede ou caminho livre, assim como verifica a linha acima ou abaixo do agente (F, dependendo do seu sentido). tendo estes dados o agente recebe uma lista contendo as possibilidades de caminhos livres, fazendo com que ele esteja apto a definir um novo sentido. Observe que desta forma não há como o agente tentar se locomover pelas paredes, já que só é possível a movimentação pelos caminhos livres, isso faz com que o agente não tenha que aprender que  não deve se  jogar contra a parede, apesar de que na matriz Q, as paredes são denotadas como valor -inf, reforçando a não possibilidade do agente atravessar paredes. Esta parcela do código também gera  sentidos auxiliares para caso todas as leituras derem 0, neste caso o agente se encontra em um beco sem saída, onde a única  possibilidade é ele voltar por onde entrou, desta forma o sentido auxiliar gera um novo sentido exatamente oposto ao atual, para que ele possa retornar, já que não há possibilidade do agente andar de costas.

A partir deste ponto se iniciou a escrita dos códigos que iriam auxiliar o algoritmo Q-learning, como os códigos que seriam usados para verificar o estado em que o agente se encontra, possibilitando sua locomoção pelo labirinto, este código está descrito abaixo, assim como o código que posteriormente servirá como base para realizar a montagem do mapa de política do agente, este código inicialmente cria uma matriz direções onde todas as posições são descritas com "o" e ao passo que o agente aprende, esta matriz é atualizada com as decisões que o agente tomou (c, b, d, e).

A seguir temos mais algumas funções que tem serventia de encontrar as possíveis próximas direções que o agente tem para seguir, assim como temos a função que opera a ação de encontrar a posição em que o agente está dentro do labirinto (descrita como 2 dentro da matriz). Outra função descrita abaixo é a função que define o próximo sentido que será adotado para o agente, já que seus sensores trabalham com 3 direções (F, E ,D), a cada mudança de rumo, é determinado um novo sentido para que o agente possa se orientar como sendo sua frente (F).

Outra função vital para o funcionamento do sistema é a função que torna possível a locomoção do agente pelo labirinto, como descrito anteriormente, a posição do agente na matriz é descrita como o local na matriz que contém o valor 2, desta forma para que o agente se locomova pelo labirinto, é necessário que o valor 2 se locomova pela matriz, isso é feito definindo os movimentos na linha e na coluna atual do agente, com base no sentido atual que o agente está adotando, desta forma podendo verificar a direções futuras possíveis, de forma complementar, a matriz maux, representa uma matriz com as mesmas dimensões da matriz labirinto, onde existe apenas um único valor 1 que é alocado na exata posição atual do agente no labirinto, e esta matriz é uma matriz auxiliar para definir a posição do a gente, esta parcela de código, faz com que a posição passada do agente se torne 0 na matriz maux, e a posição futura se torne 1 nesta mesma matriz, assim fazendo com que o agente ande um passo, o processo se repete à medida que o agente se locomove pelo labirinto.

Para o funcionamento do Q-learning, é necessária uma função que tem por objetivo  buscar a ação que irá levar ao maior valor de recompensa possível dentro das ações possíveis estipuladas (uma valor da linha da matriz Q), caso duas ações cheguem ao mesmo valor de  recompensa, uma escolha aleatória será feita para que o agente possa tomar uma das duas melhores ações possíveis.

Aplicação de treinamento ao agente

Para a etapa de treinamento inicialmente são configurados os parâmetros necessários para a implementação, neste estágio é definido onde será a posição inicial do agente e a saída do labirinto (parâmetros fixos). Alguns parâmetros referentes ao treinamento ficaram disponíveis para o usuário configurar, parâmetros como o número de épocas que o agente irá treinar (números de vezes que o agente irá sair do labirinto), assim como a taxa de exploração do agente, esta taxa define o quanto o agente irá seguir a política gulosa, onde ele tenta ao máximo priorizar as recompensas imediatas, ao invés de considerar a recompensa global. Nesta etapa também são criadas algumas matrizes auxiliares, como a própria matriz maux (citada anteriormente), assim como também é criada a matriz Q, onde sua dimensão é dada pela dimensão total da matriz labirinto, pela quantidade de ações possíveis, por exemplo, se temos um labirinto de 10x10, a matriz Q terá de 100 linhas e 4 colunas, já que temos apenas 4 possíveis estados. A imagem abaixo representa algumas operações que são feitas dentro da estrutura de laço que configura as épocas, nela são feitos os cálculos de tempo de treinamento, assim como se define o caminho escolhido pelo agente. Dentro desta estrutura de laço também está contida a estrutura que determina os passos do agente, e por sua vez o algoritmo Q-learning, esta estrutura será abordada posteriormente. Também é contido nesta etapa a inicialização da figura que ao finalizar o treinamento do agente, gera a representação em 2D do agente saindo pelo caminho em que ele acredita ser o melhor possível, esta figura é inicializada durante a penúltima época, e é atualizada a cada passo que o agente dá por esta época específica.

Contido dentro da estrutura de laço que configura as épocas, esta o condicional que opera cada passo do agente no labirinto, esta parcela do código faz com que o agente ande até encontrar a saída do labirinto, assim configurando uma única época. Esta etapa faz a leitura dos possíveis próximos passos, efetua o cálculo para definir se o agente seguirá o passo ótimo seguinte, ou se ele irá efetuar o desvio vinculado à taxa de exploração. Como dito anteriormente, nesta etapa também é apontada a posição do agente a cada passo na penúltima época, para que possa ser efetuada a visualização 2D do agente saindo do labirinto. E claro que nesta etapa também é alocada a função matemática que descreve o algoritmo Q-learning, onde ela observa o estado atual, e define um novo valor para este estado (1000 caso chegue a saída do labirinto e -100 por cada passo até lá), com base nas recompensas que esta escolha gerou até o momento (A fórmula está indicada na imagem abaixo). Alguns parâmetros para visualização posterior também são gerados dentro desta estrutura, parâmetros como o mapa de calor.

Desenvolvimento de janelas e parâmetros de comparação.

Para uma melhor facilidade de utilização do software, foram criadas janelas utilizando a biblioteca tkinter, onde se é possível realizar toda a entrada de dados necessários para a realização do treinamento de forma mais simples, sem ter que trabalhar diretamente com  o terminal do python, assim como foram criadas janelas também para a visualização das métricas. Estas janelas foram criadas para trabalharem de forma sequencial, onde inicialmente se pede as dimensões da matriz, em seguida os parâmetros de treinamento configuráveis (número de épocas e taxa de exploração), apresentando posteriormente o labirinto gerado, caso o labirinto seja considerado "bom", o usuário pode seguir com o treinamento de fato, e posteriormente, com a obtenção dos resultados, caso o usuário não goste do labirinto apresentado, ele será redirecionado à página inicial, onde poderá redefinir tudo novamente. O código que faz a criação das janelas está abaixo, tendo todas as janelas topologias similares com a representada: 

Para realizar um comparativo entre treinamentos, assim podendo verificar a funcionalidade dos parâmetros, foram criadas basicamente algumas medidas que poderiam ser usadas de base. Foi concluído que o tempo de treinamento era uma informação vital para contemplar os resultados, assim como o número de passos dados na primeira época (período onde o agente anda sem conhecimento sobre o labirinto) e número de passos dados na última época (período onde se espera que o agente dê o mínimo de passos possíveis). Outras duas funcionalidades que foram identificadas como complementares ao conjunto de dados resultantes, foram algo descrito como mapa de calor, onde as regiões mais quentes denotam que o agente passou por elas mais vezes, e, de forma dual, as regiões mais frias denotam uma frequência menor de passagens do agente. O mapa de calor é obtido somando o caminho escolhido pelo agente em cada época em uma matriz  auxiliar, onde posteriormente se utiliza a biblioteca matplotlib para gerar de fato o mapa de calor. A outra funcionalidade se trata do mapa de política, muito aplicado em trabalhos similares, ele se trata de uma imagem que representa a escolha que o agente faria em cada posição do labirinto em sua última época, este mapa denota o conhecimento do agente sobre o labirinto, de forma ideal o agente deve ser capaz de sair do labirinto de qualquer posição seguindo o mapa de política, esta forma ideal é chamada de política ótima. O mapa de política é obtido trocando os valores de direções gerados na matriz direções por setas, e mostrando o resultado em uma imagem, utilizando novamente a biblioteca matplotlib.

Download de arquivos de projeto: