<p> We study an alignment model for coding DNA sequences recently proposed by J. Hein in [4] that takes into account both DNA and protein information, and attempts to minimize the total amount of evolution at both DNA and protein levels[4,5,6]. Although there are two quadratic algorithms (i.e. Hua-Jiang algorithm[8] and PLH algorithm[9]) for Hein's model if the gap penalty function is affine, both of them are impractical because of the large constant factor embedded in the quadratic time complexity function. We therefore consider a mild simplification named Context-free Codon Alignment and present a much more efficient algorithm for the simplified model. The algorithms have been implemented and tested on both real and simulated sequences, and it is found that they produce almost identical alignments in most cases. Furthermore, we extend our model and design a heuristic algorithm to handle frame-shift errors and overlapping frames.</p> / Thesis / Master of Science (MSc)

Yes

The research presented in this dissertation investigates the use of all-at-once methods applied to aerodynamic design. All-at-once schemes are usually based on the assumption of sufficient continuity in the constraints and objectives, and this assumption can be troublesome in the presence of shock discontinuities. Special treatment has to be considered for such problems and we study several approaches. Our all-at-once methods are based on the Sequential Quadratic Programming method, and are designed to exploit the structure inherent in a given problem. The first method is a Reduced Hessian formulation which projects the optimization problem to a lower dimension design space. The second method exploits the sparse structure in a given problem which can yield significant savings in terms of computational effort as well as storage requirements. An underlying theme in all our applications is that careful analysis of the given problem can often lead to an efficient implementation of these all-at-once methods. Chapter 2 describes a nozzle design problem involving one-dimensional transonic flow. An initial formulation as an optimal control problem allows us to solve the problem as as two-point boundary problem which provides useful insight into the nature of the problem. Using the Reduced Hessian formulation for this problem, we find that a conventional CFD method based on shock capturing produces poor performance. The numerical difficulties caused by the presence of the shock can be alleviated by reformulating the constraints so that the shock can be treated explicitly. This amounts to using a shock fitting technique. In Chapter 3, we study variants of a simplified temperature control problem. The control problem is solved using a sparse SQP scheme. We show that for problems where the underlying infinite-dimensional problem is well-posed, the optimizer performs well, whereas it fails to produce good results for problems where the underlying infinite-dimensional problem is ill-posed. A transonic airfoil design problem is studied in Chapter 4, using the Reduced SQP formulation. We propose a scheme for performing the optimization subtasks that is based on an Euler Implicit time integration scheme. The motivation is to preserve the solution-finding structure used in the analysis algorithm. Preliminary results obtained using this method are promising. Numerical results have been presented for all the problems described. / Ph. D.

This thesis synthesizes general and scalable distributed nonlinear control algorithms with application to legged robots. It explores both naturally decentralized problems in legged locomotion, such as the collaborative control of human-lower extremity prosthesis and the decomposition of high-dimensional controllers of a naturally centralized problem into a net- work of low-dimensional controllers while preserving equivalent performance. In doing so, strong nonlinear interaction forces arise, which this thesis considers and sufficiently addresses. It generalizes to both symmetric and asymmetric combinations of subsystems. Specifically, this thesis results in two distinct distributed control algorithms based on the decomposition approach. Towards synthesizing the first algorithm, this thesis presents a formal foundation based on de- composition, Hybrid Zero Dynamics (HZD), and scalable optimization to develop distributed controllers for hybrid models of collaborative human-robot locomotion. This approach con- siders a centralized controller and then decomposes the dynamics and parameterizes the feedback laws to synthesize local controllers. The Jacobian matrix of the Poincaré map with local controllers is studied and compared with the centralized ones. An optimization problem is then set up to tune the parameters of the local controllers for asymptotic stability. It is shown that the proposed approach can significantly reduce the number of controller parameters to be optimized for the synthesis of distributed controllers, deeming the method computationally tractable. To evaluate the analytical results, we consider a human amputee with the point of separation just above the knee and assume the average physical parameters of a human male. For the lower-extremity prosthesis, we consider the PRleg, a powered knee-ankle prosthetic leg, and together, they form a 19 Degrees of Freedom (DoF) model. A multi-domain hybrid locomotion model is then employed to rigorously assess the performance of the afore-stated control algorithm via numerical simulations. Various simulations involving the application of unknown external forces and altering the physical parameters of the human model unbeknownst to the local controllers still result in stable amputee loco- motion, demonstrating the inherent robustness of the proposed control algorithm. In the later part of this thesis, we are interested in developing distributed algorithms for the real-time control of legged robots. Inspired by the increasing popularity of Quadratic programming (QP)-based nonlinear controllers in the legged locomotion community due to their ability to encode control objectives subject to physical constraints, this thesis exploits the idea of distributed QPs. In particular, this thesis presents a formal foundation to systematically decompose QP-based centralized nonlinear controllers into a network of lower-dimensional local QPs. The proposed approach formulates a feedback structure be- tween the local QPs and leverages a one-step communication delay protocol. The properties of local QPs are analyzed, wherein it is established that their steady-state solutions on periodic orbits (representing gaits) coincide with that of the centralized QP. The asymptotic convergence of local QPs' solutions to the steady-state solution is studied via Floquet theory. Subsequently, to evaluate the effectiveness of the analytical results, we consider an 18 DoF quadrupedal robot, A1, as a representative example. The network of distributed QPs mentioned earlier is condensed to two local QPs by considering a front-hind decomposition scheme. The robustness of the distributed QP-based controller is then established through rigorous numerical simulations that involve exerting unmodelled external forces and intro- ducing unknown ground height variations. It is further shown that the proposed distributed QPs have reduced sensitivity to noise propagation when compared with the centralized QP. Finally, to demonstrate that the resultant distributed QP-based nonlinear control algorithm translates equivalently well to hardware, an extensive set of blind locomotion experiments on the A1 robot are undertaken. Similar to numerical simulations, unknown external forces in the form of aggressive pulls and pushes were applied, and terrain uncertainties were introduced with the help of arbitrarily displaced wooden blocks and compliant surfaces. Additionally, outdoor experiments involving a wide range of terrains such as gravel, mulch, and grass at various speeds up to 1.0 (m/s) reiterate the robust locomotion observed in numerical simulations. These experiments also show that the computation time is significantly dropped when the distributed QPs are considered over the centralized QP. / Doctor of Philosophy / Inspiration from animals and human beings has long driven the research of legged loco- motion and the subsequent design of the robotic counterparts: bipedal and quadrupedal robots. Legged robots have also been extended to assist human amputees with the help of powered prostheses and aiding people with paraplegia through the development of exoskeleton suits. However, in an effort to capture the same robustness and agility demonstrated by nature, our design abstractions have become increasingly complicated. As a result, the en- suing control algorithms that drive and stabilize the robot are equivalently complicated and subjected to the curse of dimensionality. This complication is undesirable as failing to compute and prescribe a control action quickly destabilizes and renders the robot uncontrollable. This thesis addresses this issue by seeking nature for inspiration through a different perspective. Specifically, through some earlier biological studies on cats, it was observed that some form of locality is implemented in the control of animals. This thesis extends this observation to the control of legged robots by advocating an unconventional solution. It proposes that a high-dimensional, single-legged agent be viewed as a virtual composition of multiple, low-dimensional subsystems. While this outlook is not new and forms precedent to the vast literature of distributed control, the focus has always been on large-scale systems such as power networks or urban traffic networks that preserve sparsity, mathematically speaking. On the contrary, legged robots are underactuated systems with strong interaction forces acting amongst each subsystem and dense mathematical structures. This thesis considers this problem in great detail and proposes developments that provide theoretical stability guarantees for the distributed control of interconnected legged robots. As a result, two distinctly different distributed control algorithms are formulated. We consider a naturally decentralized structure appearing in the form of a human-lower extremity prosthesis to synthesize distributed controllers using the first control algorithm. Subsequently, the resultant local controllers are rigorously validated through extensive full- order simulations. In order to validate the second algorithm, this thesis considers the problem of quadrupedal locomotion as a representative example. It assumes for the purposes of control synthesis that the quadruped is comprised of two subsystems separated at the geometric center, resulting in a front and hind subsystem. In addition to rigorous validation via numerical simulations, in the latter part of this thesis, to demonstrate that distributed controllers preserve practicality, rigorous and extensive experiments are undertaken in indoor and outdoor settings on a readily available quadrupedal robot A1.

We study the behavior of numerical stabilization schemes in the context of linear quadratic regulator (LQR) control problems for convection diffusion equations. The motivation for this effort comes from the observation that when linearization is applied to fluid flow control problems the resulting equations have the form of a convection diffusion equation. This effort is focused on the specific problem of computing the feedback functional gains that are the kernels of the feedback operators defined by solutions of operator Riccati equations. We develop a stabilization scheme based on the Galerkin Least Squares (GLS) method and compare this scheme to the standard Galerkin finite element method. We use cubic B-splines in order to keep the higher order terms that occur in GLS formulation. We conduct a careful numerical investigation into the convergence and accuracy of the functional gains computed using stabilization. We also conduct numerical studies of the role that the stabilization parameter plays in this convergence. Overall, we discovered that stabilization produces much better approximations to the functional gains on coarse meshes than the unstabilized method and that adjustments in the stabilization parameter greatly effects the accuracy and convergence rates. We discovered that the optimal stabilization parameter for simulation and steady state analysis is not necessarily optimal for solving the Riccati equation that defines the functional gains. Finally, we suggest that the stabilized GLS method might provide good initial values for iterative schemes on coarse meshes. / Ph. D.

Traffic incidents routinely impact the flow of vehicles on roadways. These incidents need to be identified, and responded to in a timely fashion in order to keep traffic moving safely and efficiently. One of the main areas of transportation research that remains of contemporary interest is the study of travel times. Travel time information technologies, until very recently, have not been efficient enough to provide instantaneous information for managing traffic flow. The Virginia Department of Transportation (VDOT) currently operates a number of surveillance technologies. Of particular interest to us are Automatic Vehicle Identification (AVI) tag readers to assimilate travel time information. One of VDOT's latest research thrusts has been to develop efficient algorithms for estimating link travel times using such advanced technologies. To achieve this purpose, VDOT is currently monitoring volunteer tagged cars by using AVI tag readers fixed at certain specific locations. This thesis focuses on devising an efficient methodology to capture as much travel time information as possible, by solving a Reader Location Problem that maximizes the benefit accruing from measuring travel time variability with respect to freeways. This problem is formulated as a quadratic 0-1 optimization problem. The objective function parameters in the optimization problem represent certain benefit factors resulting from the ability to measure travel time variability along various origin-destination paths. A simulation study using the INTEGRATION package is performed to derive these benefit factors for various types of freeway sections, and two composite functions that measure benefits for O-D paths that are comprised of several such sections are presented. The simulation results are presented as generic look-up tables, and can be used for any freeway section for the purpose of computing the associated benefit factor coefficient. An optimization approach based on the Reformulation-Linearization Technique coupled with Semidefinite Programming concepts is designed to solve the formulated reader location problem. This approach can be used to derive alternative equivalent formulations of the problem that vary in the degree of tightness of their underlying linear programming relaxations. Four such model representations are explored by using the software package, AMPL-CPLEX 6.5.3, to solve them for some sample transportation networks. The sensitivity of the reader locations to the different proposed benefit factor composite functions is also investigated. The results indicate that the first level continuous RLT relaxation to problem RL produces a tight underlying representation and that the optimal solution obtained for this relaxation tends to be very close to the actual integer optimum. Moreover, it is found that the optimal locations of the readers are insensitive to either the traffic, or the benefit factor used, or the density of the graph, when these factors are considered individually. However, a combination of two or more of these factors can lead to a change in the optimal locations of the readers. / Master of Science

Let Q(√(-d)) be an imaginary quadratic field with discriminant Δ. We use the isomorphism between the ideal class groups of the field and the equivalence classes of binary quadratic forms to find the structure of the class group. We determine the structure by combining two of Shanks' algorithms [7, 8]. We utilize this method to find fields with cyclic factors that have order a large power of 2, or fields with class groups of high 5-ranks or high 7-ranks. / Master of Science

Unmanned aerial systems have been widely used for variety of civilian applications over the past few years. Some of these applications require accurate guidance and control. Consequently, Unmanned Aerial Vehicle (UAV) guidance and control attracted many researchers in both control theory and aerospace engineering. Flying wings, as a particular type of UAV, are considered to have one of the most efficient aerodynamic structures. It is however difficult to design robust controller for such systems. This is due to the fact that flying wings are highly sensitive to control inputs. The focus of this thesis is on modeling and control design for a UAV system. The platform understudy is a flying wing developed by SmartPlanes Co. located in Skellefteå, Sweden. This UAV is particularly used for topological mapping and aerial photography. The novel approach suggested in this thesis is to use two controllers in sequence. More precisely, Linear Quadratic Regulator (LQR) is suggested to provide robust stability, and Proportional, Integral, Derivative (PID) controller is suggested to provide reference signal regulation. The idea behind this approach is that with LQR in the loop, the system becomes more stable and less sensitive to control signals. Thus, PID controller has an easier task to do, and is only used to provide the required transient response. The closed-loop system containing the developed controller and a UAV non-linear dynamic model was simulated in Simulink. Simulated controller was then tested for stability and robustness with respect to some parametric uncertainty. Obtained results revealed that the LQR successfully managed to provide robust stability, and PID provided reference signal regulation.

The main contributions of this work are applications of robust control and analysis methods to complex engineering systems, namely, small fixed-wing unmanned aircraft systems (UAS). Multiple path-following controllers for a small fixed-wing Telemaster UAS are presented, including a linear parameter-varying (LPV) controller scheduled over path curvature. The controllers are synthesized based on a lumped path-following and UAS dynamic system, effectively combining the six degree-of-freedom aircraft dynamics with established parallel transport frame virtual vehicle dynamics. The robustness and performance of these controllers are tested in a rigorous MATLAB simulation environment that includes steady winds, turbulence, measurement noise, and delays. After being synthesized off-line, the controllers allow the aircraft to follow prescribed geometrically defined paths bounded by a maximum curvature. The controllers presented within are found to be robust to the disturbances and uncertainties in the simulation environment. A robust analysis framework for mathematical validation of flight control systems is also presented. The framework is specifically developed for the complete uncertainty characterization, quantification, and analysis of small fixed-wing UAS. The analytical approach presented within is based on integral quadratic constraint (IQC) analysis methods and uses linear fractional transformations (LFTs) on uncertainties to represent system models. The IQC approach can handle a wide range of uncertainties, including static and dynamic, linear time-invariant and linear time-varying perturbations. While IQC-based uncertainty analysis has a sound theoretical foundation, it has thus far mostly been applied to academic examples, and there are major challenges when it comes to applying this approach to complex engineering systems, such as UAS. The difficulty mainly lies in appropriately characterizing and quantifying the uncertainties such that the resulting uncertain model is representative of the physical system without being overly conservative, and the associated computational problem is tractable. These challenges are addressed by applying IQC-based analysis tools to analyze the robustness of the Telemaster UAS flight control system. Specifically, uncertainties are characterized and quantified based on mathematical models and flight test data obtained in house for the Telemaster platform and custom autopilot. IQC-based analysis is performed on several time-invariant H∞ controllers along with various sets of uncertainties aimed at providing valuable information for use in controller analysis, controller synthesis, and comparison of multiple controllers. The proposed framework is also transferable to other fixed-wing UAS platforms, effectively taking IQC-based analysis beyond academic examples to practical application in UAS control design and airworthiness certification. IQC-based analysis problems are traditionally solved using convex optimization techniques, which can be slow and memory intensive for large problems. An oracle for discrete-time IQC analysis problems is presented to facilitate the use of a cutting plane algorithm in lieu of convex optimization in order to solve large uncertainty analysis problems relatively quickly, and with reasonable computational effort. The oracle is reformulated to a skew-Hamiltonian/Hamiltonian eigenvalue problem in order to improve the robustness of eigenvalue calculations by eliminating unnecessary matrix multiplications and inverses. Furthermore, fast, structure exploiting eigensolvers can be employed with the skew-Hamiltonian/Hamiltonian oracle to accurately determine critical frequencies when solving IQC problems. Applicable solution algorithms utilizing the IQC oracle are briefly presented, and an example shows that these algorithms can solve large problems significantly faster than convex optimization techniques. Finally, a large complex engineering system is analyzed using the oracle and a cutting-plane algorithm. Analysis of the same system using the same computer hardware failed when employing convex optimization techniques. / Ph. D.

Yes / This paper proposes a new index to determine the static voltage stability of the load buses in a power network for certain operating conditions and hence identifies load buses which are close to voltage collapse. The proposed index is formulated from the quadratic equation derived from a two-bus network and is computed using the apparent power and the line impedance. The proposed index shows how far the load buses from their voltage stability limit and hence the most sensitive bus can be identified according to maximum loadability. 14 bus IEEE reliability test system is used to study the performance of the proposed index for its validity. A comparison is also made between proposed index and some other indices found in the literature. The results are discussed and key conclusion drawn.