UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE CENTRO DE TECNOLOGIA PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO Estratégia de Navegação com Planejamento Dinâmico e Algoritmo Genético Aplicada a Robôs Móveis Terrestres Átila Varela Ferreira Medeiros de Oliveira Orientador: Prof. Dr. Marcelo Augusto Costa Fernandes Número de ordem do PPgEEC: M461 Natal - RN 2015 Seção de Informação e Referência Catalogação da Publicação na Fonte. UFRN / Biblioteca Central Zila Mamede Oliveira, Atila Varela Ferreira Medeiros de. Estratégia de navegação com planejamento dinâmico e algoritmo genético aplicada a robôs móveis terrestres / Atila Varela Ferreira Medeiros de Oliveira. - Natal, 2015. 63f. : il. Orientador: Marcelo Augusto Costa Fernandes. Dissertação (Mestrado) - Universidade Federal do Rio Grande do Norte. Centro de Tecnologia. Programa de Pós-Graduação em Engenharia Elétrica e de Computação. 1. Algoritmos genéticos - Dissertação. 2. Robôs móveis - Dissertação. 3. Navegação autônoma - Dissertação. 4. Planejamento dinâmico - Dissertação. 5. DPNA- GA - Dissertação. I. Fernandes, Marcelo Augusto Costa. II. Título. RN/UF/BCZM CDU 004.421 UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE CENTRO DE TECNOLOGIA PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO Estratégia de Navegação com Planejamento Dinâmico e Algoritmo Genético Aplicada a Robôs Móveis Terrestres Átila Varela Ferreira Medeiros de Oliveira Orientador: Prof. Dr. Marcelo Augusto Costa Fernandes Dissertação de Mestrado apresentada ao Programa de Pós-Graduação em Engenharia Elétrica e de Computação da UFRN (área de concentração: Engenharia de Computação) como parte dos requisitos para obtenção do título de Mestre em Ciências. Natal - RN 2015 Prof. Drª. Ângela Maria Paiva Cruz Reitora da Universidade Federal do Rio Grande do Norte Prof. Dr. Luiz Alessandro Pinheiro da Câmara de Queiroz Diretor do Centro de Tecnologia Prof. Dr. Antônio Luiz Campos Coordenador do Programa de Pós-Graduação em Engenharia Elétrica e de Computação Resumo Este trabalho propõe uma estratégia de navegação autônoma assistida por algoritmo genético com planejamento dinâmico para robôs móveis terrestres, chamada DPNA-GA (Dynamic Planning Navigation Algorithm optimized with Genetic Algorithm). A estratégia foi aplicada em ambientes – tanto estáticos quanto dinâmicos – nos quais a localização e o formato dos obstáculos não são previamente conhecidos. A cada evento de deslocamento, a rota é planejada através de um algoritmo de controle que minimiza a distância entre o robô e o objetivo e maximiza a distância em relação aos obstáculos. Utilizando um sensor de localização espacial e um conjunto de sensores de distância, a estratégia de navegação proposta foi capaz de planejar dinamicamente percursos aproximadamente ótimos livres de colisão. Simulações realizadas em diferentes ambientes demostraram que a técnica fornece um alto grau de flexibilidade e robustez. Para isso, foram aplicadas diversas variações de parâmetros genéticos, tais como: taxa de cruzamento, tamanho da população, dentre outros. Finalmente, os resultados das simulações demonstram satisfatoriamente a eficácia e robustez da técnica DPNA-GA, validando-a para aplicações reais em robôs móveis terrestres. Palavras-chave – Algoritmos Genéticos, Robôs Móveis, Navegação Autônoma, Planejamento Dinâmico, DPNA-GA. Abstract This work proposes a new autonomous navigation strategy assisted by genetic algorithm with dynamic planning for terrestrial mobile robots, called DPNA-GA (Dynamic Planning Navigation Algorithm optimized with Genetic Algorithm). The strategy was applied in environments - both static and dynamic - in which the location and shape of the obstacles is not known in advance. In each shift event, a control algorithm minimizes the distance between the robot and the object and maximizes the distance from the obstacles, rescheduling the route. Using a spatial location sensor and a set of distance sensors, the proposed navigation strategy is able to dynamically plan optimal collision-free paths. Simulations performed in different environments demonstrated that the technique provides a high degree of flexibility and robustness. For this, there were applied several variations of genetic parameters such as: crossing rate, population size, among others. Finally, the simulation results successfully demonstrate the effectiveness and robustness of DPNA-GA technique, validating it for real applications in terrestrial mobile robots. Keywords – Genetic Algorithms, Mobile Robots, Autonomous Navigation, Dynamic Planning, DPNA-GA. i Sumário Sumário ........................................................................................................................................ i Lista de Figuras ......................................................................................................................... iii Lista de Tabelas .......................................................................................................................... v Lista de Algoritmos .................................................................................................................. vii 1 Introdução............................................................................................................................ 1 1.1 Revisão bibliográfica ................................................................................................... 1 1.2 Objetivo ....................................................................................................................... 3 1.3 Contribuições do trabalho ............................................................................................ 3 1.4 Artigos publicados ....................................................................................................... 4 1.5 Descrição do trabalho .................................................................................................. 4 2 Algoritmos Genéticos .......................................................................................................... 5 2.1 Introdução .................................................................................................................... 5 2.2 Funcionamento ............................................................................................................. 7 2.3 Operadores Básicos ...................................................................................................... 9 2.3.1 Métodos de Seleção .............................................................................................. 9 2.3.2 Métodos de Crossover ........................................................................................ 10 2.3.3 Métodos de Mutação .......................................................................................... 12 2.3.4 Métodos de Substituição ..................................................................................... 13 3 Estratégia DPNA-GA ........................................................................................................ 14 3.1 Etapa de Varredura .................................................................................................... 15 3.2 Detecção dos Obstáculos ........................................................................................... 17 3.3 Busca pelo Objetivo Local ......................................................................................... 18 3.4 Deslocamento ............................................................................................................. 21 4 Resultados ......................................................................................................................... 23 4.1 Visão geral ................................................................................................................. 23 4.2 Variação de parâmetros ............................................................................................. 31 4.3 Comparação com outros métodos .............................................................................. 39 5 Conclusões ........................................................................................................................ 43 Referências Bibliográficas ........................................................................................................ 45 ii iii Lista de Figuras Figura 1 - Métodos crossover (Sastry, et al., 2005, p. 101). ..................................................... 11 Figura 2 - Exemplo do polígono delimitador (linha tracejada em azul) para caso onde e ( ). .................................................................................................................... 16 Figura 3 - Exemplo ilustrativo do PV (linha tracejada em verde) para e o conjunto de pontos, , detectados (asteriscos em vermelho) que contornam os obstáculos. ............... 18 Figura 4 - Exemplo ilustrando o cálculo da função de avaliação para um -ésimo indivíduo, , em relação ao objetivo final, , e os obstáculos, ........................................ 21 Figura 5 - Exemplo ilustrando os deslocamento ( ) feitos pelo robô até o ponto final, . ........................................................................................................................................... 22 Figura 6 - Deslocamento do robô num ambiente moderadamente complexo. Num percurso próximo do ótimo, no qual foram necessários eventos. ........................................... 24 Figura 7 - Deslocamento do robô para o interior de um obstáculo em formato de U, realizando um percurso aproximadamente ótimo ( ). .................................................................... 25 Figura 8 - Deslocamento do robô para o exterior de um obstáculo em formato de U, realizando um percurso aproximadamente ótimo ( . .................................................. 25 Figura 9 - Deslocamento do robô num ambiente aberto com obstáculos retangulares aleatoriamente espaçados. O robô realizou eventos de deslocamento para alcançar o objetivo final. ............................................................................................................................ 26 Figura 10 - Deslocamento do robô num ambiente aberto com obstáculos arredondados aleatoriamente espaçados. O robô realizou eventos de deslocamento para alcançar o objetivo final. ............................................................................................................................ 27 Figura 11 - Deslocamento do robô num ambiente em formato de duto (estrutura em L com uma curvatura). O robô realizou eventos de deslocamento para alcançar o objetivo final. .......................................................................................................................................... 28 Figura 12 - Deslocamento do robô num ambiente em formato de duto (estrutura em L com duas curvaturas). O robô realizou eventos de deslocamento para alcançar o objetivo final. .......................................................................................................................................... 28 Figura 13 - Deslocamento do robô num ambiente em formato de duto (estrutura em L com quatro curvaturas). O robô realizou eventos de deslocamento para alcançar o objetivo final. .......................................................................................................................................... 29 Figura 14 - Deslocamento do robô para o interior de um obstáculo em formato de U, simulando o aparecimento repentino de um obstáculo dinâmico. O robô realizou eventos de deslocamento para alcançar o objetivo final........................................................... 30 Figura 15 - Deslocamento do robô para o exterior de um obstáculo em formato de U, simulando o aparecimento repentino de um obstáculo dinâmico. O robô realizou eventos de deslocamento para alcançar o objetivo final........................................................... 30 Figura 16 - Deslocamento do robô na simulação ( , e ). ........... 33 Figura 17 - Deslocamento do robô na simulação ( , e ). ........... 33 Figura 18 - Deslocamento do robô na simulação ( , e ). ........... 34 Figura 19 - Deslocamento do robô na simulação ( , e ). ........... 34 iv Figura 20 - Deslocamento do robô na simulação ( , e ). ........... 35 Figura 21 - Deslocamento do robô na simulação ( , e ). ........... 36 Figura 22 - Deslocamento do robô na simulação ( , e ). ........... 36 Figura 23 - Deslocamento do robô na simulação ( , e ). ........... 37 Figura 24 - Deslocamento realizado pelo robô no ambiente A. Comparação entre o método apresentado em por Tuncer & Yildirim (2012) (percurso em vermelho) e o DPNA-GA (percurso em preto). .................................................................................................................. 40 Figura 25 - Deslocamento realizado pelo robô no ambiente B. Comparação entre o método apresentado por Tuncer & Yildirim (2012) (percurso em vermelho) e o DPNA-GA (percurso em preto). .................................................................................................................................. 40 Figura 26 - Deslocamento realizado pelo robô no ambiente D. Comparação entre o método apresentado em por Yongnian et al. (2012) (percurso em vermelho) e o DPNA-GA (percurso em preto). .................................................................................................................................. 41 Figura 27 - Deslocamento realizado pelo robô no ambiente D. Comparação entre o método apresentado em por Yongnian et al. (2012) (percurso em vermelho) e o DPNA-GA (percurso em preto). .................................................................................................................................. 41 v Lista de Tabelas Tabela 1 - Parâmetros comuns utilizados nas simulações. ....................................................... 23 Tabela 2 - Tempo médio de execução do algoritmo DPNA-GA para os ambientes simulados. .................................................................................................................................................. 31 Tabela 3 - Parâmetros fixos comuns utilizados nas simulações. .............................................. 32 Tabela 4 - Parâmetros e resultados das simulações realizadas no ambiente . ..................... 35 Tabela 5 – Parâmetros e resultados das simulações realizadas no ambiente . .................... 37 Tabela 6 – Comparação entre os métodos. ............................................................................... 42 vi vii Lista de Algoritmos Algoritmo 1 – Algoritmo Genético ............................................................................................ 9 Algoritmo 2 – DPNA-GA ........................................................................................................ 22 viii 1 1 Introdução 1.1 Revisão bibliográfica A evolução das pesquisas no campo da robótica nos últimos anos teve uma grande influência nas atividades humanas em diversos setores da sociedade. Em relação à robótica móvel, o principal objetivo é desenvolver robôs inteligentes autônomos capazes de planejar efetivamente sua movimentação em ambientes estáticos e dinâmicos desconhecidos (Siegwart, et al., 2011). Métodos envolvendo Inteligência Artificial (IA) estão dentre os mais utilizados para esse propósito, e há diversos casos de novas estratégias de navegação que demonstram um alto grau de precisão no que concerne à obtenção de percursos ótimos 1 livres de colisão. Na área de IA, várias técnicas empregam lógica fuzzy, redes neurais artificiais (RNAs), algoritmos genéticos (AGs), ou uma combinação desses procedimentos (Martinez-Soto, et al., 2012; Juang & Chang, 2011). Técnicas baseadas em AGs têm sido vastamente utilizadas devido a sua robustez e, na maioria dos casos, têm sido capazes produzir caminhos ótimos tanto em ambientes estáticos quanto dinâmicos (Ismail AL-Taharwa & Al-Weshah, 2008; Yun, et al., 2011; Shi & Cui, 2010; Shamsinejad, et al., 2010; Tuncer & Yildirim, 2012; Cosío & Neda, 2004; Yongnian, et al., 2012; Zhang, et al., 2012; Samadi & Othman, 2013; Chaari, et al., 2012). Na maioria dos estudos relatados na literatura, técnicas de navegação utilizando AGs aplicam estratégias de planejamento global ou local. No planejamento global, podem ser obtidas rotas ótimas a um alto custo computacional. Além disso, em geral, é necessário um conhecimento prévio do ambiente de deslocamento. Já no planejamento local, rotas subótimas podem ser obtidas a um custo computacional mais baixo e com conhecimento mínimo ou inexistente do ambiente a ser percorrido (Ismail AL-Taharwa & Al-Weshah, 2008; Shamsinejad, et al., 2010). Ambos os tipos de planejamento podem ser aplicados em ambientes estáticos e dinâmicos. Entretanto, para ambientes dinâmicos, estratégias de 1 Neste trabalho, percurso ótimo é o trajeto de comprimento mínimo realizado pelo robô sem que haja colisões com obstáculos do ambiente. 2 planejamento global necessitam utilizar dispositivos de observação externos com o intuito de transmitir o estado corrente do ambiente ao robô numa taxa de transmissão que seja adequada (Tuncer & Yildirim, 2012). Nos trabalhos de Ismail AL-Taharwa & Al-Weshah (2008), Tuncer & Yildirim, (2012), Yongnian et al (2012), Zhang et al. (2012), Samadi & Othman (2013) e Chaari et al. (2012), são apresentadas estratégias de navegação com planejamento global utilizando AGs, nas quais os indivíduos (ou cromossomos) consistem em todas as possíveis rotas entre a posição inicial do robô e o objetivo final. Em todos os casos, é necessário um conhecimento prévio do ambiente, que é representado por um grid bidimensional. As técnicas propostas em alguns desses estudos (Ismail AL-Taharwa & Al-Weshah, 2008; Yongnian, et al., 2012; Zhang, et al., 2012; Samadi & Othman, 2013; Chaari, et al., 2012) são específicas para ambientes estáticos. O método descrito em Tuncer & Yildirim (2012) é aplicável em ambientes dinâmicos, embora seja necessário um dispositivo de observação externo para fornecer informações a respeito do estado do ambiente a uma taxa de transmissão superior à taxa das mudanças no ambiente. Apesar de todas as técnicas terem se mostrado efetivas, três aspectos devem ser ressaltados. O primeiro é que o tamanho dos indivíduos é variável em função do tamanho da rota – quanto maior a complexidade do ambiente, maior o tamanho – e da resolução do grid associada à movimentação do robô. Isso pode aumentar significativamente a complexidade espacial e temporal do AG, tornando-o inadequado para uso em sistemas de hardware limitados, como microcontroladores (MCUs), processadores de sinal digital (DSPs), dentre outros. O segundo aspecto a ser denotado é que nem sempre é possível obter uma descrição prévia do ambiente, a qual é essencial para estratégias de planejamento global. Finalmente, o terceiro aspecto é que estratégias de planejamento global são mais adequadas para uso em ambientes estáticos, devido à necessidade de uso de equipamento externo de observação no caso de ambientes dinâmicos. Estratégias de navegação utilizando AGs foram propostas para ambos os tipos de ambientes dinâmicos (Yun, et al., 2011; Shi & Cui, 2010) e estáticos (Shamsinejad, et al., 2010; Cosío & Neda, 2004). Nessas técnicas, os indivíduos possuem tamanhos variáveis dinamicamente, onde são armazenados os pontos que compõem o percurso. Apesar de utilizarem estratégias de planejamento local, esses métodos enfrentam os mesmos problemas 3 dos métodos de planejamento local, onde a complexidade do AG é uma função da complexidade do ambiente e da resolução de movimento do robô. 1.2 Objetivo Este trabalho propõe uma estratégia de navegação com planejamento dinâmico baseada em algoritmos genéticos (DPNA-GA). O objetivo do algoritmo é encontrar um percurso aproximadamente ótimo livre de colisões até um ponto espacialmente definido. Para isso, o DPNA-GA faz uso de um conjunto de sensores de distância e um sensor de localização espacial e não há necessidade de conhecimento prévio do ambiente em que se deseja realizar o deslocamento do robô. Diferentemente dos métodos comentados anteriormente, o DPNA-GA utiliza um esquema de navegação com planejamento local, no qual o ambiente é desconhecido e o tamanho dos cromossomos dos indivíduos é fixo – apenas representando possíveis objetivos locais para os quais o robô pode mover-se, ou seja, independem da complexidade do ambiente ou do tamanho da rota. Outro aspecto importante é que o DPNA-GA pode ser aplicada tanto em ambientes estáticos, quanto em ambientes dinâmicos, dado que o planejamento é reformulado a cada deslocamento. Apesar do fato de as técnicas de navegação com planejamento local fornecerem soluções subótimas, pode-se depreender dos resultados que, em vários casos, é possível obter-se rotas bastante próximas do ótimo. 1.3 Contribuições do trabalho As principais contribuições deste trabalho são: (1) a proposta de uma estratégia de navegação com planejamento local, chamada DPNA-GA; (2) os cromossomos dos indivíduos gerados pelo algoritmo genético possuem tamanho fixo, independente da complexidade do ambiente; e (3) a função de avaliação utilizada pelo algoritmo genético apresentada na Equação 13, a qual é baseada na técnica de Campos Potenciais. 4 1.4 Artigos publicados  DE OLIVEIRA, A. V. F. M.; FERNANDES, M. A. C. Dynamic planning navigation strategy for mobile terrestrial robots. Robotica, v. CJO, p. 1-16, 2014.  DE OLIVEIRA, A. V. F. M.; FERNANDES, M. A. C. Validação de Estratégia de Navegação com Planejamento Dinâmico Aplicada a Robôs Móveis Terrestres. In: XX Congresso Brasileiro de Automática (CBA 2014), 2014, Belo Horizonte. Anais do XX Congresso Brasileiro de Automática (CBA 2014), 2014. v. 1. p. 640-647.  DE OLIVEIRA, A. V. F. M.; FERNANDES, M. A. C. Dynamic Planning Navigation Technique Optimized with Genetic Algorithm. In: SBR'2014 - 2nd Brazilian Symposium on Robotics and LARS'2014 - 11th Latin American Robotics Symposium, 2014, São Carlos, SP. SBR'2014 - 2nd Brazilian Symposium on Robotics and LARS'2014 - 11th Latin American Robotics Symposium, 2014.  DE OLIVEIRA, A. V. F. M.; FERNANDES, M. A. C. Genetic Algorithm-Based Navigation Strategy For Mobile Terrestrial Robots. In: Simpósio Brasileiro de Automação Inteligente (SBAI), 2013, Fortaleza, CE. Anais do XI Simpósio Brasileiro de Automação Inteligente (SBAI), 2013. 1.5 Descrição do trabalho O trabalho é organizado da seguinte forma: o capítulo 2 apresenta um breve embasamento teórico a respeito dos algoritmos genéticos; o capítulo 3 apresenta algumas das técnicas de deslocamento desenvolvidas na área de robótica móvel; o capítulo 4 descreve detalhadamente o algoritmo no qual é baseada a técnica DPNA-GA; o capítulo 5 demonstra os resultados obtidos da aplicação do DPNA-GA em diferentes tipos de ambientes; e, finalmente, o capítulo 6 apresenta as conclusões do trabalho. 5 2 Algoritmos Genéticos 2.1 Introdução Um algoritmo genético é um método utilizado para resolver problemas de otimização – tanto problemas com restrições quanto aqueles sem restrições – baseado no processo de seleção natural, imitando assim a evolução biológica. O algoritmo modifica repetidamente uma população de soluções. A cada passo, o algoritmo genético seleciona aleatoriamente indivíduos da população atual, os quais são utilizados como pais que produzirão filhos para a próxima geração. Após sucessivas gerações, a população evolui, convergindo para a solução ótima do problema. Pode-se aplicar algoritmos genéticos para solucionar problemas para os quais não se aplicam satisfatoriamente métodos de otimização padrão, incluindo problemas em que a função objetivo é descontínua, não-derivável, estocástica, ou altamente não-linear. Os algoritmos genéticos diferenciam-se dos métodos de otimização clássicos, baseados em derivadas, em dois principais aspectos: em primeiro lugar, um algoritmo de otimização clássico gera um único ponto a cada iteração. A sequência de pontos gerados aproxima a solução ótima para o problema. Ao passo que os algoritmos genéticos geram uma população de pontos a cada iteração, e o melhor ponto da população se aproxima da solução ótima. Em segundo lugar, algoritmos de otimização clássicos selecionam o próximo ponto da sequência através de computação determinística, enquanto que algoritmos genéticos geram a próxima população utilizando métodos aleatórios. Nas décadas de 50 e 60, vários cientistas da computação estudaram independentemente sistemas evolucionários com a ideia de que a evolução poderia ser usada como uma ferramenta de otimização para problemas da engenharia. A ideia em todos esses sistemas era “evoluir” uma população de possíveis soluções para determinado problema usando operadores inspirados em variações genéticas naturais e seleção natural (Melanie, 1999). Nas décadas de 1960 e 1970, Rechenberg (1965, 1973) apresentou “estratégias evolucionárias”, um método que ele utilizou para otimizar os parâmetros de valor real para dispositivos como os aerofólios. O campo de estratégias baseadas em evolução permanece 6 uma área de intensa pesquisa. Fogel, Owens, e Walsh (1966) desenvolveram a “programação evolucionária”, uma técnica na qual possíveis soluções para uma determinada tarefa eram representadas como máquinas de estados finitos, que evoluíam através de mutações aleatórias de seus diagramas de transição de estados e era selecionada a mais apta solução. Juntos, estratégias evolucionárias, programação evolucionária, e algoritmos genéticos, formam a espinha dorsal do campo de computação evolucionária. Vários outros pesquisadores, nos anos 50 e 60, desenvolveram algoritmos inspirados em evolução para otimização e aprendizagem de máquina. Além disso, biólogos evolucionistas utilizaram computadores com o propósito de simular evolução em experimentos controlados. Os algoritmos genéticos foram inventados por John Holland na década de 60 e foram desenvolvidos por ele e seus alunos na Universidade de Michigan nos anos 60 e 70. Em contraste com as técnicas de estratégias evolucionárias e programação evolucionária, o objetivo principal de Holland não era desenvolver algoritmos para resolver um problema específico, e sim estudar formalmente o fenômeno da adaptação que ocorre na natureza e, a partir daí, desenvolver maneiras pelas quais mecanismos de adaptação natural pudessem ser importados para um sistema computacional. Em seu livro Adaptation in Natural and Artificial Systems (Holland, 1975), Holland apresenta o algoritmo genético como uma abstração da evolução biológica e desenvolve um arcabouço teórico para adaptação por algoritmos genéticos. O algoritmo genético de Holland é um método que faz com que uma população de “cromossomos” (string de bits) se transforme em uma nova população utilizando um tipo de “seleção natural” em conjunto com operações inspiradas na genética, tais quais crossover, mutação e inversão. Cada cromossomo consiste de “genes” (bits), e cada gene uma instância de um “alelo” em particular (0 ou 1). O operador de seleção escolhe aqueles cromossomos na população aos quais será dado o direito de reprodução, e, em média, os cromossomos mais aptos produzirão mais descendentes do que os menos aptos. O crossover realiza a troca de subpartes de dois cromossomos, imitando grosseiramente a recombinação biológica entre dois organismos de único cromossomo (“haplóide”). A mutação modifica aleatoriamente o valor dos alelos presentes nos cromossomos. A inversão, por sua vez, inverte a ordem de um pedaço contíguo do cromossomo, rearranjando assim a ordem em que os genes estão dispostos (Holland, 1975). 7 Mas por que utilizar evolução como uma inspiração para solucionar problemas computacionais? Para pesquisadores da computação evolucionária, os mecanismos da evolução parecem ser bastante adequados para alguns dos problemas mais complexos em diversos campos de pesquisa. Muitos problemas computacionais requerem uma busca num universo muito grande de possibilidades de soluções – como no caso do projeto aqui em questão: os pontos para os quais o robô deve locomover-se até que encontre seu objetivo estão contidos num universo “infinito” de possibilidades. 2.2 Funcionamento Como bem descrevem Sastry et al. (2005), Algoritmos Genéticos codificam as variáveis de decisão de um determinado problema de busca mapeando-as em strings de tamanho finito compostas por caracteres de um alfabeto com certa cardinalidade como, por exemplo, o alfabeto binário {0,1}. As strings, que são possíveis soluções para o problema em questão, são chamadas de cromossomos, os caracteres da string são chamados de genes e os valores dos genes são conhecidos como alelos. Para chegarmos numa boa solução e para podermos implementar seleção natural, precisamos de uma medida que nos possibilite distinguir boas soluções daquelas consideradas ruins. Essa medida poderia ser uma função objetivo, que é um modelo matemático ou uma simulação de computador, ou ainda uma função subjetiva, na qual humanos são responsáveis por determinar se as soluções são boas ou ruins. Essencialmente, a medida de fitness (aptidão) deve determinar quão relativamente boa é a possível solução, a qual será, subsequentemente, utilizada pelo AG para guiar a evolução de boas soluções. Outro conceito bastante importante em se tratando de AGs é a noção de população. Ao contrário de outros métodos tradicionais de busca, algoritmos genéticos dependem de uma população de possíveis soluções. O tamanho da população, que normalmente é um parâmetro especificado pelo próprio usuário, é um dos mais importantes fatores que afetam a escalabilidade e desempenho do AG. Por exemplo, uma população pequena pode levar a uma convergência prematura e gerar soluções precárias. Por outro lado, grandes populações podem acarretar num desnecessário consumo de tempo computacional valioso. 8 Uma vez que o problema está codificado de forma “cromossômica” e possuímos uma maneira de discriminar boas soluções de soluções ruins através de uma função de fitness, podemos começar a “evoluir” as soluções para o problema de busca utilizando os seguintes passos: 1. Inicialização: a população inicial de possíveis soluções é normalmente gerada de forma aleatória sobre o espaço de busca. No entanto, conhecimentos de domínio específico ou outra informação podem ser facilmente incorporados. 2. Avaliação: uma vez que a população é inicializada ou uma população descendente é criada, os valores de fitness das soluções candidatas são avaliados. 3. Seleção: aloca mais cópias daquelas soluções com melhores valores de aptidão, desta forma impondo um mecanismo de sobrevivência do mais apto para as soluções candidatas. A principal ideia por trás da seleção é priorizar as melhores soluções em relação às piores, e diversos procedimentos foram propostos para realizar essa ideia, como por exemplo: a seleção por roleta, seleção estocástica universal, seleção por classificação e seleção por torneio. 4. Crossover ou Recombinação: combina partes de dois ou mais soluções “pais” para criar novas, possivelmente melhores soluções (filhos). 5. Mutação: enquanto o crossover opera com dois ou mais cromossomos “pais”, a mutação modifica localmente e aleatoriamente uma solução. Há várias maneiras de realizar mutação, entretanto, geralmente envolvem a mudança de um ou mais traços individuais. Em outras palavras, a mutação realiza uma mudança aleatória em um ou mais genes do cromossomo. 6. Substituição: a população gerada através dos métodos de seleção, crossover, e mutação substituem a população pela qual foi originada. Diversas técnicas de substituição tais como Substituição Elitista, Substituição Geracional e Substituição de Regime Permanente são utilizadas em algoritmos genéticos. 7. Repetir passos 2-6 até que a condição de parada seja encontrada. Como visto em Gen & Cheng (2000), podemos definir ainda uma estrutura geral para um algoritmo genético através do seguinte pseudocódigo: 9 Algoritmo 1 – Algoritmo Genético 1 2 ( 3 ( 4 enquanto (condição de parada não alcançada) faça 5 ( ( 6 ( 7 ( ( ( 8 9 fim enquanto Onde ( é a população de indivíduos para a geração e ( é a população de novos indivíduos gerados através de crossover e mutação. 2.3 Operadores Básicos Nesta secção serão descritos alguns dos operadores de seleção, crossover e mutação mais utilizados em algoritmos genéticos (Sastry, et al., 2005). 2.3.1 Métodos de Seleção Os métodos de seleção podem ser amplamente classificados em duas classes: Seleção por Aptidão Proporcional e Seleção ordinal. A seguir são apresentados os conceitos de cada classe. 2.3.1.1 Seleção por Aptidão Proporcional Esta classe inclui métodos tais como seleção por roleta e seleção estocástica universal. Na seleção por roleta, para cada indivíduo da população é atribuído um espaço na roleta proporcional à sua aptidão. Isto é, nessa roleta “tendenciosa”, boas soluções ocupam uma 10 maior porção em relação a soluções menos aptas. A roleta é “girada” para obter-se um candidato a reprodutor. A seleção por roleta pode ser implementada como a seguir: 1. Avaliar a aptidão, , de cada indivíduo da população. 2. Computar a probabilidade (porção da roleta), , de selecionar cada membro da população: ∑ , onde é o tamanho da população. 3. Calcular a probabilidade cumulativa, , para cada indivíduo: ∑ . 4. Gerar um número aleatório uniforme, ( (um número real entre 0 e 1). 5. Se então selecionar o primeiro cromossomo, , senão, selecionar o indivíduo tal que . 6. Repetir passos 4-5 vezes para criar reprodutores. 2.3.1.2 Seleção Ordinal Esta classe inclui métodos como seleção por torneio e seleção por truncamento. Na seleção por torneio, cromossomos são escolhidos aleatoriamente (com ou sem substituição) e entram num torneio uns contra os outros. O indivíduo mais apto vence o torneio e é selecionado como pai. O valor mais comumente utilizado para é 2. Usando esse esquema de seleção, torneios são necessários para escolher indivíduos. No método de seleção por truncamento, os ( -ésimos indivíduos mais aptos são copiados vezes. Há outros métodos de seleção, como, por exemplo, o método de amostragem estocástica uniforme, que estabelece uma linha particionada, na qual cada pai corresponde a uma secção com comprimento proporcional ao seu valor em escala. O algoritmo se move sobre a linha a passos equidistantes. A cada passo, o algoritmo aloca o pai representado pela seção em que se encontra. O primeiro passo é um número aleatório uniforme menor que o pré-estabelecido para o tamanho do passo. 2.3.2 Métodos de Crossover Após a seleção, os indivíduos selecionados para reprodução serão recombinados para criar novos e melhores filhos. Nesta secção serão descritos alguns operadores de crossover 11 genéricos (independentes do problema). Na maioria desses métodos, dois indivíduos reprodutores são selecionados e recombinados com uma certa probabilidade, , chamada de probabilidade de crossover. Isto é, um número aleatório uniforme, , é gerado e se , os dois indivíduos selecionados aleatoriamente realizarão o crossover. Caso contrário, se , os dois filhos serão simples cópias de seus pais. 2.3.2.1 Crossover de -pontos Crossovers de um ponto e dois pontos são os métodos mais simples e mais aplicados. No crossover de um ponto, como ilustrado na Figura 1, o ponto onde haverá a recombinação é escolhido aleatoriamente, e os alelos situados em um dos lados do ponto são trocados entre os indivíduos. No crossover de dois pontos, dois pontos de recombinação são escolhidos aleatoriamente. O conceito de crossover de um ponto pode ser facilmente estendido para crossover de -pontos, onde pontos de crossover são escolhidos aleatoriamente. Figura 1 - Métodos crossover (Sastry, et al., 2005, p. 101). 12 2.3.2.2 Crossover uniforme Outro operador de recombinação comumente utilizado é o de crossover uniforme. Nele, como ilustrado na Figura 1, cada alelo é trocado entre o par de cromossomos aleatoriamente selecionados com certa probabilidade, , conhecida como probabilidade de permuta. Normalmente, o valor de probabilidade de permuta escolhido é 0,5. Há diversas outras formas de crossover, as quais não pertencem ao escopo deste trabalho. 2.3.3 Métodos de Mutação Se utilizarmos um operador de crossover, tal como o crossover de um ponto, poderão ser gerados cromossomos cada vez melhores, porém, o problema é, se dois pais (ou pior, a população inteira) possuem o mesmo alelo em determinado gene, então, o crossover de um ponto não será capaz de mudar isso. Em outras palavras, o gene terá sempre o mesmo alelo. A mutação é realizada para superar esse problema, tem o propósito de adicionar diversidade à população e, dessa forma, garantir que é possível explorar todo o espaço de busca. Um dos métodos de mutação mais comuns é a mutação por inversão de bit, na qual cada bit na string binária é trocado (um 0 é convertido em 1 e vice-versa) com uma certa probabilidade, , chamada de probabilidade de mutação. Um método de mutação bastante interessante pode ser encontrado no trabalho de Marsili-Libelli & Alba (2000). Nesse, é apresentado um método de mutação adaptativa, o qual reduz as chances de que cromossomos com alto grau de aptidão sofram mutação acentuada. Normalmente, em AGs, uma probabilidade constante é associada à mutação, ou seja, todos os cromossomos têm a mesma chance de sofrer mutação, independentemente de sua aptidão. Inversamente, fazendo-se da mutação uma função da aptidão, produz-se uma busca mais eficiente. Assim, é proposto um relacionamento inverso entre aptidão e probabilidade de mutação, a qual é uma função da posição do bit. Dessa forma, apenas os bits menos significativos serão propensos a sofrerem mutação nos cromossomos com grande aptidão. Analogamente, cromossomos com baixo grau de aptidão serão muito mais propensos a sofrerem mutação, aumentando o campo de exploração da busca. 13 2.3.4 Métodos de Substituição Uma vez que as soluções descendentes são criadas utilizando-se crossover e mutação, é necessário introduzi-las na população genitora. Há diversas maneiras de se realizar isso. Tendo em vista que os cromossomos-pais já tenham sido selecionados de acordo com suas aptidões, é esperado que os filhos (incluindo pais que não passaram por crossover) estejam entre os mais aptos da população e que tal população irá gradualmente, em média, aumentar sua aptidão. Algumas das técnicas de substituição mais comuns são descritas abaixo. 2.3.4.1 Apagar todos Este método apaga todos os membros da população corrente e os substitui com o mesmo número de cromossomos que foram criados. Este é provavelmente o método mais comum e o mais utilizado devido a sua relativa facilidade de implementação. 2.3.4.2 Regime Permanente Esta técnica apaga membros da população corrente e os substitui por novos membros. O número de membros apagados e substituídos, é um parâmetro deste método. Outra coisa que se deve levar em consideração nesta técnica é decidir quais membros serão eliminados da população corrente. 2.3.4.3 Regime Permanente sem Duplicatas É semelhante à técnica de Regime Permanente, porém, o algoritmo verifica se não serão adicionados cromossomos duplicados à população. Isso aumenta a sobrecarga computacional, mas pode significar que o espaço de busca será mais bem explorado. Os operadores utilizados na configuração do AG deste trabalho encontram-se resumidos na Tabela 1. 14 3 Estratégia DPNA-GA Para melhor entendimento dos resultados, a estratégia DPNA-GA será detalhada nesta seção. Assumindo-se que o robô possui um sensor de localização, que retorna sua posição espacial, ( , e um conjunto de sensores de distância, igualmente distribuídos, a estratégia de navegação baseada no DPNA-GA gera um percurso formado por eventos de deslocamentos locais até o objetivo final, ( . Em cada -ésimo evento de deslocamento, existe um objetivo local, ( ( ( ( , para o qual o robô se desloca. A escolha do objetivo local, ( , em cada -ésimo evento, é feita por um AG, o qual leva em consideração a posição atual do robô, ( , a distância para o objetivo final, , e os obstáculos detectados pelos sensores de distância. Todas as posições, ( , já visitadas pelo robô até o -ésimo deslocamento são armazenadas no vetor, , expresso por: [ ( ( ( ( ] [ ( ( ( ( ( ( ( ( ( ( ( ( ] (1) Esse vetor é utilizado na função de otimização do AG, evitando buscas em áreas já exploradas. O algoritmo termina quando a posição atual do robô é aproximadamente igual à posição do objetivo final, ou seja, ( , onde é um fator de tolerância; ou quando o número de eventos de deslocamentos ultrapassa um valor máximo predefinido, . O DPNA-GA pode ser utilizado tanto em ambientes estáticos quanto em ambientes dinâmicos, pois a cada -ésimo evento de deslocamento é feita uma nova busca por obstáculos e por um novo objetivo local, ( . 15 3.1 Etapa de Varredura Nesta etapa, o DPNA-GA força o robô a realizar uma varredura de no ambiente em torno do seu próprio eixo. A partir dessa varredura, cada -ésimo sensor, no -ésimo evento, retorna um sinal, ( , proporcional à distância (euclidiana) de alcance, , do sensor, onde ( { ( ( ( (2) e é a distância (euclidiana) medida pelo -ésimo sensor acoplado ao robô. Durante a varredura, o deslocamento angular, , pode ser expresso por (3) onde é o número de sensores de distância e representa a quantidade de deslocamentos angulares que robô pode efetuar em torno do seu próprio eixo, visando assim uma redução da resolução em detrimento de um reduzido número de sensores. Ao final do processo de varredura, o DPNA-GA gera um polígono, chamado de Polígono Delimitador (PD), formado por um conjunto de pontos expresso pelo vetor ( [ ( ( ( ] [ ( ( ( ( ( ( ( ( ( ] (4) onde e ( representa as coordenadas, no plano, do -ésimo ponto associado ao PD. Esse polígono será utilizado como uma espécie de delimitador do espaço de busca do algoritmo genético. Em outras palavras, os pontos (indivíduos) gerados dentro do polígono terão uma melhor aptidão em relação aos pontos gerados fora dele. Entretanto, não é apenas o fato de estar ou não inserido no interior do polígono que define a aptidão de cada indivíduo. São levadas em consideração também as distâncias entre o ponto gerado e os obstáculos 16 detectados pela varredura, dentre outros fatores. A Figura 2 ilustra o polígono gerado pelo DPNA-GA para o caso de e . Figura 2 - Exemplo do polígono delimitador (linha tracejada em azul) para caso onde 𝒏 𝟒 e 𝜶 𝟏𝟎 (𝒑 𝟗). 17 3.2 Detecção dos Obstáculos Ao final da etapa de varredura, é iniciada a etapa de detecção dos obstáculos, na qual, além do polígono delimitador, é gerado também um Polígono Virtual (PV), que compreende uma circunferência centrada em (centro do robô), de raio pouco menor que o alcance dos sensores, ou seja, (5) onde é um fator limitado em . O objetivo do PV é detectar apenas os pontos do PD que estão associados a obstáculos. Esses pontos são armazenados em um vetor, chamado aqui de . Assim, após esta etapa, é gerado um novo conjunto de pontos ( [ ( ( ( ] [ ( ( ( ( ( ( ( ( ( ] (6) onde ( ( ( ( ( (7) e . A função ( calcula a distância euclidiana entre dois pontos quaisquer, a qual pode ser expressa por ( √( ( (8) A Figura 3 demonstra visualmente, através de um exemplo, o PV (círculo tracejado na cor verde) e o conjunto de pontos representando os obstáculos, (asteriscos em vermelho). 18 3.3 Busca pelo Objetivo Local Nesta etapa, a estratégia de navegação proposta irá através de um AG, encontrar um possível objetivo local, , para o qual o robô irá se deslocar. Para cada -ésimo evento de deslocamento, o AG, com uma nova população, é executado para gerações. Os indivíduos são caracterizados pelo vetor ( [ ( ( ( ] [ ( ( ( ( ( ( ( ( ( ] (9) onde ( representa o -ésimo indivíduo da população de tamanho , associado a - ésima geração do -ésimo deslocamento do robô. Em outras palavras, os indivíduos são coordenadas bidimensionais no plano cartesiano de deslocamento. Figura 3 - Exemplo ilustrativo do PV (linha tracejada em verde) para 𝜼 𝟎 𝟎𝟏 e o conjunto de pontos, 𝐩𝑶, detectados (asteriscos em vermelho) que contornam os obstáculos. 19 Em cada geração , todos os indivíduos são gerados de acordo a restrição não-linear expressa por ( ( (10) onde ( ( ( ( (11) e ( (12) Essa restrição limita os indivíduos da população a uma circunferência de raio centrada na posição do robô no -ésimo instante, . A função de avaliação associada ao -ésimo indivíduo da -ésima geração no -ésimo deslocamento é expressa por ( ( ( ( ( ( ( (13) onde ( é a distância euclidiana entre o -ésimo indivíduo da -ésima geração e o objetivo final, , ou seja, ( ( ( (14) e ( é a menor distância euclidiana entre o -ésimo indivíduo da -ésima geração e todos os obstáculos encontrados. Assim, temos: ( ( ( para . (15) 20 Os termos ( , ( e ( podem ser considerados fatores de penalidade, os quais são utilizados para manipular a aptidão de cada -ésimo indivíduo gerado pelo AG. Caso nenhum obstáculo seja encontrado no -ésimo evento de deslocamento ( ), pode- se assumir que a função de avaliação é dada simplesmente por ( . Desse modo, temos: ( { (16) Partindo do princípio de que as circunferências com raio , representadas pelo vetor de centros, , são áreas já visitadas, pode-se caracterizar o fator de penalidade ( como ( { { } ( ( ( ) { } ( ( ( ) (17) onde é um número relativamente grande. Assim, caso exista algum indivíduo ( localizado dentro de alguma das circunferências do vetor , tal indivíduo será penalizado, reduzindo suas chances de ser escolhido. Por fim, a penalidade ( trata da localização dos indivíduos em relação ao PD. Assim, considerando ( o conjunto de pontos inseridos na área do polígono PD do - ésimo evento de deslocamento, temos: ( { ( ( ( ( (18) Nesse último caso, indivíduos que atenderem a essa penalidade terão pouquíssimas chances de sobreviverem para a próxima geração. A Figura 4 ilustra o cálculo da função de avaliação para um -ésimo indivíduo, ( . 21 A função de avaliação apresentada na Equação 13 é uma das principais contribuições deste trabalho. Essa equação segue o mesmo princípio da técnica de Campos Potenciais (Siegwart, et al., 2011), onde ( (distância euclidiana entre o -ésimo indivíduo e o objetivo final, ) representa uma força de atração em relação ao objetivo final e ( representa a maior força de repulsão entre o -ésimo indivíduo e os obstáculos encontrados. Ao final de gerações, é escolhido como objetivo local, ( , o indivíduo de menor valor (maior aptidão) retornado pela função de avaliação, associado ao -ésimo evento de deslocamento. 3.4 Deslocamento A etapa Deslocamento é caracterizada pela locomoção do robô ao objetivo local encontrado na etapa anterior. Após a locomoção do robô, um novo ponto de centro é gerado, ( , o qual é expresso por ( ( (19) Figura 4 - Exemplo ilustrando o cálculo da função de avaliação para um -ésimo indivíduo, ( , em relação ao objetivo final, , e os obstáculos, 22 onde é a tolerância admitida em relação ao objetivo local. Esta tolerância pode ser utilizada principalmente em robôs com restrição de locomoção, como no caso dos robôs não- holonômicos (Siegwart, et al., 2011). A Figura 5 apresenta uma seqüência de deslocamentos até o ponto final, . As etapas processadas pelo DPNA-GA estão apresentadas no Algoritmo 2 abaixo. Algoritmo 2 – DPNA-GA 1 2 ( 3 enquanto ( ( E faça 4 ( 5 ( ( ( 6 ( ( ( ( 7 ( ( ( 8 ( 9 10 fim enquanto Figura 5 - Exemplo ilustrando os deslocamento (𝑴 𝟔) feitos pelo robô até o ponto final, 𝒑𝒐𝒇. 23 4 Resultados 4.1 Visão geral Foram realizadas simulações em diferentes ambientes com o intuito de validar a técnica DPNA-GA e compará-la com outros procedimentos. As simulações foram implementadas em Matlab, utilizando-se uma versão atualizada do toolbox iRobot Create (Esposito, et al., 2011), o qual simula um robô circular não-holonômico com acionamento diferencial e quatro sensores de distância – um a cada . Na Tabela 1, são apresentados os parâmetros utilizados nas simulações. Os resultados são demonstrados nas figuras de Figura 6 a Figura 15, as quais apresentam o percurso do robô (linhas pretas), os eventos de deslocamento (círculos sobre o percurso), e os DPs associados a cada deslocamento (linhas tracejadas em azul). Nas figuras, o robô encontra-se estacionado no objetivo final (círculo vermelho), após ter percorrido um percurso partindo do ponto inicial (círculo azul). Tabela 1 - Parâmetros comuns utilizados nas simulações. Nº de sensores ( 4 Alcance dos sensores ( ) 3 m Deslocamento angular ( ) 10° Raio ( ) 1 m (Equação 17) 1000 Número de gerações ( ) 30 Tamanho da população ( ) 30 Codificação dos indivíduos Número real Método de seleção Estocástico uniforme Elitismo Sim Número de indivíduos na elite 2 Operador de cruzamento Uniforme Taxa de crossover 80% Operador de mutação Gaussiano (0, 1) 24 A Figura 6 apresenta o deslocamento do robô num ambiente moderadamente complexo, no qual foram necessários eventos de deslocamento para atingir o objetivo final. É possível notar que, nas primeiras instâncias de deslocamento ( ), o DPNA-GA retornou uma rota subótima, em que o robô foi fortemente atraído pelo objetivo. Entretanto, para , o algoritmo foi capaz de retornar um percurso bastante próximo do ótimo. No ambiente demonstrado na Figura 7, para alcançar o objetivo final, foi necessário que o robô entrasse numa espécie de garagem em formato de U. Nesse caso, o DPNA-GA utilizou eventos de deslocamento e retornou um caminho aproximadamente ótimo. Já na Figura 8, o robô foi submetido a uma situação oposta à anterior, ou seja, deveria sair do obstáculo em formato de U para poder alcançar o objetivo final. Nesse caso, o robô realizou eventos de deslocamento e, mais uma vez, percorreu um caminho aproximadamente ótimo. Figura 6 - Deslocamento do robô num ambiente moderadamente complexo. Num percurso próximo do ótimo, no qual foram necessários 𝑴 𝟐𝟒 eventos. 25 Figura 7 - Deslocamento do robô para o interior de um obstáculo em formato de U, realizando um percurso aproximadamente ótimo ( ). Figura 8 - Deslocamento do robô para o exterior de um obstáculo em formato de U, realizando um percurso aproximadamente ótimo ( . 26 Nas figuras Figura 9 e Figura 10, é demonstrado o desempenho do algoritmo de navegação para ambientes com obstáculos aleatoriamente espaçados. Nos dois casos, o robô percorreu caminhos bastante próximos dos ótimos, realizando e eventos de deslocamento, respectivamente. Figura 9 - Deslocamento do robô num ambiente aberto com obstáculos retangulares aleatoriamente espaçados. O robô realizou eventos de deslocamento para alcançar o objetivo final. 27 Figura 10 - Deslocamento do robô num ambiente aberto com obstáculos arredondados aleatoriamente espaçados. O robô realizou eventos de deslocamento para alcançar o objetivo final. As figuras Figura 11, Figura 12 e Figura 13 demonstram o desempenho do robô em ambientes que simulam corredores em diferentes formatos. Similarmente aos outros casos, o robô percorreu caminhos aproximadamente ótimos sem contato algum com as paredes dos ambientes, sendo necessários eventos de deslocamento para o ambiente em formato de L com uma curvatura (Figura 11), para o ambiente em formato de L com duas curvaturas (Figura 12) e para o ambiente em formato de L com quatro curvaturas (Figura 13). 28 Figura 11 - Deslocamento do robô num ambiente em formato de duto (estrutura em L com uma curvatura). O robô realizou eventos de deslocamento para alcançar o objetivo final. Figura 12 - Deslocamento do robô num ambiente em formato de duto (estrutura em L com duas curvaturas). O robô realizou eventos de deslocamento para alcançar o objetivo final. 29 Figura 13 - Deslocamento do robô num ambiente em formato de duto (estrutura em L com quatro curvaturas). O robô realizou eventos de deslocamento para alcançar o objetivo final. Com o intuito de observar o comportamento do DPNA-GA em ambientes dinâmicos, simulações foram realizadas utilizando os cenários apresentados nas figuras Figura 14 e Figura 15, com um obstáculo dinâmico aparecendo repentinamente em frente ao robô. Os resultados ilustram a rota realizada pelo robô na presença do novo obstáculo, confirmando a efetividade do método para ambientes dinâmicos. 30 Figura 14 - Deslocamento do robô para o interior de um obstáculo em formato de U, simulando o aparecimento repentino de um obstáculo dinâmico. O robô realizou eventos de deslocamento para alcançar o objetivo final. Figura 15 - Deslocamento do robô para o exterior de um obstáculo em formato de U, simulando o aparecimento repentino de um obstáculo dinâmico. O robô realizou eventos de deslocamento para alcançar o objetivo final. A Tabela 2 apresenta os tempos médios de execução do DPNA-GA para todos os ambientes simulados. Esses tempos foram calculados através das funções e presentes no Matlab. O comando inicia o cronômetro que mede o desempenho do programa, armazenando o tempo interno da execução do comando. Já o comando retorna o tempo decorrido desde a chamado da função . As simulações foram realizadas utilizando-se um computador com CPU de 64 bits, clock de 2,4 GHz e 4 GB de memória RAM. Os dados Obstáculo dinâmico Obstáculo dinâmico 31 confirmam que o tempo de execução do DPNA-GA é significativamente menor, quando comparado aos tempos das estratégias descritas na seção 1.1, apresentando uma diferença média de aproximadamente 300 segundos, para cenários similares aos descritos na Figura 6. Tal diferença está relacionada principalmente ao tamanho de cada indivíduo, o número de gerações e o tamanho da população, os quais, no DPNA-GA, estão limitados a 2, 30 e 30, respectivamente. Tabela 2 - Tempo médio de execução do algoritmo DPNA-GA para os ambientes simulados. Ambientes Tempo (segundos) Figura 6 51,0888 Figura 7 35,5072 Figura 8 28,5831 Figura 9 32,3145 Figura 10 34,0170 Figura 11 35,0304 Figura 12 20,3310 Figura 13 35,5635 Figura 14 35,8292 Figura 15 31,3140 4.2 Variação de parâmetros Tendo como objetivo validar o funcionamento do DPNA-GA (para ambientes estáticos e dinâmicos) em relação a sua robustez frente aos parâmetros genéticos, foram realizadas simulações em dois tipos de ambiente (ambientes e ) variando o número de gerações ( ), o tamanho da população ( ) e a taxa de cruzamento ( ). A Tabela 3 apresenta os parâmetros fixos utilizados nas simulações. Foram realizadas oito simulações: quatro para o ambiente (simulações , , e ) e quatro para o ambiente (simulações , , e ). 32 Tabela 3 - Parâmetros fixos comuns utilizados nas simulações. Nº de sensores ( 4 Alcance dos sensores ( ) 3 m Deslocamento angular ( ) 10° Raio ( ) 1 m (Equação 17) 1000 Codificação dos indivíduos Número real Método de seleção Estocástico uniforme Elitismo Sim Número de indivíduos na elite 2 Operador de cruzamento Uniforme Operador de mutação Gaussiano (0, 1) Para cada simulação, são apresentados nas tabelas Tabela 4 e Tabela 5 os dados do comprimento do percurso, , realizado pelo robô em metros (m), o tempo de processamento relativo ao percurso, , em segundos (s) para realização de todo deslocamento e o número de eventos de deslocamentos, . O deslocamento realizado pelo robô, em cada simulação, também é ilustrado graficamente nas figuras de Figura 16 a Figura 23. 33 Figura 16 - Deslocamento do robô na simulação ( , e ). Figura 17 - Deslocamento do robô na simulação ( , e ). 34 Figura 18 - Deslocamento do robô na simulação ( , e ). Figura 19 - Deslocamento do robô na simulação ( , e ). 35 Tabela 4 - Parâmetros e resultados das simulações realizadas no ambiente . Tamanho da população ( Número de gerações ( Taxa de cruzamento ( ) Comprimento do percurso ( ) Tempo de processamento ( ) Eventos de deslocamento ( ) 30 30 80% 16,52 m 39,31 s 17 10 30 80% 17,10 m 15,64 s 19 30 30 60% 18,46 m 40,60 s 19 10 30 60% 20,28 m 20,15 s 23 Para o caso do ambiente , cujos resultados estão descritos na Tabela 4 e ilustrados nas figuras Figura 16, Figura 17, Figura 18 e Figura 19, pode-se observar que a estratégia de navegação teve uma variação pouco significativa em relação ao número de eventos de deslocamento, , (valor médio de 19,5 e desvio padrão de 2,5) e o comprimento do percurso, , em metros (valor médio de 18,1 e desvio padrão de 1,67). Por outro lado, verifica-se que o tempo do processamento, dado em segundos (s), obteve variações maiores (valor médio de 28,92 e desvio padrão de 12,88). Figura 20 - Deslocamento do robô na simulação ( , e ). 36 Figura 21 - Deslocamento do robô na simulação ( , e ). Figura 22 - Deslocamento do robô na simulação ( , e ). 37 Figura 23 - Deslocamento do robô na simulação ( , e ). Tabela 5 – Parâmetros e resultados das simulações realizadas no ambiente . Tamanho da população ( Número de gerações ( Taxa de cruzamento ( ) Comprimento do percurso ( ) Tempo de processamento ( ) Eventos de deslocamento ( ) 30 10 80% 13,94 m 10,65 s 14 10 30 80% 13,19 m 11,25 s 14 30 10 60% 12,87 m 9,68 s 13 10 30 60% 12,93 m 10,16 s 13 Os maiores tempos ocorreram nas simulações e , nas quais o tamanho da população é de 30 indivíduos e os piores resultados estão associados à taxa de cruzamento de 60% indicando a necessidade de uma alta renovação dos indivíduos na população. Finalmente, outro ponto importante que deve ser observado é que a redução do tamanho da 38 população aumenta pouco o número de deslocamentos (de 17 para 19) e melhora muito o tempo total associado ao deslocamento (de 29,31 s para 15,64 s). Nas simulações associadas ao ambiente ( , , e ) o robô encontra um obstáculo dinâmico (retângulo vermelho) e precisa desviá-lo. O resultados dessas simulações estão apresentados na Tabela 5 e nas figuras Figura 20, Figura 21, Figura 22 e Figura 23. Diferentemente dos resultados para o ambiente , os dados associados ao comprimento do percurso, , (valor médio de 13,25 e desvio padrão de 0,47) o tempo de processamento, , (valor médio de 10,43 e desvio padrão de 0,67) e o número de eventos de deslocamento, , (valor médio de 13,5 e desvio padrão de 0,58) tiveram uma variação muito baixa em relação as alterações dos parâmetros genéticos. Este resultado pode ser explicado devido a alternância entre o tamanho da população, , e o número de gerações nas simulações , , e . Contrariando a tendência do ambiente , o ambiente proporcionou resultados menos satisfatórios para uma taxa de cruzamento de 80%. Esse resultado pode ser explicado pela simplicidade do ambiente em relação ao ambiente , uma vez que aquele, quando comparado a este, necessita de uma menor renovação dos indivíduos da população. Com base nos dados apresentados, pode-se verificar que o tempo de execução do DPNA-GA é menor que os tempos encontrados nas estratégias apresentadas por Samadi & Othman (2013) para ambientes semelhantes ao ambiente . Essa diferença está associada principalmente ao tamanho de cada indivíduo, ao número de gerações e ao tamanho da população que no DPNA-GA ficaram limitados em 2, 30 e 30, respectivamente. Ismail AL- Taharwa & Al-Weshah (2008), por exemplo, utilizaram populações de até 2000 indivíduos de tamanho em torno de 140 valores (no melhor caso) para um ambiente semelhante ao ambiente . Já Shi & Cui (2010), utilizaram uma população de 50 indivíduos associada a 2000 gerações. 39 4.3 Comparação com outros métodos Nesta seção, será realizada uma comparação entre o método DPNA-GA e os algoritmos propostos por Tuncer & Yildirim (2012) e Yongnian et al. (2012). Foram comparados quatro ambientes: os ambientes A (Figura 24) e B (Figura 25) foram propostos por Tuncer & Yildirim (2012), enquanto os ambientes C (Figura 26) e D (Figura 27Figura 26), foram propostos por Yongnian et al. (2012). O algoritmo proposto por Tuncer & Yildirim (2012) apresenta um novo operador de mutação genética aplicado ao planejamento dinâmico de trajetórias. Nele, é necessário conhecimento prévio da localização dos obstáculos dentro do mapa baseado em modelo de grid. No ambiente A, para que o algoritmo de Tuncer & Yildirim (2012) encontre uma solução de caminho ótimo, são realizadas 100 chamadas ao método, das quais 9 retornam caminhos ótimos, 78 retornam caminhos próximos ao ótimo e 13 retornam caminhos inviáveis. O tempo de solução para cada chamada é de 1,68 segundos, portanto, são necessários 168 segundos para o algoritmo de Tuncer & Yildirim (2012) encontrar uma solução ótima, em contraste com os 67 segundos apresentados pelo DPNA-GA, o qual apresenta um caminho muito próximo ao ótimo (diferença de 1,2 metros). A diferença entre as distâncias pode ser explicada pelo fato de o DPNA-GA fazer com que o robô tenda a se afastar das bordas dos obstáculos, evitando assim colisões nas laterais do robô. O ambiente B simula o aparecimento de um obstáculo no centro do mapa do ambiente A para demonstrar a capacidade de planejamento dinâmico do algoritmo. O algoritmo por Tuncer & Yildirim (2012) leva 69 segundos para encontrar a solução ótima de 24,71 metros de percurso, enquanto que o DPNA-GA leva em torno de 75 segundos para encontrar uma solução aproximadamente ótima de 27,31 metros. Nesse caso, deve-se levar em consideração o fato de que o DPNA-GA evita caminhos relativamente estreitos. A técnica proposta por Yongnian et al. (2012) apresenta um algoritmo genético modificado para planejamento de trajetória e é considerado um algoritmo de planejamento global (conhecimento do mapa é necessário) – em contraste com o DPNA-GA que é um algoritmo de planejamento local, ou seja, não necessita de conhecimento prévio da localização dos obstáculos. 40 No ambiente C, o DPNA-GA obteve vantagem com relação à distância e ao tempo. Já no ambiente D, o algoritmo proposto por Yongnian et al. (2012) foi superior em relação ao DPNA-GA, o que pode ser justificado pelo fato de que o DPNA-GA planeja em tempo real a trajetória do robô. Os dados das comparações entre os algoritmos são resumidos na Tabela 6. Figura 24 - Deslocamento realizado pelo robô no ambiente A. Comparação entre o método apresentado em por Tuncer & Yildirim (2012) (percurso em vermelho) e o DPNA-GA (percurso em preto). Figura 25 - Deslocamento realizado pelo robô no ambiente B. Comparação entre o método apresentado por Tuncer & Yildirim (2012) (percurso em vermelho) e o DPNA-GA (percurso em preto). 41 Figura 26 - Deslocamento realizado pelo robô no ambiente D. Comparação entre o método apresentado em por Yongnian et al. (2012) (percurso em vermelho) e o DPNA-GA (percurso em preto). Figura 27 - Deslocamento realizado pelo robô no ambiente D. Comparação entre o método apresentado em por Yongnian et al. (2012) (percurso em vermelho) e o DPNA-GA (percurso em preto). 42 Tabela 6 – Comparação entre os métodos. Ambientes Estratégias propostas em outros trabalhos (Tuncer & Yildirim, 2012; Yongnian, et al., 2012) DPNA-GA Distância percorrida Tempo Distância Percorrida Tempo A 24,6800 m 168,0000 s 25,8905 m 67,2969 s B 24,7100 m 69,0000 s 27,3064 m 75,2578 s C 15,6569 m 49,0000 s 14,7790 m 36,5487 s D 15,0711 m 49,0000 s 21,1726 m 56,7202 s 43 5 Conclusões Este trabalho teve como objetivo apresentar uma técnica de navegação com planejamento dinâmico para robôs móveis terrestres baseada em algoritmos genéticos, chamada de Dynamic Planning Navigation Algorithm optimized with Genetic Algorithm (DPNA-GA), e validá-la quanto a sua robustez e efetividade. Tomando como base as estratégias descritas na literatura, o DPNA-GA apresenta um esquema de navegação com planejamento local (aplicado a ambientes estáticos e dinâmicos), no qual não existe necessidade de conhecimento prévio do mapa a ser explorado. Além disso, o tamanho dos indivíduos independe da complexidade do ambiente, diminuindo assim custo computacional; e, portanto, sendo essa uma das vantagens em relação a métodos propostos em outros trabalhos. As simulações mostraram que o DPNA-GA alcança soluções de percursos viáveis para vários tipos de ambientes, diante de mudanças associadas aos parâmetros genéticos, mostrando assim uma robustez a um custo computacional relativamente menor quando comparado às outras estratégias de planejamento global e local. Para avaliar o funcionamento do algoritmo, primeiramente, o mesmo foi testado em ambientes diversificados (estáticos e dinâmicos), utilizando-se valores fixos para os parâmetros genéticos com o intuito de verificar sua efetividade em diferentes situações. As simulações demonstraram que, para os tipos de ambientes testados, a técnica se mostrou satisfatória, levando o robô em tempo hábil ao objetivo final em todas as situações de teste. Depois, foram feitos testes quanto à robustez frente à variação dos parâmetros genéticos. Para isso, foram realizadas simulações em dois tipos de ambiente (ambientes e ) alterando-se o número de gerações ( ), o tamanho da população ( ) e a taxa de cruzamento ( ). Mais uma vez a técnica DPNA-GA se mostrou eficaz em todas as configurações testadas, com o robô alcançando o objetivo em todos os casos, embora tenha havido vantagem de determinada configuração em relação às outras. Por fim, o algoritmo proposto neste trabalho foi comparado com outros dois métodos descritos na literatura (Tuncer & Yildirim, 2012; Yongnian, et al., 2012). Comparado com o algoritmo de Tuncer & Yildirim (2012), o DPNA-GA obteve uma desvantagem de 5% em relação à distância percorrida e uma vantagem de 60% em relação ao tempo de 44 processamento, para o ambiente do tipo A. Enquanto que, para o ambiente B, houve desvantagem por parte do DPNA-GA para ambos distância percorrida e tempo de processamento, com diferenças de 10% e 8%, respectivamente. Já quando comparado ao método apresentado por Yongnian et al. (2012), o DPNA-GA obteve vantagem tanto para a distância percorrida quanto para o tempo de processamento em se tratando do ambiente C, com diferenças de 6% e 25%, respectivamente. E, finalmente, para o ambiente do tipo D, houve desvantagem do DPNA-GA em relação ao método proposto por Yongnian et al. (2012) quanto aos dois parâmetros análisados: 29% de diferença em relação à distâcia percorrida e 14% em relação ao tempo de processamento. Com base nas análises dos dados apresentados nas simulações, a técnica de navegação proposta neste trabalho mostrou-se aplicável em diversas situações, não restando dúvidas quanto a sua aplicabilidade em casos práticos reais, sendo essa uma das sugestões para trabalhos futuros. Pretende-se ainda aprofundar o estudo da técnica, viabilizando-a para uso em ambientes ainda mais complexos, aumentando assim sua aplicabilidade. 45 Referências Bibliográficas Asama, H., Arai, T., Fukuda, T. & Hasegawa, T., 2002. Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem. Em: Distributed Autonomous Robotic Systems 5. Tokyo: Springer Japan, pp. 299-308. Bandyopadhyay, T., Liu, Z., Ang, M. H. & Seah, W. K. G., 2005. Visibility-based Exploration in Unknown Environment. Seattle, s.n. Boujelben, M., Rekik, C. & Derbel, N., 2012. Hierarchical fuzzy controller for a nonholonomic mobile robot. Barcelona, s.n. Chaari, I. et al., 2012. smartPATH: A hybrid ACO-GA algorithm for robot path planning. s.l., s.n., pp. 1-8. Cosío, F. A. & Neda, M. P. C., 2004. Autonomous robot navigation using adaptive potential fields. Mathematical and Computer Modelling, 40(9 - 10), pp. 1141-1156. Dong, D., Chen, C., Chu, J. & Tarn, T., 2012. Robust Quantum-Inspired Reinforcement Learning for Robot Navigation. IEEE/ASME Transactions on Mechatronics, 17(1), pp. 86-97. Esposito, J., Barton, O., Koehler, J. & Lim, D., 2011. http://www.usna.edu/. [Online] Available at: http://www.usna.edu/Users/weapsys/esposito/roomba.matlab/ [Acesso em 14 Dezembro 2012]. Fogel, L. J., Owens, A. J., e Walsh, M. J., 1966. Artificial Intelligence through Simulated Evolution. s.l.:Wiley. Gemeinder, M. & Gerke, M., 2003. GA-based path planning for mobile robot systems employing an active search algorithm. Applied Soft Computing, 3(2), p. 149–158. Gen, M. & Cheng, R., 2000. Genetic Algorithms and Engineering Optimization. s.l.:John Wiley & Sons. Holland, J. H., 1975. Adaptation in Natural and Artificial Systems. Second edition: MIT Press, 1992. ed. s.l.:University of Michigan Press. Hong, J. & Park, K., 2011. A new mobile robot navigation using a turning point searching algorithm with the consideration of obstacle avoidance. The International Journal of Advanced Manufacturing Technology , Volume 52, pp. 763-775. Ismail AL-Taharwa, A. S. & Al-Weshah, M., 2008. A Mobile Robot Path Planning Using Genetic Algorithm in Static Environment. Journal of Computer Science, 4(4), pp. 341-344. Juang, C.-F. & Chang, Y.-C., 2011. Evolutionary-Group-Based Particle-Swarm-Optimized Fuzzy Controller With Application to Mobile-Robot Navigation in Unknown Environments. Fuzzy Systems, IEEE Transactions on, 19(2), pp. 379-392. 46 Li, G.-H., Chang, C.-F. & Fu, L.-C., 2008. Navigation of a Wheeled Mobile Robot in Indoor Environment by Potential Field Based-Fuzzy Logic Method. Taipei, s.n. Marsili-Libelli, S. & Alba, P. S., 2000. Adaptive mutation in genetic algorithms. Soft Computing, Volume 4, pp. 76-80. Martinez-Soto, R., Castillo, O., Aguilar, L. & Baruch, I., 2012. Bio-inspired optimization of fuzzy logic controllers for autonomous mobile robots. s.l., s.n., pp. 1-6. Martinez-Soto, R., Castillo, O., Aguilar, L. T. & Baruch, I. S., 2012. Bio-inspired optimization of fuzzy logic controllers for autonomous mobile robots. Berkeley, s.n. Melanie, M., 1999. An Introduction to Genetic Algorithms. Londres: s.n. Paic-Antunovic, L. & Jakobovic, D., 2012. Evolution of automatic robot control with genetic programming. Opatija, s.n. Rechenberg, I., 1965. Cybernetic Solution Path of an Experimental Problem. s.l.:Ministry of Aviation, Royal Aircraft Establishment (U. K.). Rechenberg, I., 1973. Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution. s.l.:Frommann−Holzboog (Stuttgart). Samadi, M. & Othman, M. F., 2013. Global Path Planning for Autonomous Mobile Robot Using Genetic Algorithm. s.l., s.n., pp. 726-730. Sastry, K., Goldberg, D. & Kendall, G., 2005. Genetic Algorithms. Em: Search Methodologies. s.l.:Springer, pp. 97-125. Shamsinejad, P., Saraee, M. & Sheikholeslam, F., 2010. A new path planner for autonomous mobile robots based on genetic algorithm. s.l., s.n., pp. 115-120. Shi, C., Wangb, Y. & Yanga, J., 2010. A local obstacle avoidance method for mobile robots in partially known environment. Robotics and Autonomous Systems, Volume 58, pp. 425-434. Shi, P. & Cui, Y., 2010. Dynamic path planning for mobile robot based on genetic algorithm in unknown environment. s.l., s.n., pp. 4325-4329. Siegwart, R., Nourbakhsh, I. & Scaramuzza, D., 2011. Introduction to Autonomous Mobile Robots. s.l.:Mit Press. Toibero, J. M., Roberti, F., Carelli, R. & Fiorini, P., 2011. Switching control approach fo rstable navigation of mobile robots in unknown environments. Robotics and Computer-Integrated Manufacturing, Volume 27, p. 558–568. Tuncer, A. & Yildirim, M., 2012. Dynamic path planning of mobile robots with improved genetic algorithm. Computers \& Electrical Engineering , 38(6), pp. 1564-1572. Yamauchi, B., Schultz, A. & Adams, W., 2000. Integrating Exploration and Localization for Mobile Robots. Adaptive Behavior, 7(2). Yongnian, Z., Lifang, Z. & Yongping, L., 2012. An improved genetic algorithm for mobile robotic path planning. s.l., s.n., pp. 3255-3260. 47 Yun, S. C., Parasuraman, S. & Ganapathy, V., 2011. Dynamic path planning algorithm in mobile robot navigation. s.l., s.n., pp. 364-369. Zhang, L., Min, H., Wei, H. & Huang, H., 2012. Global path planning for mobile robot based on A*; algorithm and genetic algorithm. s.l., s.n., pp. 1795-1799.