楊晧琮 (Hao-Tsung Yang)

Assistant Professor at National Central University

haotsungyang at gmail dot com

學生招募

我在中央大學資工系擔任助理教授一職，正在招收有興趣的專題生，碩士生，或博士生加入自動化系統與AI實驗室。 實驗室著重兩個領域: 在自動化系統上的排程問題，在機器學習上的隱私、公平、透明度、可解釋性的問題。

        若你是除了動手做以外，更喜歡問"為什麼"要這樣做? 那本實驗室會非常契合你。對於碩論，研究題目以學生有興趣的為主，只要領域不要離我擅長的研究太遠即可 。除了中央資工硬性規定的畢業條件以外，研究室畢業門檻為做出一份完整的研究。所謂的完整即是一個提出與解決問題的完整過程。這包含:題目，前人相關的研究，解決辦法，驗證與討論。具體如下:

題目: 問出一個讓人有興趣的問題

相關研究: 跟這問題相關的研究是甚麼，為什麼沒辦法完全解決這個題目呢

解決辦法: 我們想出來的解決辦法是甚麼

驗證與討論: 說服 (用實驗或證明)別人我們的解決辦法解決了甚麼，或是沒有解決了甚麼。

        研究本身就很難，所以我不會開出硬性的規定，我重視的是這段期間能否學到一套完整的，解決問題的辦法，讓學生能帶到之後的職涯上。無論是專題或是碩論都是學生自己的作品，所以我希望這段過程中以學生能保持研究熱忱為主要目標，研究方向上我很歡迎學生提出自己的想法來互相討論，以我們是一個團隊的方式來完成這份研究。如果你有興趣，歡迎你寫信來或是約個時間聊聊。

P.S.，若之後有興趣出國發展(無論念書或是工作)，我本身還有跟數個不同的歐美教授合作，包括Rutgers University, Stony Brook University, University of Edinburgh, City University of New York...etc. 也會有一起的meeting可以參加合作。另外在準備出國申請學校上我也有不少經驗，都可以討論。

自介

我的博士學位是在2020年於美國石溪大學取得，由Prof. Jie Gao and Prof. Shan Lin 指導。這之後，我在Sunrise technology 擔任一年的研究科學家並從2021年9月到2022年7月於愛丁堡大學資訊學院擔任博士後研究，由 Prof. Rik Sarkar指導。

       我的研究領域主要是放在自動化系統，資料隱私，物聯網上並擅長從演算法，機器學習，或是資料科學的角度去解決問題。 我關注的問題通常都是當AI進入到人類生活之後所產生的挑戰以及各種排程問題。大方向上，都是如何安排有限的資源去達成目標，當牽扯到人類行為後，這些目標通常會比傳統的複雜或是包含多個不同需整合的目標。以機器人巡邏來維護治安來舉例，光是犯罪的面向就有分成深思熟慮的作案(e.g., 有計畫的銀行搶案)以及臨時起意(e.g., 肇事逃逸)等，對於不同的犯罪就會需要設計出完全不同的巡邏路徑。對於深思熟慮的作案，機器人設計的路線若是太過呆版，簡單，那犯罪者便可以藉由簡單的觀察來準確預測它接下來的位置，甚而避開機器人的巡邏時間。因此，加入一些隨機性在巡邏路徑上就會是必要的，但接踵而來的問題便是: 怎麼知道加入多少隨機性? 會如何影響效率?(加入隨機性勢必使得巡邏時間拉長，導致效率變差)。而把這種大問題切開來並用數學語言重新定義並釐清問題，最後找出適當的解決辦法以及了解不能解決的部分，便是我身為研究者的工作。

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.