Tematické okruhy otázek ke státní doktorské zkoušce

ŘÍDICÍ TECHNIKA A ROBOTIKA

Nelineární systémy a jejich řízení

Zkouší: prof. Čelikovský, prof. Šebek

  1. Stavový popis nelineárního dynamického systému se vstupy a výstupy ve spojitém a diskrétním čase a jeho vlastnosti. Různé typy nelineární zpětné vazby (statická, dynamická, stavová, výstupní, spojitá, nespojitá, hladká). Lokální versus globální popis. Typické nelinearity, příklady nelineárních systémů a nelineární jevy. Existence řešení, spojitá závislost na počátečních podmínkách a parametrech. Diferencovatelná závislost na počátečních podmínkách a parametrech, citlivostní funkce.
  2. Analýza nelineárních systémů. Metody analýzy stability pomocí Ljapunovské funkce. Exponenciální stabilita, Věta o exponenciální stabilitě pomocí Ljapunovské funkce. Vliv aditivních poruch na asymptoticky, resp. exponenciálně stabilní nelineární systém - případ zanikajících a nezanikajících poruch. Princip invariantnosti LaSalle pro autonomní systémy a jeho využití. Obrácené Ljapunovské věty a souvislost se stabilizovatelností. Stabilita neautonomních systémů.
  3. Struktura a řízení nelineárních systémů s jedním vstupem a jedním výstupem. Relativní stupeň. Lieova derivace, věta o inverzní funkci a věta o doplnění souboru nezávislých funkcí do úplné změny souřadnic prostoru. Linearizace typu vstup-výstup, dynamika nulového výstupu, minimalita ve fázi. Nutné a postačující podmínky pro exaktní linearizaci, Lieova závorka a Lieova algebra vektorových polí. Involutivní distribuce a její integrabilta. Souvislost s existencí relativního stupně a její důkaz. Řiditelnost a pozorovatelnost nelineárních systémů, podmínka hodnosti pro řiditelnost (rank controlability condition). Podmínka pozorovatelnosti pomocí Lieových derivací.
  4. Struktura a řízení nelineárních systémů s více vstupy a výstupy. Vektorový relativní stupeň. Linearizace typu vstup-výstup, dynamika nulového výstupu, minimalita ve fázi. Decoupling (odstranění vzájemných interakcí mezi vstupy). Podmínka hodnosti pro řiditelnosti (rank controllability condition) pro systémy s více vstupy.
  5. Dualita podmínek exaktní linearizace vyjádřených Lieovými algebrami vektorových polí a distribucemi, a podmínek vyjádřených přesnými diferenciálními formami (existencí dostatečného počtu virtuálních linearizujícíh výstupů).
  6. Pozorovatelnost a rekonstrukce. Podmínky pozorovatelnosti pomocí Lieových derivací. Pozorovatelé s vysokým zesílením, linearizace pomocí výstupní injekce, její nutné a postačující podmínky, využití pro konstrukci pozorovatelů.

Literatura:

  • H. Khalil: Nonlinear Systems. Third Edition. Prentice Hall, New Jersey 2002.
  • A. Isidori: Nonlinear Control Systems. Springer Verlag, 1995.
  • S. Čelikovský: Nelineární Systémy. ČVUT, 2006. Pouze Kapitola 6, "Pokročilé metody nelineárního řízení", která je určena pro doktorské studium.

Paralelní algoritmy

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

  1. Komunikační operace pro paralelní algoritmy (one-to-all broadcast, all-to-one reduction, all-to-all broadcast/reduction, all-reduce, prefix-sum, scatter, gather), analýza ceny komunikačních operací pro různé topologie sítí.
  2. Analytický model paralelních programů: cenově-optimální paralelní systémy, škálovatelnost paralelních systémů, isoefektivní funkce.
  3. Maticové algoritmy, násobení matice s maticí, LU rozklad a způsoby mapování výpočtů pro vyvážení zátěže.
  4. Algoritmy pro řazení, řadící sítě, mapování řadících algoritmů na různé architektury, řazení na GPU.
  5. Grafové algoritmy: minimální kostra grafu, komponenty souvislosti.
  6. Algoritmy pro řídké grafy: maximální nezávislá množina (maximal independent set), paralelní formulace pro architektury se sdíleným paměťovým prostorem a distribuovanou pamětí.
  7. Dynamické programování, formulace typu: serial monadic/serial polyadic/nonserial monadic/ nonserial polyadic.

Literatura:

  • 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

 

Kombinatorická Optimalizace

Zkouší: prof. Hanzálek, Dr. Šůcha

  1. Složitost problémů. Třídy P, NP, NP-úplná, NP-obtížná, PSPACE, EXPTIME, EXPSPACE.
  2. Celočíselné lineární programování - algoritmy a formulace kombinatorických problémů.
  3. Nejkratší cesty v grafu - algoritmy a formulace kombinatorických problémů.
  4. Toky a řezy v sítích. Párování v bipartitních grafech. Algoritmy (Successive Shortest Path, Maďarský algoritmus). Multi-komoditní toky.
  5. Problém batohu, pseudo-polynomiální algoritmus a aproximační schéma.
  6. Problém obchodního cestujícího. Neexistence k-aproximačního algoritmu pro obecný TSP. Christofidesův algoritmus. Lokální prohledávání k-OPT.
  7. Programování s omezujícími podmínkami.

Literatura:

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

Rozvrhování

Zkouší: prof. Hanzálek, Dr. Šůcha

  1. Problémy s jedním procesorem. Bratleyův algoritmus větví a mezí. Řešení problému 1/prec/Suma-wjCj metodou větví a mezí s využitím odhadu pomocí LP. EDD a EDF algoritmy; důkaz optimality a problém s relacemi následností.
  2. Problémy s paralelními identickými procesory. Relaxační, aproximační a pseudopolynomiální algoritmy pro problém P//Cmax. Optimální algoritmy pro P2/prec,Pj=1/Cmax a P2/pmtn,prec/Cmax .
  3. Problémy s dedikovanými procesory. Algoritmy pro Flow shop a Job shop.
  4. Rozvrhování projektů (Project scheduling) s temporálními omezeními. Převody problémů. ILP formulace.
  5. Rozvrhování v operačních systémech reálného času. Periodické rozvrhování. Utilisation bound pro EDF a Rate Monotonic na rozvrhovači s fixními prioritami.
  6. Cyklické rozvrhování. ILP formulace. Algoritmy pro minimální dobu cyklu.

Literatura:

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

Odhadování a filtrace

Zkouší: prof. Havlena

  1. Bayesovský přístup k popisu neurčitosti, model dynamického systému, přirozené podmínky řízení, pravděpodobnostní definice stavu. Věrohodnostní funkce, statistiky.
  2. ARX, ARMAX a OE model, rovnice pro jednokrokový prediktor. Statistické metody identifikace, lineární a pseudolineární regrese.
  3. Jednorázový a rekurzívní výpočet parametrů ARX modelu. Statistiky a jejich interpretace, zadání apriorní informace.
  4. Sledování časově proměnných parametrů, metody zapomínání, regularizované a omezené zapomínání.
  5. Lineární stochastický systém, vývoj stavu, Ljapunovova rovnice.
  6. Autokorelační funkce, výkonová spektrální hustota, racionální spektra, spektrální faktorizace.
  7. Diskrétní Kalmanův filtr. Vlastnosti chyby predikce. Inovace, tvarovací a bělicí filtr. Aplikace Kalmanova filtru pro barevné šumy.
  8. Náhodná procházka, Wienerův proces, diskretizace spojitých lineárních stochastických systémů. Spojitý Kalmanův filtr s diskrétním měřením.
  9. Numerická implementace metod odhadování a filtrace, využití faktorizované kovarianční matice, algoritmus dyádové redukce.
  10. Lokální a globální aproximace nelineárních/negaussovských filtrů. Metoda bodových mas, metoda Monte Carlo.

Literatura:

  • 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

Lineární dynamické systémy

Zkouší: prof. Kučera, prof. Šebek

  1. Stavová reprezentace lineárních (časově invariantních diferenciálních/diferenčních) systémů a její vlastnosti jako vnitřní stabilita, vnější stabilita, dosažitelnost/řiditelnost, pozorovatelnost/konstruovatelnost, stabilizovatelnost, detekovatelnost. Různé definice uvedených pojmů a jejich souvislosti.
  2. Standardní tvary lineárních systémů, jejich vlastnosti a použití. Invarianty systému vůči změně báze stavového prostoru, prostoru vstupů, prostoru výstupů, stavové zpětné vazbě a injekci výstupu do stavu.
  3. Vyjádření přenosu lineárního systému ve tvaru maticových polynomiálních zlomků, souvislost se stavovou reprezentací systému. Smithův tvar pro polynomiální matice, Smith-McMillanův tvar pro racionální matice, nuly a póly systému a přenosu, polynomiální matice zprava/zleva nesoudělné a po sloupcích/řádcích redukované.
  4. Dynamika jako invariant lineárního systému, různé způsoby jejího vyjádření, souvislost se strukturou lineárního operátoru.
  5. Změna dynamiky lineárního systému stavovou zpětnou vazbou/injekcí výstupu do stavu, Rosenbrockova věta, její důkaz, řešení úlohy pomocí přenosů.
  6. Lineárně kvadratický regulátor, formulace úlohy na konečném i nekonečném intervalu, existence řešení, řešení pomocí stavové reprezentace, konvergence k ustálenému řešení, ustálené řešení pomocí přenosů, jeho interpretace jako změna dynamiky systému.
  7. Kalmanův filtr, formulace úlohy na konečném i nekonečném intervalu, existence řešení, řešení pomocí stavové reprezentace, konvergence k ustálenému řešení, ustálené řešení pomocí přenosů, jeho interpretace jako změna dynamiky systému.
  8. Řízení LQG, formulace úlohy na konečném i nekonečném intervalu, existence řešení, řešení pomocí stavové reprezentace, konvergence k ustálenému řešení, ustálené řešení pomocí přenosů, jeho interpretace jako změna dynamiky systému.
  9. Stabilizace lineárního systému lineárním regulátorem, Youla-Kučerova parametrizace všech stabilizujících regulátorů/všech stabilizujících regulátorů s ryzím přenosem, řešení úlohy pomocí přenosů.
  10. Stabilizace lineárního systému lineárním regulátorem, Youla-Kučerova parametrizace všech stabilizujících regulátorů s ryzím přenosem, řešení úlohy pomocí stavové reprezentace. Souvislost s řízením LQG.

Literatura:

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

Optimální řízení

Zkouší: prof. Havlena, prof. Šebek, Dr. Hurák

  1. Základy statické optimalizace: minimalizace s omezujícími podmínkami typu rovnost a Lagrangeovy multiplikátory, Hamiltonián, nutné a postačující podmínky minima, použití pro odvození regulátoru pro lineární systém minimalizující kvadratické kritérium, minimalizace s omezujícími podmínkami typu nerovnost a Karush-Kuhn-Tuckera věta.
  2. Problémy s volným koncovým časem a omezeným akčním zásahem: Pontrjagynův princip maxima (minima), bang-bang řízení, podmínky normality, odvození řízení pro základní systémy (dvojný integrátor, harmonický oscilátor) Dynamické programování a jeho použití pro odvození LQ optimálního řízení. Věta Hamilton-Jacobi-Bellman.
  3. Stochastické dynamické programování.
  4. Teorie her, diferenciální hry.
  5. Singulární problémy.
  6. Metoda sousedních extremál a použití druhé variace.
  7. Numerické algoritmy pro řešení úloh optimálního řízení: metody prvního řádu (gradientní), druhého řádu (Newtonova metoda a její aproximace: kvazi Newton, BFGS, konjugované gradienty). Další metody: projekce gradientu (= rozšíření metod prvního řádu), Lagrangeovské metody / SQP (= rozšíření metod druhého řádu), pokutové funkce/interior point (= převedení na neomezený problém).
  8. Riccatiho rovnice: vlastnosti, numerické řešení, spektrální faktorizace, pozitivně reálné funkce, "inner" funkce, "inner-outer" faktorizace, J-spektrální faktorizace.
  9. Redukce řádu modelu i regulátoru: useknutí a residualizace pro balancovanou realizaci, různé metody balancování, minimalizace Hankelovy normy rozdílu. Ljapunovova rovnice: vlastnosti, numerické řešení.

Literatura:

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

Robustní řízení

Zkouší: prof. Šebek, prof. Henrion, Dr. Hurák, Dr. Hromčík

  1. Parametrické neurčitosti: klasifikace, Bialasova věta pro jednoparametrické neurčitosti, Charitonovova věta pro intervalové systémy, věta o vyloučení nuly, mapping theorem, složitější struktury.
  2. Hankelův, Toeplitzův a Hankel-Toeplitzův smíšený operátor, Nehariho věta.
  3. Formulace obecného problému H-inf řízení: zobecněný systém, lineární podílová transformace (LFT), čtyři základní problémy: FI (full information), DF (disturbance feedforward), FC (full control), OE (output estimation).
  4. Odvození řešení H-inf problému coby řešení dvou Riccatiho rovnic.
  5. Robustní stabilizace systému s nesoudělnou podílovou neurčitostí.
  6. Základní lineární maticové nerovnosti v řízení: Bounded real lemma, KYP lemma. Řešení H-inf problému pomocí lineárních maticových nerovností.
  7. Interpolační přístup k návrhu řízení: problém Nevanlinna-Pick a jeho řešení.
  8. Návrh robustních regulátorů zadaného řádu.
  9. LPV (Linear parameter varying) řízení.
  10. Pasivita vs. Robustnost, disipativní systémy.

Literatura:

  • 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.

 

Kooperativní řízení multiagentních systémů

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

  1. Grafy, topologické vlastnosti: orientovaný graf, neorientovaný,souvislý, silně a slabě souvislý, strom, kostra, spanning forest
  2. Algebraická teorie grafů, matice sousednosti, Laplaceova matice, Frobeniova forma. Vlastní čísla a vektory Laplaceovy matice a jejich souvislost s topologií grafu
  3. Konsensus a synchronizace. Diskrétní a spojitý konsensus – algoritmy, případ jednoduchých jednorozměrných agentů, případ kdy agentem je jeden integrátor, připíchnuté řízení (pinning control)
  4. Oblast synchronizace pro síť identických agentů, komplexní svazek matic (matrix pencils), odhad oblasti synchronizace pomocí lyapunovských funkcí
  5. Návrh pomocí Riccatiho rovnice pro stavovou synchronizaci identických LTI agentů, ve spojitém i diskrétním čase
  6. Výstupní synchronizace pro sítě heterogenních agentů, návrh založený na pasivitě, návrh použitím principu vnitřního modelu

Literatura:

  • 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.

 

Řízení flexibilních systémů

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

  1. Modelování flexibilních systémů. Multibody systémy. Metoda konečných prvků. Strukturální modely druhého řádu a stavové modely.
  2. Nodální a modální tvar. Proporcionální a Rayleighovo tlumení. Přirozené frekvence. Vstupní a výstupní vlastní tvary. Póly a nuly.
  3. Gramiány pozorovatelnosti a řiditelnosti: zvláštní vlastnosti pro flexibilní struktury. Vyvážená realizace. Metody redukce řádu modelu.
  4. Optimální umístění aktuátorů a senzorů. Energetické metody (gramiány, Gawronskiho metoda). Informační metody (EFI, Fisherova informační matice).
  5. Decentralizované řízení. Direct velocity feedback. Positive position feedback. Kolokované a nekolokované řízení.
  6. Optimální a robustní metody návrhu řízení pro activní tlumení flexibilních struktur. LQG, umístění pólů, H-nekonečno metody.

Literatura:

  • 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

Za obsah odpovídá: RNDr. Patrik Mottl, Ph.D.