Algebraic Geometry for Robotics and Control Theory

"The development of inexpensive and fast computers, coupled with the discovery of efficient algorithms for dealing with polynomial equations, has enabled exciting new applications of algebraic geometry and commutative algebra. Algebraic Geometry for Robotics and Control Theory shows how tools borrowed from these two fields can be efficiently employed to solve relevant problem arising in robotics and control theory. After a brief introduction to various algebraic objects and techniques, the book first covers a wide variety of topics concerning control theory, robotics, and their applications. Specifically this book shows how these computational and theoretical methods can be coupled with classical control techniques to: solve the inverse kinematics of robotic arms; design observers for nonlinear systems; solve systems of polynomial equalities and inequalities; plan the motion of mobile robots; analyze Boolean networks; solve (possibly, multi-objective) optimization problems; characterize the robustness of linear; time-invariant plants; and certify positivity of polynomials"-- Provided by publisher Contents Preface About the Authors List of Figures List of Tables List of Symbols 1. Algebraic Geometry Notions 1.1 Affine varieties and polynomial ideals 1.2 Monomial orders and Gr ̈obner bases 1.3 Homogeneous polynomials and ideals 1.4 Elimination theory 1.4.1 Resultants 1.5 Operations on ideals 1.6 Quotient rings and zero-dimensional ideals 1.7 Root localization 1.8 The Shape Lemma 1.9 Solution of parametric systems for generic specializations of the parameters 1.10 Modules and syzygies 2. Implementations in Macaulay2 2.1 The Macaulay2 language 2.2 Polynomials in Macaulay2 2.3 Monomial orders and Gr ̈obner bases 2.4 Homogeneous polynomials and ideals 2.5 Elimination theory 2.6 Operations on ideals 2.7 Quotient rings and zero-dimensional ideals 2.8 The Shape Lemma 2.9 Modules and syzygies 3. The Inverse Kinematics of Robot Arms 3.1 The direct kinematics 3.2 The inverse kinematics 3.3 Some arm-and-body structures 3.3.1 The cylindrical robot 3.3.2 The SCARA robot 3.3.3 The spherical robot of Stanford 3.3.4 The anthropomorphic robot 3.4 The inverse orientation 4. Observer Design 4.1 Observability of real analytic and polynomial time-invariant systems 4.2 Observability of time-varying systems 4.3 Input–output embeddings of SISO continuous-time linear systems 4.4 High-gain observers 4.5 Parameter estimation 4.6 Switching signal estimation 4.7 Harmonic estimation for periodically forced chaotic systems 4.8 Fault detection and isolation for a DC motor 5. Immersions of Polynomial Systems into Linear Ones up to an Output Injection 5.1 Output injection 5.2 Immersion of polynomial systems into LIS form 5.3 Immersion into LIS form up to a finite order 5.4 Approximation of the immersion into LIS form 6. Solving Systems of Equations and Inequalities 6.1 An algorithm to compute the solutions of systems of polynomial equations 6.2 The method of the Lagrange multipliers 6.3 Solution of systems of polynomial relations 6.4 Application to the static output feedback stabilization problem 6.5 Application to the stability analysis of planar polynomial systems 6.6 Application to the dead-beat regulation of mechanical juggling systems 6.6.1 Mechanical juggling systems 6.6.2 Computation of the reference polynomial yd 7. Motion Planning for Mobile Robots 7.1 Well-defined affine varieties 7.2 f-invariant affine varieties 7.3 Locally attractive affine varieties 7.4 Examples of f-invariant and attractive affine varieties 7.5 Application to unicycle-like mobile robots 7.6 Application to car-like mobile robots 8. Computation of the Largest f-Invariant Set Contained in an Affine Variety 8.1 f-invariant sets for continuous-time systems 8.2 f-invariant sets for discrete-time systems 9. Boolean Networks 9.1 The Galois field F2 9.2 Analysis of autonomous Boolean networks 9.2.1 Reduced linear representation of Boolean networks 9.3 Finite-horizon optimal control for Boolean networks 9.3.1 Solution to integer programming problems 9.3.2 Finite-horizon optimal control problem 9.3.3 One-step optimization problem 10. Multi-objective Optimization 10.1 Multi-objective optimization in control system design 10.1.1 Pole placement with compensators having a fixed structure 10.1.2 Linear quadratic optimization 10.2 Scalar optimization via algebraic geometry techniques 10.2.1 Path-connected semi-algebraic sets 10.2.2 Scalar minimization 10.2.3 The envelope over an affine variety 10.3 Multi-objective minimization 10.3.1 The weighting method 10.3.2 The method of rays 10.3.3 The envelope method 10.3.4 Test for the Pareto optimality 10.3.5 Examples 10.4 Solving control MOMPs 10.4.1 Symbolic roots of a polynomial 10.4.2 Reformulation of Problem 10.1.1 10.4.3 Reformulation of Problem 10.1.2 10.5 Application to physical plants 10.5.1 Fast stabilization 10.5.2 Pole placement 10.5.3 Placement of the characteristic polynomial’s coefficients 10.5.4 Linear quadratic multi-objective optimization 10.6 Further applications: Game design 11. Distance to Internal Instability of Linear Time-Invariant Systems Under Structured Perturbations 11.1 Introduction 11.2 Related work in the unstructured case 11.3 The border polynomial 11.3.1 The continuous-time case 11.3.2 The Sylvester matrix and the resultant 11.3.3 The Bezout matrix and the resultant 11.3.4 The discrete-time case 11.4 Problem definition and first results 11.5 The squared distance of a point to an affine variety 11.6 The exponential stability in “almost all” cases 11.7 Choosing the nominal point 11.7.1 Analytic centers 11.7.2 Chebyshev centers 11.8 Control applications 11.8.1 Continuous-time non-structured robustness analysis 11.8.2 Discrete-time structured robustness analysis 11.8.3 Parameter selection for a discrete-time system 11.8.4 Optimal robust controller design 12. Decomposition in Sum of Squares 12.1 Introduction 12.2 wSOS and the reduced echelon form 12.2.1 Review of the quadratic case (d = 1): The “completing the square” procedure 12.2.2 Definition of “generality” for wSOS 12.2.3 A first solution to Problem 12.2.1 in the case n > m 12.3 A certificate of positive (semi-)definiteness 12.4 wSOS+ decomposition in the case n >m 12.5 Examples 12.6 Randomly generated experiments 12.7 Applications in control and system theory 12.8 wSOS+ decomposition through tools of linear algebra 12.8.1 Saturation 12.8.2 Polynomial representation of forms of total degree 2d 12.8.3 Linear algebra implementation of the “completing the square” procedure 12.8.4 wSOS+ representation Bibliography Index