OpenRaiser/Intern-Atlas huggingface dataset:
Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs
Venue: arXiv cs.DC 2018
Year: 2018

We introduce a new problem in the domain of mobile robots, which we term dispersion. In this problem, $n$ robots are placed in an $n$ node graph arbitrarily and must coordinate with each other to reach a final configuration such that exactly one robot is at each node. We study this problem through the lenses of minimizing the memory required by each robot and of minimizing the number of rounds required to achieve dispersion. Dispersion is of interest due to its relationship to the problems of scattering on a graph, exploration using mobile robots, and load balancing on a graph. Additionally, dispersion has an immediate real world application due to its relationship to the problem of recharging electric cars, as each car can be considered a robot and recharging stations and the roads connecting them nodes and edges of a graph respectively. Since recharging is a costly affair relative to traveling, we want to distribute these cars amongst the various available recharge points where communication should be limited to car-to-car interactions. We provide lower bounds on both the memory required for robots to achieve dispersion and the minimum running time to achieve dispersion on any type of graph. We then analyze the trade-offs between time and memory for various types of graphs. We provide time optimal and memory optimal algorithms for several types of graphs and show the power of a little memory in terms of running time.
Learning the MMSE Channel Estimator
Venue: arXiv cs.IT 2018
Year: 2018

We present a method for estimating conditionally Gaussian random vectors with random covariance matrices, which uses techniques from the field of machine learning. Such models are typical in communication systems, where the covariance matrix of the channel vector depends on random parameters, e.g., angles of propagation paths. If the covariance matrices exhibit certain Toeplitz and shift-invariance structures, the complexity of the MMSE channel estimator can be reduced to O(M log M) floating point operations, where M is the channel dimension. While in the absence of structure the complexity is much higher, we obtain a similarly efficient (but suboptimal) estimator by using the MMSE estimator of the structured model as a blueprint for the architecture of a neural network. This network learns the MMSE estimator for the unstructured model, but only within the given class of estimators that contains the MMSE estimator for the structured model. Numerical simulations with typical spatial channel models demonstrate the generalization properties of the chosen class of estimators to realistic channel models.
Pragmatic-Pedagogic Value Alignment
Venue: arXiv cs.AI 2018
Year: 2018

As intelligent systems gain autonomy and capability, it becomes vital to ensure that their objectives match those of their human users; this is known as the value-alignment problem. In robotics, value alignment is key to the design of collaborative robots that can integrate into human workflows, successfully inferring and adapting to their users' objectives as they go. We argue that a meaningful solution to value alignment must combine multi-agent decision theory with rich mathematical models of human cognition, enabling robots to tap into people's natural collaborative capabilities. We present a solution to the cooperative inverse reinforcement learning (CIRL) dynamic game based on well-established cognitive models of decision making and theory of mind. The solution captures a key reciprocity relation: the human will not plan her actions in isolation, but rather reason pedagogically about how the robot might learn from them; the robot, in turn, can anticipate this and interpret the human's actions pragmatically. To our knowledge, this work constitutes the first formal analysis of value alignment grounded in empirically validated cognitive models.
Real-Time Head Gesture Recognition on Head-Mounted Displays using Cascaded Hidden Markov Models
Venue: arXiv cs.HC 2018
Year: 2018

Head gesture is a natural means of face-to-face communication between people but the recognition of head gestures in the context of virtual reality and use of head gesture as an interface for interacting with virtual avatars and virtual environments have been rarely investigated. In the current study, we present an approach for real-time head gesture recognition on head-mounted displays using Cascaded Hidden Markov Models. We conducted two experiments to evaluate our proposed approach. In experiment 1, we trained the Cascaded Hidden Markov Models and assessed the offline classification performance using collected head motion data. In experiment 2, we characterized the real-time performance of the approach by estimating the latency to recognize a head gesture with recorded real-time classification data. Our results show that the proposed approach is effective in recognizing head gestures. The method can be integrated into a virtual reality system as a head gesture interface for interacting with virtual worlds.
The Complexity of Concurrent Rational Synthesis
Venue: arXiv cs.LO 2018
Year: 2018

In this paper, we investigate the rational synthesis problem for concurrent game structure for a variety of objectives ranging from reachability to Muller condition. We propose a new algorithm that establishes the decidability of the non cooperative rational synthesis problem that relies solely on game theoretic technique as opposed to previous approaches that are logic based. Thanks to this approach, we construct a zero-sum turn-based game that can be adapted to each one of the afore mentioned objectives thus obtain new complexity results. In particular, we show that reachability, safety, Büchi, and co-Büchi conditions are PSpace-complete, Muller, Street, and Rabin are PSpace-hard and in ExpTime.
Cost-Driven Ontology-Based Data Access (Extended Version)
Venue: arXiv cs.DB 2018
Year: 2018

In ontology-based data access (OBDA), users are provided with a conceptual view of a (relational) data source that abstracts away details about data storage. This conceptual view is realized through an ontology that is connected to the data source through declarative mappings, and query answering is carried out by translating the user queries over the conceptual view into SQL queries over the data source. Standard translation techniques in OBDA try to transform the user query into a union of conjunctive queries (UCQ), following the heuristic argument that UCQs can be efficiently evaluated by modern relational database engines. In this work, we show that translating to UCQs is not always the best choice, and that, under certain conditions on the interplay between the ontology, the map- pings, and the statistics of the data, alternative translations can be evaluated much more efficiently. To find the best translation, we devise a cost model together with a novel cardinality estimation that takes into account all such OBDA components. Our experiments confirm that (i) alternatives to the UCQ translation might produce queries that are orders of magnitude more efficient, and (ii) the cost model we propose is faithful to the actual query evaluation cost, and hence is well suited to select the best translation.
Steklov Spectral Geometry for Extrinsic Shape Analysis
Venue: arXiv cs.GR 2018
Year: 2018

We propose using the Dirichlet-to-Neumann operator as an extrinsic alternative to the Laplacian for spectral geometry processing and shape analysis. Intrinsic approaches, usually based on the Laplace-Beltrami operator, cannot capture the spatial embedding of a shape up to rigid motion, and many previous extrinsic methods lack theoretical justification. Instead, we consider the Steklov eigenvalue problem, computing the spectrum of the Dirichlet-to-Neumann operator of a surface bounding a volume. A remarkable property of this operator is that it completely encodes volumetric geometry. We use the boundary element method (BEM) to discretize the operator, accelerated by hierarchical numerical schemes and preconditioning; this pipeline allows us to solve eigenvalue and linear problems on large-scale meshes despite the density of the Dirichlet-to-Neumann discretization. We further demonstrate that our operators naturally fit into existing frameworks for geometry processing, making a shift from intrinsic to extrinsic geometry as simple as substituting the Laplace-Beltrami operator with the Dirichlet-to-Neumann operator.
A Covert Queueing Channel in FCFS Schedulers
Venue: arXiv cs.IT 2018
Year: 2018

We study covert queueing channels (CQCs), which are a kind of covert timing channel that may be exploited in shared queues across supposedly isolated users. In our system model, a user sends messages to another user via his pattern of access to the shared resource, which serves the users according to a first come first served (FCFS) policy. One example of such a channel is the cross-virtual network covert channel in data center networks, resulting from the queueing effects of the shared resource. First, we study a system comprising a transmitter and a receiver that share a deterministic and work-conserving FCFS scheduler, and we compute the capacity of this channel. We also consider the effect of the presence of other users on the information transmission rate of this channel. The achievable information transmission rates obtained in this study demonstrate the possibility of significant information leakage and great privacy threats brought by CQCs in FCFS schedulers.
Mean Field Equilibria for Resource Competition in Spatial Settings
Venue: arXiv cs.GT 2018
Year: 2018

We study a model of competition among nomadic agents for time-varying and location-specific resources, arising in crowd-sourced transportation services, online communities, and traditional location-based economic activity. This model comprises a group of agents and a single location endowed with a dynamic stochastic resource process. Periodically, each agent derives a reward determined by the location's resource level and the number of other agents there, and has to decide whether to stay at the location or move. Upon moving, the agent arrives at a different location whose dynamics are independent and identical to the original location. Using the methodology of mean field equilibrium, we study the equilibrium behavior of the agents as a function of the dynamics of the stochastic resource process and the nature of the competition among co-located agents. We show that an equilibrium exists, where each agent decides whether to switch locations based only on their current location's resource level and the number of other agents there. We additionally show that when an agent's payoff is decreasing in the number of other agents at her location, equilibrium strategies obey a simple threshold structure. We show how to exploit this structure to compute equilibria numerically, and use these numerical techniques to study how system structure affects the agents' collective ability to explore their domain to find and effectively utilize resource-rich areas.
MVP2P: Layer-Dependency-Aware Live MVC Video Streaming over Peer-to-Peer Networks
Venue: arXiv cs.MM 2018
Year: 2018

Multiview video supports observing a scene from different viewpoints. The Joint Video Team (JVT) developed H.264/MVC to enhance the compression efficiency for multiview video, however, MVC encoded multiview video (MVC video) still requires high bitrates for transmission. This paper investigates live MVC video streaming over Peer-to-Peer (P2P) networks. The goal is to minimize the server bandwidth costs whist ensuring high streaming quality to peers. MVC employs intra-view and inter-view prediction structures, which leads to a complicated layer dependency relationship. As the peers' outbound bandwidth is shared while supplying all the MVC video layers, the bandwidth allocation to one MVC layer affects the available outbound bandwidth of the other layers. To optimise the utilisation of the peers' outbound bandwidth for providing video layers, a maximum flow based model is proposed which considers the MVC video layer dependency and the layer supplying relationship between peers. Based on the model, a layer dependency aware live MVC video streaming method over a BitTorrent-like P2P network is proposed, named MVP2P. The key components of MVP2P include a chunk scheduling strategy and a peer selection strategy for receiving peers, and a bandwidth scheduling algorithm for supplying peers. To evaluate the efficiency of the proposed solution, MVP2P is compared with existing methods considering the constraints of peer bandwidth, peer numbers, view switching rates, and peer churns. The test results show that MVP2P significantly outperforms the existing methods.
Opening the black box of energy modelling: Strategies and lessons learned
Venue: arXiv cs.CY 2018
Year: 2018

The global energy system is undergoing a major transition, and in energy planning and decision-making across governments, industry and academia, models play a crucial role. Because of their policy relevance and contested nature, the transparency and open availability of energy models and data are of particular importance. Here we provide a practical how-to guide based on the collective experience of members of the Open Energy Modelling Initiative (Openmod). We discuss key steps to consider when opening code and data, including determining intellectual property ownership, choosing a licence and appropriate modelling languages, distributing code and data, and providing support and building communities. After illustrating these decisions with examples and lessons learned from the community, we conclude that even though individual researchers' choices are important, institutional changes are still also necessary for more openness and transparency in energy research.
Closed-Loop Policies for Operational Tests of Safety-Critical Systems
Venue: arXiv cs.AI 2018
Year: 2018

Manufacturers of safety-critical systems must make the case that their product is sufficiently safe for public deployment. Much of this case often relies upon critical event outcomes from real-world testing, requiring manufacturers to be strategic about how they allocate testing resources in order to maximize their chances of demonstrating system safety. This work frames the partially observable and belief-dependent problem of test scheduling as a Markov decision process, which can be solved efficiently to yield closed-loop manufacturer testing policies. By solving for policies over a wide range of problem formulations, we are able to provide high-level guidance for manufacturers and regulators on issues relating to the testing of safety-critical systems. This guidance spans an array of topics, including circumstances under which manufacturers should continue testing despite observed incidents, when manufacturers should test aggressively, and when regulators should increase or reduce the real-world testing requirements for an autonomous vehicle.
MMGAN: Manifold Matching Generative Adversarial Network
Venue: arXiv cs.LG 2018
Year: 2018

It is well-known that GANs are difficult to train, and several different techniques have been proposed in order to stabilize their training. In this paper, we propose a novel training method called manifold-matching, and a new GAN model called manifold-matching GAN (MMGAN). MMGAN finds two manifolds representing the vector representations of real and fake images. If these two manifolds match, it means that real and fake images are statistically identical. To assist the manifold-matching task, we also use i) kernel tricks to find better manifold structures, ii) moving-averaged manifolds across mini-batches, and iii) a regularizer based on correlation matrix to suppress mode collapse. We conduct in-depth experiments with three image datasets and compare with several state-of-the-art GAN models. 32.4% of images generated by the proposed MMGAN are recognized as fake images during our user study (16% enhancement compared to other state-of-the-art model). MMGAN achieved an unsupervised inception score of 7.8 for CIFAR-10.
Curriculum Domain Adaptation for Semantic Segmentation of Urban Scenes
Venue: arXiv cs.CV 2018
Year: 2018

During the last half decade, convolutional neural networks (CNNs) have triumphed over semantic segmentation, which is one of the core tasks in many applications such as autonomous driving. However, to train CNNs requires a considerable amount of data, which is difficult to collect and laborious to annotate. Recent advances in computer graphics make it possible to train CNNs on photo-realistic synthetic imagery with computer-generated annotations. Despite this, the domain mismatch between the real images and the synthetic data cripples the models' performance. Hence, we propose a curriculum-style learning approach to minimize the domain gap in urban scenery semantic segmentation. The curriculum domain adaptation solves easy tasks first to infer necessary properties about the target domain; in particular, the first task is to learn global label distributions over images and local distributions over landmark superpixels. These are easy to estimate because images of urban scenes have strong idiosyncrasies (e.g., the size and spatial relations of buildings, streets, cars, etc.). We then train a segmentation network while regularizing its predictions in the target domain to follow those inferred properties. In experiments, our method outperforms the baselines on two datasets and two backbone networks. We also report extensive ablation studies about our approach.
Owl: A General-Purpose Numerical Library in OCaml
Venue: arXiv cs.MS 2018
Year: 2018

Owl is a new numerical library developed in the OCaml language. It focuses on providing a comprehensive set of high-level numerical functions so that developers can quickly build up data analytical applications. In this abstract, we will present Owl's design, core components, and its key functionality.
Stable Throughput of Cooperative Cognitive Networks with Energy Harvesting: Finite Relay Buffer and Finite Battery Capacity
Venue: arXiv cs.IT 2018
Year: 2018

This paper studies a generic model for cooperative cognitive radio networks where the secondary user is equipped with a finite relay queue as well as a finite battery queue. Our prime objective is to characterize the stable throughput region. Nevertheless, the complete characterization of the stable throughput region for such system is notoriously difficult, since the computation of the steady state distribution of the two-dimensional Markov Chain (MC) model for both finite queues is prohibitively complex. We first propose an algorithm to characterize the stable throughput region numerically, and show its sheer computational complexity for large queue lengths. To lend tractability and explore the nature of design parameters optimization at the cognitive node, we next focus on two simpler systems, namely, finite battery queue with infinite relay queue and finite relay queue with infinite battery queue (referred henceforth as dominant system $1$ and $2$, respectively). For each proposed dominant system, we investigate the maximum service rate of the cognitive node subject to stability conditions. Despite the complexity of the formulated optimization problems, due to their non-convexity, we exploit the problems' structure to transform them into linear programs. Thus, we are able to solve them efficiently using standard linear programming solvers. Our numerical results demonstrate that, in practical systems, finite battery and relay queues achieve the same level of benefits of a system with infinite queue sizes, when their sizes are sufficiently large. They also reveal that the achievable stable throughput region significantly expands when the arrival rate of the energy harvesting process increases.
Polar Code Construction for List Decoding
Venue: arXiv cs.IT 2018
Year: 2018

A heuristic construction of polar codes for successive cancellation list (SCL) decoding with a given list size is proposed to balance the trade-off between performance measured in frame error rate (FER) and decoding complexity. Furthermore, a construction based on dynamically frozen bits with constraints among the "low weight bits" (LWB) is presented. Simulation results show that the LWB-polar codes outperform the CRC-polar codes and the eBCH-polar codes under SCL decoding.
Pricing for Online Resource Allocation: Intervals and Paths
Venue: arXiv cs.GT 2018
Year: 2018

We present pricing mechanisms for several online resource allocation problems which obtain tight or nearly tight approximations to social welfare. In our settings, buyers arrive online and purchase bundles of items; buyers' values for the bundles are drawn from known distributions. This problem is closely related to the so-called prophet-inequality of Krengel and Sucheston and its extensions in recent literature. Motivated by applications to cloud economics, we consider two kinds of buyer preferences. In the first, items correspond to different units of time at which a resource is available; the items are arranged in a total order and buyers desire intervals of items. The second corresponds to bandwidth allocation over a tree network; the items are edges in the network and buyers desire paths. Because buyers' preferences have complementarities in the settings we consider, recent constant-factor approximations via item prices do not apply, and indeed strong negative results are known. We develop static, anonymous bundle pricing mechanisms. For the interval preferences setting, we show that static, anonymous bundle pricings achieve a sublogarithmic competitive ratio, which is optimal (within constant factors) over the class of all online allocation algorithms, truthful or not. For the path preferences setting, we obtain a nearly-tight logarithmic competitive ratio. Both of these results exhibit an exponential improvement over item pricings for these settings. Our results extend to settings where the seller has multiple copies of each item, with the competitive ratio decreasing linearly with supply. Such a gradual tradeoff between supply and the competitive ratio for welfare was previously known only for the single item prophet inequality.
Grounding Language for Transfer in Deep Reinforcement Learning
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we explore the utilization of natural language to drive transfer for reinforcement learning (RL). Despite the wide-spread application of deep RL techniques, learning generalized policy representations that work across domains remains a challenging problem. We demonstrate that textual descriptions of environments provide a compact intermediate channel to facilitate effective policy transfer. Specifically, by learning to ground the meaning of text to the dynamics of the environment such as transitions and rewards, an autonomous agent can effectively bootstrap policy learning on a new domain given its description. We employ a model-based RL approach consisting of a differentiable planning module, a model-free component and a factorized state representation to effectively use entity descriptions. Our model outperforms prior work on both transfer and multi-task scenarios in a variety of different environments. For instance, we achieve up to 14% and 11.5% absolute improvement over previously existing models in terms of average and initial rewards, respectively.