Dr. Hao-Tsung Yang

Assistant Professor at National Central University

haotsungyang at gmail dot com

I will join National Central University at August 2022 as an assistant professor. I am looking for students who are interested to join ASAI lab and work together. The only graduation requirement for my lab is to publish a "complete research", which includes, a problem that people is interested, the related work, the solution, and the evaluation & discussion. 

There are mainly two research tracks in our lab. 

A.) Autonomous system and its algorithm. 

B.) The fairness, transparency, explainability, and privacy in Machine learning algorithm.

You can see the Chinese version of this page to earn more detail or asking me directly via email. If you're interested, you're very welcome to send me a mail or chat online. 

Brief Bio.

Hao-Tsung Yang is an assistant professor at National Central University. Before that, he was a research associate at the School of Informatics in University of Edinburgh, U.K., supervised by Prof. Rik Sarkar. He receives his Ph.D. degree in Computer Science, Stony Brook University, in 2020, advised by Prof. Jie Gao and Prof. Shan Lin. 

Hao-Tsung Yang's research theme lies between autonomous systems, data privacy, algorithm, and machine learning. He focuses on new problems and challenges when A.I. comes into human life, including serving humans, interacting & cooperating with humans, or defense from the human-like adversary. For example, an autonomous system such as multi-robot path planning involves multiple works; the control-feedback loop, the algorithm design, privacy, and data misuse. The solutions of these works influence one another, especially considering the human factor in the environment. One can use machine learning techniques to learn and generate good path planning solutions but also may invade people's privacy such as revealing their routine schedule, misusing sensitive data,...etc. On the other hand, the solution may also reveal to the adversary who wants to damage the system and take advantage of it. In a patrol mission, the adversary can predict the arrival time of patrolling robots and launch attacks in vulnerable time slots. These bring new challenges and solutions could be found from algorithmic or machine learning perspectives, and sometimes, combining both together.

Research Interest

Classic problems such as path finding/ patrolling for robots. The developed solutions include both approximation algorithm and reinforcement learning. I am recently interested in scheduling problems under privacy issues. This includes two directions: (a.) scheduling under information leakage and (b.) scheduling without revealing sensitive information. There are some preliminary works published in AAMAS, WAFR, INFOCOM.. and other works are ongoing.


As sensors and robots become ubiquitous in many different applications, efficiently assigning resources to provide reliable and ensure the quality of service is a crucial problem. I have several works discussed the scheduling problems for heterogenous transmissions in wireless sensor network published in TOSN, SECON, and ALGOSENSOR. 


I also have multidisciplinary works that involve data analysis/ machine learning in multiple fields such as high-speed physical trigger detection, spam calls analysis and political donation analysis, player styles analysis in gaming.

Selected Publications

All Publications

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. 
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.
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.
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.
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.
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.
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. 

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.
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.
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.
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.
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.