OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part I: Nash Equilibria
Venue: arXiv cs.IT 2007
Year: 2007

In this two-parts paper we propose a decentralized strategy, based on a game-theoretic formulation, to find out the optimal precoding/multiplexing matrices for a multipoint-to-multipoint communication system composed of a set of wideband links sharing the same physical resources, i.e., time and bandwidth. We assume, as optimality criterion, the achievement of a Nash equilibrium and consider two alternative optimization problems: 1) the competitive maximization of mutual information on each link, given constraints on the transmit power and on the spectral mask imposed by the radio spectrum regulatory bodies; and 2) the competitive maximization of the transmission rate, using finite order constellations, under the same constraints as above, plus a constraint on the average error probability. In Part I of the paper, we start by showing that the solution set of both noncooperative games is always nonempty and contains only pure strategies. Then, we prove that the optimal precoding/multiplexing scheme for both games leads to a channel diagonalizing structure, so that both matrix-valued problems can be recast in a simpler unified vector power control game, with no performance penalty. Thus, we study this simpler game and derive sufficient conditions ensuring the uniqueness of the Nash equilibrium. Interestingly, although derived under stronger constraints, incorporating for example spectral mask constraints, our uniqueness conditions have broader validity than previously known conditions. Finally, we assess the goodness of the proposed decentralized strategy by comparing its performance with the performance of a Pareto-optimal centralized scheme. To reach the Nash equilibria of the game, in Part II, we propose alternative distributed algorithms, along with their convergence conditions.
Where are Bottlenecks in NK Fitness Landscapes?
Venue: arXiv cs.NE 2007
Year: 2007

Usually the offspring-parent fitness correlation is used to visualize and analyze some caracteristics of fitness landscapes such as evolvability. In this paper, we introduce a more general representation of this correlation, the Fitness Cloud (FC). We use the bottleneck metaphor to emphasise fitness levels in landscape that cause local search process to slow down. For a local search heuristic such as hill-climbing or simulated annealing, FC allows to visualize bottleneck and neutrality of landscapes. To confirm the relevance of the FC representation we show where the bottlenecks are in the well-know NK fitness landscape and also how to use neutrality information from the FC to combine some neutral operator with local search heuristic.
Sphere Lower Bound for Rotated Lattice Constellations in Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

We study the error probability performance of rotated lattice constellations in frequency-flat Nakagami-$m$ block-fading channels. In particular, we use the sphere lower bound on the underlying infinite lattice as a performance benchmark. We show that the sphere lower bound has full diversity. We observe that optimally rotated lattices with largest known minimum product distance perform very close to the lower bound, while the ensemble of random rotations is shown to lack diversity and perform far from it.
How to use the Scuba Diving metaphor to solve problem with neutrality ?
Venue: arXiv cs.NE 2007
Year: 2007

We proposed a new search heuristic using the scuba diving metaphor. This approach is based on the concept of evolvability and tends to exploit neutrality which exists in many real-world problems. Despite the fact that natural evolution does not directly select for evolvability, the basic idea behind the scuba search heuristic is to explicitly push evolvability to increase. A comparative study of the scuba algorithm and standard local search heuristics has shown the advantage and the limitation of the scuba search. In order to tune neutrality, we use the NKq fitness landscapes and a family of travelling salesman problems (TSP) where cities are randomly placed on a lattice and where travel distance between cities is computed with the Manhattan metric. In this last problem the amount of neutrality varies with the city concentration on the grid ; assuming the concentration below one, this TSP reasonably remains a NP-hard problem.
DIANA Scheduling Hierarchies for Optimizing Bulk Job Scheduling
Venue: arXiv cs.DC 2007
Year: 2007

The use of meta-schedulers for resource management in large-scale distributed systems often leads to a hierarchy of schedulers. In this paper, we discuss why existing meta-scheduling hierarchies are sometimes not sufficient for Grid systems due to their inability to re-organise jobs already scheduled locally. Such a job re-organisation is required to adapt to evolving loads which are common in heavily used Grid infrastructures. We propose a peer-to-peer scheduling model and evaluate it using case studies and mathematical modelling. We detail the DIANA (Data Intensive and Network Aware) scheduling algorithm and its queue management system for coping with the load distribution and for supporting bulk job scheduling. We demonstrate that such a system is beneficial for dynamic, distributed and self-organizing resource management and can assist in optimizing load or job distribution in complex Grid infrastructures.
The Cyborg Astrobiologist: Porting from a wearable computer to the Astrobiology Phone-cam
Venue: arXiv cs.CV 2007
Year: 2007

We have used a simple camera phone to significantly improve an `exploration system' for astrobiology and geology. This camera phone will make it much easier to develop and test computer-vision algorithms for future planetary exploration. We envision that the `Astrobiology Phone-cam' exploration system can be fruitfully used in other problem domains as well.
Projection semantics for rigid loops
Venue: arXiv cs.PL 2007
Year: 2007

A rigid loop is a for-loop with a counter not accessible to the loop body or any other part of a program. Special instructions for rigid loops are introduced on top of the syntax of the program algebra PGA. Two different semantic projections are provided and proven equivalent. One of these is taken to have definitional status on the basis of two criteria: `normative semantic adequacy' and `indicative algorithmic adequacy'.
Sorting and Selection in Posets
Venue: arXiv cs.DS 2007
Year: 2007

Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study a more general setting, in which some pairs of objects are incomparable. This generalization is relevant in applications related to rankings in sports, college admissions, or conference submissions. It also has potential applications in biology, such as comparing the evolutionary fitness of different strains of bacteria, or understanding input-output relations among a set of metabolic reactions or the causal influences among a set of interacting genes or proteins. Our results improve and extend results from two decades ago of Faigle and Turán. A measure of complexity of a partially ordered set (poset) is its width. Our algorithms obtain information about a poset by queries that compare two elements. We present an algorithm that sorts, i.e. completely identifies, a width w poset of size n and has query complexity O(wn + nlog(n)), which is within a constant factor of the information-theoretic lower bound. We also show that a variant of Mergesort has query complexity O(wn(log(n/w))) and total complexity O((w^2)nlog(n/w)). Faigle and Turán have shown that the sorting problem has query complexity O(wn(log(n/w))) but did not address its total complexity. For the related problem of determining the minimal elements of a poset, we give efficient deterministic and randomized algorithms with O(wn) query and total complexity, along with matching lower bounds for the query complexity up to a factor of 2. We generalize these results to the k-selection problem of determining the elements of height at most k. We also derive upper bounds on the total complexity of some other problems of a similar flavor.
Interface groups and financial transfer architectures
Venue: arXiv cs.SE 2007
Year: 2007

Analytic execution architectures have been proposed by the same authors as a means to conceptualize the cooperation between heterogeneous collectives of components such as programs, threads, states and services. Interface groups have been proposed as a means to formalize interface information concerning analytic execution architectures. These concepts are adapted to organization architectures with a focus on financial transfers. Interface groups (and monoids) now provide a technique to combine interface elements into interfaces with the flexibility to distinguish between directions of flow dependent on entity naming. The main principle exploiting interface groups is that when composing a closed system of a collection of interacting components, the sum of their interfaces must vanish in the interface group modulo reflection. This certainly matters for financial transfer interfaces. As an example of this, we specify an interface group and within it some specific interfaces concerning the financial transfer architecture for a part of our local academic organization. Financial transfer interface groups arise as a special case of more general service architecture interfaces.
The Kinematics of Manipulators Built From Closed Planar Mechanisms
Venue: arXiv cs.RO 2007
Year: 2007

The paper discusses the kinematics of manipulators builts of planar closed kinematic chains. A special kinematic scheme is extracted from the array of these mechanisms that looks the most promising for the creation of different types of robotic manipulators. The structural features of this manipulator determine a number of its original properties that essentially simplify its control. These features allow the main control problems to be effectively overcome by application of the simple kinematic problems. The workspace and singular configurations of a basic planar manipulator are studied. By using a graphic simulation method, motions of the designed mechanism are examined. A prototype of this mechanism was implemented to verify the proposed approach.
Generalized Solution Concepts in Games with Possibly Unaware Players
Venue: arXiv cs.GT 2007
Year: 2007

Most work in game theory assumes that players are perfect reasoners and have common knowledge of all significant aspects of the game. In earlier work, we proposed a framework for representing and analyzing games with possibly unaware players, and suggested a generalization of Nash equilibrium appropriate for games with unaware players that we called generalized Nash equilibrium. Here, we use this framework to analyze other solution concepts that have been considered in the game-theory literature, with a focus on sequential equilibrium. We also provide some insight into the notion of generalized Nash equilibrium by proving that it is closely related to the notion of rationalizability when we restrict the analysis to games in normal form and no unawareness is involved.
A note on minimal matching covered graphs
Venue: arXiv cs.DM 2007
Year: 2007

A graph is called matching covered if for its every edge there is a maximum matching containing it. It is shown that minimal matching covered graphs contain a perfect matching.
Moveability and Collision Analysis for Fully-Parallel Manipulators
Venue: arXiv cs.RO 2007
Year: 2007

The aim of this paper is to characterize the moveability of fully-parallel manipulators in the presence of obstacles. Fully parallel manipulators are used in applications where accuracy, stiffness or high speeds and accelerations are required \cite{Merlet:97}. However, one of its main drawbacks is a relatively small workspace compared to the one of serial manipulators. This is due mainly to the existence of potential internal collisions, and the existence of singularities. In this paper, the notion of free aspect is defined which permits to exhibit domains of the workspace and the joint space free of singularity and collision. The main application of this study is the moveability analysis in the workspace of the manipulator as well as path-planning, control and design.
Conception Isotropique D'Une Morphologie ParallÈle : Application à L'Usinage
Venue: arXiv cs.RO 2007
Year: 2007

The aim of this paper is the isotropic design of a hybrid morphology dedicated to 3-axis machining applications. It is necessary to ensure the feasibility of continuous, singularity-free trajectories, as well as a good manipulability in position and velocity. We want to propose an alternative design to conventional serial machine-tools. We compare a serial PPP machine-tool (three prismatic orthogonal axes) with a hybrid architecture which we optimize only the first two axes. The critrerion used for the optimization is the conditioning of the Jacobian matrices. The optimum, namely isotropy, can be obtained which provides our architecture with excellent manipulability properties.
Benefit of Delay on the Diversity-Multiplexing Tradeoffs of MIMO Channels with Partial CSI
Venue: arXiv cs.IT 2007
Year: 2007

This paper re-examines the well-known fundamental tradeoffs between rate and reliability for the multi-antenna, block Rayleigh fading channel in the high signal to noise ratio (SNR) regime when (i) the transmitter has access to (noiseless) one bit per coherence-interval of causal channel state information (CSI) and (ii) soft decoding delays together with worst-case delay guarantees are acceptable. A key finding of this work is that substantial improvements in reliability can be realized with a very short expected delay and a slightly longer (but bounded) worst-case decoding delay guarantee in communication systems where the transmitter has access to even one bit per coherence interval of causal CSI. While similar in spirit to the recent work on communication systems based on automatic repeat requests (ARQ) where decoding failure is known at the transmitter and leads to re-transmission, here transmit side-information is purely based on CSI. The findings reported here also lend further support to an emerging understanding that decoding delay (related to throughput) and codeword blocklength (related to coding complexity and delays) are distinctly different design parameters which can be tuned to control reliability.
Design of a Spherical Wrist with Parallel Architecture: Application to Vertebrae of an Eel Robot
Venue: arXiv cs.RO 2007
Year: 2007

The design of a spherical wrist with parallel architecture is the object of this article. This study is part of a larger project, which aims to design and to build an eel robot for inspection of immersed piping. The kinematic analysis of the mechanism is presented first to characterize the singular configurations as well as the isotropic configurations. We add the design constraints related to the application, such as (i) the compactness of the mechanism, (ii) the symmetry of the elements in order to ensure static and dynamic balance and (iii) the possibility of the mechanism to fill the elliptic form of the ell sections.
Multiple-Description Lattice Vector Quantization
Venue: arXiv cs.IT 2007
Year: 2007

In this thesis, we construct and analyze multiple-description codes based on lattice vector quantization.
Animation of virtual mannequins, robot-like simulation or motion captures
Venue: arXiv cs.RO 2007
Year: 2007

In order to optimize the costs and time of design of the new products while improving their quality, concurrent engineering is based on the digital model of these products, the numerical model. However, in order to be able to avoid definitively physical model, old support of the design, without loss of information, new tools must be available. Especially, a tool making it possible to check simply and quickly the maintainability of complex mechanical sets using the numerical model is necessary. Since one decade, our team works on the creation of tool for the generation and the analysis of trajectories of virtual mannequins. The simulation of human tasks can be carried out either by robot-like simulation or by simulation by motion capture. This paper presents some results on the both two methods. The first method is based on a multi-agent system and on a digital mock-up technology, to assess an efficient path planner for a manikin or a robot for access and visibility task taking into account ergonomic constraints or joint and mechanical limits. In order to solve this problem, the human operator is integrated in the process optimization to contribute to a global perception of the environment. This operator cooperates, in real-time, with several automatic local elementary agents. In the case of the second approach, we worked with the CEA and EADS/CCR to solve the constraints related to the evolution of human virtual in its environment on the basis of data resulting from motion capture system. An approach using of the virtual guides was developed to allow to the user the realization of precise trajectory in absence of force feedback. The result of this work validates solutions through the digital mock-up; it can be applied to simulate maintenability and mountability tasks.
Optimal Design of Ad Hoc Injection Networks by Using Genetic Algorithms
Venue: arXiv cs.NE 2007
Year: 2007

This work aims at optimizing injection networks, which consist in adding a set of long-range links (called bypass links) in mobile multi-hop ad hoc networks so as to improve connectivity and overcome network partitioning. To this end, we rely on small-world network properties, that comprise a high clustering coefficient and a low characteristic path length. We investigate the use of two genetic algorithms (generational and steady-state) to optimize three instances of this topology control problem and present results that show initial evidence of their capacity to solve it.
Separable and Low-Rank Continuous Games
Venue: arXiv cs.GT 2007
Year: 2007

In this paper, we study nonzero-sum separable games, which are continuous games whose payoffs take a sum-of-products form. Included in this subclass are all finite games and polynomial games. We investigate the structure of equilibria in separable games. We show that these games admit finitely supported Nash equilibria. Motivated by the bounds on the supports of mixed equilibria in two-player finite games in terms of the ranks of the payoff matrices, we define the notion of the rank of an n-player continuous game and use this to provide bounds on the cardinality of the support of equilibrium strategies. We present a general characterization theorem that states that a continuous game has finite rank if and only if it is separable. Using our rank results, we present an efficient algorithm for computing approximate equilibria of two-player separable games with fixed strategy spaces in time polynomial in the rank of the game.
e-Science initiatives in Venezuela
Venue: arXiv cs.CE 2007
Year: 2007

Within the context of the nascent e-Science infrastructure in Venezuela, we describe several web-based scientific applications developed at the Centro Nacional de Calculo Cientifico Universidad de Los Andes (CeCalCULA), Merida, and at the Instituto Venezolano de Investigaciones Cientificas (IVIC), Caracas. The different strategies that have been followed for implementing quantum chemistry and atomic physics applications are presented. We also briefly discuss a damage portal based on dynamic, nonlinear, finite elements of lumped damage mechanics and a biomedical portal developed within the framework of the \textit{E-Infrastructure shared between Europe and Latin America} (EELA) initiative for searching common sequences and inferring their functions in parasitic diseases such as leishmaniasis, chagas and malaria.
Balanced Virtual Humans Interacting with their Environment
Venue: arXiv cs.RO 2007
Year: 2007

The animation of human avatars seems very successful; the computer graphics industry shows outstanding results in films everyday, the game industry achieves exploits... Nevertheless, the animation and control processes of such manikins are very painful. It takes days to a specialist to build such animated sequences, and it is not adaptive to any type of modifications. Our main purpose is the virtual human for engineering, especially virtual prototyping. As for this domain of activity, such amounts of time are prohibitive.
Virtual reality: A human centered tool for improving Manufacturing
Venue: arXiv cs.RO 2007
Year: 2007

Manufacturing is using Virtual Reality tools to enhance the product life cycle. Their definitions are still in flux and it is necessary to define their connections. Thus, firstly, we will introduce more closely some definitions where we will find that, if the Virtual manufacturing concepts originate from machining operations and evolve in this manufacturing area, there exist a lot of applications in different fields such as casting, forging, sheet metalworking and robotics (mechanisms). From the recent projects in Europe or in USA, we notice that the human perception or the simulation of mannequin is more and more needed in both fields. In this context, we have isolated some applications as ergonomic studies, assembly and maintenance simulation, design or training where the virtual reality tools can be applied. Thus, we find out a family of applications where the virtual reality tools give the engineers the main role in the optimization process. We will illustrate our paper by several examples where virtual reality interfaces are used and combined with optimization tools as multi-agent systems.
A New Six Degree-of-Freedom Haptic Device based on the Orthoglide and the Agile Eye
Venue: arXiv cs.RO 2007
Year: 2007

The aim of this paper is to present a new six degree-of-freedom (dof) haptic device using two parallel mechanisms. The first one, called orthoglide, provides the translation motions and the second one produces the rotational motions. These two motions are decoupled to simplify the direct and inverse kinematics, as it is needed for real-times control. To reduce the inertial load, the motors are fixed on the base and a transmission with two universal joints is used to transmit the rotational motions from the base to the end-effector. The main feature of the orthoglide and of the agile eye mechanism is the existence of an isotropic configuration. The length of the legs and the range limits of the orthoglide are optimized to have homogeneous performance throughout the Cartesian workspace, which has a nearly cubic workspace. These properties permit to have a high stiffness throughout the workspace and workspace limits that are easily understandable by the user.
The Computation of All 4R Serial Spherical Wrists With an Isotropic Architecture
Venue: arXiv cs.RO 2007
Year: 2007

A spherical wrist of the serial type is said to be isotropic if it can attain a posture whereby the singular values of its Jacobian matrix are all identical and nonzero. What isotropy brings about is robustness to manufacturing, assembly, and measurement errors, thereby guaranteeing a maximum orientation accuracy. In this paper we investigate the existence of redundant isotropic architectures, which should add to the dexterity of the wrist under design by virtue of its extra degree of freedom. The problem formulation leads to a system of eight quadratic equations with eight unknowns. The Bezout number of this system is thus 2^8 = 256, its BKK bound being 192. However, the actual number of solutions is shown to be 32. We list all solutions of the foregoing algebraic problem. All these solutions are real, but distinct solutions do not necessarily lead to distinct manipulators. Upon discarding those algebraic solutions that yield no new wrists, we end up with exactly eight distinct architectures, the eight corresponding manipulators being displayed at their isotropic posture.