UNIVERZITA PARDUBICE FAKULTA ELEKTROTECHNIKY A INFORMATIKY
DIPLOMOVÁ PRÁCE
2012
Bc. Martin Mariška
Univerzita Pardubice Fakulta elektrotechniky a informatiky
AGENTOVĚ ORIENTOVANÉ SIMULAČNÍ MODELY PROVOZU OBSLUŽNÝCH SYSTÉMŮ Bc. Martin Mariška
Diplomová práce
2012
PROHLÁŠENÍ AUTORA
Prohlašuji, že jsem tuto práci vypracoval samostatně. Veškeré literární prameny a informace, které jsem v práci využil, jsou uvedeny v seznamu použité literatury. Byl jsem seznámen s tím, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorský zákon, zejména se skutečností, že Univerzita Pardubice má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle § 60 odst. 1 autorského zákona, a s tím, že pokud dojde k užití této práce mnou nebo bude poskytnuta licence o užití jinému subjektu, je Univerzita Pardubice oprávněna ode mne požadovat přiměřený příspěvek na úhradu nákladů, které na vytvoření díla vynaložila, a to podle okolností až do jejich skutečné výše. Souhlasím s prezenčním zpřístupněním své práce v Univerzitní knihovně.
V Pardubicích dne 20. 8. 2012
Bc. Martin Mariška
PODĚKOVÁNÍ
Na tomto místě bych rád poděkoval svému vedoucímu diplomové práce prof. Ing. Antonínu Kavičkovi, Ph.D. za cenné rady, náměty a za odborné vedení během zpracování této práce.
ANOTACE
Práce se věnuje problematice agentově orientované simulace. Další části se pak zaměřují na vytvoření a ověření mechanizmu pro modelování obslužných procesů v rámci agentově orientovaných simulačních modelů a implementaci mechanizmu do prostředí simulační platformy Repast Simphony 2. KLÍČOVÁ SLOVA Agentově orientovaná simulace, modelování obslužných systémů, simulační framework Repast Simphony 2.0
TITLE
Agent-based simulation models of service systems
ANNOTATION
The work is devoted to agent – based simulation. Next part is orientated on the creation and verification of a mechanism for modeling service processes within the agentoriented simulation models and implementation of the mechanism into the environment of simulation platform Repast Simphony 2. KEYWORDS Agent-based simulation, modelling service systems, simulation framework Repast Simphony 2.0
Obsah 1
Úvod ............................................................................................................................. 12
2
Cíl diplomové práce ..................................................................................................... 13
3
Simulace jako experimentální výzkumná metoda ........................................................ 14
4
5
3.1
Systém ................................................................................................................... 14
3.2
Model .................................................................................................................... 15
3.3
Modelování ........................................................................................................... 16
3.4
Simulace................................................................................................................ 16
3.5
Aktivity a procesy ................................................................................................. 17
3.6
Simulační experiment ........................................................................................... 18
Agentově orientované simulace ................................................................................... 19 4.1
Struktura agentově orientovaného modelu ........................................................... 19
4.2
Autonomní agenti ................................................................................................. 20
4.3
Interakce mezi agenty ........................................................................................... 25
4.4
Agent a jeho prostředí ........................................................................................... 27
4.5
Metody návrhu modelu ......................................................................................... 28
4.5.1
Otázky pro návrh modelu .............................................................................. 29
4.5.2
Bottom – up, Top – down ............................................................................. 30
Repast Suite .................................................................................................................. 32 5.1
Základní koncept frameworku Repast Simphony ................................................. 32
5.2
Repast Simphony 2 ............................................................................................... 34
5.2.1
Repast Java .................................................................................................... 35
5.2.2
ReLogo .......................................................................................................... 35
5.2.3
Repast Flowchart ........................................................................................... 36
5.3 6
Repast HPC ........................................................................................................... 37
Repast Simphony Service, proprietární software ......................................................... 39 6.1
Popis problému obslužných systémů v AOS ........................................................ 39
6.1.1
Systémy hromadné obsluhy .......................................................................... 39
6.1.2
Obslužný systém v AOS ............................................................................... 40
6.2
Požadavky ............................................................................................................. 41
6.3
Návrh .................................................................................................................... 41
6.3.1
Základní koncept ........................................................................................... 42 8
6.3.2
Aktivita.......................................................................................................... 43
6.3.3
Zdroj Obsluhy ............................................................................................... 44
6.3.4
Technologický proces ................................................................................... 44
6.4
7
Implementace ........................................................................................................ 44
6.4.1
Aktivita.......................................................................................................... 45
6.4.2
Zdroj Obsluhy ............................................................................................... 46
6.4.3
Technologický proces ................................................................................... 46
6.4.4
Vizuální podpora ........................................................................................... 47
Případové studie obslužných systémů .......................................................................... 49 7.1
Model M/M/1 ........................................................................................................ 49
7.1.1
Cíle případové studie..................................................................................... 49
7.1.2
Parametry modelu ......................................................................................... 50
7.1.3
Analytické řešení systému M/M/1 ................................................................ 50
7.1.4
Závěr ............................................................................................................. 50
7.2
Model pneuservis .................................................................................................. 51
7.2.1
Popis .............................................................................................................. 51
7.2.2
Cíle případové studie..................................................................................... 52
7.2.3
Návrh ............................................................................................................. 52
7.2.4
Parametry modelu a simulační scénáře ......................................................... 53
7.2.5
Výsledky ....................................................................................................... 54
7.2.6
Závěr případové studie .................................................................................. 55
7.3
Model výstaviště ................................................................................................... 56
7.3.1
Popis .............................................................................................................. 56
7.3.2
Cíle případové studie..................................................................................... 57
7.3.3
Návrh ............................................................................................................. 57
7.3.4
Problémy ....................................................................................................... 59
7.3.5
Parametry modelu a simulační scénář ........................................................... 63
7.3.6
Výsledky ....................................................................................................... 64
7.3.7
Závěr případové studie .................................................................................. 66
8
Závěr............................................................................................................................. 68
9
Literatura ...................................................................................................................... 69
10
Přílohy ...................................................................................................................... 71
9
Seznam Obrázků Obrázek 1 – Ilustrace modelu kontejnerového přístaviště ...................................................14 Obrázek 2 – Ilustrace modelu železničního uzlu (Villon) ....................................................14 Obrázek 3 – Aktivita simulátoru. Zdroj: [12]. ...................................................................... 17 Obrázek 4 – Spojitá aktivita. Zdroj [12] ............................................................................... 17 Obrázek 5 – Diskrétní aktivita. Zdroj: [12] ......................................................................... 18 Obrázek 6 – Proces. Zdroj: [12] ........................................................................................... 18 Obrázek 7 – Struktura typického ABM. Zdroj [20] ............................................................. 20 Obrázek 8 – Typický agent. Zdroj [20] ............................................................................... 23 Obrázek 9 – Přehled běžných topologií pro vztahy a interakce mezi agenty. Zdroj [20] ... 27 Obrázek 10 – Příklad implementace agenta chodce ........................................................... 33 Obrázek 11 – Běhové prostředí Repast Simphony s 2D a 3D pohledem ............................. 34 Obrázek 12 – Ukázka prostředí flowchart ........................................................................... 37 Obrázek 13 – Systém hromadné obsluhy zdroj [27] ........................................................... 40 Obrázek 14 - Koncept funkce technologického procesu ...................................................... 43 Obrázek 15 – Struktura balíčků RepastS Service ................................................................ 45 Obrázek 16 – Technologický proces nákupu s paralelní činností ....................................... 47 Obrázek 17 – Ukázka modelu M/M/1 ve vizuálním prostředí ............................................ 49 Obrázek 18 – Ukázka modelu pneuservisu ve vizuálním prostředí ..................................... 51 Obrázek 19 – Schéma topologie výstaviště.......................................................................... 57 Obrázek 20 – Vizuální ukázka výstaviště s problémem utlačování .................................... 60 Obrázek 21 – Vizuální ukázka výstaviště po aplikování gradientních map .........................61 Obrázek 22 – Pseudokód vytvoření gradientní mapy (vzdáleností) ................................... 62 Obrázek 23 – Gradientní mapa (vzdálenosti) ..................................................................... 62 Obrázek 24 – Gradientní mapa (směry) ............................................................................. 63 Obrázek 25 – Zahlcený východ výstaviště ........................................................................... 66
Seznam tabulek Tabulka 1 – Výsledky experimentu pneuservisu podle scénáře 1 ....................................... 54 Tabulka 2 - Výsledky experimentu pneuservisu podle scénáře 2 ....................................... 54 Tabulka 3 - Výsledky experimentu výstaviště podle scénáře 1 ............................................ 64 Tabulka 4 - Výsledky experimentu výstaviště podle scénáře 2 ........................................... 65
Seznam grafů Graf 1 - Výsledky experimentu pneuservisu podle scénáře 1 .............................................. 54 Graf 2 - Výsledky experimentu pneuservisu podle scénáře 2 ............................................. 55 Graf 3 - Výsledky experimentu výstaviště podle scénáře 1.................................................. 65 Graf 4 - Výsledky experimentu výstaviště podle scénáře 2 ................................................. 65 Graf 5 - Výsledky vlivu doby nakládání na spokojenost návštěvníků ................................. 66
10
Seznam Zkratek ABM AS BDI CA CSV DAI GIS GUI HPC JGAP MPI SHO TP UML XML 2D, 3D
Agentově orientovaný model (agent – based model) Agentové systémy (Agent Systems) Představa, přání, záměr (Beleive Desire Intend) Celulární automat Formát textového souboru (Comma Separated Value) Distribuovaná umělá inteligence (Distributed Artificial Intelligence) Geografický informační systém Grafické uživatelské prostředí (Graphical User Interface) Vysoce náročné výpočty (High Performance Computing) Java balíček genetických algoritmů (Java genetic algorithms package) Rozhraní pro předávání zpráv (Message Passing Interface) Systém hromadné obsluhy Technologický proces Unifikovaný modelovací jazyk (Unified modeling language) Rozšiřitelný značkovací jazyk (Extensible Markup Language) Dvou a tříd dimenzionální (obvykle) prostor
11
1 Úvod Agentově orientovaná technologie je rychle se vyvíjející obor umělé inteligence a počítačové vědy. Jeho využití zasahuje v dnešní době do mnoha praktických i vědních oborů. Příkladem může být použití agentově orientovaného paradigmatu v softwarovém inženýrství, webových technologiích, robotice nebo modelování a simulaci. Multiagentní modely spadají do obecnější kategorie multiagentních systémů. Rozvoj multiagentního modelování umožnil až rozvoj moderní výpočetní techniky, především v posledních třech desetiletích. Modely slouží především k simulaci komplexních systémů v různých zájmových oblastech (ekonomie, biologie, sociální vědy), které jsou jinými způsoby výzkumu těžko proveditelné. Princip multiagentní simulace spočívá ve využití tzv. „agentů“. Agenti jsou autonomní entity, reprezentující reálné jednotky sledovaného systému, situované do definovaného kontextu prostředí. Agenti v daném prostředí jednají, reagují a mají schopnost se přizpůsobit vnějším podmínkám (adaptovat se). Tímto prostředím mohou být různé formy sítí a mřížek, vybrané podle sledovaného cíle a zvolených předpokladů, které by měly odpovídat simulované realitě. Simulace je pak sledována v diskrétním čase. V každém časovém kroku se vyhodnocuje chování všech agentů a stav prostředí, v závislosti na jejich výchozích parametrech. V první teoretické části této práce bude uveden obecný přehled problematiky agentově orientovaného modelování a simulace. Dále pak přehled agentově orientované simulační platformy Repast Simphony, která byla vybrána pro implementaci a realizaci zobecněného mechanizmu, který řeší problematiku obslužných systémů v agentově orientovaných modelech. Druhá část práce se zabývá navržením, implementací a ověřením softwarové nadstavby pro realizaci obslužných systémů v ABM. Obecná možnost rychlého prototypování nebo existence podpory pro tvorbu obslužných systémů ve specializovaných nástrojích zatím není dostupná. Tato diplomová práce poskytne koncept řešení a softwarové rozšíření platformy Repast Simphony 2, pro jeho realizaci a použití. Pro ověření vytvořeného proprietárního softwaru budou realizovány případové studie orientované na různou problematiku.
12
2 Cíl diplomové práce Hlavním cílem diplomové práce je návrh, implementace a ověření zobecněného mechanizmu pro zkoumání provozu obslužných systémů a jejich rychlejší výstavbu v agentově orientovaných modelech. Modely budou realizovány v rámci frameworku Repast Simphony 2. Za tímto účelem je třeba v teoretické části práce vypracovat: a) Přehled problematiky agentově orientovaných simulací b) Přehled softwarové simulační platformy Repast Simphony 2 V praktické části: a) Seznámit se s frameworkem Repast Simphony 2 b) Navrhnout a implementovat nadstavbu v prostředí zvoleného frameworku V experimentální části práce pak: a) Ověřit základní simulační vlastnosti frameworku Repast Simphony 2 ve vhodně zvolené případové studii b) Ověřit softwarovou nadstavbu aplikací ve vhodně zvolených případových studiích c) Výsledky z případových studií následně zhodnotit z pohledu náročnosti implementace a rychlosti výstavby konečného modelu
13
3 Simulace jako experimentální výzkumná metoda Pro uvedení definice modelování a simulace je nutné vysvětlit význam některých výchozích termínů. Mezi tyto termíny patří systém, model, modelování a další pomocné termíny. Uvedené definice a pojmy vychází z publikací [9], [11], [12], [1 17]. Předmětem simulace imulace a modelování je výzkum a pozorování objektů hmotného světa, kde tyto objekty již v realitě existují (například stávající řešení železničního uzlu města Prahy, stávající řešení jaderné elektrárny, kontejnerový termin terminál ál v přístavišti), přístavišti) anebo by existovat mohly (železniční uzel hl. m. Prahy po rozšíření na další směry a jeho rekonstrukci, další výzkumná expedice na Mars).
Obrázek 1 – Ilustrace lustrace modelu kontejnerového přístaviště
Obrázek 2 – Ilustrace lustrace modelu železničního uzlu (Villon)
3.1 Systém V simulaci a modelování se zkoumá nějaká věc, c, resp. možné varianty nějaké n věci, při čemž slovo „věc“ chápeme tak, jak jej chápou filozofové: je to nnějaký jaký objekt hmotného světa, a to buď objekt, který vskutku existuje (nap (např.. organismus konkrétní osoby, konkrétní továrna, atd.), nebo o kterém uvažujeme, že by existovat mohl (např. (nap stroj, budova či 14
výrobní provoz, který by měl být realizován). Na zkoumaných věcech se zavádí abstrakce, které zanedbávají některé aspekty těchto věcí. Zanedbané aspekty jsou vybrány tak, že aspekty, které zbývají, jsou daným vědeckým, technickým či společenským oborem zvládnutelné: mimo jiné, mohou o nich racionálně komunikovat. Takovou abstrakci budeme v modelování a simulaci nazývat systémem a podle charakteru profese, která systém na věci „vidí“, „zavádí“ či „definuje“, dostává systém i přívlastek: např. železniční sít se běžně chápe jako dopravní systém, i když ekolog v ní muže vidět systém jiný. Abstrakce může, nebo nemusí zanedbat význam času. Např. význam času v systémech železniční dopravy nelze běžně zanedbat. Avšak při vytváření jízdního řádu v určitém roce konstruktér mapy železniční sítě České republiky zanedbává to, že se po jednotlivých tratích pohybují v čase vlaky a také to, že se železniční síť může měnit před rokem vzniku jízdního řádu i po něm. Systém, v němž se od významu času abstrahuje, se nazývá statickým systémem. Systém, jehož čas se nezanedbává a je přitom chápán „newtonovsky“1, se v modelování a simulaci nazývá dynamickým systémem. Dynamický systém je v každém okamžiku své existence v jistém stavu. Změna stavu dynamického systému se nazývá událost. Simulace se jinými než dynamickými systémy nezabývá. V modelování a simulaci se chápe systém tak, že je složen z prvků. V dynamickém systému se může počet jeho prvků během jeho existence měnit: systém (např. biologický) může růst a smršťovat se, avšak v technických a ekonomických aplikacích jde nejčastěji o to, že prvky mohou do systému „vstupovat“ a systém „opouštět“. Prvky, které jsou v dynamickém systému během celé jeho existence, se nazývají permanentní prvky. Naopak prvky s dočasnou existencí v systému nazýváme temporární. Prvky systému mají své vlastnosti, které se nazývají atributy. Ty přiřazují prvkům nějaké hodnoty, jež se mohou u prvků dynamického systému v čase měnit. Atributy bývají tzv. „hodnotové“, anebo „referenční“. Referenční atributy přiřazují prvkům systému jiné prvky.
3.2 Model Slovo model se používalo v běžné řeči nejprve pro předlohu. V odborném jazyku doby před simulací a virtuální realitou zůstal z této praxe termín funkční modely, a to pro první exemplář navrženého výrobku, který pracuje tak, jak by výrobek pracovat měl, přestože jiné vlastnosti výrobku (např. estetické) tento exemplář ještě nemá. Termín model je v oblasti modelování a simulace používán pro analogii mezi dvěma systémy: modelovaným (neboli originálem) a modelujícím. Jednoduché příklady nabízí mapa (model části země na papíře) nebo socha (model osoby, zvířete atd. v neživém materiálu). Model je tedy složitá struktura, která váže dva systémy, jejich prvky a jejich 1
Newtonovsky je jako v klasické fyzice, čili tak, že je smysluplné mluvit o tom, že dvě události nastaly v systému současně nebo jedna z nich nastala dříve než druhá.
15
atributy, a v případě simulačních modelů i existence obou systémů. V běžné mluvě se však ustálila praxe, že pod slovem model se rozumí modelující systém, i když tento termín není úplně výstižný a přesný. Místo termínu modelovaný systém se používá slova originál. Vztah obou systémů, modelovaného a modelujícího, je dán tím, že každému prvku ܲ modelovaného systému je přiřazen prvek ܳ modelujícího systému. Každému atributu ݃ prvku ܲ je přiřazen atribut ℎ prvku ܳ a pro hodnoty atributu ݃ a ℎ je dána nějaká relace. Její charakter není nějak obecně omezen, ale v případě, že jsou aritmetické atributy, bývá taková relace úměrnost nebo tolerance.
݃i
ℎ
V případě, že jde o simulační model, se raději mluví o systému simulovaném a simulujícím než o modelovaném a modelujícím. Existuje praxe, že se na místě termínu simulující systém používá termín simulační model nebo také simulátor. Aby se jednalo o simulační model (simulátor), musí model splňovat následující požadavky: •
Jejich modelující i modelované systémy jsou dynamické systémy.
•
Existuje zobrazení τ existence modelovaného systému do existence modelujícího systému; je-li tedy ݐଵ okamžik, v němž existuje modelovaný systém ܯଵ , je mu přiřazen okamžik τሺtଵ ሻ = t ଶ , v němž existuje modelující systém ܯଶ , a tak je zobrazením τ přiřazen i stavu ܵଵ ሺݐଵ ሻ = ߪଵ systému ܯଵ stav ܵଶ ሺݐଶ ሻ = ߪଶ systému ܯଶ .
•
Mezi stavy ߪଵ a ߪଶ jsou splněny požadavky na vztahy mezi prvky a jejich atributy, jak již bylo uvedeno při definici modelu.
•
Zobrazení τ je neklesající; pokud nastane stav ߪ originálu před stavem ߪത téhož systému, pak stav, který odpovídá v modelujícím systému stavu ߪ, nastane před stavem, který odpovídá stavu ߪത nebo mohou oba stavy nastat současně. Tento požadavek vyjadřuje nutnost dodržovat vztahy kauzality z originálu i v modelujícím systému.
3.3 Modelování Podstatou modelování, ve smyslu výzkumné techniky, je náhrada zkoumaného systému jeho modelem (přesněji: systémem, který jej modeluje). Cílem modelování je získat pomocí pokusu s modelem informaci o původním zkoumaném systému. V tomto smyslu tedy platí, že bude vytvořen model, v němž modelovaným systémem je zkoumaný systém. Experimentovat se bude s modelujícím systémem, při čemž cílem bude dozvědět se něco o modelovaném systému.
3.4 Simulace Simulace je výzkumná technika (metoda), jejíž podstatou je náhrada zkoumaného dynamického systému (originálu) jeho simulátorem, s nímž se experimentuje s cílem získat informace o původním zkoumaném dynamickém systému. Nutno zdůraznit, že aby došlo k
16
simulaci, musí být cílem experimentů se simulátorem získání informací o simulovaném systému (originálu).
3.5 Aktivity a procesy Aktivity a procesy odrážejí dynamické vlastnosti systému, tj. plynutí času a změny stavu systému v čase. Aktivita představuje základní akční jednotku simulace, která je obrazem jisté činnosti v simulovaném systému (např. pohyb vlaku po koleji), přičemž pro ni platí: •
Má jisté časové trvání
•
(Potenciálně) Mění stav systému.
Obrázek 3 – Aktivita simulátoru. Zdroj: [12].
Běh simulačního času je představován vykonáváním jednotlivých aktivit a to ve stejném pořadí, v němž se vykonávají jim odpovídající činnosti v simulovaném systému (tedy originále). Časová existence aktivity je charakterizovaná množinou reálných čísel (časových okamžiků), v nichž aktivita existuje, tedy může měnit stav systému. Z tohoto hlediska rozeznáváme dva druhy aktivit. •
Spojitá aktivita, může měnit stav systému během celé doby jejího trvání. Časová existence aktivity je tedy charakterizována intervalem časových okamžiků < ݐଵ , ݐଶ >.
Obrázek 4 – Spojitá aktivita. Zdroj [12]
•
Diskrétní aktivita, může měnit stav systému jen v okamžiku ukončení aktivity ݐଶ ; v průběhu trvání aktivity se stav systému měnit nemůže. Aktivita existuje jen v okamžiku jejího ukončení ݐଶ . Ukončení diskrétní aktivity a následná změna stavu systému se nazývá událost ሺܷሻ.
17
Obrázek 5 – Diskrétní aktivita. Zdroj: [12]
V případě, že simulovaný systém obsahuje pouze spojité aktivity, potom mluvíme o spojité simulaci. Jestliže simulovaný systém obsahuje pouze diskrétní aktivity, pak mluvíme o diskrétní simulaci. Obsahuje – li systém jak spojité, tak i diskrétní aktivity, potom příslušnou simulaci označujeme jako kombinovanou (diskrétně – spojitou) simulaci. Proces je posloupnost přirozeně na sebe navazujících aktivit, které spolu tvoří jistý logický celek (např. průjezd vlaku vybraným fragmentem železniční sítě).
Obrázek 6 – Proces. Zdroj: [12]
3.6 Simulační experiment Program řídící výpočet při simulaci se nazývá simulačním programem, přičemž tento program je spouštěn pro různé konfigurace simulátoru za účelem provádění simulačních experimentů. Běh simulačního programu se nazývá simulační pokus (experiment) se simulátorem. V rámci simulačního pokusu zkoumáme chování originálu (vymezeného systému) při použití předem určených pravidel dynamického chování simulátoru. V literatuře se populárně uvádí, že pokus dává odpověď na otázku: „Co se stane, když …“. V průběhu simulačního pokusu se eviduje čas, který v dané fázi simulačního výpočtu odráží čas v simulovaném systému. Měnící se čas v simulačním pokusu se označuje jako simulační čas. Simulační čas typicky ubíhá rychleji (výjimečně i pomaleji) než reálný čas, avšak doba provádění jednotlivých simulačních aktivit v simulátoru musí být proporcionální vůči době provádění aktivit v originálu. Simulační čas, stejně jako ten reálný, nemůže klesat.
18
4 Agentově orientované simulace Agentově orientované modelování a simulace, je relativně nový přístup, jak modelovat komplexní systémy složené z autonomních „agentů“ schopných vzájemné interakce. Agenti mají vlastní chování, často definované nějakými jednoduchými pravidly a teprve interakce s okolím tvoří jejich specifické chování. Vzory, struktury a chování celého systému se nemusí explicitně programovat. V agentově orientovaném modelu vyplyne celé systémové chování právě na základě interakcí a chování jednotlivců. Takovéto modely nabízejí například možnost, jak modelovat heterogenní sociální systémy, ve kterých se jednotliví agenti mohou ovlivňovat svým chováním. Na základě učení a zkušeností se mohou následně lépe adaptovat do cílového prostředí. Aplikace agentově orientovaných modelů zasahuje do rozsáhlého množství oblastí a disciplín, ve kterých by se daly použít. Například můžeme uvést ekonomické modely, nákupní modely a s tím spojené nákupní chování, predikce pandemických katastrof, predikce chování lidí v ohrožení biologickou hrozbou, adaptivní model imunitního systému, porozumění pádu starověkých říší, modelování námořních i leteckých bitev a spoustu dalších. Všechny tyto modely se již realizovaly a mají svůj přínos v této oblasti. Je nutné říci, že pojem abstrakce je při vytváření modelů důležitý. Některé modely jsou malé, ale elegantní a zachycují pouze základní prvky, které jsou třeba pro pozorování cíleného chování. Na druhou stranu existující i agentově orientované systémy (například v přírodě), které jsou na velice detailní úrovni a obsahují velký objem dat. Takovéto modely poskytují detailní informace a využívají se například pro podporu rozhodování. V dnešní době mohou být modely také mnohem sofistikovanější, protože vývoj a hardware nyní umožňuje do modelů zapracovat obrovské množství dat. S klesající úrovní abstrakce (zvyšuje se míra detailu) se dosáhne realističtějších výsledků. V rámci této kapitoly je uveden aktuální obecný pohled na agentově orientované simulace. Základní pojmy a důležité termíny.
4.1 Struktura agentově orientovaného modelu Typicky agentově orientovaný model obsahuje tři části:
1) Množinu agentů, jejich atributů a chování 2) Množinu relací a pravidel interakce mezi agenty (většinou je na pozadí nějaká topologie, která udává kdo a s kým může reagovat) 3) Prostředí, ve kterém agenti existují (agenti také reagují s prostředím a jsou omezováni jeho pravidly. Například prostorová aktivita agenta je dána fyzikálními pravidly daného prostředí). Návrhář modelu musí v první řadě identifikovat model a naprogramovat tyto tři výše zmíněné elementy, aby vznikl plnohodnotný agentově orientovaný model. Struktura takového modelu je prezentována na obrázku 7. 19
Obrázek 7 – Struktura typického ABM. Zdroj [20]
Pro správný běh ABM je potřeba zabezpečit, aby agenti mohli opakovaně vykonávat své chování a interakce, přičemž není podstatné, zda vykonávání bude spojité (stejné časové intervaly), diskrétní (různé časové intervaly), anebo založené na procesech (při dokončení jedné aktivity následuje aktivita další). Dnešní modelovací nástroje, programovací jazyky a ostatní implementace zaměřené na agentově orientovanou problematiku, již mají realizované simulační jádro a mechanizmy, které agentovou simulaci umožní. Důležité je zmínit, že některé nástroje jsou specializované na určitou kategorii ABM a některé jsou naopak obecné a univerzální pro široké možnosti použití.
4.2 Autonomní agenti V této kapitole jsou zmíněny některé definice a pojmy, které vycházejí hlavně z publikací [20], [21], [23], [25]. Na počátku vzniku a vývoje agentních systémů (AS) stojí distribuovaná umělá inteligence (DAI), v níž autonomní jednotky, které jsou schopné řešit určité problémy, se nazývají aktéři (Actors). Z nich se pak vyvinul pojem agenti (Agents). Princip autonomního agenta (tzv. reaktivního agenta) popsal Rodney Brooks, pracovník AI laboratoří MIT. Poté princip inteligentních agentů (Intelligent Agents) popsal M. J. Wooldridge. [21] V dnešní době existuje jediná základní charakteristika agenta, na které se dnes shodnou všichni, kteří se touto problematikou zabývají. Tato charakteristika definuje, že agent reaguje na vzniklou situaci autonomně (tedy nezávisle). Agent má v sobě zapouzdřeno vlastní chování, které mu umožňuje provádět nezávislá rozhodnutí. Ve 20
většině případů jsou agenti aktivní a snaží se pomocí vykonávání svých akcí dosáhnout nějakého svého interního cíle. Současně agent reaguje na vnější podměty přicházející od ostatních agentů nebo od prostředí, ve kterém existuje. Přesná definice, co je to agent, v literatuře není sjednocená. Někteří autoři považují za agenta jakoukoliv nezávislou komponentu (software, model, jedince, aj.). Z tohoto pohledu může být chování komponenty velice jednoduché (popsané množinou jednoduchých „if – then“ pravidel2), anebo může být až velice komplexní (chování je modelované prvky umělé inteligence). Jiní autoři tvrdí, že chování musí být adaptivní. Znamená to, že agent musí být schopen se učit a měnit své chování na základě svých aktuálních zkušeností. Z praktického pohledu modelování, založeném na tom jaké jsou potřeby a možnosti modelování v dnešních nástrojích a na tom, jaké jsou současné požadavky na výstavbu agentových modelů, můžeme vyvodit následující základní charakteristiky agenta: •
Agent je nezávislý, modulární a unikátní (lze ho identifikovat). Modularita implikuje, že agent má určité meze působnosti (znamená to, že můžeme jednoduše říct co je součástí agenta a co není, případně co je sdílená část).
•
Agent je autonomní a řídí se sám. Agent může fungovat nezávisle ve svém prostředí a reagovat na ostatní události (události z prostředí nebo ostatních agentů). Meze působnosti udávají pravidla prostředí (respektive modelu) a situace, která nás v daném případě zajímá. Agent má chování, které je úzce spojeno s informacemi, které získává ze svého okolí (prostředí, ostatní agenti). Na základě těchto informací pak provádí své další rozhodnutí a akce. Jeho chování může být specifikováno od jednoduchých pravidel až po abstraktní modely, jako jsou neuronové sítě nebo genetické algoritmy, které poskytují agentovi adaptivní mechanizmy.
•
Agent má stav, který se mění v čase. Stejně jako kterýkoliv jiný systém má i agent stav, který je reprezentován množinou atributů odrážející aktuální situaci. Stav agentově orientovaného modelu v daném čase se skládá ze všech aktuálních stavů všech agentů a aktuálních stavů prostředí, ve kterých agenti existují. Agentovo chování je podmíněno právě jeho stavem. Můžeme tedy říci, že čím více stavů může agent mít, tím více by mohlo být jeho chování rozmanitější. V ABM tedy platí, že stav systému je množina všech informací v daném čase, které jsou potřeba pro posun systému z aktuálního stavu do jiného.
•
Agent je společenský a provádí dynamické interakce s ostatními agenty, které mají vliv na jeho chování. Agenti mají pravidla pro vzájemnou interakci, komunikaci, pohyb a spory v prostoru, pro provádění změn do prostředí a jiné. Také jsou schopni rozeznat a odlišit rysy ostatních agentů.
2
„If - then“ pravidlo má jenom dvě možnosti (pravdu, nepravdu). V případě pravdy nebo nepravdy se může provést nějaká akce.
21
Agenti mohou mít také další užitečné vlastnosti:
•
Agent může být adaptabilní. Například může mít pravidla nebo nějaký abstraktní mechanizmus pro modifikování jeho chování. Agent by měl mít schopnost učit se a upravovat své chování dle narůstajících zkušeností. Učení také vyžaduje nějakou formu paměti. Kromě toho adaptace, na úrovni jednotlivých agentů, se může projevit v populaci agentů skrze proces výběru. Znamená to, že vhodnější agenti zvyšují svůj počet v cílovém prostředí a tím se celý systém lépe adaptuje.
•
Agent může být „cílově orientovaný“. Znamená to, že má definované interní cíle, kterých se snaží dosáhnout, ale nesnaží se maximalizovat počet svých splněných cílů. V rámci snažení stále respektuje svá interní pravidla pro chování. Tato schopnost umožňuje agentovi porovnávat výstup jeho chování vzhledem k jeho interním cílům a tím přizpůsobit jeho požadavky a chování pro budoucí interakce.
•
Agent může být heterogenní. Na rozdíl od simulace částic, které jsou poměrně homogenní (např. modely s plynnými částicemi, modelování molekulové dynamiky), se v agentově orientovaných modelech často uvažuje velký rozsah jednotlivých typů agentů v dané populaci. Charakteristiky a chování agentů se mohou v populaci velice lišit v závislosti na jejich rozsahu a sofistikovanosti. Rovněž na počtu informací, které může agent zvažovat v danou situaci, na tom jak moc velký model externího světa si může agent zapamatovat, na tom zda agent dokáže odhadnout reakci ostatních agentů v závislosti na provedení svých akcí, na tom kolik historických informací si dokáže zapamatovat, aby mohl následně adaptovat své chování. Agenti mohou mít také různý přístup k prostředkům, které poskytuje dané prostředí. To může omezit nebo rozšířit jejich možnosti interakce, anebo obor působnosti.
22
Obrázek 8 – Typický agent. Zdroj [20]
Typická struktura agenta dokumentuje Obrázek 8. V agentově orientovaném modelu platí, že vše co je spojené s agentem, je buď jeho atributem, anebo metodou, která operuje nad agentovými daty. Agentovy atributy mohou být buď statické (nemění se v průběhu simulace), nebo dynamické (mění se v průběhu simulace). Pro příklad statickým atributem agenta je jeho jméno a dynamickým atributem je paměť provedených akcí (historie akcí). Agenti disponují metodami, které reprezentují jeho interní chování (chování je založené na vydefinovaných pravidlech nebo nějakém abstraktním modelu např. neuronová síť). Takovéto struktury spojují jednotlivé situace s možnými akcemi nebo množinou možných akcí, které může agent v danou chvíli provést. Příkladem může být metoda, kterou agent použije pro identifikování svého okolí. Agenty lze z pohledu komplexnosti autonomního chování rozlišit na následující kategorie:
•
Agent inteligentní – má schopnost plnit cíle s využitím logické dedukce
•
Agent reaktivní – má schopnost reakce na podněty
•
Agent deliberativní (rozvážný) – má schopnost plánovat postup svých akcí, provádět výpočty, ovlivňovat prostředí tak, aby získal výhodu (proaktivita)
•
Agent kognitivní – má schopnost vyvozovat logické závěry ze svých pozorování okolního prostředí. Je schopen se učit a vytvářet bázi znalostí (ukládá informace a znalosti získané dedukcí). Musí mít deliberativní schopnosti. Pak může provádět vnitřní akce jako je analýza scény, překlad a získávání dalších znalostí.
23
•
Agent racionální – musí mít všechny výše uvedené schopnosti. Jeho struktura obsahuje plánovací jednotku i kognitivní jednotku, včetně báze znalostí. Na základě svých poznatků je schopen se učit a pak racionálním způsobem plánovat svou činnost pro dosažení cílů. Znalosti agenta lze kategorizovat:
•
Problémově – orientované znalosti (problem oriented knowledge) – “asociální” typ znalostí, sloužící k lokálnímu, samostatnému řešení úloh (např. poskytování expertizy, hledání ve vlastní databázi agenta atd.)
•
Znalosti o sobě samém (self knowledge) – znalosti o vlastním chování, vnitřním stavu, závazcích apod.
•
Sociální znalosti (social knowledge) – znalosti o chování jiných agentů, o jejich schopnostech, zatížení, zkušenostech, závazcích, o jejich znalostech, záměrech a víře
Znalosti umožňují agentům:
•
Delegovat odpovědnost
•
Dekomponovat úlohu na jednodušší úlohy
•
Kontrahovat optimálně spolupracující agenty
•
Formovat týmy a koalice
•
Vyhledávat chybějící informace
Při modelování agentova chování pro dané situace nebo souvislosti, které agenta v modelu potkají, existují i „teorie kolektivního chování“. Někteří začínají s normativním modelem, ve kterém se agenti pokoušejí optimalizovat své vnitřní hodnoty (zisk, užitek, aj.). Pro počáteční vývoj je to jednoduché, pochopitelné, hodně popisné, ale hlavně vznikne i reálný heuristický model chování. Někteří mohou začít s implementací již popsaného modelu chování, ke kterému je dostupná teorie chování a empirická data. Například existuje numerický model pro popis chování nakupujícího zákazníka (využívá se v ekonomické sféře), který může být implementován a jeho chování může být ověřeno pomocí agentově orientované simulace. Kognitivní věda a související obory se soustředí na agentovo sociální chování. Vzniknul tak modelovací framework nazývaný BDI3 (Believe – Desire – Intent), který kombinuje modální4 a temporární5 logiku, jako základ pro reaktivní plánování a agentův výběr následné akce (Wooldridge, 2000).
3
Softwarový model Belief-Desire-Intention (představy-přání-záměry) je přístup ke tvorbě softwarově implementovaných agentních a multiagentních systémů inspirovaný teoriemi filosofa M. E. Bratmana. 4 Modální logika je oblast logiky zkoumající logické operace, tzv. modality (modální operátory jsou například „je možné, je nutné, je nemožné“).
24
V aplikacích pro agentově orientované modelování, ve kterých se klade důraz na schopnost učit se, je důležité, zda je učení na úrovni jedince, anebo se učí celý kolektiv najednou. Další výhodou je využití „strojového učení6“ jako dalšího zdroje učících se algoritmů například pro rozpoznávání vzorů nebo souvislostí v datech (data mining). Strojové učení poskytuje techniky jako „učení s učitelem“, „učení bez učitele“ nebo „zpětnovazebné učení“. Dalším představitelem můžou být zmíněny genetické algoritmy. Všechny tyto techniky se běžně využívají při výstavbě a modelování ABM.
4.3 Interakce mezi agenty S agentově orientovaným modelováním nedílně souvisí i modelování vztahů a interakcí mezi agenty. Mezi dva základní problémy modelování interakcí patří „kdo“ je (anebo by mohl být) spojen a s „kým“ a druhým problémem je samotný mechanizmus dynamiky těchto spojení. Oba dva aspekty musejí být vyřešené již na úrovní vývoje ABM. Jedna ze zásad komplexních systémů a agentově orientovaného modelování je, že agent má k dispozici pouze lokální informace. Agentově zaměřené systémy jsou silně decentralizované. Typicky neexistuje žádná centrální autorita, která by shromažďovala všechny informace a dodávala je přímo agentům, anebo by řídila jejich chování za účelem optimalizace výkonu. Dále je důležité, že všichni agenti spolu nekomunikují ve stejnou chvíli a také, že mají většinou omezené možnosti a komunikují typicky pouze s některými agenty ze svého okolí, tak jako tomu je v reálném světě. Lokální informace jsou získávány z interakcí, které vzniknou v okolí agenta (ne mezi jakýmkoliv agentem nebo všemi agenty) a z jeho lokálního prostředí (ne z jakékoliv části prostředí). Dále je také typické, že agentovo okolí se s probíhající simulací stále mění (například prostorová aktivita agenta). Způsob, jakým jsou agenti propojeni, je dán topologií nebo mechanizmem konektivity. Typickou topologií je prostorová mřížka nebo síťový graf skládající se z vrcholů (agentů) a hran (vztah nebo propojení mezi agenty). Topologie udává, kdo je s kým propojen (a může s ním například komunikovat, interagovat). Některé aplikace umožňují agentům interagovat pomocí více topologií. Například model pandemického šíření nemoci. V něm agenti reagují v první řadě v prostorové mřížce, pro modelování fyzického kontaktu mezi agenty. Agenti se mohou tedy nakazit při provádění každodenních prací a akcí. V druhé řadě jsou pak součástí nějaké své sociální sítě, která zahrnuje blízké agenty (rodinu, přátelé, známé). Tato síť představuje nejpravděpodobnější kontakty jednotlivého agenta. Okolí agenta je obecný koncept, který je aplikovatelný na jakékoliv místo definované v modelu. Například ve výše zmíněném modelu mohou agenti reagovat pouze na okolí, které je fyzicky (geograficky) blízko danému agentovi a zároveň bude vyhledávat ve svém okolí agenty ze své sociální sítě. 5
Temporální logika je odvětví logiky, které zkoumá logickou strukturu výroků o čase, s nimiž se klasická výroková nebo predikátová logika nedokáže plnohodnotně vypořádat. Například výrok: „Od teď bude stále pršet.“ 6 Strojové učení je podoblastí umělé inteligence zabývající se algoritmy a technikami, které umožňují počítačovému systému „učit se“.
25
První prostorový agentově orientovaný model byl implementovaný ve formě tzv. „Celulárního automatu7“ (CA). Jeho použití bylo prezentováno v modelu „Hra života8“ od pana Conwaye. CA je realizována na prostorové mřížce. Každá buňka má své bezprostřední sousední buňky, kterým říkáme okolí. V CA každá buňka může být reprezentována agentem, který má právě dva stavy (vypnutý, zapnutý) a interaguje s fixní množinou okolních buněk. Mnoho prvních modelů mělo podobu právě CA. Pan Epstein a Axtell představili model zvaný „Sugarscape“, kde byla topologie komplexnější než v jednoduchém CA. V „Sugarscape“ modelu byli agenti mobilní a byli tedy schopni se přemísťovat z buňky do buňky. V těchto výše zmíněných modelech můžeme říct, že prostorová mřížka se stala pro agenty jejich prostředím. Toto prostředí agentům umožňovalo získávat zdroje a informace, které byly rozprostřené po celém prostředí mřížky. V dnešní době je mnohem více běžných topologií (viz. Obrázek 9), které se v praxi využívají. V CA modelu se agenti mohou pohybovat pouze z buňky do buňky a to tak, že v jednu chvíli může být v jedné buňce pouze jeden agent. Okolí podle pana von Neumanna (5 – sousedů) zobrazuje Obrázek 9a. Dále existuje ještě další nejběžnější okolí podle pana Moora (9 – sousedů). Moorovo okolí vypadá jako u pana Neumanna, ale přidává buňky i v šikmých směrech. V Eukleidovském prostoru se mohou agenti pohybovat ve dvou, třech nebo více dimenzionálních prostředích (viz. Obrázek 9b). Obecné spojení mezi agenty se nejlépe definuje pomocí síťové topologie. Ta může být obecně statická, anebo dynamická (Obrázek 9c). Ve statických sítích jsou spojení předdefinované a v průběhu času se nemění. Naopak dynamické sítě, hrany a vrcholy se mohou formovat až za běhu podle vnitřního mechanizmu modelu. Dalším typickým představitelem topologií je tzv. GIS topologie (využívaná v geografických informačních systémech), kde se agenti přesouvají mezi jednotlivými územími (reálné uzemní celky, viz. Obrázek 9d). V bezrozměrném modelu (někdy označováno jako „omáčka“, „džus“) agenti nemají žádnou informaci o poloze, protože pro tento typ modelu není podstatná (viz. Obrázek 9e). Různé náhodné páry jsou z takovéhoto modelu vybírány k vzájemné interakci a zase navráceny zpět. Velká většina agentově orientovaných modelů obsahuje více topologií, které udávají možné interakce mezi agenty a rozšiřují tak možnosti agenta a celého systému.
7
CA je souhrnné označení pro určitý typ fyzikálního modelu reálné situace, ať již v podobě reálného přístroje či mnohem častěji počítačového algoritmu (programu). Slouží k časové i prostorové diskrétní (nespojité) idealizaci (ideální modelaci) fyzikálních systémů, kde hodnoty veličin nabývají pouze diskrétních hodnot v průběhu času. 8 Hra života je dvourozměrný, dvoustavový celulární automat, který svým fungováním připomíná vývoj společenství živých organismů.
26
Obrázek 9 – Přehled běžných topologií pro vztahy a interakce mezi agenty. Zdroj [20]
4.4 Agent a jeho prostředí Prostředím nazýváme vše, s čím agent přichází za své existence do styku. Agenti provádějí interakce přímo s prostředím, anebo s ostatními agenty. Prostředí může být jednoduše použito k poskytnutí informací jako je prostorová pozice agenta vzhledem k ostatním agentům, anebo může poskytovat množinu geografických informací (jako je tomu v GIS modelech). Agentova pozice je z tohoto pohledu dynamický atribut, který je v některých případech potřeba sledovat. Například ve chvíli, kdy agent vyžaduje nějaké prostředky (z prostředí, od druhého agenta) nebo při vyskytnutí se nějaké situace (konkrétně výbuch se týká pouze určitého území, v ostatních částech území jsou agenti nezasažení), je nutné sledovat, zda atribut prostoru umožňuje interakci. Komplexní environmentální modely mohou být použity pro modelování agentových prostředí. Například hydrologické a atmosférické disperzní modely mohou poskytnout specifická lokační data pro výšku hladiny podzemní vody nebo úroveň atmosférického znečištění. Respektive jsou dostupná data, která v modelu agenti poskytují. Prostředí může naopak také definovat omezující podmínky pro agentovo chování a jeho akce (příkladem může být právě prostorové umístění). Pokud budeme mít agentově orientovaný dopravní model, ve kterém je na jednotlivých cestách definováno kapacitní omezení vozovky, může to v danou chvíli zapříčinit omezení při pohybu po dopravní síti. Na některých cestách může dojít ke
27
snížení rychlosti agentů, na jiných k úplnému „ucpání“ (zamezí se tím průjezd a agenti musí volit náhradní cestu). Prostředí agenta můžeme kategorizovat:
•
•
•
Dostupné nebo nedostupné -
Dostupné prostředí je takové, o němž má agent úplné informace
-
Efektivně dostupné prostředí je takové, o němž má agent všechny informace, které potřebuje k rozhodování
-
V dostupném prostředí agent nepotřebuje udržovat svou vnitřní reprezentaci světa, protože vše „vnímá“
Deterministické nebo nedeterministické -
Deterministické prostředí – následující stav závisí pouze na předchozím stavu a akci agenta
-
Nedeterministické prostředí – stav prostředí může být ovlivněn náhodnými stavovými změnami v prostředí
Epizodické nebo neepizodické -
•
•
V epizodickém prostředí se zkušenost agenta skládá z epizod. Epizodu tvoří vjem a následná akce, přičemž akci volí agent pouze na základě jednoho předchozího vjemu.
Statické nebo dynamické -
Statické prostředí se nemění v čase mezi vjemem a akcí agenta, v dynamickém prostředí ke změnám dochází
-
Statické prostředí se lépe zkoumá a učení agenta je v něm snazší
Diskrétní nebo souvislé -
V diskrétním prostředí je přípustná pouze omezená množina vjemů a akcí
4.5 Metody návrhu modelu Správné navržení modelu závisí také na akcích, které tomu předchází. V první řadě mezi počáteční akce a rozhodnutí patří: •
Zda je originální systém vhodný k modelování a následné simulaci
•
Zda jsou stanoveny cíle simulace (projektu)
28
•
Zda existují (nebo jsou dostupné) potřebné informace k jeho následné výstavbě a realizaci
•
Zda lze vymezit na originálním systému objekt zkoumání a následně zkoumaný (simulovaný) systém
•
Zda je možné zodpovědět otázky, které budou zmíněny v další podkapitole „otázky pro návrh modelu“
V praxi se můžeme setkat hlavně s iterativním přístupem. U složitějších systémů je nutné navrhnout model (po menších částech) a následně provádět verifikaci navržených změn (při špatném výsledku verifikace lze okamžitě upravovat návrh modelu). Tato činnost se opakuje v iteracích, tak dlouho, dokud není model kompletní a verifikovaný jako celek. Pokud by se použila pouze sekvenční metoda (celý model by se navrhnul a namodeloval najednou), pak by mohlo dojít k selhání verifikace a obtížně by se identifikovaly problémy spojené s chybami v různých podsystémech. Samotný návrh ABM by měl proběhnout v těchto fázích:
•
Analýza reálného (modelovaného) systému
•
Navržení společenství agentů, vymezit jejich kompetence, určit hranice jednotlivých typů agentů a určit orientaci na daný typ problému, vydefinování jejich chování
•
Navržení prostředí, ve kterém budou agenti kooperovat a komunikovat
•
Navržení relací: mezi agenty, mezi agenty a prostředím
•
Určení vhodnosti navrženého modelu z implementačního pohledu
4.5.1
Otázky pro návrh modelu
V době návrhu agentově orientovaného modelu je dobré se zeptat na následující otázky a pokusit se formulovat jejich odpovědi. Zodpovězení těchto otázek vede k počátečnímu návrhu modelu. Otázky jsou: •
Co je specifický problém, který by měl model řešit? Jaká je nosná otázka, na kterou by měl model odpovědět? Jaká je přidaná hodnota agentově orientovaného modelu oproti ostatním modelovacím technikám a přístupům? Je agentově orientovaný model vhodný pro daný problém?
•
Co budou agenti v modelu představovat? Kdo v daném modelu rozhoduje? Které entity budou mít chování? Která data agenta jsou popisná (statická)? Které agentovy atributy by měly být zpracovávány vnitřně modelem a aktualizovány v agentech (dynamické atributy)?
29
•
V jakém prostředí budou agenti existovat? Jak budou agenti interagovat s prostředím? Je pohyb agenta v prostoru relevantní?
•
Jaké chování nás na agentovi zajímá? Jaké rozhodnutí budou muset agenti provádět? Jaké chování je nosné pro akce agenta? Jakými akcemi bude agent disponovat?
•
Jak budou agenti interagovat (komunikovat) mezi sebou? Interakce agentů budou expanzivní nebo specializované?
•
Odkud by měla data pocházet, obzvláště pak u agentova chování? Jak velké bude lokální okolí agenta a jaké informace z něj bude chtít získávat?
•
Jak může být model validován a verifikován? Jak může být validováno chování agenta?
Zodpovědět tyto otázky je základní částí procesu návrhu agentově orientovaného modelu. Pro dnešní dobu existuje zase více metodik a přístupů jak modelovat. Celkově nejpřínosnější metodikou pro praxi se zdají být iterativní metody návrhu. Z praktického pohledu vývoje je iterativní přístup efektivní (lze sledovat částečné výsledky již v průběhu vývoje). Moderní softwarové (a modelovací) vývojové praktiky definují, že by návrh modelu měl být nezávislý na implementaci modelu. Znamená to, že implementace výsledného modelu by měla být možná v libovolném programovacím jazyce. Agentově orientovaným inženýrstvím se ve své publikaci zabývá pan Aleš Kubík [16], kde uvádí, že vhodnou implementační platformou se jeví právě objektově orientované jazyky například Java. Správný a detailní popis komunikace v modelu, návrhových předpokladů modelu a detailní popis elementů jsou základem pro pochopení a využití modelu dalšími vývojáři, kteří by chtěli dále model používat nebo rozšířit. Problematikou popisu modelu se zabýval pan Volker Grimm [8]. Grimm navrhl a publikoval standardní protokol pro popisování agentově orientovaných (a příbuzných) modelů. 4.5.2
Bottom – up, Top – down
Tyto dvě strategie (přístupy) pochází z oboru informačního procesu a můžeme se na ně dívat, jako na přístup nebo styl myšlení, učení. Nejvíce se s tímto termínem můžeme setkat při vývoji softwaru, ale používá se i v ostatních oborech. Pro oba termíny je možné v literatuře nalézt synonyma. Termín „top – down“ („od shora dolů“) je někdy nahrazován pojmem analýza nebo dekompozice. Termín „bottom – up“ („od spoda nahoru“) je zase nahrazován synonymem syntéza. Přístup „Top – down“ (známý i jako sestupný návrh) je rozkládání systému na jeho jednotlivé podsystémy a tím se získává přehled o jeho struktuře. V prvním kroku jsou definovány podsystémy a jejich přibližné charakteristiky. Dále se každý podsystém znovu rozebírá a analyzuje (může se rozpadat na další podsystémy). Tímto postupem se systém
30
rozebere až na určitou dostačující úroveň detailu (většinou to bývá specifikování až na základní elementy systému). Přístup „Bottom – up“ je založen na postupném skládání základních elementů a podsystémů do sebe tak, aby ve výsledku vznikl plnohodnotný funkční systém. Většinou se podsystémy postupně formují s přibývajícími informacemi o konečném systému. V tomto přístupu jsou již atributy základních prvků specifikovány ve velkém detailu. Nadále jsou elementy kombinovány a spojovány do větších celků (i ve více vrstvách) dokud se nezkompletuje cílený systém. Největším úskalím tohoto přístupu je velká míra detailu již v počátku návrhu a vývoje. Proto se doporučuje zhotovit základní kostru (skelet) systému v té nejjednodušší funkční formě a potom ho rozšiřovat a rozvíjet jeho komplexnost.
31
5 Repast Suite Repast Suite9 je skupina pokročilých, zdarma šiřitelných, open source softwarů. Tyto softwary jsou určeny pro podporu a vývoj agentově orientovaného modelování a simulace. Všechny součásti jsou kolektivně vyvíjeny více než 10 let skupinou z Chicagské univerzity v Illinois (USA). Mezi původní vývojáře patří David Sallach, Nick Collier, Tom Howe, Michael North. Tito lidé vytvořili první koncept původního frameworku Repast (z angl. „The Recursive Porous Agent Simulation Toolkit“). Je důležité zmínit, že Repast Simphony je rozšíření původního frameworku Repast a přináší nový přístup k vývoji a provádění agentově orientovaných simulací. Zahrnuje navíc i mnoho pokročilých výpočetních technik pro aplikace, které simulují například sociální modely. Framework v aktuální verzi nabízí dva základní softwary a to Repast HPC (High Performance Computing) a Repast Simphony 2. První zmíněný software je implementován v C++a je určen pro simulaci masivního množství agentů. Druhý zmíněný je implementován v jazyku Java a je určen pro široké uplatnění. Umožňuje využívat všechny nativní možnosti Javy a je možné do něj i integrovat knihovny třetích stran (tím využít jejich funkčnost). Repast Simphony má další podružené softwary (ReLogo, Flowchart), které usnadňují návrh, modelování a simulaci. ReLogo na rozdíl od Repast Java má již předpřipravené abstraktní třídy (Turtle, Patch, Observer) pro základní implementaci agentů. Pro vývoj se využívá jazyka Groovy10, ten by měl značně urychlit samotné kódování modelu. Dále existuje Repast Flowchart, který dále usnadňuje výstavbu modelu. Pro výstavbu modelu se používá vestavěný grafický editor, který umožňuje skládat agenta z grafických komponent (Property, Behavior, Task, Decision, Join, Loop, End).
5.1 Základní koncept frameworku Repast Simphony Všechny Repast softwary respektují stejné koncepty a vlastnosti. Tím je zjednodušeno používání celé platformy, případný přechod mezi platformami Repastu. Nejobecnějším konceptem je, že agenti jsou implementováni jako Objekty (pro Javu i C++ to jsou instance tříd). Stav agenta je reprezentován jeho vnitřními atributy a agentovo chování představují instanční metody. Například agent chodec v simulaci davu, může být implementován s atributy, jako je rychlost a směr. Metoda pohyb může pohnout chodcem o vzdálenost odpovídající jeho směru a aktuální rychlosti.
9
Framework je dostupný na webové adrese: http://repast.sourceforge.net Groovy je objektově orientovaný programovací jazyk pro platformu Java. Jde o alternativu k programovacímu jazyku Java. Můžeme se na něj dívat jako na skriptovací jazyk pro java platformu. Inspiraci čerpal z jazyků Python, Ruby, Perl a Smalltalk. 10
32
public class Chodec { private double směr; private double rychlost; public void pohyb() { // metoda pro agentuv pobyb } } Obrázek 10 – Příklad implementace agenta chodce
Simulace postupuje v čase pomocí plánovače (kalendáře událostí). Plánovač má interní frontu událostí, ze které se v každém kroku vybírají události a zároveň se provádějí. Konkrétně Repast HPC vlastní diskrétní kalendář událostí s konzervativní metodou synchronizace. Uživatel plánuje události na specifický „tik“, kde tik udává relativní pořadí, ve kterém se mají události provést. Například můžeme mít tvrzení, že událost A je naplánována na tik = 3 a událost B je naplánována na tik = 5. Z tohoto tvrzení a dřívějšího popisu tedy vyplývá, že se událost A provede dříve než událost B. Kontext je další pojem, který se ve frameworku používá k zapouzdření populace agentů. Jedno z implementačně hlídaných pravidel je, že každá instance kontextu může obsahovat pouze jedinou instanci každého agenta (nelze do Kontextu přidat stejný objekt dvakrát). Když jsou agenti vytvořeni, lze je přidat do Kontextu a pokud se jejich životní cyklus ukončí, lze je z Kontextu odebrat. Kontext je asociován s tzv. projekcí. Projekce předepisuje relační strukturu mezi agenty v Kontextu. Pro příklad můžeme uvést mřížkovou projekci (grid projection), která vkládá agenty do maticové struktury (typicky mřížka), kde každý agent zabírá nějakou buňku (buňka má navíc atribut udávající pozici buňky v maticové struktuře). Síťová projekce dovoluje agentům definovat síť, ve které může uchovávat informace o relacích mezi agenty. Další vlastností Kontextu je, že po přidání agenta do Kontextu se agent automaticky stává i součástí všech projekcí, které jsou s Kontextem asociovány. Příklad: Kontext je asociován se síťovou projekcí, tedy po přidání agenta do kontextu se agent stane novým vrcholem v síťové projekci. Následně má možnost si dynamicky, dle svého chování, dále vytvářet spojení k ostatním agentům. Repast disponuje 5 základními projekcemi (z toho 3 jsou implementované i v HPC). Dostupné projekce jsou:
•
Continous Space / projekce souvislého (reálného) prostoru (HPC)
•
Geography / geografická projekce
•
Grid / maticová projekce (HPC)
•
Network / síťová projekce (HPC)
•
PhysicsSpace / fyzikální projekce
33
Simulace v Repast frameworku je složena z množiny agentů, jednoho nebo více kontextů, které obsahují zmíněnou množinu agentů a žádné nebo více projekcí. Kontexty se mohou hierarchicky větvit a tím vytvářet různé podmnožiny projekcí a agentů. Uživatel je zodpovědný za psaní kódu agenta a framework poskytuje implementace kontextů a projekcí. Každý simulační výpočet typicky vybírá z kalendáře událostí následující událost, která byla uživatelem naplánována pro provedení. Událost vyvolá specifikované chování agenta, který je zařazen aspoň do jednoho kontextu a užívá žádnou nebo více projekcí. Například každou simulační iteraci může každý agent vytvořit nové spojení s agenty, kteří jsou dostupní v jeho lokálním okolí (okolní buňky) v maticové projekci.
5.2 Repast Simphony 2 Je inovovaný framework založený na koncepci původního frameworku Repast. V první finální verzi byl uvolněn 5. března 2012 a je to interaktivní, multi – platformní modelovací systém založený na jazyku Java. Podporuje vývoj extrémně flexibilních agentově orientovaných modelů. Software je určen pro simulace na stolních počítačích nebo malých výpočetních clustrech. Repast Simphony podporuje vývoj modelů několika různými formami zahrnující prototypování modelů pomocí nadstavby ReLogo nebo využití grafického modelování ve vizuálním prostředí pomocí Flowcharts. Pro nejflexibilnější modely je k dispozici vývoj přímo v jazyce Java nebo Groovy. Všechny tyto přístupy jsou úzce propojeny vývojovým prostředím Eclipse IDE, který je dodáván již přeinstalovaný a přednastavený v základním instalačním balíčku Repast Simphony 2.
Obrázek 11 – Běhové prostředí Repast Simphony s 2D a 3D pohledem
34
Běhové prostředí Repast Simphony poskytuje GUI aplikaci, která je připravena pro vizuální konfiguraci modelu a jeho spouštění. Běhové prostředí poskytuje: •
GUI aplikaci pro vizuální nastavení prostředí a provádění operací s modelem
•
Integrované 2D, 3D a mnoho dalších vizualizačních pohledů, které mohou zobrazovat aktuální stavové informace modelu
•
Automatické připojení na zdroje dat různého typu (XML, CSV)
•
Automatické propojení s externími programy třetích stran pro statistické zpracování, analýzu a vizualizaci výsledků modelu
•
Distribuování modelu i s běhovým prostředím jako spustitelné aplikace, pro další osoby, které mohou s modelem dále experimentovat.
Repast Simphony byl úspěšně využit v mnoha aplikačních doménách jako například sociální věda, podpora prodeje produktů, zásobovací řetězce, model budoucí vodní infrastruktury a mnoho dalších. Jednou z dalších mnohých výhod je, že k této verzi frameworku je dostupné velké množství již hotových modelů. Například model CA, Game of Life, Sugarscape a mnoho dalších. Výhodou je i částečná kompatibilita s modely, které byly vytvořené v dřívějších verzích frameworku a lze je konvertovat a využít i ve stávající verzi frameworku. 5.2.1
Repast Java
Repast Java je pouze označení, ale ve své podstatě je to základní implementace Repast Simphony 2. Je to tedy nejnižší a nejflexibilnější přístup pro modelování a vývoj vlastních modelů. Na této úrovni může být agentem instance každé obyčejné třídy. To přináší obrovské možnosti implementace. Na druhou stranu je to i úskalí, protože není připravený žádný prototyp agenta a agent musí být vystavěn od samého základu. Základní množství dostupných knihoven je velké a již v základu nám framework nabízí pomocné implementace pro nativní použití genetických algoritmů (framework JGAP11), neuronových sítí (framework Joone12), anebo regresní analýzy (framework OpenForecast13). Navíc je možné využívat vlastních knihoven nebo knihoven třetích stran, pro dosažení požadované funkcionality. 5.2.2
ReLogo
Rozšíření ReLogo je nadstavba nad Repast Java. V základu poskytuje předem připravené abstraktní třídy pro snadnější implementaci a prototypování agentů. ReLogo je 11
JGAP, Java genetic algorithms package je rozšíření pro aplikaci genetických algoritmů v Javě. Informace a celá knihovna je dostupná na adrese: http://jgap.sourceforge.net/ 12 Java Object Oriented Neural Engine (joone) je nadstavba pro realizaci neuronových sítí. Knihovna je dostupná na adrese: http://www.jooneworld.com/ 13 OpenForecast je rozšíření pro použití regresní analýzy. Knihovna je dostupná na adrese: http://openforecast.sourceforge.net/
35
dostupné, ve vývojovém prostředí dodávaným v instalačním balíčku, při založení ReLogo projektu. Vývojáři poskytují také možnost konvertovat starší modely typu NetLogo pomocí průvodce dostupného v nabídce vývojového prostředí. ReLogo poskytuje tyto typy předpřipravených tříd, které pocházejí z původního programovacího jazyka Logo: •
Turtles / Želvy – jsou mobilní agenti
•
Patches / Místa – jsou fixní agenti
•
Links / Propojení – spojují želvy, aby vytvářeli sítě
•
Observer / Pozorovatel – poskytuje celkové řízení modelu
Logo modely jsou realizovány vždy ve dvou – dimenzionálním spojitém prostoru. Např. Želvy mohou být lokalizovány na jakémkoliv místě v prostoru, zato Místa se mohou vyskytovat pouze na diskrétních celočíselných lokacích a to pouze po jednom na dané lokaci. Modely fungují tak, že Želvy představují hlavní agenty, kteří mají chování a provádějí interakce mezi sebou a Místy. 5.2.3
Repast Flowchart
Repast flowchart je další rozšíření, které umožňuje vizuální tvorbu agenta v grafickém prostředí pomocí skládání a propojování grafických komponent (ukázka na obrázku 12). Grafické prostředí je založené na frameworku Flow4J14 od vývojářů prostředí Eclipse. Prostředí je schopné na základě definic v grafickém prostředí generovat na pozadí Java nebo Groovy kód. Ten je dále použit v běhovém prostředí. Proto jsou ve vývojovém prostředí vždy dva soubory a to například Chodec.agent (soubory s příponou agent je možné upravovat právě pomocí editoru flowcharts) a automaticky generovaný soubor Chodec.groovy, kde se při uložení flowchart souboru automaticky vygeneruje příslušný kód.
14
Framework je dostupný na webové adrese http://flow4jeclipse.sourceforge.net
36
Obrázek 12 – Ukázka prostředí flowchart
5.3 Repast HPC Repast HPC (High Performance Computing) je druhá implementace Repast Simphony frameworku (je založen na stejných principech a vývojovém konceptu jako Repast Simphony). Je určen pro vysoce náročné distribuované výpočty a paralelní operace. Software je implementován v programovacím jazyce C++ s využitím MPI (Message Passing Interface), rozhraní pro paralelní operace. Výhodou je jeho možné rozšíření pomocí boost15 knihovny. MPI je standardizované rozhraní pro předávání zpráv a lze ho tedy jednoduše rozšířit i jinými nástroji. Typickými kandidáty pro Repast HPC jsou simulační modely s masivními lokálními interakcemi a velkým počtem agentů.
15
Knihovna boost je dostupná z adresy: http://boost.org
37
Repast HPC momentálně podporuje pouze tři výše zmíněné projekce a to: Grid, ContinousSpace a Network. Jak již bylo řečeno v úvodu, Repast HPC disponuje dynamickým diskrétním kalendářem událostí, který využívá konzervativní metody synchronizace.
38
6 Repast Simphony Service, proprietární software V této kapitole je popsáno vlastní řešení softwarové nadstavby nazývané „Repast Simphony Service“ (zkráceně pak RepastS Service), které bylo vyvinuto pro rozšíření možností základního frameworku a umožňuje tak modelování širší třídy systémů. Podkapitoly uvádí popis požadavků, návrh, popis vnitřní struktury a důležité koncepty pro jeho použití. Motivace pro vytvoření této nadstavby je absence mechanizmu pro rychlý vývoj obslužných systémů v prostředí ABM. Přitom mnoho modelů, které se v praxi realizují je právě kombinace agentových systémů interagujících (nebo se účastnících) právě systémů hromadné obsluhy. Například můžeme uvést model letiště, kde je zahrnut pohyb lidí po letištní hale a letadel po letišti. Lidé se přitom snaží v hale nakupovat zboží (občerstvení, suvenýry), zakoupit si letenku a následně nastoupit do letadla.
6.1 Popis problému obslužných systémů v AOS 6.1.1
Systémy hromadné obsluhy
Proces uspokojování náhodně i hromadně vznikajících požadavků na obsluhu se nazývá proces hromadné obsluhy. Předmětem teorie hromadné obsluhy, někdy také označované jako teorie front (z anglických slov queueing theory), je matematické rozpracování a analyzování systémů poskytujících hromadnou obsluhu nějakých zařízení. Systém hromadné obsluhy je obsluhové zařízení, poskytující obsluhu určitého druhu. Do tohoto zařízení vstupují zákazníci požadující konkrétní obsluhu. Zde je nutné podotknout, že pod pojmem zákazníci se rozumí nejen lidé, ale i neživé věci. Proto se také někdy, místo pojmu zákazníci, používá termín požadavky na obsluhu. Po obsloužení zákazníci opouštějí systém hromadné obsluhy. Obsluhové zařízení se může skládat z jednoho nebo více míst, na kterých se poskytuje konkrétní obsluha. Tato místa se nazývají linky obsluhy.[27] Systém hromadné obsluhy (SHO) je základní teoretický model pro realizaci obslužných procesů. SHO je tvořený obslužnými kanály, které poskytují obsluhu požadavkům, přicházejícím ve vstupním proudu. Po ukončení obsluhy trvající stanovenou dobu se kanál uvolňuje a realizovaný požadavek odchází ve výstupním proudu.[27]
39
Pokud v okamžiku příchodu požadavku není volný žádný kanál, řadí se požadavek do fronty.
Obrázek 13 – Systém hromadné obsluhy zdroj [27] (A – vstup požadavků do systému, B – odmítnuté požadavky, C – realizované položky)
Systém hromadné obsluhy je vždy tvořen následujícími prvky:
•
vstupní proud
•
fronta
•
obslužné kanály
•
výstupní proud
V reálném světě a tedy i v simulačním modelu se může takovýchto systémů objevovat více najednou. Obslužným systémem budeme tedy rozumět systém hromadné obsluhy, který by mohl v realitě existovat. 6.1.2
Obslužný systém v AOS
V agentově orientovaných systémech je typické, že se agenti mohou účastnit jednotlivých obslužných systémů, které jsou v modelu dostupné. Obecně lze říci, že v ABM je takovýchto jednotlivých obslužných systémů mnoho. Právě tato skutečnost je motivací pro vytvoření obecného mechanizmu, který umožní zjednodušit implementaci obslužných systémů v agentově orientovaných modelech. V reálném světě obslužné systémy zachycují nějaký reálný proces, který je spouštěn příchozími požadavky. Obslužné systémy lze ve většině případů popsat posloupností procesů a elementárních aktivit, které musí aktéři modelu (zákazníci, obslužné zdroje) provést pro úspěšné dokončení obsluhy. Tento postup lze zachytit například pomocí síťového grafu (nebo množinou síťových grafů), kde jednotlivé hrany grafu vyjadřují jednotlivé elementární aktivity. Vrcholy síťového grafu v našem případě, 40
pouze propojují posloupnosti aktivit mezi sebou, aby bylo možné identifikovat, v jakém pořadí se mají provést. Tento síťový graf má jeden počáteční vrchol, kde obslužný proces začíná a jeden cílový vrchol, kde proces končí.
6.2 Požadavky Pro správnou funkčnost softwaru je nutné definovat požadavky, které jsou kladeny na navrhovanou nadstavbu. Mezi hlavní požadavky patří: •
Nadstavba musí umožnit lokální realizaci obslužného systému v agentově orientovaném prostředí.
•
Nadstavba musí být jednoduše integrovatelná do agentově orientovaných simulačních modelů ve frameworku Repast Simphony 2.
A dále přehled doplňujících požadavků, které vyplynuly při konzultacích a vývoji softwarové nadstavby:
•
K Nadstavbě musí být vypracována programová dokumentace v podobě vygenerovaného Javadoc a programátorská příručka, jako návod k použití nadstavby pro další vývojáře.
•
Nadstavba musí mít možnost volitelné vizuální podpory pro elementární akce, které jsou při obslužném procesu prováděny (umožňuje názornější vizuální analýzu modelu).
•
Nadstavba musí umožnit, aby délka trvání provádění aktivity mohla být zadána staticky i dynamicky (proud náhodných čísel z konkrétního rozdělení pravděpodobnosti).
Programovací jazyk je dán platformou frameworku. Jelikož je základní implementace Repast Simphony 2 dostupná v jazyce Java, byl zvolen stejný programovací jazyk i pro vývoj nadstavby.
6.3 Návrh Z teorie o systémech hromadné obsluhy, která je uvedena v kapitole 6.1, vyplývají některé požadavky a hlavní otázky pro návrh. V následujícím textu bude uvedeno, které jednotlivé části sytému jsou pro realizaci mechanizmu podstatné a které ne. Vstupní proud požadavků zajišťuje prostředí s agenty, to tedy není předmětem návrhu ani realizace. Předmětem návrhu je, jak v simulačním prostředí realizovat obslužný proces (obslužnou událost). Dále je potřeba řešit případ, kdy není dostatek obslužných kanálů. Tím vznikají (a musíme řešit) fronty požadavků. Po dokončení obslužného procesu je požadavek úspěšně dokončen a je možné obsloužit další následující požadavek na obsluhu. V rámci diplomové práce byl tedy navržen obecný mechanizmus, jakým lze dosáhnout realizace obslužného systému pro použití v simulačním prostředí. Řekněme, že 41
se obslužný proces může skládat z libovolného nenulového a nezáporného počtu obslužných aktivit. Tyto aktivity jsou dané konkrétním obslužným procesem a dokončení všech obslužných aktivit vede k dokončení obslužného procesu. Počet aktivit v daném obslužném procesu je dán úrovní abstrakce, která se uplatní při návrhu simulačního modelu. Může tedy dojít k situaci, že se jeden obslužný proces bude skládat pouze z jedné aktivity. Aktivita je reálná nebo abstraktní činnost, která může a nemusí trvat nějaký (simulační) čas. Další otázkou je, proč vznikají fronty při obslužném procesu? V našem případě je to kvůli omezenému počtu obslužných kanálů. Obslužné kanály budeme chápat jako nějakou věc (dále budeme takovouto věc nazývat obslužným zdrojem), která je potřeba k tomu, aby se mohl provést a dokončit jeden konkrétní obslužný proces (respektive některá jeho aktivita). Při neomezeném počtu obslužných zdrojů se tedy nebudou tvořit žádné fronty, protože může současně probíhat potřebný počet obslužných procesů (existuje neomezený počet obslužných kanálů). V případě, že jsou obslužné zdroje omezené (v reálném světě tomu tak je), lze současně provádět jen omezený počet obslužných procesů a ostatní požadavky se musí zařadit do fronty a počkat, až na ně přijde řada. Nadstavba je navržena tak, aby odrážela fungování reálného světa a tím by mělo být její použití pochopitelnější, jednodušší a intuitivní. Mechanizmus nadstavby je obecný, ale z pohledu implementace je závislý na platformě Repast Simphony. Nicméně to nebraní dalšímu rozšíření a obecný princip implementovat i v jiných modelovacích nástrojích. 6.3.1
Základní koncept
Základní myšlenkou je reprezentovat obslužný proces jako „proveditelný“ síťový graf. Jednotlivé hrany síťového grafu reprezentují elementární obslužné aktivity. Síťový graf nám umožňuje definovat souběžné i sekvenční posloupnosti aktivit, jako tomu je v reálném světě a je tedy dostatečně dynamický pro modelování všech případů reálného světa. Tento obslužný proces, který je reprezentovaný síťovým grafem, budeme dále nazývat technologickým procesem. Úroveň abstrakce modelu pak udává složitost modelu. To určuje, do jaké míry dekomponujeme modelovaný problém a jak ho rozdělíme na jednotlivé technologické procesy a jejich aktivity. Dalším pravidlem je, že aktivita může trvat libovolnou nezápornou dobu a pro své provedení může vyžadovat zdroj obsluhy. V případě nedostupnosti zdroje obsluhy, se žádající instance řadí do fronty a čekají na uvolnění zdroje. Tímto konceptem jsme schopni popsat a zapouzdřit jakýkoliv obslužný systém do technologického procesu.
42
Technologický proces 1 Aktivita 1
Aktivita 2 Aktivita 4
Aktivita 3
Provedený obslužný proces
Spuštění TP z prostředí Manažer Zdrojů 1
Blokující fronta požadavků na zdroj
Sdílená část Manažer Zdrojů 2
Požadavky jiných TP
Obrázek 14 - Koncept funkce technologického procesu
6.3.2
Aktivita
Aktivita představuje elementární hranu technologického procesu. Může mít nezáporné trvání a pro její provedení může vyžadovat zdroj obsluhy. Pro definování jednotlivých aktivit do technologického procesu jsou k dispozici tři základní typy aktivit a další doplňující, které poskytují rozšířené možnosti. Typy aktivit jsou: •
Zpožďovací aktivita (Delay Activity) – její provedení trvá nějakou dobu (jediný element, který provádí posun simulačního času)
•
Alokační / přidělovací aktivita (Seize Activity) – pro její spuštění je potřeba zdroj obsluhy. Po přidělení zdroje obsluhy se zdroj do aktivity uloží a aktivita se dokončí
•
Dealokační / uvolňovací aktivita (Release Activity) – při jejím dokončením je uvolněn uložený zdroj obsluhy
•
Kombinace výše zmíněných – typicky je potřeba kombinovat aktivitu trvání s aktivitou, která vyžaduje obslužný zdroj
•
Speciální aktivity – například aktivita, která umožní spuštění jiného technologického procesu a doba trvání je stejná jako doba trvání interního technologického procesu. Dalším příkladem je předání řízení jiné struktuře, pak aktivita čeká, dokud není znovu aktivována z vnějšího okolí danou strukturou
Příkladem jedné aktivity může být výměna zadního kola automobilu, která trvá přibližně 3 až 5 minut.
43
6.3.3
Zdroj Obsluhy
Zdrojem obsluhy se rozumí objekt (člověk, věc), který je nutný pro vykonání konkrétní obslužné aktivity. Například v modelu obchodního domu, by po vybrání produktů, měli zákazníci zaplatit na pokladně. V případě, že na pokladně není pokladní (ta v tuto chvíli představuje obslužný zdroj), nelze provést zaplacení nákupu. Tímto způsobem se vytváří fronty. Ve chvíli, kdy pokladní je k dispozici, může pokračovat v obslužném procesu a úspěšně ho tak dokončit. Zdroje obsluhy tedy omezují kapacitně provádění jednotlivých obslužných procesů a to jak interně, tak i mezi jednotlivými obslužnými procesy. Pro příklad můžeme rozšířit příklad s pokladní. Pokladen by bylo více a zákazník by si mohl vybrat, u které zaplatí. Pro všechny pokladny je zdrojem obsluhy elektřina, bez které nemůžou obsluhovat pokladní své terminály. V případě, že vypneme elektřinu (odebereme zdroj obsluhy), se zastaví veškerá činnost všech pokladen. 6.3.4
Technologický proces
Obslužný proces realizovaný síťovým grafem je v prostředí nadstavby nazván „technologickým procesem“. Ten představuje návod nebo šablonu, podle které má obecně objekt jednotlivé elementární aktivity provést a v jakém pořadí aktivity vykonat. V nadstavbě jsou vytvářeny pro agenty (obecně tedy objekty modelu) instance „technologického procesu“. Tyto instance odráží aktuální stav právě prováděného obslužného procesu. Každý agent vlastní svou instanci. Je to z toho důvodu, že každý agent může být v jiné fázi svého obslužného procesu. Technologický proces tedy zapouzdřuje posloupnost aktivit, které postupným prováděním vedou k dokončení obslužného procesu. Trvání technologického procesu je sumou délky trvání všech aktivit, které obsahuje.
6.4 Implementace Nadstavba je realizována dle návrhu v předchozí kapitole a implementována v jazyce Java. Její třídy závisí na knihovnách frameworku Repast Simphony 2. Každý hlavní objekt z návrhu má své rozhraní16 například IActivity, ITechnologicalProcess, IResource. Rozhraní je veřejná část, se kterou lze implementovat ABM. Řešení nadstavby je schválně navrženo tak, aby byl programátor nucen programovat proti výše zmíněnému rozhraní. Vytváření nových objektů je implementováno pomocí továrních tříd, které umožňují kompletně skrýt implementaci jednotlivých objektů. Skrytí implementace je důležité pro případné další rozšiřování nebo úpravu nadstavby.
16
Názvy rozhraní v nadstavbě respektují konvenci popisu rozhraní z jazyka C#, tedy každý název rozhraní začíná velkým písmenem I. Například rozhraní IOsoba.
44
Obrázek 15 – Struktura balíčků RepastS Service
Zdrojové kódy jsou rozděleny do balíčku dle logického uspořádání (viz. Obrázek 15):
•
Patterns – balíček obsahuje rozhraní pro použité návrhové vzory.
•
Processing – balíček obsahuje kód spojený s výkonnou částí kódu. o Activity – obsahuje rozhraní a implementace všech aktivit. Poskytuje veřejnou tovární třídu pro vytváření instancí jednotlivých aktivit. Ostatní třídy jsou dostupné pouze v rámci balíčku. o Technological process – obsahuje rozhraní a implementace technologického procesu.
•
Resource – obsahuje rozhraní a skeletální implementaci17 obslužného zdroje.
•
Repast interface – obsahuje pomocné třídy pro zjednodušení přístupu a použití frameworku Repast Simphony. Tyto pomocné třídy slouží také jako částečné oddělení kódu nadstavby a frameworku.
Všechny UML diagramy související s návrhem a implementací nadstavby jsou uvedeny na obrázcích v příloze A. V příloze je uveden diagram tříd pro všechny rozhraní aktivit a na dalším diagramu jejich návaznost na technologický proces. 6.4.1
Aktivita
Jednotlivé instance aktivit lze získat pomocí tovární třídy ActivityFactory (návrhový vzor factory), která poskytuje instance všech dostupných typů aktivit a zapouzdřuje tak vytváření instancí aktivit. Rozhraní aktivity definuje akce jako: start, násilně ukončit, je běžící, je ukončená a další. Základní implementace aktivity je stavová třída, která uchovává informace potřebné pro správnou funkčnost. Při vytváření aktivity, která má délku trvání, lze zadat reálné číslo (statický způsob), anebo jí lze předat objekt typu AbstractDistribution (z knihovny Colt18 1.2.0), který představuje proud náhodných čísel konkrétního pravděpodobnostního rozdělení. Aktivita si před startem načte náhodnou 17
Skeletální implementace umožňuje programátorům velmi snadno poskytnout vlastní implementace rozhraní. zdroj: [3] 18 Projekt Colt je open source projekt pro náročné vědecké a technické výpočty realizovaný v jazyku Java. Dostupný na adrese http://acs.lbl.gov/software/colt/.
45
dobu trvání a uloží si ji pro interní použití. Aktivita „s délkou trvání“ je jediná aktivita, která plánuje událost do centrálního kalendáře událostí a tím provádí posun simulačního času. Aktivita si naplánuje událost, která ji po uplynulé době znovu zpětně oznámí, že je čas pokračovat a dokončit celou aktivitu (případně provést stavové změny). UML diagram tříd a rozhraní je dokumentován v příloze A. 6.4.2
Zdroj Obsluhy
Pro zdroj obsluhy nebylo zamýšleno implementovat vlastní abstraktní třídu, protože zdrojem obsluhy může být v modelu obecně jakýkoli objekt, který implementuje rozhraní IResource. Pro případ, že by někdo chtěl použít již hotové řešení. Nadstavba poskytuje jednoduchou skeletální implementaci rozhraní v podobě třídy AbstractResource. Programátor si tedy může vybrat, zda chce přímo implementovat rozhraní nebo využít dědičnosti. V modelu se instance zdrojů nepoužívají samostatně. Využívá se takzvaného manažera zdrojů obsluhy. Objekt představující manažera zdrojů je interně navržen jako návrhový vzor Fond. Při vytvoření je v něm interně vytvořena zásoba daného počtu instancí typu IResource. Manažer pak tyto instance na požádání poskytuje a čeká na jejich vrácení. Instance manažerů lze získat pomocí statických metod třídy ResourceManagerFactory. Nadstavba poskytuje dva typy manažerů zdrojů, které se liší použitím. Níže jsou uvedeny rozhraní objektů, které vrací tovární třída manažerů:
1. IResourceManager – neumožňuje automatické čekání na zdroj, pokud zdroj není aktuálně žádný k dispozici. V případě, že nelze alokovat zdroj, generuje chybovou výjimku. Je umožněno manuální zaregistrování do fronty pomocí metody definované v tomto rozhraní. 2. IResourceManagerQueued – tento manažer je použit pro automatický technologický proces a poskytuje automatické řazení do fronty, pokud nejsou aktuálně dostupné volné zdroje. V případě potřeby má v rozhraní definovanou metodu pro odstranění čekající instance z fronty. 6.4.3
Technologický proces
Pro prostředí nadstavby představuje technologický proces síťový graf skládající se z jednotlivých aktivit (aktivita odpovídá hraně grafu). Každý technologický proces implementuje rozhraní ITechnologicalProcess, které definuje jeho základní metody. Aktuálně je k dispozici jedna implementace TP a to tzv. AutomaticTechnologicalProcess. Tato třída poskytuje implementaci, která se automaticky stará o spouštění „zaregistrovaných“ aktivit s ohledem na podmínkové aktivity, které byly předány v parametru při registraci nové aktivity. Podmínkovou aktivitou se rozumí taková aktivita, která musí být dokončena před spuštěním aktuální aktivity. V síťovém grafu je to aktivita, která vchází do vrcholu a podmiňuje tím všechny aktivity, které z vrcholu vychází.
46
Pro vytvoření a získání nové instance je nutné zavolat příslušnou statickou metodu třídy Technological TechnologicalProcessFactory. 6.4.3.1 Registrace aktivit
Registrace
aktivit
probíhá
pomocí
metody registerActivity (nová Aktivita, [výčet podmí podmínkových Aktivit]). Důležité je pochopit, jak funguje princip volání této metody, protože umožňuje vkládání a zároveň uspořádání aktivit v grafu. Princip použití je následovný. Jako první parametr se uvádí instance nově nov přidávané aktivity. Pokud má tato nov nováá aktivita čekat na dokončení jiných aktivit, je možné tyto aktivity uvést jako další parametry. Tímto způsobem lze dosáhnout i paralelního provádění aktivit. V případě použití podmínkových aktivit, musí být tyto instance již zaregistrované v TP. Příklad definice paralelního provádění: ITechnologicalProcess tp = TechnologicalProcessFactory .createAutomaticTechnologicalProcess createAutomaticTechnologicalProcess(); tp.registerActivity( .registerActivity(pridelitPokladni); tp.registerActivity( .registerActivity(namarkovatNakup, pridelitPokladni); tp.registerActivity( .registerActivity(vytahnoutPenezenku, pridelitPokladni); Pokladni); tp.registerActivity(zaplatitNakup, .registerActivity(zaplatitNakup, vytahnoutPenezenku, namarkovatNakup); tp.registerActivity(uvolnitPokladni, .registerActivity(uvolnitPokladni, zaplatitNakup);
Vizuální podoba obslužného procesu pro výše zmíněný kód dokumentuje Obrázek 16. Názvy proměnných v kódu pro názornost odpovídají názvům hran v obrázku. V kódu jsou podtržením označeny aktivity, které se po spuštění technologického plánu provedou současně.
Obrázek 16 – Technologický echnologický proces nákupu s paralelní činností
6.4.4
Vizuální podpora
Vizuální podpora jako taková není potřeba, protože ji Repast Simphony již řeší implicitně. Běhové prostředí poskytuje konfigurovatelné vizualizační prostředí pro zobrazování obrazování stavového prostoru agentově orientovaného modelu. Vizualizační možnosti jsou relativně široké a lze částečně implementovat i vlastní mechanizmy vizualizace na základě informací ze stavového prostoru modelu. 47
Jak bylo již zmíněno, problém při provádění aktivity obslužného procesu nespočívá v její vizualizaci, ale v tom, jak se projeví provádění aktivity ve stavovém prostoru. Proto byla pro potřeby aktivit doplněna podpora pro automatický pohyb. Automatický pohyb je volitelná součást k aktivitám (přidává se pomocí parametru při vytváření aktivity). Přidává možnost automatického pohybu jednotlivých účastníků při provádění aktivity. Účastníkem může být objekt, který spouští aktivitu (dále ho budeme nazývat „exekutorem“), alokovaný zdroj nebo bod v prostoru. Rozhraní IActivityMovementParams definuje potřebné informace pro vytvoření různých podporovaných typů pohybů. Například informace pro pohyb „exekutora ke zdroji“ nebo „zdroje ke specifikovanému bodu“ v prostoru. Instance parametrů lze přidat jako parametr při vytváření aktivity a tím zapnout automatický pohyb účastníků dané aktivity. Pro generování instancí parametrů pohybu je potřeba získat instanci rozhraní IActivityMovementParamsFactory, která se stará o konstrukci správných instancí parametrů pohybu pro daný typ projekce. Pro tyto potřeby je implementována třída ActivityMovementParamsFactory. Tato třída vytváří pro různé projekce odlišné implementace rozhraní IActivityMovementParamsFactory (podle návrhového vzoru abstract factory). Pomocí tohoto návrhového vzoru dosáhneme nezávislosti pohybu na projekci, lze tedy případně implementovat pohyb i v dalších projekcí. Aktuální implementace poskytuje automatický pohyb pro nejpoužívanější projekci a to tzv. „souvislého prostoru“ (z angl. continuous space).
48
7 Případové studie obslužných systémů Případové studie byly zvoleny pro ověření aplikovatelnosti softwarové nadstavby v různých typech agentově orientovaných modelů s obslužnými systémy a minoritně pro prozkoumání možností platformy Repast Simphony 2. V následujících kapitolách budou uvedeny 3 případové studie. Každá z nich má jiný specifický cíl, který bude uveden v jejím popisu. Popis případové studie zahrnuje obecné představení modelované situace, popis modelu a jeho konceptuální návrh, ukázku realizace zace a vyhodnocení vzhledem k cíli případové studie.
7.1 Model M/M/1 Tato případová studie se zaměřuje na jednoduchý exponenciální model označován v teorii hromadné obsluhy jako M/M/1. Je zvolen kvůli své jednoduchosti a z důvodu existence analytického řešení systému. Tento model předpokládá jednu obslužnou linku s dobou oobsluhy, bsluhy, která se řídí exponenciálním rozdělením a předpokládá vstup jednotek do systému také pod exponenciálním rozdělením. Není – li dáno jinak, předpokládá se systém fronty typu FIFO a neomezený počet míst ve frontě. [27] Implementace modelu byla realizována ve spolupráci s panem Bc. Jiřím Popelkou, který realizoval model pomocí metody snímání aktivit. V závěru bude tedy uveden pouze výsledek jeho experimentu a v této práci bude model řešen asynchronní metodou plánování událostí událostí.
fronta
Obrázek 17 – Ukázka modelu M/M/1 ve vizuálním prostředí
7.1.1
Cíle případové studie
Cílem této případové studie je ověřit správnou funkčnost simulační platformy Repast Simphony 2. Funkcionalita bude ověřena implementací modelu do prostředí frameworku a experimentální metodou se bude zjištěna střední hodnota doby pobytu zákazníka ve frontě.. Následně budou porovnány experimentální výsledky s analytickým řešením systému.
49
7.1.2
Parametry modelu
Obecný popis modelu byl uveden na začátku kapitoly. Pro porovnání je potřeba definovat počáteční podmínky pro experiment, analytické řešení a následné porovnání. Parametry modelu jsou: •
exponenciální vstupní proud o intenzitě λ = 1 (znamená průměrně 1 požadavek obsluhy za 1 časovou jednotku)
•
exponenciální intenzita obsluhy µ = 10 / 9 (znamená, že obsluha je schopna průměrně obsloužit 9 zákazníků z 10)
Implementace modelu pro následné experimentování proběhne dvěma přístupy a to:
•
Asynchronní metodou plánování událostí – představitel diskrétní metody.
•
Synchronní metodou snímání aktivit – v našem případě představitel spojité metody.
Parametrem pro porovnání je střední hodnota doby pobytu zákazníka ve frontě. Ta by se v případě experimentálního zjištění (při dostatečném počtu opakování nebo délce simulace) měla blížit analytickému řešení. 7.1.3
Analytické řešení systému M/M/1
Následující text byl převzat z materiálu [12]. Níže je uvedeno exaktní řešení pro simulovaný obslužný model M/M/1 se zvolenými parametry. Intenzita vstupního proudu: λ [zákazníků/jednotku času] Intenzita obsluhy: μ [zákazníků/jednotku času] Využití linky obsluhy: ρ=(λ/μ)x100 [%] Průměrný počet zákazníků v systému: L = λ/(μ-λ) [zákazníků] Průměrný pobyt zákazníka v systému: w = 1/(μ-λ) [čas. jednotek] Průměrný pobyt zákazníka ve frontě: wQ = λ/(μ(μ-λ)) [čas. jednotek] λ = 1 zákazník/min μ = 10/9 zákazníků/min ρ = (λ/μ) x 100 = 90 % L = λ / (μ-λ) = 9 zákazníků w =1/(μ-λ) = 9 minut wQ=λ/(μ(μ-λ)) = 8,1 minuty
7.1.4
Závěr
Experimentálním způsobem byl naměřen výsledný průměrný čas, který stráví zákazník ve frontě. Průměr se rovná 8,06 ± 0,49 jednotky času. Jelikož je analytické řešení 50
v intervalu spolehlivosti, můžeme říci, že se výsledky přibližně rovnají. Tímto závěrem je tedy ověřena funkčnost simulační platformy Repast Simphony 2. Pan Bc. Popelka Jiří ve svém modelu dospěl k podobnému u řešení, které dokazuje, že i synchronní metodou snímání aktivit aktivit, lze dosáhnout experimentální cestou stejného řešení. Podrobná data z měření jsou přiložena v souboru na přiloženém CD.
7.2 Model pneuservis V této případové studii bude objektem zkoumání model pneuservisu. Zadání pro případovou studii bylo převzato ze studijních materiálů [11], [12] a je uvedeno v popisu modelu. Hlavní motivací tohoto modelu je realizace typického obslužného systému v agentově orientované platformě Repast Simphony 2. 7.2.1
Popis
Velká provozovna pneuservisu se připravuje na kritické období před nástupem zimní sezóny, kdy (jako každoročně) očekává obrovský zájem motoristů o výměnu výměn pneumatik na vozidlech. V tomto roce se v provozovně rozhodli, v rámci zhruba tří kritických týdnů, vyčlenit svoji velkou dílnu pouze pro účely provádění výměn letních pneumatik za zimní.
Obrázek 18 – Ukázka modelu pneuservisu ve vizuálním prostředí
Na obrázku B.1 jsou uvedeny technologické postupy dvou typů výměn pneumatik ve formě síťových grafů. Jednotlivé orientované hrany těchto grafů odpovídají elementárním tárním technologickým činnostem. U každé hrany je na uvedeném u obrázku v závorce popsán typ zdroje (Z – zvedák, M – montážní mechanik, V – vyvažovací zařízení spolu s mechanikem – vyvažovačem [uvažováno ováno jako nedělitelná dvojice]), dvojice který je pro zabezpečení této činnosti potřebný. Podle aktuální disponibility zdrojů, resp. 51
uplatňované řídící strategie, je možné každé technologické činnosti (kromě vjezdů nebo výjezdů ze zvedáku) přidělit 1–2 instance potřebného typu zdroje, přičemž počet aktuálně přidělených instancí ovlivní dobu potřebnou k provedení této činnosti. Pro potřeby modelování technologických procesů jsou prezentovány na obrázku A.2 elementární technologické aktivity, které jsou „obohaceny“ o alokace a dealokace obslužných zdrojů, případně o jejich nástupy a odstupy (způsobují časové prodlevy) od obsluhovaných objektů. 7.2.2
Cíle případové studie
V tomto simulačním modelu se zaměříme na integraci vyvinuté nadstavby do servisně orientovaného modelu tak, aby usnadnil jeho implementaci a případně umožnil jeho jednoduché rekonfigurování či rozšíření. Lze tedy říci, že cílem studie je praktické použití nadstavby pro realizaci modelu a následné zhodnocení náročnosti implementace. 7.2.3
Návrh
V první fázi identifikujeme hlavní problém, který model řeší. Model má modelovat situaci, kde zákazníci požadují dva typy obsluhy (každý z obslužných procesů je popsán síťovým grafem na obrázku B.1). Zákazníci vstupují do systému s určitou intenzitou λz a jsou obsluhováni příslušnou technologickou linkou. V případě, že není dostupná žádná linka, zákazníci čekají na odbavení. 7.2.3.1 Definice entit, agentů a chování
V agentově orientovaném modelu je potřeba specifikovat, které entity budou představovat agenty a jakou budou mít odpovědnost a chování. Přehled navržených agentů a jejich chování: •
Vstupní agent – vytváří nové zákazníky dle parametrů pravděpodobnostního rozdělení (pro náš případ je to exponenciální rozdělení) a vkládá je do modelu.
•
Výstupní agent – odebírá zákazníky ze systému.
•
Agent zákazník – jeho úkolem je pohybovat se v prostoru, najít agenta pneuservisu, účastnit se technologického procesu, po úspěšné obsluze odejít z pneuservisu
•
Agent pneuservisu – jeho úkolem je identifikovat požadavek zákazníka a vygenerovat příslušný technologický proces Přehled zdrojů obsluhy:
•
Montážní technik
•
Vyvažovací technik
•
Zvedák – zvedá zákazníkovo vozidlo, aby bylo možné provést opravu
•
Vyvažovací přístroj – používá ho vyvažovací technik pro vyvážení pneumatik 52
7.2.3.2 Volba prostředí
Při volbě prostředí musíme zvážit požadavky na model. Jeden z požadavků je vizuální prezentace stavových změn. Protože cílová platforma umí implicitně zobrazovat pouze stavový prostor a změny v něm, je potřeba zvolit takové prostředí, ve kterém se agenti mohou pohybovat. Z toho také plyne, že prostorová aktivita agentů je relevantní a je nutné zvolit prostorové prostředí. 7.2.3.3 Volba komunikačního mechanizmu
V tomto případě nebudeme zavádět žádný specializovaný mechanizmus komunikace. Agenti spolu komunikují přímým voláním metod druhé instance. Jediné omezení je prostorové. Agenti mohou komunikovat pouze s agenty v jeho těsném prostorovém okolí. 7.2.3.4 Koncept fungování modelu
Nyní je potřeba specifikovat, jak bude celý model fungovat. V první řadě se agenti zákazníků dostaví k agentovi pneuservisu. Zákazník podá požadavek na konkrétní typ obsluhy a agent pneuservisu vygeneruje příslušný obslužný proces v podobě technologického procesu. Zákazník začne provádět jednotlivé akce dle poskytnutého TP. Technologický proces zapouzdřuje posloupnost činností tak, jak jsou popsány v síťovém grafu na obrázku B.1. Pokud jednotlivé činnosti potřebují pro své provedení zdroj obsluhy, čekají až do doby, kdy je daný zdroj obsluhy dostupný. V případě, že není dostupný žádný volný zvedák pro vozidlo zákazníka, tak si zákazník stoupne do fronty, kde čeká na uvolnění zvedáku. Po dokončení technologického procesu zákazník odchází směrem k agentovi výstupu, kde je odstraněn z modelu. 7.2.4
Parametry modelu a simulační scénáře
7.2.4.1 Scénář 1 Scénář předpokládá neomezený provoz. Je nutné experimentálním způsobem zjistit, kolik je potřeba najmout zaměstnanců, aby ve frontě před pneuservisem stáli v průměru max. 3 zákazníci. Pro tři zákazníky pneuservis připravil čekárnu s kávovarem a posezením, kde by měli zákazníci pohodlně strávit čas, než se dostanou na řadu. Hlavní cíle optimalizace: • průměrný počet zákazníků [Xp<= 3] • využití zdrojů [MAX] • počet zaměstnanců (typ Z, M i V) [MIN]
7.2.4.2 Scénář 2 Scénář s omezenými zdroji. Pro každou montážní směnu je k dispozici 5 montážních techniků a 3 vyvažovací technici. Vedení pneuservisu zajímá, zda má smysl rozšířit dílnu o další zvedák (stávající řešení má k dispozici 2 zvedáky). Hlavní cíle optimalizace: • průměrný počet čekajících zákazníků [MIN] • využití zdrojů [MAX]
53
7.2.5
Výsledky
7.2.5.1 Scénář 1
č. 1 2 3 4 5 6 7 8
Z 2 3 4 3 3 3 3 3
V ∞(4) ∞(6) ∞(8) 5 4 3 3 4
M ∞(4) ∞(6) ∞(8) 5 4 3 4 5
Využití zdrojů (Z, V, M) [%] 99,5%; 35,2%; 47,2% 85,6%; 30,1%; 40,5% 64,7%; 22,7%; 30,5% 86,3%; 36,0%; 48,8% 91,0%; 47,0%; 63,25% 94,6%; 61,0%; 82,0% 93,3%; 61,3%; 61,7% 87,0%; 45,7%; 49,0%
Průměrný počet čekajících 123,03 2,37 0,37 2,25 3,50 4,18 11,51 3,12
Tabulka 1 – Výsledky experimentu pneuservisu podle scénáře 1
Výsledky experimentů pneuservisu poměrná hodnota (pro účely porovnání)
140 120 100 80
počet zdrojů [min] využití zdrojů [max]
60
Průměrný počet čekajících 40 20 0 1
2
3
4
5
6
7
8
Graf 1 - Výsledky experimentu pneuservisu podle scénáře 1
7.2.5.2 Scénář 2
č.
Z 1 2
V 2 3
M 3 3
Využití zdrojů (Z, V, M) [%] 5 5
99.5 90.1
46 60.3
Průměrný počet čekajících 37.2 48.6
Tabulka 2 - Výsledky experimentu pneuservisu podle scénáře 2
54
194.2 3.68
Výsledky experimentů pneuservisu poměrná hodnota (pro účely porovnání)
200 180 160 140 120 počet zdrojů [min]
100
využití zdrojů [max]
80
průměrný počet čekajících 60 40 20 0 1
2
Graf 2 - Výsledky experimentu pneuservisu podle scénáře 2
7.2.6
Závěr případové studie
Platforma Repast Simphony 2 nativně nepodporuje vyhodnocování dat mezi jednotlivými běhy simulačního modelu (tzv. replikacemi). Proto byl u všech měření zvolen přístup dostatečně dlouhého simulačního běhu, který zajistí ustálení hodnot. Z měření modelu nastaveného dle prvního scénáře bylo zjištěno, že optimální konfigurace (zaměstnanců a techniky) byla v simulačním experimentu č. 8 (viz. Tabulka 1). U této konfigurace sice byl zanedbán patrný přesah zadané podmínky, že průměrný počet zákazníků ve frontě musí být maximálně 3 (naměřený průměrný počet je 3,12), ale v celkovém zhodnocení vyhovuje ze všech nejvíce. Graf 1 zobrazuje data pro vizuální porovnání. Je z něj i patrné, že simulační experiment č. 6 sice nesplňuje původní podmínku, ale do budoucnosti by to byla větší úspora pro provozovatele pneuservisu. Čekárna by se rozšířila o další místo pro dalšího zákazníka a v pneuservisu by stačili pouze 3 montážní a 3 vyvažovací technici. Z dlouhodobého hlediska je výhodnější zaměstnávat o 3 zaměstnance méně. Z naměřených hodnot druhého scénáře vyplynulo, že se vyplatí investovat do dalšího zvedáku. Graf 2 zachycuje, že přidáním dalšího zvedáku se sníží počet čekajících zákazníků a zároveň bude stávající počet zaměstnanců lépe vytížen. Z pohledu náročnosti výstavby modelu, je samotná implementace obslužného systému minimalizována právě vyvinutou nadstavbou. Pokud by tato případová studie nesloužila jako demonstrační příklad pro servisně orientovanou nadstavbu, bylo by už v době návrhu vyhodnoceno, že se tento model nehodí realizovat v agentově orientovaném prostředí. Například Arena Simulation Software (od firmy Rockwell Automation) je 55
prostředí, se kterým se mohou studenti setkat při výuce předmětu modelování a simulace. Tento software podporuje vizuální tvorbu modelu pomocí definování a spojování funkčních bloků. Tento model by tímto nástrojem byl realizován mnohem rychleji a jednodušeji. Pokud vezmeme v potaz i znalost programovacího jazyka, tak pro práci s nástrojem Arena není jeho znalost vůbec vyžadována.
7.3 Model výstaviště Model výstaviště je zvolen kvůli jeho vhodnosti pro modelování v agentově orientovaném prostředí. Předmětem modelování by měl být náhodný pohyb zákazníků (agentů) po hale výstaviště, kde se zákazník rozhoduje, který stánek by chtěl navštívit a něco si zakoupit. Dále poskytuje vhodné podmínky pro lokální obslužné systémy v podobě stánku na výstavišti, kde si mohou zákazníci prohlédnout, anebo si koupit nějakou věc zájmu. Tento model by měl umožnit kompozici typického agentově orientovaného modelu s obslužnými systémy realizovanými pomocí vyvinuté nadstavby. 7.3.1
Popis
Výstaviště je velká hala, kde se každoročně uskutečňuje přehlídka jednotlivých firem, které se zabývají oblastí informačních technologií. Všechny firmy si navážejí své zásoby propagačních materiálů a produktů k prodeji do skladu, který je pro tyto účely postaven přímo u areálu výstaviště. Před otevřením výstaviště mají firmy možnost si dopravit libovolné množství produktů přímo do propagačního stánku, kde si je budou moci po otevření koupit návštěvníci. Návštěvníků je každým rokem čím dál více a majitele výstaviště by zajímalo, jaká je maximální intenzita a kapacita výstaviště při letošní topologii rozmístění stánků (viz obrázek C.1), aby v reálném provozu nedošlo k nehodám zapříčiněných právě velkým počtem návštěvníků na výstavišti. Dle interních pravidel výstaviště se mohou stánky stavět pouze po obvodu vnějších stěn, anebo po obvodu stěny vnitřního sloupu, jak je dokumentováno na schématu níže.
56
Obrázek 19 – Schéma topologie výstaviště
Zelená šipka na schématu označuje, odkud přichází vstupní proud návštěvníků. Červená šipka naopak místo, kudy mají možnost návštěvníci odcházet. Na schématu je také dokumentováno umístění skladu, ze kterého vyjíždí zásobovací vozíky. Výstaviště disponuje dispečerem skladu, který sbírá požadavky na dodávku z jednotlivých stánků, řídí skladištní prostor a přerozděluje kompetence zásobování výstaviště na jednotlivé vozíky. 7.3.2
Cíle případové studie
Prezentovat nativní možnosti simulační platformy Repast Simphony 2 v kombinaci s vyvinutou nadstavbou. Mezi prezentovanými možnostmi bude: •
Autonomní pohyb zákazníka
•
Autonomní centrálně řízená zásobovací sekce výstaviště
•
Lokální obslužný systém jednoho stánku je realizován vyvinutou nadstavbou.
7.3.3
Návrh
V případě modelu výstaviště je více hlavních problémů, jelikož se nejedná o triviální model. V tomto modelu je nutné řešit problém autonomního pohybu na úrovni agenta. Dále řízení a koordinaci skladovací části výstaviště, obslužný proces na úrovni jednotlivého stánku a kompletaci infrastruktury výstaviště. 7.3.3.1 Definice entit, agentů a chování
V další fázi návrhu provedeme rozdělení a klasifikaci jednotlivých entit, které se vyskytují v modelu. V přehledu entit provedeme i výčet chování a jednotlivých odpovědností, které entity v modelu budou mít. Seznam entit a agentů: •
Vstupní agent – vytváří nové zákazníky dle parametrů pravděpodobnostního rozdělení (exponenciální) a vkládá je do modelu. 57
•
Výstupní agent – odebírá zákazníky ze systému.
•
Návštěvník – pohybuje se po prostředí výstaviště, nakupuje ve stáncích.
•
Stánek – řídí svůj obslužný proces nákupu, kontroluje stav zásob (s predikcí podává požadavek dispečerovi na doplnění).
•
Prodávající osoba – zdroj obsluhy pro stánek.
•
Zásobovací vozík – pohybuje se po prostoru mezi návštěvníky, nakládá a rozváží zboží dle požadavků.
•
Zásobovací dispečer – sbírá požadavky na doplnění zásob a přerozděluje je na jednotlivé zásobovací vozíky.
7.3.3.2 Volba prostředí
Dalším krokem je zvolit vhodné prostředí pro realizaci modelu. Volba prostředí by byla nejrealističtější v tzv. „spojitém prostoru“ (reálné souřadnice), ale protože framework zatím neumožňuje implicitně řešit problém kolizí ve spojitém prostoru, zvolíme pouze prostředí mřížky (ve frameworku je označován jako Grid). V rámci abstrakce modelu budeme muset zvolit nejmenší velikost jedné buňky mřížky tak, aby odpovídala velikosti jednoho návštěvníka. Ostatní velikosti budou voleny v poměru, aby se výsledný model blížil realitě. Tato abstrakce souvisí s implementací projekce mřížky ve frameworku. Je to z toho důvodu, že framework nepočítá s proměnlivou velikostí agentů a projekce mřížky nebyla pro tento účel přizpůsobena. 7.3.3.3 Volba komunikačního mechanizmu
Speciální komunikační mechanizmus pro tento model nebudeme zavádět. Umožníme komunikovat agentům přímým voláním instančních metod, ale pouze v případě, že jsou agenti prostorově v těsném kontaktu. 7.3.3.4 Koncept fungování modelu
Fungování modelu rozepíšeme po částech podle typu problému, který se v modelu řeší. První popíšeme funkcionalitu návštěvníka. Návštěvník si při příchodu do modelu vybere několik míst (stánků), které by chtěl navštívit. Vybere si libovolný stánek ze svého seznamu a pohybuje se směrem k němu. V případě, že se ke stánku nemůže dostat (například je u stánku spoustu lidí), pak si vybírá ze seznamu další stánek, stávající odloží na později. Dále u návštěvníka zavedeme tzv. „odmítnutí“. Odmítnutí nastává, pokud má zákazník problém se dostat k jakémukoliv stánku po dlouhou dobu. Příčinnou může být velká zácpa, chyba v infrastruktuře atd. V tomto případě se návštěvník rozhodne odejít z modelu a stánky dále nenavštěvuje. Úroveň spokojenosti návštěvníka hodnotíme podle splněných plánů. Spokojený návštěvník navštívil všechny plánované stánky a jeho spokojenost odpovídá 100%. Návštěvník navíc disponuje jedním speciálním chováním a to
58
pro případ, kdy se blíží k agentovi zásobovací vozík. V tomto případě se agent snaží vozíku vyhnout. Dalším objektem je stánek, který slouží jako nákupní místo a temporární sklad produktů. Každý stánek má určitý počet interních prodávajících osob. Tyto osoby představují obslužné zdroje potřebné pro nákup. Nelze tedy, aby nastala situace, kdy u stánku nakupuje více návštěvníků než je počet obslužných zdrojů. Stánek při vydávání zboží kontroluje, zda má dostatečný počet zásob. V našem případě stačí, aby při kontrole bylo na skladě více než 20% maximální skladovací kapacity stánku. Pokud není, tak stánek pošle požadavek centrálnímu skladu, že by potřeboval doplnit zásoby produktů. Vizuální podoba stánku odráží stav zásob, které má k dispozici. Plně zásobený stánek je světle zelený a s úbytkem zásob přechází do červené barvy. Sytě červená označuje stánek bez skladových zásob. Pro zásobování jednotlivých stánků výstaviště disponuje sekcí skladu, kde je centrální dispečer a zásobovací vozíky. Dispečer sbírá požadavky od stánků, přerozděluje je a systematicky deleguje jejich vyřízení na dostupné zásobovací vozíky. Aktuální návrh je takový, že se může vozíkům přidělit určitý maximální počet požadavků (daný konfigurací modelu) na jednu cestu. Zbylé požadavky čekají na další vozík. Ve chvíli, kdy vozík dostane požadavek ke zpracování, začne nakládat potřebné množství nákladu a po naložení odjíždí na výstaviště. Vozík při rozhodování, který stánek obslouží, volí vždy cestu k nejbližšímu stánku, u kterého zatím nevyložil zásoby. Toto navržené řešení není globálně optimální, ale je pro účely modelu vyhovující. Implementace optimálního řešení je námět k dalšímu rozšíření případové studie. Tento problém se obecně nazývá „problém obchodního cestujícího“ a jeho popisem a efektivním řešením se zabývá publikace [11]. 7.3.3.5 Implementační detaily
V poslední fázi vysvětlím některé řešení, které souvisí s implementaci frameworku a modelu. Mřížka (Grid) implicitně umožňuje obsazení jedné buňky pouze jedním agentem. Tuto vlastnost využijeme pro řešení kolizí v prostoru. Nebude tedy možné, aby dva agenti měli stejné kartézské souřadnice, nebo aby agent prošel infrastrukturou, která je již od začátku vložena do prostředí mřížky. 7.3.4
Problémy
Jeden z problémů byl zapříčiněn špatným použitím frameworku. Ve chvíli, kdy je pro projekci mřížky nastaveno, že do každé buňky může být vložen pouze jeden agent, může vzniknout situace, kdy model „zamrzne“. Je to způsobeno implicitní implementací pro vkládání objektů do projekce. Pokud se vloží objekt do buňky, kde už nějaký objekt je, implicitní implementace na to není připravena. Dojde k výjimce, která ukončí běh celé simulace. Problém byl vyřešen vlastním umísťovacím objektem, který v případě vkládání na obsazené místo, zvolí náhodně v blízkosti jinou volnou buňku. V průběhu implementace modelu se vyskytl i další problém, který nebyl z počátku identifikován jako významný. Při realizaci autonomního chování návštěvníka se na začátku předpokládala relativně jednoduchá implementace chování chodce (návštěvníka). Původní 59
implementace byla navržena tak, aby se agent mohl pohybo pohybovat vat přímým směrem k cíli (umožňuje framework).. Pro případ, že narazil na překážku, měl agent k dispozici heuristickou funkci, která z jeho okolí vypočítala nejvhodnější pole pro další krok. Tento přístup je funkční a byl úspěšně verifikován. Bohužel v agentově tově orientovaném prostředí, kde mnoho agentů provádí stejným způsobem ve stejnou chvíli podobné chování, dochází k tzv. „utlačování“. Přii stávající topologii existovala místa, kde se dalo předpokládat, že agenti budou při obcházení překážek řešit tento problém.. Bohužel, při velkém počtu, počtu byli první agenti obklopeni ostatními agenty a nebyl jim umožněn další pohyb.
Obrázek 20 – Vizuální ukázka výstaviště s problémem utlačování
Po prozkoumání dané problematiky, kte kterou se zabývá publikace [15] a [28], jsem se rozhodl vypracovat řešení pomocí gradientních map a využít množinu předem vytvořených map jako datovou strukturu, která umožní agentům lep lepší ší orientaci v prostoru a určit optimální trasu. Tedy základní chování pro o nalezení překážky zůstává, ale nepoužívá se přímý pohyb k cíli. Pro pohyb je využita metoda zvaná „následování gradientu“, kde si agenti z gradientní mapy „přečtou“, kterým sm směrem ěrem vede optimální cesta k cíli. Pro názornost je níže dokumentována vizualizace prostředí po zavedení gradientních map. Vizuální ukázka stavuu systému je sejmuta přibližně ve stejném simulačním simulační čase.
60
Obrázek 21 – Vizuální ukázka výstaviště po aplikování gradientních map
7.3.4.1 Gradientní mapa
Pro naše potřeby jsem implementoval jednoduchý algoritmus pro vytvoření dvou dimenzionální gradientní mapy. Algoritmus pracuje ve dvou fázích: 1) Vytvoření dvourozměrného pole se vzdálenostmi od počátku počáteční lokace (x0,y0) (pole má stejný počet polí, jako má modelovaná mřížka). 2) Vytvoření dvou rozměrného pole s hodnotami směru (ukládané v radiánech) Vytvoření 2D pole se vzdálenostmi proběhne za pomocii datové struktury „fronta“. a“. Následující pseudokód demonstruje algoritmus:
61
function vytvorPoleVzdalenosti (){ fronta = new Fronta(); počátečníBuňka = new Buňka(); počátečníBuňka.x = 5; počátečníBuňka.y = 1; počátečníBuňka.hodnota = 0; fronta.vlož(počátečníBuňka); while(fronta.jePrazdná() == false){ aktuálníBuňka = fronta.vyber(); vytvorOkolniBuňky(aktuálníBuňka, fronta); } } function vytvorOkolniBuňky(buňka, fronta){ if(zkontrolujRozmery(buňka.x, buňka.y)) return; pole[buňka.x, buňka.y] = buňka.hodnota; //uložíme hodnotu do vytvářeného pole novaHodnota = buňka.hodnota + 1; fronta.vlož(new Buňka(buňka.x, buňka.y -1, novaHodnota)); fronta.vlož(new Buňka(buňka.x, buňka.y+1, novaHodnota)); fronta.vlož(new Buňka(buňka.x+1, buňka.y, novaHodnota)); fronta.vlož(new Buňka(buňka.x-1, buňka.y, novaHodnota)); fronta.vlož(new Buňka(buňka.x-1, buňka.y-1, novaHodnota)); fronta.vlož(new Buňka(buňka.x-1, buňka.y+1, novaHodnota)); fronta.vlož(new Buňka(buňka.x+1, buňka.y-1, novaHodnota)); fronta.vlož(new Buňka(buňka.x+1, buňka.y+1, novaHodnota)); } Obrázek 22 – Pseudokód vytvoření gradientní mapy (vzdáleností)
V další fázi se vytvoří druhé pole, které doplní informaci o směru. Ten projde postupně všechny buňky a v každém kroku zvolí směr k nejnižší hodnotě uložené v buňce v těsném okolí. Pro názornost je příklad demonstrován na obrázcích níže (Obrázek 23 znázorňuje okolí buňky s hodnotou 44 a zvolený směr, kde šedé místo je překážka s hodnotou ∞).
Obrázek 23 – Gradientní mapa (vzdálenosti)
62
Obrázek 24 – Gradientní mapa (směry)
Pro lepší vizuální představu je na obrázku C.2 zdokumentováno testovací prostředí, kde je zobrazeno hodnotové pole. Velikost pole je velká a hodnoty v jednotlivých buňkách by nebyly vidět, hodnoty jsou pro názornost nahrazeny barvou. Na obrázku prostředí se objevuje zelená barva (představuje vysoké hodnoty) a pomalu přechází do barvy černé (představuje minimum). Na dokumentovaném obrázku se vyskytuje ještě modrá barva, která představuje překážky. Agenti při svém pohybu směřují k minimálním hodnotám. Cíleným sledováním gradientní mapy dojde k automatickému obcházení statických překážek a cestování po optimální trase. Minimum představuje cílový bod. Obrázek C.3 dokumentuje příklad gradientní mapy z modelu výstaviště (Cílový stánek se vyskytuje vpravo dole). 7.3.5 Parametry modelu a simulační scénář Mezi parametry modelu, které jsou platné pro všechny scénáře, patří:
•
Pohyb zákazníků je částečně náhodný. Snaží se následovat optimální trasu ke zvolenému bodu zájmu (využívá gradientní mapu), ale interval odečítání optimálního směru je náhodný. Interval se zmenšuje s přibližováním k bodu zájmu.
•
Při vstupu agentů do systému je volba jednotlivých stánků z rovnoměrného rozdělení.
•
Rozměr jedné buňky mřížky je zvolen na 0,5 metru a ostatní rozměry jsou přizpůsobeny v tomto poměru, aby přibližně odpovídali realitě.
•
Zásobovací agenti se pohybují v prostoru výstaviště spolu s návštěvníky a autonomně si volí cestu k zásobovanému místu.
7.3.5.1 Scénář 1
Scénář předpokládá neomezený počet zásob v systému. Hlavním úkolem je zjistit, jaká je maximální intenzita vstupního proudu, aby nedocházelo k zahlcení systému (při stávající topologii infrastruktury). Stav zahlcení systému identifikujeme tak, že není umožněno návštěvníkům odejít z výstaviště, anebo je v systému zaplněno více než 60%70% plochy (počítají se stánky i návštěvníci). V této situaci tedy nejsou již vhodné podmínky pro pohodlný pohyb po výstavišti. 63
Hlavní cíle optimalizace:
•
intenzita vstupního proudu [MAX]
7.3.5.2 Scénář 2
Scénář předpokládá omezený počet zásob a 2/3 intenzitu vstupního proudu návštěvníků, která byla zjištěna při neomezeném provozu. V modelu probíhá kontinuální doplňování zásob z připraveného skladu. Výstaviště momentálně disponuje 6 zásobovacími vozíky. Provozovatele by zajímala optimální konfigurace vozíků a predikce stánků, aby bylo možné zabezpečit co možná nejvyšší spokojenost návštěvníků. Dále by provozovatele výstaviště zajímalo, zda má velký vliv doba nakládání zboží na celkový provoz skladu (lze zajistit brigádníky, aby bylo umožněno nakládat 2x rychleji). Hlavní cíle optimalizace: •
spokojenost návštěvníků [MAX]
•
predikce zásobování [MIN]
•
počet zásobovacích vozíků [MIN]
7.3.6
Výsledky
7.3.6.1 Scénář 1
č. intenzita vstupu prům. spokojenost [%] prům. počet návš. v systému [ks] 0.5 49.3 279 1 0.6 48.8 331 2 0.7 49.6 425 3 0.725 52.2 450 4 0.75 64.2 1150 5 0.8 68.8 1100 6 0.9 60.8 2000 7 Tabulka 3 - Výsledky experimentu výstaviště podle scénáře 1
64
trend ustálený ustálený ustálený ustálený rostoucí rostoucí rostoucí
poměrná hodnota (pro účely porovnání)
Výsledky experimentu výstaviště 80 70 60 50 40
intenzita vstupu
30
prům spokojenost [%]
20
prům. počet návš. v systému [ks]
10 0 1
2
3
4
experiment č.
Graf 3 - Výsledky experimentu výstaviště podle scénáře 1
7.3.6.2 Scénář 2 č. vozíků [ks] predikce stánků [%] spokojenost [%] doba nakládání 6 20 47.75 0 1 6 35 47.38 0 2 6 50 47.33 0 3 6 70 38.47 0 4 3 20 34.03 0.5 5 4 20 36.13 0.5 6 5 20 46.23 0.5 7 6 20 47.13 0.5 8 6 35 47.66 0.5 9 6 50 45.98 0.5 10 Tabulka 4 - Výsledky experimentu výstaviště podle scénáře 2
Výsledky výstaviště scénář 2 60 50 40 30
Vozíků [ks]
20
predikce stánků [%]
10
spokojenost [%]
0 5
6
7
8
9
10
č. experimentu Graf 4 - Výsledky experimentu výstaviště podle scénáře 2
65
Porovn Porovnání ání s nulovou dobou nakládání (přerušovaně je zkrácená doba nakládání)
60 55 50 45 40 35 30 25 20
predikce stánků [%] spokojenost [%] predikce stánků [%] spokojenost [%] 1
2
3
experiment č. Graf 5 - Výsledky vlivu doby nakládání na spokojenost návštěvníků
7.3.7
Závěr případové studie
Platforma Repast Simphony 2 nativně nepodporuje vyhodnocování dat mezi jednotlivými běhy simulačního modelu (tzv. replikacemi). Proto byl u všech měření zvolen přístup dostatečně dlouhého simulačního běhu, který zajistí ustálení hodnot. V prvním scénáři by byla la zjištěna maximální intenzita vstupního proudu návštěvníků. Identifikace zahlceného systému byla zjišťována vizuálně a pomocí trendu grafu aktuálního počtu zákazníků v systému. V případě zahlcení počet zákazníků stále roste (není umožněn odchod ze systém systému). u). Proto nejsou při vyhodnocení uvažovány experimenty s rostoucím trendem. Maximální intenzita, při které „ještě“ nedošlo k zahlcení je 0,725 (experiment č. 4). K zahlcení došlo v místě východu (viz. Obrázek 25). ). Pro další zvyšování intenzity by bylo nutné zvětšit (nebo jinak upravit) stávající východ.
Obrázek 25 – Zahlcený východ výstaviště
66
Dle zadání druhého scénáře byla zjištěna optimální konfigurace pro provoz výstaviště. Z tabulky uvedené v kapitole s výsledky a grafu, lze vyhodnotit, že (spokojenost [max] – predikce [min] – počet vozíků [min]) je optimální v experimentech č. 7 a 8. Tyto konfigurace dosahují velké míry spokojenosti návštěvníků a relativně stejné nízké hodnoty predikce doplňování zboží do stánků. Určitě by, z hlediska úspory nákladů na provoz, byl upřednostněn experiment č. 7, který má o jeden zásobovací vozík méně než experiment č. 8. Ale upřesnění priorit je na provozovatelích výstaviště. První čtyři experimenty byly pro porovnání provedeny bez čekací doby na naložení zásob. Graf 5 porovnává výsledky experimentů, kde přerušovanou čarou jsou experimenty, kdy zásobovací vozík ihned odjížděl naložený skladovými zásobami. V případě plné čáry trvalo naložení polovinu času z celkového počtu naložených zásob (100 ks nakládaných zásob zabere 50 jednotek času). Lze tedy zhodnotit, že zásobovací doba ovlivní výsledek simulace pouze v malé míře. Naopak doba, kterou potřebuje vozík k dojetí na zásobovací místo a predikce nedostatku zásob stánku, ovlivňují výsledek mnohem více (viz. experiment č. 4). Všechny ostatní grafy jsou pro úplnost přiložené v příloze a jsou označeny číslem experimentu a popiskem, ke které případové studii patří. Jako nativní řešení obslužného systému se v tomto modelu použila vyvinutá nadstavba, která umožnila implicitní omezení nakupujících agentů u stánku. Lokální obslužný proces je tímto způsobem dobře zapouzdřen a jeho další rozšíření nebo úprava jsou otázkou několika minut. Agentově orientovaný přístup přináší obrovské výhody v rychlé rekonfiguraci modelu, jelikož jeho jednotlivé části (i lokální obslužné systémy) jsou navzájem dobře oddělené a zapouzdřené v nějakém logickém celku. Model výstaviště lze dále rozvíjet a rekonfigurovat tak, aby modeloval skutečný systém nějakého výstaviště nebo letištní haly. Lze ho tedy po rozšíření uplatnit např. jako pomůcku pro rozhodování. Námětem pro rozšíření by mohla být úplná implementace chování chodce. Obecně se chodec vyskytuje ve všech modelech a přínos realistického chování přináší velké výhody při odhadování, jak se bude systém chovat. Samozřejmě pouze tam, kde chodci tvoří nezanedbatelnou část modelu.
67
8 Závěr Všechny cíle diplomové práce byly splněny. V první teoretické části práce je zpracován přehled agentově orientovaného modelování a simulace. Dále je pak zhotoven přehled simulační platformy Repast Simphony 2. V praktické části byl proveden návrh mechanizmu pro snadnou implementaci obslužných systémů v prostředí agentově orientovaných simulací. Mechanizmus, je ve své podstatě, obecný náhled jak problém řešit a lze ho tedy použít i v jiných agentově orientovaných modelovacích platformách. Implementace mechanizmu je v této práci provedena přímo pro simulační framework Repast Simphony 2. Nadstavba tak volně rozšiřuje základní funkcionalitu platformy. Usnadňuje a urychluje výstavbu servisně orientovaných simulačních modelů. Třetí experimentální část, pomocí vhodně zvolených případových studií, ověřuje a testuje, jak práci s platformou Repast Simphony, tak i implementaci vyvinuté nadstavby. První případovou studií byla ověřena funkčnost frameworku na standardním modelu M/M/1 (jednoduchý systém hromadné obsluhy, pro který existuje jednoduché analytické řešení). V druhé případové studii bylo ověřeno použití nadstavby. Nadstavba výrazně usnadnila a urychlila výstavbu obslužného systému a hlavně umožnila jeho jednoduchou následnou rekonfiguraci. Na třetí případové studii byl ověřen typický agentově orientovaný přístup (využití nativních možností frameworku) v kombinaci s lokálními obslužnými systémy. Kvůli problémům s realizací chování chodců, v třetí případové studii, byl navíc zhotoven algoritmus pro vytvoření gradientních map, které usnadňují nalezení optimálních cest v prostorovém prostředí modelu. Velkou výhodou gradientních map je jejich statický charakter. Není tedy nutné, aby mobilní entity v modelu byly stále zatěžovány výpočtem optimální cesty, tím bylo dosaženo ušetření výpočetního času. Obecně lze říci, že agentově orientovaný přístup umožnil modely vybudovat komponentním způsobem. Taková struktura modelu je velice užitečná při provádění změn a úprav, které jsou v simulačních modelech velice časté a z pohledu zkoumání většího počtu možných případů zkoumání podstatné. Modely vytvořené v této práci je samozřejmě možné dále rozšiřovat a použít je pro další výzkum, anebo praxi. Tato práce, za pomoci vedoucího práce, se stala součástí výzkumné činnosti fakulty informatiky a elektrotechniky na Univerzitě v Pardubicích.
68
9 Literatura [1]
[2] [3] [4]
[5] [6]
[7] [8]
[9]
[10]
[11] [12] [13]
[14]
[15]
ARUNACHALAM, S., R. ZALILA-WENKSTERN a R. STEINER. Environment mediated Multi Agent Simulation Tools: A Comparison. In: [online]. The University of Texas at Dallas, 2008 [cit. 2012-06-26]. Dostupné z: http://distrinet.cs.kuleuven.be/events/ecosoa/2008/contents/papers/arunachalam.pdf BANKS, J. Handbook of simulation. New York: John Wiley & Sons, 1998. 850 s. ISBN 0-471-13403-1. BLOCH, Joshua. Java efektivně: 57 rad softwarového experta. Grada Publishing, 2002, s. 10. ISBN 80-247-0416-1. COLLIER, N.T., NORTH M.J., "Repast SC++: A Platform for Large-scale Agentbased Modeling," in W. Dubitzky, K. Kurowski, and B. Schott, eds., Large-Scale Computing Techniques for Complex System Simulations, Wiley (In Press 2011). FOSTER, Ian. Message Passing Interface. [online]. 1995 [cit. 2012-06-26]. Dostupné z: http://www.mcs.anl.gov/~itf/dbpp/text/node94.html FRIEBELOVÁ, J., J. KLICNAROVÁ a L. FRIEBEL. Teorie hromadné obsluhy. In: [online]. Jihočeská univerzita v Českých Budějovicích, 2006 [cit. 2012-06-26]. Dostupné z: http://www2.ef.jcu.cz/~jfrieb/rmp/data/teorie_oa/OBSLUHA.pdf GALOTTI, K. Cognitive Psychology: In and out of the laboratory. USA: Wadsworth, 2008. GRIMMA Volker, BERGER Uta, GRIMM Finn Bastiansen. A standard protocol for describing individual-based and agent-based models. In: [online]. 2006 [cit. 2012-06-26]. Dostupné z: http://www.bio.uib.no/inc/pdffiles/Pub/pub3126.pdf HONZÁK, Roman. Experimentování s čekacími dobami vlaků v osobních železničních stanicích v rámci simulačního modelu. Pardubice, 2010. 60 s. Univerzita Pardubice, Fakulta Elektrotechniky a Informatiky. Vedoucí diplomové práce Ing. Michael Bažant. JENSEN, Finn Rosenbech. Using the travellingsalesman problem in bioinformatic algorithms. [online]. AARHUS UNIVERSITY, 2010 [cit. 2012-06-26]. Dostupné z: http://www.daimi.au.dk/~cstorm/students/RosenbechJensen_Dec2010.pdf KAVIČKA, Antonín. Pokročilé techniky modelování a simulace. [elektronické sylaby k předmětu] Pardubice : Univerzita Pardubice, 2009. KAVIČKA, Antonín. Modelování a simulace. [elektronické sylaby k předmětu] Pardubice : Univerzita Pardubice, 2011. KAVIČKA, Antonín. Aplikace paradigmatu autonomních agentů na architekturu simulačního modelu. In: [online]. Univerzita Pardubice, 2001 [cit. 2012-06-26]. Dostupné z: http://dspace.upce.cz/bitstream/10195/32107/1/CL273.pdf KAVIČKA, A., KLIMA, V., ADAMKO, N. Agentovo orientovaná simulacia dopravních uzlov. Žilina: EDIS - vydavatelstvo ŽU, 2005. 206 s. Monografie. ISBN 80-8070-477-5. KORMANOVÁ, Anna. Metódy simulácie správania sa chodcov. Žilina, 2012. Písemná práce k dizertační zkoušce. Žilinská Univerzita, Fakulta Riadenia a Informatiky. Vedoucí práce Doc. Mgr. Valent Klima, CSc.
69
[16]
[17] [18]
[19]
[20]
[21]
[22]
KUBÍK, Aleš. Agentově-orientované inženýrství: nové paradigma pro tvorbu softwaru?. In: [online]. Ústav informatiky, Slezská univerzita, 2007 [cit. 2012-0626]. Dostupné z: http://multiagent.tym.cz/clanky/MAS%207%20CZ.pdf KŘIVÝ, Ivan, KINDLER, Evžen. Simulace a modelování. Ostrava : Ostravská univerzita, 2001. 146 s. Logo (programovací jazyk). In: Wikipedia: the free encyclopedia [online]. 2006, 30.12.2011 [cit. 2012-06-26]. Dostupné z: http://cs.wikipedia.org/wiki/Logo_(programovací_jazyk) MACAL, Charles M., NORTH Michael J. TOWARD TEACHING AGENT-BASED SIMULATION. In: [online]. Argonne National Laboratory. Argonne, USA, 2010 [cit. 2012-06-26]. Dostupné z: http://repast.sourceforge.net/docs/TowardTeachingABS.pdf MACAL, Charles M., NORTH Michael J. Tutorial on agent-based modelling and simulation. In: [online]. Journal of Simulation. The University of Chicago, 2010 [cit. 2012-06-26]. Dostupné z: http://www.palgravejournals.com/jos/journal/v4/n3/pdf/jos20103a.pdf NETRVALOVÁ, A. Úvod do problematiky multiagentních systémů. In: [online]. ZČU v Plzni, FAV, KIV, 2005 [cit. 2012-06-26]. Dostupné z: http://www.kiv.zcu.cz/~netrvalo/phd/MAS.pdf NORTH, M.J., TATARA E., COLLIER N.T., OZIK J., "Visual Agent-based Model Development with Repast Simphony," In: [online]. Proceedings of the Agent, 2007 Conference on Complex Interaction and Social Emergence, Argonne National Laboratory, Argonne, IL USA [cit. 2012-06-26]. Dostupné z: http://www.dis.anl.gov/publications/articles/North_et_al_Repast_Simphony_Tutorial.pdf
[23]
[24] [25] [26]
NORTH, M.J., HOWE T.R., COLLIER N.T., VOS J.R., "A Declarative Model Assembly Infrastructure for Verification and Validation," in S. Takahashi, D.L. Sallach and J. Rouchier, eds., Advancing Social Simulation: The First World Congress, Springer, Heidelberg, FRG (2007). PELÁNEK, Radek. Modelování založené na agentech (ABM). [online]. [cit. 201206-04]. Dostupné z: http://www.fi.muni.cz/~xpelanek/IV109/slidy/abm.pdf Repast Homepage [online]. 2011 [cit. 2011-10-07]. Dostupné z: http://repast.sourceforge.net/ Státnicové otázky z předmětu ITEI - Informační management [online]. FIM UHK, 2009 [cit. 2012-06-26]. Dostupné z: http://im2-fimuhk.wikispaces.com/file/view/ITEI_14_Multiagentov%C3%A9+syst%C3%A9my.doc
[27]
[28]
ŠIROKÝ, Jaromír: Aplikace počítačů v provozu vozidel. Ostrava: VŠB – TU Ostrava. 2005. s. 128. ISBN 80-248-0768-8 [skriptum]. [cit. 2012-06-26]. Dostupný z: http://homen.vsb.cz/~s1i95/MaSvD/SHO_1.pdf VARGA, Michal. Modelovanie získavania informácií a ich využitie pri inteligentnom rozhodovani v agentovo orientovaných simulačných modeloch. Žilina, 2012. Písemná práce k dizertační zkoušce. Žilinská Univerzita, Fakulta Riadenia a Informatiky. Vedoucí práce prof. Ing. Karol Matiaško, PhD.
70
10 Přílohy Příloha A
Obrázek A.1 – UML diagram vnitřní implementace aktivit a jejich rozhraní
71
Obrázek A.2 – UML diagram rozhraní aktivit a technologického plánu
72
Příloha B
Obrázek B.1 –Technologické postupy v modelu pneuservisu. zdroj: [11]
73
Obrázek B.2 – technologické procesy v modelu pneuservisu. zdroj: [11]
74
Obrázek B.3 – technologické procesy v modelu pneuservisu. zdroj: [11]
75
Příloha C
Obrázek C.1 – Topologie výstaviště
76
Obrázek C.2 – Gradientní mapa test testovacího prostředí (modrá – infrastruktura, – černá minimum, světle zelená – maximum)
77
Obrázek C.3 – Gradientní mapa stánku (v v pravém dolním rohu) rohu
78
Příloha D – Obsah přiložených souborů K práci je přiloženo CD, jež obsahuje elektronickou verzi této práce ve formátech PDF a DOC a následující adresáře:
79
Příloha E Pneuservis Scénář 1
Obrázek E.1 – Experiment S1 / č. 2
80
Obrázek E.2 – Experiment S1 / č. 4
81
Scénář 2
Obrázek E.3 – Experiment S2 / č. 1
82
Obrázek E.4 – Experiment S2 / č. 2
83
Výstaviště Scénář 1
Obrázek E.5 – Experiment S1 / č. 3
84
Obrázek E.6 – Experiment S1 / č. 4
85
Obrázek E.7 – Experiment S1 / č. 6
86
Scénář 2
Obrázek E.8 – Experiment S2 / č. 5
87
Obrázek E.9 – Experiment S2 / č. 7
88
Obrázek E.10 – Experiment S2 / č. 9
89
Obrázek E.11 – Experiment S2 / č. 10
90
