OpenRaiser/Intern-Atlas huggingface dataset:
On the Kinetostatic Optimization of Revolute-Coupled Planar Manipulators
Venue: arXiv cs.RO 2007
Year: 2007

Proposed in this paper is a kinetostatic performance index for the optimum dimensioning of planar manipulators of the serial type. The index is based on the concept of distance of the underlying Jacobian matrix to a given isotropic matrix that is used as a reference model for purposes of performance evaluation. Applications of the index fall in the realm of design, but control applications are outlined. The paper focuses on planar manipulators, the basic concepts being currently extended to their three-dimensional counterparts.
Kinematic Calibration of the Orthoglide-Type Mechanisms
Venue: arXiv cs.RO 2007
Year: 2007

The paper proposes a novel calibration approach for the Orthoglide-type mechanisms based on observations of the manipulator leg parallelism during motions between the prespecified test postures. It employs a low-cost measuring system composed of standard comparator indicators attached to the universal magnetic stands. They are sequentially used for measuring the deviation of the relevant leg location while the manipulator moves the TCP along the Cartesian axes. Using the measured differences, the developed algorithm estimates the joint offsets that are treated as the most essential parameters to be adjusted. The sensitivity of the measurement methods and the calibration accuracy are also studied. Experimental results are presented that demonstrate validity of the proposed calibration technique.
Diversity-Multiplexing Tradeoff via Asymptotic Analysis of Large MIMO Systems
Venue: arXiv cs.IT 2007
Year: 2007

Diversity-multiplexing tradeoff (DMT) presents a compact framework to compare various MIMO systems and channels in terms of the two main advantages they provide (i.e. high data rate and/or low error rate). This tradeoff was characterized asymptotically (SNR-> infinity) for i.i.d. Rayleigh fading channel by Zheng and Tse [1]. The asymptotic DMT overestimates the finite-SNR one [2]. In this paper, using the recent results on the asymptotic (in the number of antennas) outage capacity distribution, we derive and analyze the finite-SNR DMT for a broad class of channels (not necessarily Rayleigh fading). Based on this, we give the convergence conditions for the asymptotic DMT to be approached by the finite-SNR one. The multiplexing gain definition is shown to affect critically the convergence point: when the multiplexing gain is defined via the mean (ergodic) capacity, the convergence takes place at realistic SNR values. Furthermore, in this case the diversity gain can also be used to estimate the outage probability with reasonable accuracy. The multiplexing gain definition via the high-SNR asymptote of the mean capacity (as in [1]) results in very slow convergence for moderate to large systems (as 1/ln(SNR)^2) and, hence, the asymptotic DMT cannot be used at realistic SNR values. For this definition, the high-SNR threshold increases exponentially in the number of antennas and in the multiplexing gain. For correlated keyhole channel, the diversity gain is shown to decrease with correlation and power imbalance of the channel. While the SNR-asymptotic DMT of Zheng and Tse does not capture this effect, the size-asymptotic DMT does.
Realistic Rendering of Kinetostatic Indices of Mechanisms
Venue: arXiv cs.RO 2007
Year: 2007

The work presented in this paper is related to the use of a haptic device in an environment of robotic simulation. Such device introduces a new approach to feel and to understand the boundaries of the workspace of mechanisms as well as its kinetostatic properties. Indeed, these concepts are abstract and thus often difficult to understand for the end-users. To catch his attention, we propose to amplify the problems of the mechanisms in order to help him to take the good decisions.
Decision tree modeling with relational views
Venue: arXiv cs.DB 2007
Year: 2007

Data mining is a useful decision support technique that can be used to discover production rules in warehouses or corporate data. Data mining research has made much effort to apply various mining algorithms efficiently on large databases. However, a serious problem in their practical application is the long processing time of such algorithms. Nowadays, one of the key challenges is to integrate data mining methods within the framework of traditional database systems. Indeed, such implementations can take advantage of the efficiency provided by SQL engines. In this paper, we propose an integrating approach for decision trees within a classical database system. In other words, we try to discover knowledge from relational databases, in the form of production rules, via a procedure embedding SQL queries. The obtained decision tree is defined by successive, related relational views. Each view corresponds to a given population in the underlying decision tree. We selected the classical Induction Decision Tree (ID3) algorithm to build the decision tree. To prove that our implementation of ID3 works properly, we successfully compared the output of our procedure with the output of an existing and validated data mining software, SIPINA. Furthermore, since our approach is tuneable, it can be generalized to any other similar decision tree-based method.
Unfolding Manhattan Towers
Venue: arXiv cs.CG 2007
Year: 2007

We provide an algorithm for unfolding the surface of any orthogonal polyhedron that falls into a particular shape class we call Manhattan Towers, to a nonoverlapping planar orthogonal polygon. The algorithm cuts along edges of a 4x5x1 refinement of the vertex grid.
Evolutionary Optimisation Methods for Template Based Image Registration
Venue: arXiv cs.CE 2007
Year: 2007

This paper investigates the use of evolutionary optimisation techniques to register a template with a scene image. An error function is created to measure the correspondence of the template to the image. The problem presented here is to optimise the horizontal, vertical and scaling parameters that register the template with the scene. The Genetic Algorithm, Simulated Annealing and Particle Swarm Optimisations are compared to a Nelder-Mead Simplex optimisation with starting points chosen in a pre-processing stage. The paper investigates the precision and accuracy of each method and shows that all four methods perform favourably for image registration. SA is the most precise, GA is the most accurate. PSO is a good mix of both and the Simplex method returns local minima the most. A pre-processing stage should be investigated for the evolutionary methods in order to improve performance. Discrete versions of the optimisation methods should be investigated to further improve computational performance.
Capacity of Underspread Noncoherent WSSUS Fading Channels under Peak Signal Constraints
Venue: arXiv cs.IT 2007
Year: 2007

We characterize the capacity of the general class of noncoherent underspread wide-sense stationary uncorrelated scattering (WSSUS) time-frequency-selective Rayleigh fading channels, under peak constraints in time and frequency and in time only. Capacity upper and lower bounds are found which are explicit in the channel's scattering function and allow to identify the capacity-maximizing bandwidth for a given scattering function and a given peak-to-average power ratio.
Scalability and Optimisation of a Committee of Agents Using Genetic Algorithm
Venue: arXiv cs.MA 2007
Year: 2007

A population of committees of agents that learn by using neural networks is implemented to simulate the stock market. Each committee of agents, which is regarded as a player in a game, is optimised by continually adapting the architecture of the agents using genetic algorithms. The committees of agents buy and sell stocks by following this procedure: (1) obtain the current price of stocks; (2) predict the future price of stocks; (3) and for a given price trade until all the players are mutually satisfied. The trading of stocks is conducted by following these rules: (1) if a player expects an increase in price then it tries to buy the stock; (2) else if it expects a drop in the price, it sells the stock; (3)and the order in which a player participates in the game is random. The proposed procedure is implemented to simulate trading of three stocks, namely, the Dow Jones, the Nasdaq and the S&P 500. A linear relationship between the number of players and agents versus the computational time to run the complete simulation is observed. It is also found that no player has a monopolistic advantage.
Energy-Efficient Resource Allocation in Wireless Networks: An Overview of Game-Theoretic Approaches
Venue: arXiv cs.IT 2007
Year: 2007

An overview of game-theoretic approaches to energy-efficient resource allocation in wireless networks is presented. Focusing on multiple-access networks, it is demonstrated that game theory can be used as an effective tool to study resource allocation in wireless networks with quality-of-service (QoS) constraints. A family of non-cooperative (distributed) games is presented in which each user seeks to choose a strategy that maximizes its own utility while satisfying its QoS requirements. The utility function considered here measures the number of reliable bits that are transmitted per joule of energy consumed and, hence, is particulary suitable for energy-constrained networks. The actions available to each user in trying to maximize its own utility are at least the choice of the transmit power and, depending on the situation, the user may also be able to choose its transmission rate, modulation, packet size, multiuser receiver, multi-antenna processing algorithm, or carrier allocation strategy. The best-response strategy and Nash equilibrium for each game is presented. Using this game-theoretic framework, the effects of power control, rate control, modulation, temporal and spatial signal processing, carrier allocation strategy and delay QoS constraints on energy efficiency and network capacity are quantified.
Random Linear Network Coding: A free cipher?
Venue: arXiv cs.IT 2007
Year: 2007

We consider the level of information security provided by random linear network coding in network scenarios in which all nodes comply with the communication protocols yet are assumed to be potential eavesdroppers (i.e. "nice but curious"). For this setup, which differs from wiretapping scenarios considered previously, we develop a natural algebraic security criterion, and prove several of its key properties. A preliminary analysis of the impact of network topology on the overall network coding security, in particular for complete directed acyclic graphs, is also included.
Double Sided Watermark Embedding and Detection with Perceptual Analysis
Venue: arXiv cs.MM 2007
Year: 2007

In our previous work, we introduced a double-sided technique that utilizes but not reject the host interference. Due to its nice property of utilizing but not rejecting the host interference, it has a big advantage over the host interference schemes in that the perceptual analysis can be easily implemented for our scheme to achieve the locally bounded maximum embedding strength. Thus, in this work, we detail how to implement the perceptual analysis in our double-sided schemes since the perceptual analysis is very important for improving the fidelity of watermarked contents. Through the extensive performance comparisons, we can further validate the performance advantage of our double-sided schemes.
Mean Field Models of Message Throughput in Dynamic Peer-to-Peer Systems
Venue: arXiv cs.DC 2007
Year: 2007

The churn rate of a peer-to-peer system places direct limitations on the rate at which messages can be effectively communicated to a group of peers. These limitations are independent of the topology and message transmission latency. In this paper we consider a peer-to-peer network, based on the Engset model, where peers arrive and depart independently at random. We show how the arrival and departure rates directly limit the capacity for message streams to be broadcast to all other peers, by deriving mean field models that accurately describe the system behavior. Our models cover the unit and more general k buffer cases, i.e. where a peer can buffer at most k messages at any one time, and we give results for both single and multi-source message streams. We define coverage rate as peer-messages per unit time, i.e. the rate at which a number of peers receive messages, and show that the coverage rate is limited by the churn rate and buffer size. Our theory introduces an Instantaneous Message Exchange (IME) model and provides a template for further analysis of more complicated systems. Using the IME model, and assuming random processes, we have obtained very accurate equations of the system dynamics in a variety of interesting cases, that allow us to tune a peer-to-peer system. It remains to be seen if we can maintain this accuracy for general processes and when applying a non-instantaneous model.
On the Information Rate of MIMO Systems with Finite Rate Channel State Feedback and Power On/Off Strategy
Venue: arXiv cs.IT 2007
Year: 2007

This paper quantifies the information rate of multiple-input multiple-output (MIMO) systems with finite rate channel state feedback and power on/off strategy. In power on/off strategy, a beamforming vector (beam) is either turned on (denoted by on-beam) with a constant power or turned off. We prove that the ratio of the optimal number of on-beams and the number of antennas converges to a constant for a given signal-to-noise ratio (SNR) when the number of transmit and receive antennas approaches infinity simultaneously and when beamforming is perfect. Based on this result, a near optimal strategy, i.e., power on/off strategy with a constant number of on-beams, is discussed. For such a strategy, we propose the power efficiency factor to quantify the effect of imperfect beamforming. A formula is proposed to compute the maximum power efficiency factor achievable given a feedback rate. The information rate of the overall MIMO system can be approximated by combining the asymptotic results and the formula for power efficiency factor. Simulations show that this approximation is accurate for all SNR regimes.
On-Line Condition Monitoring using Computational Intelligence
Venue: arXiv cs.AI 2007
Year: 2007

This paper presents bushing condition monitoring frameworks that use multi-layer perceptrons (MLP), radial basis functions (RBF) and support vector machines (SVM) classifiers. The first level of the framework determines if the bushing is faulty or not while the second level determines the type of fault. The diagnostic gases in the bushings are analyzed using the dissolve gas analysis. MLP gives superior performance in terms of accuracy and training time than SVM and RBF. In addition, an on-line bushing condition monitoring approach, which is able to adapt to newly acquired data are introduced. This approach is able to accommodate new classes that are introduced by incoming data and is implemented using an incremental learning algorithm that uses MLP. The testing results improved from 67.5% to 95.8% as new data were introduced and the testing results improved from 60% to 95.3% as new conditions were introduced. On average the confidence value of the framework on its decision was 0.92.
Statistical Mechanics of Nonlinear On-line Learning for Ensemble Teachers
Venue: arXiv cs.LG 2007
Year: 2007

We analyze the generalization performance of a student in a model composed of nonlinear perceptrons: a true teacher, ensemble teachers, and the student. We calculate the generalization error of the student analytically or numerically using statistical mechanics in the framework of on-line learning. We treat two well-known learning rules: Hebbian learning and perceptron learning. As a result, it is proven that the nonlinear model shows qualitatively different behaviors from the linear model. Moreover, it is clarified that Hebbian learning and perceptron learning show qualitatively different behaviors from each other. In Hebbian learning, we can analytically obtain the solutions. In this case, the generalization error monotonically decreases. The steady value of the generalization error is independent of the learning rate. The larger the number of teachers is and the more variety the ensemble teachers have, the smaller the generalization error is. In perceptron learning, we have to numerically obtain the solutions. In this case, the dynamical behaviors of the generalization error are non-monotonic. The smaller the learning rate is, the larger the number of teachers is; and the more variety the ensemble teachers have, the smaller the minimum value of the generalization error is.
Improved Approximability Result for Test Set with Small Redundancy
Venue: arXiv cs.DS 2007
Year: 2007

Test set with redundancy is one of the focuses in recent bioinformatics research. Set cover greedy algorithm (SGA for short) is a commonly used algorithm for test set with redundancy. This paper proves that the approximation ratio of SGA can be $(2-\frac{1}{2r})\ln n+{3/2}\ln r+O(\ln\ln n)$ by using the potential function technique. This result is better than the approximation ratio $2\ln n$ which directly derives from set multicover, when $r=o(\frac{\ln n}{\ln\ln n})$, and is an extension of the approximability results for plain test set.
Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) in hypre and PETSc
Venue: arXiv cs.MS 2007
Year: 2007

We describe our software package Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) publicly released recently. BLOPEX is available as a stand-alone serial library, as an external package to PETSc (``Portable, Extensible Toolkit for Scientific Computation'', a general purpose suite of tools for the scalable solution of partial differential equations and related problems developed by Argonne National Laboratory), and is also built into {\it hypre} (``High Performance Preconditioners'', scalable linear solvers package developed by Lawrence Livermore National Laboratory). The present BLOPEX release includes only one solver--the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) method for symmetric eigenvalue problems. {\it hypre} provides users with advanced high-quality parallel preconditioners for linear systems, in particular, with domain decomposition and multigrid preconditioners. With BLOPEX, the same preconditioners can now be efficiently used for symmetric eigenvalue problems. PETSc facilitates the integration of independently developed application modules with strict attention to component interoperability, and makes BLOPEX extremely easy to compile and use with preconditioners that are available via PETSc. We present the LOBPCG algorithm in BLOPEX for {\it hypre} and PETSc. We demonstrate numerically the scalability of BLOPEX by testing it on a number of distributed and shared memory parallel systems, including a Beowulf system, SUN Fire 880, an AMD dual-core Opteron workstation, and IBM BlueGene/L supercomputer, using PETSc domain decomposition and {\it hypre} multigrid preconditioning. We test BLOPEX on a model problem, the standard 7-point finite-difference approximation of the 3-D Laplacian, with the problem size in the range $10^5-10^8$.
Computability of simple games: A characterization and application to the core
Venue: arXiv cs.GT 2007
Year: 2007

The class of algorithmically computable simple games (i) includes the class of games that have finite carriers and (ii) is included in the class of games that have finite winning coalitions. This paper characterizes computable games, strengthens the earlier result that computable games violate anonymity, and gives examples showing that the above inclusions are strict. It also extends Nakamura's theorem about the nonemptyness of the core and shows that computable games have a finite Nakamura number, implying that the number of alternatives that the players can deal with rationally is restricted.
Acyclicity of Preferences, Nash Equilibria, and Subgame Perfect Equilibria: a Formal and Constructive Equivalence
Venue: arXiv cs.DM 2007
Year: 2007

In 1953, Kuhn showed that every sequential game has a Nash equilibrium by showing that a procedure, named ``backward induction'' in game theory, yields a Nash equilibrium. It actually yields Nash equilibria that define a proper subclass of Nash equilibria. In 1965, Selten named this proper subclass subgame perfect equilibria. In game theory, payoffs are rewards usually granted at the end of a game. Although traditional game theory mainly focuses on real-valued payoffs that are implicitly ordered by the usual total order over the reals, works of Simon or Blackwell already involved partially ordered payoffs. This paper generalises the notion of sequential game by replacing real-valued payoff functions with abstract atomic objects, called outcomes, and by replacing the usual total order over the reals with arbitrary binary relations over outcomes, called preferences. This introduces a general abstract formalism where Nash equilibrium, subgame perfect equilibrium, and ``backward induction'' can still be defined. This paper proves that the following three propositions are equivalent: 1) Preferences over the outcomes are acyclic. 2) Every sequential game has a Nash equilibrium. 3) Every sequential game has a subgame perfect equilibrium. The result is fully computer-certified using Coq. Beside the additional guarantee of correctness, the activity of formalisation using Coq also helps clearly identify the useful definitions and the main articulations of the proof.
Linear Tabling Strategies and Optimizations
Venue: arXiv cs.PL 2007
Year: 2007

Recently, the iterative approach named linear tabling has received considerable attention because of its simplicity, ease of implementation, and good space efficiency. Linear tabling is a framework from which different methods can be derived based on the strategies used in handling looping subgoals. One decision concerns when answers are consumed and returned. This paper describes two strategies, namely, {\it lazy} and {\it eager} strategies, and compares them both qualitatively and quantitatively. The results indicate that, while the lazy strategy has good locality and is well suited for finding all solutions, the eager strategy is comparable in speed with the lazy strategy and is well suited for programs with cuts. Linear tabling relies on depth-first iterative deepening rather than suspension to compute fixpoints. Each cluster of inter-dependent subgoals as represented by a top-most looping subgoal is iteratively evaluated until no subgoal in it can produce any new answers. Naive re-evaluation of all looping subgoals, albeit simple, may be computationally unacceptable. In this paper, we also introduce semi-naive optimization, an effective technique employed in bottom-up evaluation of logic programs to avoid redundant joins of answers, into linear tabling. We give the conditions for the technique to be safe (i.e. sound and complete) and propose an optimization technique called {\it early answer promotion} to enhance its effectiveness. Benchmarking in B-Prolog demonstrates that with this optimization linear tabling compares favorably well in speed with the state-of-the-art implementation of SLG.