Hao-Tsung Yang (Rey)

Ph.D. candidate in Computer Science

Stony Brook University

haotyang at cs dot stonybrook dot edu

Introduction:

I am a Ph.D. candidate in Computer Science, Stony Brook University since Fall 2014, advised by Prof. Jie Gao and Prof. Shan Lin. Before that, I had a B.S. degree in Applied Math and an M.S. degree in Computer Science, both from National Chiao Tung University of Taiwan. My research theme is to discuss scheduling problems and design algorithms regarding surveillance or patrol missions. The developed solutions include both approximation algorithm and reinforcement learning. I also have several works focusing on stream scheduling in wireless sensor networks to achieve low latency and high reliability. Besides that, I also have multidisciplinary works that involve data analysis/ machine learning in multiple fields such as spam calls analysis, crime data analysis, political donation analysis, player styles analysis in gaming.

If you have any questions, seeking cooperation, or just want to know more about me, you are very welcomed to contact me.

Short Research Bio.:

As sensors and robots become ubiquitous for security or surveillance missions, efficiently assigning resources to ensure security becomes crucial. For example, one common objective is requiring the protector(s) visiting/ revisiting targets with certain frequencies and simultaneously minimize the energy use or tour lengths. Thus, these problems are often formulated as resource-constrained scheduling problems. One of the main themes in my research is to discuss several scheduling problems regarding of surveillance or patrol missions that are variant by the following dimensions: there is either one or multiple agents; the models is frequency-based setting or adversarial setting; the agent(s) is either static or mobile.

Research Fields: Computational geometry and Algorithm, Robotics and Autonomous scheduling, and Wireless Sensor Network.

Selected Publications:

  • Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. (Accepted in WAFR 2020)
  • Patrol Scheduling Against Adversaries with Varying Attack Durations. (AAMAS 2019)
  • Joint sensing duty cycle scheduling for heterogeneous coverage guarantee. (INFOCOM 2017)
  • Multi-Channel Assignment and Link Scheduling for Prioritized Latency-Sensitive Applications. (ALGOSENSORS 2019)
  • Reliable Stream Scheduling with Minimum Latency for Wireless Sensor Networks. (SECON 2017)

All Publications:

Algorithms in Security applications (Surveilliance & Patrol):

  • Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency (Accepted in WAFR 2020)
Abstract: We consider the problem of finding patrol schedules for k robots to visit a given set of n sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (when k=1 and all sites have the same weight). We present an algorithm with an approximation factor of $O(k log w_max/ w_min)$ to the optimal solution, where $w_{\max}$ and w_min are the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. When the sites may have different weights, we use dynamic programming to generate an $8$-approximate solution.
  • Patrol Scheduling Against Adversaries with Varying Attack Durations (AAMAS 2019)
H. T. Yang, S. Y. Tsai, K. S. Liu, J. Gao and S. Lin
Abstract: We consider a generalization of zero-sum patrolling security game that allows the attacker choosing when, where, and how long to launch an attack, under three different attacker models. The attacker's payoff is the acquired utilities of the attack minus a penalty if the attacker is caught by the defender in patrol. The goal is to reduce the payoff of the attacker. To find the optimal defender/ attacker strategy, the game is converted to a combinatorial minimax problem with a closed-form objective function. Due to the complexity of the utility functions, we show that the minimax problem is not convex for all attacker models, even when the defender strategy is assumed as the time-homogeneous first-order Markov chain (i.e., the patroller's next visit only depends on his current location). However, for the zero penalty case, we prove that the optimal solution is either minimizing the expected hitting time or return time, based on different attacker models. We also observe that increasing the randomness of the patrol schedule helps to reduce the attacker's expected payoff for high penalty cases. Thus, to find solutions for general cases, we formulated a bi-criteria optimization problem and proposed three algorithms that support finding a trade-off between the expected maximum reward and the randomness. Another characteristic is that the third algorithm is able to find the optimal deterministic patrol schedule, although the running time is exponential on the number of patrol spots. Experiments demonstrate the effectiveness and scalability of our solutions. It also shows that our solutions outperform the baselines from state of the art in both artificial and real-world crime datasets.
  • Far-Away Spanning Trees (FWCG 2018)
J. Gao , M. Goswamiy, R. Schley, S. Y. Tsai, and H. T. Yang
Abstract: The problem of computing minimum spanning trees (MSTs) is a classical textbook problem. But not much is known about how to find spanning trees that have ‘diversity’. Using trees that do not share a lot of edges means better reliability under potential failures or attacks. If one tree is destroyed, one can quickly switch to a different tree. In many network tasks, it is desirable to have multiple good solutions and to possibly alternate between them to avoid being tracked or attacked by adversaries. Given a graph $G$, a spanning tree is a connected subgraph of $G$ with no cycles. If the edges are weighted, a minimum spanning tree is a spanning tree with minimum total weight. Initially, we are motivated to find $k$ spanning trees that are far away from each other -- that is, the maximum number of edges shared by any two trees is minimized. In this paper, we consider a more general type of trees -- $\alpha$-approximate spanning trees, which are spanning trees with total weight at most $\alpha \cdot |\MST|$. Our problem now is to find $k$ far-away $\alpha$-approximate spanning trees, which are selected within the family of spanning trees of total weight at most $\alpha \cdot |\MST|$ and the maximum number of edges that any two trees share is minimized. When $\alpha$ is one and weights are all the same, this problem becomes the problem for spanning tree. We provide an algorithm for $k$ far-away $\alpha$-approximate spanning trees which achieves $(2+\epsilon)$-approximation.
  • Optimal Safety Patrol Scheduling Using Randomized Traveling Salesman Tour (FWCG 2017 )
H. T. Yang, S. Y. Tsai, J. Gao and S. Lin
Abstract: In this paper, we consider the problem of designing schedules for a patroller to guard a given set of $n$ sites in a strategic setting modeled as the attacker-defender game. It belongs to the general framework of security games and the main challenge here is to explicitly model the time spent moving between the sites and the scalability issue, as the strategy space contains exponentially many schedules even with a finite time horizon. The traveling salesman tour visits all sites with the highest frequency but is deterministic and could be exploited by the attacker. Random tours are most unpredictable but could be substantially inefficient in visiting the sites. Instead, we formulate the randomized TSP problem and provide solutions that achieve a nice tradeoff between frequency in visiting the sites and unpredictability for the strategic setting. We provide a rigorous analysis of the randomized TSP and show how to solve for the best defender strategies under this family of tours. Evaluations demonstrate the effectiveness of our solutions compared to other alternatives using both artificial data and a real-world crime dataset.
  • Joint sensing duty cycle scheduling for heterogeneous coverage guarantee (IEEE INFOCOM 2017)
K. S. Liu, T. Mayer, H. T. Yang, E. Arkin, J. Gao, M. Goswami, M. P. Johnson, N. Kumar, and S. Lin
Abstract: In this paper we study the following problem: given a set of $m$ sensors that collectively cover a set of $n$ target points with heterogeneous coverage requirements (target $j$ needs to be covered every $f_j$ slots), how to schedule the sensor duty cycles such that all coverage requirements are satisfied and the maximum number of sensors turned on at any time slot is minimized. The problem models varied real-world applications in which sensing tasks exhibit high discrepancy in coverage requirements -- critical locations often need to be covered much more frequently. We provide multiple algorithms with best approximation ratio of $O(\log n+\log m)$ for the maximum number of sensors to turn on, and bi-criteria algorithm with $(\alpha, \beta)$-approximation factors with high probability, where the number of sensors turned on is an $\alpha = O(\frac{\delta(\log(n) + \log(m))}{\beta})$-approximation of the optimal (satisfying all requirements) and the coverage requirement is a $\beta$-approximation; $\delta$ is the approximation ratio achievable in an appropriate instance of set multi-cover. When the sensor coverage exhibits extra geometric properties, the approximation ratios can be further improved. We also evaluated our algorithms via simulations and experiments on a camera testbed. The performance improvement (energy saving) is substantial compared to turning on all sensors all the time, or a random scheduling baseline.

Wireless sensor network :

  • Reliable Communication and Latency Bound Generation in Wireless Cyber-Physical System (Journal) (TCPS 2019)
S. Munir, H. T. Yang, S. Lin, E. Hoque, S. M. S. Nirjon, C. Lin, J. Stankovic, K. Whitehouse.
Abstract: Low-power wireless communication has been widely used in cyber-physical systems which require time-critical data delivery. Achieving this goal is challenging because of link burstiness and interference. Based on significant empirical evidence of 21 days and over 3,600,000 packets transmission per link, we propose both routing and scheduling algorithms that produce latency bounds of the real-time periodic streams and accounts for both link bursts and interference. The solution is achieved through the definition of a new metric $B_{\max}$ that characterizes links by their maximum burst length, and by choosing a novel least-burst-route that minimizes the sum of worst-case burst lengths over all links in the route. With extensive data-driven analysis, we show that our algorithms outperform existing solutions by achieving accurate latency bound with much less energy consumption. In addition, a testbed evaluation consisting of 48 nodes spread across a floor of a building shows that we obtain 100\% reliable packet delivery within derived latency bounds. We also demonstrate how performance deteriorates and discuss its implications for wireless networks with insufficient high-quality links.
  • Multi-Channel Assignment and Link Scheduling for Prioritized Latency-Sensitive Applications (Algosensor 2019)
S. Y. Tsai, H. T. Yang, K. S. Liu, S. Lin, R. Chowdhury, and J. Gao
Abstract: Current wireless networks mainly focus on delay-tolerant applications while demands for latency-sensitive applications are rising with VR/AR technologies and machine-to-machine IoT applications. In this paper we consider multi-channel, multi-radio scheduling at the MAC layer to optimize for the performance of prioritized, delay-sensitive demands. Our objective is to design an interference-free schedule that minimizes the maximum weighted refresh time among all edges, where the refresh time of an edge is the maximum number of time slots between two successive slots of that edge and the weights reflect given priorities. In the single-antenna unweighted case with $k$ channels and $n$ transceivers, the scheduling problem reduces to the classical edge coloring problem when $k \geq \lfloor n/2 \rfloor$ and to strong edge coloring when $k=1$, but it is neither edge coloring nor strong edge coloring for general $k$. Further, the priority requirement introduces extra challenges. In this paper we provide a randomized algorithm and is able to generalized into the multi-antenna settings. We evaluate the performance of our methods in different settings using simulations.
  • Reliable Stream Scheduling with Minimum Latency for Wireless Sensor Networks (IEEE SECON 2017)
H. T. Yang, K. S. Liu, S. Lin,and J. Gao.
Abstract: As sensor networks are increasingly deployed for critical applications, reliability and latency guarantee become more important than ever to meet industrial requirements. In this paper, we investigated the impact of link burstiness on stream scheduling using a data trace of 3,600,000 packets collected from an indoor testbed. We demonstrate that a good tradeoff between reliability and latency can be achieved by allocating certain time slots on each link for stream transmissions based on its burst length and frequency distributions. With this observation, we design transmission scheduling and routing algorithms for data streams to meet a specified reliability requirement while minimizing end-to-end latency. For the multi-stream scheduling problem, we prove its NP-hardness and design an algorithm that achieves the reliability guarantee and an $O(\log n)$ approximation of minimizing the maximum end-to-end latency for any stream. Trace-driven simulations show that our solution meets specified end-to-end reliability requirements with latency up to 9.18 times less than existing solutions.

Mobile and games:

  • Sensemo: An Emotion Sensing System using Physiological Cues (poster) (HotMobile 2016)
K. Joshi, S. Lin, S. Nirjon, and H. T. Yang
Abstract: This paper presents a new emotion sensing based real-time adaptive learning system which uses three bio-sensors, namely Pulse Sensor, Galvanic Skin Response Sensor and Electromyography Sensor. These three bio-sensors help the system read the bio-signals from a user in real time and unobtrusively. The system is able to detect two indicators of human emotion (valence and arousal) with 75\% - 79\% accuracy. In order to improve the e-learning experience of a user, we propose two types of feedback methods: adapting the speed of the session and adapting the content, depending upon the emotion response of a user in real-time. We conduct studies to find the effectiveness of the system. We test our adaptive learning system with 22 participants, and show that the autonomous feedback methods used are effective way of improving user learning experience evident from the higher score for quizzes after the lessons.
  • Thinking Style and Team Competition Game Performance and Enjoyment (journal) (TCIAIG 7.3: 243-254)
H. Wang, H. T. Yang, and C. T. Sun.
Abstract: Almost all current matchmaking systems for team competition games based on player skill ratings contain algorithms designed to create teams consisting of players at similar skill levels. However, these systems overlook the important factor of playing style. In this paper, we analyze how playing style affects enjoyment in team competition games, using a mix of Sternberg’s thinking style theory and individual histories in the form of statistics from previous matches to categorize League of Legend (LoL) players. Data for approximately 64000 matches involving 185000 players were taken from the LoLBase website. Match enjoyment was considered low when games lasted for 26 min or less (the earliest possible surrender time). Results from statistical analyses indicate that players with certain playing styles were more likely to enhance both game enjoyment and team strength. We also used a neural network model to test the usefulness of playing style information in predicting match quality. It is our hope that these results will support the establishment of more efficient matchmaking systems.
  • Mobile Game Recommendation: using Touching Gestures (NetGames 2014)
H. T. Yang, D. Y. Chen, Y. X. Hong,and K. T. Chen.
Abstract: Today, any Internet user can find out and download more than one hundred thousands of games on mobile app marketplaces; nevertheless, how to pick the best games out of the large pool without spending much time on tryout is very challenging. The common rank list and social recommendation approaches for discovering new games do not work well when a player wants to search for games with a particular gameplay, or he may want to find out all the slow-paced games suitable for his grandparents. There is currently no feasible way to do that because these requirements cannot be formulated in a proper text search query. In this paper, we propose a scheme that can discover mobile games with similar gameplay based on players’ touch gestures while playing a game. We select 22 mobile games from 5 genres and recorded 94 touch gesture traces from 5 subjects. The evaluation results show that 1) touch gestures can serve robust signatures of gameplay as the key traits of the touch gestures from different subjects remain consistent; 2) our scheme can give reasonably accurate recommendations of similar games simply based on touch gestures.
  • Dude, the Source of Lags Is on Your Computer. In 12th ACM Network and System Support for Games (NetGames 2014)
D. Y. Chen, H. T. Yang, and K. T. Chen.
Abstract: Lag denotes the event when an application fails to respond user inputs in a timely fashion and is considered one of the most common annoyances that impair online gaming experience. Despite years of effort devoted by game developers and network designers trying to overcome lags, gamers still suffer from this annoying phenomenon. It seems to many gamers that lag is an unavoidable part of online gaming and sometimes they just give up fighting it. In this paper, we tackle the lag problem by investigating the root cause of lags for gamers. We develop a software called Game Experience Monitor (GEM), which monitors the performance of gamers’ computers and the quality of network paths during game play, and use the collected traces to correlate players’ perceived experience to find out the common cause of lags. Our analysis reveals that, surprisingly, while it is a common belief that the instability of Internet paths is the major cause of lags, the overloading of players’ computers in fact plays a more decisive role to lag. It is hoped that this counter-common-belief finding will motivate further research for providing a better infrastructure for gaming and other real-time interactive applications.