Strategy generation in multi-agent imperfect-information pursuit games

We describe a formalism and algorithms for game-tree search in partially-observable Euclidean space, and implementation and tests in a scenario where a multi-agent team, called tracking agents, pursues a target agent that wants to evade the tracking agents. Our contributions include--- • A formalism that combines geometric elements (agents' locations and trajectories and observable regions, and obstacles that restrict mobility and observability) with game-theoretic elements (information sets, utility functions, and strategies). • A recursive formula for information-set minimax values based on our formalism, and a implementation of the formula in a game-tree search algorithm. • A heuristic evaluation function for use at the leaf nodes of the game-tree search. It works by doing a quick lookahead search of its own, in a relaxed version of the problem. • Experimental results in 500 randomly generated trials. With the strategies generated by our heuristic, the tracking agents were more than twice as likely to know the target agent's location at the end of the game than with the strategies generated by heuristics that compute estimates of the target's possible locations.