Selected Research Projects and Interests

Game Theory for Homeland Security

A vehicle checkpoint at LAX I am involved in several projects that apply game-theoretic reasoning to make resource allocation decisions in real-world homeland security domains. The adversarial reasoning capabilities of game theory provide an ideal framework for modeling adaptive, intelligent attackers in security domains. The solutions to these games represent optimal, risk-based security policies that are randomized to increase the uncertainty of potential attackers and increase the risk and cost of planning attacks. This work has included new algorithms for scaling to massive resource scheduling problems, techniques for solving large Bayesian game models the result in more robust solutions, new approaches for modeling the behavior of human attackers in security games, and several deployed software decision support tools.

The ARMOR system deployed at the Los Angeles International Airport (LAX) is used to schedule canine patrols and vehicle checkpoints at the airport. The image to the right is one of the LAX checkpoints scheduled by the ARMOR system.

Screenshot of the IRIS scheduling system Building on the success of ARMOR, I worked with colleagues at USC and the Federal Air Marshals Service FAMS) to develop the IRIS system (shown in the screenshot to the left) for scheduling FAMS on flights. There are tens of thousand of flights each day and thousand of air marshals, so the game models that this system is based on are extremely large. Solving these models was only possible due to significant modeling and algorithmic advances.

The GUARDS system is currently being tested by the Transportation Security Administration to provide risk-based randomization for wide variety of security activities at airports. It is anticipated that this system will eventually be deployed nationwide.

Several additional projects based on game theory for security are also underway, including work for the United States Coast Guard, Border Patrol, and Los Angeles Sheriff's Department.

Diagram of the TAC SCM game. Trading Agents and Supply Chain Management

Automated trading agents are on of the "killer apps" for intelligent agent technologies. One specific area of interest is supply chain management, which is an enormously complex problem faced by corporations worldwide. Increasingly, business systems are becoming automated, capitalizing on the ability to capture and manage vast amounts of enterprise data, but introducing complex new decision problems. The Trading Agent Competition Supply Chain Management game (TAC/SCM) provides a unique testbed for research in this domain, pitting automated SCM agents against one another in an annual tournament. I have been one of the lead members of the University of Michigan's TAC SCM team since the first competition in 2003. Our agent, Deep Maize, has been a finalist in every tournament to date, and placed first in the 2008 and 2009 competitions. This is a result of many years of research spanning novel agent architectures for distributed decision-making, machine learning methods for forecasting market prices, and new approaches for strategic reasoning in very complex domains.

Empirical Game Theory

Schematic view of the empirical game theory methodology. Game theory is a useful paradigm for reasoning about situations with multiple decision-makers. However, to apply game theory it is necessary to first specify a game model. In many domains a suitable model is not easy for an analyst or user to specify directly. Instead, it is necessary to use simulation or other sources of historical data to build a model of the interaction between the decision-makers. The methodology of empirical game theory describes the process of building models of games using simulation or other empricical evidence. This methodology has been applied to a variety of complex multi-agent systems, including the Trading Agent Competition Supply Chain Management game. One question that I am particularly interested in is developing robust solution methods that operate on highly uncertain game models. I developed meta-strategy analysis to address this question, and showed that Nash equilibrium is typically a very poor solution concept for emprical games. Alternative approaches including Quantal Response Equilibrium (QRE) give much better performance.

Team Formation

Forming a high-quality team is the first step in accomplishing many multi-agent tasks. I helped to develop ARTFS, a tool for team formation designed primarily to support rapid team formation for disaster response scenarios. The underlying technology uses distributed constraint optimization (DCOP) to represent and reason about possible team assignments. I helped to develop new distributed optimization algorithms that use approximation to scale to very large problems, while retaining some guarantees on solution quality and very good performance on typical problems.