Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Over the years,there is a growing demand for the use of robots toassis thu mans in their tasks, especially those involving risks,such as search and rescue. For this reason, coordination amongs everal robots has been acommonoption,and one of the ways to study and model these applications involves the problem of pursuit-evasion. This work proposes the use of an evolutionary robotics approach to solve the worst-case pursuit- evasion problem, in which evaders are considered arbitrarily fast and omniscient, while pursuers have limited sensing and communication capabilities. In this research,no prior knowledge is considered regarding environments, which retreated as discrete and canbe multiply connected. A decentralized multi-robot control system is proposed, based on a nite state machine with state-action mapping de ned by means of a genetic algorithm, applied in terms of evolutionary robotics. There sults show the proposed system is able to decontaminate several typesof maps, but does not generalize to all initial conditions,due to the incompleteness in the automaton mapping.Therefore, a complementary approach is presented in which draws a reused alternatively with the evolved automaton, indicating random actions in cases of states not su ciently visited during evolution. This investigation led to better results, indicating ways for future work.Ina ddition, a comparative analysis of the evolutionary approach is also carried out with another solution method for the same problem, with advantages and disadvantages of each work being discussed. / Com o passar dos anos, é crescente a demanda pela utilização de robôs em tarefas de auxílio aos seres humanos, em especial àquelas que envolvam riscos, como resgates e buscas. Para tais atividades, tem sido comum a utilização do trabalho conjunto e coordenado entre vários robôs, e uma das formas de estudar e modelar estas aplicações envolve o problema de perseguição-evasão. Este trabalho propõe o uso de uma abordagem baseada em robótica evolutiva para solucionar o problema de perseguição-evasão de pior caso, em que os evasores são considerados infinitamente rápidos e oniscientes, enquanto os perseguidores têm capacidade de sensoriamento e comunicação limitados. Nesta pesquisa, não é considerado nenhum conhecimento prévio a respeito dos ambientes, que são tratados de forma discreta e podem ser multiplamente conectados. É proposto um sistema de controle descentralizado para múltiplos robôs baseado em uma máquina de estados finitos cujo mapeamento de estados em ações é definido por meio de um algoritmo genético, aplicado nos termos da robótica evolutiva. Os resultados mostram que o sistema proposto é capaz de descontaminar significativos mapas, porém sem robustez para todas as inicializações de posição, devido à incompletude na definição do mapeamento do autômato. Por isso, é apresentada uma abordagem complementar em que o método random walk é utilizado em conjunto com o autômato evoluído, indicando ações aleatórias nos casos de estados pouco visitados durante a evolução, o que contribuiu para melhoria dos resultados e aponta caminhos para trabalhos futuros. Além disso, é também realizada uma análise comparativa da abordagem evolutiva proposta com outro método de solução para o mesmo problema, sendo discutidas vantagens e desvantagens de cada trabalho.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / One of the greatest reasons to use robotics rather than human beings is to avoid hazardous situations such as activities related to search, surveillance and rescue. The pursuit-evasion problem is a fundamental theoretical base to apply robotics on these cases. This dissertation presents an approach to solve the pursuit-evasion problem with no previous knowledge of the map, which must be simply connected, using multi-robots systems with limited sensing. The approach is based on the random walk, since it is a mathematical formalization probabilistically complete, considering plane and obstacle free environments that shall be treated discretely through a regular occupation grid. This dissertation also presents a variation of this approach, though it considers random walk probabilities, to enhance the previous approach, decreasing the amount of iterations needed to solve the problem. In order to validate what is proposed, a discrete multi-robot simulation environment was developed. Finally, the results obtained on the tests that were performed and possible future works that could improve this approach are discussed. / Uma das principais motivações do uso de sistemas robóticos em detrimento de seres humanos é evitar situações de risco, como as encontradas em atividades de busca, vigilância e resgate. O problema de perseguição-evasão é uma base teórica fundamental para a aplicação da robótica nestes casos. Esta dissertação apresenta uma abordagem para solução do problema de perseguição-evasão sem um conhecimento a priori do mapa, que deverá ser simplesmente conectado, através da coordenação de múltiplos robôs com visão limitada. A abordagem aqui proposta é baseada na random walk, por esta ser uma formalização matemática probabilisticamente completa, sendo contemplados ambientes planos e sem obstáculos, que serão tratados discretamente por meio de uma grade de ocupação regular. Ainda nesta dissertação, foi proposta uma variação dessa abordagem, porém com a ponderação de probabilidades da random walk, com o objetivo de aprimorar a anterior, diminuindo número de iterações necessárias para solução do problema. Para a validação da abordagem proposta, foi desenvolvido um ambiente de simulações para abordagens discretas de múltiplos robôs. Finalmente, são discutidos os resultados obtidos nos testes realizados e propostos trabalhos futuros para melhoria desta abordagem.