OpenRaiser/Intern-Atlas huggingface dataset:
Context Awarw Mobile Initiated Handoff for Performance Improvement in IEEE 802.11 Networks
Venue: arXiv cs.NI 2011
Year: 2011

IEEE 802.11 is a widely used wireless LAN standard which offers a good bandwidth at low cost In an ESS, multiple APs can co-exist with overlapping coverage area. A mobile node connects to the AP from which it receives the best signal. Changes in traffic to and from different MNs occur over time. Load imbalance may develop on different APs. Throughput and delay of the different flows passing through the APs, where the load has increased beyond certain limit, may degrade. Different MNs associated to the overloaded APs will experience performance degradation. Overall performance of the ESS will also drop. In this paper we propose a scheme where MNs experiencing degraded performance will initiate action and with assistance from the associate AP perform handoff to less loaded AP within its range to improve performance.
A Survey of Routing Attacks and Security Measures in Mobile Ad-Hoc Networks
Venue: arXiv cs.NI 2011
Year: 2011

Mobile ad hoc networks (MANETs) are a set of mobile nodes which are self-configuring and connected by wireless links automatically as per the defined routing protocol. The absence of a central management agency or a fixed infrastructure is a key feature of MANETs. These nodes communicate with each other by interchange of packets, which for those nodes not in wireless range goes hop by hop. Due to lack of a defined central authority, securitizing the routing process becomes a challenging task thereby leaving MANETs vulnerable to attacks, which results in deterioration in the performance characteristics as well as raises a serious question mark about the reliability of such networks. In this paper we have attempted to present an overview of the routing protocols, the known routing attacks and the proposed countermeasures to these attacks in various works.
Transmission Control of Two-User Slotted ALOHA Over Gilbert-Elliott Channel: Stability and Delay Analysis
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider the problem of calculating the stability region and average delay of two user slotted ALOHA over a Gilbert-Elliott channel, where users have channel state information and adapt their transmission probabilities according to the channel state. Each channel has two states, namely, the 'good' and 'bad' states. In the 'bad' state, the channel is assumed to be in deep fade and the transmission fails with probability one, while in the 'good' state, there is some positive success probability. We calculate the Stability region with and without Multipacket Reception capability as well as the average delay without MPR. Our results show that the stability region of the controlled S-ALOHA is always a superset of the stability region of uncontrolled S-ALOHA. Moreover, if the channel tends to be in the 'bad' state for long proportion of time, then the stability region is a convex Polyhedron strictly containing the TDMA stability region and the optimal transmission strategy is to transmit with probability one whenever the nodes have packets and it is shown that this strategy is delay optimal. On the other hand, if the channel tends to be in the 'good' state more often, then the stability region is bounded by a convex curve and is strict subset of the TDMA stability region. We also show that enhancing the physical layer by allowing MPR capability can significantly enhance the performance while simplifying the MAC Layer design by the lack of the need of scheduling under some conditions. Furthermore, it is shown that transmission control not only allows handling higher stable arrival rates but also leads to lower delay for the same arrival rate compared with ordinary S-ALOHA.
Robot Networks with Homonyms: The Case of Patterns Formation
Venue: arXiv cs.DC 2011
Year: 2011

In this paper, we consider the problem of formation of a series of geometric patterns [4] by a network of oblivious mobile robots that communicate only through vision. So far, the problem has been studied in models where robots are either assumed to have distinct identifiers or to be completely anonymous. To generalize these results and to better understand how anonymity affects the computational power of robots, we study the problem in a new model, introduced recently in [5], in which n robots may share up to 1 <= h <= n different identifiers. We present necessary and sufficient conditions, relating symmetricity and homonymy, that makes the problem solvable. We also show that in the case where h = n, making the identifiers of robots invisible does not limit their computational power. This contradicts a result of [4]. To present our algorithms, we use a function that computes the Weber point for many regular and symmetric configurations. This function is interesting in its own right, since the problem of finding Weber points has been solved up to now for only few other patterns.
Noncoherent SIMO Pre-Log via Resolution of Singularities
Venue: arXiv cs.IT 2011
Year: 2011

We establish a lower bound on the noncoherent capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel. Our result holds for arbitrary rank Q of the channel correlation matrix, arbitrary block-length L > Q, and arbitrary number of receive antennas R, and includes the result in Morgenshtern et al. (2010) as a special case. It is well known that the capacity pre-log for this channel in the single-input single-output (SISO) case is given by 1-Q/L, where Q/L is the penalty incurred by channel uncertainty. Our result reveals that this penalty can be reduced to 1/L by adding only one receive antenna, provided that L \geq 2Q - 1 and the channel correlation matrix satisfies mild technical conditions. The main technical tool used to prove our result is Hironaka's celebrated theorem on resolution of singularities in algebraic geometry.
Level of Presence in Team-Building Activities: Gaming Component in Virtual Environments
Venue: arXiv cs.HC 2011
Year: 2011

Historically the training of teams has been implemented using a face-to-face approach. In the past decade, on-line multiuser virtual environments have offered a solution for training teams whose members are geographically dispersed. In order to develop on effective team training activity, a high sense of presence among the participant needs to be reached. Previous research studies reported being able to reach a high level of presence even when using inexpensive technology such as laptop and headset. This study evaluates the level of presence of ten subjects who have to perform a team-building activity in a multi-user virtual environment using a laptop computer and a headset. The authors are interested in determining which user characterizes, such as gender, age and knowledge of computers, have a strong correlation with the level of sense of presence. The results of this study showed that female participants were more likely to engage in the activity and perceived fewer negative effects. Participants who reported less negative effects such as feeling tired, dizzy, or experiencing eye strain during the team-building activity reached a higher level of sense of presence.
How Many Transmit Antennas to Use in a MIMO Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

The problem of finding the optimal number of data streams to transmit in a multi-user MIMO scenario, where both the transmitters and receivers are equipped with multiple antennas is considered. Without channel state information at any transmitter, with a zero-forcing receiver each user is shown to transmit a single data stream to maximize its own outage capacity in the presence of sufficient number of users. Transmitting a single data stream is also shown to be optimal in terms of maximizing the sum of the outage capacities in the presence of sufficient number of users.
Generic Traces and Constraints, GenTra4CP revisited
Venue: arXiv cs.LO 2011
Year: 2011

The generic trace format GenTra4CP has been defined in 2004 with the goal of becoming a standard trace format for the observation of constraint solvers over finite domains. It has not been used since. This paper defines the concept of generic trace formally, based on simple transformations of traces. It then analyzes, and occasionally corrects, shortcomings of the proposed initial format and shows the interest that a generic tracer may bring to develop portable applications or to standardization efforts, in particular in the field of constraints.
Multiterminal Source Coding with an Entropy-Based Distortion Measure
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider a class of multiterminal source coding problems, each subject to distortion constraints computed using a specific, entropy-based, distortion measure. We provide the achievable rate distortion region for two cases and, in so doing, we demonstrate a relationship between the lossy multiterminal source coding problems with our specific distortion measure and (1) the canonical Slepian-Wolf lossless distributed source coding network, and (2) the Ahlswede-Körner-Wyner source coding with side information problem in which only one of the sources is recovered losslessly.
Modeling and Information Rates for Synchronization Error Channels
Venue: arXiv cs.IT 2011
Year: 2011

We propose a new channel model for channels with synchronization errors. Using this model, we give simple, non-trivial and, in some cases, tight lower bounds on the capacity for certain synchronization error channels.
The BG-simulation for Byzantine Mobile Robots
Venue: arXiv cs.DC 2011
Year: 2011

This paper investigates the task solvability of mobile robot systems subject to Byzantine faults. We first consider the gathering problem, which requires all robots to meet in finite time at a non-predefined location. It is known that the solvability of Byzantine gathering strongly depends on a number of system attributes, such as synchrony, the number of Byzantine robots, scheduling strategy, obliviousness, orientation of local coordinate systems and so on. However, the complete characterization of the attributes making Byzantine gathering solvable still remains open. In this paper, we show strong impossibility results of Byzantine gathering. Namely, we prove that Byzantine gathering is impossible even if we assume one Byzantine fault, an atomic execution system, the n-bounded centralized scheduler, non-oblivious robots, instantaneous movements and a common orientation of local coordinate systems (where n denote the number of correct robots). Those hypotheses are much weaker than used in previous work, inducing a much stronger impossibility result. At the core of our impossibility result is a reduction from the distributed consensus problem in asynchronous shared-memory systems. In more details, we newly construct a generic reduction scheme based on the distributed BG-simulation. Interestingly, because of its versatility, we can easily extend our impossibility result for general pattern formation problems.
Using Lotkaian Informetrics for Ranking in Digital Libraries
Venue: arXiv cs.IR 2011
Year: 2011

The purpose of this paper is to propose the use of models, theories and laws in bibliometrics and scientometrics to enhance information retrieval processes, especially ranking. A common pattern in many man-made data sets is Lotka's Law which follows the well-known power-law distributions. These informetric distributions can be used to give an alternative order to large and scattered result sets and can be applied as a new ranking mechanism. The polyrepresentation of information in Digital Library systems is used to enhance the retrieval quality, to overcome the drawbacks of the typical term-based ranking approaches and to enable users to explore retrieved document sets from a different perspective.
Markov Localization for Mobile Robots in Dynamic Environments
Venue: arXiv cs.AI 2011
Year: 2011

Localization, that is the estimation of a robot's location from sensor data, is a fundamental problem in mobile robotics. This papers presents a version of Markov localization which provides accurate position estimates and which is tailored towards dynamic environments. The key idea of Markov localization is to maintain a probability density over the space of all locations of a robot in its environment. Our approach represents this space metrically, using a fine-grained grid to approximate densities. It is able to globally localize the robot from scratch and to recover from localization failures. It is robust to approximate models of the environment (such as occupancy grid maps) and noisy sensors (such as ultrasound sensors). Our approach also includes a filtering technique which allows a mobile robot to reliably estimate its position even in densely populated environments in which crowds of people block the robot's sensors for extended periods of time. The method described here has been implemented and tested in several real-world applications of mobile robots, including the deployments of two mobile robots as interactive museum tour-guides.
The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics
Venue: arXiv cs.AI 2011
Year: 2011

We study the complexity of the combination of the Description Logics ALCQ and ALCQI with a terminological formalism based on cardinality restrictions on concepts. These combinations can naturally be embedded into C^2, the two variable fragment of predicate logic with counting quantifiers, which yields decidability in NExpTime. We show that this approach leads to an optimal solution for ALCQI, as ALCQI with cardinality restrictions has the same complexity as C^2 (NExpTime-complete). In contrast, we show that for ALCQ, the problem can be solved in ExpTime. This result is obtained by a reduction of reasoning with cardinality restrictions to reasoning with the (in general weaker) terminological formalism of general axioms for ALCQ extended with nominals. Using the same reduction, we show that, for the extension of ALCQI with nominals, reasoning with general axioms is a NExpTime-complete problem. Finally, we sharpen this result and show that pure concept satisfiability for ALCQI with nominals is NExpTime-complete. Without nominals, this problem is known to be PSpace-complete.
Nonapproximability Results for Partially Observable Markov Decision Processes
Venue: arXiv cs.AI 2011
Year: 2011

We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don't have guarantees of finding policies within a constant factor or a constant summand of optimal. Here "unlikely" means "unless some complexity classes collapse," where the collapses considered are P=NP, P=PSPACE, or P=EXP. Until or unless these collapses are shown to hold, any control-policy designer must choose between such performance guarantees and efficient computation.
A Model of Inductive Bias Learning
Venue: arXiv cs.AI 2011
Year: 2011

A major problem in machine learning is that of inductive bias: how to choose a learner's hypothesis space so that it is large enough to contain a solution to the problem being learnt, yet small enough to ensure reliable generalization from reasonably-sized training sets. Typically such bias is supplied by hand through the skill and insights of experts. In this paper a model for automatically learning bias is investigated. The central assumption of the model is that the learner is embedded within an environment of related learning tasks. Within such an environment the learner can sample from multiple tasks, and hence it can search for a hypothesis space that contains good solutions to many of the problems in the environment. Under certain restrictions on the set of all hypothesis spaces available to the learner, we show that a hypothesis space that performs well on a sufficiently large number of training tasks will also perform well when learning novel tasks in the same environment. Explicit bounds are also derived demonstrating that learning multiple tasks within an environment of related tasks can potentially give much better generalization than learning a single task.
Partial-Order Planning with Concurrent Interacting Actions
Venue: arXiv cs.AI 2011
Year: 2011

In order to generate plans for agents with multiple actuators, agent teams, or distributed controllers, we must be able to represent and plan using concurrent actions with interacting effects. This has historically been considered a challenging task requiring a temporal planner with the ability to reason explicitly about time. We show that with simple modifications, the STRIPS action representation language can be used to represent interacting actions. Moreover, algorithms for partial-order planning require only small modifications in order to be applied in such multiagent domains. We demonstrate this fact by developing a sound and complete partial-order planner for planning with concurrent interacting actions, POMP, that extends existing partial-order planners in a straightforward way. These results open the way to the use of partial-order planners for the centralized control of cooperative multiagent systems.
Planning by Rewriting
Venue: arXiv cs.AI 2011
Year: 2011

Domain-independent planning is a hard combinatorial problem. Taking into account plan quality makes the task even more difficult. This article introduces Planning by Rewriting (PbR), a new paradigm for efficient high-quality domain-independent planning. PbR exploits declarative plan-rewriting rules and efficient local search techniques to transform an easy-to-generate, but possibly suboptimal, initial plan into a high-quality plan. In addition to addressing the issues of planning efficiency and plan quality, this framework offers a new anytime planning algorithm. We have implemented this planner and applied it to several existing domains. The experimental results show that the PbR approach provides significant savings in planning effort while generating high-quality plans.
Conformant Planning via Symbolic Model Checking
Venue: arXiv cs.AI 2011
Year: 2011

We tackle the problem of planning in nondeterministic domains, by presenting a new approach to conformant planning. Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal despite the nondeterminism of the domain. Our approach is based on the representation of the planning domain as a finite state automaton. We use Symbolic Model Checking techniques, in particular Binary Decision Diagrams, to compactly represent and efficiently search the automaton. In this paper we make the following contributions. First, we present a general planning algorithm for conformant planning, which applies to fully nondeterministic domains, with uncertainty in the initial condition and in action effects. The algorithm is based on a breadth-first, backward search, and returns conformant plans of minimal length, if a solution to the planning problem exists, otherwise it terminates concluding that the problem admits no conformant solution. Second, we provide a symbolic representation of the search space based on Binary Decision Diagrams (BDDs), which is the basis for search techniques derived from symbolic model checking. The symbolic representation makes it possible to analyze potentially large sets of states and transitions in a single computation step, thus providing for an efficient implementation. Third, we present CMBP (Conformant Model Based Planner), an efficient implementation of the data structures and algorithm described above, directly based on BDD manipulations, which allows for a compact representation of the search layers and an efficient implementation of the search steps. Finally, we present an experimental comparison of our approach with the state-of-the-art conformant planners CGP, QBFPLAN and GPT. Our analysis includes all the planning problems from the distribution packages of these systems, plus other problems defined to stress a number of specific factors. Our approach appears to be the most effective: CMBP is strictly more expressive than QBFPLAN and CGP and, in all the problems where a comparison is possible, CMBP outperforms its competitors, sometimes by orders of magnitude.
The GRT Planning System: Backward Heuristic Construction in Forward State-Space Planning
Venue: arXiv cs.AI 2011
Year: 2011

This paper presents GRT, a domain-independent heuristic planning system for STRIPS worlds. GRT solves problems in two phases. In the pre-processing phase, it estimates the distance between each fact and the goals of the problem, in a backward direction. Then, in the search phase, these estimates are used in order to further estimate the distance between each intermediate state and the goals, guiding so the search process in a forward direction and on a best-first basis. The paper presents the benefits from the adoption of opposite directions between the preprocessing and the search phases, discusses some difficulties that arise in the pre-processing phase and introduces techniques to cope with them. Moreover, it presents several methods of improving the efficiency of the heuristic, by enriching the representation and by reducing the size of the problem. Finally, a method of overcoming local optimal states, based on domain axioms, is proposed. According to it, difficult problems are decomposed into easier sub-problems that have to be solved sequentially. The performance results from various domains, including those of the recent planning competitions, show that GRT is among the fastest planners.
Quantum-Like Uncertain Conditionals for Text Analysis
Venue: arXiv cs.CL 2011
Year: 2011

Simple representations of documents based on the occurrences of terms are ubiquitous in areas like Information Retrieval, and also frequent in Natural Language Processing. In this work we propose a logical-probabilistic approach to the analysis of natural language text based in the concept of Uncertain Conditional, on top of a formulation of lexical measurements inspired in the theoretical concept of ideal quantum measurements. The proposed concept can be used for generating topic-specific representations of text, aiming to match in a simple way the perception of a user with a pre-established idea of what the usage of terms in the text should be. A simple example is developed with two versions of a text in two languages, showing how regularities in the use of terms are detected and easily represented.
Physarum Can Compute Shortest Paths
Venue: arXiv cs.DS 2011
Year: 2011

Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0 - s1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by the biologists and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years.