Research conducted by Michigan Tech doctoral candidate James Bialas and faculty members Thomas Oommen (DataS/GMES/CEE) and Timothy Havens (DataS/CS) made news in the Michigan Ag Connection, August 7, 2019. The item is a re-posting of the Michigan Tech Unscripted article, “Found in Translation, which was posted on the Michigan Tech website July 12, 2019.
http://michiganagconnection.com/story-state.php?Id=856&yr=2019
https://www.mtu.edu/news/stories/2019/july/found-in-translation.html
Jeremy Bos’ (DataS/ECE) Paulding Lights Research Part of NPR and WXPR Stories
Ali Ebnenasir (SAS/CS), professor of computer science, is co-author of the article, “On the verification of livelock-freedom and self-stabilization on parameterized rings,” published in the July 2019 issue of the journal ACM Transactions on Computational Logic. The article is co-authored by Alex Klinkhamer of Google.
Abstract: This article investigates the verification of livelock-freedom and self-stabilization on parameterized rings consisting of symmetric, constant space, deterministic, and self-disabling processes. The results of this article have a significant impact on several fields, including scalable distributed systems, resilient and self-* systems, and verification of parameterized systems. First, we identify necessary and sufficient local conditions for the existence of global livelocks in parameterized unidirectional rings with unbounded (but finite) number of processes under the interleaving semantics. Using a reduction from the periodic domino problem, we show that, in general, verifying livelock-freedom of parameterized unidirectional rings is undecidable (specifically, Π10-complete) even for constant space, deterministic, and self-disabling processes. This result implies that verifying self-stabilization for parameterized rings of self-disabling processes is also undecidable. We also show that verifying livelock-freedom and self-stabilization remain undecidable under (1) synchronous execution semantics, (2) the FIFO consistency model, and (3) any scheduling policy. We then present a new scope-based method for detecting and constructing livelocks in parameterized rings. The proposed semi-algorithm behind our scope-based verification is based on a novel paradigm for the detection of livelocks that totally circumvents state space exploration. Our experimental results on an implementation of the proposed semi-algorithm are very promising as we have found livelocks in parameterized rings in a few microseconds on a regular laptop. The results of this article have significant implications for scalable distributed systems with cyclic topologies.
Citation: Klinkhamer, A., & Ebnenasir, A. (2019). On the verification of livelock-freedom and self-stabilization on parameterized rings. ACM Transactions on Computational Logic, 20(3), 16:1-16:36. http://dx.doi.org/10.1145/3326456
MTU Digital Commons link: https://digitalcommons.mtu.edu/michigantech-p/146/
ACM link: https://dl.acm.org/citation.cfm?doid=3338853.3326456
Saeid Nooshabadi (SAS/ECE), professor of electrical and computer engineering, is co-author of the article, “High-dimensional image descriptor matching using highly parallel KD-tree construction and approximate nearest neighbor search,” to be published in the October 2019 issue of the Journal of Parallel and Distributed Computing, which is published by Elsevier. The article is co-authored by Michigan Tech Computer Science department doctoral candidate Linjia Hu.
Abstract: To overcome the high computational cost associated with the high-dimensional digital image descriptor matching, this paper presents a set of integrated parallel algorithms for the construction of K-dimensional tree (KD-tree) and P approximate nearest neighbor search (P-ANNS) on the modern massively parallel architectures (MPA). To improve the runtime performance of the P-ANNS, we propose an efficient sliding window for a parallel buffered P-ANNS on KD-tree to mitigate the high cost of global memory accesses. When applied to high dimensional real-world image descriptor datasets, the proposed KD-tree construction and the buffered P-ANNS algorithms are of comparable matching quality to the traditional sequential counterparts on CPU, while outperforming their serial CPU counterparts by speedup factors of up to 17 and 163, respectively. The algorithms are also studied for the performance impact factors to obtain the optimal runtime configurations for various datasets. Moreover, we verify the features of the parallel algorithms on typical 3D image matching scenarios. With the classical local image descriptor signature of histograms of orientations (SHOT) datasets, the parallel KD-tree construction and image descriptor matching can achieve up to 11 and 138-fold speedups, respectively.
Citation: Hu, L., & Nooshabadi, S. (2019). High-dimensional image descriptor matching using highly parallel KD-tree construction and approximate nearest neighbor search. Journal of Parallel and Distributed Computing, 132, 127-140. http://dx.doi.org/10.1016/j.jpdc.2019.06.003
MTU Digital Commons link: https://digitalcommons.mtu.edu/michigantech-p/145/
Elsevier link: https://www.sciencedirect.com/science/article/pii/S0743731519304319?via%3Dihub
Zhenlin Wang (SAS), professor of computer science, is co-author of the article, “Lightweight and accurate memory allocation in key-value cache,” published in the June 2019 issue of the International Journal of Parallel Programming, which is published by Springer.
Abstract: The use of key-value caches in modern web servers is becoming more and more ubiquitous. Representatively, Memcached as a widely used key-value cache system, originally intended for speeding up dynamic web applications by alleviating database load. One of the key factors affecting the performance of Memcached is the memory allocation among different item classes. How to obtain the most efficient partitioning scheme with low time and space consumption is a focus of attention. In this paper, we propose a lightweight and accurate memory allocation scheme in Memcached, by sampling access patterns, analyzing data locality, and reassigning the memory space. One early study on optimizing memory allocation is LAMA, which uses footprint-based MRC to optimize memory allocation in Memcached. However, LAMA does not model deletion operations in Memcached and its spatial overhead is quite large. We propose a method that consumes only 3% of LAMA space and can handle read, write and deletion operations. Moreover, evaluation results show that the average stable-state miss ratio is reduced by 15.0% and the average stable-state response time is reduced by 12.3% when comparing our method to LAMA.
Citation: Pan, C., Zhou, L., Luo, Y., Wang, X., & Wang, Z. (2019). Lightweight and accurate memory allocation in key-value cache. International Journal of Parallel Programming, 47(3), 451-466.http://dx.doi.org/10.1007/s10766-018-0616-4
Digital Commons link: https://digitalcommons.mtu.edu/michigantech-p/144/
Springer link: https://link.springer.com/article/10.1007%2Fs10766-018-0616-4
Researchers: Myounghoon “Philart” Jeon, PI
Sponsor: National Institutes of Health through the National Robotics Initiative
Amount of Support: $258,362
Abstract: The purpose of the research is to design novel forms of musical interaction combined with physical activities for improving social interactions and emotional responses of children with autism spectrum disorder (ASD). It is well known that a subject with ASD shows deficiency in emotional and social interactions. We propose to address two aspects of this issue: physio-musical stimulus for initiating engagement and empathizing for deepening interaction and thus enhancing a child’s emotional and social interactions. People with or without ASD between the ages of 5 and 10 may join this study.
Summary: In the United States, the rapid increase in the population of children with autism spectrum disorder (ASD) has revealed the deficiency in the realm of therapeutic accessibility for children with ASD in the domain of emotion and social interaction. There have been a number of approaches including several robotic therapeutic systems, but most of these efforts have been centered on speech interaction and task-based turn-taking scenarios. Unfortunately, the spectral diversity of ASD is so vast that many current approaches are, as novel and intriguing as they are, still insufficient to provide parameterized therapeutic tools and approaches.
To overcome this challenge, state-of-the-art techniques must still be developed to facilitate the autonomous interaction methods for robots to effectively stimulate the emotional and social interactivity of children. We focus on the recent studies that reveal strong relevance in premotor cortex among neural domains for music, emotion, and motor behaviors. We propose that musical interaction and activities can provide a new therapeutic domain for effective development in the children’s emotion and social interaction. Of key importance within this proposed work are providing capabilities for the robotic system to monitor the emotional and interactive states of children and provide effective musical and behavioral stimuli with respect to the emotion and social interaction of children. Major research questions include (1) What kinds of music-based signals and music-coordinated activities can play effective roles in encouraging emotional interaction and social engagement?, (2) How can robotic learning of human behaviors during musical activities increase the interaction between human and robot and reinforce the emotional and social engagement?, and (3) What metrics can be designed to effectively measure and evaluate the changes in emotional and social engagement through musical interaction activities?
Intellectual Merits: Designing and evaluating core techniques to fuse music, emotion, and socio-physical interaction should be invaluable to advancing affective computing, robotics, and engineering psychology theory as well as providing guidelines in developing an effective therapeutic robot companion. With this research endeavor, we will identify the most crucial features of musical components in stimulating emotional and interactive intentions of children and the most effective way to correlate those musical components with motion behaviors to maximize the children’s social engagement and development. The findings of the proposed work will also contribute to the design of interactive scenarios for natural and creative therapy with an individualized and systematic approach.
Broader Impacts: The successful development of our framework with the music-based approach has the capability of creating a new domain of pediatric therapy that can tremendously increase the abilities of robots to interact with children in a safe and natural manner. The novelty and significance of this approach correlates to therapeutic design for children with ASD, but the foundation for our interactive and adaptive reinforcement scheme can be extended to other pediatric populations and developmental studies. We plan to incorporate these knowledge and approaches into courses designed for robotics and affective computing. Furthermore, we plan to encapsulate many of these ideas into an “outreach” workshop for underrepresented students. Undergraduate research projects and demonstrations are expected to inspire the next generation of engineers and scientist with a new robot-coexistent world.
Main Results: We have developed an emotion-based robotic motion platform that can encapsulate spatial components as well as emotional dimensions into robotic movement behaviors. The Romo robot and DARwin-OP are first used for our project (Figure 1). The robotic characters and interfaces are also newly designed to accommodate characteristics of children with ASD while satisfying software design specifications. We have also developed a multi-modal analysis system to monitor and quantify physical engagements and emotional reactions of children through facial expression recognition app (Figure 2), Kinect based movement analysis system, voice analysis app, and a music analysis software. All systems are designed for mobile computing environments, so our developed therapy sessions can be installed in any place with proper space and connectivity. We have implemented a sonification server (Figure 3) with 600 emotional sound cues for 30 emotional keywords and a real-time sonification generation platform. We have also carried out extensive user study with Americans and Koreans to validate our sounds and compare cultural differences. The results show that there are some commonalities in terms of emotional sound preferences between the two countries and we can narrow down our emotional sound cues for further research. We have created robotic scenarios for a pilot study (Typical day of Senses & Four Seasons), and will expand the scenarios with diverse genres of music and motion library sets.
Publications
Robotic Sonification for Promoting Emotional and Social Interactions of Children with ASD
Musical Robots for Children with ASD Using a Client-Server Architecture
Researchers: Philart Jeon, PI
Sponsor: Hyundai Motor Company
Amount of Support: $130, 236
Duration of Support: 1 year
Purpose and Target: To investigate effectiveness of an in-vehicle gesture control system and culture-specific sound preference, Michigan Tech will design a prototype of in-air gesture system and auditory displays and conduct successive experiments using a medium fidelity driving simulator.
Technical Background: Touchscreens in vehicles have increased in popularity in recent years. Touchscreens provide many benefits over traditional analog controls like buttons and knobs. They also introduce new problems. Touchscreen use requires relatively high amounts of visual-attentional resources because they are visual displays. Driving is also a visually demanding task. Competition between driving and touchscreen use for visual-attentional resources has been shown to increase unsafe driving behaviors and crash risk
Researchers: Keith Vertanen, PI, Assistant Professor, Computer Science
Sponsor: Google Faculty Research Award
Amount of Support: $47,219
Abstract: While there have been significant improvements to text input on touchscreen mobile devices, entry rates still fall far short of allowing the free-flowing conversion of thought into text. Such free-flowing writing has been estimated to require input at around 67 words-per-minute (wpm) [1]. This is far faster than current mobile text entry methods that have entry rates of 20–40 wpm. The approach we investigate in this project is to accelerate entry by allowing users to enter an abbreviated version of their desired text. Users are allowed to drop letters or entire words, relying on a sentence-based decoder to infer the unabbreviated sentence. This project aims to answer four questions: 1) What sorts of abbreviations, a priori, do users think they should use? 2) How do users change the degree and nature of their abbreviations in response to recognition accuracy? 3) Can we train users to drop parts of their text intelligently in order to aid the decoder? 4) Can we leverage the abbreviation behaviors observed to improve decoder accuracy?
To answer these questions, we adopt a data-driven approach; collecting lots of data, from many users, over long-term use. To this end, we will extend our existing multi-player game Text Blaster [2], deploying the game on the Android app store. Text Blaster’s game play encourages players to type sentences both quickly and accurately. Players adopting successful abbreviation strategies will gain a competitive advantage. Text Blaster provides a platform to not only investigate abbreviated input but also a host of other open research questions in text entry. Data collected via Text Blaster will be released as a public research resource.
References
[1] Kristensson, P.O. and Vertanen, K. (2014). The Inviscid Text Entry Rate and its Application as a Grand Goal for Mobile Text Entry. In MobileHCI 2014, 335-338.
Researcher: Myounghoon “Philart” Jeon, PI
Sponsor: KATRI (Korea Automotive Testing & Research Institute)
Amount of Support: $450,703
Duration of Support: 4 years
Abstract: The goal of the project is to design and evaluate intelligent auditory interactions for improving safety and user experience in the automated vehicles. To this end, we have phased plans for four years. In year 1, we prepare for the driving simulator for the automated driving model. In year 2, we estimate and model driver states in automated vehicles using multiple sensing approaches. In year 3, we design and evaluate discrete auditory alerts for safety purpose, with a focus, specifically, on take-over scenarios. In year 4, we develop real-time sonification systems for overall user experience and make guidelines.
Intellectual Merits: The proposed work will significantly advance theory and practice in the design of natural and intuitive communication between a driver (or occupant) and an automated/autonomous vehicle. The results of the proposed research will not only contribute to design of the current vehicles, but also guide directions of social interaction in the automated vehicles in the near future. We will additionally obtain a theoretical framework to estimate and predict driver state and driving behavior. A more comprehensive understanding of the relationship between multiple sensing (e.g., neurophysiological and behavioral) data and driver states will ultimately be used to construct a more generic driving behavior model capable of combining affective elements and cognitive elements to positively influence safer driving. The proposed work will specifically contribute to the body of current literature in using auditory user interfaces for the automated vehicle contexts. Subsequently, this work will significantly advance theory and practice in interactive sonification design, affective computing, and driving psychology.
Broader Impacts: Applying novel in-vehicle auditory interactions to facilitate take-over process and eco-driving, and to mitigate distractions has the high potential to significantly decrease driving accidents and carbon footprints. Moreover, the entire program of the proposed research can be further developed for other vehicle situations. The proposed work offers an exciting simulated driving platform to integrate research with multidisciplinary STEM (Science, Technology, Engineering & Math) education. The principal investigator of the project will train graduate students, who will mentor undergraduates in the Mind Music Machine Lab at Michigan Tech. Driving simulators will be used for diverse hands-on curricula and courses. The PI will design driving simulation activities to teach courses as part of Michigan Tech’s Summer Youth Programs (SYP). Michigan Tech’s SYP has a strong longitudinal history of recruiting women, rural students from the Upper Peninsula of Michigan, and inner city minority students from the Detroit and Grand Rapids area. They also have a decade of assessment data that demonstrate SYP alumni are more likely to pursue STEM college degrees. The PI will also try to develop close partnerships and collaborations with other universities of the consortium and KATRI in Korea. Students and researchers can come to Michigan Tech and conduct and experience research projects together using cutting edge technologies. Research and education outcomes will be disseminated by the team, through the planned workshop on “New opportunities for in-vehicle auditory interactions in highly automated vehicles” at the International Conference on Auditory Display and AutomotiveUI Conference.
Keith Vertanen (CS/HCC), associate professor of computer science, traveled to Mumbai, India, in July to co-facilitate a three-day workshop on best practices for writing conference papers. The workshop was presented by ACM SIGCHI and its Asian Development C
ommittee, which works to increase its engagement with researchers and practitioners from Asia. The aim of the workshop was to encourage res
earchers from Asia to submit papers for the ACM CHI 2021 Conference on Human Factors in Computing Systems.
Vertanen, who is co-chair of the Usability Subcommittee for CHI 2020, presented lectures on paper writing and experimental design to 20 PhD candidates from various universities in India, Sri Lanka, and South Korea. Vertanen also presented a talk on his text entry research and served on an advisory panel that offered feedback to the PhD students on their research in a forum similar to a doctoral consortium. Also co-facilitating the workshop were faculty members from University of Central Lancashire, UK, KAIST University, South Korea, and Georgia Institute of Technology, Atlanta. Visit https://www.indiahci.org/sigchischool/paperCHI2021/ to learn more about the workshop.