Optimizing a security patrolling strategy using decomposed optimal Bayesian Stackelberg solver
US8224681B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 17, 2008 |
| Grant date | Jul 17, 2012 |
| Priority date | — |
| Expiry date | Aug 11, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06Q10/063
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques are described for Stackelberg games, in which one agent (the leader) must commit to a strategy that can be observed by other agents (the followers or adversaries) before they choose their own strategies, in which the leader is uncertain about the types of adversaries it may face. Such games are important in security domains, where, for example, a security agent (leader) must commit to a strategy of patrolling certain areas, and robbers (followers) have a chance to observe this strategy over time before choosing their own strategies of where to attack. An efficient exact algorithm is described for finding the optimal strategy for the leader to commit to in these games. This algorithm, Decomposed Optimal Bayesian Stackelberg Solver or “DOBSS,” is based on a novel and compact mixed-integer linear programming formulation. The algorithm can be implemented in a method, software, and/or system including computer or processor functionality.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.