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.

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

Amigoni F.;
2018-01-01

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.
2018
Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Limited visibility; Min-max search; Pursuit-evasion
File in questo prodotto:
File Dimensione Formato  
pic103.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 1.6 MB
Formato Adobe PDF
1.6 MB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1099128
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 11
social impact