Nature-Inspired Algorithms for Robotic Odour Search

Abstract

In nature, animals use the sense of smell to successfully locate sources of food, danger and mates. This sense may also be used in many other applications, such as locating victims in disaster scenarios or buried landmines, detecting concealed drugs or tracking the sources of pollutants and diseases. While currently many of these tasks are tackled with the help of trained dogs, the dangerous work conditions that are typically involved have been motivating the research community to propose methods to replace the animals with autonomous robots that can be monitored from safe distances. Yet, most of the existing approaches are manually designed and, due to the difficulty of the task at hand, tend to be sub-optimal. A promising approach would be not to hand-design, but rather to automatically produce those controllers though artificial intelligence methods.This thesis devises nature-inspired artificial intelligence methods (i.e., Evolutionary Algorithms) to evolve robots which, much like animals, are able to locate odour sources both individually and as a group. Similarly to most Evolutionary Robotics (ER) works, this thesis evolves the robotic controllers in simulation, as it is not only faster, cheaper and safer, but also enables testing scenarios that would be difficult to test in the real world. As such, one our first contributions is the development of a fast and realistic simulator for enabling the evolution of search strategies for odour source localisation. Moreover, due to the lack of ER works for odour source localisation, a study is conducted to design an adequate evaluation function for this task, i.e., one that provides a reliable fitness value with a minimum number of evaluations and a minimum amount of prior knowledge to prevent biasing the evolution.Four approaches were devised to evolve the robotic controllers. The first approach relies on Genetic Programming (GP) to produce human-readable search strategies from bio-inspired perceptions and actions. The ability to visually inspect the controllers is of great importance, as it not only enables verifying their soundness and adjusting their parameters to better suit particular scenarios, but also enables experimenters to draw insights from the search strategies, which may be used to further advance the knowledge of the field. However, GP often suffers from bloat, phenomenon that translates into the uncontrolled growth of the individuals without a corresponding increase in performance. Bloat will inevitably decrease the readability of the evolved controllers and increase their computational requirements. In this thesis, we propose Geometric Syntactic Genetic Programming (GSynGP), a new GP variant that produces compact syntax trees with equivalent performance to those evolved by the standard variant.The second approach is based on Infotaxis, a popular method to estimate the location of the source by fitting a gas dispersion model to environmental measurements. We propose Evolutionary Infotaxis, an evolutionary approach that addresses one of the main drawbacks of Infotaxis by using a Genetic Algorithm to automatically parametrise its gas dispersion model, optimising its performance in a given environment. The results show that, contrarily to common belief, the parameters that better approximate the environment are not necessarily the ones that lead to the best performance.The third approach relies on GSynGP to evolve tree-based controllers that combine infotactic behaviours with bio-inspired building blocks. The experimental results show that this approach outperforms both its counterparts and, the analysis of the evolved solutions shows that Infotaxis is better suited for finding and reacquiring the odour plume, while bio-inspired behaviours are more efficient for tracking it to its source. Finally, a multi-robot evolutionary approach is devised and the influence of the number of robots and of cooperation is investigated. Furthermore, the multi-robot approach is compared to the single-robot approaches, showing that using multiple robots provides better results than even the most complex single-robot approach. Preliminary tests of the best evolved controllers are conducted in a wind-tunnel, qualitatively validating the simulation-based results. One of the advantages of their white-box nature is also demonstrated by manually adjusting their parameters to better cope with the differences between the simulated environment and the wind tunnel.

Na natureza, os animais usam o olfato para detectar e localizar fontes de alimento, perigo e outros membros da sua espécie. O sentido olfativo pode ser usado em muitas outras aplicações, tais como localizar pessoas desaparecidas, detectar narcóticos ou encontrar fontes de poluentes e doenças. Atualmente muitas destas tarefas são realizadas com o auxílio de cães, mas os riscos inerentes têm motivado a comunidade científica a propor métodos baseados em robôs autónomos que possam ser monitorizados a partir de distâncias seguras. No entanto, a maioria das abordagens existentes são desenhadas manualmente e, devido à dificuldade desta tarefa, tendem a ser sub-ótimas. Um caminho promissor seria recorrer a métodos de inteligência artificial para produzir estratégias de procura.Esta tese propõe métodos de inteligência artificial inspirados na natureza (i.e., Algoritmos Evolucionários (AE)) para evoluir robôs que, tal como os animais, são capazes de localizar fontes de odor, tanto individualmente, como trabalhando em equipa. À semelhança da maioria dos trabalhos de Robótica Evolucionária (RE), os controladores robóticos são evoluídos em simulação, dado ser uma forma mais rápida, segura e com menores custos, permitindo ainda testar cenários que seriam difíceis de testar no mundo real. Como tal, uma das nossas contribuições é o desenvolvimento de um simulador rápido e realista para permitir a evolução de estratégias de procura de fontes de odor. Além disso, devido à escassez de trabalhos de RE na procura de fontes de odor, realizou-se um estudo para desenhar uma função de avaliação adequada para esta tarefa, i.e., uma função que produz um valor de aptidão confiável com o mínimo de avaliações e contendo uma quantidade mínima de conhecimento prévio para evitar enviesar a evolução.Esta tese propões quatro abordagens para evoluir controladores robóticos. A primeira recorre a Programação Genética (PG) para produzir estratégias de procura de fontes de odor interpretáveis por humanos, a partir the percepções e acções bioinspiradas. A capacidade de inspecionar visualmente os controladores é de extrema relevância, uma vez que permite verificar sua solidez e refinar os seus parâmetros para cenários específicos. Para além disso, através da análise dos controladores é possível extrair conhecimento para melhorar as estratégias de procura desenhadas manualmente, avançando o conhecimento da área. No entanto, a PG sofre frequentemente de bloat, um fenómeno que se traduz no crescimento descontrolado dos indivíduos sem um correspondente aumento de desempenho, que diminui a sua legibilidade e aumenta os seus requisitos computacionais. Nesta tese propomos um novo algoritmo de PG (GSynGP) que efectua operações de recombinação geométricas no espaço sintático, produzindo indivíduos compactos com desempenho equivalente aos evoluídos pela PG tradicional.A segunda abordagem baseia-se na Infotaxis, uma abordagem com grande popularidade para estimar a localização de fontes de odor com recurso a modelos de dispersão de gás. A abordagem que propomos, Evolutionary Infotaxis, utiliza um Algoritmo Genético para parametrizar o modelo de dispersão de gás da Infotaxis, optimizando a sua performance num ambiente específico e solucionando uma das suas principais desvantagens (i.e., a necessidade de parametrizar o modelo de dispersão de gás manualmente). Os resultados experimentais mostram que, contrariamente ao expectável, os parâmetros que melhor se aproximam do ambiente não são necessariamente os que levam ao melhor desempenho.A terceira abordagem proposta recorre ao GSynGP para evoluir controladores white-box que combinam comportamentos infotáticos com percepções e ações bioinspiradas. Os resultados experimentais mostram que esta abordagem supera ambos os métodos que lhe deram origem e, através da análise dos controladores, é possível verificar que a Infotaxis é mais adequada para (re)encontrar a pluma de odor, enquanto os comportamentos bioinspirados são mais eficientes para segui-la até à sua fonte.Propomos ainda uma abordagem evolucionária multi-robô, estudando a influência do número de robôs e da cooperação no desempenho da procura. Além disso, a abordagem multi-robô é comparada com as abordagens que usam um único robô, mostrando que o uso de vários robôs origina melhores resultados do que todas as abordagens com um único robô.Finalmente, realizamos testes preliminares dos controladores num túnel de vento, validando qualitativamente os resultados obtidos em simulação. Uma das vantagens da natureza white-box dos controladores é também demonstrada, permitindo o ajuste manual dos seus parâmetros para lidar melhor com as diferenças entre o ambiente simulado e o túnel de vento.