Agent Subset Adversarial Search for Complex Non-cooperative Domains
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F10%3A00173920" target="_blank" >RIV/68407700:21230/10:00173920 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Agent Subset Adversarial Search for Complex Non-cooperative Domains
Original language description
We investigate reduction of the complexity of a multi-agent adversarial search in the domain of n-player games. We describe a method that decomposes the game into a set of smaller overlapping sub-games, solves each sub-game separately, and then combinesthe results into a global solution. This way, the exponential dependence of the adversarial search complexity on the number of agents can be reduced to polynomial. Still, the proposed method performs well in the domains with sparse agents' interactions.The method can be used with a generic adversarial search algorithm. For the experimental evaluation, we implement it on top of an existing adversarial search algorithm designed for complex domains and we evaluate its performance on a game, which is a model of a humanitarian relief operation in conflict environment. The results show that the method often finds the same solutions as the complete search, but the search efficiency is significantly improved.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/ME09053" target="_blank" >ME09053: Adversarial planning in complex dynamic domains</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2010
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the IEEE Conference on Computational Intelligence and Games 2010
ISBN
978-1-4244-6297-1
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
—
Publisher name
IEEE
Place of publication
New Jersey
Event location
Copenhagen
Event date
Aug 18, 2010
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—