research-article

Anytime algorithms for multi-agent visibility-based pursuit-evasion games

Authors:

Viliam Lisý,

Branislav Bošanský,

Michal PěchoučekAuthors Info & Claims

AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3

Pages 1301 - 1302

Published: 04 June 2012 Publication History

Get Access

Abstract

We investigate algorithms for playing multi-agent visibility-based pursuit-evasion games. A team of pursuers attempts to maintain visibility contact with an evader who actively avoids tracking. We aim for applicability of the algorithms in real-world scenarios; hence, we impose hard constraints on the run-time of the algorithms and we evaluate them in a simulation model based on a real-world urban area. We compare Monte-Carlo tree search (MCTS) and iterative deepening minimax algorithms running on the information-set tree of the imperfect-information game. The experimental results demonstrate that both methods create comparable good strategies for the pursuer, while the later performs better in creating the evader's strategy.

References

[1]

P. Ciancarini and G. P. Favini. Monte Carlo tree search in Kriegspiel. Artif. Intell., 174:670--684, July 2010.

Digital Library

Google Scholar

[2]

L. Kocsis and C. Szepesvári. Bandit based monte-carlo planning. In ECML, pages 282--293, 2006.

Digital Library

Google Scholar

[3]

E. Raboin, D. Nau, U. Kuter, and S. Gupta. Strategy generation in multi-agent imperfect-information pursuit games. In AAMAS, pages 947--954, 2010.

Digital Library

Google Scholar

Cited By

View all

Quattrini Li AFioratto RAmigoni FIsler VAndre EKoenig SDastani MSukthankar G(2018)A Search-Based Approach to Solve Pursuit-Evasion Games with Limited Visibility in Polygonal EnvironmentsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237951(1693-1701)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237951
Lisý VLanctot MBowling MWeiss GYolum PBordini RElkind E(2015)Online Monte Carlo Counterfactual Regret Minimization for Search in Imperfect Information GamesProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2772887(27-36)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2772887
Novák PKomenda ALisý VBošanský Bčáp MPěchouček M(2012)Tactical operations of multi-robot teams in urban warfare (demonstration)Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 310.5555/2343896.2344067(1473-1474)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.5555/2343896.2344067

Index Terms

Anytime algorithms for multi-agent visibility-based pursuit-evasion games
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Multi-player pursuit-evasion games with one superior evader

Inspired by the hunting and foraging behaviors of group predators, this paper addresses a class of multi-player pursuit-evasion games with one superior evader, who moves faster than the pursuers. We are concerned with the conditions under which the ...
Uncertain pursuit-evasion game
Abstract
Pursuit-evasion game deals with the situation in which a pursuer tries to catch an evader. Taking into account the subjectivity of the players’ strategies and the fact that the noise of system state does not obey the statistical regularity, this ...
Existence of Value in Generalized Pursuit-Evasion Games

The results presented here relate both to a pursuit-evasion game and to a game of fixed time duration. The dynamics of both games is governed by a system of differential inclusions, and the state variables x, y have to satisfy some general type ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3

June 2012

376 pages

ISBN:0981738133

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 04 June 2012

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS 12

Sponsor:

The International Foundation for Autonomous Agents and Multiagent Systems

AAMAS 12: International Conference on Autonomous Agents and Multiagent Systems

June 4 - 8, 2012

Valencia, Spain

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
158
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Quattrini Li AFioratto RAmigoni FIsler VAndre EKoenig SDastani MSukthankar G(2018)A Search-Based Approach to Solve Pursuit-Evasion Games with Limited Visibility in Polygonal EnvironmentsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237951(1693-1701)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237951
Lisý VLanctot MBowling MWeiss GYolum PBordini RElkind E(2015)Online Monte Carlo Counterfactual Regret Minimization for Search in Imperfect Information GamesProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2772887(27-36)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2772887
Novák PKomenda ALisý VBošanský Bčáp MPěchouček M(2012)Tactical operations of multi-robot teams in urban warfare (demonstration)Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 310.5555/2343896.2344067(1473-1474)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.5555/2343896.2344067

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Multi-player pursuit-evasion games with one superior evader

Uncertain pursuit-evasion game

Existence of Value in Generalized Pursuit-Evasion Games

Comments

Information

Published In

Sponsors

In-Cooperation

Publisher

Publication History

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations