Paper Info
Title
Strategy generation in multi-agent imperfect-information pursuit games
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--- • 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.
Year
DOI
Venue
2010
10.5555/1838206.1838333
AAMAS
Keywords
Field
DocType
tracking agent,multi-agent imperfect-information pursuit game,quick lookahead search,geometric element,recursive formula,heuristic evaluation function,strategy generation,game-theoretic element,target agent,game-tree search,game-tree search algorithm,imperfect information
Minimax,Mathematical optimization,Observability,Heuristic,Search algorithm,Computer science,Evaluation function,Heuristics,Multi-agent planning,Artificial intelligence,Machine learning,Recursion
Conference
Citations 
PageRank 
References 
5
0.72
25
Authors
5
Name
Order
Citations
PageRank
Eric Raboin1223.06
Dana S Nau24290531.46
Ugur Kuter3126474.54
Satyandra K Gupta468777.11
Petr Svec5626.68