演講公告

演講主題：Safety Patrol Scheduling Using Randomized Traveling Salesman Tour
主講人：楊皓琮先生 (Ph.D. student of Computer Science, Stony Brook University
演講日期：2017年9月11日(星期一) 13:40–14:40
演講地點：(光復校區) 科學一館 213 室
摘要內容：
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 set
相關檔案：Talk_1060911.pdf

$返回$ go back