Efficient solutions for joint activity based security games: fast algorithms, results and a field experiment on a transit system
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 605514860 | ||
| 003 | CHVBK | ||
| 005 | 20210128100706.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 210128e20150901xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1007/s10458-014-9270-4 |2 doi |
| 035 | |a (NATIONALLICENCE)springer-10.1007/s10458-014-9270-4 | ||
| 245 | 0 | 0 | |a Efficient solutions for joint activity based security games: fast algorithms, results and a field experiment on a transit system |h [Elektronische Daten] |c [Francesco Delle Fave, Eric Shieh, Manish Jain, Albert Jiang, Heather Rosoff, Milind Tambe, John Sullivan] |
| 520 | 3 | |a In recent years, several security agencies have been deploying scheduling systems based on algorithmic advances in Stackelberg security games (SSGs). Unfortunately, none of the existing algorithms can scale up to domains where benefits are accrued from multiple defender resources performing jointly coordinated activities. Yet in many domains, including port patrolling where SSGs are in use, enabling multiple defender resources to perform jointly coordinated activities would significantly enhance the effectiveness of the patrols. To address this challenge, this paper presents four contributions. First, we present Smart(Security games with Multiple coordinated Activities and Resources that are Time-dependent), a novel SSG model that explicitly represents jointly coordinated activities between defender's resources. Second, we present two branch-and-price algorithms, $$S\textsc {mart}_{\textsc {O}}\,$$ S M A R T O —an optimal algorithm, and $$S\textsc {mart}_{\textsc {H}}\,$$ S M A R T H —a heuristic approach, to solve Smartinstances. The two algorithms present three novel features: (i) a novel approach to generate individual defender strategies by ordering the search space during column generation using insights from the Traveling Salesman Problem(TSP); (ii) exploitation of iterative modification of rewards of multiple defender resources to generate coordinated strategies and (iii) generation of tight upper bounds for pruning using the structure of the problem. Third, we present an extensive empirical and theoretical analysis of both $$S\textsc {mart}_{\textsc {O}}\,$$ S M A R T O and $$S\textsc {mart}_{\textsc {H}}\,$$ S M A R T H . Fourth, we describe a large scale real-world experiment whereby we run the first head-to-head comparison between game-theoretic schedules generated using $$S\textsc {mart}_{\textsc {H}}\,$$ S M A R T H against schedules generated by humans on a one-day patrol exercise over one train line of the Los Angeles Metro System. Our results show that game-theoretic schedules were evaluated to be superior to ones generated by humans. | |
| 540 | |a The Author(s), 2014 | ||
| 690 | 7 | |a Game theory |2 nationallicence | |
| 690 | 7 | |a Security |2 nationallicence | |
| 690 | 7 | |a Stackelberg games |2 nationallicence | |
| 690 | 7 | |a Simulations |2 nationallicence | |
| 690 | 7 | |a Field evaluation |2 nationallicence | |
| 700 | 1 | |a Delle Fave |D Francesco |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | |
| 700 | 1 | |a Shieh |D Eric |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | |
| 700 | 1 | |a Jain |D Manish |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | |
| 700 | 1 | |a Jiang |D Albert |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | |
| 700 | 1 | |a Rosoff |D Heather |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | |
| 700 | 1 | |a Tambe |D Milind |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | |
| 700 | 1 | |a Sullivan |D John |u Los Angeles County Sheriff's Department, Los Angeles, CA, USA |4 aut | |
| 773 | 0 | |t Autonomous Agents and Multi-Agent Systems |d Springer US; http://www.springer-ny.com |g 29/5(2015-09-01), 787-820 |x 1387-2532 |q 29:5<787 |1 2015 |2 29 |o 10458 | |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10458-014-9270-4 |q text/html |z Onlinezugriff via DOI |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 900 | 7 | |a Metadata rights reserved |b Springer special CC-BY-NC licence |2 nationallicence | |
| 908 | |D 1 |a research-article |2 jats | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-springer | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1007/s10458-014-9270-4 |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Delle Fave |D Francesco |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Shieh |D Eric |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Jain |D Manish |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Jiang |D Albert |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Rosoff |D Heather |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Tambe |D Milind |u University of Southern California, 90089, Los Angeles, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Sullivan |D John |u Los Angeles County Sheriff's Department, Los Angeles, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Autonomous Agents and Multi-Agent Systems |d Springer US; http://www.springer-ny.com |g 29/5(2015-09-01), 787-820 |x 1387-2532 |q 29:5<787 |1 2015 |2 29 |o 10458 | ||