As sensors and robots become ubiquitous for security or surveillance missions, efficiently assigning resources to ensure security becomes crucial. However, patrol/ surveillance scheduling has different characteristics compared to other resource-constrained problems. First, the agents are required to visit/ re-visit targets and the feedback may not be obtained in a short run. Secondly, it naturally consists of the adversary in the model and the problems are varied based on different assumptions of the adversary behaviors. In this talk, I will show how we tackle the patrolling problems from both game-theoretic and geometric views. The problem is formulated into a generalization of the patrol security game. We found that there are two simple objective functions, latency and entropy, that affect the utility of the adversary greatly. Hence, we design different algorithms along with these two objective functions. In the following works, we also discuss latency from the geometric view and provide different approximation algorithms in static and mobile multi-agent scenarios. Unlike the first work that gives heuristic solutions, approximation algorithms are explainable, provide performance guarantee, and are adapted to other scenarios.

Hao-Tsung Yang is a Research Scientist at Sunrise Technology Inc. starting from Feb. 2021. He received his Ph.D. degree at Computer Science, Stony Brook University, in 2020, advised by Prof. Jie Gao and Prof. Shan Lin. Before that, He has a B.S. degree in Applied Math and an M.S. degree in Computer Science, both from National Chiao Tung University of Taiwan. Hao-Tsung Yang's research theme focuses on scheduling problems in the autonomous system, such as sensor surveillance or path scheduling/ patrolling for robots. The developed solutions include both approximation algorithms and reinforcement learning. He recently has interests in scheduling problems under privacy issues. This includes (a.) scheduling under information leakage and (b.) scheduling without revealing sensitive information. There are some preliminary works published in AAMAS, FWCG,.. and other works are ongoing.