Center-configuration selection technique for the reconfigurable modular robot

The reconfigurable modular robot has an enormous amount of configurations to adapt to various environments and tasks. It greatly increases the complexity of configuration research in that the possible configuration number of the reconfigurable modular robot grows exponentially with the increase of module number. Being the initial configuration or the basic configuration of the reconfigurable robot, the center-configuration plays a crucial role in system’s actual applications. In this paper, a novel center-configuration selection technique has been proposed for reconfigurable modular robots. Based on the similarities between configurations’ transformation and graph theory, configuration network has been applied in the modeling and analyzing of these configurations. Configuration adjacency matrix, reconfirmation cost matrix, and center-configuration coefficient have been defined for the configuration network correspondingly. Being similar to the center-location problem, the center configuration has been selected according to the largest center-configuration coefficient. As an example of the reconfigurable robotic system, AMOEBA-I, a three-module reconfigurable robot with nine configurations which was developed in Shenyang Institute of Automation (SIA), Chinese Academy of Sciences (CAS), has been introduced briefly. According to the numerical simulation result, the center-configuration coefficients for these nine configurations have been calculated and compared to validate this technique. Lastly, a center-configuration selection example is provided with consideration of the adjacent configurations. The center-configuration selection technique proposed in this paper is also available to other reconfigurable modular robots. Supported in part by the National High-Technology 863 Program (Grant No. 2001AA422360), the Chinese Academy of Sciences Advanced Manufacturing Technology R&D Base Fund (Grant Nos. A050104 and F050108), and the GUCAS-BHP Billiton Scholarship     

Configuration representation and reconfiguration optimization for the reconfigurable robots with independent manipulation

Single module of the reconfigurable robots with independent manipulation can perform the actions of locomotion and manipulation. In conformity with the request for achieving autonomous operation in the unstructurized environment instead of fixed operation in the structurized environment, these robots are applied in the complicated and dangerous environment. The existing researches on the configuration theory focus on the reconfigurable robots with limited locomotion and the ones with independent locomotion, not being applicable to the reconfigurable robots with independent manipulation. The vector configuration is put forward, the research content of which contains the topology and locomotion direction of configuration, the posture and orientation and connection relation between modules. Module state vector and configuration state matrix are proposed for representation methodology for the swarm configuration of these reconfigurable robots, which supports transformation operation to represent and trigger behavior motion of the module and reconfiguration between configurations. Optimization algorithm of assembly reconfiguration applying workload as the optimization target is presented, as well as optimization algorithm of transformation reconfiguration applying the integration of posture orientation workload and connection workload. The result of optimization is the relation of state transformation between the initial configuration and the object one as the basic of reconfiguration plan and control. Supported by the National High-Tech Research and Development Program of China (Grant No. 2006AA04Z254) and the Scientific Research Fund for Doctor of Liaoning Provice (Grant No. 20071007)     

Programming for modular reconfigurable robots

Composed of multiple modular robotic units, self-reconfigurable modular robots are metamorphic systems that can autonomously rearrange the modules and form different configurations depending on dynamic environments and tasks. The goal of self-reconfiguration is to determine how to change connectivity of modules to transform the robot from the current configuration to the goal configuration subject to restrictions of physical implementation. The existing reconfiguration algorithms use different methods, such as divide-and-conquer, graph matching, and the like, to reduce the reconfiguration cost. However, an optimal solution with a minimal number of reconfiguration steps has not been found yet. The optimal reconfiguration planning problem consists in finding the least number of reconfiguration steps transforming the robot from one configuration to another. This is an NP-complete problem. In this paper, we describe an approach to solve this problem. The approach is based on constructing logical models of the problem under study.     

Lifting scheme of symmetric tight wavelets frames

This paper proposes a method to realize the lifting scheme of tight frame wavelet filters. As for 4-channel tight frame wavelet filter, the tight frame transforms＇ matrix is 2×4, but the lifting scheme transforms＇ matrix must be 4×4. And in the case of 3-channel tight frame wavelet filter, the transforms＇ matrix is 2×3, but the lifting scheme transforms＇ matrix must be 3×3. In order to solve this problem, we introduce two concepts： transferred polyphase matrix for 4-channel filters and transferred unitary matrix for 3-channel filters. The transferred polyphase matrix is symmetric/antisymmetric. Thus, we use this advantage to realize the lifting scheme.     

Design of a multimode beamforming network based on the scattering matrix analysis

The investigation of the multimode beamforming network (BFN) has been developed from its scattering matrix (S-matrix) analysis. A substrate integrated waveguide (SIW) BFN is designed and fabricated on a single Rogers 5880 substrate. This device is not only marked by features of conventional BFN, such as Butler matrix, but also has additional benefits, e.g. more compact configuration and higher radiation efficiency. Measured and simulated results based on the proposed structure are in a good agreement, which indicates that this novel type of BFN has good characteristics and presents an excellent candidate in the development of intelligent microwave and millimeter-wave multibeam antenna systems. Supported by the National Natural Science Foundation of China (Grant No. 60621002), the National High-Tech Research & Development Program of China (Grant No. 2007AA01Z2B4), and the Scientific Research Foundation of Graduate School of Southeast University     

Self-Repairing Algorithm of Lattice-Type Self-Reconfigurable Modular Robots

Self-reconfigurable modular robots consist of many identical modules. By changing the connections among modules, the configuration of the robot can be transformed into other configurations. For the self-reconfigurable modular robot, one of its main functions is its self-repairing ability. First, the module of the lattice-type self-reconfigurable robot is presented. It is composed of a central cube and six rotary arms. On each rotary arm the docking mechanism is designed to show the self-repairing ability. Second, the basic motion of the self-reconfigurable robot is described to change the positions of the module. The state matrix and the location matrix are proposed to describe the connection states. Third, a self-repairing algorithm based on the positions of the faulty modules is presented. The algorithm applies the Breadth-First-Search method and the Depth-First-Search method to find a locomotion path by which the faulty module is ejected and replaced by a spare module. At last, a simulation on the fourth-order lattice-type self-reconfigurable robot consisting of 729 modules shows the feasibility and effectiveness of this self-repairing algorithm in three dimensions.     

Efficient approach and application of the Green’s functions in spatial domain in multilayered media

Based on the dipole source method, all components of the Green＇s functions in spectral domain are restructured concisely by four basis functions, and in terms of the two-level discrete complex image method （DCIM） with the high order Sommerfeld identities, an efficient algorithm for closed-form Green＇s functions in spatial domain in multilayered media is presented. This new work enjoys the advantages of the surface wave pole extraction directly carried out by the generalized integral path without troubles of that all components of Green＇s function in spectral domain should be reformed respectively in transmission line network analogy, and then the Green＇s functions for mixed-potential integral equation （MPIE） analysis in both near-field and far-field in multilayered media are obtained. In addition, the curl operator for coupled field in MPIE is avoided conveniently. It is especially applicable and useful to characterize the electromagnetic scattering by, and radiation in the presence of, the electrically large 3-D objects in multilayered media. The numerical results of the S-parameters of a microstrip periodic bandgap （PBG） filter, the radar cross section （RCS） of a large microstrip antenna array, the characteristics of scattering, and radiation from the three-dimensional （3-D） targets in multilayered media are obtained, to demonstrate better effectiveness and accuracy of this technique.     

Accurate evaluation of Green’s functions in a layered medium by SDP-FLAM

Based on local Taylor expansions on the complex plane, a method for fast locating all modes (FLAM) of spectral-domain Green’s Functions in a planar layered medium is developed in this paper. SDP-FLAM, a combination of FLAM with the steepest descent path algorithm (SDP), is employed to accurately evaluate the spatial-domain Green’s functions in a layered medium. According to the theory of complex analysis, the relationship among the poles, branch points and Riemann sheets is also analyzed rigorously. To inverse the Green’s functions from spectral to spatial domain, SDP-FLAM method and discrete complex image method (DCIM) are applied to the non-near field region and the near filed region, respectively. The significant advantage of SDP-FLAM lies in its capability of calculating Green’s functions in a layered medium of moderate thickness with loss or without loss. Some numerical examples are presented to validate SDP-FLAM method. Supported by the National Natural Science Foundation of China (Grant No. 60621002), and the State Key Development Program for Basic Research of China (Grant No. 2009CB320200)     

Adaptive blind separation of underdetermined mixtures based on sparse component analysis

The independence priori is very often used in the conventional blind source separation （BSS）. Naturally, independent component analysis （ICA） is also employed to perform BSS very often. However, ICA is difficult to use in some challenging cases, such as underdetermined BSS or blind separation of dependent sources. Recently, sparse component analysis （SCA） has attained much attention because it is theoretically available for underdetermined BSS and even for blind dependent source separation sometimes. However, SCA has not been developed very sufficiently. Up to now, there are only few existing algorithms and they are also not perfect as well in practice. For example, although Lewicki-Sejnowski＇s natural gradient for SCA is superior to K-mean clustering, it is just an approximation without rigorously theoretical basis. To overcome these problems, a new natural gradient formula is proposed in this paper. This formula is derived directly from the cost function of SCA through matrix theory. Mathematically, it is more rigorous. In addition, a new and robust adaptive BSS algorithm is developed based on the new natural gradient. Simulations illustrate that this natural gradient formula is more robust and reliable than Lewicki-Sejnowski＇s gradient.     

SNR estimation algorithm based on the preamble for wireless OFDM systems

Based on the analysis of the performance of Boumard＇s SNR method for wireless orthogonal frequency division multiplexing （OFDM） systems, a new estimation algorithm of the noise variance is proposed by only using the data samples of the two training symbols in the preamble, and the second order moment of these data samples is employed to estimate the signal power. The average SNR and the SNRs on the subchannels can all be estimated by the proposed algorithm, and its performance is independent of the channel＇s frequency selectivity. Simulation results show that the performance of the proposed method is highly improved and much better than that of Boumard＇s method.     

On detection performance and system configuration of MIMO radar

Multiple-input multiple-output (MIMO) radar is a new concept with some new characteristics, such as multiple orthogonal waveforms and omnidirectional coverage. Based on Stein’s lemma, we use relative entropy as a precise and general measure of error exponent to study detection performance for both MIMO radar and phased array radar. And based on derived analytical results, we further study the system configuration problem of Bistatic MIMO radar systems, where transmitters and receivers are located in different positions. Some interesting results are presented. For phased array radar, when the total numbers of transmitters and receivers are fixed, we should alwaysmake the number of transmitters equal to the number of receivers. For MIMO radar, we should use a small number of transmitters in low signal noise ratio (SNR) region, and make the number of transmitters equal to the number of receivers in high SNR region. These results are instructive for deployment of bistatic MIMO radar systems in the future. Supported in part by the National Natural Science Foundation of China (Grant No. 60602048), in part by aviation science funds of China (Grant No. 20060112118), and in part by the National Ministry Foundation of China (Grant No. 20094010040)     

模块化机器人拓扑重构规划研究

模块化可重构机器人由若干个相同的机器人模块组合装配而成,能够重构成不同的几何形态和结构,从而适应不同的作业任务要求。本论文主要对树状拓扑结构的模块化机器人的重构规划问题进行了研究,定义了构型重构的基本概念,提出了分支重构规划算法。这类模块化可重构机器人可以用树状拓扑结构图来描述。机器人的拓扑结构从自由树转化为有根树,然后分解为若干个分支结构,并按一定顺序排列,通过对各个分支结构的逐步比较和操作,完成重构过程。最后选定模块数目,进行了重构规划过程的仿真计算。结果表明,文中所述算法对于树状拓扑结构的模块化机器人的重构规划问题是有效的。     

A novel strong tracking finite-difference extended Kalman filter for nonlinear eye tracking

Non-intrusive methods for eye tracking are important for many applications of vision-based human computer interaction. However, due to the high nonlinearity of eye motion, how to ensure the robustness of external interference and accuracy of eye tracking poses the primary obstacle to the integration of eye movements into todays’s interfaces. In this paper, we present a strong tracking finite-difference extended Kalman filter algorithm, aiming to overcome the difficulty in modeling nonlinear eye tracking. In filtering calculation, strong tracking factor is introduced to modify a priori covariance matrix and improve the accuracy of the filter. The filter uses finite-difference method to calculate partial derivatives of nonlinear functions for eye tracking. The latest experimental results show the validity of our method for eye tracking under realistic conditions. Supported by the National Natural Science Foundation of China (Grant No. 60572027), the Outstanding Young Researchers Foundation of Sichuan Province (Grant No. 03ZQ026-033), the Program for New Century Excellent Talents in University of China (Grant No. NCET-05-0794), and the Young Teacher Foundation of Mechanical School (Grant No. MYF0806)     

ModRED: Hardware design and reconfiguration planning for a high dexterity modular self-reconfigurable robot for extra-terrestrial exploration

This paper presents a homogeneous modular robot system design based on four per-module degrees of freedom (DOF), including a prismatic DOF to increase the versatility of its reconfiguration and locomotion capabilities. The ModRED (Modular Robot for Exploration and Discovery) modules are developed with rotary-plate genderless single sided docking mechanisms (RoGenSiD) that allow chain-type configurations and lead towards hybrid-type configurations. Various locomotion gaits are simulated through the Webots robot simulator and implemented in the real ModRED system. This work also addresses the problem of dynamic reconfiguration in a modular self-reconfigurable robot (MSR). The self-reconfiguration problem is modeled as an instance of the graph-based coalition formation problem. We formulate the problem as a linear program that finds the “best” partition or coalition structure among a set of ModRED modules. The technique is verified experimentally for a variety of settings on an accurately simulated model of the ModRED robot within the Webots robot simulator. Our experimental results show that our technique can find the best partition with a reasonably low computational overhead.     

SKY: efficient peer-to-peer networks based on distributed Kautz graphs

Many proposed P2P networks are based on traditional interconnection topologies. Given a static topology, the maintenance mechanism for node join/departure is critical to designing an efficient P2P network. Kautz graphs have many good properties such as constant degree, low congestion and optimal diameter. Due to the complexity in topology maintenance, however, to date there have been no effective P2P networks that are proposed based on Kautz graphs with base > 2. To address this problem, this paper presents the “distributed Kautz (D-Kautz) graphs”, which adapt Kautz graphs to the characteristics of P2P networks. Using the D-Kautz graphs we further propose SKY, the first effective P2P network based on Kautz graphs with arbitrary base. The effectiveness of SKY is demonstrated through analysis and simulations. Supported partially by the National Natural Science Foundation of China (Grant Nos. 60673167 and 60703072), the Hunan Provincial Natural Science Foundation of China (Grant No. 08JJ3125), and the National Basic Research Program of China (973) (Grant No. 2005CB321801)     

Dynamic multi-robot team reconfiguration using weighted voting games

We consider the problem of dynamic reconfiguration of robot teams when they encounter obstacles while navigating in formation, in an initially unknown environment. We have used a framework from coalition game theory called weighted voting games to analyse this problem and proposed two heuristics that can appropriately partition a robot team into sub-teams. We have experimentally verified our technique on teams of e-puck robots of different sizes and with different obstacle geometries, both on the Webots simulator and on physical robots. We have also shown that our technique performs faster and generates considerably fewer partitions than an existing robot coalition formation algorithm.     

W^1,2（Ω）- and X^1,2（Ω）-stability of reaction- diffusion cellular neural networks with delay

With Poincare＇s inequality and auxiliary function applied in a class of retarded cellular neural networks with reaction-diffusion, the conditions of the systems＇ W^1,2（Ω）-exponential and X^1,2（Ω）-asmptotic stability are obtained. The stability conditions containing diffusion term are different from those obtained in the previous papers in their exponential stability conditions. One example is given to illustrate the feasibility of this method in the end.     

Genetic algorithm-based dynamic reconfiguration for networked control system

This paper represents a genetic algorithm (GA) based dynamic reconfiguration for networked control systems (NCS) with the objective of minimizing network time-delay. With the development of NCS, it is become more and more important for them to have the minimum time-delay and the ability of dynamic reconfiguration, which can accommodate the changes rapidly, smartly and flexibly. And it is important to find a routing algorithm, which is quicker to reduce the time to update the router and decrease the reconfiguration time as much as possible. In this paper, based on NCS, we discuss the process of GA with specialized encoding, initialization, selection, crossover and mutation. A specialized repair function is used to improve performance. In addition, experiment results are given to illuminate that GA can improve the performance of the NCS. This work was supported by grants from the National Natural Science Foundation of China (No.60674081 and No.60574088).     

Multihead Two-Way Probabilistic Finite Automata

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies. We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata. This research was supported by the National Science Foundation under Grant No. CDA 8822724 while the author was at the University of Rochester. An extended abstract of this paper appeared in Proceedings, Second Latin American Symposium, LATIN ’95: Theoretical Informatics, Valparaiso, Chile, April 1995.