隨機性巡邏排程對抗具有不同攻擊時長的敵手;Randomized patrolling schedules to counter adversaries with varying attack durations

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/95844

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/95844

Title:	隨機性巡邏排程對抗具有不同攻擊時長的敵手;Randomized patrolling schedules to counter adversaries with varying attack durations
Authors:	翁庭凱;Weng, Ting-Kai
Contributors:	資訊工程學系
Keywords:	機器人巡邏;賽局理論;機器學習;旅行家問題;Robot patrol;Game theory;Machine learning;Traverse salesman problem
Date:	2024-08-21
Issue Date:	2024-10-09 17:19:45 (UTC+8)
Publisher:	國立中央大學
Abstract:	我們研究了一種擴展的零和巡邏安全遊戲，其中攻擊者可以自由決定攻擊的時間、地點和持續時間，並在三種不同的攻擊者模型下進行考察。在這個遊戲中，攻擊者的收益由攻擊獲得的效用減去被巡邏防守者抓到時的懲罰來確定。我們的主要目標是最小化攻擊者的總收益。為此，我們將遊戲轉化為一個具有明確目標函數的組合極小極大問題在沒有被捕獲懲罰的情況下，我們發現最佳策略涉及根據所使用的攻擊者模型，最小化預期的到達時間或返回時間。此外，我們發現，在高懲罰情況下增加巡邏日程的隨機性顯著降低了攻擊者的預期收益。為了應對一般情況下呈現的挑戰，我們定義了一個雙標準優化問題，並比較了四種算法，旨在平衡最大化預期獎勵和增加巡邏日程隨機性之間的權衡。;We explore an extended version of the zero-sum patrolling security game where the attacker has the flexibility to decide the timing, location, and duration of their attack, examined under three distinct attacker models. In this game, the attacker′s payoff is determined by the utilities gained from the attack minus any penalties incurred if caught by the patrolling defender. Our primary objective is to minimize the attacker′s overall payoff. To achieve this, we transform the game into a combinatorial minimax problem with a clearly defined objective function. In cases where there is no penalty for getting caught, we establish that the optimal strategy involves minimizing either the expected hitting time or return time, contingent on the attacker model employed. Furthermore, we find that enhancing the randomness of the patrol schedule significantly reduces the attacker′s expected payoff in scenarios involving high penalties. To address the challenges presented in general scenarios, we developed a bi-criteria optimization problem and compare four algorithms designed to balance the trade-off between maximizing expected rewards and increasing randomness in patrol scheduling.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	49	View/Open

社群 sharing

Loading...