Agent security via approximate solvers

US8195490B2 · kind B2 · utility

Assignee

• University of Southern California · US

Inventors

• Milind Tambe · Rancho Palos Verdes, US
• Praveen Paruchuri · Pittsburgh, US
• Fernando Ordóñez · San Fernando, US
• Sarit Kraus · Givat Shmuel, IL
• Jonathan Pearce · New York, US
• Janusz Marecki · Los Angeles, US

Key dates

• Filing date: Oct 15, 2008
• Grant date: Jun 5, 2012
• Expiry date: Nov 12, 2030

Classification

• Technology area (CPC G): Physics
• CPC primary: G06Q10/063
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

Efficient heuristic methods are described for approximating the optimal leader strategy for security domains where threats come from unknown adversaries. These problems can be modeled as Bayes-Stackelberg games. An embodiment of the heuristic method can include defining a patrolling or security domain problem as a mixed-integer quadratic program. The mixed-integer quadratic program can be converted to a mixed-integer linear program. For a single follower (e.g., robber or terrorist) scenario, the mixed-integer linear program can be solved, subject to appropriate constraints. For embodiments applicable to multiple follower situations, the relevant mixed-integer quadratic program and related mixed-integer linear program can be decomposed, e.g., by changing the response function for the follower from a pure strategy to a weighted combination over various pure follower strategies where the weights are probabilities of occurrence of each of the follower types.