Solving large-scale pursuit-evasion games using pre-trained strategies
Pursuit-evasion games on graphs model the coordination of police forces chasing a fleeing felon in real-world urban settings, using the standard framework of imperfect-information extensive-form games (EFGs). In recent years, solving EFGs has been largely dominated by the Policy-Space Response Oracl...
Saved in:
Main Authors: | , , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2023
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/9047 https://ink.library.smu.edu.sg/context/sis_research/article/10050/viewcontent/26369_Pursuit_evasion_pvoa.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-10050 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-100502024-07-25T07:41:33Z Solving large-scale pursuit-evasion games using pre-trained strategies LI, Shuxin WANG, Xinrun ZHANG, Youzhi XUE, Wanqi CERNY, Jakub AN, Bo Pursuit-evasion games on graphs model the coordination of police forces chasing a fleeing felon in real-world urban settings, using the standard framework of imperfect-information extensive-form games (EFGs). In recent years, solving EFGs has been largely dominated by the Policy-Space Response Oracle (PSRO) methods due to their modularity, scalability, and favorable convergence properties. However, even these methods quickly reach their limits when facing large combinatorial strategy spaces of the pursuit-evasion games. To improve their efficiency, we integrate the pre-training and fine-tuning paradigm into the core module of PSRO -- the repeated computation of the best response. First, we pre-train the pursuer's policy base model against many different strategies of the evader. Then we proceed with the PSRO loop and fine-tune the pre-trained policy to attain the pursuer's best responses. The empirical evaluation shows that our approach significantly outperforms the baselines in terms of speed and scalability, and can solve even games on street maps of megalopolises with tens of thousands of crossroads -- a scale beyond the effective reach of previous methods. 2023-02-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9047 info:doi/10.1609/aaai.v37i10.26369 https://ink.library.smu.edu.sg/context/sis_research/article/10050/viewcontent/26369_Pursuit_evasion_pvoa.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Multiagent Learning Energy Environment & Sustainability Security Representation Learning Artificial Intelligence and Robotics Theory and Algorithms |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Multiagent Learning Energy Environment & Sustainability Security Representation Learning Artificial Intelligence and Robotics Theory and Algorithms |
spellingShingle |
Multiagent Learning Energy Environment & Sustainability Security Representation Learning Artificial Intelligence and Robotics Theory and Algorithms LI, Shuxin WANG, Xinrun ZHANG, Youzhi XUE, Wanqi CERNY, Jakub AN, Bo Solving large-scale pursuit-evasion games using pre-trained strategies |
description |
Pursuit-evasion games on graphs model the coordination of police forces chasing a fleeing felon in real-world urban settings, using the standard framework of imperfect-information extensive-form games (EFGs). In recent years, solving EFGs has been largely dominated by the Policy-Space Response Oracle (PSRO) methods due to their modularity, scalability, and favorable convergence properties. However, even these methods quickly reach their limits when facing large combinatorial strategy spaces of the pursuit-evasion games. To improve their efficiency, we integrate the pre-training and fine-tuning paradigm into the core module of PSRO -- the repeated computation of the best response. First, we pre-train the pursuer's policy base model against many different strategies of the evader. Then we proceed with the PSRO loop and fine-tune the pre-trained policy to attain the pursuer's best responses. The empirical evaluation shows that our approach significantly outperforms the baselines in terms of speed and scalability, and can solve even games on street maps of megalopolises with tens of thousands of crossroads -- a scale beyond the effective reach of previous methods. |
format |
text |
author |
LI, Shuxin WANG, Xinrun ZHANG, Youzhi XUE, Wanqi CERNY, Jakub AN, Bo |
author_facet |
LI, Shuxin WANG, Xinrun ZHANG, Youzhi XUE, Wanqi CERNY, Jakub AN, Bo |
author_sort |
LI, Shuxin |
title |
Solving large-scale pursuit-evasion games using pre-trained strategies |
title_short |
Solving large-scale pursuit-evasion games using pre-trained strategies |
title_full |
Solving large-scale pursuit-evasion games using pre-trained strategies |
title_fullStr |
Solving large-scale pursuit-evasion games using pre-trained strategies |
title_full_unstemmed |
Solving large-scale pursuit-evasion games using pre-trained strategies |
title_sort |
solving large-scale pursuit-evasion games using pre-trained strategies |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2023 |
url |
https://ink.library.smu.edu.sg/sis_research/9047 https://ink.library.smu.edu.sg/context/sis_research/article/10050/viewcontent/26369_Pursuit_evasion_pvoa.pdf |
_version_ |
1814047717202067456 |