Nonsmooth multi-objective synthesis with applications

Nonsmooth optimization is used to design feedback controllers subject to closed-loop performance specifications both in time and frequency-domains. In time domain the nonlinear plant is submitted to a set of test input signals and the closed-loop responses so generated are called scenarios. A design technique is proposed which computes a controller with a prescribed structure that satisfies performance specifications for a given set of scenarios in tandem with robustness constraints in the frequency-domain, and is locally optimal among other controllers with these properties.     

Logarithmic Barrier Decomposition Methods for Semi-infinite Programming

A computational study of some logarithmic barrier decomposition algorithms for semi-infinite programming is presented in this paper. The conceptual algorithm is a straightforward adaptation of the logarithmic barrier cutting plane algorithm which was presented recently by den Hartog et al. ( Annals of Operations Research , 58 , 69–98, 1995), to solve semi-infinite programming problems. Usually decomposition (cutting plane methods) use cutting planes to improve the localization of the given problem. In this paper we propose an extension which uses linear cuts to solve large scale, difficult real world problems. This algorithm uses both static and (doubly) dynamic enumeration of the parameter space and allows for multiple cuts to be simultaneously added for larger/difficult problems. The algorithm is implemented both on sequential and parallel computers. Implementation issues and parallelization strategies are discussed and encouraging computational results are presented.     

A computational model of time for stiff hybrid systems applied to control synthesis

Computation has quickly become of paramount importance in the design of engineered systems, both to support their features as well as their design. Tool support for high-level modeling formalisms has endowed design specifications with executable semantics. Such specifications typically include not only discrete-time and discrete-event behavior, but also continuous-time behavior that is stiff from a numerical integration perspective. The resulting stiff hybrid dynamic systems necessitate variable-step solvers to simulate the continuous-time behavior as well as solver algorithms for the simulation of discrete-time and discrete-event behavior. The combined solvers rely on complex computer code which makes it difficult to directly solve design tasks with the executable specifications. To further leverage the executable specifications in design, this work aims to formalize the semantics of stiff hybrid dynamic systems at a declarative level by removing implementation detail and only retaining ‘what’ the computer code does and not ‘how’ it does it. A stream-based approach is adopted to formalize variable-step solver semantics and to establish a computational model of time that supports discrete-time and discrete-event behavior. The corresponding declarative formalization is amenable to computational methods and it is shown how model checking can automatically generate, or synthesize, a feedforward control strategy for a stiff hybrid dynamic system. Specifically, a stamper in a surface mount device is controlled to maintain a low acceleration of the stamped component for a prescribed minimum duration of time.     

Nonlinear robust control of a small-scale helicopter on a test bench

A nonlinear robust controller design procedure is presented, which is designed to simultaneously satisfy multiple conflicting closed-loop performance specifications. Significantly, a robust performance specification for the experimental system, developed for studying the attitude control of a small-scale helicopter in our previous work, is discussed quantitatively. The robust performance specifications and nominal multiple closed-loop performance specifications are conflicting. Use of the Convex Integrated Design (CID) method can provide, where feasible, a single closed-loop controller which satisfies a set of multiple conflicting performance specifications. However, the resultant controller has a complex form. Here, the standard CID method is extended to a more general control system framework to solve the conflicting simultaneous performance design problem. When compared with the standard CID design, the extended CID design procedure generates a relatively simple closed-loop controller. Finally, the synthesised controller is tested in simulation and is validated with an experimental small-scale test helicopter, demonstrating the performance of the proposed controller.     

Controller reduction with closed loop H infinity performance constraints: A QFT perspective

Assume that an initial stabilizing controller K₀₍s₎, which satisfies various closed loop frequency domain specifications, has been a priori synthesized using, e.g. H infinity control, mu synthesis techniques or closed loop convex synthesis. Remembering that the order of K₀₍s₎ is typical y at least equal to the order of the plant to be controlled, the aim of this paper is to find a stabilizing reduced order controller, which also satisfies the performance specifications and which moreover minimizes the open loop bandwidth. To this aim, the structured singular value mu is used to translate at each frequency closed loop frequency domain specifications into requirements on the frequency response of the controller. The principle of our reduction method is thus very close to the original idea of the SISO QFT design approach, except that the problem of translating closed loop frequency domain specifications into open loop ones is much more complex in the MIMO case. The problem reduces to the issue of finding a controller, whose frequency response belongs at each frequency to a template. The convexity of these templates greatly facilitates the practical realization of the controller. As a final point, the method is successfully applied to a standard H problem, which is extracted from the mu Analysis and Synthesis Toolbox of Matlab, namely the synthesis of an autopilot for the space shuttle.     

Improvements on the computation of boundaries in QFT

Quantitative feedback theory (QFT) is an engineering design technique of uncertain feedback systems that uses frequency domain specifications. A key step in QFT is the mapping of these specifications into regions of the Nichols plane, whose borders are usually referred to as boundaries. Boundaries computation is a key design step, thus a precise and efficient computation is critical for both obtaining low bandwidth feedback compensators and simplification of the design process. In this work, the problem of boundaries computation is analysed, introducing a new algorithm based on the computation of level curves of a three‐dimensional surface. Besides magnitude boundaries, associated with some specification over the magnitude of a closed‐loop transfer function, phase boundaries are also considered. In addition, comparison with previous published algorithms is done in terms of precision and computational efficiency. Copyright © 2006 John Wiley & Sons, Ltd.     

Functional synthesis for linear arithmetic and sets

Synthesis of program fragments from specifications can make programs easier to write and easier to reason about. To integrate synthesis into programming languages, synthesis algorithms should behave in a predictable way—they should succeed for a well-defined class of specifications. To guarantee correctness and applicability to software (and not just hardware), these algorithms should also support unbounded data types, such as numbers and data structures. To obtain appropriate synthesis algorithms, we propose to generalize decision procedures into predictable and complete synthesis procedures. Such procedures are guaranteed to find the code that satisfies the specification if such code exists. Moreover, we identify conditions under which synthesis will statically decide whether the solution is guaranteed to exist and whether it is unique. We demonstrate our approach by starting from a quantifier elimination decision procedure for Boolean algebra of set with Presburger arithmetic and transforming it into a synthesis procedure. Our procedure also works in the presence of parametric coefficients. We establish results on the size and the efficiency of the synthesized code. We show that such procedures are useful as a language extension with implicit value definitions, and we show how to extend a compiler to support such definitions. Our constructs provide the benefits of synthesis to programmers, without requiring them to learn new concepts, give up a deterministic execution model, or provide code skeletons.     

On the design of robust controllers for arbitrary uncertainty structures

The focal point of this paper is the design of robust controllers for linear time-invariant uncertain systems. Given bounds on performance (defined by a convex performance evaluator) the algorithm converges to a controller that robustly satisfies the specifications. The procedure introduced has its basis on stochastic gradient algorithms and it is proven that the probability of performance violation tends to zero with probability one. Moreover, this algorithm can be applied to any uncertain plant, independently of the uncertainty structure. As an example of application of this new approach, we demonstrate its usefulness in the design of robust H/sub 2/ controllers.     

UML状态机的模型检验方法

模型检验是一种确保设计规范正确性的形式化自动验证技术,本文提出了对UML状态机进行模型检验的方法。文中首先对UML状态机的语法和语义进行描述,然后基于语义中的RTC步给出生状态机全局可达状态迁移图的方法,方法的核心是在当前格局下根据使能条件确定所有的最大无冲突迁移集。文章最后给出算法以验证UML状态机是否满足用计算树逻辑（CTL）公式表示的性质。     

Feasibility of H∞ design specifications: an interpolation method

Given a set of H _∞ design specifications, the issue is to check whether there exists a controller, whose order is free, which satisfies these specifications. The classical solution, which is based on Youla parametrization and convex closed loop design, is not really satisfactory since it should use an infinite dimensional basis of filters, which cannot be done in practice. Let J* the minimal value of the design objective over such an infinite dimensional basis of filters. A Nevanlinna Pick interpolation method is proposed here to compute lower and upper bounds of J*, by solving the design problem on a finite set of frequencies. Finite-time convergence of the algorithm is proved.     

瓶颈Steiner网络设计问题的算法研究

瓶颈Steiner网络设计问题要求从网络中找出一个满足某种瓶颈条件的Steiner树,由于该问题的NP困难性,因此必须找出它的近似算法。该文针对树和一般图这2种网络情形,在问题转化的基础上分别给出了基于分组Steiner问题的近似算法,在Marathe等算法思想的基础上给出了有根和无根2种情形下的2个近似算法。     

Parallelization of the Ising model and its performance evaluation

We report on the parallelization of two widely used algorithms in computational physics: The Monte Carlo simulation of the Ising model and a cluster identification algorithm which is used for percolation or percolation-like problems. Both parallel algorithms were tested on a multi-transputer system using up to 128 processors. The results show that the algorithms can perform with a linear speedup. We propose a scaling law for the speedup and show that the speedup for both algorithms satisfies this scaling.     

Multi-input/single-output computer-aided control design using the quantitative feedback theory

The quantitative feedback theory is an engineering design technique of uncertain feedback systems having robust stability and robust performance specifications. The crux of the quantitative feedback theory is a transformation of robust stability and robust performance specifications into domains in the complex plane, referred to as bounds, where a nominal loop transmission should lie within. To date, a quantitative feedback theory design is being carried out using manual (i.e. graphical) procedures or search algorithms. This paper shows that there exists a formal map from the uncertain plant and each closed-loop specification to these bounds. In particular, it is shown that each map has a closed form consisting of a quadratic inequality. These maps greatly simplify the computational aspects of the quantitative feedback theory in design of single-loop feedback systems. Based on this new development, a simple-to-implement, efficient computer algorithm is outlined.     

Product portfolio identification with data mining based on multi-objective GA

In the initial stage of product design, it is essential to define product specifications according to various market niches. An important issue in this process is to provide designers with sufficient design knowledge to find out what customers really want. This paper proposes a data mining method to facilitate this task. The method focuses on mining association rules that reflect the mapping relationship between customer needs and product specifications. Four objectives, support, confidence, interestingness and comprehensibility, are used for evaluating the extracted rules. To solve such a multi-objective problem, a Pareto-based GA is utilized to perform the rule extraction. Through computational experiments on an electrical bicycle case, it is shown that our approach is capable of extracting useful and interesting knowledge from a design database.     

A sequential approximate programming strategy for reliability-based structural optimization

Although reliability-based structural optimization (RBSO) is recognized as a rational structural design philosophy that is more advantageous to deterministic optimization, most common RBSO is based on straightforward two-level approach connecting algorithms of reliability calculation and that of design optimization. This is achieved usually with an outer loop for optimization of design variables and an inner loop for reliability analysis. A number of algorithms have been proposed to reduce the computational cost of such optimizations, such as performance measure approach, semi-infinite programming, and mono-level approach. Herein the sequential approximate programming approach, which is well known in structural optimization, is extended as an efficient methodology to solve RBSO problems. In this approach, the optimum design is obtained by solving a sequence of sub-programming problems that usually consist of an approximate objective function subjected to a set of approximate constraint functions. In each sub-programming, rather than direct Taylor expansion of reliability constraints, a new formulation is introduced for approximate reliability constraints at the current design point and its linearization. The approximate reliability index and its sensitivity are obtained from a recurrence formula based on the optimality conditions for the most probable failure point (MPP). It is shown that the approximate MPP, a key component of RBSO problems, is concurrently improved during each sub-programming solution step. Through analytical models and comparative studies over complex examples, it is illustrated that our approach is efficient and that a linearized reliability index is a good approximation of the accurate reliability index. These unique features and the concurrent convergence of design optimization and reliability calculation are demonstrated with several numerical examples.     

The application of parameter optimisation techniques to linear optimal control system design

The linear quadratic regulator (LQR) design technique produces controllers with well-known properties including good stability margins. A fundamental question with the LQR technique is the appropriate selection of the state and control weighting matrices to achieve given design specifications. A solution to this problem is presented whereby a parameter optimisation approach is employed to automate the LQR design procedure. Standard numerical algorithms are used to calculate the weighting matrices such that the specifications are satisfied. Decoupled command tracking specifications in the time domain are considered at present, and a multivariable proportional plus integral controller structure is employed. To the knowledge of the authors the design methodology is new and has the advantages of both optimal control and accommodation of additional design specifications. The application of the method is demonstrated in the design of a decoupled longitudinal control system for a vertical take-off-and-land (VTOL) aircraft.     

Parametric design adaptation for competitive products

Very often product development is seen as a process where designers iterate through several design cycles until they converge upon a design that satisfies all of the necessary requirements—design within a single generation. If one takes the view that products change (i.e. adapt and evolve), a broader view must be adopted to capture the drivers of design adaptation across multiple product generations. This paper offers a new multi-generation conceptual framework of parametric design adaptation for consumer products, called the Artisan–Patron (AP) framework, and a complementary computational model. The AP framework captures the interaction between manufacturers (the Artisan) and consumers (the Patron) by structuring the various relevant information (e.g., consumer taste, government policy, cost of raw materials, etc.). Additionally, based on this framework, a corresponding computational model is developed, which allows engineers to find optimal settings for the design variables in a dynamic multi-generation environment. The utility of the conceptual framework and the computational model is demonstrated by considering the parametric design adaptation of the automobile with respect to two design parameters—engine horsepower and weight—based on historical automotive industry data.     

SPARE: a development environment for program analysis algorithms

A tool that bridges the gap between the theory and practice of program analysis specifications is described. The tool supports a high-level specification language that enables clear and concise expression of analysis algorithms. The denotational nature of the specifications eases the derivation of formal proofs of correctness for the analysis algorithm. SPARE (structured program analysis refinement environment) is based on a hybrid approach that combines the positive aspects of both the operational and the semantics-driven approach. An extended denotational framework is used to provide specifications in a modular fashion. Several extensions to the traditional denotational specification language have been designed to allow analysis algorithms to be expressed in a clear and concise fashion. This extended framework eases the design of analysis algorithms as well as the derivation of correctness proofs. The tool provides automatic implementation for testing purposes     

Subdefinite Models and Logic Programming: Implementation of Constraints

Subdefinite models, described in [11], are a common approach to representation and processing of partial specifications. This approach is closely related to constraint programming, and, actually, is a method for constructing constraint satisfaction algorithms. The paper describes subdefinite models themselves, the method of their integration into logic programming, and two calculators created on the basis of this method. Results of a comparison of these calculators with the best available calculators designed for the same purpose are given. Applications are listed that were developed on the base of these calculators for solving problems of SAPR and computational geometry.     

Schur Decomposition and Model Reduction in the Design of Two-Dimensional Separable-Denominator Digital Filters

A new and numerically efficient technique for designing two-dimensional (2-D) separable-denominator digital filters using Schur decomposition (SD) and the diagonal symmetry of the 2-D impulse response specifications. This technique is based on two steps: first, the 2-D impulse response specifications are decomposed into two cascaded specifications, representing SIMO and MISO 1-D digital filters. By using the symmetry property of the 2-D impulse response matrix and that the left and right eigenspaces obtained by SD are a transpose of each other, the design problem of the two 1-D digital filters is reduced to the design problem of only one 1-D digital filter. Thus, the computational effort is reduced by approximately half. Further computational reduction is obtained by applying the SD to only part of the 2-D impulse response matrix, the leading principal minor submatrix, and from the symmetry property of the class of filters that are considered here, the decomposition of the impulse response matrix is obtained. In the second step, a model reduction algorithm is used to design a filter that approximates the 1-D specifications obtained from the first step. Two design examples illustrate the advantages of the proposed technique.