OpenRaiser/Intern-Atlas huggingface dataset:
Configuration Lattices for Planar Contact Manipulation Under Uncertainty
Venue: arXiv cs.RO 2016
Year: 2016

This work addresses the challenge of a robot using real-time feedback from contact sensors to reliably manipulate a movable object on a cluttered tabletop. We formulate contact manipulation as a partially observable Markov decision process (POMDP) in the joint space of robot configurations and object poses. The POMDP formulation enables the robot to actively gather information and reduce the uncertainty on the object pose. Further, it incorporates all major constraints for robot manipulation: kinematic reachability, self-collision, and collision with obstacles. To solve the POMDP, we apply DESPOT, a state-of-the-art online POMDP algorithm. Our approach leverages two key ideas for computational efficiency. First, it performs lazy construction of a configuration-space lattice by interleaving construction of the lattice and online POMDP planning. Second, it combines online and offline POMDP planning by solving relaxed POMDP offline and using the solution to guide the online search algorithm. We evaluated the proposed approach on a seven degree-of-freedom robot arm in simulation environments. It significantly outperforms several existing algorithms, including some commonly used heuristics for contact manipulation under uncertainty.
Stochastic Contextual Bandits with Known Reward Functions
Venue: arXiv cs.LG 2016
Year: 2016

Many sequential decision-making problems in communication networks can be modeled as contextual bandit problems, which are natural extensions of the well-known multi-armed bandit problem. In contextual bandit problems, at each time, an agent observes some side information or context, pulls one arm and receives the reward for that arm. We consider a stochastic formulation where the context-reward tuples are independently drawn from an unknown distribution in each trial. Motivated by networking applications, we analyze a setting where the reward is a known non-linear function of the context and the chosen arm's current state. We first consider the case of discrete and finite context-spaces and propose DCB($ε$), an algorithm that we prove, through a careful analysis, yields regret (cumulative reward gap compared to a distribution-aware genie) scaling logarithmically in time and linearly in the number of arms that are not optimal for any context, improving over existing algorithms where the regret scales linearly in the total number of arms. We then study continuous context-spaces with Lipschitz reward functions and propose CCB($ε, δ$), an algorithm that uses DCB($ε$) as a subroutine. CCB($ε, δ$) reveals a novel regret-storage trade-off that is parametrized by $δ$. Tuning $δ$ to the time horizon allows us to obtain sub-linear regret bounds, while requiring sub-linear storage. By exploiting joint learning for all contexts we get regret bounds for CCB($ε, δ$) that are unachievable by any existing contextual bandit algorithm for continuous context-spaces. We also show similar performance bounds for the unknown horizon case.
Energy-Distortion Tradeoff for the Gaussian Broadcast Channel with Feedback
Venue: arXiv cs.IT 2016
Year: 2016

This work focuses on the minimum transmission energy required for communicating a pair of correlated Gaussian sources over a two-user Gaussian broadcast channel with noiseless and causal channel output feedback (GBCF). We study the fundamental limit on the required transmission energy for broadcasting a pair of source samples, such that each source can be reconstructed at its respective receiver to within a target distortion, when the source-channel bandwidth ratio is not restricted. We derive a lower bound and three distinct upper bounds on the minimum required energy. For the upper bounds we analyze three transmission schemes: Two schemes are based on separate source-channel coding, and apply coding over multiple samples of source pairs. The third scheme is based on joint source-channel coding obtained by extending the Ozarow-Leung (OL) transmission scheme, which applies uncoded linear transmission. Numerical simulations show that despite its simplicity, the energy-distortion tradeoff of the OL-based scheme is close to that of the better separation-based scheme, which indicates that the OL scheme is attractive for energy-efficient source transmission over GBCFs.
MagBoard: Magnetic-based Ubiquitous Homomorphic Off-the-shelf Keyboard
Venue: arXiv cs.HC 2016
Year: 2016

One of the main methods for interacting with mobile devices today is the error-prone and inflexible touch-screen keyboard. This paper proposes MagBoard: a homomorphic ubiquitous keyboard for mobile devices. MagBoard allows application developers and users to design and print different custom keyboards for the same applications to fit different user's needs. The core idea is to leverage the triaxial magnetometer embedded in standard mobile phones to accurately localize the location of a magnet on a virtual grid superimposed on the printed keyboard. This is achieved through a once in a lifetime fingerprint. MagBoard also provides a number of modules that allow it to cope with background magnetic noise, heterogeneous devices, different magnet shapes, sizes, and strengths, as well as changes in magnet polarity. Our implementation of MagBoard on Android phones with extensive evaluation in different scenarios demonstrates that it can achieve a key detection accuracy of more than 91% for keys as small as 2cm*2cm, reaching 100% for 4cm*4cm keys. This accuracy is robust with different phones and magnets, highlighting MagBoard promise as a homomorphic ubiquitous keyboard for mobile devices.
CheapSMC: A Framework to Minimize SMC Cost in Cloud
Venue: arXiv cs.CR 2016
Year: 2016

Secure multi-party computation (SMC) techniques are increasingly becoming more efficient and practical thanks to many recent novel improvements. The recent work have shown that different protocols that are implemented using different sharing mechanisms (e.g., boolean, arithmetic sharings, etc.) may have different computational and communication costs. Although there are some works that automatically mix protocols of different sharing schemes to fasten execution, none of them provide a generic optimization framework to find the cheapest mixed-protocol SMC execution for cloud deployment. In this work, we propose a generic SMC optimization framework CheapSMC that can use any mixed-protocol SMC circuit evaluation tool as a black-box to find the cheapest SMC cloud deployment option. To find the cheapest SMC protocol, CheapSMC runs one time benchmarks for the target cloud service and gathers performance statistics for basic circuit components. Using these performance statistics, optimization layer of CheapSMC runs multiple heuristics to find the cheapest mix-protocol circuit evaluation. Later on, the optimized circuit is passed to a mix-protocol SMC tool for actual executable generation. Our empirical results gathered by running different cases studies show that significant cost savings could be achieved using our optimization framework.
A Cloud Platform-as-a-Service for Multimedia Conferencing Service Provisioning
Venue: arXiv cs.NI 2016
Year: 2016

Multimedia conferencing is the real-time exchange of multimedia content between multiple parties. It is the basis of a wide range of applications (e.g., multimedia multiplayer game). Cloud-based provisioning of the conferencing services on which these applications rely will bring benefits, such as easy service provisioning and elastic scalability. However, it remains a big challenge. This paper proposes a PaaS for conferencing service provisioning. The proposed PaaS is based on a business model from the state of the art. It relies on conferencing IaaSs that, instead of VMs, offer conferencing substrates (e.g., dial-in signaling, video mixer and audio mixer). The PaaS enables composition of new conferences from substrates on the fly. This has been prototyped in this paper and, in order to evaluate it, a conferencing IaaS is also implemented. Performance measurements are also made.
BLMA: A Blind Matching Algorithm with Application to Cognitive Radio Networks
Venue: arXiv cs.GT 2016
Year: 2016

We consider a two-sided matching problem with a defined notion of pairwise stability. We propose a distributed blind matching algorithm (BLMA) to solve the problem. We prove the solution produced by BLMA will converge to an $ε$-pairwise stable outcome with probability one. We then consider a matching problem in cognitive radio networks. Secondary users (SUs) are allowed access time to the spectrum belonging to the primary users (PUs) provided that they relay primary messages. We propose a realization of the BLMA to produce an $ε$-pairwise stable solution assuming quasi-convex and quasi-concave utilities. In the case of more general utility forms, we show another BLMA realization to provide a stable solution. Furthermore, we propose negotiation mechanism to bias the algorithm towards one side of the market. We use this mechanism to protect the exclusive rights of the PUs to the spectrum. In all such implementations of the BLMA, we impose a limited information exchange in the network so that agents can only calculate their own utilities, but no information is available about the utilities of any other users in the network.
Connecting every bit of knowledge: The structure of Wikipedia's First Link Network
Venue: arXiv cs.SI 2016
Year: 2016

Apples, porcupines, and the most obscure Bob Dylan song---is every topic a few clicks from Philosophy? Within Wikipedia, the surprising answer is yes: nearly all paths lead to Philosophy. Wikipedia is the largest, most meticulously indexed collection of human knowledge ever amassed. More than information about a topic, Wikipedia is a web of naturally emerging relationships. By following the first link in each article, we algorithmically construct a directed network of all 4.7 million articles: Wikipedia's First Link Network. Here, we study the English edition of Wikipedia's First Link Network for insight into how the many articles on inventions, places, people, objects, and events are related and organized. By traversing every path, we measure the accumulation of first links, path lengths, groups of path-connected articles, and cycles. We also develop a new method, traversal funnels, to measure the influence each article exerts in shaping the network. Traversal funnels provides a new measure of influence for directed networks without spill-over into cycles, in contrast to traditional network centrality measures. Within Wikipedia's First Link Network, we find scale-free distributions describe path length, accumulation, and influence. Far from dispersed, first links disproportionately accumulate at a few articles---flowing from specific to general and culminating around fundamental notions such as Community, State, and Science. Philosophy directs more paths than any other article by two orders of magnitude. We also observe a gravitation towards topical articles such as Health Care and Fossil Fuel. These findings enrich our view of the connections and structure of Wikipedia's ever growing store of knowledge.
An optimized round robin cpu scheduling algorithm with dynamic time quantum
Venue: arXiv cs.OS 2016
Year: 2016

CPU scheduling is one of the most crucial operations performed by operating system. Different algorithms are available for CPU scheduling amongst them RR (Round Robin) is considered as optimal in time shared environment. The effectiveness of Round Robin completely depends on the choice of time quantum. In this paper a new CPU scheduling algorithm has been proposed, named as DABRR (Dynamic Average Burst Round Robin). That uses dynamic time quantum instead of static time quantum used in RR. The performance of the proposed algorithm is experimentally compared with traditional RR and some existing variants of RR. The results of our approach presented in this paper demonstrate improved performance in terms of average waiting time, average turnaround time, and context switching.
Healthiness from Duality
Venue: arXiv cs.LO 2016
Year: 2016

Healthiness is a good old question in program logics that dates back to Dijkstra. It asks for an intrinsic characterization of those predicate transformers which arise as the (backward) interpretation of a certain class of programs. There are several results known for healthiness conditions: for deterministic programs, nondeterministic ones, probabilistic ones, etc. Building upon our previous works on so-called state-and-effect triangles, we contribute a unified categorical framework for investigating healthiness conditions. We find the framework to be centered around a dual adjunction induced by a dualizing object, together with our notion of relative Eilenberg-Moore algebra playing fundamental roles too. The latter notion seems interesting in its own right in the context of monads, Lawvere theories and enriched categories.
Dynamic Address Allocation Algorithm for Mobile Ad hoc Networks
Venue: arXiv cs.NI 2016
Year: 2016

A Mobile Ad hoc network (MANET) consists of nodes which use multi-hop communication to establish connection between nodes. Traditional infrastructure based systems use a centralized architecture for address allocation. However, this is not possible in Ad hoc networks due to their dynamic structure. Many schemes have been proposed to solve this problem, but most of them use network-wide broadcasts to ensure the availability of a new address. This becomes extremely difficult as network size grows. In this paper, we propose an address allocation algorithm which avoids network-wide broadcasts to allocate address to a new node. Moreover, the algorithm allocates addresses dynamically such that the network maintains an "IP resembles topology" state. In such a state, routing becomes easier and the overall overhead in communication is reduced. This algorithm is particularly useful for routing protocols which use topology information to route messages in the network. Our solution is designed with scalability in mind such that the cost of address assignment to a new node is independent of the number of nodes in the network.
Isogeometric analysis using manifold-based smooth basis functions
Venue: arXiv cs.NA 2016
Year: 2016

We present an isogeometric analysis technique that builds on manifold-based smooth basis functions for geometric modelling and analysis. Manifold-based surface construction techniques are well known in geometric modelling and a number of variants exist. Common to all is the concept of constructing a smooth surface by blending together overlapping patches (or, charts), as in differential geometry description of manifolds. Each patch on the surface has a corresponding planar patch with a smooth one-to-one mapping onto the surface. In our implementation, manifold techniques are combined with conformal parametrisations and the partition-of-unity method for deriving smooth basis functions on unstructured quadrilateral meshes. Each vertex and its adjacent elements on the surface control mesh have a corresponding planar patch of elements. The star-shaped planar patch with congruent wedge-shaped elements is smoothly parameterised with copies of a conformally mapped unit square. The conformal maps can be easily inverted in order to compute the transition functions between the different planar patches that have an overlap on the surface. On the collection of star-shaped planar patches the partition of unity method is used for approximation. The smooth partition of unity, or blending functions, are assembled from tensor-product b-spline segments defined on a unit square. On each patch a polynomial with a prescribed degree is used as a local approximant. To obtain a mesh-based approximation scheme, the coefficients of the local approximants are expressed in dependence of vertex coefficients. This yields a basis function for each vertex of the mesh which is smooth and non-zero over a vertex and its adjacent elements. Our numerical simulations indicate the optimal convergence of the resulting approximation scheme for Poisson problems and near optimal convergence for thin-plate and thin-shell problems.
Fourier Analysis and q-Gaussian Functions: Analytical and Numerical Results
Venue: arXiv cs.CV 2016
Year: 2016

It is a consensus in signal processing that the Gaussian kernel and its partial derivatives enable the development of robust algorithms for feature detection. Fourier analysis and convolution theory have central role in such development. In this paper we collect theoretical elements to follow this avenue but using the q-Gaussian kernel that is a nonextensive generalization of the Gaussian one. Firstly, we review some theoretical elements behind the one-dimensional q-Gaussian and its Fourier transform. Then, we consider the two-dimensional q-Gaussian and we highlight the issues behind its analytical Fourier transform computation. We analyze the q-Gaussian kernel in the space and Fourier domains using the concepts of space window, cut-off frequency, and the Heisenberg inequality.
Hybrid Architectures with Few-Bit ADC Receivers: Achievable Rates and Energy-Rate Tradeoffs
Venue: arXiv cs.IT 2016
Year: 2016

Hybrid analog/digital architectures and receivers with low-resolution analog-to-digital converters (ADCs) are two low power solutions for wireless systems with large antenna arrays, such as millimeter wave and massive MIMO systems. Most prior work represents two extreme cases in which either a small number of RF chains with full-resolution ADCs, or low resolution ADC with a number of RF chains equal to the number of antennas is assumed. In this paper, a generalized hybrid architecture with a small number of RF chains and finite number of ADC bits is proposed. For this architecture, achievable rates with channel inversion and SVD based transmission methods are derived. Results show that the achievable rate is comparable to that obtained by full-precision ADC receivers at low and medium SNRs. A trade-off between the achievable rate and power consumption for different numbers of bits and RF chains is devised. This enables us to draw some conclusions on the number of ADC bits needed to maximize the system energy efficiency. Numerical simulations show that coarse ADC quantization is optimal under various system configurations. This means that hybrid combining with coarse quantization achieves better energy-rate trade-off compared to both hybrid combining with full-resolutions ADCs and 1-bit ADC combining.
Security and Privacy Aspects in MapReduce on Clouds: A Survey
Venue: arXiv cs.DB 2016
Year: 2016

MapReduce is a programming system for distributed processing large-scale data in an efficient and fault tolerant manner on a private, public, or hybrid cloud. MapReduce is extensively used daily around the world as an efficient distributed computation tool for a large class of problems, e.g., search, clustering, log analysis, different types of join operations, matrix multiplication, pattern matching, and analysis of social networks. Security and privacy of data and MapReduce computations are essential concerns when a MapReduce computation is executed in public or hybrid clouds. In order to execute a MapReduce job in public and hybrid clouds, authentication of mappers-reducers, confidentiality of data-computations, integrity of data-computations, and correctness-freshness of the outputs are required. Satisfying these requirements shield the operation from several types of attacks on data and MapReduce computations. In this paper, we investigate and discuss security and privacy challenges and requirements, considering a variety of adversarial capabilities, and characteristics in the scope of MapReduce. We also provide a review of existing security and privacy protocols for MapReduce and discuss their overhead issues.
From Modular to Distributed Open Architectures: A Unified Decision Framework
Venue: arXiv cs.SY 2016
Year: 2016

This paper introduces a conceptual, yet quantifiable, architecture framework by extending the notion of system modularity in its broadest sense. Acknowledging that modularity is not a binary feature and comes in various types and levels, the proposed framework introduces higher levels of modularity that naturally incorporate decentralized architecture on the one hand and autonomy in agents and subsystems on the other. This makes the framework suitable for modularity decisions in Systems of Systems and for analyzing the impact of modularity on broader surrounding ecosystems. The stages of modularity in the proposed framework are naturally aligned with the level of variations and uncertainty in the system and its environment, a relationship that is central to the benefits of modularity. The conceptual framework is complemented with a decision layer that makes it suitable to be used as a computational architecture decision tool to determine the appropriate stage and level of modularity of a system, for a given profile of variations and uncertainties in its environment. We further argue that the fundamental systemic driving forces and trade-offs of moving from monolithic to distributed architecture are essentially similar to those for moving from integral to modular architectures. The spectrum, in conjunction with the decision layer, could guide system architects when selecting appropriate parameters and building a system-specific computational tool from a combination of existing tools and techniques. To demonstrate the applicability of the framework, a case for fractionated satellite systems based on a simplified demo of the DARPA F6 program is presented.
Optimal Remote Estimation Over Use-Dependent Packet-Drop Channels - Extended Version
Venue: arXiv cs.SY 2016
Year: 2016

Consider a discrete-time remote estimation system formed by an encoder, a transmission policy, a channel, and a remote estimator. The encoder assesses a random process that the remote estimator seeks to estimate based on information sent to it by the encoder via the channel. The channel is affected by Bernoulli drops. The instantaneous probability of a drop is governed by a finite state machine (FSM). The state of the FSM is denoted as the channel state. At each time step, the encoder decides whether to attempt a transmission through the packet-drop link. The sequence of encoder decisions is the input to the FSM. This paper seeks to design an encoder, transmission policy and remote estimator that minimize a finite-horizon mean squared error cost. We present two structural results. The first result in which we assume that the process to be estimated is white and Gaussian, we show that there is an optimal transmission policy governed by a threshold on the estimation error. The second result characterizes optimal symmetric transmission policies for the case when the measured process is the state of a scalar linear time-invariant plant driven by white Gaussian noise. Use-dependent packet-drop channels can be used to quantify the effect of transmission on channel quality when the encoder is powered by energy harvesting. An application to a mixed initiative system in which a human operator performs visual search tasks is also presented.