Coordinating Randomized Policies for Increasing the Security of Agent Systems

doi:10.1017/CBO9780511973031.007

7 - Coordinating Randomized Policies for Increasing the Security of Agent Systems

from PART III - EFFICIENT ALGORITHMS FOR MASSIVE SECURITY GAMES

Published online by Cambridge University Press: 05 January 2012

Fernando Ordóñez and

Milind Tambe: Affiliation:
University of Southern California

Book contents

Get access

Summary

Introduction

Security, commonly defined as the ability to deal with intentional threats from other agents, is a major challenge for agents deployed in adversarial environments (Paruchuri et al., 2006). In this paper, we focus on adversarial domains in which the agents have limited information about the adversaries. Such adversarial scenarios arise in a wide variety of situations that are becoming increasingly important, such as patrol agents providing security for a group of houses or regions (Carroll et al., 2005; Paruchuri et al., 2007), UAVs monitoring a humanitarian mission (Beard and Mclain, 2003; Paruchuri et al., 2006), agents assisting in routine security checks at airports (Poole and Passantino, 2003), agents providing privacy in sensor network routing (Ozturk, Zhang, and Trappe, 2004), and agents maintaining anonymity in peer-to-peer networks (Borisov and Waddle, 2005).

This paper brings together some of our recent work on how to plan for agents acting in uncertain environments in the presence of adversaries (Paruchuri et al., 2006, 2007, 2008). This research has introduced two very different approaches to increasing security in agent systems and has lead to the ARMOR (Assistant for Randomized Monitoring over Routes) system, which has been deployed for security scheduling at the LAX airport since August 2007 (Murr, 2007; Paruchuri et al., 2008; Pita et al., 2008). Here we will present the main results and algorithms proposed in these two approaches and highlight the relationship between them.

Type: Chapter
Information: Security and Game Theory
Algorithms, Deployed Systems, Lessons Learned
, pp. 131 - 155

DOI: https://doi.org/10.1017/CBO9780511973031.007 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

R., Beard and T., McLain. Multiple uav cooperative search under collision avoidance and limited range communication constraints. In IEEE Conference on Decision and Control (CDC), 2003.Google Scholar

N., Borisov and J., Waddle. Anonymity in structured peer-to-peer networks. In University of California, Berkeley, Technical Report No. UCB/CSD-05-1390, 2005.Google Scholar

G., Brown, M., Carlyle, J., Salmeron, and K., Wood. Defending critical infrastructures. Interfaces, 36(6):530–544, 2006.Google Scholar

J., Brynielsson and S., Arnborg. Bayesian games for threat prediction and situation analysis. In International Conference on Information Fusion (FUSION), 2004.Google Scholar

D. M., Carroll, C., Nguyen, H., Everett, and B., Frederick. Development and testing for physical security robots. http://www.nosc.mil/robots/pubs/spie5804-63.pdf, 2005.

V., Conitzer and T., Sandholm. Choosing the optimal strategy to commit to. In ACM Conference on Electronic Commerce, 2006.Google Scholar

D., Dolgov and E., Durfee. Approximating optimal policies for agents with limited execution resources. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), 2003.Google Scholar

D., Dolgov and E., Durfee. Constructing optimal policies for agents with constrained architectures. Technical report, Univ of Michigan, 2003.

D., Fudenberg and J., Tirole. Game Theory. MIT Press, 1991.Google Scholar

J. C., Harsanyi and R., Selten. A generalized Nash solution for two-person bargaining games with incomplete information. Management Science, 18(5):80–106, 1972.Google Scholar

A., Murr. Random checks. In Newsweek National News, http://www.newsweek.com/id/43401, Sept., 28, 2007.Google Scholar

C., Ozturk, Y., Zhang, and W., Trappe. Source-location privacy in energy-constrained sensor network routing. 2004.

P., Paruchuri, J. P., Pearce, J., Marecki, M., Tambe, F., Ordonez, and S., Kraus. Playing games for security: An efficient exact algorithm for solving bayesian stackelberg. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2008.Google Scholar

P., Paruchuri, J. P., Pearce, M., Tambe, F., Ordonez, and S., Kraus. An efficient heuristic approach for security against multiple adversaries. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2007.Google Scholar

P., Paruchuri, M., Tambe, F., Ordonez, and S., Kraus. Towards a formalization of teamwork with resource constraints. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2004.Google Scholar

P., Paruchuri, M., Tambe, F., Ordonez, and S., Kraus. Security in multiagent systems by policy randomization. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2006.Google Scholar

J., Pita, M., Jain, J., Marecki, F., Ordonez, C., Portway, M., Tambe, C., Western, P., Paruchuri, and S., Kraus. Deployed armor protection: The application of a game theoretic model for security at the los angeles international airport. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (Industry Track), 2008.Google Scholar

R., Poole and G., Passantino. A risk based airport security policy. 2003.

M., Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 1994.Google Scholar

T., Roughgarden. Stackelberg scheduling strategies. In TOC: ACM Symposium on Theory of Computing, 2001.Google Scholar

T., Sandholm, A., Gilpin, and V., Conitzer. Mixed-integer programming methods for finding nash equilibria. In National Conference on Artificial Intelligence (AAAI), 2005.Google Scholar

C., Shannon. A mathematical theory of communication. The Bell Labs Technical Journal, pages 379–457, 623, 656, 1948.Google Scholar

H. V., Stackelberg. Marktform and gleichgewicht. In Springer, 1934.