Adversarial Planning for Multi-Agent Pursuit-Evasion Games in Partially Observable Euclidean Space

We describe a heuristic search technique for multi-agent pursuit-evasion games in partially observable Euclidean space where a team of trackers attempt to minimize their uncertainty about an evasive target. Agents' movement and observation capabilities are restricted by polygonal obstacles, while each agent's knowledge of the other agents is limited to direct observation or periodic updates from team members. Our polynomial-time algorithm is able to generate strategies for games in continuous two-dimensional Euclidean space, an improvement over past algorithms that were only applicable to simple gridworld domains. We demonstrate that our algorithm is tolerant of interruptions in communication between agents, continuing to generate good strategies despite long periods of time where agents are unable to communicate directly. Experiments also show that our technique generates effective strategies quickly, with decision times of less than a second for reasonably sized domains with six or more agents.