@conference {18864, title = {Strategy generation in multi-agent imperfect-information pursuit games}, series = {AAMAS {\textquoteright}10}, year = {2010}, month = {2010///}, pages = {947 - 954}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, organization = {International Foundation for Autonomous Agents and Multiagent Systems}, address = {Richland, SC}, abstract = {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--- {\textbullet} A formalism that combines geometric elements (agents{\textquoteright} locations and trajectories and observable regions, and obstacles that restrict mobility and observability) with game-theoretic elements (information sets, utility functions, and strategies). {\textbullet} A recursive formula for information-set minimax values based on our formalism, and a implementation of the formula in a game-tree search algorithm. {\textbullet} 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. {\textbullet} 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{\textquoteright}s location at the end of the game than with the strategies generated by heuristics that compute estimates of the target{\textquoteright}s possible locations.}, keywords = {game tree search, multi-agent planning, visibility-based pursuit-evasion games}, isbn = {978-0-9826571-1-9}, url = {http://dl.acm.org/citation.cfm?id=1838206.1838333}, author = {Raboin,Eric and Nau, Dana S. and Kuter,Ugur and Gupta, Satyandra K. and Svec,Petr} }