This paper deals with a problem from discrete-time robust control which requires the solution of constraints over the reals that contain both universal and existential quantifiers. For solving this problem we formulate it as a program in a (fictitious) constraint logic programming language with explicit quantifier notation. This allows us to clarify the special structure of the problem, and to extend an algorithm for computing approximate solution sets of first-order constraints over the reals to exploit this structure. As a result we can deal with inputs that are clearly out of reach for current symbolic solvers.
First-order constraints occur frequently in control, and especially robust control. Up to now they either have been solved by specialized methods @cite_19 @cite_3 @cite_1 or by applying general solvers like QEPCAD @cite_27 . In the first case one is usually restricted to conditions like linearity, and in the second case one suffers from the high run-time complexity of computing exact solutions @cite_5 @cite_17 . We know of only one case where general solvers for first-order constraints have been applied to discrete-time systems @cite_26 , but they have been frequently applied to continuous systems @cite_14 @cite_15 @cite_25 . For non-linear discrete-time systems without perturbations or control, interval methods have also proved to be an important tool @cite_20 @cite_13 .
@cite_26 @cite_14 @cite_1 @cite_3 @cite_19 @cite_27 @cite_5 @cite_15 @cite_13 @cite_25 @cite_20 @cite_17
2114681281 2061749308 2124488301 1588998206 2007074311 2104715607 2029381483 63626580 2121579770 1601908671
State and output dead beat controllability tests for a very large class of polynomial systems with rational coefficients may be based on the quantifier elimination by partial cylindrical algebraic decomposition (QEPCAD) symbolic computation program. The method is unified for a very large class of systems and can handle one- or two-sided control constraints. Families of minimum time state output dead beat controllers are obtained. The computational complexity of the test is prohibitive for general polynomial systems, but by constraining the structure of the system we may beat the curse of complexity. A computationally less expensive algebraic test for output dead beat controllability for a class of odd polynomial systems is presented. Necessary and sufficient conditions are given. They are still very difficult to check. Therefore, a number of easier-to-check sufficient conditions are also provided. The latter are based on the Grobner basis method and QEPCAD. It is shown on a subclass of odd polynomial systems how it is possible to further reduce the computational complexity by exploiting the structure of the system. Many problems in control theory can be formulated as formulae in the first-order theory of real closed fields. In this paper we investigate some of the expressive power of this theory. We consider dynamical systems described by polynomial differential equations subjected to constraints on control and system variables and show how to formulate questions in the above framework which can be answered by quantifier elimination. The problems treated in this paper regard stationarity, stability, and following of a polynomially parametrized curve. The software package QEPCAD has been used to solve a number of examples. Abstract This paper surveys a subset of the body of research which was sparked by Kharitonov's Theorem. The focal point is extreme point results for robust stability and robust performance. That is, we give conditions under which satisfaction of a performance specification is ascertained for a family of systems by only checking a finite subset of the extreme members of this family. The results which are surveyed apply mainly to systems with structured real parametric uncertainty. In addition, a number of counterexamples are given to illustrate cases for which an extreme point result does not hold. For such cases, a solution via the so-called Edge Theorem is often possible. 1. Introduction. 2. Linear Algebra. 3. Linear Systems. 4. H2 and Ha Spaces. 5. Internal Stability. 6. Performance Specifications and Limitations. 7. Balanced Model Reduction. 8. Uncertainty and Robustness. 9. Linear Fractional Transformation. 10. m and m- Synthesis. 11. Controller Parameterization. 12. Algebraic Riccati Equations. 13. H2 Optimal Control. 14. Ha Control. 15. Controller Reduction. 16. Ha Loop Shaping. 17. Gap Metric and ...u- Gap Metric. 18. Miscellaneous Topics. Bibliography. Index. The Cylindrical Algebraic Decomposition method (CAD) decomposes R^r into regions over which given polynomials have constant signs. An important application of CAD is quantifier elimination in elementary algebra and geometry. In this paper we present a method which intermingles CAD construction with truth evaluation so that parts of the CAD are constructed only as needed to further truth evaluation and aborts CAD construction as soon as no more truth evaluation is needed. The truth evaluation utilizes in an essential way any quantifiers which are present and additionally takes account of atomic formulas from which some variables are absent. Preliminary observations show that the new method is always more efficient than the original, and often significantly more efficient. We consider linear problems in fields, ordered fields, discretely valued fields (with finite residue field or residue field of characteristic zero) and fields with finitely many independent orderings and discrete valuations. Most of the fields considered will be of characteristic zero. Formally, linear statements about these structures (with parameters) are given by formulas of the respective first-order language, in which all bound variables occur only linearly. We study symbolic algorithms (linear elimination procedures) that reduce linear formulas to linear formulas of a very simple form, i.e. quantifier-free linear formulas, and algorithms (linear decision procedures) that decide whether a given linear sentence holds in all structures of the given class. For all classes of fields considered, we find linear elimination procedures that run in double exponential space and time. As a consequence, we can show that for fields (with one or several discrete valuations), linear statements can be transferred from characteristic zero to prime characteristic p, provided p is double exponential in the length of the statement. (For similar bounds in the non-linear case, see Brown, 1978.) We find corresponding linear decision procedures in the Berman complexity classes @[email protected]?NSTA(*,2^c^n,dn) for d = 1, 2. In particular, all hese procedures run in exponential space. The technique employed is quantifier elimination via Skolem terms based on Ferrante & Rackoff (1975). Using ideas of Fischer & Rabin (1974), Berman (1977), Furer (1982), we establish lower bounds for these problems showing that our upper bounds are essentially tight. For linear formulas with a bounded number of quantifiers all our algorithms run in polynomial time. For linear formulas of bounded quantifier alternation most of the algorithms run in time 2^O^(^n^^^k^) for fixed k. This paper shows how certain robust multi-objective feedback design problems can be reduced to quantifier elimination (QE) problems. In particular it is shown how robust stabilization and robust frequency domain performance specifications can be reduced to systems of polynomial inequalities with suitable logic quantifiers, ? and ?. Because of computational complexity the size of problems that can solved by QE methods is limited. However, the design problems considered here do not haveanalyticalsolutions, so that even the solution of modest-sized problems may be of practical interest. This paper deals with the determination of the position and orientation of a mobile robot from distance measurements provided by a belt of onboard ultrasonic sensors. The environment is assumed to be two-dimensional, and a map of its landmarks is available to the robot. In this context, classical localization methods have three main limitations. First, each data point provided by a sensor must be associated with a given landmark. This data-association step turns out to be extremely complex and time-consuming, and its results can usually not be guaranteed. The second limitation is that these methods are based on linearization, which makes them inherently local. The third limitation is their lack of robustness to outliers due, e.g., to sensor malfunctions or outdated maps. By contrast, the method proposed here, based on interval analysis, bypasses the data-association step, handles the problem as nonlinear and in a global way and is (extraordinarily) robust to outliers. Interval analysis is used to characterize the set of all input sequences with a given length that drive a nonlinear discrete-time state-space system from a given initial state to a given set of terminal states. No requirement other than computability (i.e. ability to be evaluated by a finite algorithm) is put on the nature of the state equations. The method is based on an algorithm for set inversion and approximates the solution set in a guaranteed way. PLEASE NOTE: The original Technical Report TR00853 is missing. A copy can be found at http: www.sciencedirect.com science article pii S0747717110800033