ALGORITHM FOR COMPUTER PERCEPTION OF TOPOLOGICAL SYMMETRY

For the exhaustive and irredundant generation of candidate structures in ESESOC (Expert System for the Elucidation of the Structures of Organic Compounds), a new algorithm for computer perception of topological equivalence classes of the nodes (non-hydrog

A new wind vector algorithm for C-band SAR

Ocean wind speed and wind direction are estimated simultaneously using the normalized radar cross sections or' corresponding to two neighboring (25-km) blocks, within a given synthetic aperture radar (SAR) image, having slightly different incidence angles. This method is motivated by the methodology used for scatterometer data. The wind direction ambiguity is removed by using the direction closest to that given by a buoy or some other source of information. We demonstrate this method with 11 EN-VISAT Advanced SAR sensor images of the Gulf of Mexico and coastal waters of the North Atlantic. Estimated wind vectors are compared with wind measurements from buoys and scatterometer data. We show that this method can surpass other methods in some cases, even those with insufficient visible wind-induced streaks in the SAR images, to extract wind vectors.

Algorithm Studies on How to Obtain a Conditional Nonlinear Optimal Perturbation (CNOP)

The conditional nonlinear optimal perturbation (CNOP), which is a nonlinear generalization of the linear singular vector (LSV), is applied in important problems of atmospheric and oceanic sciences, including ENSO predictability, targeted observations, and ensemble forecast. In this study, we investigate the computational cost of obtaining the CNOP by several methods. Differences and similarities, in terms of the computational error and cost in obtaining the CNOP, are compared among the sequential quadratic programming (SQP) algorithm, the limited memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm, and the spectral projected gradients (SPG2) algorithm. A theoretical grassland ecosystem model and the classical Lorenz model are used as examples. Numerical results demonstrate that the computational error is acceptable with all three algorithms. The computational cost to obtain the CNOP is reduced by using the SQP algorithm. The experimental results also reveal that the L-BFGS algorithm is the most effective algorithm among the three optimization algorithms for obtaining the CNOP. The numerical results suggest a new approach and algorithm for obtaining the CNOP for a large-scale optimization problem.

基于智能优化算法的设备布局设计

制造系统的设备布局与生产率和生产成本密切相关 ,布局设计是制造系统设计者面临的关键问题之一。文章针对布局问题的平方分派模型 ,构建了一种布局设计的混合智能优化算法———遗传退火算法 ,并分析了算法实现的方法。实例表明遗传退火算法的高效性。

监控式水下机械手及相关技术的研究

水下机械手作为水下机器人通用作业工具得到广泛地应用，目前水下机械手的主要操作方式为主从方式。虽然主从方式具有操作直观，灵活的特点，但难于完成需要精确定位，轨迹控制的水下作用，如海洋石油钻井平台导管架的检查作用。为了扩展水下机器人的作业能力，提高水下作业智能化程度，沈阳自动化所承担国家863课题“水下虚拟遥操作与监控机械手系统”关键技术的研究工作。作者参加了此课题的研究工作，以Schilling水下机械手为研究对象，深入研究机械手的作用功能，对机械手的逆运动学，焊缝空间轨迹规划作了深入的研究，形成本文阐述的主要内容。由于Schilling水下机械手各关节之间的连接参数中存在多个偏距，其运动学逆解不能简单由解析方式给出。机械手进行控制与轨迹规划等操作必须找到一种快速求解的方法。本篇文章得出一种基于信赖域法的机械手运动学逆解算法。由于该算法具有收敛速度快的特点，故可以被应用于在线求解机械手运动学逆解；由于没有直接求解二阶导数，故不存在奇异解的问题。经理论分析和实验证明该方法在解决水下监控机械手在线跟踪水下结构物空间轨迹的技术问题具有较好的效果。作为课题的实际应用背景的导管架焊缝曲面为一复杂的空间曲面。为了实现课题的研究目标，本课题不仅要求解焊缝的轨迹，而且要给出其法线方向。对于这样一个问题，用空间解析几何和微分几何方法是很难求解的，本文给出了一种基于B样条参数曲面及曲面求交的方法，具有速度快，通用性强的优点。

A Scheduling Algorithm for Flexible Manufacturing Cell

In this paper, a new scheduling algorithm for the flexible manufacturing cell is presented, which is a discrete time control method with fixed length control period combining with event interruption. At the flow control level we determine simultaneously the production mix and the proportion of parts to be processed through each route. The simulation results for a hypothetical manufacturing cell are presented.

波动方程模拟与偏移的实用化方法研究

Along with the widespread and in-depth applications in petroleum prospecting and development, the seismic modeling and migration technologies are proposed with a higher requirement by oil industrial, and the related practical demand is getting more and more urgent. Based on theories of modeling and migration methods for wave equation, both related with velocity model, I thoroughly research and develop some methods for the goal of highly effective and practical in this dissertation. In the first part, this dissertation probes into the layout designing by wave equations modeling, focusing on the target-oriented layout designing method guided by wave equation modeling in complicated structure areas. It is implemented by using the fourth order staggered grid finite difference (FD) method in velocity-stress 2D acoustic wave equations plus perfectly matched layer (PML) absorbing boundary condition. To design target-oriented layout: (a) match the synthetic record on the surface with events of subsurface structures by analyzing the snapshots of theoretical model; (b) determine the shot-gather distance by tracking the events of target areas and measuring the receiving range when it reaches the surface; (c) restrict the range of valid shot-gather distance by drawing seismic windows in single shot records; (d) choose the best trace distance by comparing the resolution of prospecting targets from the simulated records with different trace distance. Eventually, we obtained the observation system parameters, which achieve the design requirements. In the second part, this dissertation presents the practical method to improve the 3D Fourier Finite Difference (FFD) migration, and carefully analyzes all the factors which influence 3D FFD migration’s efficiency. In which, one of the most important parameters of migration is the extrapolating step. This dissertation presents an efficient 3D FFD migration algorithm, which use FFD propagator to extrapolate wavefields over big layers, and use Born-Kirchhoff interpolator to image wavefields over small layers between the big ones. Finally, I show the effectiveness of this hybrid migration method by comparing migration results from 3D SEG/EAGE model with different methods.

Free Indexation: Combinatorial Analysis and a Compositional Algorithm

In the principles-and-parameters model of language, the principle known as "free indexation'' plays an important part in determining the referential properties of elements such as anaphors and pronominals. This paper addresses two issues. (1) We investigate the combinatorics of free indexation. In particular, we show that free indexation must produce an exponential number of referentially distinct structures. (2) We introduce a compositional free indexation algorithm. We prove that the algorithm is "optimal.'' More precisely, by relating the compositional structure of the formulation to the combinatorial analysis, we show that the algorithm enumerates precisely all possible indexings, without duplicates.

A Nondeterministic Minimization Algorithm

The problem of minimizing a multivariate function is recurrent in many disciplines as Physics, Mathematics, Engeneering and, of course, Computer Science. In this paper we describe a simple nondeterministic algorithm which is based on the idea of adaptive noise, and that proved to be particularly effective in the minimization of a class of multivariate, continuous valued, smooth functions, associated with some recent extension of regularization theory by Poggio and Girosi (1990). Results obtained by using this method and a more traditional gradient descent technique are also compared.

An Efficient Correspondence Based Algorithm for 2D and 3D Model Based Recognition

A polynomial time algorithm (pruned correspondence search, PCS) with good average case performance for solving a wide class of geometric maximal matching problems, including the problem of recognizing 3D objects from a single 2D image, is presented. Efficient verification algorithms, based on a linear representation of location constraints, are given for the case of affine transformations among vector spaces and for the case of rigid 2D and 3D transformations with scale. Some preliminary experiments suggest that PCS is a practical algorithm. Its similarity to existing correspondence based algorithms means that a number of existing techniques for speedup can be incorporated into PCS to improve its performance.

Some Extensions of the K-Means Algorithm for Image Segmentation and Pattern Classification

In this paper we present some extensions to the k-means algorithm for vector quantization that permit its efficient use in image segmentation and pattern classification tasks. It is shown that by introducing state variables that correspond to certain statistics of the dynamic behavior of the algorithm, it is possible to find the representative centers fo the lower dimensional maniforlds that define the boundaries between classes, for clouds of multi-dimensional, mult-class data; this permits one, for example, to find class boundaries directly from sparse data (e.g., in image segmentation tasks) or to efficiently place centers for pattern classification (e.g., with local Gaussian classifiers). The same state variables can be used to define algorithms for determining adaptively the optimal number of centers for clouds of data with space-varying density. Some examples of the applicatin of these extensions are also given.

An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer

Amorphous computing is the study of programming ultra-scale computing environments of smart sensors and actuators cite{white-paper}. The individual elements are identical, asynchronous, randomly placed, embedded and communicate locally via wireless broadcast. Aggregating the processors into groups is a useful paradigm for programming an amorphous computer because groups can be used for specialization, increased robustness, and efficient resource allocation. This paper presents a new algorithm, called the clubs algorithm, for efficiently aggregating processors into groups in an amorphous computer, in time proportional to the local density of processors. The clubs algorithm is well-suited to the unique characteristics of an amorphous computer. In addition, the algorithm derives two properties from the physical embedding of the amorphous computer: an upper bound on the number of groups formed and a constant upper bound on the density of groups. The clubs algorithm can also be extended to find the maximal independent set (MIS) and $Delta + 1$ vertex coloring in an amorphous computer in $O(log N)$ rounds, where $N$ is the total number of elements and $Delta$ is the maximum degree.

An Accelerated Chow and Liu Algorithm: Fitting Tree Distributions to High Dimensional Sparse Data

Chow and Liu introduced an algorithm for fitting a multivariate distribution with a tree (i.e. a density model that assumes that there are only pairwise dependencies between variables) and that the graph of these dependencies is a spanning tree. The original algorithm is quadratic in the dimesion of the domain, and linear in the number of data points that define the target distribution $P$. This paper shows that for sparse, discrete data, fitting a tree distribution can be done in time and memory that is jointly subquadratic in the number of variables and the size of the data set. The new algorithm, called the acCL algorithm, takes advantage of the sparsity of the data to accelerate the computation of pairwise marginals and the sorting of the resulting mutual informations, achieving speed ups of up to 2-3 orders of magnitude in the experiments.

The Essential Dynamics Algorithm: Essential Results

This paper presents a novel algorithm for learning in a class of stochastic Markov decision processes (MDPs) with continuous state and action spaces that trades speed for accuracy. A transform of the stochastic MDP into a deterministic one is presented which captures the essence of the original dynamics, in a sense made precise. In this transformed MDP, the calculation of values is greatly simplified. The online algorithm estimates the model of the transformed MDP and simultaneously does policy search against it. Bounds on the error of this approximation are proven, and experimental results in a bicycle riding domain are presented. The algorithm learns near optimal policies in orders of magnitude fewer interactions with the stochastic MDP, using less domain knowledge. All code used in the experiments is available on the project's web site.