IV120 Spojité a hybridní systémy Uvod do problematiky a informace o kurzu David Šafránek Jiří Barnat Jana Fabriková Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky. ■Hf^SlMI NVESTICE DO ROZVOJE VZDĚLÁVÁNÍ Obsah a cíle předmětu • pochopení základních pojmů obecné teorie systémů • pojem dynamického systému • problematika lineárních a nelineárních spojitých systémů • pojem hybridního systému » základní metody analýzy o analytické metody • simulace • základní pojmy teorie řízení • aplikace v systémové biologii • elementární praktická znalost - cvičení • Octave, SpaceEx, GNA IV120 Úvod do problematiky a informace o kurzu str. 2/46 Co získám absolvováním? • pochopení pojmů a problémů z oblasti dynamických systémů • schopnost použít procvičované nástroje • schopnost použít základní analytické techniky • pochopení základního aparátu systémových věd • schopnost formálně zapsat spojitý/hybridní systém • rozšíření vědomostí v oblasti komplexních systémů IV120 Úvod do problematiky a informace o kurzu str. 3/46 Co se zde nenaučím. • podrobné formální odvození teoretických východisek • podrobnou znalost nástrojů • podrobnou znalost výpočetních algoritmů • schopnost systémového myšlení o ... IV120 Úvod do problematiky a informace o kurzu Osnova • Úvod do teorie systémů. • Definice a vlastnosti dynamického systému. • Lineárni spojité systémy a jejich analýza. • Nelineárni spojité systémy a jejich analýza. • Hybridní systémy a jejich analýza. • Hybridní kvocienty nelineárních spojitých systémů. • Parametrizace, neurčitost, identifikovatelnost. • Srovnávání a robustnost chování; dekompozice. • Úvod do teorie řízení. • Aplikace v biologii. IV120 Úvod do problematiky a informace o kurzu str. 5/46 Kontext v rámci ostatních předmětů Zařazen do povinně volitelných předmětů magisterského programu Bioinformatika. • PB050 Modelování a predikce v systémové biologii • praktické seznámení s dynamickými modely v systémové biologii • povrchní úroveň - důraz na intuitivní pochopení pojmů • aplikační doplněk (předch. absolvování je výhodou) • semestrální projekty • PA052 Úvod do systémové biologie » úvod do aplikační oblasti systémové biologie • přehledový kurz » PA054 Formální modely v systémové biologii • alternativní možnosti sémantiky (operační pohled) • formální metody pro biologické dynamické systémy • semestrální projekty IV120 Úvod do problematiky a informace o kurzu str. 6/46 Kontext v rámci ostatních předmětů • IV109 Modelování a simulace (doc. R. Pelánek, Ph.D.) • uchopení systémového přístupu • mentální cvičení systémového myšlení » modelování a simulace na obecné a přehledové úrovni • IA158 Real time systems (RNDr. T. Brázdil, Ph.D.) • návrh, implementace a verifikace systémů reálného času • časové automaty » nástroj UPPAAL » PA190 Digital Signál Processing • diskrétní technické (lineární) systémy • zpracování digitálních signálů • přenos do frekvenčního spektra IV120 Úvod do problematiky a informace o kurzu str. 7/46 Kontext v rámci ostatních předmětů • DBLOK2 Formal Methods for Complex Systems (Dr. L. Bortolussi, Ph.D.) • pokročilé formální metody • stochastický hybridní model • hybridní limity stochastických modelů o IV120 Úvod do problematiky a informace o kurzu str. 8/46 Literatura Základní literatura: » ŠTECHA, Jan a HAVLENA, Vladimír. Teorie dynamických systémů: přednášky. 2. vyd. Praha: Vydavatelství ČVUT, 2002. • VRIES, Gerda de. A course in mathematical biology quantitative modeling with mathematical and computational methods. Philadelphia, Pa.: Society for Industrial and Applied Mathematics, 2006. Doplňující literatura: • J.H. van Schuppen. Control and System Theory of Positive Systems, CWI Lecture notes, 2007. • P. Tabuada. Verification and Control of Hybrid Systems: A Symbolic Approach. Springer, 2009. IV120 Úvod do problematiky a informace o kurzu str. 9/46 Hodnocení • semestrální projekt - 50 bodů • seznámení s konkrétním modelem • provedení analýzy (stabilita, dosažitelnost) • zkouška - 50 bodů • na konci výukového období bude vydán seznam pojmů, které budou zkoušeny • zkouška bude zahrnovat vysvětlení 2 pojmů • kolokvium o stačí získat 30 bodů (není nutno absolvovat ústní zkoušku) IV120 Úvod do problematiky a informace o kurzu str. 10/46 Sekce IV120 Úvod do problematiky a informace o kurzu str. 11/46 Základní pojmy Systémový přístup » obecný pojem systému jako prostředníka porozumění složitých (komplexních) jevů • myšlenku zavedl von Bertalanffy v 30. letech 20. stol. • složitost vzniká silnou nezanedbatelnou interakcí uvnitř celku (mezi složkami) a vně (interakce s okolím) • rozvoj v 50. a 60. letech (Kálmán a Mesarovič) • podstatou je chápání jevů komplexně ve vnitřních i vnějších souvislostech (srovnej s mechanickým pohledem) IV120 Úvod do problematiky a informace o kurzu str. 12/46 Základní pojmy Systémová věda • samostatný teoretický vědní obor definující obecné paradigma • předmětem je studium systémů definovaných na různých objektech » systémové teorie • teorie řízení, kybernetika (dříve) • teorie systémů • systémové aplikace • systémová biologie • systémová chemie • systémové inženýrství • systémová psychologie • .. . IV120 Úvod do problematiky a informace o kurzu str. 13/46 Základní pojmy Pojem objektu • předmětem zkoumání je vymezená oblast objektivní reality -objekt • např. živá buňka, skákající míček, jaderná elektrárna, výrobní linka, el. obvod, . .. • zbytek objektivní reality (doplněk objektu) nazýváme okolí • hranice typicky není přesně vymezitelná (přírodní objekty) • objekt je zkoumán prostřednictvím pozorovatelných/měřitelných veličin • vztahy mezi veličinami jsou determinovány vlastnostmi objektu IV120 Úvod do problematiky a informace o kurzu str. 14/46 Základní pojmy Pojem systému « systém je definován na objektu výběrem veličin a sledovaných vlastností (srovnej s pojmem systému v abstraktních vědách -veličiny i vztahy mezi nimy uvedeny explicitně) • systém je určen: • množinou veličin • rozlišovací úrovní - přesnost pozorovaní (např. frekvence vzorkovaní) • chovaním - vztahy mezi veličinami • množina hodnot všech veličin sledovaných po danou dobu zkoumání popisuje aktivitu (běh) systému • např. systém na objektu živé buňky - veličiny jsou koncentrace detekovatelných látek měřené s rozlišovací schopností použité technologie, aktivita takového systému vykazuje např. zvýšení koncentrace některých proteinů při odebrání určitého nutrientu, chováním je pak tento vztah proteinů a nutrientu IV120 Úvod do problematiky a informace o kurzu str. 15/46 Základní pojmy Pojem systému • při zkoumání systému se snažíme dekomponovat chování • rozložení každého komplexního vztahu na množinu jednodušších (dílčích) vztahů • dílčí vztahy jsou asociovány se složkami systému (podsystémy, tzv. elementy) • celkové chování systému je určeno: • chováním jednotlivých elementů • vzájemnými kompozicemi chování elementů • elementy jsou spojeny sdílenými veličinami, tato spojení determinují vazby uvnitř systému • toto členění určuje strukturu systému » okamžitou hodnotu všech veličin nazýváme stavem systému IV120 Úvod do problematiky a informace o kurzu str. 16/46 Základní pojmy Pojem systému - příklad Uvažujme systém definovaný na objektu populace živých buněk. Veličiny velikost populace, koncentrace nutrientů, teplota Aktivita vývoj populace, změna stavu prostředí Chování vztah mezi veličinami prostředí a velikostí populace Elementy proteiny a metabolity různých typů, DNA, RNA, příslušné vnitřní veličiny (koncentrace), vazby - transkripční aktivace/represe, katalýza, apod. IV120 Úvod do problematiky a informace o kurzu str. 17/46 Základní pojmy Možné definice systému • Systém je dán množinou n veličin (tzv. proměnných) S = {Xi, ...,X„}, kde každá z proměnných má definovánu množinu přípustných hodnot: V/ G {1,n}.T>(Xj) = {x/i,x/2, ...,xin} kde ry určuje velikost příslušné množiny (teoreticky mohou být definovány tyto množiny i jako spojité, prakticky se uvažují vždy diskrétní vzhledem k rozlišovací schopnosti pozorování). Příklady • populace živých buněk - fáze populace (exponenciální, stacionární), hmotnost populace měřená s určitou přesností • systém počasí v dané lokaci - čas měření (ráno, večer), teplota vzduchu měřená s danou přesností, relativní vlhkost, .. . IV120 Úvod do problematiky a informace o kurzu str. 18/46 Základní pojmy Možné definice systému » Zdrojový systém lze doplnit daty popisujícími jeho aktivity. • S tímto rozšířením je systém definován jako uspořádaná množina dvojice proměnných a tzv. pole aktivit: S = ({X,-,/ = l,2,...,n},[x,-ř]) kde [x/,t],x/it G V{Xi) je matice (pole) aktivit, ř £ 7 značí čas měření v časové množině T. Příklady • populace živých buněk - fáze populace a hmotnost populace zachycená při experimentu trvajícím určitou dobu • systém turbovrtulového motoru - časová řada hodnot veličin při provedeném letu (palivo, otáčky, nadmořská výška) IV120 Úvod do problematiky a informace o kurzu str. 19/46 Základní pojmy Možné definice systému • Zdrojový systém lze doplnit popisem vztahů mezi veličinami -generativním předpisem. • Tímto rozšířením je zdrojový systém S = {Xi, ...,X„} rozšířen o relaci U C P(Xi) x V(X2) x ... x V(Xn). Relace může být určena např. diferenčními nebo diferenciálními rovnicemi. o Příklady • katalytická reakce (přeměna substrátu na produkt) d S VmaxS dP VmaxS dt K + S dt K + S • S ... koncentrace substrátu » P ... koncentrace produktu » K, k, Vmax ■■■ konstanty zachycující vlastnosti enzymu a substrátu IV120 Úvod do problematiky a informace o kurzu str. 20/46 Základní pojmy Možné definice systému Další možnosti definice systému jsou: (1) strukturální: pomocí elementu a vazeb mezi nimi (2) stavově prechodová: systém určen množinou stavů a prechodu mezi nimi Příklady (1) systém udržování hladiny v nádrži - elementy: snímač výšky hladiny, čerpadlo, regulátor otáček čerpadla (2) systém světelné křižovatky - stavy jsou jednotlivé konfigurace světel s jasně definovanými přechody IV120 Úvod do problematiky a informace o kurzu str. 21/46 Základní pojmy Kauzální vztahy v systémech • nezávislé veličiny - veličiny produkované okolím, které jsou příčinou jevů v systému » závislé veličiny - veličiny produkované systémem, odvozené z nezávislých veličin a chování systému • časová orientace (tzv. směr kauzality) je dán uspořádáním množiny {příčina, následek} • u fyzikálních systémů (konečná rychlost) příčina vždy předchází následek IV120 Úvod do problematiky a informace o kurzu str. 22/46 Základní pojmy Pojem řízeného systému • jsou-li separovatelné veličiny produkované okolím od veličin produkovaných systémem, používame členění na vstupní a výstupní veličiny (zkráceně vstupy a výstupy systému) • příkladem jsou technické systémy (např. el. obvody) • jelikož vstupy ovlivňují chování (a aktivitu) systému, hovoříme o vstupních veličinách jako o řídících veličinách • systémy s neprázdnou množinou řídících (vstupních) veličin nazýváme řízené systémy, v opačném případě hovoříme o neřízených systémech (někdy také volné nebo neutrální systémy) • srovnej systémy např. v ekonomii nebo meteorologii se systémy v inženýrství IV120 Úvod do problematiky a informace o kurzu str. 23/46 Základní pojmy Základní atributy systémů • otevřenost - se separovatelností vstupů/výstupů souvisí charakter vztahu systému s okolím • uzavřený systém — neřízený systém • otevřený systém — řízený systém • ohraničenost - ohraničený systém má konečnou množinu veličin (konečný řád) o srovnej přírodní evoluční vývoj a technický systém » ohraničenost lze docílit určením časového horizontu (např. generace buňky) IV120 Úvod do problematiky a informace o kurzu str. 24/46 Základní pojmy Základní atributy systémů • statické vs. dynamické systémy • statický systém - bez paměti (hodnoty vnitřních a výstupních veličin určeny okamžitými hodnotami vstupu) • dynamický systém - s pamětí (okamžitá hodnota vnitřních veličin závisí na okamžitých i minulých hodnotách vstupu) • ancipativní systémy - dynamický systém s předvídáním, navíc závislost na budoucích hodnotách (fyzikálně nerealizovatelné; příkladem je evoluce, existují studie, které pokládají za ancipativní systém lidský mozek - Robert Rosen) IV120 Úvod do problematiky a informace o kurzu str. 25/46 Základní pojmy Základní atributy systémů » spojité vs. diskrétni systémy • dle povahy veličin - spojité/diskrétní v úrovni (ve stavech) (discrete-state) • teoretické modely spojité, číslicová reprezentace vždy diskrétni (vzorkování, kvantování) • dle chápaní času - spojité/diskrétní v čase (discrete-time) » spojitá nebo diskrétni časová množina • např. systém vývoje populace uvažovaný po generacích vs. systém střídavého servomotoru • kombinace spojitých a diskrétních veličin (nebo úseků času) -hybridní systém • vzniká spojením aktivity ve spojitém čase s aktivitou v diskrétním čase IV120 Úvod do problematiky a informace o kurzu str. 26/46 Základní pojmy Základní atributy systémů - příklady • spojitý v čase i ve stavech - matematické kyvadlo, střídavý servomotor, ... • diskrétní v čase, spojitý ve stavech - populace ovocných mušek v uzavřeném kontejneru (čas uvažován v generacích, velikost populace poměrem zaplněného prostoru vůči objemu kontejneru) » výše uvedené typy systémů vykazují dynamické chování, které lze zachytit stavovými rovnicemi • popis závislosti okamžitého stavu na paměti » použití diferenčních nebo diferenciálních rovnic (implicitní popis přechodové struktury) IV120 Úvod do problematiky a informace o kurzu str. 27/46 Základní pojmy Základní atribúty systému - príklady - matematické kyvadlo • pohyb určen vývojem úhlu odklonu 9 od vertikální (klidové) polohy • určeno pohybovou (diferenciální) rovnicí mls + dIŠ + mgsm(9) = 0 kde m ...hmotnost h.b., / ... délka závěsu, d ... faktor disipace • určíme-li jako vnitřní veličiny x\ = 9 a X2 = 9, dostaneme soustavu: xi = x2 f s/n(xi) - ^x2 IV120 Úvod do problematiky a informace o kurzi str. 28/46 Základní pojmy Základní atribúty systému - príklady - logistický rust • model fluktuací populace ovocných mušek v nádobě při konstantním (limitovaném) přísunu potravy • časovou jednotkou je generace • vnitřní veličinou x je množství populace vyjádřené vzhledem objemu nádoby (předpokládáme 0 < x < 1) • přechodová struktura vyjádřena implicitně diferenční rovnicí: Xk+i = rxk(l - xk) = f(xk) http://www.enm .bris.ac.uk/staff/hinke/courses/rtiath5337/ds/applets/iteration/Iteration.html IV120 Úvod do problematiky a informace o kurzu Základní pojmy Základní atributy systémů - příklady • diskrétní v čase, diskrétní ve stavech - výrobní linka se stavy { pohotovost, činnost, porucha }, přechody jako reakce na diskrétní události { zpracováno, porucha, opraveno } a zásadním charakteristickým prvkem je diskrétní vstupní veličina charakterizující diskrétní události • výskyt událostí uvažován v diskrétním čase • odpovídá většině "human-made" systémů (SW, komunikační protokoly, .. .) IV120 Úvod do problematiky a informace o kurzu str. 30/46 Základní pojmy Základní atributy systémů - příklady - výrobní linka • vnitřní veličina X charakterizující stav systému: V(X) = {I,W,D} o / ... pohotovost, W ... činnost, D ... porucha • vstupní veličina U charakterizující diskrétni udalosti: V(U) = {p,c,f, r} • p ... požadavek, c ... zpracováno, f ... porucha, r ... oprava • přechodová struktura určena schématem IV120 Úvod do problematiky a informace o kurzu str. 31/46 Základní pojmy Základní atributy systémů - příklady • spojitý v čase, diskrétní ve stavech - např. systém sledující počet diskrétních udalostí v určitém časovém intervalu • úroveň zdrojového nebo datového systému (např. Poissonův proces), nelze vyjádřit přímo stavovými rovnicemi ani konečnou přechodovou strukturou, používají se statistické modely • do této kategorie lze řadit systémy reálného času (např. semafor), používá se rozšířeného formalismu pro popis přechodové struktury (časové automaty) » hybridní - termostat, skákající míček • zobecnění předchozích kategorií • spojení diskrétních událostí a spojité dynamiky • nemusí nutně zahrnovat diskrétní veličinu - viz skákající míček • klíčová charakteristika je výskyt diskrétních událostí, které porušují spojitost aktivit na jednotlivých veličinách • rozšířený popis přechodové struktury - hybridní automat IV120 Úvod do problematiky a informace o kurzu str. 32/46 Základní pojmy Základní atributy systémů - příklady hybridních systémů Základní pojmy Spojitost vs. diskrétnost - poznámky • typicky se označením spojitý/diskrétní systém rozumí způsob zachycení času (discrete-time vs. continuous-time dynamics) • čas lze chápat jako jednu z veličin systému, popsanou jednoduchou stavovou rovnicí - konstantní diferenční nebo diferenciální rovnicí • systém zadaný diferenciální rovnicí vykazuje spojité aktivity » hybridnost vzniká kombinací spojitých a diskrétních aktivit • dosaženo kombinací spojité a diskrétní dynamiky na úrovni elementů systému (element teploty a element přepínače v termostatu) • zavedením diskrétních vstupů (řízení) do spojité dynamiky (diskrétní událost odrazu míčku) IV120 Úvod do problematiky a informace o kurzu str. 34/46 Základní pojmy Bouldingova klasifikace systému Třída Název třídy Typ systému Typické nové vlastnosti 1 statická, struktura. strukturní vzorec látky 2 mechanicky systém hod Lnový stroj dynamický deterministický pohyb 3 kyberneticky systém regulační obvod zpětná vazba, zpracování informace 4 otevřený systém buňka látková výmena j samorc produkce 5 genetický systém rostlina diferenciace částí G zoologický systém zvíře cílové chování, představy 7 systém lidského jedince člověk vedomí, vytváření symbolů 8 sociální systém mésto vytvářeni rolí, systém hodnot 9 transcendentní systém ne p o znatelnost • aparát pro systémy třídy 5 a vyšší není vyvinut! • Kenneth Boulding (1956) - http: //www.panarchy.org/boulding/systems.1956.html IV120 Úvod do problematiky a informace o kurzu str. 35/46 Základní pojmy Vlastnosti systému - konečně-stavovost • charakter množiny všech stavů systémů je klíčový pro rozhodnutelnost některých problémů analýzy • spojité systémy v čase a netriviální hybridní systémy jsou vždy nekonečně-sta vové • diskrétní systémy v čase mohou být rovněž nekonečně-stavové • nekonečná množina stavů (např. neohraničená Petriho síť, logistický růst) • nekonečná množina vstupních událostí (např. model SW) IV120 Úvod do problematiky a informace o kurzu str. 36/46 Základní pojmy Vlastnosti systému - stabilita • stav systému je rovnovážným stavem, pokud z něj systém nepřejde do jiného stavu bez působení vnějších vlivů (např. na vstupech) • chování systému v okolí rovnovážného stavu může být stabilní • malým vychýlením nedojde k výrazné změně chování • systém se nadále pohybuje v blízkém okolí rovnovážného stavu • nestabilní okolí znamená výraznou změnu chování vedoucí ke vzdálení od rovnovážného stavu IV120 Úvod do problematiky a informace o kurzu str. 37/46 Základní pojmy Vlastnosti systému • systém je deterministický pokud pro daný výchozí stav a sledovaný časový úsek existuje právě jedna aktivita • nedeterministický systém vykazuje různé aktivity z téhož vých. stavu • deterministický systém vykazuje chaotické chování, pokud pro velmi blízké výchozí stavy generuje výrazně odlišné aktivity a obraz lib. otevřené množiny stavů v konečném čase inciduje s lib. jinou množinou stavů • výzkum chaotických systémů vedl ke speciální oblasti teorie systémů - teorii chaosu « chaos mohou vykazovat i zdánlivě jednoduché systémy • způsobeno komplexností vazeb v systému (nelineární systémy) o nebo neohraničeností řádu (neohraničené systémy) IV120 Úvod do problematiky a informace o kurzu str. 38/46 Základní pojmy Historie zkoumání chaotických systému • otázka stability sluneční soustavy (Lapiace aplikuje teorii pravděpodobnosti a vede k popření deterministického modelu světa, přelom 18.-19.stol.) • problém soustavy vzájemného gravitačního působení 3 a více těles • Poincaré prokazuje možnost nestability (přelom 19.-20.stol) • existují neperiodické aktivity, které nedivergují ani nekonvergují ke stabilnímu stavu • pozorování kvalitativní změny stability při změnách parametrů systému (později základ tzv. teorie bifurkací) IV120 Úvod do problematiky a informace o kurzu str. 39/46 Základní pojmy Historie zkoumání chaotických systému » stabilitou systémů se dále zabývali Ljapunov (kritéria stability), Birkhoff (studium ergodicity) a Kolmogorov (eliptické pevné body) • Lorenz roku 1961 při počítačové simulaci modelu pohybu vzduchu v atmosféře (12 veličin) objevil (náhodou) nestabilitu • dále vytvořil malý model 3. řádu, který vykazuje velmi složité chaotické chování (tzv. motýlí efekt) IV120 Úvod do problematiky a informace o kurzu str. 40/46 Základní pojmy Chaotické chovaní - příklady - Lorenzův atraktor IV120 Úvod do problematiky a informace o kurzu str. 41/46 Chaotické chovaní - příklady • prvním dokladem chaotického chování ve vesmíru je objev J. Wisdoma (výzkum drah planetek, 1983) • problém tzv. Kirkwoodovy mezery • prostor mezi planetkami, z něhož dochází chaoticky k přenosu materiálu do kritické blízkosti Země • vypočítána maximální doba (200 tis. let) do níž se materiál z mezery dramaticky odchýlí ve své dráze pohybu • dalším příkladem je rezonance oběžných dob dvou měsíců Saturnu (Hyperionu a Titanu) • Hyperion nerotuje kolem sve osy, pohybuje se chaoticky (další příčinou chaosu je nepravidelný tvar Hyperionu) IV120 Úvod do problematiky a informace o kurzu str. 42/46 Základní pojmy Chaotické chovaní - příklady - logistický růst Xk+i = rxk(l - xk) = f(xk) • diskrétní systém logistického růstu populace s nosnou kapacitou 1 (maximální množství populace udržitelné při daném konstantním množství zdrojů) • systém je citlivý na nastavení parametrů a iniciální podmínky • parametr r vyjadřuje rychlost růstu populace při absenci vnitřního soupeření • pro 3 < r < 4 dochází ke komplexnímu chování (oscilace, chaos) • důvodem je zpožděná zpětná vazba, díky níž může být překročen při diskrétním kroku rovnovážný stav (příklad nestability) • viz cvičení » chaotické chování není přítomno ve spojité formulaci (asymptotické chování) IV120 Úvod do problematiky a informace o kurzu str. 43/46 Základní pojmy Chaotické chovaní - příklady - logistický růst chování v dlouhočasovém horizontu (pro různá r) IV120 Úvod do problematiky a informace o kurzu Základní pojmy Stabilní chování - příklady - logistický růst • nelineární diferenciální rovnice dx ri \ 2 rx(l — x) = rx — rx dt řešení: x(0) + (1 - x(0))e-rt Logistic growth time course for varying x(0) Proč se zabývat dynamickými systémy? • formální matematické uchopení komplexních procesů • zdánlivě jednoduché systémy mohou vykazovat nepředvídatelné chování • systémy využíváme jako modely reálných objektů • za určitých okolností lze navrhnout řízení systémů IV120 Úvod do problematiky a informace o kurzu str. 46/46