日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

群制御arXiv:2410.15600

巡回警備ゲーム:攻撃のタイミング・場所・持続時間に自由度を持つ敵対者への防御

Patrol Security Game: Defending Against Adversary with Freedom in Attack Timing, Location, and Duration

シェア:XThreadsFacebookLINEはてブBluesky

攻撃者がタイミング・場所・持続時間を自由に選べる状況でのロボット巡回警備をスタッケルベルクゲームとして定式化し、最適な巡回スケジュールを求めるアルゴリズムを提案した。

著者: Hao-Tsung Yang, Ting-Kai Weng, Ting-Yu Chang, Kin Sum Liu, Shan Lin, Jie Gao, Shih-Yu Tsai

分類: cs.AI, cs.GT, cs.RO

原文アブストラクト

We explored the Patrol Security Game (PSG), a robotic patrolling problem modeled as an extensive-form Stackelberg game, where the attacker determines the timing, location, and duration of their attack. Our objective is to devise a patrolling schedule with an infinite time horizon that minimizes the attacker's payoff. We demonstrated that PSG can be transformed into a combinatorial minimax problem with a closed-form objective function. By constraining the defender's strategy to a time-homogeneous first-order Markov chain (i.e., the patroller's next move depends solely on their current location), we proved that the optimal solution in cases of zero penalty involves either minimizing the expected hitting time or return time, depending on the attacker model, and that these solutions can be computed efficiently. Additionally, we observed that increasing the randomness in the patrol schedule reduces the attacker's expected payoff in high-penalty cases. However, the minimax problem becomes non-convex in other scenarios. To address this, we formulated a bi-criteria optimization problem incorporating two objectives: expected maximum reward and entropy. We proposed three graph-based algorithms and one deep reinforcement learning model, designed to efficiently balance the trade-off between these two objectives. Notably, the third algorithm can identify the optimal deterministic patrol schedule, though its runtime grows exponentially with the number of patrol spots. Experimental results validate the effectiveness and scalability of our solutions, demonstrating that our approaches outperform state-of-the-art baselines on both synthetic and real-world crime datasets.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  3. 3newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

MINISFORUM(ミニPC)

MINISFORUM(ミニPC)の公式広告バナーMINISFORUM公式ストアを見る ↗
PR本紙発行元 EmplifAI