OpenRaiser/Intern-Atlas huggingface dataset:
ALAN: Adaptive Learning for Multi-Agent Navigation
Venue: arXiv cs.MA 2017
Year: 2017

In multi-agent navigation, agents need to move towards their goal locations while avoiding collisions with other agents and static obstacles, often without communication with each other. Existing methods compute motions that are optimal locally but do not account for the aggregated motions of all agents, producing inefficient global behavior especially when agents move in a crowded space. In this work, we develop methods to allow agents to dynamically adapt their behavior to their local conditions. We accomplish this by formulating the multi-agent navigation problem as an action-selection problem, and propose an approach, ALAN, that allows agents to compute time-efficient and collision-free motions. ALAN is highly scalable because each agent makes its own decisions on how to move using a set of velocities optimized for a variety of navigation tasks. Experimental results show that the agents using ALAN, in general, reach their destinations faster than using ORCA, a state-of-the-art collision avoidance framework, the Social Forces model for pedestrian navigation, and a Predictive collision avoidance model.
Generic Results for Concatenation Hierarchies
Venue: arXiv cs.FL 2017
Year: 2017

In the theory of formal languages, the understanding of concatenation hierarchies of regular languages is one of the most fundamental and challenging topic. In this paper, we survey progress made in the comprehension of this problem since 1971, and we establish new generic statements regarding this problem.
What Would a Graph Look Like in This Layout? A Machine Learning Approach to Large Graph Visualization
Venue: arXiv cs.SI 2017
Year: 2017

Using different methods for laying out a graph can lead to very different visual appearances, with which the viewer perceives different information. Selecting a "good" layout method is thus important for visualizing a graph. The selection can be highly subjective and dependent on the given task. A common approach to selecting a good layout is to use aesthetic criteria and visual inspection. However, fully calculating various layouts and their associated aesthetic metrics is computationally expensive. In this paper, we present a machine learning approach to large graph visualization based on computing the topological similarity of graphs using graph kernels. For a given graph, our approach can show what the graph would look like in different layouts and estimate their corresponding aesthetic metrics. An important contribution of our work is the development of a new framework to design graph kernels. Our experimental study shows that our estimation calculation is considerably faster than computing the actual layouts and their aesthetic metrics. Also, our graph kernels outperform the state-of-the-art ones in both time and accuracy. In addition, we conducted a user study to demonstrate that the topological similarity computed with our graph kernel matches perceptual similarity assessed by human users.
Designing Low-Complexity Heavy-Traffic Delay-Optimal Load Balancing Schemes: Theory to Algorithms
Venue: arXiv cs.DC 2017
Year: 2017

We establish a unified analytical framework for load balancing systems, which allows us to construct a general class $Π$ of policies that are both throughput optimal and heavy-traffic delay optimal. This general class $Π$ includes as special cases popular policies such as join-shortest-queue and power-of-$d$, but not the join-idle-queue (JIQ) policy. In fact, we show that JIQ, which is not in $Π$, is actually not heavy-traffic delay optimal. Owing to the significant flexibility offered by class $Π$, we are able to design a new policy called join-below-threshold (JBT-d), which maintains the simplicity of pull-based policies such as JIQ, but updates its threshold dynamically. We prove that JBT-$d$ belongs to the class $Π$ when the threshold is picked appropriately and thus it is heavy-traffic delay optimal. Extensive simulations show that the new policy not only has a low complexity in message rates, but also achieves excellent delay performance, comparable to the optimal join-shortest-queue in various system settings.
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty, Fomin et al. (SODA 2017) introduced the concept of fully polynomial FPT algorithms. For a problem with the current best time complexity $O(n^c)$, the goal is to design an algorithm running in $k^{O(1)}n^{c'}$ time for a parameter $k$ and a constant $c'<c$. In this paper, we investigate the complexity of graph problems in P parameterized by tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in $O(\mathrm{td}\cdot m)$ time or $O(\mathrm{td}\cdot (m+n\log n))$ time, where $\mathrm{td}$ is the tree-depth of the input graph. Because any graph of tree-width $\mathrm{tw}$ has tree-depth at most $(\mathrm{tw}+1)\log_2 n$, our algorithms also run in $O(\mathrm{tw}\cdot m\log n)$ time or $O(\mathrm{tw}\cdot (m+n\log n)\log n)$ time. These results match or improve the previous best algorithms parameterized by tree-width. Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by tree-width posed by Fomin et al.
Querying Best Paths in Graph Databases
Venue: arXiv cs.DB 2017
Year: 2017

Querying graph databases has recently received much attention. We propose a new approach to this problem, which balances competing goals of expressive power, language clarity and computational complexity. A distinctive feature of our approach is the ability to express properties of minimal (e.g. shortest) and maximal (e.g. most valuable) paths satisfying given criteria. To express complex properties in a modular way, we introduce labelling-generating ontologies. The resulting formalism is computationally attractive -- queries can be answered in non-deterministic logarithmic space in the size of the database.
Markerless visual servoing on unknown objects for humanoid robot platforms
Venue: arXiv cs.RO 2017
Year: 2017

To precisely reach for an object with a humanoid robot, it is of central importance to have good knowledge of both end-effector, object pose and shape. In this work we propose a framework for markerless visual servoing on unknown objects, which is divided in four main parts: I) a least-squares minimization problem is formulated to find the volume of the object graspable by the robot's hand using its stereo vision; II) a recursive Bayesian filtering technique, based on Sequential Monte Carlo (SMC) filtering, estimates the 6D pose (position and orientation) of the robot's end-effector without the use of markers; III) a nonlinear constrained optimization problem is formulated to compute the desired graspable pose about the object; IV) an image-based visual servo control commands the robot's end-effector toward the desired pose. We demonstrate effectiveness and robustness of our approach with extensive experiments on the iCub humanoid robot platform, achieving real-time computation, smooth trajectories and sub-pixel precisions.
Pure Operation-Based Replicated Data Types
Venue: arXiv cs.DC 2017
Year: 2017

Distributed systems designed to serve clients across the world often make use of geo-replication to attain low latency and high availability. Conflict-free Replicated Data Types (CRDTs) allow the design of predictable multi-master replication and support eventual consistency of replicas that are allowed to transiently diverge. CRDTs come in two flavors: state-based, where a state is changed locally and shipped and merged into other replicas; operation-based, where operations are issued locally and reliably causal broadcast to all other replicas. However, the standard definition of op-based CRDTs is very encompassing, allowing even sending the full-state, and thus imposing storage and dissemination overheads as well as blurring the distinction from state-based CRDTs. We introduce pure op-based CRDTs, that can only send operations to other replicas, drawing a clear distinction from state-based ones. Data types with commutative operations can be trivially implemented as pure op-based CRDTs using standard reliable causal delivery; whereas data types having non-commutative operations are implemented using a PO-Log, a partially ordered log of operations, and making use of an extended API, i.e., a Tagged Causal Stable Broadcast (TCSB), that provides extra causality information upon delivery and later informs when delivered messages become causally stable, allowing further PO-Log compaction. The framework is illustrated by a catalog of pure op-based specifications for classic CRDTs, including counters, multi-value registers, add-wins and remove-wins sets.
Multimodal Observation and Interpretation of Subjects Engaged in Problem Solving
Venue: arXiv cs.HC 2017
Year: 2017

In this paper we present the first results of a pilot experiment in the capture and interpretation of multimodal signals of human experts engaged in solving challenging chess problems. Our goal is to investigate the extent to which observations of eye-gaze, posture, emotion and other physiological signals can be used to model the cognitive state of subjects, and to explore the integration of multiple sensor modalities to improve the reliability of detection of human displays of awareness and emotion. We observed chess players engaged in problems of increasing difficulty while recording their behavior. Such recordings can be used to estimate a participant's awareness of the current situation and to predict ability to respond effectively to challenging situations. Results show that a multimodal approach is more accurate than a unimodal one. By combining body posture, visual attention and emotion, the multimodal approach can reach up to 93% of accuracy when determining player's chess expertise while unimodal approach reaches 86%. Finally this experiment validates the use of our equipment as a general and reproducible tool for the study of participants engaged in screen-based interaction and/or problem solving.
Average Stack Cost of Buechi Pushdown Automata
Venue: arXiv cs.FL 2017
Year: 2017

We study the average stack cost of Buechi pushdown automata (Buechi PDA). We associate a non-negative price with each stack symbol and define the cost of a stack as the sum of costs of all its elements. We introduce and study the average stack cost problem (ASC), which asks whether there exists an accepting run of a given Buechi PDA such that the long-run average of stack costs is below some given threshold. The ASC problem generalizes mean-payoff objective and can be used to express quantitative properties of pushdown systems. In particular, we can compute the average response time using the ASC problem. We show that the ASC problem can be solved in polynomial time.
Mobile IMUs Reveal Driver's Identity From Vehicle Turns
Venue: arXiv cs.CR 2017
Year: 2017

As vehicle maneuver data becomes abundant for assisted or autonomous driving, their implication of privacy invasion/leakage has become an increasing concern. In particular, the surface for fingerprinting a driver will expand significantly if the driver's identity can be linked with the data collected from his mobile or wearable devices which are widely deployed worldwide and have increasing sensing capabilities. In line with this trend, this paper investigates a fast emerging driving data source that has driver's privacy implications. We first show that such privacy threats can be materialized via any mobile device with IMUs (e.g., gyroscope and accelerometer). We then present Dri-Fi (Driver Fingerprint), a driving data analytic engine that can fingerprint the driver with vehicle turn(s). Dri-Fi achieves this based on IMUs data taken only during the vehicle's turn(s). Such an approach expands the attack surface significantly compared to existing driver fingerprinting schemes. From this data, Dri-Fi extracts three new features --- acceleration along the end-of-turn axis, its deviation, and the deviation of the yaw rate --- and exploits them to identify the driver. Our extensive evaluation shows that an adversary equipped with Dri-Fi can correctly fingerprint the driver within just one turn with 74.1%, 83.5%, and 90.8% accuracy across 12, 8, and 5 drivers --- typical of an immediate family or close-friends circle --- respectively. Moreover, with measurements on more than one turn, the adversary can achieve up to 95.3%, 95.4%, and 96.6% accuracy across 12, 8, and 5 drivers, respectively.
Supporting Requirements Engineering Research that Industry Needs: The Naming the Pain in Requirements Engineering Initiative
Venue: arXiv cs.SE 2017
Year: 2017

In light of the 40th jubilee of Requirements Engineering (RE), roughly 40 experts met in Switzerland to discuss where our discipline stands today. As of today, the common view is, indisputably, that RE as a discipline is stable and respected, as pointed out by Sarah Gregory when covering the seminar in her column to which articles like this one are invited to present ongoing research. However, it is also evident that after 40 years of promising research, conducting research that industry needs is still an ongoing challenge. Research that industry needs means research that solves industrial problems practitioners face; but do we really understand those problems? Here, I want to recapitulate on this research challenge and outline an initiative, the Naming the Pain in Requirements Engineering Initiative, that aims at tackling this problem.
How to Ask for Technical Help? Evidence-based Guidelines for Writing Questions on Stack Overflow
Venue: arXiv cs.CY 2017
Year: 2017

Context: The success of Stack Overflow and other community-based question-and-answer (Q&A) sites depends mainly on the will of their members to answer others' questions. In fact, when formulating requests on Q&A sites, we are not simply seeking for information. Instead, we are also asking for other people's help and feedback. Understanding the dynamics of the participation in Q&A communities is essential to improve the value of crowdsourced knowledge. Objective: In this paper, we investigate how information seekers can increase the chance of eliciting a successful answer to their questions on Stack Overflow by focusing on the following actionable factors: affect, presentation quality, and time. Method: We develop a conceptual framework of factors potentially influencing the success of questions in Stack Overflow. We quantitatively analyze a set of over 87K questions from the official Stack Overflow dump to assess the impact of actionable factors on the success of technical requests. The information seeker reputation is included as a control factor. Furthermore, to understand the role played by affective states in the success of questions, we qualitatively analyze questions containing positive and negative emotions. Finally, a survey is conducted to understand how Stack Overflow users perceive the guideline suggestions for writing questions. Results: We found that regardless of user reputation, successful questions are short, contain code snippets, and do not abuse with uppercase characters. As regards affect, successful questions adopt a neutral emotional style. Conclusion: We provide evidence-based guidelines for writing effective questions on Stack Overflow that software engineers can follow to increase the chance of getting technical help. As for the role of affect, we empirically confirmed community guidelines that suggest avoiding rudeness in question writing.
Identifying On-time Reward Delivery Projects with Estimating Delivery Duration on Kickstarter
Venue: arXiv cs.CY 2017
Year: 2017

In Crowdfunding platforms, people turn their prototype ideas into real products by raising money from the crowd, or invest in someone else's projects. In reward-based crowdfunding platforms such as Kickstarter and Indiegogo, selecting accurate reward delivery duration becomes crucial for creators, backers, and platform providers to keep the trust between the creators and the backers, and the trust between the platform providers and users. According to Kickstarter, 35% backers did not receive rewards on time. Unfortunately, little is known about on-time and late reward delivery projects, and there is no prior work to estimate reward delivery duration. To fill the gap, in this paper, we (i) extract novel features that reveal latent difficulty levels of project rewards; (ii) build predictive models to identify whether a creator will deliver all rewards in a project on time or not; and (iii) build a regression model to estimate accurate reward delivery duration (i.e., how long it will take to produce and deliver all the rewards). Experimental results show that our models achieve good performance -- 82.5% accuracy, 78.1 RMSE, and 0.108 NRMSE at the first 5% of the longest reward delivery duration.
Can the early human visual system compete with Deep Neural Networks?
Venue: arXiv cs.CV 2017
Year: 2017

We study and compare the human visual system and state-of-the-art deep neural networks on classification of distorted images. Different from previous works, we limit the display time to 100ms to test only the early mechanisms of the human visual system, without allowing time for any eye movements or other higher level processes. Our findings show that the human visual system still outperforms modern deep neural networks under blurry and noisy images. These findings motivate future research into developing more robust deep networks.
Movement-efficient Sensor Deployment in Wireless Sensor Networks
Venue: arXiv cs.IT 2017
Year: 2017

We study a mobile wireless sensor network (MWSN) consisting of multiple mobile sensors or robots. Two key issues in MWSNs - energy consumption, which is dominated by sensor movement, and sensing coverage - have attracted plenty of attention, but the interaction of these issues is not well studied. To take both sensing coverage and movement energy consumption into consideration, we model the sensor deployment problem as a constrained source coding problem. %, which can be applied to different coverage tasks, such as area coverage, target coverage, and barrier coverage. Our goal is to find an optimal sensor deployment to maximize the sensing coverage with specific energy constraints. We derive necessary conditions to the optimal sensor deployment with (i) total energy constraint and (ii) network lifetime constraint. Using these necessary conditions, we design Lloyd-like algorithms to provide a trade-off between sensing coverage and energy consumption. Simulation results show that our algorithms outperform the existing relocation algorithms.
Sparse Weighted Canonical Correlation Analysis
Venue: arXiv cs.LG 2017
Year: 2017

Given two data matrices $X$ and $Y$, sparse canonical correlation analysis (SCCA) is to seek two sparse canonical vectors $u$ and $v$ to maximize the correlation between $Xu$ and $Yv$. However, classical and sparse CCA models consider the contribution of all the samples of data matrices and thus cannot identify an underlying specific subset of samples. To this end, we propose a novel sparse weighted canonical correlation analysis (SWCCA), where weights are used for regularizing different samples. We solve the $L_0$-regularized SWCCA ($L_0$-SWCCA) using an alternating iterative algorithm. We apply $L_0$-SWCCA to synthetic data and real-world data to demonstrate its effectiveness and superiority compared to related methods. Lastly, we consider also SWCCA with different penalties like LASSO (Least absolute shrinkage and selection operator) and Group LASSO, and extend it for integrating more than three data matrices.
VGR-Net: A View Invariant Gait Recognition Network
Venue: arXiv cs.CV 2017
Year: 2017

Biometric identification systems have become immensely popular and important because of their high reliability and efficiency. However person identification at a distance, still remains a challenging problem. Gait can be seen as an essential biometric feature for human recognition and identification. It can be easily acquired from a distance and does not require any user cooperation thus making it suitable for surveillance. But the task of recognizing an individual using gait can be adversely affected by varying view points making this task more and more challenging. Our proposed approach tackles this problem by identifying spatio-temporal features and performing extensive experimentation and training mechanism. In this paper, we propose a 3-D Convolution Deep Neural Network for person identification using gait under multiple view. It is a 2-stage network, in which we have a classification network that initially identifies the viewing point angle. After that another set of networks (one for each angle) has been trained to identify the person under a particular viewing angle. We have tested this network over CASIA-B publicly available database and have achieved state-of-the-art results. The proposed system is much more efficient in terms of time and space and performing better for almost all angles.
Fast Top-k Area Topics Extraction with Knowledge Base
Venue: arXiv cs.AI 2017
Year: 2017

What are the most popular research topics in Artificial Intelligence (AI)? We formulate the problem as extracting top-$k$ topics that can best represent a given area with the help of knowledge base. We theoretically prove that the problem is NP-hard and propose an optimization model, FastKATE, to address this problem by combining both explicit and latent representations for each topic. We leverage a large-scale knowledge base (Wikipedia) to generate topic embeddings using neural networks and use this kind of representations to help capture the representativeness of topics for given areas. We develop a fast heuristic algorithm to efficiently solve the problem with a provable error bound. We evaluate the proposed model on three real-world datasets. Experimental results demonstrate our model's effectiveness, robustness, real-timeness (return results in $<1$s), and its superiority over several alternative methods.
Anti-jamming Communications Using Spectrum Waterfall: A Deep Reinforcement Learning Approach
Venue: arXiv cs.IT 2017
Year: 2017

This letter investigates the problem of anti-jamming communications in dynamic and unknown environment through on-line learning. Different from existing studies which need to know (estimate) the jamming patterns and parameters, we use the spectrum waterfall, i.e., the raw spectrum environment, directly. Firstly, to cope with the challenge of infinite state of raw spectrum information, a deep anti-jamming Q-network is constructed. Then, a deep anti-jamming reinforcement learning algorithm is proposed to obtain the optimal anti-jamming strategies. Finally, simulation results validate the the proposed approach. The proposed approach is relying only on the local observed information and does not need to estimate the jamming patterns and parameters, which implies that it can be widely used various anti-jamming scenarios.