Showing 1–37 of 37 results for author: Ho, H

Enhancing Distractor Generation for Multiple-Choice Questions with Retrieval Augmented Pretraining and Knowledge Graph Integration

Authors: Han-Cheng Yu, Yu-An Shih, Kin-Man Law, Kai-Yu Hsieh, Yu-Chen Cheng, Hsin-Chih Ho, Zih-An Lin, Wen-Chuan Hsu, Yao-Chung Fan

Abstract: In this paper, we tackle the task of distractor generation (DG) for multiple-choice questions. Our study introduces two key designs. First, we propose \textit{retrieval augmented pretraining}, which involves refining the language model pretraining to align it more closely with the downstream task of DG. Second, we explore the integration of knowledge graphs to enhance the performance of DG. Throug… ▽ More In this paper, we tackle the task of distractor generation (DG) for multiple-choice questions. Our study introduces two key designs. First, we propose \textit{retrieval augmented pretraining}, which involves refining the language model pretraining to align it more closely with the downstream task of DG. Second, we explore the integration of knowledge graphs to enhance the performance of DG. Through experiments with benchmarking datasets, we show that our models significantly outperform the state-of-the-art results. Our best-performing model advances the F1@3 score from 14.80 to 16.47 in MCQ dataset and from 15.92 to 16.50 in Sciq dataset. △ Less

Submitted 19 June, 2024; originally announced June 2024.

Comments: Findings at ACL 2024

Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives

Authors: Qi Heng Ho, Martin S. Feather, Federico Rossi, Zachary N. Sunberg, Morteza Lahijanian

Abstract: Partially Observable Markov Decision Processes (POMDPs) are powerful models for sequential decision making under transition and observation uncertainties. This paper studies the challenging yet important problem in POMDPs known as the (indefinite-horizon) Maximal Reachability Probability Problem (MRPP), where the goal is to maximize the probability of reaching some target states. This is also a co… ▽ More Partially Observable Markov Decision Processes (POMDPs) are powerful models for sequential decision making under transition and observation uncertainties. This paper studies the challenging yet important problem in POMDPs known as the (indefinite-horizon) Maximal Reachability Probability Problem (MRPP), where the goal is to maximize the probability of reaching some target states. This is also a core problem in model checking with logical specifications and is naturally undiscounted (discount factor is one). Inspired by the success of point-based methods developed for discounted problems, we study their extensions to MRPP. Specifically, we focus on trial-based heuristic search value iteration techniques and present a novel algorithm that leverages the strengths of these techniques for efficient exploration of the belief space (informed search via value bounds) while addressing their drawbacks in handling loops for indefinite-horizon problems. The algorithm produces policies with two-sided bounds on optimal reachability probabilities. We prove convergence to an optimal policy from below under certain conditions. Experimental evaluations on a suite of benchmarks show that our algorithm outperforms existing methods in almost all cases in both probability guarantees and computation time. △ Less

Submitted 4 June, 2024; originally announced June 2024.

Comments: Accepted to the Conference on Uncertainty in Artificial Intelligence (UAI) 2024

4D-DRESS: A 4D Dataset of Real-world Human Clothing with Semantic Annotations

Authors: Wenbo Wang, Hsuan-I Ho, Chen Guo, Boxiang Rong, Artur Grigorev, Jie Song, Juan Jose Zarate, Otmar Hilliges

Abstract: The studies of human clothing for digital avatars have predominantly relied on synthetic datasets. While easy to collect, synthetic data often fall short in realism and fail to capture authentic clothing dynamics. Addressing this gap, we introduce 4D-DRESS, the first real-world 4D dataset advancing human clothing research with its high-quality 4D textured scans and garment meshes. 4D-DRESS capture… ▽ More The studies of human clothing for digital avatars have predominantly relied on synthetic datasets. While easy to collect, synthetic data often fall short in realism and fail to capture authentic clothing dynamics. Addressing this gap, we introduce 4D-DRESS, the first real-world 4D dataset advancing human clothing research with its high-quality 4D textured scans and garment meshes. 4D-DRESS captures 64 outfits in 520 human motion sequences, amounting to 78k textured scans. Creating a real-world clothing dataset is challenging, particularly in annotating and segmenting the extensive and complex 4D human scans. To address this, we develop a semi-automatic 4D human parsing pipeline. We efficiently combine a human-in-the-loop process with automation to accurately label 4D scans in diverse garments and body movements. Leveraging precise annotations and high-quality garment meshes, we establish several benchmarks for clothing simulation and reconstruction. 4D-DRESS offers realistic and challenging data that complements synthetic sources, paving the way for advancements in research of lifelike human clothing. Website: https://ait.ethz.ch/4d-dress. △ Less

Submitted 29 April, 2024; originally announced April 2024.

Comments: CVPR 2024 paper, 21 figures, 9 tables

"It's Not a Replacement:" Enabling Parent-Robot Collaboration to Support In-Home Learning Experiences of Young Children

Authors: Hui-Ru Ho, Edward Hubbard, Bilge Mutlu

Abstract: Learning companion robots for young children are increasingly adopted in informal learning environments. Although parents play a pivotal role in their children's learning, very little is known about how parents prefer to incorporate robots into their children's learning activities. We developed prototype capabilities for a learning companion robot to deliver educational prompts and responses to pa… ▽ More Learning companion robots for young children are increasingly adopted in informal learning environments. Although parents play a pivotal role in their children's learning, very little is known about how parents prefer to incorporate robots into their children's learning activities. We developed prototype capabilities for a learning companion robot to deliver educational prompts and responses to parent-child pairs during reading sessions and conducted in-home user studies involving 10 families with children aged 3-5. Our data indicates that parents want to work with robots as collaborators to augment parental activities to foster children's learning, introducing the notion of parent-robot collaboration. Our findings offer an empirical understanding of the needs and challenges of parent-child interaction in informal learning scenarios and design opportunities for integrating a companion robot into these interactions. We offer insights into how robots might be designed to facilitate parent-robot collaboration, including parenting policies, collaboration patterns, and interaction paradigms. △ Less

Submitted 20 March, 2024; originally announced March 2024.

DNABERT-S: Learning Species-Aware DNA Embedding with Genome Foundation Models

Authors: Zhihan Zhou, Weimin Wu, Harrison Ho, Jiayi Wang, Lizhen Shi, Ramana V Davuluri, Zhong Wang, Han Liu

Abstract: Effective DNA embedding remains crucial in genomic analysis, particularly in scenarios lacking labeled data for model fine-tuning, despite the significant advancements in genome foundation models. A prime example is metagenomics binning, a critical process in microbiome research that aims to group DNA sequences by their species from a complex mixture of DNA sequences derived from potentially thous… ▽ More Effective DNA embedding remains crucial in genomic analysis, particularly in scenarios lacking labeled data for model fine-tuning, despite the significant advancements in genome foundation models. A prime example is metagenomics binning, a critical process in microbiome research that aims to group DNA sequences by their species from a complex mixture of DNA sequences derived from potentially thousands of distinct, often uncharacterized species. To fill the lack of effective DNA embedding models, we introduce DNABERT-S, a genome foundation model that specializes in creating species-aware DNA embeddings. To encourage effective embeddings to error-prone long-read DNA sequences, we introduce Manifold Instance Mixup (MI-Mix), a contrastive objective that mixes the hidden representations of DNA sequences at randomly selected layers and trains the model to recognize and differentiate these mixed proportions at the output layer. We further enhance it with the proposed Curriculum Contrastive Learning (C$^2$LR) strategy. Empirical results on 18 diverse datasets showed DNABERT-S's remarkable performance. It outperforms the top baseline's performance in 10-shot species classification with just a 2-shot training while doubling the Adjusted Rand Index (ARI) in species clustering and substantially increasing the number of correctly identified species in metagenomics binning. The code, data, and pre-trained model are publicly available at https://github.com/Zhihan1996/DNABERT_S. △ Less

Submitted 14 February, 2024; v1 submitted 13 February, 2024; originally announced February 2024.

SiTH: Single-view Textured Human Reconstruction with Image-Conditioned Diffusion

Authors: Hsuan-I Ho, Jie Song, Otmar Hilliges

Abstract: A long-standing goal of 3D human reconstruction is to create lifelike and fully detailed 3D humans from single-view images. The main challenge lies in inferring unknown body shapes, appearances, and clothing details in areas not visible in the images. To address this, we propose SiTH, a novel pipeline that uniquely integrates an image-conditioned diffusion model into a 3D mesh reconstruction workf… ▽ More A long-standing goal of 3D human reconstruction is to create lifelike and fully detailed 3D humans from single-view images. The main challenge lies in inferring unknown body shapes, appearances, and clothing details in areas not visible in the images. To address this, we propose SiTH, a novel pipeline that uniquely integrates an image-conditioned diffusion model into a 3D mesh reconstruction workflow. At the core of our method lies the decomposition of the challenging single-view reconstruction problem into generative hallucination and reconstruction subproblems. For the former, we employ a powerful generative diffusion model to hallucinate unseen back-view appearance based on the input images. For the latter, we leverage skinned body meshes as guidance to recover full-body texture meshes from the input and back-view images. SiTH requires as few as 500 3D human scans for training while maintaining its generality and robustness to diverse images. Extensive evaluations on two 3D human benchmarks, including our newly created one, highlighted our method's superior accuracy and perceptual quality in 3D textured human reconstruction. Our code and evaluation benchmark are available at https://ait.ethz.ch/sith △ Less

Submitted 30 March, 2024; v1 submitted 27 November, 2023; originally announced November 2023.

Comments: 23 pages, 23 figures, CVPR 2024

Recursively-Constrained Partially Observable Markov Decision Processes

Authors: Qi Heng Ho, Tyler Becker, Benjamin Kraske, Zakariya Laouar, Martin S. Feather, Federico Rossi, Morteza Lahijanian, Zachary N. Sunberg

Abstract: Many sequential decision problems involve optimizing one objective function while imposing constraints on other objectives. Constrained Partially Observable Markov Decision Processes (C-POMDP) model this case with transition uncertainty and partial observability. In this work, we first show that C-POMDPs violate the optimal substructure property over successive decision steps and thus may exhibit… ▽ More Many sequential decision problems involve optimizing one objective function while imposing constraints on other objectives. Constrained Partially Observable Markov Decision Processes (C-POMDP) model this case with transition uncertainty and partial observability. In this work, we first show that C-POMDPs violate the optimal substructure property over successive decision steps and thus may exhibit behaviors that are undesirable for some (e.g., safety critical) applications. Additionally, online re-planning in C-POMDPs is often ineffective due to the inconsistency resulting from this violation. To address these drawbacks, we introduce the Recursively-Constrained POMDP (RC-POMDP), which imposes additional history-dependent cost constraints on the C-POMDP. We show that, unlike C-POMDPs, RC-POMDPs always have deterministic optimal policies and that optimal policies obey Bellman's principle of optimality. We also present a point-based dynamic programming algorithm for RC-POMDPs. Evaluations on benchmark problems demonstrate the efficacy of our algorithm and show that policies for RC-POMDPs produce more desirable behaviors than policies for C-POMDPs. △ Less

Submitted 4 June, 2024; v1 submitted 14 October, 2023; originally announced October 2023.

Comments: Accepted to the Conference on Uncertainty in Artificial Intelligence (UAI) 2024

Autonomous Navigation of Micro Air Vehicles in Warehouses Using Vision-based Line Following

Authors: Ling Shuang Soh, Hann Woei Ho

Abstract: In this paper, we propose a vision-based solution for indoor Micro Air Vehicle (MAV) navigation, with a primary focus on its application within autonomous warehouses. Our work centers on the utilization of a single camera as the primary sensor for tasks such as detection, localization, and path planning. To achieve these objectives, we implement the HSV color detection and the Hough Line Transform… ▽ More In this paper, we propose a vision-based solution for indoor Micro Air Vehicle (MAV) navigation, with a primary focus on its application within autonomous warehouses. Our work centers on the utilization of a single camera as the primary sensor for tasks such as detection, localization, and path planning. To achieve these objectives, we implement the HSV color detection and the Hough Line Transform for effective line detection within warehouse environments. The integration of a Kalman filter into our system enables the camera to track yellow lines reliably. We evaluated the performance of our vision-based line following algorithm through various MAV flight tests conducted in the Gazebo 11 platform, utilizing ROS Noetic. The results of these simulations demonstrate the system capability to successfully navigate narrow indoor spaces. Our proposed system has the potential to significantly reduce labor costs and enhance overall productivity in warehouse operations. This work contributes to the growing field of MAV applications in autonomous warehouses, addressing the need for efficient logistics and supply chain solutions. △ Less

Submitted 2 October, 2023; originally announced October 2023.

A Comprehensive Review on Tree Detection Methods Using Point Cloud and Aerial Imagery from Unmanned Aerial Vehicles

Authors: Weijie Kuang, Hann Woei Ho, Ye Zhou, Shahrel Azmin Suandi, Farzad Ismail

Abstract: Unmanned Aerial Vehicles (UAVs) are considered cutting-edge technology with highly cost-effective and flexible usage scenarios. Although many papers have reviewed the application of UAVs in agriculture, the review of the application for tree detection is still insufficient. This paper focuses on tree detection methods applied to UAV data collected by UAVs. There are two kinds of data, the point cl… ▽ More Unmanned Aerial Vehicles (UAVs) are considered cutting-edge technology with highly cost-effective and flexible usage scenarios. Although many papers have reviewed the application of UAVs in agriculture, the review of the application for tree detection is still insufficient. This paper focuses on tree detection methods applied to UAV data collected by UAVs. There are two kinds of data, the point cloud and the images, which are acquired by the Light Detection and Ranging (LiDAR) sensor and camera, respectively. Among the detection methods using point-cloud data, this paper mainly classifies these methods according to LiDAR and Digital Aerial Photography (DAP). For the detection methods using images directly, this paper reviews these methods by whether or not to use the Deep Learning (DL) method. Our review concludes and analyses the comparison and combination between the application of LiDAR-based and DAP-based point cloud data. The performance, relative merits, and application fields of the methods are also introduced. Meanwhile, this review counts the number of tree detection studies using different methods in recent years. From our statics, the detection task using DL methods on the image has become a mainstream trend as the number of DL-based detection researches increases to 45% of the total number of tree detection studies up to 2022. As a result, this review could help and guide researchers who want to carry out tree detection on specific forests and for farmers to use UAVs in managing agriculture production. △ Less

Submitted 6 October, 2023; v1 submitted 28 September, 2023; originally announced September 2023.

Comments: This paper has been submitted to Computers and Electronics in Agriculture for review

Incremental Nonlinear Dynamic Inversion based Optical Flow Control for Flying Robots: An Efficient Data-driven Approach

Authors: Hann Woei Ho, Ye Zhou

Abstract: This paper presents a novel approach for optical flow control of Micro Air Vehicles (MAVs). The task is challenging due to the nonlinearity of optical flow observables. Our proposed Incremental Nonlinear Dynamic Inversion (INDI) control scheme incorporates an efficient data-driven method to address the nonlinearity. It directly estimates the inverse of the time-varying control effectiveness in rea… ▽ More This paper presents a novel approach for optical flow control of Micro Air Vehicles (MAVs). The task is challenging due to the nonlinearity of optical flow observables. Our proposed Incremental Nonlinear Dynamic Inversion (INDI) control scheme incorporates an efficient data-driven method to address the nonlinearity. It directly estimates the inverse of the time-varying control effectiveness in real-time, eliminating the need for the constant assumption and avoiding high computation in traditional INDI. This approach effectively handles fast-changing system dynamics commonly encountered in optical flow control, particularly height-dependent changes. We demonstrate the robustness and efficiency of the proposed control scheme in numerical simulations and also real-world flight tests: multiple landings of an MAV on a static and flat surface with various tracking setpoints, hovering and landings on moving and undulating surfaces. Despite being challenged with the presence of noisy optical flow estimates and the lateral and vertical movement of the landing surfaces, the MAV is able to successfully track or land on the surface with an exponential decay of both height and vertical velocity at almost the same time, as desired. △ Less

Submitted 5 July, 2023; originally announced July 2023.

Journal ref: Proceedings of Robotics: Science and Systems 2023

Designing Parent-child-robot Interactions to Facilitate In-Home Parental Math Talk with Young Children

Authors: Hui-Ru Ho, Nathan White, Edward Hubbard, Bilge Mutlu

Abstract: Parent-child interaction is critical for child development, yet parents may need guidance in some aspects of their engagement with their children. Current research on educational math robots focuses on child-robot interactions but falls short of including the parents and integrating the critical role they play in children's learning. We explore how educational robots can be designed to facilitate… ▽ More Parent-child interaction is critical for child development, yet parents may need guidance in some aspects of their engagement with their children. Current research on educational math robots focuses on child-robot interactions but falls short of including the parents and integrating the critical role they play in children's learning. We explore how educational robots can be designed to facilitate parent-child conversations, focusing on math talk, a predictor of later math ability in children. We prototyped capabilities for a social robot to support math talk via reading and play activities and conducted an exploratory Wizard-of-Oz in-home study for parent-child interactions facilitated by a robot. Our findings yield insights into how parents were inspired by the robot's prompts, their desired interaction styles and methods for the robot, and how they wanted to include the robot in the activities, leading to guidelines for the design of parent-child-robot interaction in educational contexts. △ Less

Submitted 3 May, 2023; originally announced May 2023.

Comments: 15 pages, Accepted to IDC'23

Learning Locally Editable Virtual Humans

Authors: Hsuan-I Ho, Lixin Xue, Jie Song, Otmar Hilliges

Abstract: In this paper, we propose a novel hybrid representation and end-to-end trainable network architecture to model fully editable and customizable neural avatars. At the core of our work lies a representation that combines the modeling power of neural fields with the ease of use and inherent 3D consistency of skinned meshes. To this end, we construct a trainable feature codebook to store local geometr… ▽ More In this paper, we propose a novel hybrid representation and end-to-end trainable network architecture to model fully editable and customizable neural avatars. At the core of our work lies a representation that combines the modeling power of neural fields with the ease of use and inherent 3D consistency of skinned meshes. To this end, we construct a trainable feature codebook to store local geometry and texture features on the vertices of a deformable body model, thus exploiting its consistent topology under articulation. This representation is then employed in a generative auto-decoder architecture that admits fitting to unseen scans and sampling of realistic avatars with varied appearances and geometries. Furthermore, our representation allows local editing by swapping local features between 3D assets. To verify our method for avatar creation and editing, we contribute a new high-quality dataset, dubbed CustomHumans, for training and evaluation. Our experiments quantitatively and qualitatively show that our method generates diverse detailed avatars and achieves better model fitting performance compared to state-of-the-art methods. Our code and dataset are available at https://custom-humans.github.io/. △ Less

Submitted 28 April, 2023; originally announced May 2023.

Comments: 12+11 pages, CVPR'23, project page https://custom-humans.github.io/

Sampling-based Reactive Synthesis for Nondeterministic Hybrid Systems

Authors: Qi Heng Ho, Zachary N. Sunberg, Morteza Lahijanian

Abstract: This paper introduces a sampling-based strategy synthesis algorithm for nondeterministic hybrid systems with complex continuous dynamics under temporal and reachability constraints. We model the evolution of the hybrid system as a two-player game, where the nondeterminism is an adversarial player whose objective is to prevent achieving temporal and reachability goals. The aim is to synthesize a wi… ▽ More This paper introduces a sampling-based strategy synthesis algorithm for nondeterministic hybrid systems with complex continuous dynamics under temporal and reachability constraints. We model the evolution of the hybrid system as a two-player game, where the nondeterminism is an adversarial player whose objective is to prevent achieving temporal and reachability goals. The aim is to synthesize a winning strategy -- a reactive (robust) strategy that guarantees the satisfaction of the goals under all possible moves of the adversarial player. Our proposed approach involves growing a (search) game-tree in the hybrid space by combining sampling-based motion planning with a novel bandit-based technique to select and improve on partial strategies. We show that the algorithm is probabilistically complete, i.e., the algorithm will asymptotically almost surely find a winning strategy, if one exists. The case studies and benchmark results show that our algorithm is general and effective, and consistently outperforms state of the art algorithms. △ Less

Submitted 23 December, 2023; v1 submitted 13 April, 2023; originally announced April 2023.

Comments: Published in IEEE Robotics and Automation Letters (RA-L)

Journal ref: IEEE Robotics and Automation Letters, vol. 9, no. 2, pp. 931-938, 2024

Planning with SiMBA: Motion Planning under Uncertainty for Temporal Goals using Simplified Belief Guides

Authors: Qi Heng Ho, Zachary N. Sunberg, Morteza Lahijanian

Abstract: This paper presents a new multi-layered algorithm for motion planning under motion and sensing uncertainties for Linear Temporal Logic specifications. We propose a technique to guide a sampling-based search tree in the combined task and belief space using trajectories from a simplified model of the system, to make the problem computationally tractable. Our method eliminates the need to construct f… ▽ More This paper presents a new multi-layered algorithm for motion planning under motion and sensing uncertainties for Linear Temporal Logic specifications. We propose a technique to guide a sampling-based search tree in the combined task and belief space using trajectories from a simplified model of the system, to make the problem computationally tractable. Our method eliminates the need to construct fine and accurate finite abstractions. We prove correctness and probabilistic completeness of our algorithm, and illustrate the benefits of our approach on several case studies. Our results show that guidance with a simplified belief space model allows for significant speed-up in planning for complex specifications. △ Less

Submitted 9 April, 2023; v1 submitted 18 October, 2022; originally announced October 2022.

Comments: 8 pages, to appear in the IEEE International Conference on Robotics and Automation (ICRA), 2023

Chance-Constrained Motion Planning with Event-Triggered Estimation

Authors: Anne Theurkauf, Qi Heng Ho, Roland Ilyes, Nisar Ahmed, Morteza Lahijanian

Abstract: We consider the problem of autonomous navigation using limited information from a remote sensor network. Because the remote sensors are power and bandwidth limited, we use event-triggered (ET) estimation to manage communication costs. We introduce a fast and efficient sampling-based planner which computes motion plans coupled with ET communication strategies that minimize communication costs, whil… ▽ More We consider the problem of autonomous navigation using limited information from a remote sensor network. Because the remote sensors are power and bandwidth limited, we use event-triggered (ET) estimation to manage communication costs. We introduce a fast and efficient sampling-based planner which computes motion plans coupled with ET communication strategies that minimize communication costs, while satisfying constraints on the probability of reaching the goal region and the point-wise probability of collision. We derive a novel method for offline propagation of the expected state distribution, and corresponding bounds on this distribution. These bounds are used to evaluate the chance constraints in the algorithm. Case studies establish the validity of our approach, demonstrating fast computation of optimal plans. △ Less

Submitted 20 March, 2023; v1 submitted 13 October, 2022; originally announced October 2022.

Comments: 8 pages, to appear in IEEE International Conference on Robotics and Automation (ICRA), 2023

Stochastic Robustness Interval for Motion Planning with Signal Temporal Logic

Authors: Roland B. Ilyes, Qi Heng Ho, Morteza Lahijanian

Abstract: In this work, we present a novel robustness measure for continuous-time stochastic trajectories with respect to Signal Temporal Logic (STL) specifications. We show the soundness of the measure and develop a monitor for reasoning about partial trajectories. Using this monitor, we introduce an STL sampling-based motion planning algorithm for robots under uncertainty. Given a minimum robustness requi… ▽ More In this work, we present a novel robustness measure for continuous-time stochastic trajectories with respect to Signal Temporal Logic (STL) specifications. We show the soundness of the measure and develop a monitor for reasoning about partial trajectories. Using this monitor, we introduce an STL sampling-based motion planning algorithm for robots under uncertainty. Given a minimum robustness requirement, this algorithm finds satisfying motion plans; alternatively, the algorithm also optimizes for the measure. We prove probabilistic completeness and asymptotic optimality, and demonstrate the effectiveness of our approach on several case studies. △ Less

Submitted 28 May, 2023; v1 submitted 10 October, 2022; originally announced October 2022.

Automaton-Guided Control Synthesis for Signal Temporal Logic Specifications

Authors: Qi Heng Ho, Roland B. Ilyes, Zachary N. Sunberg, Morteza Lahijanian

Abstract: This paper presents an algorithmic framework for control synthesis of continuous dynamical systems subject to signal temporal logic (STL) specifications. We propose a novel algorithm to obtain a time-partitioned finite automaton from an STL specification, and introduce a multi-layered framework that utilizes this automaton to guide a sampling-based search tree both spatially and temporally. Our ap… ▽ More This paper presents an algorithmic framework for control synthesis of continuous dynamical systems subject to signal temporal logic (STL) specifications. We propose a novel algorithm to obtain a time-partitioned finite automaton from an STL specification, and introduce a multi-layered framework that utilizes this automaton to guide a sampling-based search tree both spatially and temporally. Our approach is able to synthesize a controller for nonlinear dynamics and polynomial predicate functions. We prove the correctness and probabilistic completeness of our algorithm, and illustrate the efficiency and efficacy of our framework on several case studies. Our results show an order of magnitude speedup over the state of the art. △ Less

Submitted 4 October, 2022; v1 submitted 7 July, 2022; originally announced July 2022.

Comments: 8 pages, 3 figures, to appear in CDC 2022

Gaussian Belief Trees for Chance Constrained Asymptotically Optimal Motion Planning

Authors: Qi Heng Ho, Zachary N. Sunberg, Morteza Lahijanian

Abstract: In this paper, we address the problem of sampling-based motion planning under motion and measurement uncertainty with probabilistic guarantees. We generalize traditional sampling-based tree-based motion planning algorithms for deterministic systems and propose belief-$\mathcal{A}$, a framework that extends any kinodynamical tree-based planner to the belief space for linear (or linearizable) system… ▽ More In this paper, we address the problem of sampling-based motion planning under motion and measurement uncertainty with probabilistic guarantees. We generalize traditional sampling-based tree-based motion planning algorithms for deterministic systems and propose belief-$\mathcal{A}$, a framework that extends any kinodynamical tree-based planner to the belief space for linear (or linearizable) systems. We introduce appropriate sampling techniques and distance metrics for the belief space that preserve the probabilistic completeness and asymptotic optimality properties of the underlying planner. We demonstrate the efficacy of our approach for finding safe low-cost paths efficiently and asymptotically optimally in simulation, for both holonomic and non-holonomic systems. △ Less

Submitted 4 October, 2022; v1 submitted 24 February, 2022; originally announced February 2022.

Comments: 9 pages, 4 figures. In ICRA 2022

Render In-between: Motion Guided Video Synthesis for Action Interpolation

Authors: Hsuan-I Ho, Xu Chen, Jie Song, Otmar Hilliges

Abstract: Upsampling videos of human activity is an interesting yet challenging task with many potential applications ranging from gaming to entertainment and sports broadcasting. The main difficulty in synthesizing video frames in this setting stems from the highly complex and non-linear nature of human motion and the complex appearance and texture of the body. We propose to address these issues in a motio… ▽ More Upsampling videos of human activity is an interesting yet challenging task with many potential applications ranging from gaming to entertainment and sports broadcasting. The main difficulty in synthesizing video frames in this setting stems from the highly complex and non-linear nature of human motion and the complex appearance and texture of the body. We propose to address these issues in a motion-guided frame-upsampling framework that is capable of producing realistic human motion and appearance. A novel motion model is trained to inference the non-linear skeletal motion between frames by leveraging a large-scale motion-capture dataset (AMASS). The high-frame-rate pose predictions are then used by a neural rendering pipeline to produce the full-frame output, taking the pose and background consistency into consideration. Our pipeline only requires low-frame-rate videos and unpaired human motion data but does not require high-frame-rate videos for training. Furthermore, we contribute the first evaluation dataset that consists of high-quality and high-frame-rate videos of human activities for this task. Compared with state-of-the-art video interpolation techniques, our method produces in-between frames with better quality and accuracy, which is evident by state-of-the-art results on pixel-level, distributional metrics and comparative user evaluations. Our code and the collected dataset are available at https://git.io/Render-In-Between. △ Less

Submitted 1 November, 2021; originally announced November 2021.

Comments: 12 pages

An Effective Early Multi-core System Shared Cache Design Method Based on Reuse-distance Analysis

Authors: Hsin-Yu Ho, Ren-Song Tsay

Abstract: In this paper, we proposed an effective and efficient multi-core shared-cache design optimization approach based on reuse-distance analysis of the data traces of target applications. Since data traces are independent of system hardware architectures, a designer can easily compute the best cache design at the early system design phase using our approach. We devise a very efficient and yet accurate… ▽ More In this paper, we proposed an effective and efficient multi-core shared-cache design optimization approach based on reuse-distance analysis of the data traces of target applications. Since data traces are independent of system hardware architectures, a designer can easily compute the best cache design at the early system design phase using our approach. We devise a very efficient and yet accurate method to derive the aggregated reuse-distance histograms of concurrent applications for accurate cache performance analysis and optimization. Essentially, the actual shared-cache contention results of concurrent applications are embedded in the aggregated reuse-distance histograms and therefore the approach is very effective. The experimental results show that the average error rate of shared-cache miss-count estimations of our approach is less than 2.4%. Using a simple scanning search method, one can easily determine the true optimal cache configurations at the early system design phase. △ Less

Submitted 9 September, 2021; originally announced September 2021.

On the binary adder channel with complete feedback, with an application to quantitative group testing

Authors: Samuel H. Florin, Matthew H. Ho, Zilin Jiang

Abstract: We determine the exact value of the optimal symmetric rate point $(r, r)$ in the Dueck zero-error capacity region of the binary adder channel with complete feedback. We proved that the average zero-error capacity $r = h(1/2-δ) \approx 0.78974$, where $h(\cdot)$ is the binary entropy function and $δ= 1/(2\log_2(2+\sqrt3))$. Our motivation is a problem in quantitative group testing. Given a set of… ▽ More We determine the exact value of the optimal symmetric rate point $(r, r)$ in the Dueck zero-error capacity region of the binary adder channel with complete feedback. We proved that the average zero-error capacity $r = h(1/2-δ) \approx 0.78974$, where $h(\cdot)$ is the binary entropy function and $δ= 1/(2\log_2(2+\sqrt3))$. Our motivation is a problem in quantitative group testing. Given a set of $n$ elements two of which are defective, the quantitative group testing problem asks for the identification of these two defectives through a series of tests. Each test gives the number of defectives contained in the tested subset, and the outcomes of previous tests are assumed known at the time of designing the current test. We establish that the minimum number of tests is asymptotic to $(\log_2 n) / r$ as $n \to \infty$. △ Less

Submitted 28 December, 2021; v1 submitted 25 January, 2021; originally announced January 2021.

Comments: 39 pages, 3 figures, accepted to IEEE Trans. Inf. Theory, corrections suggested by the referees have been incorporated

MSC Class: 94A17; 94A24; 94A40

Journal ref: IEEE Transactions on Information Theory, Volume 68, Issue 5, pp 2839-2856, May 2022

When and how CNNs generalize to out-of-distribution category-viewpoint combinations

Authors: Spandan Madan, Timothy Henry, Jamell Dozier, Helen Ho, Nishchal Bhandari, Tomotake Sasaki, Frédo Durand, Hanspeter Pfister, Xavier Boix

Abstract: Object recognition and viewpoint estimation lie at the heart of visual understanding. Recent works suggest that convolutional neural networks (CNNs) fail to generalize to out-of-distribution (OOD) category-viewpoint combinations, ie. combinations not seen during training. In this paper, we investigate when and how such OOD generalization may be possible by evaluating CNNs trained to classify both… ▽ More Object recognition and viewpoint estimation lie at the heart of visual understanding. Recent works suggest that convolutional neural networks (CNNs) fail to generalize to out-of-distribution (OOD) category-viewpoint combinations, ie. combinations not seen during training. In this paper, we investigate when and how such OOD generalization may be possible by evaluating CNNs trained to classify both object category and 3D viewpoint on OOD combinations, and identifying the neural mechanisms that facilitate such OOD generalization. We show that increasing the number of in-distribution combinations (ie. data diversity) substantially improves generalization to OOD combinations, even with the same amount of training data. We compare learning category and viewpoint in separate and shared network architectures, and observe starkly different trends on in-distribution and OOD combinations, ie. while shared networks are helpful in-distribution, separate networks significantly outperform shared ones at OOD combinations. Finally, we demonstrate that such OOD generalization is facilitated by the neural mechanism of specialization, ie. the emergence of two types of neurons -- neurons selective to category and invariant to viewpoint, and vice versa. △ Less

Submitted 17 November, 2021; v1 submitted 15 July, 2020; originally announced July 2020.

On the environment-destructive probabilistic trends: a perceptual and behavioral study on video game players

Authors: Quan-Hoang Vuong, Manh-Toan Ho, Minh-Hoang Nguyen, Thanh-Hang Pham, Hoang-Anh Ho, Thu-Trang Vuong, Viet-Phuong La

Abstract: Currently, gaming is the world's favorite form of entertainment. Various studies have shown how games impact players' perceptions and behaviors, prompting opportunities for purposes beyond entertainment. This study uses Animal Crossing: New Horizons (ACNH), a real-time life-simulation game, as a unique case study of how video games can affect humans' environmental perceptions. A dataset of 584 obs… ▽ More Currently, gaming is the world's favorite form of entertainment. Various studies have shown how games impact players' perceptions and behaviors, prompting opportunities for purposes beyond entertainment. This study uses Animal Crossing: New Horizons (ACNH), a real-time life-simulation game, as a unique case study of how video games can affect humans' environmental perceptions. A dataset of 584 observations from a survey of ACNH players and the Hamiltonian MCMC technique has enabled us to explore the relationship between in-game behaviors and perceptions. The findings indicate a probabilistic trend towards exploiting the in-game environment despite players' perceptions, suggesting that the simplification of commercial game design may overlook opportunities to engage players in pro-environmental activities. △ Less

Submitted 17 June, 2020; originally announced June 2020.

Comments: 6 pages, 2 figures, 1 table

Report number: AISDL-2006-A

Online Multi-Target Tracking for Maneuvering Vehicles in Dynamic Road Context

Authors: Zehui Meng, Qi Heng Ho, Zefan Huang, Hongliang Guo, Marcelo H. Ang Jr., Daniela Rus

Abstract: Target detection and tracking provides crucial information for motion planning and decision making in autonomous driving. This paper proposes an online multi-object tracking (MOT) framework with tracking-by-detection for maneuvering vehicles under motion uncertainty in dynamic road context. We employ a point cloud based vehicle detector to provide real-time 3D bounding boxes of detected vehicles a… ▽ More Target detection and tracking provides crucial information for motion planning and decision making in autonomous driving. This paper proposes an online multi-object tracking (MOT) framework with tracking-by-detection for maneuvering vehicles under motion uncertainty in dynamic road context. We employ a point cloud based vehicle detector to provide real-time 3D bounding boxes of detected vehicles and conduct the online bipartite optimization of the maneuver-orientated data association between the detections and the targets. Kalman Filter (KF) is adopted as the backbone for multi-object tracking. In order to entertain the maneuvering uncertainty, we leverage the interacting multiple model (IMM) approach to obtain the \textit{a-posterior} residual as the cost for each association hypothesis, which is calculated with the hybrid model posterior (after mode-switch). Road context is integrated to conduct adjustments of the time varying transition probability matrix (TPM) of the IMM to regulate the maneuvers according to road segments and traffic sign/signals, with which the data association is performed in a unified spatial-temporal fashion. Experiments show our framework is able to effectively track multiple vehicles with maneuvers subject to dynamic road context and localization drift. △ Less

Submitted 2 December, 2019; originally announced December 2019.

Comments: Submitted to ICRA 2020

Revisiting Timed Logics with Automata Modalities

Authors: Hsi-Ming Ho

Abstract: It is well known that (timed) $ω$-regular properties such as `p holds at every even position' and `p occurs at least three times within the next 10 time units' cannot be expressed in Metric Interval Temporal Logic ($\mathsf{MITL}$) and Event Clock Logic ($\mathsf{ECL}$). A standard remedy to this deficiency is to extend these with modalities defined in terms of automata. In this paper, we show tha… ▽ More It is well known that (timed) $ω$-regular properties such as `p holds at every even position' and `p occurs at least three times within the next 10 time units' cannot be expressed in Metric Interval Temporal Logic ($\mathsf{MITL}$) and Event Clock Logic ($\mathsf{ECL}$). A standard remedy to this deficiency is to extend these with modalities defined in terms of automata. In this paper, we show that the logics $\mathsf{EMITL}_{0,\infty}$ (adding non-deterministic finite automata modalities into the fragment of $\mathsf{MITL}$ with only lower- and upper-bound constraints) and $\mathsf{EECL}$ (adding automata modalities into $\mathsf{ECL}$) are already as expressive as $\mathsf{EMITL}$ (full $\mathsf{MITL}$ with automata modalities). In particular, the satisfiability and model-checking problems for $\mathsf{EMITL}_{0,\infty}$ and $\mathsf{EECL}$ are PSPACE-complete, whereas the same problems for $\mathsf{EMITL}$ are EXPSPACE-complete. We also provide a simple translation from $\mathsf{EMITL}_{0,\infty}$ to diagonal-free timed automata, which enables practical satisfiability and model checking based on off-the-shelf tools. △ Less

Submitted 25 December, 2018; originally announced December 2018.

Comments: To appear in HSCC'19

On Verifying Timed Hyperproperties

Authors: Hsi-Ming Ho, Ruoyu Zhou, Timothy M. Jones

Abstract: We study the satisfiability and model-checking problems for timed hyperproperties specified with HyperMTL, a timed extension of HyperLTL. Depending on whether interleaving of events in different traces is allowed, two possible semantics can be defined for timed hyperproperties: asynchronous and synchronous. While the satisfiability problem can be decided similarly to HyperLTL regardless of the cho… ▽ More We study the satisfiability and model-checking problems for timed hyperproperties specified with HyperMTL, a timed extension of HyperLTL. Depending on whether interleaving of events in different traces is allowed, two possible semantics can be defined for timed hyperproperties: asynchronous and synchronous. While the satisfiability problem can be decided similarly to HyperLTL regardless of the choice of semantics, we show that the model-checking problem, unless the specification is alternation-free, is undecidable even when very restricted timing constraints are allowed. On the positive side, we show that model checking HyperMTL with quantifier alternations is possible under certain conditions in the synchronous semantics, or when there is a fixed bound on the length of the time domain. △ Less

Submitted 24 December, 2018; originally announced December 2018.

A Novel Approach for Network Attack Classification Based on Sequential Questions

Authors: Md Mehedi Hassan Onik, Nasr Al-Zaben, Hung Phan Hoo, Chul-Soo Kim

Abstract: With the development of incipient technologies, user devices becoming more exposed and ill-used by foes. In upcoming decades, traditional security measures will not be sufficient enough to handle this huge threat towards distributed hardware and software. Lack of standard network attack taxonomy has become an indispensable dispute on developing a clear understanding about the attacks in order to h… ▽ More With the development of incipient technologies, user devices becoming more exposed and ill-used by foes. In upcoming decades, traditional security measures will not be sufficient enough to handle this huge threat towards distributed hardware and software. Lack of standard network attack taxonomy has become an indispensable dispute on developing a clear understanding about the attacks in order to have an operative protection mechanism. Present attack categorization techniques protect a specific group of threat which has either messed the entire taxonomy structure or ambiguous when one network attacks get blended with few others attacks. Hence, this raises concerns about developing a common and general purpose taxonomy. In this study, a sequential question-answer based model of categorization is proposed. In this article, an intrusion detection framework and threat grouping schema are proposed on the basis of four sequential questions (Who, Where, How and What). We have used our method for classifying traditional network attacks in order to identify initiator, source, attack style and seriousness of an attack. Another focus of the paper is to provide a preventive list of actions for network administrator as a guideline to reduce overall attack consequence. Recommended taxonomy is designed to detect common attacks rather than any particular type of attack which can have a practical effect in real life attack classification. From the analysis of the classifications obtained from few infamous attacks, it is obvious that the proposed system holds certain benefits related to the prevailing taxonomies. Future research directions have also been well acknowledged. △ Less

Submitted 1 April, 2018; originally announced April 2018.

Journal ref: Annals of Emerging Technologies in Computing (AETiC), Print ISSN: 2516-0281, Online ISSN: 2516029X, Print ISSN: 2516-0281, Online ISSN: 2516029X, pp. 1-14, Vol. 2, No. 2, 1st April 2018. http://www.aetic.theiaer.org/archive/v2n2/p1.html

Parallel FPGA Router using Sub-Gradient method and Steiner tree

Authors: Rohit Agrawal, Chin Hao Hoo, Kapil Ahuja, Akash Kumar

Abstract: In the FPGA (Field Programmable Gate Arrays) design flow, one of the most time-consuming step is the routing of nets. Therefore, there is a need to accelerate it. In a recent paper by Hoo et. al., the authors have developed a Linear Programming based framework that parallelizes this routing process to achieve significant speedups (the algorithm is termed as ParaLaR). However, this approach has cer… ▽ More In the FPGA (Field Programmable Gate Arrays) design flow, one of the most time-consuming step is the routing of nets. Therefore, there is a need to accelerate it. In a recent paper by Hoo et. al., the authors have developed a Linear Programming based framework that parallelizes this routing process to achieve significant speedups (the algorithm is termed as ParaLaR). However, this approach has certain weaknesses. Namely, the constraints violation by the solution and a local minima that could be improved. We address these two issues here. In our paper, we use this framework and solve it using the Primal-Dual sub-gradient method that better exploits the problem properties. We also propose a better way to update the size of the step taken by this iterative algorithm. We perform experiments on a set of standard benchmarks, where we show that our algorithm outperforms the standard existing algorithms (VPR and ParaLaR). We achieve up to 22% improvement in the constraints violation and the standard metric of the minimum channel width when compared with ParaLaR (which is same as in VPR). We achieve about 20% savings in another standard metric of the total wire length (when compared with VPR), which is the same as for ParaLaR. Hence, our algorithm achieves minimum value for all the three parameters. Also, the critical path delay for our algorithm is almost same as compared to VPR and ParaLaR. We achieve relative speedups of 3 times when we run a parallel version of our algorithm using 4 threads. △ Less

Submitted 19 August, 2018; v1 submitted 10 March, 2018; originally announced March 2018.

Comments: 5 pages, double column, 1 figure, and 2 tables

On the Expressiveness and Monitoring of Metric Temporal Logic

Authors: Hsi-Ming Ho, Joël Ouaknine, James Worrell

Abstract: It is known that Metric Temporal Logic (MTL) is strictly less expressive than the Monadic First-Order Logic of Order and Metric (FO[<, +1]) when interpreted over timed words; this remains true even when the time domain is bounded a priori. In this work, we present an extension of MTL with the same expressive power as FO[<, +1] over bounded timed words (and also, trivially, over time-bounded signal… ▽ More It is known that Metric Temporal Logic (MTL) is strictly less expressive than the Monadic First-Order Logic of Order and Metric (FO[<, +1]) when interpreted over timed words; this remains true even when the time domain is bounded a priori. In this work, we present an extension of MTL with the same expressive power as FO[<, +1] over bounded timed words (and also, trivially, over time-bounded signals). We then show that expressive completeness also holds in the general (time-unbounded) case if we allow the use of rational constants $q \in \mathbb{Q}$ in formulas. This extended version of MTL therefore yields a definitive real-time analogue of Kamp's theorem. As an application, we propose a trace-length independent monitoring procedure for our extension of MTL, the first such procedure in a dense real-time setting. △ Less

Submitted 9 May, 2019; v1 submitted 7 March, 2018; originally announced March 2018.

Journal ref: Logical Methods in Computer Science, Volume 15, Issue 2 (May 10, 2019) lmcs:4366

Virtual-to-Real: Learning to Control in Visual Semantic Segmentation

Authors: Zhang-Wei Hong, Chen Yu-Ming, Shih-Yang Su, Tzu-Yun Shann, Yi-Hsiang Chang, Hsuan-Kung Yang, Brian Hsi-Lin Ho, Chih-Chieh Tu, Yueh-Chuan Chang, Tsu-Ching Hsiao, Hsin-Wei Hsiao, Sih-Pin Lai, Chun-Yi Lee

Abstract: Collecting training data from the physical world is usually time-consuming and even dangerous for fragile robots, and thus, recent advances in robot learning advocate the use of simulators as the training platform. Unfortunately, the reality gap between synthetic and real visual data prohibits direct migration of the models trained in virtual worlds to the real world. This paper proposes a modular… ▽ More Collecting training data from the physical world is usually time-consuming and even dangerous for fragile robots, and thus, recent advances in robot learning advocate the use of simulators as the training platform. Unfortunately, the reality gap between synthetic and real visual data prohibits direct migration of the models trained in virtual worlds to the real world. This paper proposes a modular architecture for tackling the virtual-to-real problem. The proposed architecture separates the learning model into a perception module and a control policy module, and uses semantic image segmentation as the meta representation for relating these two modules. The perception module translates the perceived RGB image to semantic image segmentation. The control policy module is implemented as a deep reinforcement learning agent, which performs actions based on the translated image segmentation. Our architecture is evaluated in an obstacle avoidance task and a target following task. Experimental results show that our architecture significantly outperforms all of the baseline methods in both virtual and real environments, and demonstrates a faster learning curve than them. We also present a detailed analysis for a variety of variant configurations, and validate the transferability of our modular architecture. △ Less

Submitted 28 October, 2018; v1 submitted 1 February, 2018; originally announced February 2018.

Comments: 7 pages, accepted by IJCAI-18

Summarizing First-Person Videos from Third Persons' Points of Views

Authors: Hsuan-I Ho, Wei-Chen Chiu, Yu-Chiang Frank Wang

Abstract: Video highlight or summarization is among interesting topics in computer vision, which benefits a variety of applications like viewing, searching, or storage. However, most existing studies rely on training data of third-person videos, which cannot easily generalize to highlight the first-person ones. With the goal of deriving an effective model to summarize first-person videos, we propose a novel… ▽ More Video highlight or summarization is among interesting topics in computer vision, which benefits a variety of applications like viewing, searching, or storage. However, most existing studies rely on training data of third-person videos, which cannot easily generalize to highlight the first-person ones. With the goal of deriving an effective model to summarize first-person videos, we propose a novel deep neural network architecture for describing and discriminating vital spatiotemporal information across videos with different points of view. Our proposed model is realized in a semi-supervised setting, in which fully annotated third-person videos, unlabeled first-person videos, and a small number of annotated first-person ones are presented during training. In our experiments, qualitative and quantitative evaluations on both benchmarks and our collected first-person video datasets are presented. △ Less

Submitted 26 July, 2018; v1 submitted 24 November, 2017; originally announced November 2017.

Comments: 16+10 pages, ECCV 2018

Adaptive Control Strategy for Constant Optical Flow Divergence Landing

Authors: H. W. Ho, G. C. H. E. de Croon, E. van Kampen, Q. P. Chu, M. Mulder

Abstract: Bio-inspired methods can provide efficient solutions to perform autonomous landing for Micro Air Vehicles (MAVs). Flying insects such as honeybees perform vertical landings by keeping flow divergence constant. This leads to an exponential decay of both height and vertical velocity, and allows for smooth and safe landings. However, the presence of noise and delay in obtaining flow divergence estima… ▽ More Bio-inspired methods can provide efficient solutions to perform autonomous landing for Micro Air Vehicles (MAVs). Flying insects such as honeybees perform vertical landings by keeping flow divergence constant. This leads to an exponential decay of both height and vertical velocity, and allows for smooth and safe landings. However, the presence of noise and delay in obtaining flow divergence estimates will cause instability of the landing when the control gains are not adapted to the height. In this paper, we propose a strategy that deals with this fundamental problem of optical flow control. The key to the strategy lies in the use of a recent theory that allows the MAV to see distance by means of its control instability. At the start of a landing, the MAV detects the height by means of an oscillating movement and sets the control gains accordingly. Then, during descent, the gains are reduced exponentially, with mechanisms in place to reduce or increase the gains if the actual trajectory deviates too much from an ideal constant divergence landing. Real-world experiments demonstrate stable landings of the MAV in both indoor and windy outdoor environments. △ Less

Submitted 21 September, 2016; originally announced September 2016.

Comments: This manuscript is submitted to the IEEE Transactions on Robotics

Real-Time Synthesis is Hard!

Authors: Thomas Brihaye, Morgane Estiévenart, Gilles Geeraerts, Hsi-Ming Ho, Benjamin Monmege, Nathalie Sznajder

Abstract: We study the reactive synthesis problem (RS) for specifications given in Metric Interval Temporal Logic (MITL). RS is known to be undecidable in a very general setting, but on infinite words only; and only the very restrictive BRRS subcase is known to be decidable (see D'Souza et al. and Bouyer et al.). In this paper, we precise the decidability border of MITL synthesis. We show RS is undecidable… ▽ More We study the reactive synthesis problem (RS) for specifications given in Metric Interval Temporal Logic (MITL). RS is known to be undecidable in a very general setting, but on infinite words only; and only the very restrictive BRRS subcase is known to be decidable (see D'Souza et al. and Bouyer et al.). In this paper, we precise the decidability border of MITL synthesis. We show RS is undecidable on finite words too, and present a landscape of restrictions (both on the logic and on the possible controllers) that are still undecidable. On the positive side, we revisit BRRS and introduce an efficient on-the-fly algorithm to solve it. △ Less

Submitted 22 June, 2016; originally announced June 2016.

Effective Static and Adaptive Carrier Sensing for Dense Wireless CSMA Networks

Authors: Chi-Kin Chau, Ivan W. H. Ho, Zhenhui Situ, Soung Chang Liew, Jialiang Zhang

Abstract: The increasingly dense deployments of wireless CSMA networks arising from applications of Internet-of-things call for an improvement to mitigate the interference among simultaneous transmitting wireless devices. For cost efficiency and backward compatibility with legacy transceiver hardware, a simple approach to address interference is by appropriately configuring the carrier sensing thresholds in… ▽ More The increasingly dense deployments of wireless CSMA networks arising from applications of Internet-of-things call for an improvement to mitigate the interference among simultaneous transmitting wireless devices. For cost efficiency and backward compatibility with legacy transceiver hardware, a simple approach to address interference is by appropriately configuring the carrier sensing thresholds in wireless CSMA protocols, particularly in dense wireless networks. Most prior studies of the configuration of carrier sensing thresholds are based on a simplified conflict graph model, whereas this paper considers a realistic signal-to-interference-and-noise ratio model. We provide a comprehensive study for two effective wireless CSMA protocols: Cumulative-interference-Power Carrier Sensing and Incremental-interference-Power Carrier Sensing, in two aspects: (1) static approach that sets a universal carrier sensing threshold to ensure interference-safe transmissions regardless of network topology, and (2) adaptive approach that adjusts the carrier sensing thresholds dynamically based on the feedback of nearby transmissions. We also provide simulation studies to evaluate the starvation ratio, fairness, and goodput of our approaches. △ Less

Submitted 11 October, 2016; v1 submitted 23 February, 2016; originally announced February 2016.

Comments: To appear in IEEE Transactions on Mobile Computing

Journal ref: IEEE Transactions on Mobile Computing, Vol. 16, No. 2, pp355-366 (Feb 2017)

Optical-Flow based Self-Supervised Learning of Obstacle Appearance applied to MAV Landing

Authors: H. W. Ho, C. De Wagter, B. D. W. Remes, G. C. H. E. de Croon

Abstract: Monocular optical flow has been widely used to detect obstacles in Micro Air Vehicles (MAVs) during visual navigation. However, this approach requires significant movement, which reduces the efficiency of navigation and may even introduce risks in narrow spaces. In this paper, we introduce a novel setup of self-supervised learning (SSL), in which optical flow cues serve as a scaffold to learn the… ▽ More Monocular optical flow has been widely used to detect obstacles in Micro Air Vehicles (MAVs) during visual navigation. However, this approach requires significant movement, which reduces the efficiency of navigation and may even introduce risks in narrow spaces. In this paper, we introduce a novel setup of self-supervised learning (SSL), in which optical flow cues serve as a scaffold to learn the visual appearance of obstacles in the environment. We apply it to a landing task, in which initially 'surface roughness' is estimated from the optical flow field in order to detect obstacles. Subsequently, a linear regression function is learned that maps appearance features represented by texton distributions to the roughness estimate. After learning, the MAV can detect obstacles by just analyzing a still image. This allows the MAV to search for a landing spot without moving. We first demonstrate this principle to work with offline tests involving images captured from an on-board camera, and then demonstrate the principle in flight. Although surface roughness is a property of the entire flow field in the global image, the appearance learning even allows for the pixel-wise segmentation of obstacles. △ Less

Submitted 17 August, 2017; v1 submitted 4 September, 2015; originally announced September 2015.

Comments: This manuscript is submitted to Robotics and Autonomous Systems

The Cyclic-Routing UAV Problem is PSPACE-Complete

Authors: Hsi-Ming Ho, Joel Ouaknine

Abstract: Consider a finite set of targets, with each target assigned a relative deadline, and each pair of targets assigned a fixed transit flight time. Given a flock of identical UAVs, can one ensure that every target is repeatedly visited by some UAV at intervals of duration at most the target's relative deadline? The Cyclic-Routing UAV Problem (CR-UAV) is the question of whether this task has a solution… ▽ More Consider a finite set of targets, with each target assigned a relative deadline, and each pair of targets assigned a fixed transit flight time. Given a flock of identical UAVs, can one ensure that every target is repeatedly visited by some UAV at intervals of duration at most the target's relative deadline? The Cyclic-Routing UAV Problem (CR-UAV) is the question of whether this task has a solution. This problem can straightforwardly be solved in PSPACE by modelling it as a network of timed automata. The special case of there being a single UAV is claimed to be NP-complete in the literature. In this paper, we show that the CR-UAV Problem is in fact PSPACE-complete even in the single-UAV case. △ Less

Submitted 22 January, 2015; v1 submitted 9 November, 2014; originally announced November 2014.

Comments: 19 pages. Full version of the FoSSaCS'15 paper with the same title

ContactTrees: A Technique for Studying Personal Network Data

Authors: Arnaud Sallaberry, Yang-Chih Fu, Hwai-Chung Ho, Kwan-Liu Ma

Abstract: Network visualization allows a quick glance at how nodes (or actors) are connected by edges (or ties). A conventional network diagram of "contact tree" maps out a root and branches that represent the structure of nodes and edges, often without further specifying leaves or fruits that would have grown from small branches. By furnishing such a network structure with leaves and fruits, we reveal deta… ▽ More Network visualization allows a quick glance at how nodes (or actors) are connected by edges (or ties). A conventional network diagram of "contact tree" maps out a root and branches that represent the structure of nodes and edges, often without further specifying leaves or fruits that would have grown from small branches. By furnishing such a network structure with leaves and fruits, we reveal details about "contacts" in our ContactTrees that underline ties and relationships. Our elegant design employs a bottom-up approach that resembles a recent attempt to understand subjective well-being by means of a series of emotions. Such a bottom-up approach to social-network studies decomposes each tie into a series of interactions or contacts, which help deepen our understanding of the complexity embedded in a network structure. Unlike previous network visualizations, ContactTrees can highlight how relationships form and change based upon interactions among actors, and how relationships and networks vary by contact attributes. Based on a botanical tree metaphor, the design is easy to construct and the resulting tree-like visualization can display many properties at both tie and contact levels, a key ingredient missing from conventional techniques of network visualization. We first demonstrate ContactTrees using a dataset consisting of three waves of 3-month contact diaries over the 2004-2012 period, then compare ContactTrees with alternative tools and discuss how this tool can be applied to other types of datasets. △ Less

Submitted 31 October, 2014; originally announced November 2014.