A search-based approach to solve pursuit-evasion games with limited visibility in polygonal environments

Alberto Quattrini Li, Francesco Amigoni, Raffaele Fioratto, Volkan Isler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

A pursuit-evasion game is a non-cooperative game in which a pursuer tries to detect or capture an adversarial evader. We study a pursuit-evasion game which takes place in a known polygonal environment. The goal of the pursuer is to capture the evader by moving onto its location. The players can observe each others' locations only if they can "see" each other - i.e., if the line segment connecting their locations lies entirely inside the polygonal environment. The complexity of representing the information available to the players at a given time makes solving pursuit-evasion games with visibility limitations difficult. We represent the state of the game using an efficient visibility-based decomposition of the environ-. ment paired with a more classical grid-based decomposition. The optimal players' strategies are computed using a min-max search algorithm improved with specific speedup techniques that preserve optimality. We show that our decomposition is complete for a rash evader, which hides from the pursuer and does not move from its hiding location when the pursuer is not visible. Simulations in realistic indoor environments and comparison with a Monte Carlo tree search algorithm validate our approach.

Original languageEnglish (US)
Title of host publication17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1693-1701
Number of pages9
ISBN (Print)9781510868083
StatePublished - Jan 1 2018
Event17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018 - Stockholm, Sweden
Duration: Jul 10 2018Jul 15 2018

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume3
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Other

Other17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
CountrySweden
CityStockholm
Period7/10/187/15/18

Keywords

  • Limited visibility
  • Min-max search
  • Pursuit-evasion

Fingerprint Dive into the research topics of 'A search-based approach to solve pursuit-evasion games with limited visibility in polygonal environments'. Together they form a unique fingerprint.

  • Cite this

    Li, A. Q., Amigoni, F., Fioratto, R., & Isler, V. (2018). A search-based approach to solve pursuit-evasion games with limited visibility in polygonal environments. In 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018 (pp. 1693-1701). (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; Vol. 3). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).