Worst-Case Pursuit-Evasion using random walk for multiply connected environment

• Daniel Augusto Santos Franco UFS
• Elyson Ádan Nunes Carvalho UFS
• José Gilmar Nunes De Carvalho Filho UFS
• Lucas Molina UFS
• Eduardo Oliveira Freire UFS

Resumo

The clearing problem and search and rescue are examples of tasks that can be modeled as pursuit-evasion. The problem of pursuit-evasion has been extensively studied, however, there are still open questions. This paper highlights the problem of worst-case for pursuit-evasion with limited sensor range and proposes a method based on random walk that solves this problem in simply and multiply connected environments, it was tested for both environments and with several number of robots. The method was also compared with a method that solves the worst-case of pursuit-evasion with limited sensor range, and the proposed method showed good results, being able to solve for different environments, with fewer robots than the method compared.

Palavras-chave: Pursuit-evasion, random walk, clearing problem