Problema de perseguição-evasão de pior caso em ambientes limitados baseado em Random Walk

Abstract

One of the motivations to use robots is their capacity to complete dangerous tasks without exposing humans, such as search and rescue tasks. In these tasks, it is common to use multiple robots for robustness or because the task is impossible to be completed with only one robot. One of these tasks is the pursuit-evasion. To complete this task the robots must capture the evader that is inside of an area of interest. If the conditions of the task are that the evader has infinite velocity and complete knowledge of the environment, while the pursuers have limited velocity and without knowledge of the environment, it is considered the worst-case pursuitevasion, and this work proposes a method to solve it. The robots in this method have a random walk-based movement so the method has a guarantee of completing the task if it is possible to complete it and the demonstration is also shown in this work. This work also proposes two polarizations for the random walk-based moviment to reduce the mean time to complete the task. To validate the method a simulation environment is implemented, where the method was tested. In this environment is also tested the polarizations proposed and how the number of robots influenced the mean time of the system to complete the task. The proposed method is capable of finalizing the task in a finite time if there are enough robots to be able to complete the task.