OpenRaiser/Intern-Atlas huggingface dataset:
Vehicle management in a modular production context using Deep Q-Learning
Venue: arXiv cs.LG 2022
Year: 2022

We investigate the feasibility of deploying Deep-Q based deep reinforcement learning agents to job-shop scheduling problems in the context of modular production facilities, using discrete event simulations for the environment. These environments are comprised of a source and sink for the parts to be processed, as well as (several) workstations. The agents are trained to schedule automated guided vehicles to transport the parts back and forth between those stations in an optimal fashion. Starting from a very simplistic setup, we increase the complexity of the environment and compare the agents' performances with well established heuristic approaches, such as first-in-first-out based agents, cost tables and a nearest-neighbor approach. We furthermore seek particular configurations of the environments in which the heuristic approaches struggle, to investigate to what degree the Deep-Q agents are affected by these challenges. We find that Deep-Q based agents show comparable performance as the heuristic baselines. Furthermore, our findings suggest that the DRL agents exhibit an increased robustness to noise, as compared to the conventional approaches. Overall, we find that DRL agents constitute a valuable approach for this type of scheduling problems.
One-sorted Program Algebras
Venue: arXiv cs.LO 2022
Year: 2022

Kleene algebra with tests, KAT, provides a simple two-sorted algebraic framework for verifying properties of propositional while programs. Kleene algebra with domain, KAD, is a one-sorted alternative to KAT. The equational theory of KAT embeds into KAD, but KAD lacks some natural properties of KAT. For instance, not each Kleene algebra expands to a KAD, and the subalgebra of tests in each KAD is forced to be the maximal Boolean subalgebra of the negative cone. In this paper we propose a generalization of KAD that avoids these features while still embedding the equational theory of KAT. We show that several natural properties of the domain operator of KAD can be added to the generalized framework without affecting the results. We consider a variant of the framework where test complementation is defined using a residual of the Kleene algebra multiplication.
OMU: A Probabilistic 3D Occupancy Mapping Accelerator for Real-time OctoMap at the Edge
Venue: arXiv cs.AR 2022
Year: 2022

Autonomous machines (e.g., vehicles, mobile robots, drones) require sophisticated 3D mapping to perceive the dynamic environment. However, maintaining a real-time 3D map is expensive both in terms of compute and memory requirements, especially for resource-constrained edge machines. Probabilistic OctoMap is a reliable and memory-efficient 3D dense map model to represent the full environment, with dynamic voxel node pruning and expansion capacity. This paper presents the first efficient accelerator solution, i.e. OMU, to enable real-time probabilistic 3D mapping at the edge. To improve the performance, the input map voxels are updated via parallel PE units for data parallelism. Within each PE, the voxels are stored using a specially developed data structure in parallel memory banks. In addition, a pruning address manager is designed within each PE unit to reuse the pruned memory addresses. The proposed 3D mapping accelerator is implemented and evaluated using a commercial 12 nm technology. Compared to the ARM Cortex-A57 CPU in the Nvidia Jetson TX2 platform, the proposed accelerator achieves up to 62$\times$ performance and 708$\times$ energy efficiency improvement. Furthermore, the accelerator provides 63 FPS throughput, more than 2$\times$ higher than a real-time requirement, enabling real-time perception for 3D mapping.
The Supervisionary proof-checking kernel (or: a work-in-progress towards proof generating code)
Venue: arXiv cs.CR 2022
Year: 2022

Interactive theorem proving software is typically designed around a trusted proof-checking kernel, the sole system component capable of authenticating theorems. Untrusted automation procedures reside outside of the kernel, and drive it to deduce new theorems via an API. Kernel and untrusted automation are typically implemented in the same programming language -- the "meta-language" -- usually some functional programming language in the ML family. This strategy -- introduced by Milner in his LCF proof assistant -- is a reliability mechanism, aiming to ensure that any purported theorem produced by the system is indeed entailed by the theory within the logic. Changing tack, operating systems are also typically designed around a trusted kernel, a privileged component responsible for -- amongst other things -- mediating interaction betwixt user-space software and hardware. Untrusted processes interact with the system by issuing kernel system calls across a hardware privilege boundary. In this way, the operating system kernel supervises user-space processes. Though ostensibly very different, squinting, we see that the two kinds of kernel are tasked with solving the same task: enforcing system invariants in the face of unbounded interaction with untrusted code. Yet, the two solutions to solving this problem, employed by the respective kinds of kernel, are very different. In this abstract, we explore designing proof-checking kernels as supervisory software, where separation between kernel and untrusted code is enforced by privilege, not programming language module boundaries and type abstraction. We describe work on the Supervisionary proof-checking kernel, and briefly sketch its unique system interface. We then describe some potential uses of the Supervisionary kernel.
UAV-aided RF Mapping for Sensing and Connectivity in Wireless Networks
Venue: arXiv cs.IT 2022
Year: 2022

The use of unmanned aerial vehicles (UAV) as flying radio access network (RAN) nodes offers a promising complement to traditional fixed terrestrial deployments. More recently yet still in the context of wireless networks, drones have also been envisioned for use as radio frequency (RF) sensing and localization devices. In both cases, the advantage of using UAVs lies in their ability to navigate themselves freely in 3D and in a timely manner to locations of space where the obtained network throughput or sensing performance is optimal. In practice, the selection of a proper location or trajectory for the UAV very much depends on local terrain features, including the position of surrounding radio obstacles. Hence, the robot must be able to map the features of its radio environment as it performs its data communication or sensing services. The challenges related to this task, referred here as radio mapping, are discussed in this paper. Its promises related to efficient trajectory design for autonomous radio-aware UAVs are highlighted, along with algorithm solutions. The advantages induced by radio-mapping in terms of connectivity, sensing, and localization performance are illustrated.
Statistical Data Privacy: A Song of Privacy and Utility
Venue: arXiv cs.CR 2022
Year: 2022

To quantify trade-offs between increasing demand for open data sharing and concerns about sensitive information disclosure, statistical data privacy (SDP) methodology analyzes data release mechanisms which sanitize outputs based on confidential data. Two dominant frameworks exist: statistical disclosure control (SDC), and more recent, differential privacy (DP). Despite framing differences, both SDC and DP share the same statistical problems at its core. For inference problems, we may either design optimal release mechanisms and associated estimators that satisfy bounds on disclosure risk, or we may adjust existing sanitized output to create new optimal estimators. Both problems rely on uncertainty quantification in evaluating risk and utility. In this review, we discuss the statistical foundations common to both SDC and DP, highlight major developments in SDP, and present exciting open research problems in private inference.
Shortcomings of Class-level Documentation: A Survey
Venue: arXiv cs.SE 2022
Year: 2022

To better understand the shortcomings of class-level documentation, we conducted a survey of 167 experienced software developers. The survey focused on the participants' programming-related information needs and how often class-level documentation satisfies such needs.
Overview of solution methods for elliptic partial differential equations on cartesian and hierarchical grids
Venue: arXiv cs.CE 2022
Year: 2022

Elliptic partial differential equations (PDEs) arise in many areas of computational sciences such as computational fluid dynamics, biophysics, engineering, geophysics and more. They are difficult to solve due to their global nature and sometimes ill-conditioned operators. We review common discretization methods for elliptic PDEs such as the finite difference, finite volume, finite element, and spectral methods and the linear systems they form. We also provide an overview of classic to modern solution methods for the linear systems formed by these discretization methods. These methods include splitting and Krylov methods, direct methods, and hierarchical methods. Finally, we show applications that would benefit from fast and efficient solvers for elliptic PDEs, including projection methods for the incompressible Navier-Stokes equations and the shallow water wave equations with dispersive corrections.
Journaling Data for Daily PHQ-2 Depression Prediction and Forecasting
Venue: arXiv cs.LG 2022
Year: 2022

Digital health applications are becoming increasingly important for assessing and monitoring the wellbeing of people suffering from mental health conditions like depression. A common target of said applications is to predict the results of self-assessed Patient-Health-Questionnaires (PHQ), indicating current symptom severity of depressive individuals. In this work, we explore the potential of using actively-collected data to predict and forecast daily PHQ-2 scores on a newly-collected longitudinal dataset. We obtain a best MAE of 1.417 for daily prediction of PHQ-2 scores, which specifically in the used dataset have a range of 0 to 12, using leave-one-subject-out cross-validation, as well as a best MAE of 1.914 for forecasting PHQ-2 scores using data from up to the last 7 days. This illustrates the additive value that can be obtained by incorporating actively-collected data in a depression monitoring application.
LatentKeypointGAN: Controlling Images via Latent Keypoints -- Extended Abstract
Venue: arXiv cs.CV 2022
Year: 2022

Generative adversarial networks (GANs) can now generate photo-realistic images. However, how to best control the image content remains an open challenge. We introduce LatentKeypointGAN, a two-stage GAN internally conditioned on a set of keypoints and associated appearance embeddings providing control of the position and style of the generated objects and their respective parts. A major difficulty that we address is disentangling the image into spatial and appearance factors with little domain knowledge and supervision signals. We demonstrate in a user study and quantitative experiments that LatentKeypointGAN provides an interpretable latent space that can be used to re-arrange the generated images by re-positioning and exchanging keypoint embeddings, such as generating portraits by combining the eyes, and mouth from different images. Notably, our method does not require labels as it is self-supervised and thereby applies to diverse application domains, such as editing portraits, indoor rooms, and full-body human poses.
AdaptiveON: Adaptive Outdoor Local Navigation Method For Stable and Reliable Actions
Venue: arXiv cs.RO 2022
Year: 2022

We present a novel outdoor navigation algorithm to generate stable and efficient actions to navigate a robot to reach a goal. We use a multi-stage training pipeline and show that our approach produces policies that result in stable and reliable robot navigation on complex terrains. Based on the Proximal Policy Optimization (PPO) algorithm, we developed a novel method to achieve multiple capabilities for outdoor navigation tasks, namely alleviating the robot's drifting, keeping the robot stable on bumpy terrains, avoiding climbing on hills with steep elevation changes, and avoiding collisions. Our training process mitigates the reality (sim-to-real) gap by introducing generalized environmental and robotic parameters and training with rich features of Lidar perception in a high-fidelity Unity simulator. We evaluate our method in both simulation and real world environments using Clearpath Husky and Jackal robots. Further, we compare our method against the state-of-the-art approaches and observe that, in the real world it improves stability by at least 30.7% on uneven terrains, reduces drifting by 8.08% and decreases the elevation changes by 14.75%.
Attract me to Buy: Advertisement Copywriting Generation with Multimodal Multi-structured Information
Venue: arXiv cs.CL 2022
Year: 2022

Recently, online shopping has gradually become a common way of shopping for people all over the world. Wonderful merchandise advertisements often attract more people to buy. These advertisements properly integrate multimodal multi-structured information of commodities, such as visual spatial information and fine-grained structure information. However, traditional multimodal text generation focuses on the conventional description of what existed and happened, which does not match the requirement of advertisement copywriting in the real world. Because advertisement copywriting has a vivid language style and higher requirements of faithfulness. Unfortunately, there is a lack of reusable evaluation frameworks and a scarcity of datasets. Therefore, we present a dataset, E-MMAD (e-commercial multimodal multi-structured advertisement copywriting), which requires, and supports much more detailed information in text generation. Noticeably, it is one of the largest video captioning datasets in this field. Accordingly, we propose a baseline method and faithfulness evaluation metric on the strength of structured information reasoning to solve the demand in reality on this dataset. It surpasses the previous methods by a large margin on all metrics. The dataset and method are coming soon on \url{https://e-mmad.github.io/e-mmad.net/index.html}.
CogIntAc: Modeling the Relationships between Intention, Emotion and Action in Interactive Process from Cognitive Perspective
Venue: arXiv cs.HC 2022
Year: 2022

Intention, emotion and action are important psychological factors in human activities, which play an important role in the interaction between individuals. How to model the interaction process between individuals by analyzing the relationship of their intentions, emotions, and actions at the cognitive level is challenging. In this paper, we propose a novel cognitive framework of individual interaction. The core of the framework is that individuals achieve interaction through external action driven by their inner intention. Based on this idea, the interactions between individuals can be constructed by establishing relationships between the intention, emotion and action. Furthermore, we conduct analysis on the interaction between individuals and give a reasonable explanation for the predicting results. To verify the effectiveness of the framework, we reconstruct a dataset and propose three tasks as well as the corresponding baseline models, including action abduction, emotion prediction and action generation. The novel framework shows an interesting perspective on mimicking the mental state of human beings in cognitive science.
Reliability of Robotic Ultrasound Scanning for Scoliosis Assessment in Comparison with Manual Scanning
Venue: arXiv cs.RO 2022
Year: 2022

Background: Ultrasound (US) imaging for scoliosis assessment is challenging for a non-experienced operator. The robotic scanning was developed to follow a spinal curvature with deep learning and apply consistent forces to the patient' back. Methods: 23 scoliosis patients were scanned with US devices both, robotically and manually. Two human raters measured each subject's spinous process angles (SPA) on robotic and manual coronal images. Results: The robotic method showed high intra- (ICC > 0.85) and inter-rater (ICC > 0.77) reliabilities. Compared with the manual method, the robotic approach showed no significant difference (p < 0.05) when measuring coronal deformity angles. The MAD for intra-rater analysis lies within an acceptable range from 0 deg to 5 deg for a minimum of 86% and a maximum 97% of a total number of the measured angles. Conclusions: This study demonstrated that scoliosis deformity angles measured on ultrasound images obtained with robotic scanning are comparable to those obtained by manual scanning.
Towards Computationally Feasible Deep Active Learning
Venue: arXiv cs.CL 2022
Year: 2022

Active learning (AL) is a prominent technique for reducing the annotation effort required for training machine learning models. Deep learning offers a solution for several essential obstacles to deploying AL in practice but introduces many others. One of such problems is the excessive computational resources required to train an acquisition model and estimate its uncertainty on instances in the unlabeled pool. We propose two techniques that tackle this issue for text classification and tagging tasks, offering a substantial reduction of AL iteration duration and the computational overhead introduced by deep acquisition models in AL. We also demonstrate that our algorithm that leverages pseudo-labeling and distilled models overcomes one of the essential obstacles revealed previously in the literature. Namely, it was shown that due to differences between an acquisition model used to select instances during AL and a successor model trained on the labeled data, the benefits of AL can diminish. We show that our algorithm, despite using a smaller and faster acquisition model, is capable of training a more expressive successor model with higher performance.
Dispersing Facilities on Planar Segment and Circle Amidst Repulsion
Venue: arXiv cs.CG 2022
Year: 2022

In this paper we consider the problem of locating $k$ obnoxious facilities (congruent disks of maximum radius) amidst $n$ demand points (existing repulsive facility sites) ordered from left to right in the plane so that none of the existing facility sites are affected (no demand point falls in the interior of the disks). We study this problem in two restricted settings: (i) the obnoxious facilities are constrained to be centered on along a predetermined horizontal line segment $\bar{pq}$, and (ii) the obnoxious facilities are constrained to lie on the boundary arc of a predetermined disk $\cal C$. An $(1-ε)$-approximation algorithm was given recently to solve the constrained problem in (i) in time $O((n+k)\log{\frac{||pq||}{2(k-1)ε}})$, where $ε>0$ \cite{Sing2021}. Here, for the problem in (i), we first propose an exact polynomial-time algorithm based on a binary search on all candidate radii computed explicitly. This algorithm runs in $O((nk)^2\log{(nk)}+(n+k)\log{(nk)})$ time. We then show that using the parametric search technique of Megiddo \cite{MG1983}; we can solve the problem exactly in $O((n+k)^2)$ time, which is faster than the latter. Continuing further, using the improved parametric technique we give an $O(n\log^2 n)$-time algorithm for $k=2$. We finally show that the above $(1-ε)$-approximation algorithm of \cite{Sing2021} can be easily adapted to solve the circular constrained problem of (ii) with an extra multiplicative factor of $n$ in the running time.
Playing Tic-Tac-Toe Games with Intelligent Single-pixel Imaging
Venue: arXiv cs.CV 2022
Year: 2022

Single-pixel imaging (SPI) is a novel optical imaging technique by replacing a two-dimensional pixelated sensor with a single-pixel detector and pattern illuminations. SPI have been extensively used for various tasks related to image acquisition and processing. In this work, a novel non-image-based task of playing Tic-Tac-Toe games interactively is merged into the framework of SPI. An optoelectronic artificial intelligent (AI) player with minimal digital computation can detect the game states, generate optimal moves and display output results mainly by pattern illumination and single-pixel detection. Simulated and experimental results demonstrate the feasibility of proposed scheme and its unbeatable performance against human players.
Better Retrieval May Not Lead to Better Question Answering
Venue: arXiv cs.CL 2022
Year: 2022

Considerable progress has been made recently in open-domain question answering (QA) problems, which require Information Retrieval (IR) and Reading Comprehension (RC). A popular approach to improve the system's performance is to improve the quality of the retrieved context from the IR stage. In this work we show that for StrategyQA, a challenging open-domain QA dataset that requires multi-hop reasoning, this common approach is surprisingly ineffective -- improving the quality of the retrieved context hardly improves the system's performance. We further analyze the system's behavior to identify potential reasons.
Accuracy Convergent Field Predictors
Venue: arXiv cs.LG 2022
Year: 2022

Several predictive algorithms are described. Highlighted are variants that make predictions by superposing fields associated to the training data instances. They operate seamlessly with categorical, continuous, and mixed data. Predictive accuracy convergence is also discussed as a criteria for evaluating predictive algorithms. Methods are described on how to adapt algorithms in order to make them achieve predictive accuracy convergence.
Exact recovery algorithm for Planted Bipartite Graph in Semi-random Graphs
Venue: arXiv cs.DS 2022
Year: 2022

The problem of finding the largest induced balanced bipartite subgraph in a given graph is NP-hard. This problem is closely related to the problem of finding the smallest Odd Cycle Transversal. In this work, we consider the following model of instances: starting with a set of vertices $V$, a set $S \subseteq V$ of $k$ vertices is chosen and an arbitrary $d$-regular bipartite graph is added on it; edges between pairs of vertices in $S \times (V \setminus S)$ and $(V \setminus S) \times (V \setminus S)$ are added with probability $p$. Since for $d=0$, the problem reduces to recovering a planted independent set, we don't expect efficient algorithms for $k=o(\sqrt{n})$. This problem is a generalization of the planted balanced biclique problem where the bipartite graph induced on $S$ is a complete bipartite graph; [Lev18] gave an algorithm for recovering $S$ in this problem when $k=Ω(\sqrt{n})$. Our main result is an efficient algorithm that recovers (w.h.p.) the planted bipartite graph when $k=Ω_p(\sqrt{n \log n})$ for a large range of parameters. Our results also hold for a natural semi-random model of instances, which involve the presence of a monotone adversary. Our proof shows that a natural SDP relaxation for the problem is integral by constructing an appropriate solution to it's dual formulation. Our main technical contribution is a new approach for constructing the dual solution where we calibrate the eigenvectors of the adjacency matrix to be the eigenvectors of the dual matrix. We believe that this approach may have applications to other recovery problems in semi-random models as well. When $k=Ω(\sqrt{n})$, we give an algorithm for recovering $S$ whose running time is exponential in the number of small eigenvalues in graph induced on $S$; this algorithm is based on subspace enumeration techniques due to the works of [KT07,ABS10,Kol11].