PURSUIT
Pursuit and Evasion in Imperfect-Information Environments
We are developing formalisms and algorithms for game-tree search in partially-observable Euclidean space, and implementation and tests in a scenario where a multi-agent team of tracking agents pursues a target agent that wants to evade the tracking agents. Our formalism 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).
We have used the above formalism to develop a game-tree search algorithm and a heuristic evaluation function that solves a relaxation of the problem, and have conducted preliminary experimental studies on 500 randomly generated trials. In our experiments, tracking agents were more than twice as likely keep track of the target agent's location than with the strategies generated by heuristics that computed estimates of the target's possible locations.
Project lead: Dr. Dana Nau.
For additional information, please contact Dr. Dana Nau or Dr. Uger Kuter.
Last updated: November 2009 by John Dickerson.
Publication links contingent upon publication!
This page will be updated as our work enters print. For information about receiving draft publications, technical reports, and conference presentations, please do not hesitate to contact team members.
The following sections may include links to restricted access material. Please do not hesitate to contact a group member for instructions regarding how to obtain a username and password.
Presentation links contingent upon publication!
The following sections may include links to restricted access material. Please do not hesitate to contact a group member for instructions regarding how to obtain a username and password.
Software links contingent upon publication!