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

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/95844

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/95844

題名:	隨機性巡邏排程對抗具有不同攻擊時長的敵手;Randomized patrolling schedules to counter adversaries with varying attack durations
作者:	翁庭凱;Weng, Ting-Kai
貢獻者:	資訊工程學系
關鍵詞:	機器人巡邏;賽局理論;機器學習;旅行家問題;Robot patrol;Game theory;Machine learning;Traverse salesman problem
日期:	2024-08-21
上傳時間:	2024-10-09 17:19:45 (UTC+8)
出版者:	國立中央大學
摘要:	我們研究了一種擴展的零和巡邏安全遊戲，其中攻擊者可以自由決定攻擊的時間、地點和持續時間，並在三種不同的攻擊者模型下進行考察。在這個遊戲中，攻擊者的收益由攻擊獲得的效用減去被巡邏防守者抓到時的懲罰來確定。我們的主要目標是最小化攻擊者的總收益。為此，我們將遊戲轉化為一個具有明確目標函數的組合極小極大問題在沒有被捕獲懲罰的情況下，我們發現最佳策略涉及根據所使用的攻擊者模型，最小化預期的到達時間或返回時間。此外，我們發現，在高懲罰情況下增加巡邏日程的隨機性顯著降低了攻擊者的預期收益。為了應對一般情況下呈現的挑戰，我們定義了一個雙標準優化問題，並比較了四種算法，旨在平衡最大化預期獎勵和增加巡邏日程隨機性之間的權衡。;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.
顯示於類別:	[資訊工程研究所] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	49	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....