Game-theoretic Patrol Strategies for Transit Systems: the TRUSTS System and its Mobile App (Demonstration)


Samantha Luber, Zhengyu Yin, Francesco Delle Fave, Albert Xin Jiang, Milind Tambe, and John P. Sullivan. 2013. “Game-theoretic Patrol Strategies for Transit Systems: the TRUSTS System and its Mobile App (Demonstration) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS)[Demonstrations Track].


Fare evasion costs proof-of-payment transit systems significant losses in revenue. In 2007 alone, the Los Angeles Metro system, using proof-of-payment, suffered an estimated revenue loss of $5.6 million due to fare evasion [2]. In addition, resource limitations prevent officers from verifying all passengers. Thus, such officers periodically inspect a subset of the passengers based on a patrol strategy. Effective patrol strategies are then needed to deter fare evasion and maximize revenue in transit systems. In addition, since potential fare evaders can exploit knowledge about the patrol strategy to avoid inspection, an unpredictable patrol strategy is needed for effectiveness. Furthermore, due to transit system complexity, human schedulers cannot manually produce randomized patrol strategies, while taking into account all of the system’s scheduling constraints [3]. In previous work on computing game-theoretic patrol strategies, Bayesian Stackelberg games have been successfully used to model the patrolling problem. In this model, the security officer commits to a patrol strategy and the fare evaders observe this patrol strategy and select a counter strategy accordingly [4]. This approach has also been successfully deployed in real-world applications, including by the L.A. International Airport police, the U.S. Coast Guard at the Port of Boston, and the Federal Air Marshal Service [5]. However, this approach cannot be used within our setting due to the increased complexity of having more potential followers and scheduling constraints [6]. In addition, transit systems face the challenge of execution uncertainty, in which unexpected events cause patrol officers to fall off schedule and exist in unknown states in the model [1]. Addressing the increased complexity challenge, TRUSTS (Tactical Randomizations for Urban Security in Transit Systems) reduces the temporal and spatial scheduling constraints imposed by the transit system into a single transition graph, a compact representation of all possible movement throughout the transit system as flows from each station node [1]. In addition, TRUSTS remedies the execution uncertainty challenge by modeling the execution of patrol units as Markov Decision Processes (MDPs) [1]. In simulation and trial testing, the TRUSTS approach has generated effective patrol strategies for L.A. Metro System [1, 6]. In order to implement the TRUSTS approach in real-world transit systems, the METRO mobile app presented in this paper is being developed to work with TRUSTS to (i) provide officers with realtime TRUSTS-generated patrol schedules, (ii) provide recovery from schedule interruptions, and (iii) collect patrol data. An innovation in transit system patrol scheduling technology, the app works as an online agent that provides officers with the best set of patrol actions for maximizing fare evasion deterrence based on the current time and officer location. In this paper, we propose a demonstration of the TRUSTS system, composed of the TRUSTS and METRO app components, which showcases how the system works with emphasis on the mobile app for user interaction. To establish sufficient background context for the demonstration, this paper also presents a brief overview of the TRUSTS system, including the TRUSTS approach to patrol strategy generation in Section 2.1 and discussion of the METRO app’s features and user interface design in Section 2.2, and the expected benefits from deployment in the L.A. Metro System.
See also: 2013