<p> In computer vision, grammatical models are models that represent objects hierarchically as compositions of sub-objects. This allows us to specify rich object models in a standard Bayesian probabilistic framework. In this thesis, we formulate shape grammars, a probabilistic model of curve formation that allows for both continuous variation and structural variation. We derive an EM-based training algorithm for shape grammars. We demonstrate the effectiveness of shape grammars for modeling human silhouettes, and also demonstrate their effectiveness in classifying curves by shape. We also give a general method for heuristically speeding up a large class of dynamic programming algorithms. We provide a general framework for discussing coarse-to-fine search strategies, and provide proofs of correctness. Our method can also be used with inadmissible heuristics. </p><p> Finally, we give an algorithm for doing approximate context-free parsing of long strings in linear time. We define a notion of approximate parsing in terms of restricted families of decompositions, and construct small families which can approximate arbitrary parses.</p>

<p> Fast and accurate recognition of offline Chinese characters is a problem significantly more difficult than the recognition of the English alphabet. The vastly larger set of characters and noise in handwriting require more sophisticated normalization, feature extraction, and classification methods. This thesis explores the feasibility of a fast and accurate classification and translation retrieval system. An ensemble classifier composed of k-nearest neighbors and support vector machines is used as the basis of a fast classifier to recognize Chinese and Japanese characters. In contrast to other models, this classifier incorporates contextual N-gram information directly into the classification task to increase the accuracy of the classifier.</p>

Neural networks have been found to be useful as a technique for the modeling of non-linear functions or processes that involve several variables. The primary goal of this thesis is to explore the feasibility of applying feedforward backpropagation neural networks in the optimization of multistage thermal systems. Basically, the idea consists of using neural networks as a function approximation technique for each stage of a multistage process. After the successful approximation, existing optimization methods are used to obtain the parameters that optimize the system. In addition, it is shown how feedforward backpropagation neural networks can be used in solving calculus of variation problems, by separating the process into discrete stages, thus forming a multistage process problem. Finally, parallel work was done in developing a faster deterministic training algorithm, as an alternative to the time consuming backpropagation training algorithm.

Certain properties of back-propagation neural networks have been found to be useful in structuring models for multiple-input, multiple-output (MIMO) processes. The network's simplicity and its ability to identify the non-linearity can have wide impacts on the construction of model-based control system. Care must be taken to train the network with consistent data that contains sufficient dynamic information. A predictive control system based on the network model was proposed. Although the controller is relatively simple in terms of concept and computation, it shows excellent performances both in servo and regulator problems. Model prediction error sometimes causes a cyclic behavior in process responses; however, it can be stabilized by imposing certain constraints of controller action. The constraints are also effective for noisy measurements. Use of neural networks for modeling and control of MIMO system appears to be very promising with its ability to treat non-linearity and process interactions.

The research presented in this thesis is categorized into two areas. In the first part we address the issue of uniform boundedness of the elements of the equations of motion of serial robots, an important issue for the control of robots in this class. The second part is dedicated to the dynamic modeling and model based control of parallel robots. The field of serial robot control experienced tremendous growth over the past few decades resulting in a rigorous body of control results. An important assumption that is frequently made in establishing stability properties of these control laws is that the terms associated with the equations of motion of serial robots such as the inertia matrix, the Coriolis/centrifugal terms, and the Hessian of potential energy are uniformly bounded. This assumption however, is not valid for all serial robots. Since the stability conclusions of many control laws become local for robots that violate this assumption, it's important to be able to determine whether the terms in question are indeed uniformly bounded for a given robot. In the first part of this research we examine this issue and characterize the class of serial robots for which each of these terms are uniformly bounded. We also derive explicit uniform bounds for these terms which become important in control synthesis since the uniform bounds appear in the expressions of many control laws. The second part of this research is dedicated to parallel robots. Unlike in the case of serial robots, in parallel robots the independent generalized coordinates corresponding to the actuated joints do not uniquely determine the configuration of the robot. Therefore, an important issue that must be resolved in order to derive the dynamics of parallel robots is the existence of a transformation from the independent coordinates to a set of dependent coordinates that completely determine the robot configuration. The existence of such a transformation will enable the extension of most results in serial robots to parallel robots. In this research we characterize a region with specified boundaries where such a transformation exists and derive a numerical scheme for implementing the transformation in real time. Another contribution of this research is the design and construction of the Rice Planar Delta Robot which will serve as a test bed for results on parallel robots. This robot was used to experimentally verify the above result in a trajectory tracking experiment and a fast pick and place experiment.

Instruction scheduling is a code reordering transformation used to hide latencies present in modern day microprocessors. Scheduling is often critical in achieving peak performance from these processors. The designer of a compiler's instruction scheduler has many choices to make, including the scope of scheduling, the underlying scheduling algorithm, and handling interactions between scheduling and other transformations. List scheduling algorithms, and variants thereof, have been the dominate algorithms used by instruction schedulers for years. In this work we explore the strengths and weaknesses of this algorithm aided by the use of stochastic scheduling techniques. These new techniques we call RBF (randomized backward and forward scheduling) and iterative repair or IR. We examine how the algorithms perform in a variety of contexts, including different scheduling scope, different scheduling problem instances, different architectural features, and scheduling in the presence of register allocation. IR is a search framework enjoying a lot of attention in the artificial intelligence community. IR scheduling techniques have shown promise on other scheduling problems such as shuttle mission scheduling. In this work we describe how to target the framework for compiler instruction scheduling. We describe the evolution of our algorithm, how to integrate register pressure concerns, and the technique's performance. We evaluate our alternative algorithms based on a set of real applications and random instruction scheduling problems. Not surprisingly, list scheduling performs very well when scheduling basic blocks of machine instructions. However, there is some opportunity for alternative techniques when scheduling over larger scopes and targeting more complicated architectures. We describe an interesting link between list scheduling efficacy and the amount of parallelism available in a random problem instance. Increasingly we see complex microprocessors being used in embedded systems applications. Often the price of such systems is affected by the amount of on-board memory needed to store executable code for the microprocessor. Much work on instruction scheduling has improved the running time of scheduled code while sacrificing code size. Thus, finding scheduling techniques that do not increase code size is another focus of this work. We also develop techniques to decrease code size without increasing running time using genetic algorithms-another stochastic search method.

We construct models of the evolution of human learning on a visualmotor task by analysing a large sequential corpus of low-level performance data generated from it. The performance data is drawn sparsely from a large, high-dimensional space, is non-stationary---slowly evolving control policies are punctuated by radical conceptual shifts---and has non-Gaussian noise, which is difficult to model. We develop novel, data-driven algorithms for identifying the conceptual shifts, and for constructing compact representations of the subjects' stationary control policies. The policy models are "local" and use a novel extension to locally weighted regression. The closeness of fit of model performance to human learning curves experimentally demonstrates the effectiveness of our methods. In contrast to previous modeling work, we make no a priori assumptions about the underlying cognitive architecture required to duplicate subject behavior. By comparing the performance of our methods to decision trees, we demonstrate the superiority of local models for learning compact representations of high-dimensional, noisy, non-stationary sequential data.

Artificial neural networks have primarily been utilized to solve problems in pattern recognition, decision-making, signal analysis and controls. This thesis investigates the use of networks in modeling physical systems in fluid mechanics by using the governing partial differential equations to initialize the network parameters. The initialization requires imposing certain constraints on the values of the input, bias, and output weights. The attribution of certain roles to each of these parameters allows for mapping a polynomial approximation into an artificial neural network architecture. This approach is shown to be capable of incorporating smooth neuron transfer functions, such as the popular hyperbolic tangent. Attention is focused on the two-dimensional Navier-Stokes equations for Boussinesq convection that model two-dimensional double diffusive convection. The network used to model this example utilizes an approximation of the Gudermannian function and an application of the pseudospectral method for complete network initiation. Numerical examples are presented illustrating the accuracy and utility of the method.

Closed kinematic chains (CKCs) are constrained multibody systems that contain closed kinematic loops. Nowadays, CKCs are used in a variety of applications ranging from flight simulators to medical instruments, and are becoming increasingly popular in the machine-tool industry and haptic interfaces due to their better performance in terms of accuracy, rigidity and payload capacity as compared to open-chain mechanisms. This document intends to present a novel methodology for the modeling and control of general CKCs. The dynamics of CKCs are characterized by index-3 differential algebraic equations (DAEs). Dynamic models in the form of DAEs pose difficulties in model-based control because most existing control design techniques are devised for explicit state space models. The control methodology presented in this document is based on a singular perturbation formulation (SPF), which has attractive properties including the minimum dimension of its slow dynamics and the large validity domain that contains the entire singularity-free workspace of the CKCs. The key issue of the model approximation error is addressed under different stability conditions. Explicit error bounds are derived and sufficient conditions for the exponential convergence of the approximation errors are established. For the control of CKCs, our approach transfers the control of the original DAE system to the control of an artificially created singularly perturbed system. Compared to control methods which directly solve the nonlinear algebraic constraint equations, the proposed method uses an ODE solver to obtain the dependent coordinates, hence eliminating the need for Newton type iterations and is amenable to real-time implementation. The closed loop system, when controlled by typical open kinematic chain schemes, achieves asymptotic trajectory tracking. The efficacy of the approach is illustrated by simulating the dynamics of a CKC mechanism, the Rice Planar Delta Robot, and then by validating the simulation results with experimental data. Thus, this work establishes a framework in which the control of CKCs can be systematically addressed.

No description available.