OpenRaiser/Intern-Atlas huggingface dataset:
Identification of Successive "Unobservable" Cyber Data Attacks in Power Systems Through Matrix Decomposition
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents a new framework of identifying a series of cyber data attacks on power system synchrophasor measurements. We focus on detecting "unobservable" cyber data attacks that cannot be detected by any existing method that purely relies on measurements received at one time instant. Leveraging the approximate low-rank property of phasor measurement unit (PMU) data, we formulate the identification problem of successive unobservable cyber attacks as a matrix decomposition problem of a low-rank matrix plus a transformed column-sparse matrix. We propose a convex-optimization-based method and provide its theoretical guarantee in the data identification. Numerical experiments on actual PMU data from the Central New York power system and synthetic data are conducted to verify the effectiveness of the proposed method.
Fast and Bounded Probabilistic Collision Detection in Dynamic Environments for High-DOF Trajectory Planning
Venue: arXiv cs.RO 2016
Year: 2016

We present a novel approach to perform probabilistic collision detection between a high-DOF robot and high-DOF obstacles in dynamic, uncertain environments. In dynamic environments with a high-DOF robot and moving obstacles, our approach efficiently computes accurate collision probability between the robot and obstacles with upper error bounds. Furthermore, we describe a prediction algorithm for future obstacle position and motion that accounts for both spatial and temporal uncertainties. We present a trajectory optimization algorithm for high-DOF robots in dynamic, uncertain environments based on probabilistic collision detection. We highlight motion planning performance in challenging scenarios with robot arms operating in environments with dynamically moving human obstacles.
Phase Noise Influence in Coherent Optical OFDM Systems with RF Pilot Tone: Digital IFFT Multiplexing and FFT Demodulation
Venue: arXiv cs.IT 2016
Year: 2016

We present a comparative study of the influence of dispersion induced phase noise for CO-OFDM systems using Tx channel multiplexing and Rx matched filter (analogue hardware based); and FFT multiplexing/IFFT demultiplexing techniques (software based). An RF carrier pilot tone is used to mitigate the phase noise influence. From the analysis, it appears that the phase noise influence for the two OFDM implementations is very similar. The software based system provides a method for a rigorous evaluation of the phase noise variance caused by Common Phase Error (CPE) and Inter-Carrier Interference (ICI) and this, in turns, leads to a BER specification. Numerical results focus on a CO-OFDM system with 1GS/s QPSK channel modulation. Worst case BER results are evaluated and compared to the BER of a QPSK system with the same capacity as the OFDM implementation. Results are evaluated as a function of transmission distance, and for the QPSK system the influence of equalization enhanced phase noise (EEPN) is included. For both types of systems, the phase noise variance increases significantly with increasing transmission distance. An important and novel observation is that the two types of systems have very closely the same BER as a function of transmission distance for the same capacity. For the high capacity QPSK implementation, the increase in BER is due to EEPN, whereas for the OFDM approach it is due to the dispersion caused walk-off of the RF pilot tone relative to the OFDM signal channels. For a total capacity of 400 Gb/s, the transmission distance to have the BER < 10-4 is less than 277 km.
A platform-independent robot control architecture for multiple therapeutic scenarios
Venue: arXiv cs.RO 2016
Year: 2016

While social robots are developed to provide assistance to users through social interactions, their behaviors are dominantly pre-programmed and remote-controlled. Despite the numerous robot control architectures being developed, very few offer reutilization opportunities in various therapeutic contexts. To bridge this gap, we propose a robot control architecture to be applied in different scenarios taking into account requirements from both therapeutic and robotic perspectives. As robot behaviors are kept at an abstract level and afterward mapped with the robot's morphology, the proposed architecture accommodates its applicability to a variety of social robot platforms.
Monitoring and Prediction in Smart Energy Systems via Multi-timescale Nexting
Venue: arXiv cs.SY 2016
Year: 2016

Reliable prediction of system status is a highly demanded functionality of smart energy systems, which can enable users or human operators to react quickly to potential future system changes. By adopting the multi-timescale nexting method, we develop an architecture of human-in-the-loop energy control system, which is capable of casting short-term predictive information about the specific smart energy system. The developed architecture does either require a system model nor additional acquisition of (sensor) data in the existing system configuration. Our first experiments demonstrate the performance of the proposed control architecture in an electrical heating system simulation. In the second experiment, we verify the effectiveness of our developed structure in simulating a heating system in a thermal model of a building, by employing natural EnergyPlus temperature data.
VBCA: A Virtual Forces Clustering Algorithm for Autonomous Aerial Drone Systems
Venue: arXiv cs.NI 2016
Year: 2016

We consider the positioning problem of aerial drone systems for efficient three-dimensional (3-D) coverage. Our solution draws from molecular geometry, where forces among electron pairs surrounding a central atom arrange their positions. In this paper, we propose a 3-D clustering algorithm for autonomous positioning (VBCA) of aerial drone networks based on virtual forces. These virtual forces induce interactions among drones and structure the system topology. The advantages of our approach are that (1) virtual forces enable drones to self-organize the positioning process and (2) VBCA can be implemented entirely localized. Extensive simulations show that our virtual forces clustering approach produces scalable 3-D topologies exhibiting near-optimal volume coverage. VBCA triggers efficient topology rearrangement for an altering number of nodes, while providing network connectivity to the central drone. We also draw a comparison of volume coverage achieved by VBCA against existing approaches and find VBCA up to 40\% more efficient.
Playing Atari Games with Deep Reinforcement Learning and Human Checkpoint Replay
Venue: arXiv cs.AI 2016
Year: 2016

This paper introduces a novel method for learning how to play the most difficult Atari 2600 games from the Arcade Learning Environment using deep reinforcement learning. The proposed method, human checkpoint replay, consists in using checkpoints sampled from human gameplay as starting points for the learning process. This is meant to compensate for the difficulties of current exploration strategies, such as epsilon-greedy, to find successful control policies in games with sparse rewards. Like other deep reinforcement learning architectures, our model uses a convolutional neural network that receives only raw pixel inputs to estimate the state value function. We tested our method on Montezuma's Revenge and Private Eye, two of the most challenging games from the Atari platform. The results we obtained show a substantial improvement compared to previous learning approaches, as well as over a random player. We also propose a method for training deep reinforcement learning agents using human gameplay experience, which we call human experience replay.
Improved Hardness for Cut, Interdiction, and Firefighter Problems
Venue: arXiv cs.CC 2016
Year: 2016

We study variants of the classic $s$-$t$ cut problem and prove the following improved hardness results assuming the Unique Games Conjecture (UGC). - For any constant $k \geq 2$ and $ε> 0$, we show that Directed Multicut with $k$ source-sink pairs is hard to approximate within a factor $k - ε$. This matches the trivial $k$-approximation algorithm. By a simple reduction, our result for $k = 2$ implies that Directed Multiway Cut with two terminals (also known as $s$-$t$ Bicut) is hard to approximate within a factor $2 - ε$, matching the trivial $2$-approximation algorithm. Previously, the best hardness factor for these problems (for constant $k$) was $1.5 - ε$ under the UGC. - For Length-Bounded Cut and Shortest Path Interdiction, we show that both problems are hard to approximate within any constant factor, even if we allow bicriteria approximation. If we want to cut vertices or the graph is directed, our hardness factor for Length-Bounded Cut matches the best approximation ratio up to a constant. Previously, the best hardness factor was $1.1377$ for Length-Bounded Cut and $2$ for Shortest Path Interdiction. - Assuming a variant of the UGC (implied by another variant of Bansal and Khot), we prove that it is hard to approximate Resource Minimization Fire Containment within any constant factor. Previously, the best hardness factor was $2$. Our results are based on a general method of converting an integrality gap instance to a length-control dictatorship test for variants of the $s$-$t$ cut problem, which may be useful for other problems.
Congestion Games with Mixed Objectives
Venue: arXiv cs.GT 2016
Year: 2016

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.
Optimal Consistent Network Updates in Polynomial Time
Venue: arXiv cs.NI 2016
Year: 2016

Software-defined networking (SDN) allows operators to control the behavior of a network by programatically managing the forwarding rules installed on switches. However, as is common in distributed systems, it can be difficult to ensure that certain consistency properties are preserved during periods of reconfiguration. The widely-accepted notion of PER-PACKET CONSISTENCY requires every packet to be forwarded using the new configuration or the old configuration, but not a mixture of the two. If switches can be updated in some (partial) order which guarantees that per-packet consistency is preserved, we call this order a CONSISTENT ORDER UPDATE. In particular, switches that are incomparable in this order can be updated in parallel. We call a consistent order update OPTIMAL if it allows maximal parallelism. This paper presents a polynomial-time algorithm for finding an optimal consistent order update. This contrasts with other recent results in the literature, which show that for other classes of properties (e.g., loop-freedom and waypoint enforcement), the optimal update problem is NP-complete.
Detecting Byzantine Attacks Without Clean Reference
Venue: arXiv cs.IT 2016
Year: 2016

We consider an amplify-and-forward relay network composed of a source, two relays, and a destination. In this network, the two relays are untrusted in the sense that they may perform Byzantine attacks by forwarding altered symbols to the destination. Note that every symbol received by the destination may be altered, and hence no clean reference observation is available to the destination. For this network, we identify a large family of Byzantine attacks that can be detected in the physical layer. We further investigate how the channel conditions impact the detection against this family of attacks. In particular, we prove that all Byzantine attacks in this family can be detected with asymptotically small miss detection and false alarm probabilities by using a sufficiently large number of channel observations \emph{if and only if} the network satisfies a non-manipulability condition. No pre-shared secret or secret transmission is needed for the detection of these attacks, demonstrating the value of this physical-layer security technique for counteracting Byzantine attacks.
Efficient and Modular Consensus-Free Reconfiguration for Fault-Tolerant Storage
Venue: arXiv cs.DC 2016
Year: 2016

Quorum systems are useful tools for implementing consistent and available storage in the presence of failures. These systems usually comprise a static set of servers that provide a fault-tolerant read/write register accessed by a set of clients. We consider a dynamic variant of these systems and propose FreeStore, a set of fault-tolerant protocols that emulates a register in dynamic asynchronous systems in which processes are able to join/leave the servers set during the execution. These protocols use a new abstraction called view generators, that captures the agreement requirements of reconfiguration and can be implemented in different system models with different properties. Particularly interesting, we present a reconfiguration protocol that is modular, efficient, consensus-free and loosely coupled with read/write protocols, improving the overall system performance.
Genetic Transfer or Population Diversification? Deciphering the Secret Ingredients of Evolutionary Multitask Optimization
Venue: arXiv cs.NE 2016
Year: 2016

Evolutionary multitasking has recently emerged as a novel paradigm that enables the similarities and/or latent complementarities (if present) between distinct optimization tasks to be exploited in an autonomous manner simply by solving them together with a unified solution representation scheme. An important matter underpinning future algorithmic advancements is to develop a better understanding of the driving force behind successful multitask problem-solving. In this regard, two (seemingly disparate) ideas have been put forward, namely, (a) implicit genetic transfer as the key ingredient facilitating the exchange of high-quality genetic material across tasks, and (b) population diversification resulting in effective global search of the unified search space encompassing all tasks. In this paper, we present some empirical results that provide a clearer picture of the relationship between the two aforementioned propositions. For the numerical experiments we make use of Sudoku puzzles as case studies, mainly because of their feature that outwardly unlike puzzle statements can often have nearly identical final solutions. The experiments reveal that while on many occasions genetic transfer and population diversity may be viewed as two sides of the same coin, the wider implication of genetic transfer, as shall be shown herein, captures the true essence of evolutionary multitasking to the fullest.
Performance Comparison of Dual Connectivity and Hard Handover for LTE-5G Tight Integration
Venue: arXiv cs.NI 2016
Year: 2016

Communications at frequencies above 10 GHz (the mmWave band) are expected to play a major role for the next generation of cellular networks (5G), because of the potential multi-gigabit, ultra-low latency performance of this technology. mmWave frequencies however suffer from very high isotropic pathloss, which may result in cells with a much smaller coverage area than current LTE macrocells. High directionality techniques will be used to improve signal quality and extend coverage area, along with a high density deployment of mmWave base stations (BS). However, when propagation conditions are hard and it is difficult to provide high quality coverage with mmWave BS, it is necessary to rely on previous generation LTE base stations, which make use of lower frequencies (900 MHz - 3.5 GHz), which are less sensitive to blockage and experience lower pathloss. In order to provide ultra-reliable services to mobile users there is a need for network architectures that tightly and seamlessly integrate the LTE and mmWave Radio Access Technologies. In this paper we will present two possible alternatives for this integration and show how simulation tools can be used to assess and compare their performance.
Selfish Cops and Passive Robber: Qualitative Games
Venue: arXiv cs.DM 2016
Year: 2016

Several variants of the cops and robbers (CR) game have been studied in the past. In this paper we examine a novel variant, which is played between two cops, each one independently trying to catch a "passive robber". We will call this the Selfish Cops and Passive Robber {SCPR} game. In short, SCPR is a stochastic two-player, zero-sum game where the opponents are the two cop players. We study sequential and concurrent versions of the SCPR game. For both cases we prove the existence of value and optimal strategies and present algorithms for the computation of these.
On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization
Venue: arXiv cs.CV 2016
Year: 2016

Some recent works in machine learning and computer vision involve the solution of a bi-level optimization problem. Here the solution of a parameterized lower-level problem binds variables that appear in the objective of an upper-level problem. The lower-level problem typically appears as an argmin or argmax optimization problem. Many techniques have been proposed to solve bi-level optimization problems, including gradient descent, which is popular with current end-to-end learning approaches. In this technical report we collect some results on differentiating argmin and argmax optimization problems with and without constraints and provide some insightful motivating examples.
Exponentially Stabilizing Continuous-Time Controllers for multi-domain hybrid systems with application to 3D bipdeal walking
Venue: arXiv cs.SY 2016
Year: 2016

This paper presents a systematic approach to exponentially stabilize the periodic orbits of multi-domain hybrid systems arising from 3D bipedal walking. Firstly, the method of Poincare sections is extended to the hybrid systems with multiple domains. Then, based on the properties of the Poincare maps, a continuous piecewise feedback control strategy is presented, and three methods are furthermore given to design the controller parameters based on the developed theorems. By those design methods, the controller parameters in each continuous phase can be designed independently, which allows the strategy to be applied to hybrid systems with multiple domains. Finally, the proposed strategy is illustrated by a simulation example. To show that the proposed strategy is not limited to bipedal robots with left-right symmetry property which is assumed in some previous works, an underactuated 3D bipedal robot with asymmetric walking gait is considered.
Dendritic Spine Shape Analysis: A Clustering Perspective
Venue: arXiv cs.CV 2016
Year: 2016

Functional properties of neurons are strongly coupled with their morphology. Changes in neuronal activity alter morphological characteristics of dendritic spines. First step towards understanding the structure-function relationship is to group spines into main spine classes reported in the literature. Shape analysis of dendritic spines can help neuroscientists understand the underlying relationships. Due to unavailability of reliable automated tools, this analysis is currently performed manually which is a time-intensive and subjective task. Several studies on spine shape classification have been reported in the literature, however, there is an on-going debate on whether distinct spine shape classes exist or whether spines should be modeled through a continuum of shape variations. Another challenge is the subjectivity and bias that is introduced due to the supervised nature of classification approaches. In this paper, we aim to address these issues by presenting a clustering perspective. In this context, clustering may serve both confirmation of known patterns and discovery of new ones. We perform cluster analysis on two-photon microscopic images of spines using morphological, shape, and appearance based features and gain insights into the spine shape analysis problem. We use histogram of oriented gradients (HOG), disjunctive normal shape models (DNSM), morphological features, and intensity profile based features for cluster analysis. We use x-means to perform cluster analysis that selects the number of clusters automatically using the Bayesian information criterion (BIC). For all features, this analysis produces 4 clusters and we observe the formation of at least one cluster consisting of spines which are difficult to be assigned to a known class. This observation supports the argument of intermediate shape types.
Dual Purpose Hashing
Venue: arXiv cs.CV 2016
Year: 2016

Recent years have seen more and more demand for a unified framework to address multiple realistic image retrieval tasks concerning both category and attributes. Considering the scale of modern datasets, hashing is favorable for its low complexity. However, most existing hashing methods are designed to preserve one single kind of similarity, thus improper for dealing with the different tasks simultaneously. To overcome this limitation, we propose a new hashing method, named Dual Purpose Hashing (DPH), which jointly preserves the category and attribute similarities by exploiting the Convolutional Neural Network (CNN) models to hierarchically capture the correlations between category and attributes. Since images with both category and attribute labels are scarce, our method is designed to take the abundant partially labelled images on the Internet as training inputs. With such a framework, the binary codes of new-coming images can be readily obtained by quantizing the network outputs of a binary-like layer, and the attributes can be recovered from the codes easily. Experiments on two large-scale datasets show that our dual purpose hash codes can achieve comparable or even better performance than those state-of-the-art methods specifically designed for each individual retrieval task, while being more compact than the compared methods.
Distributed Construction of Purely Additive Spanners
Venue: arXiv cs.DS 2016
Year: 2016

This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts. We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity using information theory. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications.
A Local-Global Approach to Semantic Segmentation in Aerial Images
Venue: arXiv cs.CV 2016
Year: 2016

Aerial images are often taken under poor lighting conditions and contain low resolution objects, many times occluded by other objects. In this domain, visual context could be of great help, but there are still very few papers that consider context in aerial image understanding and still remains an open problem in computer vision. We propose a dual-stream deep neural network that processes information along two independent pathways. Our model learns to combine local and global appearance in a complementary way, such that together form a powerful classifier. We test our dual-stream network on the task of buildings segmentation in aerial images and obtain state-of-the-art results on the Massachusetts Buildings Dataset. We study the relative importance of local appearance versus the larger scene, as well as their performance in combination on three new buildings datasets. We clearly demonstrate the effectiveness of visual context in conjunction with deep neural networks for aerial image understanding.