Colloquium / Seminars
Topic:Safety Patrol Scheduling Using Randomized Traveling Salesman Tour
Speaker:Mr. Hso-Tsung, .Yang
(Ph.D. student of Computer Science, Stony Brook UniversityDate time:Sep. 11, 2017 13:40–14:40
Venue:SA213
Abstract:
Abstract
In this talk, we consider the problem of designing schedules for a patroller to guard a given set of n sites in a strategic setting modeled as the attacker-defender game. It belongs to the general framework of security games and the main challenge here is to explicitly model the time spent moving between the sites and the scalability issue, as the strategy space contains exponentially many schedules even with a finite time horizon. The traveling salesman tour visits all sites with the highest frequency but is deterministic and could be exploited by the attacker. Random tours are most unpredictable but could be substantially inefficient in visiting the sites. Instead, we formulate the randomized TSP problem and provide solutions that achieve a nice tradeoff between frequency in visiting the sites and unpredictability for the strategic setting. We provide a rigorous analysis of the randomized TSP and show how to solve for the best defender strategies under this family of tours. Evaluations demonstrate the effectiveness of our solutions
compared to other alternatives using both artificial data and a real world crime data setDownload:Talk_1060911.pdf
go back