Conference Proceeding Article
Mass Rapid Transit using rail is a popular mode of transport employed by millions of people in many urban cities across the world. Typically, these networks are massive, used by many and thus, can be a soft target for criminals. In this paper, we consider the problem of scheduling randomised patrols for improving security of such rail networks. Similar to existing work in randomised patrols for protecting critical infrastructure, we also employ Stackelberg Games to represent the problem. In solving the Stackelberg games for massive rail networks, we make two key contributions. Firstly, we provide an approach called RaPtoR for computing randomized strategies in patrol teams, which guarantees (i) Strong Stackelberg equilibrium (SSE); and (ii) Optimality in terms of distance traveled by the patrol teams for specific constraints on schedules. Secondly, we demonstrate RaPtoR on a real world data set corresponding to the rail network in Singapore. Furthermore, we also show that the algorithm scales easily to large rail networks while providing SSE randomized strategies.
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Transportation
Intelligent Systems and Decision Analytics
Proceedings of the Twenty-Fifth Innovative Applications of Artificial Intelligence Conference IAAI 2013: Bellevue, WA, July 14-18, 2013
City or Country
Palo Alto, CA
VARAKANTHAM, Pradeep; LAU, Hoong Chuin; and YUAN, Zhi.
Scalable randomized patrolling for securing rapid transit networks. (2013). Proceedings of the Twenty-Fifth Innovative Applications of Artificial Intelligence Conference IAAI 2013: Bellevue, WA, July 14-18, 2013. 1563-1568. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1812
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.