OpenRaiser/Intern-Atlas huggingface dataset:
Monte Carlo Sampling Methods for Approximating Interactive POMDPs
Venue: arXiv cs.AI 2014
Year: 2014

Partially observable Markov decision processes (POMDPs) provide a principled framework for sequential planning in uncertain single agent settings. An extension of POMDPs to multiagent settings, called interactive POMDPs (I-POMDPs), replaces POMDP belief spaces with interactive hierarchical belief systems which represent an agent's belief about the physical world, about beliefs of other agents, and about their beliefs about others' beliefs. This modification makes the difficulties of obtaining solutions due to complexity of the belief and policy spaces even more acute. We describe a general method for obtaining approximate solutions of I-POMDPs based on particle filtering (PF). We introduce the interactive PF, which descends the levels of the interactive belief hierarchies and samples and propagates beliefs at each level. The interactive PF is able to mitigate the belief space complexity, but it does not address the policy space complexity. To mitigate the policy space complexity -- sometimes also called the curse of history -- we utilize a complementary method based on sampling likely observations while building the look ahead reachability tree. While this approach does not completely address the curse of history, it beats back the curse's impact substantially. We provide experimental results and chart future work.
A Bilinear Programming Approach for Multiagent Planning
Venue: arXiv cs.AI 2014
Year: 2014

Multiagent planning and coordination problems are common and known to be computationally hard. We show that a wide range of two-agent problems can be formulated as bilinear programs. We present a successive approximation algorithm that significantly outperforms the coverage set algorithm, which is the state-of-the-art method for this class of multiagent problems. Because the algorithm is formulated for bilinear programs, it is more general and simpler to implement. The new algorithm can be terminated at any time and-unlike the coverage set algorithm-it facilitates the derivation of a useful online performance bound. It is also much more efficient, on average reducing the computation time of the optimal solution by about four orders of magnitude. Finally, we introduce an automatic dimensionality reduction method that improves the effectiveness of the algorithm, extending its applicability to new domains and providing a new way to analyze a subclass of bilinear programs.
Content Modeling Using Latent Permutations
Venue: arXiv cs.IR 2014
Year: 2014

We present a novel Bayesian topic model for learning discourse-level document structure. Our model leverages insights from discourse theory to constrain latent topic assignments in a way that reflects the underlying organization of document topics. We propose a global model in which both topic selection and ordering are biased to be similar across a collection of related documents. We show that this space of orderings can be effectively represented using a distribution over permutations called the Generalized Mallows Model. We apply our method to three complementary discourse-level tasks: cross-document alignment, document segmentation, and information ordering. Our experiments show that incorporating our permutation-based model in these applications yields substantial improvements in performance over previously proposed methods.
BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm
Venue: arXiv cs.AI 2014
Year: 2014

Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, and Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.
Dynamic Spectrum Access in Cognitive Radio Networks with RF Energy Harvesting
Venue: arXiv cs.NI 2014
Year: 2014

Spectrum efficiency and energy efficiency are two critical issues in designing wireless networks. Through dynamic spectrum access, cognitive radios can improve the spectrum efficiency and capacity of wireless networks. On the other hand, radio frequency (RF) energy harvesting has emerged as a promising technique to supply energy to wireless networks and thereby increase their energy efficiency. Therefore, to achieve both spectrum and energy efficiencies, the secondary users in a cognitive radio network (CRN) can be equipped with the RF energy harvesting capability and such a network can be referred to as an RF-powered cognitive radio network. In this article, we provide an overview of the RF-powered CRNs and discuss the challenges that arise for dynamic spectrum access in these networks. Focusing on the tradeoff among spectrum sensing, data transmission, and RF energy harvesting, then we discuss the dynamic channel selection problem in a multi-channel RF-powered CRN. In the RF-powered CRN, a secondary user can adaptively select a channel to transmit data when the channel is not occupied by any primary user. Alternatively, the secondary user can harvest RF energy for data transmission if the channel is occupied. The optimal channel selection policy of the secondary user can be obtained by formulating a Markov decision process (MDP) problem. We present some numerical results obtained by solving this MDP problem.
Swar The Voice Operated PC
Venue: arXiv cs.HC 2014
Year: 2014

Keyboard, although a popular medium, is not very convenient as it requires a certain amount of skill for effective usage. A mouse on the other hand requires a good hand-eye co-ordination. Also current computer interfaces also assume a certain level of literacy from the user. It also expect the user to have certain level of proficiency in English. In our country where the literacy level is as low as 50% in some states, if information technology has to reach the grass root level; these constraints have to be eliminated. As a solution for these, Speech Recognition and hence the concept of Voice operated computer system comes into picture. In this paper we propose a technique to develop a voice recognition system which will be used for controlling computer via speech input from any user i.e. without the use of mouse and / or keyboard. Once developed this system would be of great benefit to physically handicapped people as Instead of scrolling through written procedures on a laptop or handheld computer, they can wear a headset and have their hands and eyes free.
Full-Duplex Transceiver System Calculations: Analysis of ADC and Linearity Challenges
Venue: arXiv cs.IT 2014
Year: 2014

Despite the intensive recent research on wireless single-channel full-duplex communications, relatively little is known about the transceiver chain nonidealities of full-duplex devices. In this paper, the effect of nonlinear distortion occurring in the transmitter power amplifier (PA) and the receiver chain is analyzed, alongside with the dynamic range requirements of analog-to-digital converters (ADCs). This is done with detailed system calculations, which combine the properties of the individual electronics components to jointly model the complete transceiver chain, including self-interference cancellation. They also quantify the decrease in the dynamic range for the signal of interest caused by self-interference at the analog-to-digital interface. Using these system calculations, we provide comprehensive numerical results for typical transceiver parameters. The analytical results are also confirmed with full waveform simulations. We observe that the nonlinear distortion produced by the transmitter PA is a significant issue in a full-duplex transceiver and, when using cheaper and less linear components, also the receiver chain nonlinearities become considerable. It is also shown that, with digitally-intensive self-interference cancellation, the quantization noise of the ADCs is another significant problem.
Accelerating SystemVerilog UVM Based VIP to Improve Methodology for Verification of Image Signal Processing Designs Using HW Emulator
Venue: arXiv cs.OH 2014
Year: 2014

In this paper we present the development of Acceleratable UVCs from standard UVCs in SystemVerilog and their usage in UVM based Verification Environment of Image Signal Processing designs to increase run time performance. This paper covers development of Acceleratable UVCs from standard UVCs for internal control and data buses of ST imaging group by partitioning of transaction-level components and cycle-accurate signal-level components between the software simulator and hardware accelerator respectively. Standard Co-Emulation API: Modeling Interface (SCE-MI) compliant, transaction-level communications link between test benches running on a host system and Emulation machine is established. Accelerated Verification IPs are used at UVM based Verification Environment of Image Signal Processing designs both with simulator and emulator as UVM acceleration is an extension of the standard simulation-only UVM and is fully backward compatible with it. Acceleratable UVCs significantly reduces development schedule risks while leveraging transaction models used during simulation. In this paper, we discuss our experiences on UVM based methodology adoption on TestBench-Xpress(TBX) based technology step by step. We are also doing comparison between the run time performance results from earlier simulator-only environment and the new, hardware-accelerated environment. Although this paper focuses on Acceleratable UVCs development and their usage for image signal processing designs, Same concept can be extended for non-image signal processing designs. KEYWORDS- SystemVerilog, Universal Verification Methodology (UVM), TestBench-Xpress (TBX), Universal Verification Component (UVC), Standard Co-Emulation API: Modelling Interface (SCE-MI), Acceleratable UVC, Emulator, XRTL Tasks/Functions (xtf), Transactor interface (tif), Verification IP (VIP).
Equivalent Codes, Optimality, and Performance Analysis of OSTBC: Textbook Study
Venue: arXiv cs.IT 2014
Year: 2014

An equivalent model for a multi-input multi-output (MIMO) communication system with orthogonal space-time block codes (OSTBCs) is proposed based on a newly revealed connection between OSTBCs and Euclidean codes. Examples of distance spectra, signal constellations, and signal coordinate diagrams of Euclidean codes equivalent to simplest OSTBCs are given. A new asymptotic upper bound for the symbol error rate (SER) of OSTBCs, based on the distance spectra of the introduced equivalent Euclidean codes is derived, and new general design criteria for signal constellations of the optimal OSTBC are proposed. Some bounds relating distance properties, dimensionality, and cardinality of OSTBCs with constituent signals of equal energy are given, and new optimal signal constellations with cardinalities M = 8 and M = 16 for Alamouti's code are designed. Using the new model for MIMO communication systems with OSTBCs, a general methodology for performance analysis of OSTBCs is developed. As an example of the application of this methodology, an exact evaluation of the SER of any OSTBC is given. Namely, a new expression for the SER of Alamouti's OSTBC with binary phase shift keying (BPSK) signals is derived.
Service-oriented Communities: Visions and Contributions towards Social Organizations
Venue: arXiv cs.CY 2014
Year: 2014

With the increase of the populations, resources are becoming scarcer, and a smarter way to make use of them becomes a vital necessity of our societies. On the other hand, resource management is traditionally carried out through well established organizations, policies, and regulations that are often considered as impossible to restructure. Our position is that merely expanding the traditional approaches might not be enough. Systems must be radically rethought in order to achieve a truly effective and rational use of the available resources. Classical concepts such as demand and supply need to be rethought as well, as they operate artificial classifications that limit the true potential of systems and organizations. In what follows we propose our vision to future, "smarter" systems able to overcome the limitations of the status quo. Such systems require what Boulding called "gestalts," namely concepts able to "directing research towards the gaps which they reveal". In this paper we elaborate on this and show how such gestalts can pave the way towards novel reformulations of traditional services able to reach a better and more sensible management of the available resources and cope with their scarcity. Our vision of a Service-oriented Community is also introduced. We believe that such communities---in heterarchical coexistence with traditional systems---provide the necessary diversity and innovation orientation to prevent societal lock-ins such as the ones we are experiencing in assisting our elderly ones.
Testing Equivalence of Polynomials under Shifts
Venue: arXiv cs.CC 2014
Year: 2014

Two polynomials $f, g \in \mathbb{F}[x_1, \ldots, x_n]$ are called shift-equivalent if there exists a vector $(a_1, \ldots, a_n) \in \mathbb{F}^n$ such that the polynomial identity $f(x_1+a_1, \ldots, x_n+a_n) \equiv g(x_1,\ldots,x_n)$ holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our algorithm runs in time polynomial in the circuit size of the polynomials, to which it is given black box access. This complements a previous work of Grigoriev (Theoretical Computer Science, 1997) who gave a deterministic algorithm running in time $n^{O(d)}$ for degree $d$ polynomials. Our algorithm uses randomness only to solve instances of the Polynomial Identity Testing (PIT) problem. Hence, if one could de-randomize PIT (a long-standing open problem in complexity) a de-randomization of our algorithm would follow. This establishes an equivalence between de-randomizing shift-equivalence testing and de-randomizing PIT (both in the black-box and the white-box setting). For certain restricted models, such as Read Once Branching Programs, we already obtain a deterministic algorithm using existing PIT results.
Large Alphabet Compression and Predictive Distributions through Poissonization and Tilting
Venue: arXiv cs.IT 2014
Year: 2014

This paper introduces a convenient strategy for coding and predicting sequences of independent, identically distributed random variables generated from a large alphabet of size $m$. In particular, the size of the sample is allowed to be variable. The employment of a Poisson model and tilting method simplifies the implementation and analysis through independence. The resulting strategy is optimal within the class of distributions satisfying a moment condition, and is close to optimal for the class of all i.i.d distributions on strings of a given length. Moreover, the method can be used to code and predict strings with a condition on the tail of the ordered counts. It can also be applied to distributions in an envelope class.
Adaptive Link Selection Strategies for Distributed Estimation in Wireless Sensor Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we propose adaptive link selection strategies for distributed estimation in diffusion-type wireless networks. We develop an exhaustive search-based link selection algorithm and a sparsity-inspired link selection algorithm that can exploit the topology of networks with poor-quality links. In the exhaustive search-based algorithm, we choose the set of neighbors that results in the smallest excess mean square error (EMSE) for a specific node. In the sparsity-inspired link selection algorithm, a convex regularization is introduced to devise a sparsity-inspired link selection algorithm. The proposed algorithms have the ability to equip diffusion-type wireless networks and to significantly improve their performance. Simulation results illustrate that the proposed algorithms have lower EMSE values, a better convergence rate and significantly improve the network performance when compared with existing methods.
An Information-Spectrum Approach to Weak Variable-Length Source Coding with Side-Information
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies variable-length (VL) source coding of general sources with side-information. Novel one-shot coding theorems for coding with common side-information available at the encoder and the decoder and Slepian- Wolf (SW) coding (i.e., with side-information only at the decoder) are given, and then, are applied to asymptotic analyses of these coding problems. Especially, a general formula for the infimum of the coding rate asymptotically achievable by weak VL-SW coding (i.e., VL-SW coding with vanishing error probability) is derived. Further, the general formula is applied to investigating weak VL-SW coding of mixed sources. Our results derive and extend several known results on SW coding and weak VL coding, e.g., the optimal achievable rate of VL-SW coding for mixture of i.i.d. sources is given for countably infinite alphabet case with mild condition. In addition, the usefulness of the encoder side-information is investigated. Our result shows that if the encoder side-information is useless in weak VL coding then it is also useless even in the case where the error probability may be positive asymptotically.
Reasoning About the Transfer of Control
Venue: arXiv cs.AI 2014
Year: 2014

We present DCL-PC: a logic for reasoning about how the abilities of agents and coalitions of agents are altered by transferring control from one agent to another. The logical foundation of DCL-PC is CL-PC, a logic for reasoning about cooperation in which the abilities of agents and coalitions of agents stem from a distribution of atomic Boolean variables to individual agents -- the choices available to a coalition correspond to assignments to the variables the coalition controls. The basic modal constructs of DCL-PC are of the form coalition C can cooperate to bring about phi. DCL-PC extends CL-PC with dynamic logic modalities in which atomic programs are of the form agent i gives control of variable p to agent j; as usual in dynamic logic, these atomic programs may be combined using sequence, iteration, choice, and test operators to form complex programs. By combining such dynamic transfer programs with cooperation modalities, it becomes possible to reason about how the power of agents and coalitions is affected by the transfer of control. We give two alternative semantics for the logic: a direct semantics, in which we capture the distributions of Boolean variables to agents; and a more conventional Kripke semantics. We prove that these semantics are equivalent, and then present an axiomatization for the logic. We investigate the computational complexity of model checking and satisfiability for DCL-PC, and show that both problems are PSPACE-complete (and hence no worse than the underlying logic CL-PC). Finally, we investigate the characterisation of control in DCL-PC. We distinguish between first-order control -- the ability of an agent or coalition to control some state of affairs through the assignment of values to the variables under the control of the agent or coalition -- and second-order control -- the ability of an agent to exert control over the control that other agents have by transferring variables to other agents. We give a logical characterisation of second-order control.
Efficient Planning under Uncertainty with Macro-actions
Venue: arXiv cs.AI 2014
Year: 2014

Deciding how to act in partially observable environments remains an active area of research. Identifying good sequences of decisions is particularly challenging when good control performance requires planning multiple steps into the future in domains with many states. Towards addressing this challenge, we present an online, forward-search algorithm called the Posterior Belief Distribution (PBD). PBD leverages a novel method for calculating the posterior distribution over beliefs that result after a sequence of actions is taken, given the set of observation sequences that could be received during this process. This method allows us to efficiently evaluate the expected reward of a sequence of primitive actions, which we refer to as macro-actions. We present a formal analysis of our approach, and examine its performance on two very large simulation experiments: scientific exploration and a target monitoring domain. We also demonstrate our algorithm being used to control a real robotic helicopter in a target monitoring experiment, which suggests that our approach has practical potential for planning in real-world, large partially observable domains where a multi-step lookahead is required to achieve good performance.
Mixed Strategies in Combinatorial Agency
Venue: arXiv cs.GT 2014
Year: 2014

In many multiagent domains a set of agents exert effort towards a joint outcome, yet the individual effort levels cannot be easily observed. A typical example for such a scenario is routing in communication networks, where the sender can only observe whether the packet reached its destination, but often has no information about the actions of the intermediate routers, which influences the final outcome. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a basic combinatorial agency model for this setting, where the principal is restricted to inducing a pure Nash equilibrium. Here we study various implications of this restriction. First, we show that, in contrast to the case of observable efforts, inducing a mixed-strategies equilibrium may be beneficial for the principal. Second, we present a sufficient condition for technologies for which no gain can be generated. Third, we bound the principals gain for various families of technologies. Finally, we study the robustness of mixed equilibria to coalitional deviations and the computational hardness of the optimal mixed equilibria.