Encontrei esse trabalho realizado por mim durante a minha graduação, e resolvi compartilhá-lo aqui para relembrar meus primeiros passos nesse longo caminho da pesquisa e desenvolvimento no campo dos sistemas inteligentes.
Resumo
O presente artigo apresenta o desenvolvimento de um simulador de navegação autônoma de robôs, que utiliza algoritmos evolutivos como treinamento. O trabalho apresenta os temas de computação natural, algoritmos evolutivos e navegação autônoma, aplicados no treinamento de navegação nos robôs simulados, eliminando a necessidade de um robô físico. Ao final, após os testes, são apresentados gráficos que comprovam o funcionamento do software e do algoritmo proposto. Levando em conta que os recursos obtidos com o projeto, venham a ser usados nas mais diversas áreas além da robótica autônoma, como no desenvolvimento de jogos com agentes mais inteligentes.
1. Introdução
Este projeto envolve assuntos como Computação Evolutiva (CE), Algoritmos Evolutivos (AEs), Navegação Autônoma (NA), e suas aplicações em simulações e robótica.
A CE é um conceito que abrange várias áreas, se baseando na biologia para buscar variadas soluções para um determinado problema, podendo obter uma maior variação de resultados eficientes, porém sem a garantia de uma solução ótima (ZUBEN, 2000).
Os AEs ou algoritmos genéticos (AG) como também são conhecidos, são baseados na teoria da evolução de Charles Darwin. Sua principal função é utilizar esse conceito para gerar variadas soluções candidatas para um determinado problema. Primeiramente é gerada uma população aleatória, que será testada em um ambiente, essa população é composta por indivíduos, que possuem cromossomos, esses carregam uma representação das possíveis soluções. Os cromossomos são avaliados e recebem um valor de aptidão (fitness), indicando a qualidade da solução. O melhor indivíduo, ou um grupo com os melhores é selecionado com base em suas pontuações. Então são aplicados os operadores evolutivos como crossover e mutação, gerando assim novos cromossomos, novas soluções candidatas que novamente serão testadas no ambiente, avaliadas, e assim todo o processo se repete, com a intuição de a cada geração, gerar novas soluções cada vez mais aptas a solucionar o problema proposto.
Uma visão atual da sociedade, sobre a aplicação da robótica, é a substituição de humanos por robôs em trabalhos que coloquem em risco a vida humana, ou atividades em que o ser humano não é capaz de realizar de forma eficiente (PESSIN, et Al, 2007).
O estudo na área de robótica móvel vem se mostrando um tema bastante relevante, já que tem ocorrido grande crescimento em sua área nas últimas décadas. As aplicações de robôs móveis além de promissoras, abrangem uma grande variedade de áreas, desde aplicações domésticas em aspiradores de pó e cortadores de grama, até em indústrias, áreas urbanas, militares e na segurança e defesa civil e militar (WOLF, et Al, 2009).
Na área de robótica móvel, a NA propõe que o robô aprenda a se locomover por um determinado ambiente sem colidir, e completar determinada função da melhor forma possível. Nesse ambiente a máquina deve ser capaz de sintetizar suas próprias escolhas, proporcionando um comportamento mais adequado de acordo com a situação presente (CRESTANI; FIGUEIREDO; ZUBEN, 2001).
Uma das formas de aplicação de navegação autônoma em robôs é utilizando o aprendizado de máquina, que pode ser implementado com algoritmos de inteligência artificial ou AE. Porém esse processo de treinamento do robô, pode ser demorado e custoso, pois muitas vezes o tempo e a quantidade de robôs é curto o que causa uma menor variabilidade genética e um menor número de possíveis soluções.
A proposta de uso de um simulador para aplicar esse treinamento em robôs é dada para eliminar os fatores negativos como a demora, e outras dificuldades que podem ocorrer ao se tratar de um robô físico. Além disso, outra vantagem de um simulador é a não necessidade de aplicação direta em um robô real, evitando possíveis riscos ao operador e /ou desgastes do equipamento (HOSS; HOUNSELL; LEAL, 2009). Com isso é proposto neste trabalho o desenvolvimento de um sistema, simulador de navegação autônoma de robôs, utilizando um algoritmo evolutivo para o aprendizado dos robôs.
2. Revisão Bibliográfica
No trabalho de (REIS, 2002), o autor desenvolveu um agente que foi simulado em um ambiente com o objetivo de encontrar o melhor caminho, ou o caminho mais rápido, para um determinado ponto. Esse agente foi utilizado e testado em uma competição onde se classificou em segundo lugar, confirmando sua eficiência. O artigo critica alguns pontos, como a forma de avaliação e aplicação da competição, já que a mesma tem um certo peso científico, por ser usada como forma de teste e comprovação de eficiência para muitos trabalhos. Um diferencial desse trabalho com o proposto é o não uso de um algoritmo evolutivo, e o fato da possibilidade de uma intervenção direta humana.
O objetivo do trabalho (PESSIN, et Al, 2007) é o desenvolvimento de um ambiente de simulação para aplicação de treinamento de robôs combatentes de incêndio florestais, onde o ambiente simulado representa as florestas. Os robôs devem se mover por esse ambiente, que apresenta diversas características realísticas, como terrenos irregulares, restrições físicas entre outras. Além desse trabalho também não utilizar algoritmos evolutivos no treinamento dos robôs, é um sistema próprio, que só pode ser utilizado para uma única finalidade.
O trabalho de (SALVATO; CROCOMO, 2015), tem como objetivo a criação de um simulador 3D capaz de gerar diferentes ambientes para a aplicação de simulações de vida artificial. Neste trabalho é criado um método automático de geração de ambientes, e os algoritmos evolutivos são aplicados em criaturas artificiais, que são simuladas e avaliadas em diversos ambientes. Diferente do trabalho aqui proposto, esse é um trabalho voltado à simulação de vida artificial, e não tem ligações com robótica e navegação, mas é um excelente exemplo de simulação e aplicação de algoritmos evolutivos para obter melhores soluções.
Em (GONZALEZ; MAREGONI, 2005) é possível observar uma aplicação diferente para os algoritmos genéticos ainda na área da robótica, aqui a aplicação está no controle da movimentação de um braço robótico móvel. A solução apresentada deve definir o tempo e a direção que cada motor presente no braço devem ser ativados, além disso, diminuir o consumo de energia de seus movimentos.
3. Objetivos
O objetivo deste trabalho é o desenvolvimento de um ambiente de simulação para testes de algoritmos evolutivos aplicados à navegação autônoma de robôs. O software será disponibilizado em uma página web e poderá ser baixado gratuitamente, seu público alvo são estudantes e pesquisadores que realizam pesquisas e trabalhos relacionados à navegação autônoma de robôs utilizando algoritmos evolutivos.
O foco do trabalho é testar a funcionalidade do algoritmo evolutivo, como um meio de aprendizado para que as populações de robôs sejam capazes de se adaptar e aprender a navegar por um ambiente, e cumprir suas tarefas da melhor forma possível sem uma intervenção humana direta, e sem a necessidade de possuir ou testar diretamente em um robô físico. Assim é esperado que esse trabalho contribua com pesquisas realizadas na área de simulação de navegação autônoma e de algoritmos evolutivos. Com isso, será construído um simulador computacional com gráficos 3D para uma melhor visualização do funcionamento, e um modo sem gráficos para que o algoritmo possa ser testado de forma mais rápida e eficiente.
4. Metodologia
Para o desenvolvimento da simulação proposta foi utilizado o motor gráfico Unity 3D (UNITY, 2016). O Unity é um motor desenvolvido para o desenvolvimento de jogos, sua principal finalidade é facilitar e agilizar o desenvolvimento, o mesmo possui toda física que uma simulação 3D precisa já implementada, trabalha com objetos de uma forma direta e possibilita programar nas linguagens C#, Javascript e Lua.
Para o aprendizado e adaptação dos robôs no ambiente está sendo utilizado um Algoritmo Evolutivo (AE). Os AE são baseados na teoria da evolução de Charles Darwin, onde em uma geração são simulados ou “treinados” uma quantidade de robôs, aqueles que marcarem a maior quantidade de pontos executando da melhor forma seus objetivos, serão considerados os indivíduos “pai”. Quando a simulação de sua geração terminar, seu cromossomo será cruzado com o de todos os outros indivíduos de sua espécie ou tipo naquela geração, o que irá gerar novos cromossomos de novos indivíduos, que poderão sofrer mutações ou não e assim gerar os robôs da nova geração. Essa nova geração, novamente será simulada, e assim segue até atingirem um resultado específico ou por quanto tempo for determinado, a Figura 1 ilustra o funcionamento do algoritmo evolutivo implementado no software proposto.
Figura 1: Diagrama do funcionamento de um algoritmo evolutivo
Primeiramente foi implementado o mapa, onde toda vez que uma simulação é iniciada, um novo mapa em modo de código é gerado. A geração do mapa é de modo completamente aleatório, onde em uma matriz são armazenados os dados dos objetos presentes no mapa em cada posição, por exemplo, as posições com o valor 0, estão vazias, as posições com valor 10 possuem uma parede, os valores 50 e 100 representam dois tipos de pedras distintas e os valores 1000 e 50000 representam os robôs coletores e os robôs perseguidores respectivamente, como ilustra a Tabela 1.
Tabela 1: Representação dos objetos em mapa, de forma numérica
Esse método foi adotado para facilitar a distinção de quais objetos estão em um mesmo espaço caso isso ocorra, já que os robôs são capazes de se movimentar pelo ambiente. As principais regras de navegação dos robôs pelo mapa são:
Ambos os robôs não podem atravessar paredes ou ficar no mesmo espaço que a parede.
Se um robô coletor estiver na mesma posição que uma pedra do tipo 2, a pedra é coletada e o robô recebe um ponto de fitness.
A Tabela 2 ilustra as possíveis situações descritas e as reações levadas a acontecer, onde P é a posição da matriz, Tr é o valor que representa o tipo de robô, Fr representa o fitness dos robôs e Pr a posição dos robôs.
Tabela 2: Possíveis situações e reações
Os valores e situações ilustrados anteriormente, são muito simples e exatas, existindo a possibilidade de haver situações mais complexas como mais de dois objetos em uma mesma posição, por isso, foram criados tratamentos que fazem as regras ainda serem válidas da melhor forma possível, evitando um conflito.
Os primeiros robôs, ou seja os presentes na primeira geração da simulação, são criados completamente aleatoriamente, primeiramente é definido seu tipo, coletor (1000) ou perseguidor (50000), são criados a mesma quantia de ambos os robôs, em seguida são gerados os dados presentes no cromossomo de cada robô. Os cromossomos são representados por um vetor de 10 posições, cada posição equivale a uma situação, ou a um ambiente em que o robô se encontra, a Figura 2 representa o cromossomo do robô.
Figura 2: Representação do cromossomo
Cada posição do cromossomo pode receber valores de 0 a 4, onde cada valor representa uma ação a ser tomada pelo robô, como mostra a Tabela 3. O cromossomo é chamado dependendo da visão do robô, o valor da visão é o que definirá qual posição do cromossomo será lido. O valor do cromossomo é o que definirá qual ação será realizada pelo robô, e logo após a ação ser concluída, o código verifica o valor total da posição e causa uma reação, como ilustrado anteriormente na Tabela 2.
Tabela 3: Códigos das possíveis ações
Após a simulação ser iniciada os robôs iniciais ficarão percorrendo o ambiente com seus valores aleatórios por um determinado tempo. Esse tempo é definido pelo número de ações executadas pelos robôs, sendo o padrão 100 ações, com o término desse tempo, a simulação é parada e são realizadas as etapas de contagem de fitness (seleção do pai), crossover (cruzamento), mutação e os novos cromossomos gerados são inseridos em robôs que serão novamente simulados e testados no ambiente na próxima geração, e assim segue sucessivamente.
O fitness de cada robô é implementado e decrementado durante a simulação, conforme suas ações, ao final os fitness de todos os robôs serão comparados e o melhor de cada tipo de robô se tornará o “pai”. Parte de seu cromossomo irá para todos os robôs do seu tipo, junto com parte de seus cromossomos anteriores, essa distribuição se dá com 50% de chance do novo cromossomo herdar o pai ou o próprio valor, valendo para todas as posições do cromossomo. Após o crossover acontece a mutação, onde seguindo a ideia anterior, existe 3% de chance de ocorrer uma mutação aleatória em uma posição do cromossomo, a Figura 3 ilustra esse processo.
Figura 3: Exemplo de crossover e mutação
O sistema salva os dados referentes aos fitness de cada geração em arquivo .txt para comparação, estudo e uma melhor observação da evolução e adaptação dos robôs ao ambiente e a suas tarefas.
Outra função muito importante do software é o modo visual da simulação, ou seja, a possibilidade de ativar o modo gráfico. Com imagens 3D, é possível observar como os robôs estão agindo dentro do mapa utilizando os cromossomos da geração atual.
Para ativar o modo gráfico da simulação basta pressionar o botão “Lig/Des Gráficos” na tela do sistema. Assim que o comando é dado, a simulação com ênfase em treinar e evoluir os robôs é pausada, o mapa 3D é gerado e os modelos dos robôs também são gerados em cada posição, e seus cromossomos são inseridos em seus objetos 3D. Eles passam a funcionar de um modo que é possível observar suas ações no mapa, e quando os gráficos são desligados, a simulação anterior volta a funcionar de onde parou. A Figura 4 mostra uma versão do mapa 3D junto com alguns robôs em funcionamento.
Figura 4: Mapa 3D no modo visual
5. Resultados
O software foi terminado dentro do prazo, suas principais funcionalidades são o algoritmo evolutivo aplicado na evolução dos robôs em código, e a possibilidade de ligar os gráficos para observar os robôs funcionando com o atual cromossomo.
Foram criadas quatro diferentes telas, a primeira tela a ser executada ao abrir a aplicação é o menu inicial. O menu possui quatro botões, o primeiro é “Iniciar simulação”, que ao ser clicado leva o usuário à tela de simulação. O segundo é o botão “Como Usar” que leva o usuário a uma tela com explicações simples do funcionamento do software, o terceiro é “Sobre”, que explica o software ser um projeto de faculdade e outras coisas, e o último botão é o “Sair”, que ao ser clicado fecha a aplicação. Todas as telas foram criadas utilizando elementos 3D e 2D do próprio Unity, como pode ser observado na Figura 5.
Figura 5: Telas do software
A simulação inicialmente é executada com os gráficos desligados, conforme pode ser visto na quarta imagem da Figura 5. São exibidos dois textos, um que indica estar na simulação, e o segundo mostra a geração atual dos robôs, que muda cada vez que são evoluídos. A figura vermelha, dentro da tela de simulação, preenche a tela enquanto os gráficos estão desligados, e serve como um chão para o mapa quando os gráficos são ligados, como é possível observar na Figura 6. Os menus presentes na tela de simulação são, “Voltar” que leva o usuário de volta ao menu inicial, “Lig/Des Gráficos” que como o nome sugere é o botão de ligar e desligar os gráficos da simulação, e “Sair” que encerra o programa.
Simulação com Gráficos
Figura 6: Simulação final em modo gráfico
Tanto na tela “Como Usar”, como em um arquivo .txt que acompanha o software é dada a explicação de que para que os dados da simulação possam ser salvos automaticamente. O usuário deve criar uma pasta com o nome “resultados” no diretório “C:”, pois os dados estão programados para serem salvos no caminho “C:/resultados/”.
Após simular quantas vezes for desejado, o usuário pode ir até a pasta criada e lá ele encontrará quatro arquivos .txt. Os dois primeiros arquivos, com os nomes “doc1” e “doc2” salvam respectivamente o fitness do coletor pai e do perseguidor pai, de cada geração simulada. Enquanto os arquivos “docf1” e “docf2” guardam informações mais gerais dos robôs, como o número do pai, o fitness, seu cromossomo e sua geração.
Para a realização dos testes de comprovação do funcionamento do software e do algoritmo evolutivo, foram criadas 2 versões diferentes para o programa. Na primeira a evolução acontece mais rápido (a cada 100 iterações) enquanto na segunda a evolução é um pouco mais lenta (a cada 1000 interações). Cada simulação foi testada mais de uma vez e deixadas funcionando por um tempo. Após isso os dados de cada simulação foram recolhidos e alguns gráficos foram gerados com os valores dos fitness dos robôs, para facilitar a visualização da evolução caso ela tenha ocorrido. Um dos primeiros gráficos gerados é o mostrado na Figura 7, nesse, assim como no gráfico da Figura 8 é possível observar de forma clara a evolução dos robôs. Houveram alguns casos onde os gráficos ficaram similares ao da Figura 9, onde a evolução para em alguns pontos e volta a acontecer em seguida.
Figura 7: Gráfico mostrando a evolução dos robôs
Figura 8: Gráfico ilustrando os resultados da simulação
Figura 9: Gráfico com evolução não constante
Com a análise dos gráficos foi possível perceber uma certa dificuldade de evolução dos robôs coletores, diferente dos perseguidores, que evoluíram muito bem, e tiveram um aumento muito grande em seu fitness em um dado momento em que o coletor tem uma queda. A dificuldade de evolução dos coletores e facilidade dos perseguidores se deu devido ao fato dos robôs perseguidores apenas ganharem pontos de fitness, o fato de não possuírem um “predador”, ou algo que fizesse com que perdessem os pontos ganhados, fez com que evoluíssem com facilidade, enquanto os coletores, que ganhavam ponto coletando as pedras, perdiam ponto quando eram pegos por robôs perseguidores, que ao aprenderem a perseguir aquele robô, faziam com que o mesmo perdesse pontos continuamente.
Mesmo com essa disputa de pontos onde os perseguidores tiveram certa vantagem evolutiva, é possível observar a evolução de ambos os robôs, comprovando assim o funcionamento do software e do algoritmo, conforme foi proposto.
O software proposto foi desenvolvido conforme o planejado, foi testado, e os resultados dos testes comprovaram seu funcionamento. Com isso é esperado que o software e o algoritmo desenvolvido nesse trabalho contribuam com a comunidade científica de pesquisadores da área de algoritmos evolutivos e navegação autônoma. Isso pode auxiliar no aprendizado de robôs autônomos, e até mesmo no uso do algoritmo em jogos, onde o mesmo pode ser aplicado a inimigos os deixando mais inteligentes e aumentando a imersão de jogadores. O software está disponível para download em sua página* onde tanto o projeto como o software pronto podem ser baixados, a página também possui informações sobre o desenvolvimento e funcionamento do software.
Possíveis continuações desse projeto preveem o desenvolvimento do mesmo software na plataforma jMonkey. Aumentando a disponibilidade e abrangência do software, já que a plataforma jMonkey é uma plataforma muito conhecida no meio científico e utiliza programação em java, o que torna o software e o algoritmo disponível para um público maior.
7. Referências
AZZOLINI, R. P., SERAPIÃO, A. B. S., Navegação Autônoma de Robôs em Ambientes Aleatórios Através de Estratégias Evolutivas.X SBAI – Simpósio Brasileiro de Automação Inteligente, São João del-Rei – MG, 2011.
CRESTANI, P. R. J., FIGUEIREDO, M. F., ZUBEN, F. J. VON., Controlador neural nebuloso autônomo de direção e velocidade para robôs móveis.V Simpósio Brasileiro de Automação Inteligente, novembro, Canela- RS, 2001.
GONZALEZ, J. A., MAREGONI, M., Controle Baseado em Algoritmo Genético para um Braço Robótico Móvel.VII SBAI/ II IEEE LARS. São Luís, 2005.
HOSS, A., HOUNSELL, M. S., LEAL, A. B., VirBot4u: Um Simulador de Robô usando X3D. In:I Simpósio de Computação Aplicada, Passo Fundo – RS. I SCA. Porto Alegre – RS: SBC. pp. 1-15, 2009.
PESSIN, G., OSÓRIO, F., MUSSE, S., NONNEMMACHER, V., FERREIRA, S. S., Desenvolvimento de um ambiente para simulação de robótica móvel em áreas florestais. In:Anais do VI SIRC-RS, Santa Maria, RS, 2007.
REIS, L. P., Ciber-FEUP – Um Agente para Utilizar o Simulador Ciber-Rato no Ensino da Inteligência Artificial e Robótica Inteligente.Revista do DETUA, 3(7):655-658, 2002.
SALVATO, H. C., CROCOMO, M. K., Criação de um Ambiente Virtual para Simulação de Aplicações de Vida Artificial.6° Congresso de Iniciação Científica e Tecnológica do IFSP – CINTEC. 2015.
TF3DM.,TF3DM – 3D Models for free. Disponível em <http://tf3dm.com/> .Acesso em 22 abr. 2016.
UNITY.,Unity – Game Engine. Disponível em: <http://unity3d.com/pt>. Acesso em: 22 abr. 2016.
WOLF, D. F., SIMÕES, E. V., OSÓRIO, F. S., JUNIOR, O. T., Robótica Inteligente: Da Simulação às Aplicações no Mundo Real. [Tutorial] In: André Ponce de Leon F. De Carvalho; Tomasz Kowaltowski. (Org.).JAI: Jornada de Atualização em Informática da SBC. Rio de Janeiro: SBC – Editora da PUC Rio, v. 1, p. 279-330, 2009.
ZUBEN, F. J. VON., Computação Evolutiva: Uma Abordagem Pragmática.Anais da I Jornada de Estudos em Computação de Piracicaba e Região, p. 25–45, 2000.
Nenhum comentário:
Postar um comentário