Ting-Yu Chang

Ting-Yu Chang

Auto-generated profile, based on publicly available information

Ting-Yu Chang

Department of Computer Science and Information Engineering, National Central University, Zhongli, Taiwan

Research Focus & Metrics

Academic Career Length

1Year (2026-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
21 April 2026 in ACM Transactions on Cyber-Physical Systems
Verified
Journal Article
Open access
Hao-Tsung YangHao-Tsung Yang
Hao-Tsung Yang
TWTing-Kai Weng
Ting-Kai Weng
TCTing-Yu Chang
Ting-Yu Chang
KLKin Sum Liu
Kin Sum Liu
SLShan Lin
Shan Lin
STShih-Yu Tsai
Shih-Yu Tsai
We study the Patrol Security Game (PSG), a robotic patrolling problem formulated as an extensive-form Stackelberg game, in which the attacker strategically selects the timing, location, and duration of an attack. The defender’s goal is to compute an infinite-horizon patrolling policy that minimizes the attacker’s expected payoff. By restricting the defender’s strategy to a time-homogeneous first-order Markov chain, we show that PSG can be reformulated as a combinatorial minimax problem. We prove that the optimal strategy under zero-penalty scenarios corresponds to minimizing either the expected hitting time or return time, depending on the attacker’s visibility model. These optimal policies are closed-form and can be computed efficiently. On the other hand, in high-penalty cases, we observe that the patrolling schedule with high randomness can minimize the attacker’s expected gain. However, in general, the minimax objective becomes non-convex. To address this, we introduce a bi-criteria optimization framework that jointly considers the expected maximum reward (EMR) and entropy rate of the patrolling policy. We propose three graph-based algorithms and a deep reinforcement learning model to efficiently balance these two objectives. Each algorithm demonstrates distinct strengths under different configurations, such as varying penalty scales and cost function settings. The extensive experiments on both synthetic and real-world crime datasets validate the effectiveness of our approaches, demonstrating superior performance and scalability compared to state-of-the-art baselines.