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
- 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.
- 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ů.
- 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í.
- 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.
- 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ů).
- 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
- 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í.
- Analytický model paralelních programů: cenově-optimální paralelní systémy, škálovatelnost paralelních systémů, isoefektivní funkce.
- Maticové algoritmy, násobení matice s maticí, LU rozklad a způsoby mapování výpočtů pro vyvážení zátěže.
- Algoritmy pro řazení, řadící sítě, mapování řadících algoritmů na různé architektury, řazení na GPU.
- Grafové algoritmy: minimální kostra grafu, komponenty souvislosti.
- 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í.
- 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
- Složitost problémů. Třídy P, NP, NP-úplná, NP-obtížná, PSPACE, EXPTIME, EXPSPACE.
- Celočíselné lineární programování - algoritmy a formulace kombinatorických problémů.
- Nejkratší cesty v grafu - algoritmy a formulace kombinatorických problémů.
- Toky a řezy v sítích. Párování v bipartitních grafech. Algoritmy (Successive Shortest Path, Maďarský algoritmus). Multi-komoditní toky.
- Problém batohu, pseudo-polynomiální algoritmus a aproximační schéma.
- 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.
- 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
- 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í.
- 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 .
- Problémy s dedikovanými procesory. Algoritmy pro Flow shop a Job shop.
- Rozvrhování projektů (Project scheduling) s temporálními omezeními. Převody problémů. ILP formulace.
- 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.
- 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
- 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.
- ARX, ARMAX a OE model, rovnice pro jednokrokový prediktor. Statistické metody identifikace, lineární a pseudolineární regrese.
- Jednorázový a rekurzívní výpočet parametrů ARX modelu. Statistiky a jejich interpretace, zadání apriorní informace.
- Sledování časově proměnných parametrů, metody zapomínání, regularizované a omezené zapomínání.
- Lineární stochastický systém, vývoj stavu, Ljapunovova rovnice.
- Autokorelační funkce, výkonová spektrální hustota, racionální spektra, spektrální faktorizace.
- Diskrétní Kalmanův filtr. Vlastnosti chyby predikce. Inovace, tvarovací a bělicí filtr. Aplikace Kalmanova filtru pro barevné šumy.
- 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.
- Numerická implementace metod odhadování a filtrace, využití faktorizované kovarianční matice, algoritmus dyádové redukce.
- 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
- 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.
- 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.
- 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é.
- 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.
- 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ů.
- 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.
- 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.
- Ří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.
- 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ů.
- 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
- 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.
- 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.
- Stochastické dynamické programování.
- Teorie her, diferenciální hry.
- Singulární problémy.
- Metoda sousedních extremál a použití druhé variace.
- 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).
- Riccatiho rovnice: vlastnosti, numerické řešení, spektrální faktorizace, pozitivně reálné funkce, "inner" funkce, "inner-outer" faktorizace, J-spektrální faktorizace.
- 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
- 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.
- Hankelův, Toeplitzův a Hankel-Toeplitzův smíšený operátor, Nehariho věta.
- 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).
- Odvození řešení H-inf problému coby řešení dvou Riccatiho rovnic.
- Robustní stabilizace systému s nesoudělnou podílovou neurčitostí.
- 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í.
- Interpolační přístup k návrhu řízení: problém Nevanlinna-Pick a jeho řešení.
- Návrh robustních regulátorů zadaného řádu.
- LPV (Linear parameter varying) řízení.
- 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.
- Grafy, topologické vlastnosti: orientovaný graf, neorientovaný,souvislý, silně a slabě souvislý, strom, kostra, spanning forest
- Algebraická teorie grafů, matice sousednosti, Laplaceova matice, Frobeniova forma. Vlastní čísla a vektory Laplaceovy matice a jejich souvislost s topologií grafu
- 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)
- Oblast synchronizace pro síť identických agentů, komplexní svazek matic (matrix pencils), odhad oblasti synchronizace pomocí lyapunovských funkcí
- Návrh pomocí Riccatiho rovnice pro stavovou synchronizaci identických LTI agentů, ve spojitém i diskrétním čase
- 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.
- Modelování flexibilních systémů. Multibody systémy. Metoda konečných prvků. Strukturální modely druhého řádu a stavové modely.
- Nodální a modální tvar. Proporcionální a Rayleighovo tlumení. Přirozené frekvence. Vstupní a výstupní vlastní tvary. Póly a nuly.
- Gramiány pozorovatelnosti a řiditelnosti: zvláštní vlastnosti pro flexibilní struktury. Vyvážená realizace. Metody redukce řádu modelu.
- Optimální umístění aktuátorů a senzorů. Energetické metody (gramiány, Gawronskiho metoda). Informační metody (EFI, Fisherova informační matice).
- Decentralizované řízení. Direct velocity feedback. Positive position feedback. Kolokované a nekolokované řízení.
- 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