State doctoral exam topics

Control Engineering and Robotics


Estimation and filtering

Examiner: prof. Havlena, prof. Kučera

  1. Bayesian approach to uncertainty description, model of a dynamic system, natural condition of control, probabilistic definition of system state. Likelihood function, sufficient statistics.
  2. ARX, ARMAX and OE model, relation to a single-step predictor. Statistical identification methods, linear and pseudo-linear regression.
  3. Batch and recursive estimation of ARX model parameters, statistics and their interpretation, incorporation of prior information.
  4. Tracking of time-varying parameters, forgetting methods, regularized and restricted forgetting.
  5. Gaussian process regression.
  6. Linear stochastic system, state mean and covariance development, Lyapunov equation for steady-state state covariance.
  7. Random process, autocorrelation function, power spectrum density, rational spectrum, spectral factorization.
  8. Discrete-time Kalman filter. Stochastic properties of prediction error. Innovation, whitening and noise-shaping filter. Kalman filter for colored noise.
  9. Random walk, Wiener process. Sampling of continuous-time linear stochastic system. Continuous-time Kalman filter with discrete measurements.
  10. Robust numerical implementation of estimation methods using factorized covariance matrix, LDL factorization, dyadic reduction update.
  11. Local and global approximation of non-linear/non-gaussian filters. Point-mass and particle filters, Monte Carlo method.

References:

  • Peterka, V.: Bayesian Approach To System Identification. In: Trends and Progress in System Identification, P. Eykhoff, Elsevier (1981) ISBN 08025683X http://www.utia.cas.cz/user_data/scientific/AS_dep
  • Kailath, T., A. H. Sayed and B. Hassibi: Linear Estimation (Paperback). Prentice Hall (2001). ISBN 978-0133007084
  • Papoulis, A.: Probability, Random variables and stochastic processes. McGraw Hill (1991), ISBN 0-07-048477-05
  • Jazwinski, A. H.: Stochastic Processes and Filtering Theory (Mathematics in Science and Engineering. Academic Press (1970), ISBN 0-12-381550-9
  • Simon, D.: Optimal state estimation. John Willey & Sons, Inc. (2006). ISBN 0-471-70858-5
  • Rasmussen, C.E. and K. I. Williams: Gaussian Processes for Machine Learning. The MIT Press (2006). ISBN 026218253X


Combinatorial Optimization

Examiner: prof. Hanzálek, Dr. Šůcha

  1. Theory of NP-Completeness. Classes P, NP, NP-complete, NP-hard, PSPACE, EXPTIME and EXPSPACE.
  2. Integer Linear Programming (ILP) - algorithms and formulation of combinatorial problems as an ILP problem.
  3. The Shortest Path (SP) in graphs - algorithms and formulation of combinatorial problems as a SP problem.
  4. Network Flows. Bipartite matching. Algorithms (Successive Shortest Path and Hungarian algorithms). Multi-commodity network flows.
  5. Knapsack problem. Pseudo-polynomial algorithms and approximation schemes.
  6. Traveling salesman problem (TSP). Non-existence of k-factor approximation for the TSP. Christofides’ algorithm. k-OPT local search algorithm.
  7. Constraint programming.

References:

  • B. H. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, 2008.
  • R. Dechter: Constraint Processing. Morgan Kaufmann, 2003.


Scheduling

Examiner: prof. Hanzálek, Dr. Šůcha

  1. Single machine scheduling. Bratley’s branch and bound algorithm. Solution of 1/prec/Suma-wjCj problem using branch and bound algorithm with LP relaxation. EDD and EDF algorithms, optimality proofs and problem with precedence relations.
  2. Parallel identical machines scheduling problem. Relaxation, approximation and pseudo-polynomial algorithms for P//Cmax problem. Optimal algorithms for P2/prec,Pj=1/Cmax and P2/pmtn,prec/Cmax .
  3. Problems with dedicated processors. Algorithms for Flow shop and Job shop problems.
  4. Project scheduling with temporal constraints. Problem reductions and ILP formulations.
  5. Scheduling in real-time operating systems, response time analysis. Periodic scheduling. Utilization bound for EDF and fixed priorities with Rate Monotonic.
  6. Cyclic scheduling. ILP formulation. Algorithms for minimum cycle duration.

References:

  • J. Blazevicz: Handbook on Scheduling From Theory to Applications. Springer, 2007.

 

Parallel Algorithms

Examiner: doc. Ing. Přemysl Šůcha, Ph.D., prof. Dr. Ing. Zdeněk Hanzálek

  1. Communication operations of parallel algorithms (one-to-all broadcast, all-to-one reduction, all-to-all broadcast/reduction, all-reduce, prefix-sum, scatter, gather), cost analysis of communication operations on different network topologies.
  2. Analytical modeling of parallel programs: cost-optimal parallel systems, scalability of parallel systems, isoefficiency function.
  3. Dense matrix algorithms, matrix-matrix multiplication, LU factorization and mapping techniques for load balancing.
  4. Sorting algorithms, sorting networks, mapping of sorting algorithms on different architectures, sorting on a GPU.
  5. Graph algorithms for dense graphs, minimum spanning tree, connected components.
  6. Algorithms for sparse graphs, maximal independent set, parallel formulations for shared address space and distributed memory.
  7. Dynamic programming, serial monadic/serial polyadic/nonserial monadic/ nonserial polyadic formulations.

References:

  • A. Grama, A. Gupta, G. Karypis, V. Kumar: Introduction to Parallel Computing, Second Edition, Addison Wesley, 2003.
  • G. Hager, G. Wellein: Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2011.
  • J. Reinders, J. Jeffers: Intel Xeon Phi Coprocessor High-Performance Programming, Newnes, 2013.
  • Z. Bäumelt, J. Dvořák, P. Šůcha, Z. Hanzálek, A Novel Approach for the Nurse Rerostering Problem based on a Parallel Algorithm In: European Journal of Operational Research. 2016.
  • P. Harish, P. J. Narayanan, Accelerating Large Graph Algorithms on the GPU Using CUDA, International Conference on High-Performance Computing, pp 197-208, 2007.
  • N. Satish, M. Harris and M. Garland, Designing efficient sorting algorithms for manycore GPUs, 2009 IEEE International Symposium on Parallel & Distributed Processing, Rome, 2009.
  • V. Boyer, D. El Baz, M. Elkihel, Solving knapsack problems on GPU, Computers & Operations Research, Volume 39, Issue 1, January 2012, Pages 42-47.


Linear Dynamical Systems

Examinators: prof. Kučera, prof. Šebek

  1. State representation of linear (time invariant, differential/difference) systems and its properties, such as internal/external stability, reachability/controllability, observability/constructibility, stabilizability/detectability. Various different definitions of these notions and their relationships.
  2. Standard forms of linear systems, their properties and applications. System invariants with respect to state, input, and output coordinate transformations, and state feedback/output injection.
  3. Transfer functions of linear systems and polynomial matrix fractions, relationship to state space representations. Smith form for polynomial matrices, Smith-McMillan form for rational matrices, poles and zeros of systems and transfer functions, left/right coprime polynomial matrices, row/column reduced polynomial matrices.
  4. Dynamics as a linear system invariant, various different expressions for dynamics, relationship to the structure of linear operators.
  5. Modification of dynamics via state feedback/output injection, Rosenbrock’s theorem, the proof of the theorem, and transfer function solution of the problem. 
  6. Linear quadratic regulator, problem formulation on a finite/infinite horizon, solvability conditions, state space solution, convergence to steady-state solutions, transfer function solution and its interpretation in terms of dynamics modification.
  7. Kalman filter, problem formulation on a finite/infinite horizon, solvability conditions, state space solution, convergence to steady-state solutions, transfer function solution and its interpretation in terms of dynamics modification.
  8. Linear quadratic gaussian control, problem formulation on a finite/infinite horizon, solvability conditions, state space solution, convergence to steady-state solutions, transfer function solution and its interpretation in terms of dynamics modification.
  9. Stabilization of linear systems using linear controllers, Youla-Kučera parameterization of all controllers that stabilize a given system, transfer function solution.
  10. Stabilization of linear systems using linear controllers, Youla-Kučera parameterization of all proper controllers that stabilize a given system, state space solution. Relationship to the linear quadratic gaussian control.

References:

  • P. J. Antsaklis, A. N. Michel, Linear Systems, Boston: Birkhäuser, 2006. ISBN-0 0-8176-4432-2.
  • T. Kailath, Linear Systems, Englewood Cliffs: Prentice-Hall, 1980. ISBN 0-13-536961-4.
  • V. Kučera, Analysis and Design of Discrete Linear Control Systems. Praha: Academia / London: Prentice Hall, 1991. ISBN 80-200-0252-9.


Nonlinear Systems and Their Control

Examiners: prof. Čelikovský, prof. Šebek

  1. State space description of nonlinear dynamical system with inputs and outputs for continuous and discrete time and its properties. Various types of nonlinear feedback (static, dynamic, state, output, continuous, discontinuous, smooth). Local and global description. Typical nonlinearities, examples of nonlinear systems and nonlinear phenomena. Differentiability with respect to initial conditions and parameters, sensitivity function.
  2. Nonlinear systems analysis. Methods of stability analysis using Lyapunov function. Exponential stability. Theorem characterizing the exponential stability via Lyapunov function properties. Influence of additive disturbances on asymptotically and exponentially stable system - vanishing and nonvanishing disturbances cases. LaSalle invariance principle for autonomous systems and its application. Inverse Lyapunov theorems and relation to stabilizability. Stability of nonautonomous systems.
  3. Structure and control of nonlinear systems with single input and single output (SISO). Relative degree. Lie derivative, inversion function theorem and its generalization. Input output linearization, zero dynamics, minimum phase property of SISO nonlinear systems. Necessary and sufficient conditions of exact feedback linearization, Lie bracket and Lie algebra of vector fields. Involutive distributions and their integrability. Relation of involutivity and the existence of relative degree. Controllability and observability of nonlinear systems, rank controllability condition. Observability conditions via Lie derivatives. All this for SISO systems.
  4. Structure and control of multi input multi output (MIMO) systems. Vector relative degree. Input output linearization, zero dynamics, and minimum phase property for MIMO systems. Decoupling via feedback. Rank controllability condition for MIMO systems.
  5. Duality between conditions for exact feedback linearization expressed via Lie algebras of vector fields and distributions and conditions expressed via differential forms ( the existence of virtual outputs with suitable vector relative degree).
  6. Observability and observers. Observability conditions via Lie derivatives. High gain observers, exact linearization using output injection, its necessary and sufficient conditions, and application of exact linearization using output injection to observers` construction.

References:

  • H. Khalil: Nonlinear Systems. Third Edition. Prentice Hall, New Jersey 2002.
  • A. Isidori: Nonlinear Control Systems. Springer Verlag, 1995.


Optimal control

Examiner: prof. Havlena, prof. Šebek, Dr. Hurák

  1. Static optimization. Minimization with equality constraints, Lagrange multipliers, necessary and sufficient optimality conditions. Hamiltonian equation, and its application for LQ controller design. Minimization with inequality constraints, Karush-Kuhn-Tucker theorem.
  2. Calculus of variation, optimization problems with fixed/free terminal time and constrained control input, Pontryagin Maximum Principle, bang-bang control, normality conditions, control of elementary dynamic systems (double integrator, harmonic oscillator). Dynamic programming, its application for LQ controller design. Hamilton-Jacobi-Bellman theorem.
  3. Stochastic dynamic programming, LQG controller design..
  4. Game theory, differential games.
  5. Singular solutions of optimization problems.
  6. Neighboring extremal paths, application of second variation.
  7. Numerical algorithms in optimization: first order methods (gradient), second order methods (Newton method and its approximation – quasi Newton, BFGS, conjugated gradients). Extensions for constrained problems: gradient projection, Lagrange methods, SQP, penalty functions, interior point methods.
  8. Riccati equation: properties, numerical solution. Spectral factorization, positive-real functions, inner-outer factorization, J-spectral factorization.
  9. Model/controller order reduction, balanced truncation/residualization. Gramian, balancing methods, minimization of Hankel norm. Lyapunov equation, properties, numerical solution.

References:

  • A. E. Bryson, Y. Ho: Applied Optimal Control. Hemisphere Publishing Corp., 1975.
  • D. P. Bertsekas: Dynamic Programming and Optimal Control (3rd ed.). Athena Scientific, 2005.
  • K. Zhou, J. C. Doyle, K. Glover: Robust and Optimal Control. Prentice Hall, 1996.


Robust control

Examiner: prof. Šebek, Dr. Hurák

  1. Uncertainties in physical parameters: classification, Bialas' theorem for one-parametric uncertainties, Kharitonov theorem for interval plants, zero exclusion principle, mapping theorem, more complicated structures.
  2. Hankel, Toeplitz and Hankel-Toeplitz mixed operator, Nehari's theorem.
  3. Formulation of the general problem of H-infinity optimal control: generalized plant, linear fractional transformation (LFT), four fundamental problems: full information (FI), disturbance feedforward (DF), full control (FC) and output estimation (OE).
  4. Solution of the H-infinity optimal control problem using Riccati equations.
  5. Robust stabilization of systems with non-coprime fractional uncertainty.
  6. Fundamentals of linear matric inequalities (LMI) in control: Bounded real lemma, KYP lemma. Solving the H-infinity optimal control problem using LMIs.
  7. Interpolation approach to control design: Nevanlinna-Pick interpolation.
  8. Design of robust controllers of fixed order.
  9. LPV (Linear Parameter Varying) control.
  10. Passivity, dissipative system, energy-based control.

References:

  • K. Zhou, J.C. Doyle, K. Glover: Robust and Optimal Control. Prentice Hall, 1996.
  • B. A. Francis: A Course in H-inf Control Theory. Springer, 1987.
  • M. Green and D. J. N. Limebeer: Linear Robust Control. Prentice Hall, London, 1994.
  • S.P. Bhattacharyya, H. Chapellat, L.H. Keel: Robust Control - The Parametric Approach. Prentice-Hall, 1996.
  • R. Barmish: New Tools for Robustness of Linear Systems. Prentice Hall, 1993.


Cooperative Control of Multi-agent Systems 
 

Examiner: Dipl.Ing. Kristian Hengster-Movric, Ph.D., Prof. Ing. Michael Sebek, DrSc.; Ing. Zdenek Hurak, Ph.D.

  1. Graphs, topological properties: undirected, directed, connected, irreducible, reducible, tree, spanning tree, spanning forest
  2. Algebraic graph theory, adjacency matrix, Laplacian matrix, Frobenius form. Eigenvalues and eigenvectors of graph Laplacians and connection to graph topology
  3. Consensus and synchronization. Discrete-time and continuous-time consensus algorithms, simple one-dimensional agents, single-integrators. Pinning control.
  4. Synchronizing regions for general identical agents, complex matrix pencils, Lyapunov estimates
  5. Riccati design for state-synchronization control of identical LTI agents, in discrete and continuous-time
  6. Output synchronization for heterogeneous agents, passivity based design, internal-model-principle based design

References:

  • Lewis, F.L., Zhang, H., Hengster-Movric, K., Das , A.: Cooperative Control of Multi-Agent Systems: Optimal and Adaptive Design Approaches, Springer-Verlag, London 2014, ISBN 978-1-4471-5573-7,DOI 10.1007/978-1-4471-5574-4
  • Olfati-Saber R, Fax JA, Murray RM: Consensus and Cooperation in Networked Multi-Agent Systems (invited paper). Proceedings of the IEEE 2007;95(1): 215-233. DOI: 10.1109/JPROC.2006.887293
  • Zhang H, Lewis FL: Optimal Design for Synchronization of Cooperative Systems: State Feedback, Observer and Output Feedback, IEEE Transactions on Automatic Control 2011; 56(8): 1948-1953. DOI: 10.1109/TAC.2011.2139510
  • Hengster-Movric, K., Keyou, Y., Lewis, F.L., Xie, L.: Synchronization of discrete-time multi-agent systems on graphs using Riccati design, Automatica, Feb 2013, vol. 49, no. 2, pp. 414-423. DOI:10.1016/j.automatica.2012.11.038.
  • Chopra, N., Spong, M.: (2006) Passivity-based Control of Multi-agent Systems, Advances in Robot Control, Springer, pp 107-134.
  • Wieland, P., Sepulchre, R., Allgower, F. An internal model principle is necessary and sufficient for linear output synchronization, Automatica 47 (2011), pp. 1068-1074.
     

Flexible structures control
 

Examiner: Doc. Ing. Martin Hromcik, Ph.D.; Prof.Ing. Michael Sebek, DrSc.; Ing. Zdenek Hurak, Ph.D.; Dipl.Ing. Kristian Hengster-Movric, Ph.D.

  1. Flexible structures modeling. Multibody systems. Finite element methods. Second order structural models and state space models.
  2. Nodal and modal forms. Proportional and Rayleigh damping. Natural frequencies. Input and output mode-shapes. Poles and zeros patterns.
  3. Controllability and observability Grammians: special properties for flexible structures models. Balanced representations of flexible structures. Model order reduction techniques: modes truncation, residualization, balanced truncation.
  4. Optimal sensors and actuators placement. Energy-based methods (Grammians-based, Gawronski’s method). Information-based methods (Fisher information matrix, EFI).
  5. Decentralized control. Direct velocity feedback. Positive position feedback. Collocated and non-collocated control.
  6. Optimal and robust control design methods for active damping of flexible structures. LQG, pole placement, H-infinity methods.

References:

  • Wodek Gawronski, Advanced Structural Dynamics and Active Control of Structures, Springer, Mechanical Engineering Series, ISBN: 978-0-387 -40649-7

  • André Preumont, Vibration Control of Acti ve Structures, 3rd edition, Springer, ISBN: 978-94-007-2032-9

 
 
Responsible person: RNDr. Patrik Mottl, Ph.D.