Coordinated exploration for labyrinthine environments with application to the Pursuit-Evasion problem

In this paper, we consider the following problem: a group of robots have to explore a labyrinthine environment and find an intruder if need be. Such a problem has been already studied in mainly two different aspects. On the one hand, the "prey predators" problem has been proposed for the first time by [BJD86]: the prey and the predators, i.e. the agents, share a common environment which is represented by a mere grid. The hunt is simulated and the agents that are autonomous processes can move horizontally or vertically all the time. Quite obviously, the goal of the prey is to escape as long as possible whereas the predators have to capture the prey as fast as possible. Therefore, the "prey predators" problem is an interesting testbed for competing agents and coordination protocols. Indeed, because each agent does not perceive all the environment, and can have incomplete or inconsistent knowledge about the other agents, many challenging issues have to be tackled: which information has to be communicated?