Simulace mraveniště pomocí DEVS formalismu

VYSOKÁ ŠKOLA POLYTECHNICKÁ JIHLAVA Katedra elektrotechniky a informatiky

Simulace mraveniště pomocí DEVS formalismu bakalářská práce

Autor: Michal Kovář. Vedoucí práce: Ing. Tomáš Richta.

Jihlava 2010

Anotace Moje bakalářská práce se zabývá simulací mraveniště pomocí DEVS formalismu. Simulace je implementována v jazyce Smalltalk, konkrétně v dialektu Squeak. Pro implementaci DEVS formalismu byla zvolena knihovna SmallDEVS vyvinutá na VUT Brno. Simulace se zabývá generováním mravenců, jejich zapojením do společenstva (mraveniště) a jejich úkolováním. Toto je prováděno společným vědomím mraveniště. Vzhledem k vlastnostem prostředí Squeak je možné simulaci spustit na většině platforem. Samotnou simulaci je rovněž možné snadno rozšířit.

Klíčová slova SmallDEVS, DEVS formalismus, Squeak

Abstract This bachelor thesis deals with the DEVS formalized simulation of an anthill. The prototype of the simulation is implemented using the Squeak - Smalltalk development environment. The implementation uses the SmallDEVS library, developed at the Brno University of Technology. The simulation describes the ant’s production, its integration into the structures of the anthill, and also solves the problem of the ants working plan. This is done by the common anthill consciousness. Squeak development environment enabled the simulation to run on almost all platforms. The simulation is also easily extendable.

Keywords SmallDEVS, DEVS formalism, Squeak

Poděkování Rád bych poděkoval vedoucímu bakalářské práce Ing. Tomáš Richtovi za poskytnutí tématu a možnosti vytvářet ho pod jeho vedením.

Prohlášení Prohlašuji, že předložená bakalářská práce je původní a zpracoval jsem ji samostatně. Prohlašuji, že citace použitých pramenů je úplná, že jsem v práci neporušil autorská práva (ve smyslu zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů, v platném znění, dále též „AZ“). Souhlasím s umístěním bakalářské práce v knihovně VŠPJ a s jejím užitím k výuce nebo k vlastní vnitřní potřebě VŠPJ . Byl jsem seznámen s tím, že na mou bakalářskou práci se plně vztahuje AZ, zejména §60 (školní dílo). Beru na vědomí, že VŠPJ má právo na uzavření licenční smlouvy o užití mé bakalářské práce a prohlašuji, že s o u h l a s í m s případným užitím mé bakalářské práce (prodej, zapůjčení apod.). Jsem si vědom toho, že užít své bakalářské práce či poskytnout licenci k jejímu využití mohu jen se souhlasem VŠPJ, která má právo ode mne požadovat přiměřený příspěvek na úhradu nákladů, vynaložených vysokou školou na vytvoření díla (až do jejich skutečné výše), z výdělku dosaženého v souvislosti s užitím díla či poskytnutím licence. V Jihlavě dne 10. 1. 2011 ...................................................... Podpis

Obsah

Anotace ............................................................................................................................. 3 Klíčová slova .................................................................................................................... 3 Abstract ............................................................................................................................. 3 Keywords .......................................................................................................................... 3 Poděkování........................................................................................................................ 4 Prohlášení.......................................................................................................................... 5 Obsah ................................................................................................................................ 6 1. Úvod a cíl práce ........................................................................................................ 7 2. Teoretický popis řešeného problému ........................................................................ 8 2.1 Simulační techniky ............................................................................................. 8 2.1.1 HLA (High-Level Architecture) ................................................................. 8 2.1.2 DEVS/HLA ................................................................................................. 9 2.1.3 Swarm (Roj) ................................................................................................ 9 2.1.4 MASON .................................................................................................... 10 2.1.5 JAMES ...................................................................................................... 12 2.2 Popis formalismu DEVS .................................................................................. 12 2.2.1 Atomic DEVS ............................................................................................... 12 2.2.2 Coupled DEVS ............................................................................................. 13 2.3 Obecné fungování mraveniště .......................................................................... 15 3. Analýza řešeného problému.................................................................................... 19 3.1 Identifikace entit a vztahů ................................................................................ 19 4. Použité technologie ................................................................................................. 21 4.1 Popis knihovny SmallDEVS ............................................................................ 21 4.2 Popis prostředí Squeak ..................................................................................... 22 5. Datová struktura aplikace ....................................................................................... 26 5.1 Obecný datový model SmallDEVS .................................................................. 26 5.2 Model mraveniště jako popis entit ................................................................... 30 6. Popis implementace ................................................................................................ 36 6.1 Simulační engine .............................................................................................. 36 6.2 Simulační scénáře............................................................................................. 37 7. Závěr ....................................................................................................................... 39 Literatura ......................................................................................................................... 41 Seznamy .......................................................................................................................... 42 Seznam obrázků .......................................................................................................... 42 Seznam zkratek ........................................................................................................... 42 Přílohy............................................................................................................................. 43

1. Úvod a cíl práce Jako téma bakalářské práce jsem si vybral zadání s názvem „Simulace mraveniště“ od Ing. Tomáše Richty. Důvod výběru byl poměrně prostý, většina zadání bakalářských prací se zabývala vývojem webových aplikací, což mne v té době nijak neoslovilo. Poprvé jsem se s problematikou simulací setkal v jazyce Java, kde jsem se pokoušel částečně nasimulovat chod mraveniště, s využitím poznatků o formalismu DEVS (Discrete Event System Specification). To se ovšem ukázalo jako neefektivní z důvodů absence vhodných nástrojů a tudíž velkých nároků na implementaci. V té době jsem rovněž sledoval cyklus dokumentárních seriálů o sledování chování zvířecích druhů a posléze implementací částí jejich chování v lidských technologiích což můj zájem o toto zadání ještě více posílilo. Cílem samotné práce je posoudit možnosti využití výše zmíněného formalismu při návrhu simulace živého organismu, případně jeho společenství. Dále bylo třeba rozhodnout o platformě, na které bude samotná simulace implementována. Nakonec, po domluvě s vedoucím práce bylo rozhodnuto o implementaci v jazyce Smalltalk a to s využitím prostředí Squeak. Důvod tohoto rozhodnutí spočíval především v tom, že pro toto prostředí je k dispozici volně dostupná knihovna SmallDEVS, která byla vyvinuta na VUT Brno, a jejímž cílem je právě implementace formalismu DEVS. Dalším důvodem pro výběr právě tohoto prostředí je jednak přehlednost a jednoduchost jazyka Smalltalk a jednak samotné prostředí Squeak, které může svými možnostmi směle konkurovat profesionálním IDE prostředím, které mu ovšem nemohou konkurovat svojí cenou, jelikož Squeak je vyvíjen jako svobodný open source software. Díky využití knihovny SmallDEVS (nutno podotknout, že podobných knihoven je více a pro různé programovací jazyky) mám možnost se zaměřit pouze na chování samotných entit a nemusím řešit přechody mezi jednotlivými stavy chování, jelikož to obstará právě zmíněná knihovna. Práce samozřejmě nebude simulovat mraveniště jako komplexní celek, což je prakticky nerealizovatelné, nýbrž se bude snažit simulovat výběrovou skupinu spolu souvisejících modelů chování. Na akademické půdě může být 7

práce dále využita například pro seznámení studentů s formalismem DEVS a jeho možnostmi.

2. Teoretický popis řešeného problému 2.1 Simulační techniky Zde jsou uvedeny stručné popisy jiných simulačních systémů, architektur. Popis formalismu DEVS je podrobněji popsán ve zvláštní kapitole.

2.1.1 HLA (High-Level Architecture) Jedná se o univerzální architekturu určenou pro simulaci distribuovaných systémů. Byla navržena pro US Department of Defence a slouží jako standard pro spolupráci vojenských simulačních systémů USA, později se stala i standardem NATO.[1] Základní terminologie HLA: Federate – jedná se o simulaci kompatibilní s HLA specifikaci, Federation – jedná se o více subjektů, simulací, komunikujících spolu skrze standardizované běhové rozhraní (RTI – Run Time Infrastrukture) společně s objektovým modelem šablon (OMT – Object Model Template), který určuje, jaké informace se mezi simulacemi předávají, Object – kolekce dat, které si simulace navzájem zasílají, Attribute – datová položka objektu, Interaction – události zasílané mezi entitami simulace, Parameter – datová položka interakce[2]. HLA kombinuje existující systémy místo toho, aby nějaký vytvářela. Přestože se jedná o architekturu vytvořenou pro armádní sektor, začíná se využívat i v civilní sféře, např. v odvětví průmyslu a přepravy[1].

8

2.1.2 DEVS/HLA Jedná se o simulační prostředí vyhovující specifikacím HLA založeném na DEVS formalismu. Na vývoji se podílel i autor DEVS formalismu Bernard Zeigler. Projekt vznikl jako součást projektu spadajícího pod instituci DARPA (agentura amerického ministerstva obrany, která je odpovědná za vývoj nových vojenských technologií. Tyto mají umožnit technologickou převahu nad jinými státy).[1] Formalismus DEVS je v tomto prostředí implementován v jazyce C++. Důvod výběru tohoto jazyka spočívá v tom, že se jedná o jazyk používaný pro první běhové rozhraní (RTI) vydané organizací DMSO (Defense Modeling Simulation Organization) implementované ve standardu HLA (High Level Architecture). DEVS C++ byl vyvinut na základě formalismu DEVS a poskytuje dvě hlavní třídy, na základně kterých může uživatel vytvořit modely. Těmito třídami je atomic class a coupled class, které představují atomic DEVS a coupled DEVS. Spojení s HLA spočívá v implementaci federate (viz. HLA) za pomoci atomic, coupled class.[3]

Obrázek 1 Architektura DEVS/HLA

2.1.3 Swarm (Roj) Jedná se o simulační, multi-agentní, balíček programů. Je určen pro modelování, simulování biologických systémů (např. migrace ptactva). Jako taková, je simulace 9

založena na vzájemném ovlivňování jednotlivých entit simulace, resp. ovlivňování jednotlivých agentů.[1] Původně byl vyvinut v Santa Fe institutu. Je licencován pod GNU licencí, hlavními jazyky využívanými v balíčcích jsou Objektive-C a Java, díky tomu je možno balíčky Swarm využívat v prostředí Linux, Windows, Macintosh. Při vývoji je možnost využití rovněž uživatelské podpory[4]. Využití tohoto balíčku je tedy zřejmé, simulace živých organismů. Nicméně není omezena jen na ně, jak se na oficiálních stránkách můžeme dočíst, jeden ze dvou nejvýznamnějších projektů během posledních dvou let spočívá v simulaci šíření ohně. Povzbudivě působí skutečnost, že komunita je aktivní a na oficiálních stránkách lze dohledat veškerou potřebnou dokumentaci. V porovnání s ostatními uvedenými simulačními technikami mi osobně přijde Swarm nejpřívětivější vzhledem k tomu, že působí oproti ostatním „nejotevřeněji“ ve smyslu poskytování informací o co se vlastně jedná a jak to využít[4].

2.1.4 MASON Tento projekt vznikl na univerzitě George Mason University (je to výsledek společného úsilí více společností, nikoliv samotné školy). Jedná se o simulační knihovnu napsanou v jazyce Java, inspirovanou výše zmíněnou sadou Swarm. Obsahuje rovněž volitelnou sadu doplňků v oblasti 2D a 3D.[5] Na oficiálních internetových stránkách projektu je k dispozici několik simulací ve formě java apletu k vyzkoušení. Knihovna poskytuje poměrně široké možnosti výstupu simulace, například ve formě tabulek, grafů, obrázků a filmů ve formátu Quick[5]. Knihovna se využívá v různých projektech, jak se na oficiálních stánkách můžeme dočíst. Mezi tyto projekty patří například simulace městské dopravy, simulace finančních trhů, simulace šíření antraxu v lidském těle[5]. Na další stránce je zobrazeno několik obrázků ze simulace mravenců hledajících potravu. Oválné objekty představují překážky, osamocený bod vlevo je zdroj potravy, body vpravo představují mravence, světle šedá plocha (obr.3) značí oblast 10

prozkoumanou mravenci a tmavou šedou (obr.4) je znázorněna trasa od potravy k mraveništi, představující stopu z feromonů, kterou mravenec po objevení potravy vylučuje během návratu do mraveniště[5].

Obrázek 2 Stav simulace chvíli po spuštění

Obrázek 3 Stav simulace po nalezení potravy

Obrázek 4 Vytváření feromonové stopy

11

2.1.5 JAMES Jedná se o modelovací prostředí založené na paralelní verzi formalismu DEVS napsaném v jazyce Java. Prostředí je vyvíjeno na univerzitě v Ulmu[13]. Simulace je založena na agentech, ti jsou implementování jako atomické DEVS komponenty. Vzhledem ke spolupráci s agenturou NASA se neuvažuje o zveřejnění zdrojových kódů či dokumentace.[1]

2.2 Popis formalismu DEVS V diskrétním modelu je stav určen stavovými veličinami. Během simulace v daném časovém intervalu existuje konečně mnoho bodů (okamžiků), ve kterých dochází ke změně stavových veličin, tyto změny můžeme nazvat události. Samotný průběh změny má nulovou dobu trvání, to znamená, že změna je okamžitá. Tato skoková změna představuje hlavní odlišnost od spojitých systémů, u nichž dochází ke změně stavové veličiny postupně. Formalismus DEVS (Discrete Event System Specification) formuloval Dr. Bernard P. Zeigler a byl veřejnosti prezentován v knize Teorie modelování a simulace v roce 1976. Jedná se o formalismus určený k modelování a simulování diskrétních systémů. Základními entitami DEVS formalismu jsou AtomicDEVS a CoupledDEVS [1].

2.2.1 Atomic DEVS Atomický DEVS je definován jako n – tice kde: X je množina vstupních portů, Y je množina výstupních portů, S je množina vnitřních stavů, je časová funkce určující délku trvání stavu, je vnější přechodová funkce určující chování entity na vnější podnět, kdy představuje množinu všech stavů a t je uplynulý čas od poslední změny, je vnitřní přechodová funkce, definující jak se mění stav systému interně, představuje výstupní funkce, která zajišťuje mapování stavu stavů entity na výstupní porty[6]. 12

Atomický DEVS slouží k implementování základního chování dané simulace, které je již dále nedělitelné. Může mít libovolný počet vstupních a výstupních portů. Při spojování více atomických entit může výstupní port jedné entity sloužit jako vstupní port druhé entity. Stavy mohou být ovlivněny pouze vnitřní či vnější přechodovou funkcí. Délka trvání jednotlivých stavů systému je určena časovou funkcí ta. Tak jako v reálném světě je tok času pouze kladný, může být i velikost ta pouze kladná, v intervalu hodnota

, kdy velikost 0 znamená skokovou změnu stavu, zatímco může značit například to, že entita se v daném stavu bude nacházet tak

dlouho, dokud tento stav nebude změněn vnější přechodovou funkcí. Atomická komponenta tvoří základní prvek spojované komponenty neboli Coupled DEVS.

2.2.2 Coupled DEVS Spojovaný DEVS představuje síť DEVS komponent, která se navenek může prezentovat jako jediná entita s danými vstupy a výstupy. Formálně se spojovaná komponenta definuje jako n – tice kde: X je množina vstupních portů, Y je množina výstupních portů, D je množina unikátních jmen na komponenty modelu, Mi je množina sub-komponent, ty mohou jak atomické, tak spojované, Ii je množina odkazů na komponenty, jež jsou ovlivňovány komponentou , Zi,j je mapovací funkce, která má za úkol správně transformovat výstup jedné komponenty na vstup druhé komponenty, select představuje výběrovou funkci používanou pro řešení případných kolizí, řešení v podstatě spočívá ve výběru komponenty pro přednostní zpracování.[1] Zatímco v případě atomických komponent, kdy určujeme základní, nedělitelné chování simulace, u spojovaných komponent pracujeme se samotnými komponentami, při čemž určujeme jejich vzájemnou kooperaci pomocí propojení vstupních a výstupních portů, čímž vytvoříme síť. Z tohoto pohledu můžeme říci, že atomické komponenty plní roli simulační, zatímco spojované komponenty hrají roli koordinační.

13

Pomocí výše uvedených poznatků bych se nyní pokusil nastínit průběh implementace DEVS formalismu na příkladu hry ping-pong pro dva hráče. Za prvé si nastíníme trochu lépe výchozí situaci, máme hráče player_A a player_B. Předpokládejme, že hru začíná hráč player_A tím že odpálí míček druhému hráči. Tento akt můžeme chápat jako výstupní událost odpal. Poté player_A čeká, dokud se k němu míček nevrátí zpět po odpalu protivníkem, player_B. V tomto případě se bude jednat o vstupní událost, kterou můžeme nazvat příjem. Oba hráči tedy představují atomickou DEVS komponentu se vstupním portem příjem a výstupním portem odpal, přičemž po každém odpálení míčku musí jeden hráč čekat na hráče druhého, lépe řečeno na jeho odpal. Což znamená, že čekající hráč bude mít časovou funkci ta nastavenu na nekonečno, přičemž změna stavu nastane až jako reakce na příjem od druhého hráče. Aby mohli hráči navzájem reagovat, musíme napojit jejich porty, v tuto chvíli již v podstatě vytváříme spojovanou DEVS komponentu, která bude obsahovat atomické komponenty a to player_A a player_B. Nyní provedeme formalizaci jednotlivých entit simulace. Jako první formalizujeme hráče reprezentující atomickou komponentu. Jak je výše uvedeno, atomickou komponentu lze zapsat jako n – tici: , ta v našem případě obsahuje:

Máme tedy vstupní port příjem a výstupní port odpal, dále jsme definovali dva stavy a to stav čekej a stav hraj. Definice ta nám říká, že pokud se hráč nachází ve stavu čekej tak se v něm nalézá nekonečně dlouho, to znamená po tak dlouhou dobu, dokud nebude tento stav změněn vnějším podnětem. Pokud se hráč nachází ve stavu hraj tak v něm 14

přetrvá po dobu 0.1j. Externí funkce nám popisuje chování z hlediska vnějších událostí. Naproti tomu vnitřní funkce popisuje autonomní přechody uvnitř entity. Výstupní funkce nám říká, že pokud se nacházíme ve stavu hraj pak na výstup odpal pošleme hodnotu #odpal. Ve stavu čekej se na výstupní port nic nezasílá. Jak již bylo zmíněno, atomický DEVS nám plní roli simulační, abychom tedy mohli simulaci oživit, musíme náležitě propojit porty, tím dostáváme spojovaný DEVS, který hraje roli především koordinátora. Spojovaný DEVS definuje n – tice

, ta v našem

případě obsahuje:

Samotný spojovaný DEVS nemá v našem případě žádné vstupní, či výstupní porty, obě množiny, tj. X, Y jsou tedy prázdné. Množina D obsahuje unikátní názvy vnitřních komponent, v našem případě to jsou player_A, player_B. Množina Mi je zde stejná jako množina D. Ii nám říká, že player_A ovlivňuje chování player_B a naopak. Množina Zij definuje způsob, jakým jsou propojeny vstupy a výstupy vnitřních komponent. Vzhledem k jednoduchosti příkladu zde nenastávají kolize a tudíž množina select je prázdná.

2.3 Obecné fungování mraveniště Mraveniště je uměle vybudovaná stavba sloužící jako domov pro kolonii mravenců. Jeho tvar a vlastnosti do jisté míry závisí na druhu mravence, který jej vybudoval. Lesní mravenci budují zpravidla typické kupy z nahromaděného jehličí a drobných klacíků. Jiné druhy mravenců upřednostňují spíše podzemní mraveniště, nebo například 15

v dutinách stromů. Skládá se z chodbiček, zásobáren potravy, komůrek sloužící jako líheň nových mravenců a komůrky s královnou.[7,8] Mravenci jsou drobný, šestinohý hmyz, jejich tělo tvoří hlava, hruď a zadeček. Jedná se o společenský hmyz žijící v kolonii. Velikost kolonie závisí na konkrétním druhu mravence, může mít i několik tisíc členů, přičemž jsou známy i případy super kolonií čítající miliony spolupracujících jedincům. Příkladem mohou být mravenčí kolonie v deštných pralesech, které nemají mraveniště, nýbrž neustále putují, kolonie se přitom táhne v délce několika kilometrů.[8,9] Mravenci se vyskytují téměř na celé planetě, potřebují vysokou vlhkost vzduchu a nejvíce jím vyhovuje teplé, vlhké prostředí. Nicméně existuje i mravenec pouštní, jenž je schopen přežít teploty až 55°C u kterého je i zajímavá orientace v prostředí, které mu prakticky neskýtá žádné orientační body. Mravenec využívá systém vnitřního krokoměru, pomocí kterého zachycuje změny rychlosti a směru a díky tomu je schopen určit svoji polohu[8,10]. Kolonii zakládá mravenčí královna, po opuštění domovského hnízda je během letu oplodněna samečky, ti po několika dnech uhynou, zatímco genetický materiál předaný královně ji vydrží po celý život. Ta si poté najde vhodné místo, kde postaví základ mraveniště a vychová první generaci dělnic. Jedná se o nejnebezpečnější období života mraveniště. O pohlaví potomků rozhoduje královna, z oplodněného vajíčka se rodí dělnice, z neoplodněného sameček. Královna zároveň pomocí speciálního sekretu zabraňuje zrození dalších královen, pokud chce nové královny zplodit, přestane sekret vylučovat. Dělnice zpravidla nerodí, nicméně u některých druhů jsou toho schopny v případě, kdy zahyne královna a kolonii tak hrozí postupný zánik. Velké dělnice s vyvinutými kusadly se nazývají vojáky. Jednotlivé kasty mravence, tj. královna, dělnice, vojáci a samečci, se mohou vzájemně lišit velikostí i tvarem těla. Délka života mravence záleží samozřejmě na druhu, například mravenec lesní se dožívá až 10 let. Mravenčí královny některých druhů se mohou dožívat i více jak dvaceti let, a během svého života zplodit až 150 milionů potomků.[8] Komunikace mezi mravenci je založena na feromonech, dále mohou užívat ke komunikaci např. chuťové smysly (dají ostatním ochutnat, co mají), stridulace (jedná se 16

o vyluzování zvuků třením pevných částí těla o sebe), zrak příliš nevyužívají. Vzhledem k tomu, že základem jsou feromony, obývá mraveniště i celá řada parazitů, která je schopna tyto pachy vytvářet, mohou to být i mravenci jiného druhu. Mravenci jsou schopni vytvářet i vztahy založené na symbióze, kdy chrání stromy, keře či například mšice.[8] Vzhledem ke skvělé kooperaci mravenců a faktu, že zde převládá „vůle kolonie“ nad jednotlivými individualitami, se mravenci spíše podobají buňkám, než samostatnému organismu, z

tohoto důvodu se pak mravenčí kolonie označuje pojmem

„superorganismus“. Tuto hypotézu potvrzují i nové studie biologů.[8,11] Pokud chceme mluvit o inteligenci mravence, měli bychom spíše mluvit o kolektivním vědomí, obecně uznávanou definici, co to vlastně je, se mi nepodařilo nalézt. Nicméně bych zde uvedl názor filozofa Pierre Lévyho, který ji chápe jako „formu univerzálně distribuované inteligence, konstantně zdokonalované, koordinované v reálném čase a vyúsťující v efektivní využití schopností “ [12]

17

Obrázek 5 Složení těla mravence

Obrázek 6 Mravenci, vojáci

18

3. Analýza řešeného problému 3.1 Identifikace entit a vztahů Základ analýzy spočívá v identifikaci použitých objektů a dále v určení vazeb mezi nimi. Je celkem zřejmé, že zde existují dva základní hlavní typy entit, a sice entita mraveniště a entita mravence. Vzhledem ke skutečnosti, že mravenec, jak je výše popsáno, je spíše podoben buňce nežli

autonomnímu

hmyzu,

je

třeba

rozhodnout

o

způsobu,

jakým

bude

implementována inteligence. Inteligence v našem případě představuje mechanismus zodpovědný za činnost mravence. Nicméně, je rovněž nutné dořešit dalekosáhlost tohoto řízení. Tím je myšleno, zda inteligence pouze sdělí požadavek, nebo zároveň s vysláním požadavku bude nějakým způsobem dohlížet na způsob jeho plnění. Aby mohlo být rozhodnuto o tom, jak velkou roli bude inteligence hrát, je ovšem nejprve nutné určit, kde se bude nalézat. Jak již bylo zmíněno, mravenec je řízen kolektivním vědomím, novodobé výzkumy sice prokázaly výskyt určité míry individuality, která spočívala v zefektivňování činností jím prováděných, nicméně tento projev „osobnosti“ je v podstatě stále podřízen kolektivnímu vědomí. Je tedy zcela jasné, že inteligence ve smyslu řídícího mechanismu odpovědného za úkolování mravence nemůže být implementován v samotném mravenci. Nejpřirozenější vzhledem k realitě se tedy jeví implementace této inteligence v mraveništi. To tedy znamená, že mraveniště nereprezentuje naši běžnou představu obydlí kolonie, ale bylo v jistém slova smyslu povýšeno. V rámci simulaci tudíž pojmy jako mraveniště, kolektivní vědomí a kolonie spíše splývají, než aby byly striktně určeny. Máme tedy entitu mraveniště, která reprezentuje obydlí kolonie (myšleno jako neurčité množství mravenců), a dále obsahující mechanismus řízení mravenců. Nyní je nutno rozhodnout o tom, jak bude řízení realizováno, lépe řečeno, do jaké míry bude mraveniště rozhodovat o činnosti mravence.

19

Mraveniště jako kolektivní vědomí, by tedy mělo hrát hlavní roli ve způsobu určování činnosti mravence, díky čemuž může teoreticky řídit samo sebe tak, aby byla zajištěna maximální možná prosperita. Toto řízení může zajišťovat například dostatek materiálu, potravy či například možnost rozšíření mraveniště tak, aby bylo schopno dalšího navyšování počtu mravenců. Mraveniště by ovšem nemělo být „vševědoucí“ vůči mravencům, tato „vševědoucnost“ by totiž značně omezila možnosti případného rozšiřování simulace o další prvky, jelikož by vše bylo velmi silně provázáno. Proto se jako nejvhodnější jeví, aby mraveniště mělo možnost řídit rozdělení mravenců do jednotlivých činností a těmito je pak úkolovat. Úkolování by mělo spočívat pouze v zaslání správné zprávy mravencovi, který sám pak zařídí jeho plnění. Díky tomu je zachována pružná vazba mezi mravencem a mraveništěm. To pro nás mimo jiné znamená snadnou přístupnost simulace ve smyslu jejího vylepšování (např. o znaky jisté individuality mravence). Dále je třeba si upřesnit určení entity mravence. Jak je již výše naznačeno, tak tato entita by měla obsahovat znalosti činností, které po ní může mraveniště vyžadovat. Mezi tyto činnosti může patřit například sběr materiálu, obrana, atd. Mravenec tedy dostane od mraveniště úkol, ten se pokusí splnit a v případě úspěchu předat mraveništi výsledky své činnosti. Dále je nutno uvážit způsob, jakým bude činnost prováděna, zde mám především na mysli „nedělitelnost“ operace. Dejme tomu, že mraveniště vyšle mravence pro materiál. Je celkem zřejmé, že ne vždy mravenec něco přinese, a ne vždy tuto výpravu musí přežít. Bude tedy nutné tuto činnost, která se z hlediska mraveniště tváří jako elementární uvnitř samotného mravence implementovat tak, aby zde byla možnost formou vnějších podnětů změnit chování mravence. Tato změna chování tedy bude vyjadřovat v jistém slova smyslu přirozenou reakci na podnět. Jako základní entity máme tedy mravence a mraveniště. Přičemž mraveniště by mělo být odpovědné za úkolování mravenců takovým způsobem, aby zajistilo prosperitu kolonie, a samotný mravenec mu bude plně podřízen tak, že bude plnit jeho požadavky. V případě obdržení požadavku se jej pokusí vyplnit, nicméně během plnění může vykonávat i jinou činnost v závislosti na vnějších podnětech.

20

4. Použité technologie 4.1 Popis knihovny SmallDEVS Knihovna SmallDEVS vznikla na VUT Brno. Jedná se o software vyvinutý pro výzkum a vzdělání v rámci modelů a simulací pomocí DEVS formalismu. Knihovna je napsána v jazyce Smalltalk – konkrétně v dialektu Squeak, odtud taky pochází jméno knihovny. Knihovnu je možné stáhnout ve formě souborů samotné knihovny, která se poté instaluje v rámci prostředí Squeak. Další možnost je stáhnutí samotné Squeak image. Ta obsahuje jednak knihovnu a dále doporučené nástroje (ty samozřejmě nejsou pro správný běh knihovny nutné). [14] Základní třídy SmallDEVS knihovny jsou: MyRepository – jak již vyplývá z názvu, jedná se o úložiště a základní třídu používanou při tvorbě modelu, simulace. Zvláště pokud využíváme grafického rozhraní. Jedná se o hierarchicky uspořádané úložiště obsahující modely, simulace, traity a prototypy, AtomicDEVSPrototype – jedná se o předpřipravenou atomickou DEVS komponentu, pomocí které se namodeluje základní chování (možnosti) simulace, CoupledDEVSPrototype – tato třída slouží především k zapouzdřování komponent a jejich propojování do sítě, PrototypeObjectForSimulation – jedná se o třídu určenou pro pomocné objekty, AtomicDEVSTrait – tato třída rozšiřuje PrototypeObjectForSimulation třídu, DEVSRootSolverRT [14] Samotné vytváření modelu, resp. simulace se děje v rámci grafického rozhraní. Výhodou tohoto přístupu je přehlednost a usnadnění orientace v simulaci. Nicméně grafické rozhraní vykazuje i jisté nedostatky a to například možnosti ladění samotné simulace, kdy nelze provádět úpravy v kódu. Další nedostatky se ukazují při snaze deklarace metod, přepisování definic metod. Veškeré tyto chyby je možné poměrně 21

snadno vyřešit a tak spíše kazí dojem z knihovny, než že by se jednalo vyloženě o chyby, na základě kterých bychom se rozhodovali pro jiný nástroj.

4.2 Popis prostředí Squeak Squeak je volně šiřitelný open source dialekt jazyka Smalltalk. Jeho historie začíná koncem roku 1995, kdy vznikl z důvodu absence přenositelného, prakticky použitelného, programovacího

prostředí.

Při

tvorbě vývojové platformy její

programátoři vycházeli ze staré applovské implementace Smalltalk-80. Jejím základem byla objektová paměť, neboli image a oddělený virtuální stroj. Problémem tohoto virtuálního stroje bylo, že byl tvořen několika desítkami stran prakticky nekomentovaného assembleru a o nějaké přenositelnosti se tudíž nedalo uvažovat. Zde se ukázala první nutnost a to vytvořit nový, přenositelný virtuální stroj. Vzhledem ke složení vývojového týmu, ten tvořili lidé, jako například Dan Ingalls či Alan Kay, a vzhledem k jejich nechuti k odlaďování kódu v jazyce C, se rozhodli, že virtuální stroj napíší v samotném Smalltalku. Přesněji řečeno, v podstatě vzali jeho podmnožinu tvořenou 42 pravidly, a zároveň vytvořili překladač pro překlad této podmnožiny do jazyka C. Díky tomu, je část virtuálního stroje generována samotným prostředím Squeak. Squeak pro své spuštění vyžaduje virtuální stroj, image – jedná se o obraz objektové paměti Squeaku a konečně zdrojové kódy metod, ty jsou uloženy zvlášť ve dvou souborech sources a changes. Primárně se pro ukládání používá soubor sources, soubor changes slouží k ukládání změn – typicky pokud uložíme image Squeaku. Kupodivu v případě, kdy nemáte k dispozici soubor sources tak zjistíte, že prostředí sice vypíše varovnou hlášku, ale poté se bez problému spustí. Zajímavá situace nastane i ve chvíli, kdy v takto spuštěném prostředí, budete chtít prohlížet zdrojové kódy, které jsou uloženy v souboru, který nemáte k dispozici. Jednoduše se stane to, že prostředí provede dekompilaci, kterou vám ukáže. Nutno dodat, že se jedná o dekompilaci značně věrnou. Ukázku můžete vidět na další straně, v podobě print screenu System Browseru prostředí Squeak.

22

Obrázek 7 Print screen prostředí Squeak s přítomným souborem sources

Obrázek 8 Print screen prostředí Squeak bez souboru sources

23

Co se mých zkušeností s tímto prostředím týče, tak musím přiznat, že mne značně překvapilo. V první řadě mne značně překvapila velikost tohoto prostředí, která se pohybuje rámcově v desítkách megabajtů. Například velikost verze, ze které pocházejí výše uvedené print screeny zabírá necelých 40 MB (je zde zahrnuta image, soubory sources a changes i virtuální stroj). Vzhledem k velikostem řekněme běžných vývojových prostředí ať už komerčních, či open source, které se pohybují spíše ve stovkách megabajtů, jsem tedy logicky očekával snížené možnosti při práci s tímto prostředím. Ani samo spuštění image, kdy se objeví modré logo s něčím, co připomíná králičí obličej a posléze grafika, o které si v prvních chvílích asi většina pomyslí něco o špatném vtipu příliš šancí Squeaku nedávali. O to více překvapí možnosti, které toto prostředí nabízí při práci se zdrojovými kódy, či objekty. Po pár kliknutí myší, jste schopni se dostat k definici čehokoliv, co je v prostředí k dispozici. S čímž jsem se u ostatních prostředí nesetkal, ne, že by nebylo možno dohledat kódy objektů, ale rozhodně to nebylo tak jednoduché jako v tomto případě. V posledních letech se čím dál více mluví o „čistotě zdrojového kódu“. V tomto směru bych řekl, že Squeak ji udržuje, dalo by se říci, tak nějak sám od sebe. Můžete procházet libovolnou definici jakéhokoliv objektu a vždy narazíte na naprosto čitelný zdrojový kód, kde definice metody zabere zpravidla něco kolem pěti řádků. Jistě, není problém se snažit tohoto dosáhnout i v jiných jazycích a jiných prostředích. Většinou ovšem narazíme na problém, že samotné prostředí řekněme nepodporuje vaši snahu o zachování čistoty svými možnostmi. Další problém je v samotných jazycích, každou chvíli se objevují nové verze, přibude nová syntaxe, nové klíčové slovo. V tomto směru jednoduchosti Smalltalku asi nemůže konkurovat žádný jazyk. Smalltalk oplývá totiž jednoduchou, přehlednou syntaxí. Naopak neoplývá přemírou klíčových slov, a rozhodně se každý rok neobjevuje v nové verzi, a před tímto součtem jeho, řekl bych kladných, vlastností nemůže asi obstát žádný novodobý programovací jazyk. Dále mne velice překvapily možnosti při práci s „živým“ kódem v rámci ladění. Pracoval jsem s tímto režimem nejčastěji v prostředí Eclipse v rámci jazyku Java a prostředí Microsoft Visual Studio v rámci jazyka C. Obě prostředí považuji za vynikající a za vynikající jsem považoval i možnosti ladění. Považoval, jelikož možnosti Squeaku v tomto směru jsou neuvěřitelné, zvláště pak možnost během 24

provádění kódu tam paralelně provádět změny, žádné jiné prostředí mi doposud nic takového nenabídlo. Nicméně každá mince má dvě strany, a ani Squeak podle mne není výjimkou. Velký klad tohoto prostředí je možnost jej upravovat, ať už úpravami v něm samotném, či doinstalováním balíčků. Například zvýrazňování zdrojového kódu, jeho doplňování v rámci nápovědy není nutně samozřejmostí. Záleží na image, kterou máte, nicméně i když jsem si stáhnul poslední verzi přímo z oficiálních stránek, tak v tomto směru příliš nenabízela. A to je podle mne, zvláště pro člověka, který se s Squeakem seznamuje problém. Navíc to, že doinstalujete případný balíček, ještě neznamená, že vše pojede tak jak balíček slibuje. Což je asi jedna z těch chvil, kdy méně otrlí jedinci s tímto prostředím, potažmo jazykem Smalltalk skončí. Tudíž zde silně platí, není image jako image, a pokud budete mít tu smůlu, že se k vám dostane ta horší verze, tak se taky může stát, že si v prostředí ani nekliknete, lépe řečeno, co klik to chybová hláška, což se mi už taky stalo. Dalším záporem je to, že vše běží v jednom vláknu, tudíž se někdy zdá, že prostředí nereaguje a navíc, což se mi taky stalo, díky jistým balíčkům vytíží procesor do takové míry, že se nedostanete ani k možnosti v rámci operačního systému Squeak ukončit. Závěrem k prostřední Squeak, bych rád zdůraznil skutečnost, že Squeak je dialekt jazyka Smalltalk a tudíž značná část vlastností tohoto prostředí přímo vyplývá z vlastností jazyka, ostatně, jak už bylo řečeno, samotné prostředí je psáno v jazyce Smalltalk.

25

5. Datová struktura aplikace 5.1 Obecný datový model SmallDEVS Na níže uvedeném obrázku vidíme atomickou DEVS komponentu tak, jak nám ji knihovna SmallDEVS nabízí.

Obrázek 9 Atomická komponenta knihovny SmallDEVS

Atomický DEVS model v grafickém podání knihovny tedy obsahuje tři základní oblasti. V levé části můžeme pomocí tlačítka myši přidávat vstupní porty (reset, control) sloužící k zasílání požadavků. Stejným postupem můžeme přidat výstupní porty (stateAndReward). V prostřední části máme možnost nadefinovat sloty, pomocné metody, delegáty. Nejdůležitější je asi položka DEVS methods, po jejím otevření se nám nabídnou deklarace základních metod typických pro atomickou komponentu.

Obrázek 10 Atomická komponenta knihovny SmallDEVS s rozbalenou nabídkou DEVS methods

26

Zde vkládáme zdrojové kódy pro vnější přechodovou funkci (extTransition), výstupní funkci (outputFnc), vnitřní přechodovou funkci (intTransition) a časovou funkci (timeAdvance). Při psaní zdrojových kódu si musíme vystačit s poměrně jednoduchým editorem s pevně danou velikostí textového pole.

Tímto způsobem máme tedy možnost vytvářet atomické komponenty pomocí grafické šablony, do které implementujeme požadovanou činnost. Nicméně samotné atomické komponenty zpravidla tvoří základ simulace. Ony zodpovídají za jednotlivé simulace, ale nějakým způsobem musíme koordinovat jednotlivé simulační procesy, zde využijeme spojovaný DEVS.

Obrázek 11 Spojovaná komponenta na úrovni vnitřních komponent

Na výše uvedeném obrázku máme ukázku spojované DEVS komponenty. Má jeden vstupní

port

stateAndReware

propojený se

vstupním

portem

state objektu

state discretizer, přestože se na první pohled jeví jako atomická komponenta, může to být ve skutečnosti i spojovaná komponenta. Tato je propojena s další komponentou 27

RL controller a výstupy této komponenty jsou dále propojeny s výstupními porty spojovaného DEVSu. Takto vytvořená, spojovaná komponenta může dále rovněž být použita v jiné spojované komponentě. Pokud bychom tedy výše uvedenou spojovanou komponentu vložili do další spojované komponenty, spatříme objekt, který na první pohled vypadá jako atomický, přestože ve skutečnosti zapouzdřuje další síť komponent.

Obrázek 12 Spojovaná komponenta

Po sestavení modelů a jejich propojení můžeme spustit samotnou simulaci a to například přes tlačítko „Simulation“ (viz. např. obrázek 12). Přes jeho nabídku můžeme například simulaci spustit, pozastavit, resetovat. Můžeme zde i určit zda chceme výstup simulace směrovat na okno „Transcript“ či do textového souboru. Ukázku takového výstupu vidíme níže.

Obrázek 13 Výpis průběhu simulace

28

Na výstupu jsou například zobrazeny hodnoty vnitřních stavů jednotlivých komponent. Z obrázku můžeme například vyčíst existenci stavů first, ia, ib atd. patřící komponentě generator. U komponenty můžeme navíc vyčíst i existenci vstupního portu s názvem in a jeho hodnotu. Na výše uvedeném postupu lze spatřit výhody knihovny SmallDEVS mezi než například patří: srozumitelné a přehledné grafické rozhraní pro tvorbu jednotlivých komponent (např. AtomicDEVS, CoupledDEVS), grafické vyobrazení samotné simulace ji činí srozumitelnější, díky celkovému jednoduchému způsobu manipulace s jednotlivými knihovními třídami není nutná znalost způsobu „fungování na pozadí“. Nicméně knihovna má i jisté méně příjemné stránky, jako je poměrně omezený workspace u AtomicDEVS, nízké možnosti nápovědy a zpřehlednění kódu. V jistých případech jsem se setkal i s tím, že workspace komponenty ignoroval mnou uložený kód po jeho změně a to tak, že sice uložil mnou provedené změny, ale po spuštění simulace vykonával instrukce kódu před změnou. Výskyt této chyby je patrně spojen s chybnou syntaxí kódu, který chcete uložit. Obvykle je sice vypsána chybová hláška při pokusu o uložení změny nevalidního kódu, ale není to pravidlem. Celkově se domnívám, že knihovna bohatě poslouží svému určení školní pomůcky a při snaze seznámit studenty s DEVS formalismem. Není mi známo, zdali se nyní knihovna stále vyvíjí, či zda byl vývoj ukončen. Ovšem vzhledem k posledním úpravám na oficiálních webových stránkách projektu [14] se zdá, že byl vývoj ukončen.

29

5.2 Model mraveniště jako popis entit

Základní entitou celé simulace je mraveniště. Tato entita by měla zodpovídat za životaschopnost sebe sama, což znamená to, že musí být schopna zařídit například dostatek potravy pro veškeré mravence, které pod mraveniště spadají. Entita mraveniště by měla být tedy schopná řídit jednotlivé mravence tak, aby ti, svým dílem, přispěli k přežití celé kolonie. Je celkem zřejmé, že mraveniště bude tedy spojovaný DEVS model. Vzhledem k tomu, že tato entita by měla být schopná koordinovat sama sebe bez vnějších impulsů, nemá v tuto chvíli žádné vstupní či výstupní porty. Ty mohou být přidány v budoucnu, v případě, že by se uvažovalo o vylepšení modelu tak aby byl schopný interakce s jinými modely, třeba modelem simulující les, v němž mravenci sbírají materiál. Základní entitou mraveniště na úrovni atomických DEVS komponent je komponenta s názvem „Anthill consciousness“. Tato entita představuje mozek mraveniště. Jako taková by měla mít přehled o všech mravencích a věcech nezbytných pro fungování mraveniště jako je například množství jídla.

30

Obrázek 14 Diagram tříd Anthill consciousness

Výše zobrazený diagram tříd představuje „Anthill consciousness“ neboli „mravenčí vědomí“. Jako takové by mělo mít vždy představu o tom, kolik mravenců pod něj spadá. Tato hodnota odpovídá velikosti antPool. Tento atribut by měl představovat datovou strukturu obsahující jednotlivé mravence. Tento atribut by hrál významnou roli v případě, kdy bychom se rozhodli o rozšíření celé simulace o další modely, například les, kdy by pak mraveniště vyslalo mravence pro materiál, a poté přepojilo řídící porty mravence z mraveniště na model lesa. Jako základní činnosti byly identifikovány sběr potravy, sběr materiálu a obrana (hlídání) mraveniště. Pro každou tuto činnost by mělo mraveniště poskytnout trojici výstupních portů. Trojici z toho důvody, že entita mravence obsahuje tři vstupní porty 31

a to visuální, kinestetický a auditivní. Skrz tyto porty přijme mravenec pokyny z mraveniště určující jeho činnost. Výsledek činnosti může mravenec sdělit mraveništi skrze své výstupní porty, které jsou napojeny na mraveniště, resp. jeho vědomí, a tím je zajištěna zpětná vazba.

Obrázek 15 Simulace AnthillConsciousness se dvěma mravenci

Výše uvedený obrázek zobrazuje vědomí mraveniště ve spojení s mravenci typu soldier v prostředí Squeak. Jak je z něj patrné, mravenci jsou na „vědomí“ propojeni skrze trojici vstupních portů a naopak, „vědomí“ je s mravencem propojeno skrze jeho výstupní porty.

32

Vstupní port input, který obsahuje „vědomí“, zajišťuje tvorbu nových mravenců. Nicméně implementace byla dělána s myšlenkou, že tuto tvorbu by měla zaručovat mravenčí královna. Ta by v podstatě pouze nahradila port impuls. Mravenec, přestože z obrázku to není patrné, je zkonstruován jako spojovaný DEVS. Ten tvoří dvě atomické komponenty, mozek a tělo. Toto rozdělení umožňuje striktnější rozdělení vlastností mravence a snadnější přidávání nových vlastností.

Obrázek 16 Model vojáka

Obrázek 17 Model vojáka na úrovni vnitřních komponent

Mravenec tedy přijme na úrovni spojovaného modelu tři vstupy a výsledkem toho, je změna hodnot na trojici výstupních portů. Z pohledu atomického modelu mravenec disponuje trojicí vstupních portů, které jsou napojeny na mozek mravence. Ten na základě kombinací vstupních hodnot rozhodne a rozhodne o činnosti, kterou mravenec 33

provede. Mozek je dále napojen na tělo, v němž můžeme určit možnosti mravence, například možnosti omezení nosnosti. Z těla mravence jsou dále vyvedeny výstupní porty oznamující okolí aktuální stav. Na níže uvedené tabulce jsou uvedeny veškeré kombinace hodnot pro mravence, resp. vojáka.

Obrázek 18 Tabulka přechodů

Tabulka koresponduje s možnostmi přechodů, ty jsou zobrazeny na stavovém diagramu na následující straně.

34

Obrázek 19 Stavový diagram vojáka

Z něj je patrné, že mravenec (voják) se po svém narození dostane do stavu adolescence. Po určitém čase (ten určuje časová funkce ta atomického modelu) se stav přepne do chůze (walk). V tomto stavu mravence setrvává do doby, než mu mraveniště přidělí činnost. Voják může v našem případě chodit (walk), hlídat (watch), útočit (attack), bránit (defence) a nést náklad (carry). Jak je z diagramu patrné, mravenec nemůže přecházet mezi činnostmi libovolně. Nemůže kupříkladu být ve stavu „carry“ a z něj ihned přejít třeba do stavu „attack“. První musí přejít do stavu „defence“ a poté teprve může přejít do stavu „attack“. Pouze ze stavu „walk“ může přejít do libovolného stavu (samozřejmě do stavu „adolescence“ se již mravenec nemůže dostat) a naopak.

35

6. Popis implementace 6.1 Simulační engine Simulační engine je součástí implementace knihovny SmallDEVS. Na tomto místě se snažím vystihnout základní princip chování simulace poté, co je obdržen požadavek na vytvoření mravence. Chování enginu bylo zjišťováno v debugg módu. Nejedná se o detailní popis, jelikož snahou je spíše získání obecného povědomí o pozadí průběhu simulace.

Obrázek 20 Sekvenční diagram vytváření mravence

Na výše uvedeném obrázku vidíme sekvenční diagram znázorňující průběh vytváření mravence poté, co je na vstup impuls, který je napojen na „vědomí mraveniště“, vložena

36

hodnota (její obsah není podstatný, podstatné je to, že po vložení hodnoty na libovolný vstup základního DEVS modelu se spouští vnější přechodová funkce). Po příjmu vstupu třída DEVSRootSolverRT zkontroluje, v jakém stavu se simulace nachází, resp. zdali simulace probíhá, či nikoliv. Poté se spustí proces provádějící metodu processBody. Tato metoda začíná voláním metody prepareToStart a je ukončena metodou prepareToStop. Metoda posléze vyhodnotí stav procesu a na základě výsledku rozhoduje o spouštění metody simulationStep. Tato metoda zajišťuje časovou synchronizaci a rovněž zodpovídá za výpis stavu simulace. Tato metoda je volána několikanásobně na základě podmínky v metodě processBody. V metodě simulationStep je dále použit objekt Time, konkrétně jeho milisecondSince. SimulationStep je rovněž zodpovědná za volání objektu

metoda

CoupledDEVSPrototype, konkrétně jeho metody rozhoduje

o

volání

stejnojmenné

metody

receiveMsgX:time:. Tato metoda v podřízených

komponentách,

AtomicDEVSPrototype, tyto komponenty poté spouští vnější přechodovou funkci.

6.2 Simulační scénáře Simulační scénáře byly utvářeny hned na začátku, jsou to vlastně představy toho, jak by celá simulace mohla vypadat. Na základě scénářů byl poté vytvořen model simulace. Rovněž představují ideální možnosti rozšíření modelu, jelikož model byl vlastně vytvářen s ohledem na tyto scénáře. Základní scénář představuje samotné mraveniště, to je tvořeno mravenčí královnou, ta pouze vytváří (generuje) mravence, ty se poté napojí na mraveniště skrze své vstupní a výstupní porty. O konkrétním typu mravence (ten se po připojení nalézá ve stavu adolescence, dospívání) posléze rozhodne až mraveniště na základě svých potřeb. Mraveniště na základě svých potřeb, případně vnějších podnětů rozhodne, jakou činnost bude konkrétní mravenec dělat.

37

Mravenec by tedy mohl jít například do lesa na dříví. Mraveniště tedy pošle mravence do lesa, a přepojí jeho porty na les, který je implementován jako spojovaný model. Les může obsahovat další sub modely, například jiné tvory. Mravenec tedy v lese posbírá dřevo a vydá se na cestu zpět. Po celou dobu co je v lese, může od něj dostávat impulsy, na které patřičně zareaguje. Vzhledem k tomu, že je v tuto chvíli napojen na model lesa a nikoliv na model mraveniště je nutné, aby si mraveniště uchovávalo informaci o každém mravenci. Po té co vyjde z lesa, je napojen zpět na model mraveniště a pokračuje dále ve své činnosti. Simulace tedy umožňuje, a implementačně podporuje, možnosti výskytu dalších simulací, resp. spojovaných modelů. Díky nim je možné simulaci snadno rozšířit do komplexnější podoby.

38

7. Závěr Cílem práce bylo popsat chování mravenců v mraveništi za pomoci formalismu DEVS. Tohoto cíle bylo dosaženo za cenu zjednodušení pohledu na danou problematiku. Zjednodušení v tom slova smyslu, že byla vybrána pouze podmnožina navzájem souvisejících činností ze života mravence – činnosti mravence vojáka. Činnosti jako například sběr surovin či obrana byly implementovány samotnému mravenci. Ovšem rozhodování o tom, co má mravenec vlastně udělat, vydává mraveniště – to zde reprezentuje jednak naši klasickou představu mraveniště jako „hromádku něčeho“ obývanou kolonií mravenců a dále představuje to, co nazýváme kolektivním vědomím. Mravenec reaguje na změnu smyslů – ty jsou prezentovány trojicí portů, resp. visuálním portem, auditivním portem a kinestetickým portem. Tím jsou pokryty veškeré možné smyslové vstupy libovolného organismu. Mraveniště v roli vyššího vědomí tedy zašle mravenci na jeho vstupní porty hodnoty, podle kterých mravenec přejde do jiného stavu – chování. Zde můžeme spatřit další zjednodušení, možnosti mraveniště jsou určeny možnostmi mravence, zjednodušením mravence bylo dosaženo i zjednodušení mraveniště jako celku. Přestože se může zjednodušení jevit na první pohled jako nežádoucí jev, jedná se o jev nutný. Obecně totiž jakákoliv snaha o popsání dané skutečnosti je v podstatě založena na abstrakci a zobecnění daného jevu. O to horší je situace, kdy se snažíme vystihnout něco tak nestálého jako je živý organismus, jež se neustále mění. Poté se setkáváme díky tomu s pojmy jako instinkt či vyšší vědomí, které vlastně představují množinu možností daného organismu, o kterých víme (ty o kterých nevíme a nastanou, pak zpravidla označíme za náhodu), že můžou nastat, ale nedokážeme určit proč, resp. za jakých podmínek nastávají a mnohdy se tedy dané chováni jeví jako zcela nezávislé na vnějších. V naší práci jsme tento problém vyřešili právě již zmiňovanou abstrakcí. Tato práce se nazývá Simulace mraveniště, a proto bychom na ni taky tak měli nahlížet, jako na simulaci. Na simulaci, která se snaží připodobnit části chování mraveniště. Pokud bychom chtěli řekněme „přesnější“ simulaci, bylo by nutné implementovat 39

požadovanou množinu chování. Což vzhledem k prostředí Squeak, resp. knihovny SmallDEVS a celkové struktuře formalismu DEVS není příliš obtížné. Co se výběru jazyka, resp. prostředí týče, tak přestože to tak zprvu nevypadalo, zpětně musím uznat výhody jazyka Smalltalk, potažmo prostředí Squeak, ty jsou ostatně popsány výše. Samotný formalismus DEVS mě zaujal především svojí elegancí, jež pramení z jeho jednoduchosti, ostatně pokud si z příkladu hráčů ping-pongu odmyslíme tu formálnější část s predikáty, tak se domnívám, že transformace hráčů ping-pongu do formalismu DEVS je jasná a není tam nic, co by se dalo nazvat „věcmi na pozadí“ (ostatně i samotné predikáty jsou, řekl bych, srozumitelné). Co se knihovny SmallDEVS týče tak ji nemohu porovnat s jinými obdobnými knihovnami, kterých je poměrně dost (spousta z nich pochází z akademické půdy), a přestože se v ní vyskytují věci, jež by se jí dali vytknout, tak celkem vzato se s ní pracovalo dobře. O výhodách skrývající se v samotném prostředí Squeak se již nebudu zmiňovat, ty jsou, řekl bych, celkem jasně vysvětleny v příslušné kapitole.

40

Literatura [1] SLAVÍČEK, Pavel. Distribuované simulační prostředí. [s.l.], 2006. 90 s. Dizertační práce. Vysoké učení technické v Brně. [2] Wikipedia [online]. 2010 [cit. 2010-12-09]. High level architecture (simulation). Dostupné z WWW: . [3] ZEIGLER , Bernard. The DEVS/HLA Distributed Simulation Environment . [s.l.], 1998. 51 s. University of Arizona. [4] SwarmWiki [online]. 2003, 2010. Dostupné z WWW: . [5] Department of Computer Science [online]. 2002, 2011. Dostupné z WWW: . [6] Wikipedia [online]. 2011. DEVS. Dostupné z WWW: . [7] Wikipedia [online]. 2010. Mraveniště. Dostupné z WWW: . [8] Wikipedia [online]. 2011. Mravencovití. Dostupné z WWW: . [9] Wikipedia [online]. 2010. Mravenec argentinský. Dostupné z WWW: . [10] Extremofilní organismy [online]. 2010. Extremofilní organismy. Dostupné z WWW: . [11] Český rozhlas Leonardo [online]. 2010. Koloniální hmyz funguje jako superorganismus. Dostupné z WWW: . [12] Wikipedia [online]. 2010. Kolektivní inteligence. Dostupné z WWW: . [13] JAMES - A Java-Based Agent Modeling Environment for Simulation [online]. 2001. Dostupné z WWW: . [14] SmallDEVS [online]. 2007. Dostupné z WWW: . 41

Seznamy Seznam obrázků Obrázek 1 Architektura DEVS/HLA ................................................................................ 9 Obrázek 2 Stav simulace chvíli po spuštění ................................................................... 11 Obrázek 3 Stav simulace po nalezení potravy ................................................................ 11 Obrázek 4 Vytváření feromonové stopy ......................................................................... 11 Obrázek 5 Složení těla mravence.................................................................................... 18 Obrázek 6 Mravenci, vojáci ............................................................................................ 18 Obrázek 7 Print screen prostředí Squeak s přítomným souborem sources ..................... 23 Obrázek 8 Print screen prostředí Squeak bez souboru sources ...................................... 23 Obrázek 9 Atomická komponenta knihovny SmallDEVS ............................................. 26 Obrázek 10 Atomická komponenta knihovny SmallDEVS s rozbalenou nabídkou DEVS methods ........................................................................................................................... 26 Obrázek 11 Spojovaná komponenta na úrovni vnitřních komponent............................. 27 Obrázek 12 Spojovaná komponenta ............................................................................... 28 Obrázek 13 Výpis průběhu simulace .............................................................................. 28 Obrázek 14 Diagram tříd Anthill consciousness ............................................................ 31 Obrázek 15 Simulace AnthillConsciousness se dvěma mravenci .................................. 32 Obrázek 16 Model vojáka ............................................................................................... 33 Obrázek 17 Model vojáka na úrovni vnitřních komponent ............................................ 33 Obrázek 18 Tabulka přechodů ........................................................................................ 34 Obrázek 19 Stavový diagram vojáka .............................................................................. 35 Obrázek 20 Sekvenční diagram vytváření mravence ..................................................... 36

Seznam zkratek DEVS

Discrete EVent System Specification.

HLA

High-Level Architecture.

MASON

Multi-Agent Simulator Of Neighborhoods or Networks.

JAMES

Java-based Agent Modeling Environment for Simulation

42

Přílohy K práci je přiložen jeden CD disk. Přiložené CD obsahuje adresář textová příloha, ten obsahuje bakalářskou práci ve formátu PDF, dizertační práci na téma Distribuované simulační prostředí, ve formátu PDF, která je uvedena v použité literatuře (1) a dále je zde zpráva The DEVS/HLA Distributed Simulation Environment rovněž uvedená v použité literatuře (3). Druhý adresář s názvem zdrojové kódy obsahujete virtuální stroj pro Win platformu (adresář virtual machine) a obraz obsahující simulaci (adresář image).

43