Univerzita Hradec Králové Fakulta informatiky a managementu
LETNÍ ŠKOLA „MEZIOBOROVÉ PŘÍSTUPY INFORMATIKY A KOGNITIVNÍ VĚDY“ Recenzovaný sborník 1. ročníku letní školy Hradec Králové 6.6. až 10.6.2011
Tribun EU s.r.o., 2011
Recenzenti: Prof. RNDr. Josef Zelenka, CSc.
Tato publikace neprošla jazykovou úpravou.
Editoři:
ISBN
Prof. RNDr. Josef Zelenka, CSc.
Obsah 1. ÚVOD ............................................................................................................ 4 2. PŘÍSPĚVKY ................................................................................................. 5 RICHARD CIMLER, KAMILA OLŠEVIČOVÁ ........................................................... 6 MICHAL GREGOR, KAREL PETRÁNEK, MARTIN BURIAN ................................... 11 LUKÁŠ BERAN, KAREL PETRÁNEK .................................................................... 17 TOMÁŠ MACHÁLEK........................................................................................... 26 3. POSTERY ................................................................................................... 37 ALENA POZDÍLKOVÁ ......................................................................................... 37
1.
Úvod
2.
Příspěvky
HLEDÁNÍ CESTY A GENEROVÁNÍ MAPY PATHFINDING AND MAP GENERATING Luboš Běhounek
Abstrakt Tato práce se zabývá jednoduchým generováním výškové mapy pomocí generování náhodných hodnot a jejich rozostřením a následným grafickým zobrazením v ukázkovém programu, dále se zabývá hledáním nejvýhodnější cesty v této vygenerované výškové mapě za využití algoritmu A* s heuristikou i bez s možností nastavení různých parametrů – například jestli se lze pohybovat diagonálně, podle jaké cenové funkce se má cesta hledat apod. To je vše ukázáno v ukázkovém programu, který nabízí i možnost editace vlastní mapy. Klíčová slova hledání cesty, generování mapy Abstract This work is about simple generating of heightmap using random values and their blurring followed by graphic presentation in example application. In this heightmap, A* algorithm is used to search for the best path both with and without heuristics with optional parameters – if agent can move on diagonals, what cost function is used etc. Example application which allows user's customization of map is used for demonstration. Keywords pathfinding, map generating 1. Úvod Počítačové generování map se dnes často používá pro generování terénu za využití tzv. heightmapy (výšková mapa), především z toho důvodu, že je to poměrně jednoduché a efektivní. Takto generované mapy se používají pro různé zobrazení terénu v simulacích, počítačových hrách, ale i jinde. Díky diskrétnosti takto generovaných map je pak jednoduché sestavení grafů reprezentujících tuto mapu a hledání optimálních cest - například pro navigaci botů (počítačem ovládaných postav). K tomuto účelu jsem v jazyce C# vytvořil jednoduchý ukázkový program (ze kterého je většina zde přiložených obrázků), který dokáže generovat
pseudonáhodné mapy (nebo nechá uživatele je upravovat) a umožňuje uživateli nastavovat základní parametry zobrazování výsledků a měnit základní parametry prohledávacího (i generovacího) algoritmu. 2. Generování mapy Pro uchovávání výšky trojrozměrného terénu se dnes mimo kompletních modelů využívá také výše zmíněná výšková mapa, což je dvourozměrné pole, ve kterém každý záznam určuje výšku nějakého bodu terénu. Mezi jeho výhody patří především snadná editovatelnost. Výsledná pozice bodu je určena jeho souřadnicemi v poli a jako třetí souřadnice je použita právě hodnota v poli na této pozici, například pokud hodnota pole[4,8]=5, pak pozice bodu je (4,8,5). Pro případné dopočítání pozice bodů, které v poli nejsou, se pak používá interpolace z pozic bodů okolních. Na obr. 1 je vidět ukázková heightmapa ve stupních šedé (čím je barva světlejší, tím je vyšší nadmořská výška).
Obr. 1: Příklad výškové mapy - Austrálie [4]
Při generování výškové mapy lze postupovat mnoha způsoby, mezi základní patří ruční editace, která sice většinou vypadá nejlépe, ale může být pro velké mapy příliš pracná. Proto se někdy přistupuje k procedurálnímu generování map, které dokáží vygenerovat více či méně realisticky vypadající mapu, v závislosti na kvalitě algoritmu a vhodně nastavených parametrech. V dnešní době se pro tvorbu výškových map často využívají fraktály a Perlinův šum (perlin noise)[1], pro ukázkovou aplikaci byl z důvodu jednoduchosti vytvořen následující algoritmus, který je pro účely ukázkové aplikace plně dostačující (dá se říci, že je to vlastně zjednodušená verze Perlinova šumu). Pro každý bod v dvourozměrném poli je vygenerováno náhodné číslo v rozsahu 0Vmax, kde Vmax je maximální výška terénu, vznikne terén, který je ale příliš členitý (zrnitý), viz obr. 2, proto je několikrát aplikováno ještě jednoduché rozostření, které pro každý záznam spočítá průměr z jeho okolí (obr. 3) a nakonec je ještě celý
terén o určitou hodnotu snížen, aby bylo možné určovat množství vody na mapě (obr. 4), voda je neprůchozí pole, za vodu jsou považována všechna pole, kde je výška<0.
Obr. 2: Terén vygenerovaný z náhodných čísel
Obr. 3: Terén po pětinásobné aplikaci rozostření
Obr. 4: Terén po pětinásobném rozostření a snížení výšky 3. Hledání cesty Kvůli jednoduchosti implementace algoritmu a zobrazení výsledků je zde mapa převedena na graf jako pravidelná mřížka, ale existují i jiné přístupy, například
navigation mesh, který mapu průchodnosti ukládá jako množinu mnohoúhelníků, což je výhodnější především pro rozsáhlé spojité prostory (více viz. [6]). Pro hledání cesty byl zvolen velmi rozšířený algoritmus A*, který za pomoci heuristiky kombinuje optimálnost Dijsktrova algoritmu s rychlostí např. algoritmu Greedy Best-First-Search (který není optimální, ale je rychlejší)[5]. Pokud je u heuristické funkce dodržena podmínka, že odhad nepřesáhne reálnou vzdálenost, tak je nalezená cesta vždy optimální, tedy že má nejmenší cenu[2]. Popis algoritmu[3]: Openset a Closedset jsou množiny polí, openset je množina právě prohledávaných a closedset je množina již prohledaných. H cena je heuristický odhad ceny z tohoto pole do cíle, G cena je aktuální cena cesty do daného políčka od startu a F je odhad výsledné délky cesty přes toto políčko (F=G+H). 1) Přidá se počáteční pole do opensetu. 2) Opakuje se následující: a) Vyhledá se políčko X s nejnižsí F cenou v opensetu. b) X se vyřadí z opensetu a přidá do closedsetu. c) Pro všechny sousední pole Y tohoto políčka X: • Ignoruje se, pokud není průchodné nebo je v closedsetu, jinak • Pokud není v opensetu, přidá se do něj. X se nastaví jako jeho rodič. Nastaví se F, G a H ceny políčka Y. • Pokud již byl v opensetu, zkontroluje se, jestli je tato cesta k tomuto políčku lepší (použitím G ceny). Nižší G cena znamená, že je to lepší cesta, pokud tomu tak je, změní se rodič políčka Y na políčko X a přepočítá se G a F skóre políčka Y. 3) Algoritmus končí když: a) Je přidáno cílové políčko do closedsetu – cesta byla nalezena b) Openset je prázdný – cesta neexistuje 4) Uložit cestu. Začíná se od cíle, najde se jeho rodič, přidá se do výsledné cesty, nalezne se rodič jeho rodiče (ten se také přidá do výsledné cesty) a toto se analogicky opakuje, dokud se nedojde k počátku. Pro heuristickou funkci H(n) políčka n existuje velké množství heuristických funkcí, mezi běžně používané se řadí například Manhattanská a Chebyshevova vzálenost[5], v ukázkovém programu byla použita vzdálenost Eukleidovská: H(n) = dist(n, cíl). Tato funkce dodržuje podmínku nutnou pro nalezení optimální cesty[2] a hledání je většinou značně urychleno, protože jsou při prohledávání upřednostňována pole směrem k cíli, takže jich program musí prohledat menší množství. Jako heuristickou funkci lze použít i H(n)=0, což bude mít za následek, že žádná heuristika nebude použita. Rozdíl mezi použitím a nepoužitím heuristické funkce je vidět v množství prohledaných polí na obr. 5 a obr. 6 (lze postřehnout, že různé heuristické funkce mohou vracet různé cesty, ale celková cena těchto cest je vždy stejná).
Obr. 5: Vyhledávání s H(n) = 0
Obr. 6: Vyhledávání s H(n) = dist(n,cil)
Způsobů výpočtu ceny přechodu mezi sousedními políčky lze použít mnoho, v ukázkovém programu jsou ukázány tyto tři: minimální výškový rozdíl – hledá se taková cesta, která bude mít nejmenší součet převýšení, agent se bude snažit veškeré překážky obejít, pokud je to možné, i kdyby měl vzdálenostně ujít mnohonásobek nejkratší přímé cesty (obr. 7) costheight = abs(height(n1)-height(n2))
•
•
minimální vzdálenost – agent ignoruje převýšení, jde nejkratší vzdušnou cestou, pouze pokud jsou v cestě neprůchozí místa, tak se jim vyhýbá (obr. 8). Pokud se lze pohybovat po diagonálách a v daném prostředí cesta po diagonále má větší cenu (jako v reálném světě), tak pro výpočet vzdálenosti na diagonále je vhodnější použít vzdálenost spíše než 1.
costdist = sqrt((n1.x-n2.x)2 + (n1.y-n2.y)2)
kombinovaná – použije se výškový rozdíl i vzdálenost políček (obr. 9), každému parametru lze nastavit jinou váhu (v následujícím vzorci jsou váhami proměnné alpha a beta) costcomb = alpha*costheight + beta*costdist
•
Obr. 7: Cena - minimální výškový rozdíl
Obr. 8: Cena - minimální vzdálenost
Obr. 9: Kombinovaná cena (obě váhy 1)
4. Závěr Tento článek se zabýval jednoduchým vytvářením výškových map, včetně jednoho ukázkového algoritmu využívajícího generování náhodných hodnot a jejich následním rozostřením pro realističtější vzhled a hledáním nejkratší cesty v této
mapě s různým nastavením ohodnocovací funkce (výškový rozdíl, vzdálenost a obě kritéria zkombinovaná) a různými funkcemi pro heuristickou analýzu, která při volbě vhodného algoritmu pro daný typ mapy dokáže prohledávání výrazně urychlit. Literatura [1] ELIAS, Hugo. The good-looking textured light-sourced bouncy fun smart and stretchy page [online]. 2003 [cit. 2011-06-04]. Perlin Noise. Dostupné z WWW:
. [2] KORF, Richard. Symposium on Abstraction, Reformulation and Approximation [online]. 2000 [cit. 2011-06-04]. Recent Progress in the Design and Analysis of Admissible Heuristic Functions. Dostupné z WWW: . [3] LESTER, Patrick. Almanac of Policy Issues [online]. 2005 [cit. 2011-06-04]. A* Pathfinding for Beginners. Dostupné z WWW: . [4] ModTheSims [online]. 2010 [cit. 2011-06-04]. Issue with self-made heightmaps in CAW. Dostupné z WWW: . [5] PATEL, Amit. Amit's A* Pages [online]. 2009 [cit. 2011-06-04]. Dostupné z WWW: . [6] TOZOUR, Paul. Game/AI [online]. 2008 [cit. 2011-06-04]. Fixing Pathfinding Once and For All. Dostupné z WWW: .
Luboš Běhounek Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected]
ROZPOZNÁNÍ OBLIČEJŮ NA MOBILNÍCH ZAŘÍZENÍCH FACE RECOGNITION ON MOBILE DEVICES Lukáš Beran, Karel Petránek
Abstrakt Vývoj současných aplikací je v současnosti velkou měrou ovlivněn zejména nároky na uživatelskou přívětivost, intuitivní a rychlé ovládání výsledné aplikace. V souvislosti s tímto trendem se v aplikacích čím dál více využívá počítačového vidění. Jedním z nejčastějších úkolů počítačového vidění je detekce a rozpoznání osob na fotografii. Příspěvek se věnuje detekci a rozpoznání obličejů na fotografiích, které jsou pořízeny pomocí mobilního telefonu s platformou Android. V příspěvku jsou představeny běžně používané algoritmy a navržena demonstrační mobilní aplikace typu klient-server, která rozpozná osoby na fotografii pořízené vestavěnou kamerou. Klíčová slova detekce obličejů, rozpoznání obličejů, počítačové vidění, Android, mobilní zařízení Abstract The development of modern applications strongly depends on user friendliness and fast responses of the user interface. Following this trend, many applications employ computer vision as a key usability element. The most frequent use of computer vision is in the area of face detection and recognition. This article presents face detection and recognition on mobile devices running the Android operating system and discusses some commonly used algorithms. The results of face recognition on a mobile device using its built-in camera are demonstrated on a sample application. Keywords face detection, face recognition, computer vision, Android, mobile devices
1. Úvod Zvyšující se požadavky na rychlost a bezpečnost dnešních systémů vedou vývojáře k používání sofistikovaných metod jak spolehlivě a v krátkém časovém intervalu jednoznačně identifikovat jedince. Jednou z možností jsou biometrická data. Mezi tato data patří např. otisky prstů, oční sítnice, duhovka nebo obličej. Jejich porovnávání s referenčními daty uloženými v databázi lze určit jejich shodu a potvrdit totožnost nebo naopak. V souvislosti s rozvojem technologií umožňujícími pracovat s vizuálními daty vzrostla poptávka po jejich využívání v nejrůznějších aplikacích. Mezi velmi populární případy využití počítačové analýzy obrazu patří rozpoznávání lidského obličeje. Tento princip identifikace jedince lze využít v celé řadě aplikací, které pracují s fotografiemi jednotlivých lidí. Typickým příkladem jsou např. sociální sítě, kde jsou kromě některých osobních údajů uživatelů obsaženy také fotografie s jejich obličeji. Mezi základní cíle tohoto příspěvku patři využití algoritmu rozpoznání lidské tváře v oblasti mobilních technologií a sociálních sítí.
1
2. Úvod do problematiky 2.1. Biometrická data Biometrická data se v současnosti využívají v mnoha odvětvích zejména v souvislosti s identifikací dané osoby a zvýšení bezpečnosti. Ať už se jedná o velkou organizaci (např. tovární komplex s utajenými výrobními postupy) nebo pouze o přístupový terminál pro výdej určitého druhu zboží (identifikace pomocí obličeje v tomto případě zvyšuje zejména rychlost autentizace), slouží biometrická data obecně za účelem rozpoznání. Způsob využití těchto dat pak primárně závisí kontextu a na konkrétním účelu, za kterým jsou získávána. Následující tabulka shrnuje některé příklady jak tato data využít (zdroj [10]). Oblast
Konkrétní využití řidičské průkazy, imigrace, pasy, registrace voličů
Biometrika
úřady vyžadující kontrolu totožnosti (sociální příspěvky,…) logování do systémů (např. Windows 7) zabezpečení přístupu k databázi, bezpečnost aplikací, šifrování souborů
Informační bezpečnost
zabezpečení obchodních terminálů (bankomatů) přístup k síti intranet, přístup k síti internet, lékařské záznamy kamerové systémy
Dohlížení a prosazování zákonů
identifikace tváře podezřelého vyšetřování
Identifikační karty
autentizace uživatele
Přístupová práva
přístup do organizace (např. do továrny, do utajeného prostoru) možnost přístupu k vybranému přístroji
Tabulka 1- Typické aplikace rozpoznání obličeje
2
2.2. Proces rozpoznání obličeje Celý proces rozpoznávání obličeje lze z teoretického hlediska rozdělit do několika následujících kroků: Získání dat pro následnou analýzu o pořízení snímku z fotoaparátu, popř. nalezení existujícího snímku, extrahování snímku z videa Identifikace obličeje na analyzovaném snímku o využití vhodného algoritmu, volba správné míry kritérií pro rozpoznání obličeje Porovnání zjištěného obličeje s obličeji v databázi o porovnání získaných grafických dat s grafickými daty v databázi 2.3. Identifikace obličejů v obraze Identifikace obličejů ve vyfotografovaném snímku se dá rozdělit na dvě dílčí části: Detekce obličejů – zjištění oblastí, ve kterých se obličeje nachází Rozpoznání obličejů – porovnání detekovaných oblastí s databází známých obličejů Protože rozpoznání obličejů vyžaduje databázi obličejů, která může být velmi rozsáhlá, není vhodné provádět rozpoznání obličejů na mobilním zařízení s omezenou pamětí. Vhodnou strategií je provést detekci obličejů na zařízení a detekované obličeje odeslat k rozpoznání na server. 2.3.1. Detekce obličejů Detekce obličejů na mobilním zařízení musí být co nejméně výpočetně náročná, aby nedocházelo k prodlevám při používání aplikace a s tím spojené vysoké spotřebě elektrické energie. 2.3.2. Detekce na základě barvy kůže Jednou z nejjednodušších a zároveň výpočetně nejméně náročných metod je detekce obličejů na základě barvy kůže. Dá se ukázat, že barva lidské kůže se pohybuje v poměrně úzké části barevného spektra, a lze ji proto snadným způsobem segmentovat ze vstupního obrazu [1]. Vhodným barevným modelem pro snadnou specifikaci barvy kůže je HSV [8] (HueSaturation-Value). HSV reprezentuje barvu jako tři hodnoty – odstín (hue), jako mix základních barev červené, zelené, modré a žluté; sytost (saturation), která reprezentuje barevnost (nulová sytost znamená šedotónový obrázek); světlost (value), která udává intenzitu dopadajícího světla. Mezi výhody detekce na základě barvy patří nezávislost na orientaci obličeje a jeho vzdálenosti od kamery. Metoda je rovněž robustní vůči změnám v osvětlení obličeje a změnám výrazu. Nevýhodou detekce na základě barvy kůže je fakt, že se tato barva na fotografiích vyskytuje často i v oblastech, které nejsou součástí lidského těla. Navíc není možné detekovat obličeje na černobílých fotografiích.
3
Obrázek 1 - Ukázka segmentace na základě barvy kůže. Na obrázku je vidět častý výskyt barvy kůže mimo oblast těla.
2.3.3. Detekce algoritmem pro rozpoznání objektů Viola a Jones [9] v roce 2001 navrhli adaptivní algoritmus pro detekci objektů v obraze. Protože obličeje lze chápat jako speciální případ objektu, je možné tento algoritmus využít pro jejich detekci. Algoritmus nejprve transformuje vstupní obraz do jednoduchého feature space, které obsahuje pouze čtyři druhy obdélníkových features. Tyto features lze vypočítat v konstantním čase, nezávisle na velikosti obdélníku [4]. Díky tomu je možné dosáhnout velmi rychlého běhu algoritmu, a zároveň testovat různé velikosti obdélníků, čímž je zajištěna nezávislost na velikosti obličeje. Protože obecně existuje v obrazu velké množství features (několikanásobně větší než je počet pixelů), je nutné eliminovat features, které nejsou pro detekci objektu kritické. Viola a Jones používají adaptivní učící se algoritmus AdaBoost [6] pro detekci takových features. Pro detekci na základě natrénovaných dat je opět použit AdaBoost pro rozhodnutí, zda daná množina features odpovídá danému objektu. Výhodou Viola-Jones algoritmu je vysoká rychlost, detekce obličejů i v šedotónových obrazech, možnost adaptace a nezávislost na velikosti objektu. Nevýhodou je nutnost algoritmus natrénovat a citlivost vůči rotaci a afinnímu zkreslení, které je u fotografií běžné. Tento algoritmus je použit v implementaci mobilní aplikace, přičemž jako základ byly využity knihovny OpenCV [3] a JViolaJones [2], které obsahují implementaci tohoto algoritmu a rovněž natrénované modely ve formě XML souborů.
4
Obrázek 2 - Ukázka detekce obličejů s použitím Viola-Jones algoritmu a trénovacích dat OpenCV. Obličej, který je pootočen, není správně detekován.
2.3.4. Rozpoznání obličejů Cílem rozpoznání obličejů je porovnání oblastí vrácených detektorem obličejů s databází známých obličejů. V implementaci byla fáze rozpoznání obličejů přesunuta na server kvůli vysoké paměťové náročnosti při zpracovávání rozsáhlejší databáze obličejů. Umístění na serveru rovněž umožňuje jednodušší propojení se sociálními sítěmi. 2.3.5. Rozpoznávání na základě 2D informace Pro 2D rozpoznání obličejů je možné využít podobné principy jako pro detekci. Základem je extrakce features ze snímku obličeje, čímž dojde ke snížení výpočetní složitosti problému a ke zvýšení SNR. Často aplikovanými metodami pro extrakci features jsou Principal Component Analysis (PCA), Independent Component Analysis či Linear Discriminant Analysis (LDA) [7]. Po extrakci těchto features je vypočítána euklidovská vzdálenost mezi vzorovým snímkem a snímkem s neznámým obličejem. Osoba na snímku je označena, pokud je nalezen takový vzorový snímek, který má od vstupního snímku vzdálenost menší než stanovený práh. Pokud je takových snímků více, je vybrán ten s nejmenší vzdáleností. Díky těmto výpočetně jednoduchým krokům je možné provádět rychlé rozpoznání osob. Nevýhodou těchto metod je závislost na intenzitě osvětlení, velikosti, rotaci a afinních transformacích, takže jsou vhodné především na rozpoznání obličejů orientovaných přímo do kamery. 2.3.6. Rozpoznávání na základě 3D informace Další třídou algoritmů, které lze využít pro rozpoznání obličeje, je rozpoznávání na základě 3D informace. Předpokladem je získání trojrozměrných grafických dat a jejich následné převedení do vhodné zpracovatelné digitální podoby. Nejčastěji se pro tento účel využívá tzv. normálová mapa. Jedná se o barevný obrázek, kde jednotlivé složky RGB modelu reprezentují ve dvojdimenzionálním (dále jen 2D, 3D) obraze odpovídající obraz ve 3D. Zjednodušeně řečeno se jedná o 2D reprezentaci povrchu tváře ve 3D. Jednotlivé barevné pixely RGB modelu pak představují odpovídající normály. Samotný převod obrazu obličeje na normálovou mapu probíhá v několika krocích. Nejprve je nutné z originálního obrazu tváře získat pomocí aproximace její přibližný 5
tvar. V tomto kroku je s využitím normál vytvořena rekonstrukce obličeje pomocí polygonů a vznikne síť reprezentující tvar obličeje ve 3D (viz Obrázek 3b.). Následně je vytvořena sférická projekce (promítnutí) 3D sítě na 2D plátno (Obrázek 3c.). Posledním krokem je převedení normál ze získané sítě (Obrázek 3d.) na dvourozměrné pole, kde každý obrazový bod představuje normálu pomocí hodnoty barevného spektra RGB [5].
Obrázek 3 - Princip převodu grafických dat na normálovou mapu (a) 3D model, (b) aproximovaná síť, (c) 2D projekce sítě, (d) normálová mapa
Hlavním důvodem procesu převodu na normálovou mapu je snadnější manipulace s daty v této podobě. Při použití této reprezentace grafických dat lze provádět celá řada akcí, jako jsou rozpoznání výrazu obličeje nebo vzájemné porovnávání dvou obličejů. 2.3.7. Porovnání grafických dat obličejů Ve chvíli, kdy jsou grafická data převedena do podoby normálové mapy, lze přejít k samotnému procesu porovnávání obličejů. Ve výše uvedeném postupu jsou grafická data převedena pomocí RGB modelu na normálovou mapu. Tato reprezentace je vhodná pro porovnání dvou obličejů a následnému určení jejich shody. Podle [2] se pro porovnání normálové mapy NA a NB použije následující rovnice, kde jsou obsaženy jednotlivé normály zastoupeny složkami RGB modelu. ar cos( rN A rN B
g N A g NB
bN A bN B )
Kde ϴ je úhlová vzdálenost mezi obrazovými body (xNA, yNA) a (xNB, yNB) normálové mapy NA a NB. Následně je vytvořena diferenční mapa, kde jsou jednotlivé rozdíly zaznamenány pomocí stupnice šedivé barvy. Pomocí této mapy diferencí lze sestavit histogram (obr. č. 2), z kterého je patrné jako velká je vzájemná podobnost obou tváří.
Obrázek 4 - Histogram diferencí, zdroj [8]
6
Obrázek 4 zobrazuje dva histogramy, které zachycují úhlové vzdálenosti. V prvním případě (a) byla rozdílnost obou porovnávaných tváři velmi malá (shodné tváře, podobná normálová mapa). V druhém případě (b) jsou normálové mapy odlišné (odlišné obličeje) [8]. 3. Návrh demonstrační aplikace Navrhovaná aplikace funguje na mobilním zařízení a k identifikaci obličejů využívá služby pro on-line rozpoznávání obličejů Face.com. Jako softwarová platforma byl zvolen operační systém Google Android. Pro implementaci byl vybrán algoritmus detekce obličejů Viola-Jones především kvůli vysoké rychlosti a existující implementaci v podobě OpenCV [3] a JViolaJones [2]. V aplikaci jsou pro porovnání použity obě implementace, přičemž z rychlosti zpracování je zřejmá výhoda nativního kódu v podobě OpenCV. Protože je z paměťových a výpočetních důvodů nevhodné udržovat na mobilním zařízení kompletní databázi známých obličejů pro rozpoznání, byla část pro rozpoznání obličejů přesunuta na server. Na server jsou odesílány pouze výřezy s detekovanými obličeji, aby byl minimalizován datový přenos. 3.1. Způsob použití aplikace Základním účelem demonstrační aplikace (z uživatelského úhlu pohledu) je využití možnosti mobilního zařízení pracovat s fotografiemi a následně využití dat umístěných na sociální síti. Uživatel bude pak během krátkého okamžiku schopen zjistit informace o vyfotografované osobě. Mezi základní dostupné funkce ze strany uživatele patří: Identifikace obličeje s využitím vestavěného fotoaparátu vlastního zařízení Identifikace obličeje s využitím fotografie uložené v galerii 4. Závěr Mezi základní požadavky na rozpoznání obličejů na mobilních zařízeních patří výpočetní nenáročnost a rychlost zpracování. V příspěvku bylo prozkoumáno několik způsobů rozpoznání obličeje. Přístup, který využívá snímání 3D obrazu celého obličeje a porovnává rozdíly normálových vektorů dvou obličejů, je velmi přesný, není však vhodný pro mobilní zařízení. Důvodem je vysoká výpočetní náročnost a absence 3D informace v datech z vestavěné kamery. V demonstrační aplikaci byl využit postup rozpoznání založený na detekci obličejů na zařízení a následné rozpoznání těchto obličejů na serveru. Metoda detekce obličejů je založena na algoritmu Viola-Jones, který pomocí adaptivního přístupu redukuje dimenzionalitu úlohy. V kombinaci s implementací v nativním kódu je tento postup dostatečně výkonný i pro mobilní zařízení, přičemž úspěšnost detekce dosahuje 50– 80 % v závislosti na světelných podmínkách a vzdálenosti obličejů od kamery.
7
Literatura [1] ALBIOL, A., TORRES, L. & DELP, E.J. Optimum Color Spaces for Skin Detection. , 2001. [2] ANON. Jviolajones - Java face detection - Google Project Hosting [online]. [Cit. 18.4.2011]. Dostupné z WWW: . [3] ANON. OpenCV Homepage [online]. [Cit. 18.4.2011]. Dostupné z WWW: . [4] CROW, F.C. Summed-area tables for texture mapping. ACM SIGGRAPH Computer Graphics, 1984, vol. 18, s 207–212. [5] DELAC, K. & GRGIC, M. Face Recognition. InTech 2007, ISBN 9783902613035. [6] FREUND, Y. & SCHAPIRE, R.E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. , 1995. [7] GRGIC, M. & DELAC, K. Face Recognition Homepage [online]. [Cit. 18.4.2011]. Dostupné z WWW: . [8] Oliveira. Skin Detection Using HSV Color Space [online]. [Cit. 18.4.2011]. Dostupné z WWW: <www.matmidia.mat.pucrio.br/sibgrapi2009/media/posters/59928.pdf>. [9] VIOLA, P. & JONES, M. Robust Real-time Object Detection. INTERNATIONAL JOURNAL OF COMPUTER VISION, 2001. [10] ZHAO, W., CHELLAPPA, R., PHILLIPS, P.J. & ROSENFELD, A. Face recognition: A literature survey. ACM Computing Surveys (CSUR), 2003, vol. 35, s 399–458. Lukáš Beran Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected] Karel Petránek Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected]
8
UŽITÍ SOFTBOTŮ A „UI“ PRO NPC USING SOFTBOTS AND „AI“ FOR NPC Stanislav Brandejs
Abstrakt Tato práce je zaměřena primárně na oblast nehráčských charakterů (NPC) v počítačových hrách. Po definování podstatných pojmů bude čtenáři představeno roztřídění žánrů her a příslušných NPC a také odpovídají techniky UI, které jsou používané pro implementaci požadovaného chování herních elementů. V následující části následuje detailní popis vlastní funkcionality a architektury botů použitých v akčních hrách z prvního pohledu (FPS). V závěru jsou uvedeny informace o budoucí práci a konceptech v této oblasti vývoje. Klíčová slova počítačové hry, herní entity, NPC, softwaroví boti, architektura softbotů Abstract This paper is focused primarily on area of Non-Player Characters (NPC) in computer games. After definition of necessary terms, reader will be introduced to classification of both games and NPCs, according to AI techniques used for implementation of desired behavior in game elements. In the following part, detailed description of functionality and architecture of bots used in First Person Shooter (FPS) games will be provided. Information on future work and concepts in this area is concluding this paper. Keywords Computer games, Game entities, NPC, Software Bots, Architecture of Softbots 1. Úvod V dnešní době jsou již počítačové hry chápány jako další mediální forma, stejně jako filmová produkce, nebo knižní tvorba. Na rozdíl od filmů a textu nabízejí širokou možnost zpětné vazby, značnou dynamičnost děje a vlastního zážitku. Krom toho, že při hraní hry vnímáme její audiovizuální stránku, jsme zároveň součástí celého herního prostředí, které reaguje na naše akce. Tato reaktivnost se s dnešním vývojem stále zdokonaluje a jsou používány nové mechanismy, které tento zážitek umocňují.
Velice důležitým prvkem je implementace Umělé Inteligence (dále jen UI), její integrace do herního prostředí a její použití pro NPC, které jsou nedílnou součástí zážitku. 2. Typologie Her Každá hra má odlišnou hratelnost. Pro přehlednost se používá dělení do kategorií. Kompletní výčet můžete najít ve článku „Video-herní žánry“ publikovaný na Wikipedii [8]. Pro přiblížení principů UI a její použití pro NPC jsou nejzajímavější následující herní žánry: • arkády, • strategie, • RPG. Pokud obecně hovoříme o arkádových hrách, jsou myšleny takové hry, které mají hratelnost postavenou na odměňování hráče za adekvátní reflexy a schopnost účelně vnímat herní prostředí. Jedná se především o akční hry z prvního pohledu (tzv. FPS, neboli First Person Shooter), akční hry z pohledu třetí osoby (3rd person), hry závodní, letecké simulátory atd. Strategické hry se oproti arkádám nesou v pomalejším tempu s důrazem na bystrost a logiku hráče. Implementace UI je stěžejním prvkem hratelnosti. Hráč pouze zadává jednoduché příkazy, ale elementární chování NPC jednotek zaopatřuje počítač. RPG (Role-Playing Game), neboli hry na hrdiny jsou založené na příběhu a vlastním vyprávění (to mají společné s adventurami, které však neobsahují systém pravidel herního světa). Typický je vývoj postav, celého herního světa a také působení náhody (veškeré dění ovlivňují generátory náhodných čísel). 3. Non-Player Character Podle článku na Wikipedii [7] je „NPC, neboli „Non Player Character“ (dále jen NPC) reprezentací jakékoliv živoucí herní entity, která není ovládána hráčem.“ Existují v herním virtuálním světě a představují iluzi určité inteligence. Všechna NPC obsahují konkrétní naprogramování (statické, nebo implementaci botů), které zajišťuje odpovídající reakce na podněty (podobně jako čistě reaktivní agent). Při použití softwarových botů je možno dosáhnout komplexnější autonomie. Další článek [4] nahlíží na NPC jako na „specifické expertní systémy, v rozsahu od elementárních, až po skutečně obsáhlé.“ V klasických FPS hrách představují oponenty/spoluhráče a je u nich kladen důraz na používání schopností, zbraní, dostupných předmětů, path-finding, reflexní chování a aktuální uvažování obecně. V těchto případech se již pro tyto entity zažilo označení "boti". Bot je však mechanismus interního programování, který NPC řídí. Na rozdíl od arkádových her jsou v RPG hrách používány NPC v mnohem širším měřítku. Zastupují veškeré bytosti herního světa, počínaje enviromentálními NPC bez širšího vlivu, až po dějové NPC. U těchto NPC je kladen největší důraz na věrohodnost entity: tedy jak dobře dokáže zahrát určenou roli.
Speciální kategorií NPC jsou UI pro strategické hry. Ty musí zajišťovat souhru všech jednotek na herní mapě včetně logistiky a path-finding. Stěžejním prvkem je spočítání adekvátní strategie vzhledem k probíhajícímu dění ale také s ohledem na budoucí možný vývoj situace. Důležitá je tedy kooperace, ovládání prostředků a hlavně racionální, logické uvažování. 4. Softwarový bot Používá se pro každou entitu video-herních NPC, která mají vykazovat známky autonomního chování. Zaopatřují zpracování vstupních informací dle kognitivní reprezentace světa a následné vyhodnocení a provedení adekvátní reakce. Na rozdíl od klasických agentů UI (kteří jsou optimalizovaní na nejvyšší možnou efektivitu) se schopnosti botů omezují tak, aby se přiblížili jednání lidského hráče. Vzhledem ke strojové povaze není problém sestrojit bota s nadlidskou přesností. S takovým botem by se však nedalo soupeřit a pro to herní boti podléhají určitým omezením. 5. Statický softbot Podle článku „Computer game bot“ [4] jsou činnosti statického softbota předdefinované a dokáže pracovat pouze v deterministickém prostředí. Tyto prostředí jsou konkrétní herní mapy. Pro každou mapu musí mít bot definovanou soustavu waypointů: tedy bodů na mapě, ke kterým se vážou algoritmy a předem definované rutiny (skripty). U tohoto typu softbotů jsou mechanismy strojového učení a získávání poznatků omezené jen na úzkou oblast vlastního rozhodování. Nevýhoda těchto botů spočívá v tom, že jejich chování je předvídatelné (obzvláště patrné bez zásahu hráče) a ve znovu opakované situaci takřka identické. Pouze v případě, že program statického bota obsahuje širokou škálu různorodých reakcí, tak se tato předvídatelnost ztrácí. Typickým příkladem pro jejich použití jsou arkádová multiplayerová klání jako Quake 3 Arena (tato hra posloužila jako příklad principu implementace UI pro jednotlivá NPC.), Unreal tournament, Counter-Strike apod. 5.1. Historie Statických Softbotů Vývoj statických botů začal se zavedením FPS žánru a her, jako byl Wolfenstein 3D, legendární DOOM, Duke-Nukem 3D, apod. Všechny tyto hry využívaly pro NPC oponenty velice jednoduché skripty, které operovaly jen s minimálním množstvím FSM modelů (viz Níže). Velký zlom nastal v roce 1998 s příchodem hry Unreal a technologie Unreal Engine (jehož nové verze se používají dodnes a jsou základem spousty počítačových her), ve které se začalo používat instancí statických botů pro každé NPC zvlášť. Boti byli doplněni o systém waypointů (bodů cesty) a také o modely pro kooperaci mezi více NPC. To bylo umožněno díky integraci vyšší UI, která řídila základní vrstvy chování botů a umožnila jejich vzájemnou kooperaci v rámci skupiny a dále konkrétní a definovatelné chování jednotlivých skupin.
Později, v témže roce (1998), byla také vydaná hra Half-Life, ve které stojí za pozornost její modularita. Hra obsahovala možnost instalace dalších modulů, které používaly původní herní engine bez návaznosti na originální obsah. Začaly tak vznikat zcela nové herní módy a vznikla široká komunita hráčů, vývojářů a programátorů, kteří vytvořili spoustu rozsáhlých projektů. Z ohledu na vývoj UI a softbotů byl klíčový mód Counter-Strike. Původně neobsahoval žádnou implementaci UI, což bylo impulzem pro vývojáře. Vznikla spousta doplňkových programů pro podporu botů (nejznámější: PODBot). Zajímavé je, že přes značné stáří hry vývoj pokračuje dodnes. Komunita sídlí na serveru Bots-United.com [3] a dají se zde dohledat zajímavé informace o vývoji. 6. Dynamický softbot Tito softboti si dokáží vytvořit vlastní systém waypointů. Vytvářejí si kognitivní model tím, že procházejí herní prostředí. Také počítají s možností změny okolností a s aktuálností získaných informací. Vyvozené závěry pak ovlivňují chování bota. V případě kooperace těchto softbotů je lépe ošetřeno předávání informací, jejich zpracování, následné usuzování a rozhodování. 7. Principy funkce Softbotů Jak je uvedeno výše, použití a implementace UI se liší podle typu hry. Dále si ukážeme základní funkčnost softbotů pro použití v akčních hrách. Tito softboti dokáží simulovat přirozené lidské reflexy, reakční logiku a dokáží využívat herních mechanismů obdobně jako hráč. Bot stejně jako člověk dokáže vnímat prostředí kolem sebe a v návaznosti na to jednat. Na rozdíl od člověka však bot vnímá jen pomocí systému pro reprezentaci vjemů získaných z virtuálního prostředí. Dle aktuální situace je pak odvozováno následné chování bota, které je určeno naprogramováním a v případě dynamických softbotů také znalostní databází, která se postupem existence bota rozšiřuje a usnadňuje tak vlastní rozhodování. Všechny tyto principy a vzory chování jsou aplikované pomocí jednotlivých modulů, ze kterých je sestavena vlastní architektura softbota. Každý tento modul odpovídá za řešení určité situace a používá k tomu příslušné aritmeticko-logické operace. Pro váhové rozhodování se využívá fuzzy logiky (v jednodušších případech) a také neuronových sítí, které dokáží řešit složitější problémy, jako jsou různý puzzly apod. Řeší se tak hlavní problémy jako je navigace bota (realizovaná modulem pro path-finding) výběr předmětu, schopnosti a načasování vlastní akce. 7.1. Path-finding Je základní operací, které musí být bot schopný a slouží k vyhledání optimální cesty skrz herní prostředí. Jednotlivé úseky, zóny, křižovatky, klíčová místa a výhodné pozice jsou označeny soustavou bodů (waypointů) a pomocí výpočtu je zvolena nejoptimálnější trasa ke zvolenému cíli. Momentální cíl je určen dle váhových proměnných. Pokud se váha dosavadního cíle během cesty změní, je také přepočítána nová cesta a bot se vydá za novým cílem.
Pro vypočítání optimální trasy se většinou používají heuristické algoritmy, v případě Quake 3 Arena botů konkrétně Floyd-Warshallův, Dijkstra a A* algoritmus. Ukázalo se však, že už samotné rozmisťování waypointů je problematickou záležitostí a je s ním potřeba počítat při prvotním návrhu úrovní. To je obzvlášť důležité, pokud jsou používáni ryze statičtí boti. Ti se totiž řídí pouze předem definovanou strukturou waypointů. Dynamičtí boti si vytváří waypointy vlastní, ale i tak je potřeba úroveň vhodně navrhnout, aby toto bylo vůbec možné. Na obrázku č. 1 je vidět jednoduchá síť pro průchod bludištěm. Waypointy musí být na všech klíčových místech, jako jsou rohy, křižovatky a cílové oblasti, jinak by bot nebyl schopen bludištěm vůbec projít a pravděpodobně by se „zasekl“ na první zatáčce bez příslušného waypointu.
Obr.1: Struktura waypointů pro průchod bludištěm (zdroj [2])
Pro komplexní herní prostředí nestačí ani podrobná soustava waypointů a je třeba používat techniku pro plánování mezicest. Tato technika se nazývá Routing, a slouží k počítání všech možných cest od bodu 1 k bodu 2. Zahrnuty jsou všechny možné situace, které cestou mohou nastat a jejich optimální řešení. Cesta se určuje dle momentální situace, tedy v závislosti na aktuálním dění. Pokročilejší principy routingu jsou použity kupříkladu při konfrontaci s dalším NPC nebo hráčem a umožňují využívat vlastnosti prostředí pro potřeby NPC.
Obr. 2: Ukázka plánovače cesty pro průchod komplexní mapou (zdroj [2])
Pokud se jedná o dynamického bota, využívá funkčnost routingu i pro vlastní označování waypointů dle momentální váhy konkrétního místa. Přesné postupy pro implementaci takovéto funkčnosti jsou podrobně popsány v tezi botů pro Quake 3 Arena [2]. Na obrázku č. 2, který je z této teze převzat, je vidět grafická ukázka plánovače routingu, kdy je každá část prostoru označena obdélníkovou výsečí, z kterých je nakonec vyselektována optimální cesta. 7.2. Final State Machine Model (FSM Model) Každý bot obsahuje systém pro určení svého stavu. Z těchto stavů se následně odvozuje vlastní chování a reaktivnost bota. Změny stavů jsou řízené rozhodovací logikou pomocí vyšších vrstev UI (viz níže). Každý stav obsahuje různou sestavu rutin a následně ovlivňuje dílčí váhové priority. Počet těchto stavů je konečný.
Obr. 3: Ukázka jednoduchého FSM modelu bota (zdroj [2])
7.3. Rozhodovací moduly Používá se Fuzzy logika, neuronové sítě a genetické algoritmy. Pomocí těchto metod se určují priority bota v ohledu na vstupní proměnné. Tyto prvky zohledňují zpracování paralelně distribuovaných informací a předchozích instancí konkrétního rozhodnutí. Používají se také pro práci s informacemi, které bot zaznamená během vlastní existence a které se dají použít pro efektivnější řešení složitých váhových operací. Celá tato vrstva UI řeší nejednoznačné problémy ovlivněné širokým spektrem vstupních proměnných. 8. Architektura softbotů Bot je soustavou dílčích procesů s různou prioritou, které obstarávají zpracování informací a odpovídající reakce. Jedná se o poměrně složitý víceúrovňový model, který odpovídá implementované rozhodovací logice. Tato architektura je rozdělena na úrovňové vrstvy. Dále bude rozepsána struktura botů použitých ve hře Quake3 Arena. Všechny poznatky jsou přejaté z oficiální Q3A teze [2]. První vrstva slouží pro interakci s prostředím, tedy vnímání herního prostředí a následné akce vykonané botem, je to tedy vlastní I/O rozhraní, podobně, jako skutečný hráč má k dispozici ovládací a audiovizuální zařízení. Smysly bota jsou vytvořeny pomocí „AAS“ systému povědomí o okolí (Area Awareness System), který zaopatřuje bota všemi podstatnými vjemy o
momentálním stavu herního prostředí. Používají se přímo herní data, která jsou abstrahována do použitelné formy. Tyto data následně tvoří kognitivní model. Základní akce jsou dílčí elementy chování bota a jsou obdobou akcí namapovaných na klávesnici a myš. Druhá vrstva obstarává nižší inteligenci, která simuluje podvědomé reakční chování a také určuje dílčí preference bota. Skládá se z fuzzy logiky, báze dílčích cílů, navigace (path-finding, routing) a dodatečných procesních metod. Modul charakter obsahuje prvotní nastavení bota a může se lišit pro každou instanci. Zde je uloženo nastavení preferencí a v podstatě vlastní „osobnost“ softbota (realizováno jako .ini soubor). Tato vrstva také obsahuje komunikační modul, který slouží ke zpracování příkazů pro koordinaci týmu. Třetí vrstva je UI síť, která zajišťuje vyšší inteligenci a také řídící a vyhodnocovací procesy. Jedná se o kombinaci produkčních pravidel (většinou zapsaných jako podmíněné příkazy) a klíčových uzlů (node) určujících reakci v různých situacích dle „stavu mysli“ bota. Principem funkce je velice podobná s Final State Machine a je tedy nejvyšší rozhodovací vrstvou. Obsahuje implementaci vyšší logiky pro samotný souboj, ale také UI pro překonávání možných překážek a řešení puzzlů. Navíc umožňuje práci s externími příkazy. Čtvrtá vrstva je určená pro kooperaci mezi více boty a určenému botovi přidává funkci „team leadera,“ který je pak odpovědný za distribuci příkazů mezi ostatními boty a jejich kooperaci. To je v tomto případě vyřešeno pomocí teamového in-game chatu a textových zpráv, které mohou číst i lidští hráči. Pokud hráč zná klíčové slova tohoto textového protokolu, může sám koordinovat NPC týmové spoluhráče. Je tím zajištěna dodatečná zpětná vazba. Rozvrstvení rozhodovací logiky je záměrné a to pro to, že nižší vrstvy pouze zprostředkují informace vrstvám vyšším a nemusí se zabývat vyhodnocováním. Je tím zvýšena efektivita systému, protože moduly mohou kontinuálně zpracovávat další příchozí informace bez případných „hluchých míst“. Na dalším obrázku je zobrazen informační tok mezi jednotlivými moduly softbota. Všechny datové toky, které míří vzhůru, nesou informace o statusu bota a stavu jeho okolí. Vyšší rozhodovací vrstvy zpracují tyto informace a udržují aktuální informace o herním světě a o tom, „co se vlastně děje.“
Obr. 4: Model komunikace mezi moduly ve víceúrovňové architektuře softbota. (zdroj [2])
9. Implementace a použití Softbotů Pokud hovoříme o botech, hovoříme o v podstatě nezávislých programech, které vnímají hru na podobné úrovni jako samotný hráč. Zajímavé je, že vlastní „myšlení“ botů je vůči hře realizováno asynchronně. Přes to že herní engine zpracovává jednotlivé herní rámy dle výpočetních možností, boti jsou na těchto výpočtech nezávislí a reagují v předem definovaných intervalech (Q3A boti operují na 10hz). 10. Další vývoj NPC Hry, které pro NPC využívají softboty dokážou vytvořit iluzi plného a živoucího světa. Mnoho moderních her má implementaci umělé inteligence na velice dobré úrovni a při hraní máte skutečně pocit, že jste součástí herního světa a NPC jsou skuteční živí tvorové. Bohužel, poslední dobou je na vzestupu tendence hry zpracovat pouze audiovizuálně a až tak se nezabývat vlastním obsahem a funkčností prostředí a vše jednoduše scenáristicky „předskriptovat“. Vznikají tak díla, která sice vypadají úchvatně, ale více než o dynamickou hru se jedná o statický herní zážitek, který neposkytuje žádnou výzvu a ani pocit z dobrého hraní. Díky tomuto trendu upadá i samotná snaha o vývoj dokonalejší a abstraktnější herní UI. V herním průmyslu se již točí ohromné množství peněz, ale vývoj umělé inteligence přes to značně stagnuje. Všechny dnešní hry jsou stále jen kopie dávných herních konceptů, které tu jsou v takřka nezměněné formě od počátku devadesátých let. Skutečně obsáhlé a autonomní NPC se zatím používají jen pro úzkou paletu her (převážně právě FPS). V ostatních hrách jsou implementované jen velice jednoduché modely. Bylo by dobré nasazení softbotů rozšířit do většího počtu her a implementovat funkce, které zajistí větší míru abstraktního uvažování.
Toho by se také dalo mnohem lépe dosáhnout, kdyby dnešní hry obsahovaly podrobnou dokumentaci, otevřený zdrojový kód a také byly ve větší míře editovatelné samotnými hráči. Z historického vývoje je dobře vidět, že nejrozsáhlejší projekty ohledně softbotů byli právě takové, kolem kterých mohla vzniknout komunita nadšených nezávislých vývojářů. Herní společnosti přes to zarputile chrání své „know-how“ a spousta mechanismů, které by se daly snadno vylepšit, podléhají informační bariéře. 11. NPC pracující s přirozeným jazykem Na serveru Gamasutra.com nedávno vyšel článek [5] o integrování jazykového zpracovávání do NPC a použití pro herní dialogy. Takovéto NPC by mohli v určité míře chápat vlastní herní prostředí a bylo by možné vytvářet složitější relace. Taková NPC by měla využití kupříkladu pro RPG a adventury. NPC, které ovládají přirozený jazyk a s kterými můžete přímo komunikovat pomocí vlastních otázek by bylo dalším krokem k pokročilejší UI. Vlastní funkčnost by byla podobná mechanismům, které obsahuje například cleverbot.com. 12. Závěr S rostoucím výpočetním výkonem je již možné simulovat autonomní procesy a používat dynamická herní prostředí. Je však potřeba popularizovat i jiné aspekty her, než jejich audiovizuální zpracování a vytvořit prostor pro tvorbu vyzrálejších děl, které by dokázaly poskytnout mnohem sofistikovanější zážitky doplněné o další spektrum dynamiky virtuálního realismu. Literatura [1] [2]
[3] [4]
SMED, Jouni; KAUKORANTA, Timo; HAKONEN, Harri. Aspects of Networking in Multiplayer Computer Games. N/a. 2001, n/a, s. 8. WAVEREN, J.M.P. van. The Quake III Arena Bot : Thesis. University of Technology Delft Faculty ITS, 2001. 108 s. University of Technology Delft Faculty ITS. Bots United [online]. 2011 [cit. 2011-05-20]. Dostupné z WWW: . En.wikipedia.org [online]. 2011 [cit. 2011-05-20]. Computer_game_bot. Dostupné z WWW: .
[5]
NUTT, Christian. Future of Games: Generating Natural Language For Game Dialogue. Http://www.gamasutra.com [online]. 15. 4. 2011, n/a, [cit. 201105-28]. Dostupný z WWW: .
[6]
En.wikipedia.org [online]. 2011 [cit. 2011-05-20]. Game_artificial_intelligence. Dostupné z WWW: .
[7]
En.wikipedia.org [online]. 2011 [cit. 2011-05-20]. Non-player_character. Dostupné z WWW: .
[8]
Video game genres. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida) : Wikipedia Foundation, 10. 3. 2004, last modified on 30.4.2004 [cit. 2011-05-27]. Dostupné z WWW: .
Stanislav Brandejs Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected]
AGENTOVÝ MODEL DOPRAVY: POROVNÁNÍ KŘIŽOVATKY A KRUHOVÉHO OBJEZDU AGENT-BASED TRAFFIC SIMULATION: ROUNDABOUT COMPARED WITH INTERSECTION Richard Cimler, Kamila Olševičová
Abstrakt V příspěvku představujeme agentové modely fungování dopravy na křižovatce a na zvláštním typu kruhového objezdu. Modely jsou implementovány v prostředí NetLogo a jsou navržen tak, aby pomocí nich bylo možné provést experimenty a ověřit dvě hypotézy, a sice že (a) tok dopravy vedený po kruhovém objezdu je plynulejší, než tok dopravy na světly řízené křižovatce, (b) kombinace dvou kruhových objezdů zrychlí průjezd sanitky danou lokalitou. Klíčová slova Agent, agentový model, NetLogo, simulace, dopravní problém Abstract The objective of the paper is to present the agent-based models that were developed for simulation of the traffic flow in the center of Hradec Králové. Two frequented intersections are planned to be rebuilt into the system of two roundabouts, with the aim to eliminate traffic jams and to enable faster through passage of ambulances going from and to the hospital situated along the intersections. Keywords Agent, agent-based model, NetLogo, simulation, transport, traffic
1. Úvod Prostřednictvím agentových modelů a simulací můžeme zkoumat komplexní systémy a případně i predikovat důsledky zásahů do takových systémů. Jednou z oblastí, v níž lze přístupy založené na agentech úspěšně uplatnit a na kterou se zaměřujeme v tomto příspěvku, je modelování dopravních situací. Představujeme agentové modely fungování dopravy v lokalitě Mileta v Hradci Králové. V současné době se jedná o jednu z nejzatíženějších křižovatek ve městě. Dle výsledků celostátního sčítání dopravy, které byly zveřejněny v květnu 2011, proje-
de po mostě přes Labe (který s křižovatkou těsně sousedí) téměř 30 000 vozidel za den. Vedle křižovatky se navíc nalézá Fakultní nemocnice, takže tudy často projíždějí vozidla záchranné služby. Dopravní provoz není stejně intenzivní ve všech čtyřech směrech. Po hlavním městském okruhu projíždí tranzitní doprava, směr do centra je vytížen relativně více, než výjezd ve směru k nemocnici. Z těchto důvodů je plánováno přebudování dvou světelných křižovatek na systém dvou mimoúrovňových kruhových objezdů (obr. 1).
Obr. 1: Plánovaný systém dvou kruhových objezdů v lokalitě Mileta
2. Modelování situace v prostředí NetLogo Rozhodli jsme vytvořit agentovou simulaci v prostředí NetLogo a použít ji k experimentálnímu porovnání stávajícího řešení dopravní situace v lokalitě Mileta s řešením navrhovaným. Za účelem tohoto srovnání byly navrženy dva modely se stejnými vlivnými parametry (hustota dopravy, vytíženost jednotlivých směrů, rychlost vozidel apod.). Modely jsou vytvořeny za využití reálných údajů (mj. rozměry křižovatky, rozdělení jízdních pruhů, umístění semaforů a další), resp. v souladu s návrhem nového řešení křižovatky. Jednotlivé vozidlo je reprezentováno agentem, který se pohybuje křižovatkou v souladu s dopravními předpisy a přitom nezávisle na ostatních agentech. Agent reaguje na nastavení semaforů, popř. na ostatní agenty, pokud dává přednost protijedoucím vozidlům. Parametry agentů vycházejí také z reálných dat (např. velikost agenta je volena v měřítku odpovídajícím rozměrům křižovatky). Každý agent (vozidlo) má definovánu počáteční pozici na některém příjezdu ke křižovatce, počáteční rychlost, maximální rychlost a zrychlení. Výchozí hodnoty parametrů jsou náhodně generovány při vytvoření agenta. Tato variabilita v nastavení parametrů přispívá k podobnosti modelu s modelovanou situací. Pohyb agenta je usměrňován pomocí značek, umístěných v prostředí. Základní chování agenta spočívá v postupném zrychlování až do maximální rychlosti a v pohybu stále stejným směrem. Toto základní chování může přerušit buď jiný
agent (dojde ke zpomalení, aby se zabránilo srážce), nebo značka, nalezená v prostředí. V simulaci kruhového objezdu je použito 5 typů značek: Začátek nájezdu na kruhový objezd – při zjištění této značky agent změní chování: začíná hledat značku „konec nájezdu na kruhový objezd“. Konec nájezdu na kruhový objezd – zde agent zhodnotí, zda je možné najet na kruhový objezd, v kladném případě začne hledat značku „křížení s kruhovým objezdem“. Křížení s kruhovým objezdem – po nalezení této značky agent změní způsob pohybu: namísto rovné jízdy sleduje tvar kruhového objezdu. Výjezd z kruhového objezdu – pokud je tato značka v dohledu agenta a shoduje se s hlavním cílem jízdy (nebo alespoň vede směrem k hlavnímu cíli), agent směřuje k této značce. Po dosažení výjezdu je stanoven nový směr pohybu a agent se navrací k základnímu chování. Před nájezdem na kruhový objezd agent sleduje, zda k místu nájezdu nepřijíždí po objezdu jiný agent a zda tento agent bude objezd opouštět nebo nikoli. Při pohybu po kruhovém objezdu se opět agent řídí základním pravidlem, tedy zjišťuje, zda před ním nejede jiný agent a pokud ano, zpomalí na rychlost agenta před sebou. Opuštění objezdu je řešeno rovněž pomocí značek, představujících směry výjezdů. Obdobně je zaveden systém čtyř značek pro usměrnění pohybu agentů při průjezdu světelnou křižovatkou: Semafor je značka, která nese informaci, zda je možné pokračovat v jízdě a hledat značku „výjezd z křižovatky“. Výjezd z křižovatky je značka, po jejímž přejetí se agent vrací k základnímu chování. Změna pruhu – pokud agent zjistí tuto značku, odpovídajícím způsobem změní směr jízdy a sleduje jiný semafor. Přednost v jízdě – řeší případ, kdy směr jízdy není volný, i když barva semaforu je zelená.
Obr. 2: Model řešení křižovatky pomocí dvou kruhových objezdů Obr. 2 představuje hlavní okno simulace řešení dopravní situace pomocí dvou kruhových objezdů. Mezi nastavitelné parametry patří hustoty dopravy z jednotlivých směrů a vytížení výjezdů. Je zde také možnost vygenerovat zvláštního agentasanitku a simulovat jeho průjezd. V rámci experimentů budou na obou modelech zkoumány stejné dopravní situace, jako je ranní špička nebo víkendový provoz. K simulování hustot dopravy v jednotlivých směrech budou využita data, získaná měřením (počty osobních a nákladních vozidel a jejich obvyklé rychlosti). Smyslem experimentů bude prověření hypotézy o plynulosti dopravy. Druhá hypotéza se týká rychlosti průjezdu sanitky. K experimentu bude použit zvláštní typ agenta s chování odlišným od ostatních agentů v modelu, tj. s absolutní předností jízdy. Sanitka ignoruje semafory a ani se neřídí pravidly přednosti na kruhovém objezdu. Budeme předpokládat, že ostatní řidiči respektují absolutní přednost sanitky a nedělají chyby. Rychlost sanitky je závislá na počtu vozidel v okolí. Ostatní vozidla reagují na průjezd sanitky zastavením. 3. Závěr Představené modely dopravní situace křižovatky Mileta v Hradci Králové a jejího připravovaného řešení pomocí dvou kruhových objezdů jsou navrženy tak, aby bylo možné provádět i další experimenty a měření. Po získání a nastavení potřebných parametrů aut bude možné například zkoumat spotřebu a emise vypuštěné do ovzduší v souvislosti s časem, potřebným na brzdění a zrychlování při průjezdu křižovatkou, resp. objezdem. Logiku modelu křižovatky i kruhového objezdu je možné využit i pro simulaci dopravy v jiných lokalitách, v modelu stačí pouze upravit umístění jednotlivých důle-
žitých míst, jako je vjezd na kruhový objezd, umístění a nastavení semaforů, hustoty dopravy z jednolitých směrů apod. Poděkování Příspěvek vznikl v rámci řešení projektu GAČR č.402/09/0662 – Rozhodovací procesy v autonomních systémech. Ing. Richard Cimler Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected] doc. RNDr. Kamila Olševičová, Ph.D. Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected]
VÍCEKRITERIÁLNÍ ROZHODOVÁNÍ U AUTONOMNÍCH AGENTŮ MULTICRITERIA DECISION MAKING OF AUTONOMOUS AGENTS Nikola Dostálová
Abstrakt Práce se zabývá vícekriteriálním rozhodováním v multiagentových systémech a popisem architektury agentů rozhodujících se na tomto principu. Bude zde uveden stručný přehled souvisejících pojmů a vývoje v této oblasti. Na příkladu budou srovnány dvě metody – PRIAM a ORESTE – v teoretické i praktické rovině. Klíčová slova Autonomní agent, vícekriteriální rozhodování, kriteriální matice, metoda PRIAM, metoda ORESTE. Abstract Text is focused on multicriterial decision-making in multiagent systems and provides description of architecture of agents which use this decision-making method as their control mechanism. Short overview of related terminology and historical development in this field will be presented. Two methods – PRIAM and ORESTE – will be applied to comparison. Keywords Autonomous agent, multicriteria decision making, criterial matrix, PRIAM method, ORESTE method. 1. Úvod V průběhu vývoje lidstva se vyskytly mnohé snahy o vytvoření tzv. umělého člověka, nebo lépe řečeno stroje, který by nejen vypadal jako člověk, ale i se tak choval. S těmito snahami se setkáváme nejen v literatuře, kdy se autoři snaží čtenáři přeložit návrh takového „stroje“, ale i ve vědě, kdy se vědci snaží vytvořit první robotické systémy (viz [1]). Časem se ukázalo, že snaha o vytvoření umělého člověka zatím není na dané úrovni poznání realizovatelná. Tedy, umělé inteligence se nezabývá konstruováním umělého člověka, ale stroje, který umí řešit problémy v daném prostředí. Takový stroj se nazývá agent. Tato práce by měla přiblížit, jaké charakteristické vlastnosti by měl mít agent, aby mohl být označován za agenta autonomního. Dále stručně seznámit s funkčností autonomního agenta a ukázat důležitost schopnosti rozhodování.
V případech, kdy se agent rozhoduje mezi více možnostmi pomocí stanovení určitých kritérií, se toto rozhodování nazývá vícekriteriální. Dále budou uvedeny některé základní pojmy z této oblasti a něco málo z historie vícekriteriálního rozhodování. V poslední části jsou uvedeny dvě vícekriteriální metody – metoda PRIAM, založená na aspiračních úrovních volených uživatelem, a metoda ORESTE, která vyžaduje od uživatele ordinální informaci o kritériích (tzn. jejich uspořádání podle důležitosti). Srovnání není jen teoretické, ale součástí seminární práce je i praktická část, kde jsou principy obou metod ukázány na příkladu.
2. Autonomní agent Dle [3], pod pojmem agent, resp. autonomní agent, rozumíme uzavřený počítačový systém zasazený do nějakého okolí, který je schopen pružně a autonomně působit za účelem plnění daného cíle. Za charakteristické vlastnosti autonomního agenta je považováno (dle[3]): •
autonomnost – schopnost samostatného fungování, řízení svých výkonů a kontrolování svého vnitřního stavu (bez vnějšího zasahování),
•
společenské chování – schopnost interakce s jinými agenty (resp. s člověkem) prostřednictvím jistého komunikačního mechanismu,
•
reaktivita neboli reagování na podněty z okolí,
•
iniciativnost – schopnost cíleného chování vyvíjením vlastní iniciativy, nejen reagování na podněty z okolí.
Na základě těchto vlastností lze charakterizovat hlavní funkce agenta. Jakmile agent identifikuje cíl, řídí „svůj“ úsudek v cyklu: rozpoznávání situace – rozhodování o řešení – výkon řešení. Pro podporu rozhodování mu slouží funkce návrhu řešení a kooperace s jiným agentem (resp. s člověkem). Podrobněji jsou schopnosti agenta popsány na obr. 1.
Obr.1: Schopnosti agenta Dle [3]: „Pro funkci kooperace agenta slouží jeho schopnost komunikovat s okolím (s jinými agenty, resp. s člověkem). Pro podporu rozhodování disponuje schopností navrhovat jednorázová řešení problémů (typicky volání optimalizačních algoritmů), jakož i schopnost vytváření dlouhodobějších plánů řešení problémů. Percepční (senzorickou) funkci agenta zabezpečuje schopnost jednorázově se dotazovat na stav systému nebo spustit „monitor“, který iniciativně a samostatně informuje o jistých situacích. A konečně výkonnou funkci naplňuje buď zahájením akce, která okamžitě změní stav systému anebo spuštěním samostatného procesu, který potom bez dalších vnějších zásahů mění stav systému v jistých časových okamžicích.“ Dále se budeme zabývat samotnou schopností rozhodování. Z [2]:„Jak ale zabezpečíme, aby se agent dokázal rozhodnout, jakou část úkolu bude právě plnit, jaké prostředky na plnění cílů použije a jakým postupem?“. Jestliže je agent nucen se rozhodnout, většinou existují nebo je možné vytvořit určitá kritéria, podle kterých se bude rozhodovat a vybírat z možných variant řešení. Takovému rozhodování se říká vícekriteriální. Agent jej může využívat ve formě zadaných algoritmů vytvořených podle některé z metod vícekriteriálního rozhodování.
3. Historie vícekriteriálního rozhodování Již v nejstarších dochovaných filosofických textech je možné se setkat s potřebou respektování různých a často i protichůdných kritérií při rozhodování. Tento problém vystupuje tím více, čím méně je autorem vnímán dogmatismus či tolerovány ideologie.
Poprvé byl problém vícekriteriálního rozhodování formulován v rámci ekonomie, a to Vilfredem Paretem r. 1896 (odtud vznikl pojem paretovská optimalita nebo paretovská hranice označující druh optimality ve vícekriteriálních úlohách). O rozvoj teorie vícekriteriálního rozhodování významně přispěl i T. Ch. Koopmans. Kolem r. 1960 vzniká tzv. cílové programování, což je disciplína, zabývající se hledáním výrobních programů, vyhovujících současně několika předem zadaným cílům. Po pár letech již vychází první knižní díla se samotnou tématikou vícekriteriálního rozhodování. Této problematice se začíná věnovat i řada vědeckých časopisů a vzniká i časopis, Multi-Criteria Decision Analysis, zabývající se výlučně touto problematikou. Od r. 1972 se o vícekriteriálním rozhodování pravidelně pořádají velké mezinárodní vědecké konference a řada konferencí místního významu. Odborníci pracující v této oblasti jsou sdruženi v mezinárodní organizaci International Society on Multiple Criteria Decision Making.
4. Vícekriteriální rozhodování Rozhodovací úlohy, v nichž se důsledky rozhodnutí posuzují podle více kritérií, budeme nazývat úlohami vícekriteriálního rozhodování. Do této kategorie patří velice různorodé úlohy, a proto není možné předložit jakoukoli univerzální teorii a z ní vyplývající výsledný rozhodující algoritmus, který je vhodný pro všechny typy úloh. Teorii vícekriteriálního rozhodování je tedy nutné uvést klasifikací úloh vícekriteriálního rozhodování. Jedním z nejdůležitějších klasifikačních hledisek je způsob zadání množiny přípustných variant: a) pokud je tato množina zadána ve formě konečného seznamu -> mluvíme o úloze vícekriteriálního hodnocení variant (s tímto úlohami budeme dále pracovat), b) pokud je vymezena souborem podmínek, které rozhodovací alternativy musí splňovat, aby byly přípustné -> mluvíme o úloze vícekriteriálního programování. Dalším klasifikačním hlediskem jsou informace, podle nichž můžeme úlohy vícekriteriálního rozhodování dělit do čtyř skupin (dle [2]): 1. úlohy s informací umožňující skalarizaci optimalizačního kriteria (= s kardinální informací o kritériích) – jde sice o úlohu jednokriteriální, ale je nutno ji zařadit, jelikož je původně formulována jako vícekriteriální a je zde informace umožňující shrnutí více kritérií do jednoho kritéria skalárního. Je zde nutná teorie vícekriteriálního rozhodování a to proto, aby byla objasněna uvedená redukce na skalár a nedošlo k případnému zkreslení či ztrátě původních informací. 2. úlohy bez informace umožňující solarizaci – tyto úlohy jsou jádrem teorie i praxe vícekriteriálního rozhodování. Je zde zaveden pojem
nedominovaného řešení. Většinou je v tomto případě velice obtížné najít jednoznačné “optimální“ řešení, jelikož nedominovaných řešení je obecně velice mnoho a informace, kterou máme k dispozici, neumožňuje mezi nedominovanými řešeními dále rozlišovat. 3. úlohy s informací získaných v průběhu řešení – často je k řešení vícekriteriální úlohy k dispozici nedostatek informací, jelikož ani aplikace, ani uživatel předem nemůžou přesně předpovědět, jaké informace budou potřeba. Proto byly vyvinuty postupy, které během procesu rozhodování umožňují získávání informací od uživatele skrze dotazovací mechanismus. Problémem ovšem je, že uživatel občas nedokáže spolehlivě odpovědět na dotaz počítače a za účelem dostat od počítače řešení úlohy, vkládá do něj řadu domněnek. Výsledkem počítače potom nemůže být zcela optimální řešení. 4. parametrická řešení – jelikož jsou si mnozí uživatelé vědomi toho, že je výsledné řešení závislé na ne vždy spolehlivé počáteční informaci, dávají přednost širšímu náhledu do problematiky před více či méně jednoznačným doporučením k akci. Parametrická řešení jsou tedy zobrazení, která udávají optimální řešení jako funkci vložené informace. Jejich nevýhodou může být nepřehlednost. V úlohách, kde dochází k vícekriteriálnímu rozhodování na základě hodnocení variant, má množina rozhodovacích variant konečný počet prvků. Tuto množinu budeme značit A. Dále je nezbytné určit hodnotící kriteria a metody, kterými zjistíme kvantitativní údaje o hodnotách těchto kriterií pro všechny varianty. Z předešlého, a to z variant a kriterií, můžeme vytvořit tzv. kriteriální matici.
Jak je uvedeno v [2], jestliže není dáno jinak, předpokládá se, že matice je brána jako maximalizační, což znamená, že varianta je tím lepší, čím je hodnota kriteria vyšší. Jestliže je matice minimalizační, není problém její hodnoty přetransformovat na maximalizační – například namísto kritéria „náklady na pořízení“ zavést kriterium „ušetřené náklady na pořízení oproti stanovenému standardu“. Je nutné seznámit s pojmem nedominovaná varianta. Jedná se o variantu, ke které neexistuje varianta lepší, v tom smyslu, že pokud u ní zlepšíme hodnoty některých kritérií, nedojde ke zhoršení kriterií jiných. Přesněji podle definice: Nechť ai ≈ (Yi1, Yi2, …, Yik) a aj ≈ (Yj1, Yj2, …, Yjk) jsou dvě varianty. Jestliže varianta ai dominuje variantu aj, pak ai ≥ aj. Varianta a se nazývá nedominovaná, jestliže v množině rozhodovacích variant A neexistuje varianta, která ji dominuje.
Dle [3]: „Je-li v množině A jediná nedominovaná varianta, je možné ji beze vší pochybnosti označit za optimální variantu. Typickým případem však je, že nedominovaných variant je více. Často se můžeme setkat s případem, že AN = A. Jeli totiž rozhodovací situace jen trochu přehledná a je-li uživatel seznámen s problematikou, podaří se mu dominované varianty předem vyloučit. Je-li v množině AN více variant a je-li nutné doporučit k realizaci pouze variantu jedinou, je nutné aplikovat metody, které vyberou z množiny AN v jistém smyslu reprezentativní variantu. Varianta, která je vybrána jako reprezentant množiny AN se nazývá variantou kompromisní (někdy se mluví o nejlepší kompromisní variantě).
5. Srovnání dvou vícekriteriálních metod 5.1. Metoda PRIAM Pokud uživatel nedodá žádné dodatečné informace o kritériích, je úplným řešením úlohy vícekriteriálního hodnocení variant množina všech nedominovaných variant AN. Ale tato množina nedominovaných variant může být v některých případech velice obsáhlá. Platí, že čím větší počet kritérií je zadán, tím vzniká více nedominovaných variant. Proto je nutné nějakým způsobem získat preference uživatele – např. získat požadovanou aspirační úroveň kritérií, uspořádání kritérií podle důležitosti, zadání vah kritérií apod. Poté je možné zvolit jednu kompromisní variantu (nejlepší možnou variantu). Metoda PRIAM patří mezi metody s informací o aspiračních úrovních kritérií. Jedná se o přístup, který vychází ze znalosti aspiračních hodnot, které by měly varianty alespoň dosahovat při hodnocení podle jednotlivých kritérií, aby byly pro uživatele akceptovatelné. Metoda PRIAM je založena na heuristickém prohledávání množiny a uživatel udává směr, ve kterém prohledávání postupuje. Mluvíme-li o heuristické informaci, jedná se o počet variant, které zůstávají přípustné pro danou aspirační úroveň. Formální přístupy rozhodovací analýzy vytvářejí model rozhodovací situace a řeší tento model pomocí formálních technik. Výsledek je prezentován uživateli. Konkrétněji, k rozhodování dochází u množiny p variant A = a1, a2, a3, .., ap. Hodnoty ki(aj); i = 1, 2, 3,…,p; j = 1, 2, 3,…,k reprezentují hodnotu i-tého kritéria pro j-tou variantu. Nyní navrhne uživatel aspirační úrovně ke každé kriteriální hodnotě: ()
()
()
() = , , … , . ()
Následně, jestliže platí () ≥ , dostáváme akceptovatelné varianty, jejichž počet označíme d. Číslo d je heuristická informace pro změny aspiračních úrovní. Podle [2]: „Jestliže platí :
•
d>1, potom může rozhodovatel změnit aspirační úrovně podle počtu akceptovatelných variant,
•
d=1,
•
d=0, potom neexistuje žádná akceptovatelná varianta a hledá se nejbližší varianta k zadaným aspiračním úrovním řešením úlohy.
∗ ∑
potom je dosažena nedominovaná varianta,
()
=
− () →
aj ∈ A,
Kde ∗ ; i=1, 2, ..,k jsou ideální kriteriální hodnoty. Výsledkem metody PRIAM je cesta aspiračních úrovní a kompromisní varianta.
5.2. Metoda ORESTE Metoda ORESTE se řadí mezi metody s ordinální informací o kritériích. Od uživatele je požadováno kvaziuspořádání kritérií a kvaziuspořádání variant (tzn. že připouštíme stejně důležitá kritéria i stejně důležité varianty). Tato metoda obsahuje dvě části. V první jsou určeny vzdálenosti každé varianty pode každého kritéria od fiktivního počátku (pořadová čísla fiktivní varianty a fiktivního čísla jsou 0). Poté jsou varianty podle určitých pravidel uspořádány. V druhé části dochází k preferenční analýze, kdy pro každou variantu lze provést test na zjištění preference P, indiference I nebo nesrovnalosti N. Celkem se metoda ORESTE skládá z šesti dílčích kroků, z [2]: 1) sestavíme vektor q a matici P. • •
vektor q = ( , , … , ! ), kde qj je pořadí j-tého kritéria, matice P = (pij); i = 1, 2, …p; j = 1, 2, …k, kde pij je pořadí varianty ai podle jtého kritéria,
• v případě indiferentních kritérií jsou brána průměrná pořadová čísla. 2) vytvoříme matici D vzdáleností od fiktivního počátku. •
matice D = (" ); i=1, 2, …p; j=1,2, …k;
•
pro prvky platí " = $
•
obvykle se používá r = 3,
( )%
+
)
(')% %
(,
•
pro měření vzdálenosti od fiktivního počátku je použita tzv. Dujmovičova metrika ([4]]. 3) uspořádáme varianty. •
hodnoty dij seřadíme od nejmenší po největší a ohodnotíme je pořadím,
•
na místo dij napíšeme pořadí (případně průměrné pořadí),
•
vznikne nová matice R = (rij),
•
* = ∑ * ,
pro každou variantu ai spočítáme
• hodnoty ri seřadíme od nejmenší po největší, čímž získáme uspořádání variant. 4) vypočítáme normalizované preferenční intenzity. •
Spočítáme hodnoty tzv. preferenčních intenzit podle: + = ∑-∈.(*ℎ − * ℎ); i,j = 1,2, …p, kde Iij je množina kritérií, pro která je ai preferováno před aj (ajPaj),
•
vznikne matice C = (cij),
•
spočítáme maximální intenzitu + /01 = (2 − 1),
•
normalizovanou preferenční intenzitou rozumíme hodnotu
•
4 vznikne matice Cn = (+ ).
4 + =
56 789 5
,
5) test indiference. 4 + ≤ ;
4 + − +4 ≤ <,
•
musí být splněny následující podmínky:
•
parametr ; volíme tak, aby ; ≤
•
parametr < volíme tak, aby < ≤
•
pokud jsou obě podmínky splněny, řekneme, že varianta ai je indiferentní s aj (ai I aj).
,
( =)
,
( =)
6) test nesrovnatelnosti variant. •
podmínka nesrovnatelnosti říká, že preferenční intenzity jsou příliš velké vzhledem k tomu, jak blízko jsou varianty u sebe, ale nejsou indiferentní,
•
pokud platí
•
parametr τ volíme tak, aby
> 56 > > 56 − 56
≥ ? , pak jsou varianty ai a aj nesrovnatelné (ai N aj), ?≥
−2 4
,
•
pokud předchozí podmínka není splněna, konstatujeme, že varianta ai je preferována před aj (ai P aj). Výsledky preferenční analýzy můžeme zachytit jednak v matici, kdy řádky i sloupce odpovídají variantám (prvky matice potom přinášejí informaci o vzájemném vztahu pro každou dvojici variant), a jednak graficky.
5.3. Srovnání Nyní tyto dvě metody vícekriteriálního rozhodování srovnáme na řešení rozhodovacího problému: Máme vybrat z vybraných studijních oborů na vysokých školách obor, který by nám nejvíce vyhovoval podle námi zadaných kritérií. Vybrali jsme 13 oborů a zadali 7 kriterií: k1) vzdálenost od domova (hodnoty udávány v km). k2) počet přijímaných na vybraný obor.
k3) šance na přijetí na vybraný obor (hodnoty udávány v %; hodnotu dostáváme z údajů o počtu uchazečů a počtu přijímaných na obor, a úspěšnosti u přijímacích zkoušek v uplynulých několika letech). k4) spokojenost a uplatnění absolventů (hodnoty ve škále od 1 (=nízké) do 5 (=vysoké); hodnotu dostáváme z údajů, jak byli studenti spokojeni se studiem, kolik z absolventů dále po ukončení VŠ pokračuje ve stejném oboru, jaké jsou jejich platy atd. k5) úroveň vědecké a výzkumné činnosti školy (hodnoty ve škále od 1 (=nízké) do 5 (=vysoké)). k6) možnosti studia v zahraničí a mezinárodní spolupráce (hodnoty ve škále od 1 (=žádné) do 5 (=mnoho)). k7) možnost bydlení na kolejích (hodnoty 1 (jestliže ne) nebo 2 (jestliže ano)). Sestavíme kriteriální matici: Tab. 1: Kriteriální matice zadaného rozhodovacího problému i
k1
k2
k3
k4
k5
k6
k7
1
392
68
80
3
4
5
1
2
230
100
85
5
5
5
2
3
392
35
33
5
5
4
2
4
381
80
48
4
4
3
2
5
155
120
95
2
3
2
1
6
381
35
42
1
2
5
2
7
0
50
76
5
3
4
2
8
230
95
78
3
4
3
2
9
381
12
25
4
5
5
2
10
367
20
47
4
4
5
1
11
230
53
50
3
4
4
2
12
281
70
69
2
1
2
2
13
367
38
56
1
2
1
2
6. Závěr Autonomní agenty se s vývojem nových technologií stále více podobají člověku. Někteří agenti jsou schopni chovat se, reagovat a rozhodovat se stejně jako člověk, ale nikdy toho nebudou schopni sami, bez pomoci člověka. Člověk jim tuto schopnost dává naprogramovanými algoritmy, které sám vytvoří, aby fungovaly v určitých situacích tak jako člověk sám.
Metody vícekriteriálního rozhodování jsou pro člověka užitečné i při řešení běžných rozhodovacích problémů. Usnadňují mu rozhodování a pomáhají v hledání optimálních řešení.
Literatura [1] [2]
Kubík, A.: Inteligentní agenty – Tvorba aplikačního software na bázi multiagentových systémů. Computer Press, Brno, 2004. ISBN 80-252-0323-4. Fiala, P.; Jablonský, J.; Maňas, M.: Vícekriteriální rozhodování. Praha, VŠE, 1994, ISBN 80-7079-748-7.
[3]
Digitální knihovna Univerzity Pardubice: http://dspace.upce.cz. 1.5.2011. (http://dspace.upce.cz/bitstream/10195/32107/1/CL273.pdf)
[4]
http://www.seas.com/downloadUNReg/ISEE.pdf
Nikola Dostálová Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected]
ROBOTICKÁ RUKA – KONSTRUKCE A POUŽITÍ ROBOTIC ARM – CONSTRUCTION AND APPLICATIONS Michal Gregor, Karel Petránek, Martin Burian
Abstrakt Robotické ruce a robotická ramena jsou nedílnou součástí moderních výrobních hal, kde usnadňují obtížnou montáž složitých technických zařízení, snižují chybovost způsobenou lidským faktorem a šetří náklady. Příspěvek se věnuje konstrukci obecné robotické ruky, která je schopna uchopovat a manipulovat s předměty. Rovněž jsou rozebrány možnosti a problémy automatického ovládání ruky. Příspěvek je založen na zkušenostech z praktické konstrukce a softwarového ovládání stavebnice Merkur, Robotická ruka Beta. Klíčová slova robotika, robotická ruka, hardware, Merkur Abstract Robotic arms are a common part of modern assembly halls. They facilitate an often complicated construction of various technical devices, decrease error rate caused by human factors and cut down the manufacturing costs. This article describes a generic robotic arm construction and the options and problems of an automated artificial control. The generic arm is able to grab and manipulate various objects. The article is based on a practical robotic arm construction and software control using a Merkur kit called “Robotic Arm Beta”. Keywords robotics, robotic arm, hardware, Merkur
4. Úvod S rozmachem robotiky v druhé polovině 20. století je úzce spojen vývoj hardwarových zařízení, která mají za úkol napodobit a nahradit části lidského těla. Jednou z nejčastěji napodobovaných částí těla jsou ruce – především díky jejich všestrannému použití při montáži stále složitějších zařízení či manipulaci s těžkými objekty.
V příspěvku je popsána konstrukce robotické ruky s pěti stupni volnosti, která vychází z robotické stavebnice Merkur [1]. Je rozebráno konstrukční řešení ruky a zmíněny technické obtíže při konstrukci ruky ze stavebnice. Druhá část příspěvku se věnuje ovládání ruky pomocí softwaru a možnostmi automatického ovládání pomocí algoritmů umělé inteligence, především počítačového vidění a umělých neuronových sítí. 5. Konstrukce robotické ruky Sestavená robotická ruka je ovládána pomocí šesti krokových servo motorů, které umožňují volný pohyb ruky s pěti stupni volnosti. První motor je umístěn v podstavě ruky a zajišťuje otáčení celého ramene ruky v teoretickém rozsahu 0– 360°. Prakticky je tento rozsah omezen nastavením motoru a kabely, které vedou k ostatním součástem ruky. Druhý motor se nachází nad podstavou a zajišťuje předklon a záklon celého ramene ruky v rozsahu 0–180°. Třetí motor umístěný v lokti umožňuje vertikální pohyb předloktí, běžně v rozsahu 0–90°. Čtvrtý motor ovládá pohyb zápěstí ve vertikálním směru v rozsahu 0–180°. Zbylé dva motory umožňují dlani ruky provádět jemnější motoriku – jeden zajišťuje otáčení dlaně o 180° a druhý slouží k rozevírání a svírání dvou prstů ruky. Vyvážení ruky, aby nedošlo k převracení, je vyřešeno širokou podstavou a vysunutím ovládací desky z podstavy v opačném směru než rameno ruky. Aby byla snížena zátěž na první motor, který nese a otáčí celou ruku, je ruka umístěna na ocelovém kuličkovém ložisku a motor je připojen pomocí ozubených kol. Robotická ruka Merkur neobsahuje kamery ani jiné senzory pro snímání okolí ruky. Aby bylo možné ruku řídit pomocí umělé inteligence, je nutné na ruku připevnit dodatečné senzory. Vhodné umístění pro obrazové senzory je na zápěstí ruky, těsně nad robotickými prsty. Takto umístěný senzor může snímat objekty, které se nacházejí přímo pod rukou, a není tak nutné softwarově řešit synchronizaci obrazu a pohybu ruky. Jako obrazový senzor lze využít některou z běžně dostupných webových kamer.
Obrázek 1: Robotická ruka Merkur. 1., 3., 4., 5., 6., 7. jsou krokové motory ovládající pohyb ruky, 2. – základní deska 6. Konstrukční problémy a jejich řešení Použitá robotická ruka ze stavebnice Merkur obsahuje několik konstrukčních problémů, které omezují funkčnost ruky a možnosti jejího použití. Většina obtíží pochází z faktu, že celá ruka je sestavena z kovových dílů, což v některých případech neúměrně zvyšuje hmotnost a vede k rychlému opotřebení určitých součástek. Nejvíce namáhanou částí je loketní kloub ruky, který musí držet celé kovové předloktí, dlaň a případný nesený náklad. Protože nejčastější poloha předloktí vůči podstavě ruky je okolo 90°, musí být motor v loketním kloubu neustále v tahu, aby vyrovnal působení gravitace. To způsobuje jeho silné zahřívání již po několika desítkách sekund a může vést až k vyhoření motoru. Řešením je uchycení pružiny k podstavě a k předloktí ruky, která ulehčí zátěž loketního motoru. Další silně namáhanou částí je ložisko v podstavě, které drží celou ruku a umožňuje její volné otáčení. Toto ložisko je namáháno nerovnoměrně, protože těžiště horní části ruky je vychýleno mimo střed podstavy. Nerovnoměrná zátěž vede k namáhání vnitřních závitů v ložisku, což může v extrémním případě způsobit jejich stržení a nefunkčnost ložiska. Tomuto problému lze předejít umístěním ruky po vypnutí do takového stavu, kdy je těžiště celého systému umístěno na středu podstavy. 7. Softwarové ovládání robotické ruky Merkur Základní desku robotické ruky je možné propojit s běžným PC a z něj ovládat jednotlivé krokové motory. V případě ruky Merkur se jedná o sériový port COM. Ke stavebnici je přiloženo CD s ovládacím softwarem, který umožňuje změnu pozice motorů a jednoduché nastavování pohybových sekvencí.
Aby bylo možné použít přístupy umělé inteligence k ovládání ruky, je nutné zasílat základní desce ruky signály z vlastního programu, dodávaný ovládací software nepodporuje vlastní programování. V manuálu ke stavebnici není bohužel uvedena specifikace komunikačního protokolu se základní deskou ruky, bylo proto nutné jeho specifikaci získat zpětným inženýrstvím. Protokol pro komunikaci s deskou je uveden v tabulce Tabulka 1. Byte
1
2
3
Význam
Úvodní sekvence
Číslo motoru
Pozice motoru
Možné hodnoty
255 (0xFF)
0 až 5
0 až 255
Tabulka 1: Protokol pro komunikaci se základní deskou robotické ruky Merkur. 8. Robotická ruka a umělá inteligence Pro ovládání ruky lze využít algoritmy z oblasti strojového učení a automatizovat tak některé úkony. Jednou z možných aplikací je třídění objektů v dosahu ruky na dvě různé skupiny. Rozpoznání jednotlivých objektů je úkolem počítačového vidění. Pro rychlé, avšak málo robustní rozpoznání druhu objektu lze využít barevného rozlišení rozpoznávaných objektů. Vstupní obraz kamery je pak rozdělen na oblasti s podobnou barvou pomocí některého ze segmentačních algoritmů, jako je K-Means [8], MeanShift [3] či Watershed Segmentation [9]. Jednotlivé oblasti, které jsou výstupem z těchto algoritmů, lze považovat za objekty k roztřídění. Robustnější metodou pro rozpoznání objektů je využití algoritmů pro detekci podobných oblastí. Tyto algoritmy nevyžadují barevné vstupní snímky, je tak možné ušetřit paměťové a výpočetní prostředky. Mezi tyto algoritmy spadá algoritmus pro detekci objektů Viola-Jones [11], který je velmi rychlý a invariantní vůči změně velikosti objektů. SIFT [5], SURF [2] a MSER [6] jsou algoritmy, které z šablony objektu extrahují významné a unikátní znaky, jež lze použít pro odlišení objektu od ostatních. Výhodou těchto algoritmů je invariance vůči změně velikosti, rotaci a perspektivnímu zkreslení objektů. Aby ruka mohla uchopit objekt, je nutné provést koordinovanou sérii pohybů, která je řízena podle aktuálního pohledu kamery. Tuto úlohu lze zjednodušit, je-li možné získat 3D informaci o okolním prostředí. Toho lze dosáhnout například připevněním hloubkového senzoru ke kameře či přidáním druhé kamery a rekonstrukcí hloubkové informace pomocí některého z algoritmů uvedených v [10]. Samotný proces uchopení objektu lze řídit pomocí umělých neuronových sítí. Pro řízení pohybu stačí použití jednoduchého modelu vícevrstvého perceptronu [7]. Naučení neuronové sítě je možné provést pomocí algoritmu back propagation [7] či metodou učení posilováním [4].
9. Závěr V příspěvku byla představena konstrukce robotické ruky s pěti stupni volnosti – byly popsány jednotlivé konstrukční součásti, identifikovány přetěžované části konstrukce a navržen přístup pro minimalizaci těchto přetížení. Byly popsány praktické zkušenosti se sestavením ruky z prefabrikovaných součástí stavebnice Merkur, Robotická ruka Beta [1] a postup ovládání této stavebnice pomocí vlastního software. Na principiálně jednoduchém příkladu třídění objektů na dvě skupiny byly představeny algoritmy počítačového vidění a umělé inteligence, jež lze využít pro řízení robotické ruky.
Literatura [1] ANON. Robotická ruka - BETA | MERKURTOYS s. r. o. [online]. [Cit. 5.6.2011]. Dostupné z WWW: . [2] BAY, H., TUYTELAARS, T. & GOOL, L. SURF: Speeded Up Robust Features. In A. Leonardis, H. Bischof, & A. Pinz, ed.Computer Vision – ECCV 2006. Berlin, Heidelberg : Springer Berlin Heidelberg, 2006, s 404-417. ISBN 978-3-540-33832-1. [3] COMANICIU, D. & MEER, P. Mean Shift: A Robust Approach Toward Feature Space Analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, vol. 24, no. 5, s 603-619. [4] KORMUSHEV, P., CALINON, S. & CALDWELL, D.G. Robot motor skill coordination with EM-based Reinforcement Learning. In 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. Taipei, 2010, s 3232-3237. [5] LOWE, D.G. Object Recognition from Local Scale-Invariant Features. In Computer Vision, IEEE International Conference on. Los Alamitos, CA, USA : IEEE Computer Society, 1999, s 1150. ISBN 0-7695-0164-8. [6] NISTÉR, D. & STEWÉNIUS, H. Linear Time Maximally Stable Extremal Regions. In D. Forsyth, P. Torr, & A. Zisserman, ed.Computer Vision – ECCV 2008. Berlin, Heidelberg : Springer Berlin Heidelberg, 2008, s 183-196. ISBN 978-3-540-88685-3. [7] PLEBE, A. & GRASSO, G. Localization of spherical fruits for robotic harvesting. Machine Vision and Applications, 2001, vol. 13, no. 2, s 70-79. [8] Ray & Turi. Determination of number of clusters in K-means clustering and application in colour image segmentation. Proceedings of the 4th International Conference on Advances in Pattern Recognition and Digital Techniques (ICAPRDT’99), vol. 99, no. 4. [9] SHAFARENKO, L., PETROU, M. & KITTLER, J. Automatic watershed segmentation of randomly textured color images. IEEE Transactions on Image Processing, 1997, vol. 6, no. 11, s 1530-1544.
[10] SCHARSTEIN, D. & SZELISKI, R. A Taxonomy and Evaluation of Dense TwoFrame Stereo Correspondence Algorithms. International Journal of Computer Vision, 2002, vol. 47, no. 1-3. [11] VIOLA, P. & JONES, M. Robust Real-time Object Detection. INTERNATIONAL JOURNAL OF COMPUTER VISION, 2001. Bc. Michal Gregor Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected] Karel Petránek Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected] Bc. Martin Burian Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected]
TÝMOVÁ KOMUNIKACE A ZÁZNAMNÍK POZNÁMEK Z TERÉNU TEAM COMMUNICATION AND NOTES RECORDING Bc. Kinc Lukáš, Bc. Neuman Jiří
Abstrakt Tato práce pojednává o problematice týmové komunikace, rychlém záznamu informací a sdílení dokumentů. Identifikuje typické problémy a potřeby členů týmu pracujících v různorodých podmínkách, kde může být omezený pracovní prostor či čas. Na tyto problémy se pokouší nalézt dostatečně vhodné řešení. Řešení, které by značnou měrou přispělo k vyšší efektivitě, produktivitě a komfortu při každodenní práci v terénu i mimo něj. Toto řešení se snaží aplikovat vývojem informačního systému, který je v této práci navrhnut a následně také implementován. Systém využívá moderních, ale zároveň široce rozšířených, technologií a možnosti svého využití zvyšuje volnou dostupností zdrojových kódů a podporou implementace uživatelských rozšíření.
Klíčová slova Týmová komunikace, správa dokumentů, mobilní aplikace, vývoj software, informační systémy.
Abstract This work deals with the topic of team communication, instant notes recording and document sharing. It identifies typical problems and needs of team members working under varied conditions where workspace and time can be very limited. It attempts to find a solution good enough to eliminate these problems. The work proposes a solution which highly increases productivity, efficiency and comfort of a worker both outdoors and indoors. This solution is applied in development of a new information system which is designed and implemented as a part of this work. The information system is built upon modern and widely spread technologies. Usability of this system is increased by a free availability of its source codes and support for user interface implementation.
Keywords Team communication, document management, mobile application, software development, information systems.
Úvod V dnešní době je závislost na informačních systémech zřejmá a stále více je nutné řešit otázku mobility. Přístup k informačnímu systému přímo z terénu velkou měrou zefektivňuje práci uživatelů. Pro některé profese či zájmové skupiny je práce v terénu jejich hlavní činností a v terénu tráví většinu svého času. Pro tyto uživatele je velmi důležité, aby mohli k systému přistupovat bez těžkého notebooku, jehož start vyžaduje určitý čas. Tyto problémy zejména nastávají tam, kde je nutný pohyb z místa na místo v krátkém čase, jako je kupříkladu značení tras či vyměřování pozemkových ploch, anebo tam, kde jsou podmínky pro práci nějakým způsobem omezeny, například při výstupu na horskou plošinu. Pro tyto situace je nutné sáhnout ještě po menších zařízeních, jako jsou PDA nebo dnešní mobilní telefony, částečně uzpůsobené pro office-like aplikace. S těmi je možné relativně pohodlně zpracovávat i některé lehce složitější úlohy, jako je vyplnění formulářů, komunikace v kratších zprávách anebo ukládání rychlých poznámek nebo souborů, přístrojem pořízených. Některé z výše zmíněných situací pomáhá řešit náš malý informační systém AirBird Colibri. Ten nabízí prostředí pro týmovou komunikaci, záznamník poznámek včetně poznámek v multimediální podobě, správce dokumentů pořízených v terénu i jinde. Veškeré tyto funkce systém zpřístupňuje přes webové rozhraní a rozhraní mobilního klienta. Tento systém je určen právě pro osoby, které si potřebují zaznamenávat důležité poznámky, informace či myšlenky při pohybu v terénu nebo časové tísni a potřebují data zaznamenat co nejrychleji bez čekání.
Problém týmové komunikace Týmová komunikace je důležitou součástí práce v kolektivu spolupracovníků. Každý pracovní tým se potýká s problémem zvládnutí efektivní komunikace, vhodnou dostupností společných dokumentů nebo například s omezenými zdroji, ze kterých musí načerpat maximum pro svou práci. Jedním z druhů komunikace mohou být i porady v reálném čase, na což mohou být lepší hlasové konferenční aplikace, než diskuze psanou formou. Dalším druhem je naopak stálejší diskuze, která se může týkat například vývoje aktuálních problémů, popřípadě diskuze, která nemusí být řešena v reálném čase anebo u které je vhodné persistentní uložení s rychlou možností vyhledávání. Při práci mají spolupracovníci často potřebu sdílet společné dokumenty a to ať již společně vytvářené, tak výsledky práce jednotlivých členů skupiny. Jako příklad si lze snadno představit různé odborné články, postupy a manuály, směrnice, zákony, reporty, zvukové či obrazové záznamy a další. Řešením pak bývá nějaký společný prostor dostupný po síti anebo přes informační systém, kam mají spolupracovníci přístup. Při práci více lidí na jednom souboru nebo na souvisejících datech je vhodné řešit i logování úprav se záznamem kdo kterou věc v jaký čas upravil a v nejlepším případě umožnit i verzování dat, kdy každá uložená úprava vytvoří další verzi souborů a je možné se vracet i ke starším verzím. Tuto
funkčnost uživatelé ocení především ve chvíli, kdy byla například uložena nějaká nežádaná změna. Systém AirBird Colibri se zaměřuje na podporu stálé a persistentní komunikace v týmu a poskytuje uživatelům službu podobnou klasickým diskusním fórům. Funkčnosti a parametry, které mohou uživatelé systému ocenit, zahrnují možnost vytvoření a udržování více diskusních vláken s různými tématy. Založené téma není již obvykle potřeba dále větvit. Takové větvení má za následek typicky sníženou přehlednost, a to především na mobilních zařízeních, které mívají menší zobrazovací plochu. V rámci komentářů v tématech diskuze je možné ukládat i přílohy, což mohou mít například fotografie anebo pracovní dokumenty v elektronické podobě. Tyto dokumenty jsou spravovány systémem pro správu dokumentů a je tak možné jejich verzování a snadné stažení.
Problém zaznamenávání poznámek v terénu Často se stává, že pracovníci v terénu si potřebují zaznamenat nějaké poznámky či například fotografie při své práci. Někdy se jedná například o akutní situaci nebo myšlenku, která nesmí být zapomenuta a je nutné ji rychle zaznamenat. Médium, na které může být taková důležitá informace zaznamenána, zahrnuje prostý papír, diktafon, ale především i elektronické zařízení, které má dnes každý u sebe. Je jím mobilní telefon. Naše aplikace je schopna poskytnout právě efektivní, přehledné a pohotové rozhraní pro záznam informací s využitím elektroniky. Umožňuje rychlou poznámku s instantním uložením na serveru. Tím se stává ihned dostupnou odkudkoliv. Ve chvíli, kdy se autor vrátí domů, ke svému počítači, může ji dále zpracovávat na výkonnějším systému s větší zobrazovací plochou. Rychlé poznámky mohou být využity i opačně. Pokud si uživatel cokoli poznamená do svých poznámek z pohodlí domova, v terénu se potom stačí připojit na stejný server, ovšem za pomoci mobilního klienta, a k daným poznámkám se dostat během několika sekund.
Problém omezených zdrojů Valná většina pracovních týmů se musí při pořizování softwarových řešení řídit především omezeným rozpočtem. Obzvláště to platí pro různé zájmové skupiny, neziskové organizace nebo vzdělávací instituce. Při řešení unikátních problémů může nastat problém, kdy nelze v rámci daného rozpočtu pořídit nový systém šitý na míru potřebám organizace. Pak může být vhodné zvolit univerzálnější, již dostupné, řešení. Při výběru jsou důležitými kritérii podpora požadovaných funkcí, cena, hardwarové nároky, licenční podmínky a cena na pořízení podpůrného software (OS, databáze,…). Problémy s nevhodně zvoleným systémem se mohou projevit až po nějaké době provozu. Například pokud se organizace rozhodne přejít na nová hardwarová zařízení, naroste počet klientů a výkon se stane nedostatečným nebo poskytované funkce přestanou být dostatečné a je potřeba je rozšířit o nové. Částečným řešením těchto situací může být predikce budoucího
vývoje situace v týmu anebo snaha o nezávislost, tedy pořízení produktů, které je možné provozovat téměř za všech podmínek. Systém Airbird Colibri je vyvíjen jako open source projekt, což umožní komukoli nahlížet do kódu a upravovat jej podle svých potřeb. Systém je zároveň díky tomu nabízen zcela zdarma k nekomerčním i komerčním účelům. Je tedy možné ho bez problémů vyzkoušet a v případě osvědčení jej bez problémů nasadit do provozu. Serverový systém je schopen komunikovat s různými klientskými aplikacemi za pomoci webových služeb, což z něj dělá nezávislým vůči technologii zpracování klientských aplikací. Základním klientem je aplikace vyvíjená nad platformou Java ME. Díky široké rozšířenosti běhového prostředí Javy na mobilní zařízení, by měla tato klientská aplikace bez problémů běžet na všech moderních zařízeních.
Informační systém AirBird Colibri Cílem informačního systému AirBird Colibri je zavézt jednoduchý centralizovaný komunikační kanál pro spolupráci v týmu. Hlavním přínosem systému je umožnění komunikace všech členů týmu (projektového, vědeckého, zájmové skupiny atd.), která je centralizovaná, jednoduchá, efektivní a dostupná i v terénu. Aby bylo možné dostát potřebné úrovně bezpečnosti, poskytuje systém rozhraní pro správu uživatelů. Funkce pro správu uživatelů jsou dostupné přes webové rozhraní a jsou přístupné pouze uživatelům s patřičnými právy. Systém slouží také jako centralizované úložiště relevantních dokumentů. Základní mobilní klientská aplikace je dostupná pro platformu Java ME. Její výhodou je dostupnost na většině moderních mobilních zařízení bez potřeby instalace dodatečných aplikací. Výhodou je také její nezávislost na konkrétní mobilní platformě z hlediska hardware, i z hlediska operačního systému. Předpoklady pro správné fungování aplikace jsou dány pouze jejím charakterem a jsou uvedeny v požadavcích na systém. Díky dostupné integrační vrstvě serverové aplikace AirBird Colibri je možné vytvořit novou aplikaci, která bude se systémem spolupracovat a bude využívat jeho hotové služby. Tyto aplikace mohou být díky integraci přes webové služby implementovány v jakémkoliv moderním jazyce. Jejich složitost se může značně lišit – od jednoduchých aplikací poskytujících pouze optimalizované grafické rozhraní k serverové části až po aplikace, které umožní zpracování, editaci a vytváření dokumentů spravovaných systémem AirBird Colibri. Co systém AirBird Colibri nabízí? Diskuze ve vláknech s možností připojení přílohy k příspěvkům Ukládání rychlých poznámek včetně dat v multimediální podobě Otevřené zdrojové kódy s možností rozšíření funkčnosti Hotovou mobilní aplikaci založenou na technologii Java ME Integraci s exitujícími, nebo nově vyvíjenými systémy Přístup přes webové rozhraní
Spolehlivost, škálovatelnost a vysokou dostupnost díky možnosti nasazení na cluster. Pro koho je systém určen? Pro spolupracující tým lidí, který je často roztroušen v terénu Pro zájmovou skupinu lidí zabývající se sportem v přírodě nebo přírodními vědami Pro tvůrčí osoby, potřebující rychle si zaznamenávat své nápady Jak IS AirBird Colibri funguje v praxi? Představme si skupinu turistů se zájmem o pohoří Krkonoš. Tato skupina ráda diskutuje o svých zážitcích a turistických výletech po všemožných trasách, kde naráží na různé zážitky a krásná místa. Každá navržená trasa a místo v Krkonoších zde mají svou vlastní diskusi plnou názorů, rad a fotografií z těchto míst. Turisté často plánují své trasy na základě této diskuse, avšak na cestě mohou znejistit nebo jim něco zabrání pokračovat v naplánované trase. Najednou musí pečlivě naplánovanou trasu operativně změnit. Díky diskusi k této trase mohou rychle najít alternativní cestu anebo se ujistit, že je vše v pořádku, pokud si nejsou jisti místem. Díky početné skupině osob v tomto týmu je i pravděpodobné, že se potkají na nějakém místě, popřípadě že se právě nachází více osob z tohoto týmu na stejné trase. Systém diskuse jim umožní operativně si naplánovat setkání v nějakém bodě, který domluví doslova za pochodu. Zde se přímo vybízí služba, která by sledovala za pomoci GPS přihlášené uživatele a mohla je upozornit na blízkost kolegy z týmu; tato služba by mohla být obratem rychle implementována do systému na žádost komunity a to jak autory systému, tak i programátory z řad turistické skupiny, díky volně dostupným zdrojovým kódům. Turisté na svých cestách zažívají různé zážitky a navštěvují různá místa v různou dobu. O každém zážitku se dá napsat poutavý příběh, místa se dají vyfotografovat a každá fotka může být nějak unikátní, stačí stejné místo vyfotografovat v jinou hodinu či jiný měsíc v roce. Na cestě však není čas dlouze popisovat své zážitky, ovšem je vhodné psát si poznámky, aby nic nebylo po návratu domů zapomenuto. K tomu tito uživatelé používají naši službu ukládání poznámek. Díky ní si ukládají textové poznámky, fotografie a nahrávky pořízené přímo na cestě. Své poznámky pak mohou v klidu domova utřídit, multimediální záznamy upravit a vše ve strukturované podobě zpřístupnit ostatním uživatelů, a podělit se s nimi tak o své zážitky a zkušenosti.
Typická omezení mobilní platformy a jejich řešení Mobilní platformy disponují typicky značně omezenými zdroji, které je při vývoji aplikačního řešení třeba brát v úvahu. Mezi omezení, se kterými se jak uživatelé, tak vývojáři systému běžně potýkají, patří především omezená konektivita (dostupnost a cena připojení, přenosová rychlost, stabilita připojení,…), méně
výkonný hardware, malá zobrazovací plocha nebo velké rozdíly mezi různými druhy a modely mobilních zařízení. Informační systém AirBird Colibri byl vyvíjen takovým způsobem, aby koncový uživatel systému pocítil daná omezení co nejméně. Omezená konektivita mobilních zařízení patří pravděpodobně mezi největší problémy. IS AirBird se snaží minimalizovat dopad tohoto problému na uživatele použitím hned několika metod. Předně je to kompresí dat přenášených mezi serverem a klientem. Tím lze dosáhnout rychlejšího přenosu dat mezi mobilním zařízením a serverem, ale také úspory financí v případě, kdy uživatel platí za přenesená data. V případě, kdy konektivita není dostupná vůbec, systém lze stále používat v offline režimu. V tomto režimu jsou dostupné pouze funkce zaznamenávání poznámek včetně multimediálních příloh. Jelikož veškerá diskusní vlákna jsou uložena na serveru, přístup k nim není v offline režimu možný. Pro ukládání příloh poznámek ovšem systém vyžaduje dostatek volného místa v souborovém systému mobilního telefonu. Ve chvíli, kdy přejde systém do online režimu, budou veškeré poznámky zaznamenané offline přeneseny na server. Nižší výkonnost hardware řeší systém velmi efektivně použitím architektury klient-server. Díky tomu veškeré zpracování dat, transformace formátů, validace a další aplikační logika probíhá na výkonném serveru. Klient již získá data ve finální podobě a jeho úkolem je již jen vhodnou formou data prezentovat uživateli. S tímto si již hravě poradí jakékoliv moderní mobilní zařízení. Vzhledem k tomu, že systém AirBird Colibri se snaží být dostupný i pro uživatele mobilních telefonů, je grafické uživatelské rozhraní jeho mobilního klienta přizpůsobeno velmi malým rozměrům displejů. Pro zařízení s většími displeji, jako jsou třeba tablety, je vhodnější využít možnosti implementace vlastního klienta. V případě stále konektivity lze také pohodlně přistupovat k systému přes webový prohlížeč. Poslední problém s velkými rozdíly mezi konfigurací a hardware je již částečně překonán zvolenou platformou výchozího mobilního klienta. Klientská aplikace je navíc navržena tak, aby vyžadovala co nejmenší množinu knihoven.
Technologie Server Technologie informačního systému použité na serveru jsou již zčásti dány vývojovou platformou. Serverová část je vyvinuta nad platformou .NET od společnosti Microsoft. Již samotná platforma poskytuje dostatek knihoven pro vývoj aplikací (Unity Framework, Entity Framework, ASP.NET). Kromě knihoven od společnosti Microsoft byl použit také framework pro logování Log4net. Mobilní klient Výchozí mobilní klient je dostupný pro platformu Java ME. Tato technologie umožní provozovat mobilního klienta na téměř všech moderních mobilních zařízení a dokáže nabídnout dostačující prostředí pro práci se systémem.
Návrh Uživatelské role Systém bude pracovat s následujícími rolemi uživatelů: Anonymní uživatel o Má velmi omezená práva, která lze rozšířit registrací, po jejíž přijetí správcem se stane uživatel členem týmu. o Může prohlížet veřejná témata a zprávy a přidávat příspěvky k veřejným tématům. Nemůže však k příspěvkům přikládat dokumenty. Člen týmu o Může prohlížet veškerá témata a zprávy v systému. o Smí vkládat příspěvky k tématům a k těmto příspěvkům přikládat dokumenty. o Může stahovat dokumenty a dokumenty také nahrávat. Vybrané typy dokumentů je možno přímo upravovat. o Má k dispozici soukromé poznámky, které jsou ideální pro zaznamenání aktuálních poznatků z terénu, výzkumu atd. o K poznámkám může přikládat také dokumenty, které je později možné přiložit například také ke zprávě nebo je zpřístupnit ostatním uživatelům přímo. Vedoucí týmu o Může využívat všech funkcí, které má k dispozici člen týmu. o Může do aplikace registrovat vlastní zásuvné moduly, které umožní dále zvýšit produktivitu a efektivitu práce v týmu. Tyto moduly lze následně zpřístupnit vybraným rolím. o Navíc mu systém poskytuje jednoduché rozhraní pro správu všech uživatelů. Toto rozhraní obsahuje funkce pro přidávání, odstraňování a zobrazení uživatelů a dále možnost potvrzování / zamítnutí registrací. Výše uvedený seznam obsahuje pouze výchozí role systému. Díky integrovanému správci uživatelů, rolí a práv je možné seznam rozšířit nebo zcela změnit. Případy užití Create registration Jediným případem užití pro neregistrovaného uživatele je v současné verzi vytvoření registrace. Uživatel vyplní vstupní pole formuláře grafického rozhraní a potvrdí žádost o registraci. Confirm registration Dává vedoucímu týmu možnost potvrzení žádosti o registraci, kterou dříve vyplnil neregistrovaný uživatel prostřednictvím UC Create registration. Veškerá funkčnost je obsažena v tabulce, která zobrazuje všechny žádosti o registraci s připnutými tlačítky pro zamítnutí nebo potvrzení žádosti.
User list Obsahuje seznam všech registrovaných uživatelů, tj. v současné verzi všech členů týmu. Kromě přehledu základních informací o členech týmu neposkytuje žádné další funkčnosti. Notes list Umožňuje členovi týmu evidovat vlastní poznámky, které nejsou veřejné a jsou přístupné pouze jemu. Může tak vkládat poznatky, postřehy či nápady přímo v terénu a zpracovat je později. Každá poznámka může obsahovat textovou část a / nebo přílohu ve formě dokumentu libovolného typu. Člen týmu může zobrazit seznam a detail svých poznámek a poznámky také vytvářet prostřednictvím jednoduchého formuláře se vstupem pro text a přílohu. Topic list Poskytuje členům týmu pohled na seznam řešených, diskutovaných témat. Formou přehledného seznamu poskytuje informace o zakladateli tématu a datech jeho vytvoření a poslední modifikace. Vybráním požadovaného tématu ze seznamu je uživatel přesměrován na Message list. Message list Umožňuje členovi týmu prohlížet si zprávy přiřazené k jednotlivým tématům. Na tyto zprávy může také reagovat zasláním nové zprávy pod svým jménem vyplněním textové pole umístěného pod seznamem zpráv. K zasílané zprávě může připojit také libovolný dokument, který bude zobrazen jako příloha zprávy. V případě, že je ke zprávě připojena příloha, může si ji člen týmu prostřednictvím ikonky sponky stáhnout.
Obr. 1: Use Case model
Datový model Tabulka Tab. 1 shrnuje entity, které informační systém obsahuje. Název
Popis
Topic
obsahuje záznamy o tématech jednotlivých diskuzí. Eviduje především název daného tématu a jeho autora
Message
ukládá zprávy náležící do některého z témat. Ke zprávě je vždy přiřazen její autor a čas vzniku
Note
tabulka obsahující osobní poznámky uživatele. V případě, že poznámka obsahuje také dokument jako přílohu, záznam obsahuje odkaz na přiložený dokument
Document
obsahuje dokumenty vložené do systému buď samostatně anebo jako přílohy k týmovým zprávám a osobním poznámkám
User
tabulka obsahující seznam uživatelů systému. V současné verzi obsahuje především jejich autentizační údaje a jméno
Authentication_Token
tabulka autentizačních tokenů, které byly přiděleny uživateli. Obsahuje historii tokenů za poslední týden
Tab. 1: Popis datového modelu
Pohled na systém Systém je navržen tak, aby usnadňoval komunitě uživatelů jeho snadnou integraci. Z tohoto důvodu jsou jeho hlavní funkce dostupné přes webové služby. Současně zpřístupňuje veškeré své funkce přes webové rozhraní přístupné přímo z webového prohlížeče bez nutnosti další instalace či konfigurace. Spolu se serverovou aplikací je dodáván také mobilní klient napsaný v jazyce Java. Tento klient přistupuje k serverové aplikaci právě přes webové služby. Mobilní klient Architektura mobilního klienta je založena na důkladném oddělení všech vrstev tak, aby byla možnost v případě potřeby vrstvu vyměnit za jinou. Skládá se ze tří základních vrstev, vrstvy pro grafické uživatelské prostředí, vrstvy komunikační se stuby webových služeb a vrstvy integrační oddělující předchozí dvě vrstvy. Grafické prostředí je reprezentované jedním midletem. Tato třída v sobě obsahuje veškeré uživatelské obrazovky a informace o přechodech mezi nimi. Důvodem k jedné třídě je možnost pohodlné editace v grafickém prostředí vývojového IDE; přehlednost komponent je udržována v tomto editoru, nikoli v rozdělení do tříd. Z grafického prostředí jsou volány potřebné metody na fasádách webových služeb. Fasády mají za úkol odstínit uživatelské rozhraní od komunikační vrstvy. Samotné fasády primárně pouze přesměrovávají z midletu na konkrétní stub. Stuby webových služeb jsou generovány vývojovým prostředím na základě wsdl souboru, který definuje danou webovou službu.
Komponenty serveru Funkčnost a zodpovědnost jednotlivých komponent je popsána v tabulce Tab. 2. V případě některých komponent může být funkčnost z důvodu složitosti delegována dále na dílčí komponenty. Toto rozdělení však již není z high-level pohledu důležité. Název
Popis
ExternalFacade
Fasáda, která zajišťuje jednotný přístup k funkcím systému všem externím rozhraním systému, tj. webovým službám i webovému rozhraní.
DocumentManager
Správce dokumentů. Zprostředkovává přístup k dokumentům, jejich verzování a bezpečné ukládání.
DocumentStorage
Úložiště dokumentů. Tato vrstva umožňuje snadno vyměnit úložiště dokumentů (např. databáze, souborový systém, FTP server, …)
MessagingService
Služba zajišťující operace nad diskusními vlákny, zasílání zpráv a jejich správu.
NotesManager
Správce osobních poznámek. Zajišťuje přístup k vlastním poznámkám a operace nad nimi.
SecurityManager
Správce zabezpečení má na starost autentizaci a autorizaci uživatelů, správu práv a uživatelských rolí.
Tab. 2: Popis komponent serveru
Závěr IS AirBird Colibri se snaží vyřešit některé problémy týmové komunikace a zaznamenávání poznámek při práci v terénu. Nabízí multiplatformní, nízkonákladové a snadno dostupné prostředí pro základní potřeby práce v omezených podmínkách a dává možnost k implementaci další funkcionality podle přání konkrétních uživatelů.
Bc. Lukáš Kinc Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e‐mail: [email protected] Bc. Jiří Neuman Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e‐mail: [email protected]
APLIKACE VÍCEKRITERIÁLNÍHO ROZHODOVÁNÍ V MULTIAGENTNÍCH SYSTÉMECH APPLICATION OF MULTI-CRITERIA DECISION-MAKING IN MULTI-AGENT SYSTEMS Nela Klusáčková
Abstrakt Obsah práce je zaměřen na popis a spojení dvou vědních disciplín, konkrétně vícekriteriálního rozhodování s problematikou multiagentních systémů. Obsahuje stručné seznámení s principem, pojmy a podstatou každé ze jmenovaných oblastí a popisuje také příklady, kde se s těmito problematikami setkat jak v běžném životě, tak v oblasti umělé inteligence, za účelem snadného pochopení principu každé z uvedených disciplín. Dále zdůrazňuje výhody, které může sloučení těchto dvou oblastí přinést, jako např. úspora času nebo výběr a současně vykonání optimálního řešení, což vysvětluje a současně prohlubuje motivaci se této problematice hlouběji věnovat. Klíčová slova agent, vícekriteriální, multiagentní systém, vícekriteriální rozhodování Abstract This text is focused on description and combination of two disciplines, specifically multi-criteria decision-making and area of multi-agent systems. This work brings a brief introduction to principle, concepts and fundamental understanding of each of the mentioned areas and also presents demonstrational examples from everyday life situations, both from real and artificial environments allowing easier understanding of combination of both areas. This combined approach brings several advantages, for example time saving or selection and implementation of the optimal solution, which are motivation for further work in this problem area. Keywords agent, multi-criteria, multi-agent system, decision making 1. Úvod Text se zabývá kombinací dvou vědních disciplín, a to vícekriteriálního rozhodování a multiagentních systémů.
Cílem této práce zaměřit se především na možné přínosy kombinace obou přístupů a na to, v jakých případech (popř. jakým způsobem) aplikovat vícekriteriální rozhodování do multiagentních systémů i v praxi. Aby bylo možno si problematiku obou oblastí lépe představit, bude uveden stručný popis jejich základních principů v následující části tohoto příspěvku. 2. Podstata vícekriteriálního rozhodování S vícekriteriálním rozhodováním je možné se setkat v rozmanitých oblastech, ať už se jedná o jakákoliv přijímací řízení, uvedení nového výrobku na trh, výběr auta, ale třeba i v kriminalistických metodách, a sami jej denně aplikujeme. Podstatou vícekriteriálního rozhodování (dále VR) je nalezení optimálního řešení libovolného problému, závislého na daných kritériích, která nabývají určité hodnoty důležitosti. Metody VR poté řeší konflikty mezi vzájemně protichůdnými kritérii, o nichž je možné se dočíst např. v knize Vícekriteriální rozhodování od autorů Doc. RNDr. Ing. Fialy CSc., Ing. Jablonského CSc. a Prof. RNDr. DrSc. Maňase. Problém rozhodování, kritéria, varianty i cíle jsou formulovány v systému zvaném objekt rozhodování, kdy daným problémem se zabývá (a rozhoduje o něm) tzv. subjekt rozhodování, což může být buď jednotlivec, nebo skupina lidí. 2.1. Cíl Cílem rozumíme to, čeho chceme hodnocením variant dosáhnout – tedy co je pro nás optimální, o čem se budeme rozhodovat. Cíle vícekriteriálních úloh mohou být různé a jsou charakterizovány v následujících větách. •
Cílem je nalezení jediného optimálního řešení neboli určení nejlepší varianty z nějakého souboru možností. Zde není vhodné využití nominální informace o preferencích mezi kritérii, jelikož to může vést k výběru několika přípustných řešení. Může se stát, že každá metoda určí za optimální jinou variantu. Takto určené varianty značíme jako „kompromisní“.
•
Cílem je uspořádání variant, kde hledáme jediné optimální řešení a postupně vylučujeme kompromisní varianty, až zbude jediná - optimální.
•
Cílem je klasifikace variant na dobré a špatné, kde rozdělujeme varianty, jak již bylo zmíněno, na dobré a špatné (popř. přípustné, nepřípustné) na základě znalosti aspirační úrovně jednotlivých kritérií.
2.2. Kritéria hodnocení Hodnotící kritéria mohou nabývat různé povahy, od procentuelních či peněžních vyjádření, přes fyzikální a technologicky měřitelné vlastnosti až po kritéria výhradně subjektivní, kam můžeme zahrnout např. krásu nebo zábavu. Díky nim máme možnost posuzovat jednotlivé varianty a jsou nezbytnou součástí cesty k nalezení optimálního řešení. Obecně se uvažuje m kritérií, kde m je celé kladné číslo > 1, tj. m = 1, 2, 3, …, n).
Kritéria můžeme rozdělit buď dle povahy na: •
maximalizační, neboli výnosová, kde jsou preferovány hodnoty vyšší (např. maximalizace zisku) a
•
minimalizační, tedy nákladová, s upřednostňovanými nižšími hodnotami (např. spotřeba materiálu),
nebo dle kvantifikovatelnosti na: •
kvantitativní, umožňující stanovit hodnoty kritérií pro každou variant. Nevýhodou je, že tato kritéria bývají často nesouměřitelná kvůli vyjádření v různých jednotkách a někdy je nutné tuto nesouměřitelnost normalizačně odstranit,
•
kvalitativní kritéria nám dovolují pouze na základě určitého kritéria stanovit buď rovnocennost srovnávaných variant, nebo určit, zda je některá z variant lepší, či horší.
2.3 Varianta Rozhodovací variantou se rozumí nějaký prvek (předmět, služba), který má smysl porovnávat s jiným, popř. více prvky, přicházející v úvahu pro výběr v procesu rozhodování. Obecně se uvažuje n variant, kdy ne je celé kladné číslo > 1. Dle zadání množiny přípustných variant můžeme dělit problémy na: •
úlohy vícekriteriálního hodnocení variant, kdy jsou přípustné pouze explicitně (jasně, přímo) vymezené varianty, a
•
úlohy vícekriteriálního programování, kdy jsou přípustné varianty naopak vymezeny implicitně, soustavou podmínek, kdy jsou všechna kritéria kvantitativního rázu.
2.4 Důsledky Důsledky jsou vyjádřeny hodnotami kritérií a mohou být jednoznačné nebo závisející na stavech světa, které charakterizujeme jako vzájemně se vylučující stavy rozhodovacího systému, které rozhodovatel nekontroluje (popř. nemá možnost kontrolovat). Tyto náhodné faktory okolí považujeme buď za diskrétní náhodné veličiny, které určují stavy světa nebo za fuzzy veličiny (množiny). Více o metodách, stanovení kritérií i řešené příklady je možno nalézt na webové stránce www.scss.sk (přesný odkaz je uveden ve zdrojích). Pokud je subjekt rozhodování jistý, jaké budou důsledky variant a jaký nastane stav světa, hovoříme o rozhodování za jistoty. Pokud je subjekt rozhodování znalý alespoň pravděpodobnostních hodnot, ale současně ne s určitou jistotou, označujeme toto rozhodování jako rozhodování za rizika. Pokud subjekt rozhodování není seznámen ani s pravděpodobnostmi důsledků a vývoje stavu světa, setkáváme se s tzv. rozhodováním za nejistoty.
3. Multiagentní systém Na webovém serveru cs.wikipedia.org je multiagentní systém (dále MAS) definován jako [1]simulované prostředí se síťovým charakterem, v němž dochází k interakci určitých typů aktérů (agentů) mezi sebou a/nebo s prostředím, ve kterém se nacházejí. MAS jsou charakteristické decentralizovaným pojetím, asynchronními výpočty, často i neexistencí centrálního prvku. Agenty nemusí být schopny řešit samostatně univerzální spektrum úloh. V tom případě žádný z agentů není schopen vyřešit daný problém sám, jelikož k tomu buď nemá schopnosti, anebo není schopen zkompletovat veškeré dostupné a potřebné informace. Proto je mezi agenty třeba komunikace a spolupráce. Umělá inteligence v multiagentních systémech vychází z principu emergentní funkcionality, což znamená, že racionální chování agenta může být samovolným impulzem v rámci interakcí s okolním prostředím, dále dekompozice na úrovni úloh, kdy se jedná o to, že je problém rozdělen na menší části v souladu s cíli a reaktivity, neboli zásady, že akce je reakcí na aktuální stav prostředí. Základním podnětem ke vzniku MAS bylo především nalézt účinnější řešení rozsáhlých a složitých úloh. Základním kamenem byl nástup distribuované umělé inteligence, nebo také DAI (Distributed Artificial Intelligence), která spočívá v rozdělení úlohy na konkrétní části, které jsou poté samostatně řešeny. Konkrétně se jedná o přelom 70. a 80. let 20.století, kdy bylo dosaženo výrazných pokroků v rámci expertních systémů, a začaly se využívat sítě typu LAN. Dozvědět se více o DAI je možné např. v knize Distributed Artificial Intelligence : Theory and Praxis od Nicholase M. Avourise, která je dostupná i na internetu v databázi knih books.google.cz . 3.1. Agent Agent je v knize Inteligentní agenty od Aleše Kubíka definován jako [2]entita, zkonstruovaná za účelem kontinuálně a do jisté míry autonomně plnit své cíle v adekvátním prostředí na základě vnímání prostřednictvím senzorů a prováděním akcí prostřednictvím aktuátorů. Agent přitom ovlivňuje podmínky v prostředí tak, aby se přibližoval k plnění cílů. Agenty rozdělujeme na několik typů v závislosti na možnostech chování a uvažování a v následujících řádkách si je stručně představíme. •
Reaktivní agent má nejjednodušší vnitřní strukturu a disponuje pouze vyrovnávací pamětí obsahující záznam stavu agenta. Jeho chování je racionální, když se daný paralelní proces spustí buď vlivem z okolního prostředí, nebo vnitřního stavu agenta, popř. může být spuštěn také kombinací těchto dvou podnětů, ale současně je jeho vnímání omezeno danou množinou impulzů z okolí. Je vhodný pro rychle se měnící prostředí.
•
Deliberativní agent, neboli uvažující agent, se svým chováním již blíží autonomnosti lidí a dokáže jednoduše reprezentovat prostředí i vnitřní stavy. Současně dokáže této reprezentace využít k vytvoření plánu, jak dosáhnout daného cíle. Cíle jsou hodnoceny dle priorit a plány mívají hierarchické
uspořádání. Nevýhoda uvažujícího agenta spočívá v tom, že nemá možnost si svobodně zvolit jak prostředky pro plnění cílů, tak i postupy, jak daného cíle dosáhnout a zároveň tedy nemá možnost zlepšovat svoji funkcionalitu i chování. •
Sociální agent je takový, který komunikuje ve vyšším komunikačním jazyce, kam řadíme např. KQML. Jeho princip je založen na tzv. sociální inteligenci, která spočívá v získávání a udržení co největšího množství informací o ostatních agentech, se kterými přichází do interakcí. Tyto údaje potřebuje znát z důvodu ad hoc povahy interakcí, tedy z důvodu dočasnosti a krátkého trvání koalic a současně mají sociální agenti k dispozici také historii interakcí, jako jsou například jména agentů, negociační strategie, ceny transakcí aj., kterou dokáže později využít k vyhledání pomoci od ostatních agentů ve snaze zmírnit negativní důsledky svého jednání z důvodu omezenosti vlastních dispozic.
•
Hybridní agent kombinuje některé, popř. všechny architektury v jeden celek. Je složen ze dvou hlavních částí – plánovací a reaktivní jednotky. Během akce vytvoří plán, který se posléze začíná uskutečňovat. Každá akce je kontrolována reaktivní jednotkou, která dohlíží na to, zda se daná činnost drží plánu a nedošlo ke změně. Pokud změna v okolí nastane, odešle se plánující jednotce impuls k přehodnocení plánu.
4. Spojení MAS a VR Architektury MAS jsou v nemalé míře inspirovány říší hmyzu. Typickým příkladem je kolonie mravenců, kde je pro optimální život v mraveništi zapotřebí hned několik cílů – např.: •
vybudování samotného mraveniště, tedy nalézt vhodné místo a sbírat vhodný materiál,
•
obstarání potravy, kdy je často potřeba spolupráce při přemístění většího kusu,
•
nalezení vhodné cesty při přesunu potravy, obsahující co nejméně překážek,
•
překonávání menších překážek (např. větev) a vyhýbání se větším a obtížnějším (např. kaluž),
•
místo hledání potravy, tedy kde a jak daleko od mraveniště potravu hledat,
•
rozšiřování kolonie a ochrana vajec,
reakce v případě narušení, popř. zničení stanoviště, kdy je nutné stanovit priority, jako záchrana královny, obnovení mraveniště apod.. K jednomu cíli (resp. optimu) je tedy zapotřebí vykonat řadu menších úkolů, kdy každý jednotlivec disponuje určitými schopnostmi (má ve skupině danou roli) a ke splnění úkolu je nezbytné, aby mezi sebou jedinci (popř. soubory jedinců) komunikovali a kooperovali, i když je v tomto případě kritérií pro rozhodování jen pomálu. Obdobné chování v populaci je možné pozorovat samozřejmě také v jiných společenstvích, jako jsou např. včely apod..
•
4.1. Umělá inteligence V souvislosti s umělou inteligencí je možno zmínit oblast robotického fotbalu. Jedná se o zápas dvou skupin robotů s pravidly podobnými klasickému fotbalu, avšak pozměněnými pro možnosti robotiky. Cíl je zde zřejmý – dostat míč do soupeřovy brány, popř. oblasti, která bránu reprezentuje. Rozhodčím je sice člověk, ale při samotné hře jím nesmí být do hry nijak zasaženo a vše spočívá pouze v uvažování a akci robotů. Ti musí reagovat na pohyb svých protihráčů, uvažovat, zda míč přihrát spoluhráči (popř. vybrat, kterému ze spoluhráčů, kteří jsou v dosahu) nebo rozhodnout, že určitou akci vykoná agent sám, dále se musí taktéž vyhýbat překážkám, jako je např. pohyb kolem protivníka nebo koordinace své rychlosti. Toto úsilí je výchozím bodem pro řešení návazných problémů z oblasti robotiky, autonomních systémů, umělé inteligence a jiných disciplín, kdy samotný vývoj samozřejmě pokračuje a samotným cílem v této oblasti je vytvoření dokonalých humanoidních robotů schopných porazit mistry světa. Více informací o robotickém fotbalu je k dispozici na webové stránce www.fira.net. 4.2. Ekonomie Z oblasti ekonomie je možné si MAS představit např. na trhu s akciemi, kdy agenty jsou v tomto případě účastníci prodávající a nakupující určitý objem aktiv. Aplikace VR by mohla rozhodovat především o tom, zda (popř. kdy) akcie nakoupit či prodat, do jaké komodity investovat a za jakou cenu, apod.. Hlavním cílem je tedy maximalizace výdělku, popř., vzhledem k riziku a dynamičnosti akciového trhu, eliminace bankrotu. Kritéria by v tomto případě mohla být např.: •
vývoj komodity na trhu v časovém intervalu, popř. v několika časových intervalech najednou (za poslední týden, měsíc, rok…), a klasifikace důležitosti růstu/poklesu v posledním týdnu, ale současně zhodnocení, jak si daná komodita na trhu stála v posledním roce a odhadnutí její (ne)stability,
•
aktuální postavení komodity na trhu,
•
aktuální procentuelní nárůst/pokles,
•
procento zájmu o danou komoditu,
•
procento potenciálního využití komodity v budoucnu,
•
znalost stavu ekonomiky,
•
sledování trendů,
•
ovlivnění názorem,
• postavení firmy, obchodující s komoditou, na trhu (popř. více firem) aj.. Kritéria mohou být aplikována buď na jedno konkrétní aktivum, nebo na více aktiv a výsledky poté porovnávány mezi sebou. Vzhledem k širokému spektru kritérií a situací na trhu je nutné, aby v systému fungovalo několik agentů, zaměřujících se na specifické oblasti, tedy: •
agent sledující trendy,
•
agent shromažďující a vyhodnocující informace o situaci na trhu za určité období,
•
agent zabývající se aktuálním stavem ekonomiky,
• agent zpracovávající a vyhodnocující informace. Agenty, zabývající se konkrétní oblastí, posílají shromážděné informace jednotce zpracovávající a vyhodnocující data. Agent, který sleduje trendy, se zabývá aktuální situací na trhu, tedy do jaké komodity investovat, popř. kterou službou se zabývat, aby bylo dosaženo zisku. Jelikož je trh dynamický, je třeba spolupracovat také s entitou, která shromažďuje a uchovává informace o situaci na trhu za minulé období a má tak možnost prověřit míru stability, nebo v závislosti na vzrůstajícím zájmu o danou komoditu, předvídat budoucí vývoj a podpořit, nebo naopak zavrhnout, investici či prodej. Podobný problém řeší také jednotka, zabývající se aktuálním stavem ekonomiky. Neřeší tedy produkt jako takový, ale to, zda bude do něj vůbec investováno a současně musí informace o stavu ekonomiky neustále obnovovat z důvodu objektivity a o daných aktualizacích informovat agenta, zpracovávajícího a vyhodnocujícího informace. Ten na základě dat, shromážděných od ostatních aktérů, vyhodnotí optimální variantu dle zadaného cíle. 4.3. Medicína Vícekriteriální rozhodování v rámci MAS se dá aplikovat také v medicíně. Jako příklad může sloužit systém shromažďující informace o pacientovi a současně vyhodnocující zdravotní stav sestávající z: •
agentů zabývajících se sběrem informací z konkrétní oblasti,
•
agentů shromažďujících a třídících informace,
•
agenta zpracovávajícího data,
•
agenta kontrolujícího zpracované informace a vyhodnocujícího data,
• agenta doplňujícího informace. První zmíněná skupina agentů má za úkol sbírat data o konkrétním pacientovi od lékařů z jednotlivých oborů (praktický lékař, neurologie, alergologie…), jako např.: •
soupis potíží,
•
věk
•
výška/váha,
•
choroby v rodině,
•
podstoupená vyšetření,
•
výsledky vyšetření,
•
diagnózy,
•
léčba,
•
operativní zákroky,
•
trvalé užívání léků,
•
dočasné užívání léků,
•
(ne)užívání omamných látek, cigaret a alkoholu,
•
přecitlivělost na látky (alergie, potíže po užití léku…) atd..
Jednotlivé agenty předají data entitě, která bude veškeré informace shromažďovat a třídit (celkový soupis potíží, léků, diagnóz, ale také vizuální prvky, jako rentgenové snímky, grafy vyšetření EKG apod.) a posílat je další jednotce, jejíž úkolem je přijatá data zpracovávat. Ta předá již zpracované informace agentovi, který je zkontroluje a vyhodnotí (např. stanoví jednu nebo více diagnóz v závislosti na příznacích a potížích pacienta) a současně bude spolupracovat s entitou vyhledávající a doplňující informace, např. z internetu, jako je složení léků, příznaky a průběh chorob aj.. Agent, který vyhodnotí data, poté může určit např. zda smí pacient užívat určité léky, tedy není přecitlivělý na některou z obsažených látek a současně nebude mít potíže v kombinaci s jiným medikamentem, zda je schopen podstoupit operativní zákrok (vzhledem k věku, aktuálnímu zdravotnímu stavu apod.), stanovit jednu konkrétní nebo více potenciálních diagnóz v závislosti na aktuálních potížích či výsledcích vyšetření nebo navrhnout účinnou léčbu, jako je aplikace léků a jakých, rehabilitace nebo operace. 4.5. Vojenství a prozkoumávání vesmírných těles MAS je možné využít také k prohledávání terénu, popř. hledání nejvhodnější cesty, což může být využito např. ve vojenství nebo v prozkoumání povrchu vesmírných těles za pomocí třech druhů agentů: •
agent provádějící kontrolní činnost,
•
agent shromažďující a vyhodnocující informace a
agent prohledávající terén, tedy takový, co sbírá informace a odesílá je agentovi, který informace shromažďuje (tento agent může popř. také sbírat vzorky povrchu). Agent, provádějící kontrolní činnost, by měl dohlédnout především na anomálie v terénu (ve vojenství např. podezření na umístění miny) a odeslat informaci o této odlišnosti agentovi, který má za úkol, kromě shromažďování informací, vyhodnotit data o potenciálním nebezpečí (zda se jedná skutečně o minu nebo kámen, kaluž…) a výsledek poslat interagující jednotce, která se v případě nebezpečí nebo neschopnosti překonání překážky tomuto místu vyhne, čímž může být zabráněno jejímu poškození. V rámci prozkoumávání vesmírného tělesa nemusí být odlišnost nutnou hrozbou, ale naopak impulzem ke sběru vzorku povrchu vhodného k prozkoumání a na základě složení určit, zda na tělese byl či je život, nebo vyhodnotit, zda by bylo možné podmínky pro život vytvořit, v závislosti na vyhodnocených vzorcích, povrchu tělesa a jeho struktuře, okolní teplotě a její proměnlivosti, koncentraci vzduchu, dopadu světla, přítomnosti plynů apod..
•
Ve vojenství je příkladem cíle nalezení nejkratší (nebo také nejméně náročné, kryté…) a současně bezpečné cesty a pro, zde potřebnou, časovou úsporu může být
do terénu aplikováno několik agentů, prohledávajících terén, kteří si mohou vzájemně posílat informace o místech s potenciální hrozbou a poté čekat na zprávu od agenta vyhodnocujícího informace. Cílem ale také může být vymezení bezpečné, popř. kryté, plochy, vhodné k utáboření. 5. VÝHODY SLOUČENÍ VÍCEKRITERIÁLNÍHO ROZHODOVÁNÍ S MAS Hlavní důvody, pro které kombinace obou přístupů představuje přínos: •
Úspora času, kdy v určitých případech může spolupráce většího množství agentů přinést výsledek ve výrazně kratším časovém úseku, než sběr informací a vykonávání akcí solitérního agenta.
•
Ekonomické důvody, kde sice výrobní náklady na jednotku nemusí být malé, ale netřeba opomenout, že multiagentní systém se může skládat pouze ze dvou entit. Např. první jednotka bude vykonávat akce a druhá kontrolní činnost, jejímž hlavním účelem bude zaznamenání nežádoucích impulsů (akcí) a zpětnou reakcí odesláním zprávy první jednotce může zamezit její poruše, jejíž renovace a opětovný sběr informací, popř. vykonávání akcí by mohl znamenat vyšší finanční ztrátu (nejen z materiálního, ale i časového hlediska), než výroba a uvedení do provozu dvou jednotek. Současně může kontrolní agent sbírat a uchovávat data zjištěná první entitou, popř. může být sběr dat samotným účelem. Příkladem může být zkoumání terénu.
•
Vyhledání a popř. vykonání optimálního řešení, což je cílem samotného vícekriteriálního rozhodování a hlavní důvod sloučení s problematikou MAS.
•
Možnost dosažení cíle několika alternativami, jelikož se někdy může stát, že pro nás bude v rámci stejného problému vhodnější určitá varianta, závislá na odlišných omezeních. V závislosti na těchto omezeních je třeba také lehce přizpůsobit chování agentů k dané situaci. I když se teď nebudeme pohybovat přímo v oblasti MAS, může být dobře pochopitelným příkladem volba cesty přes GPS. Naším úkolem bude zvolení trasy Hradec Králové – Brno, kde máme volby nejrychlejší nebo nejkratší trasy. Omezení budou pro nás v závislosti na konkrétní situaci – při malém množství benzínu z úsporných důvodů nekratší cestu, z důvodu časové úspory nejrychlejší.
možnost důležitá zvolíme zase tu
•
Přesnost řešení, díky postupnému shromažďování, vyhodnocování a možnému doplňování informací, které bylo zmíněno v souvislosti s aplikací v oblasti medicíny.
•
Možnost práce i s velkým množstvím dat, díky rozdělení funkcí mezi několik agentů – někteří budou pověřeni sběrem a předáváním informací, kdy má každý jednotlivec na starosti jinou oblast. Předaná data může vyhodnotit rovněž několik agentů z důvodu přesnosti v konkrétní oblasti a eliminaci komplikací z přijímání nadměrného množství dat a zpracované informace poslat dalšímu agentovi, který je vyhodnotí a vybere optimální variantu.
6. Závěr I přesto, že je spojení vícekriteriálního rozhodování s multiagentními systémy teprve v začátcích a není běžně aplikováno v praxi, dosažený a nadále pokračující vývoj v obou disciplínách samostatně, především v oboru multiagentních systémů, slibuje velkou budoucnost především díky široké škále možností aplikace obou oblastí. Vícekriteriální rozhodování a řešení úloh může například výrazně přispět k vývoji robotů díky spojení samotné naprogramované inteligence s logickým uvažováním na bázi výpočtů a schopností komunikace i interakce s jinými entitami, popř. i se samotným člověkem. Zkoumání a spojení obou oborů je tedy do budoucna minimálně zajímavou výzvou. Literatura [1]
Cs.wikipedia.org [online]. 2011. [cit.2011-06-02]. Multiagentní systém. Dostupné z WWW: .
[2]
KUBÍK, Aleš Inteligentní agenty. Vydání první. Brno : Computer Press, 2004.s.12. ISBN 80-251-0323-4. RAMÍK, J, PERZINA, J. Moderní metody hodnocení a rozhodování. Vydání první. Karviná : Slezská Univerzita v Opavě, 2008. ISBN 978-80-7248-497-3.
[3] [4]
KUBÍK, Aleš Inteligentní agenty. Vydání první. Brno : Computer Press, 2004. ISBN 80-251-0323-4.
[5]
Theses.cz [online]. 2009. Vícekriteriální hodnocení variant a její aplikace v praxi. Dostupné z WWW: .
[6]
Advances.uniza.sk [online]. 2011. Možnosti využití multiagentních systému v medicíně. Dostupné z WWW: . Eldar.cz [online]. 2010. Reaktivní multiagentní modely v ekonomii.
[7]
Dostupné z WWW: . [8]
Scss.sk [online]. 2011. Vícekriteriální rozhodování. Dostupné z WWW : .
Nela Klusáčková Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected]
VYUŽITÍ METODY PARTICLE SWARM OPTIMIZATION PŘI VZÁJEMNÉM ZAROVNÁVÁNÍ 2D OBRÁZKŮ APPLICATION OF PARTICLE SWARM OPTIMIZATION IN 2D IMAGE ALIGNMENT Tomáš Machálek
Abstrakt Problematika zarovnávání (registrace) 2D obrazových dat zasahuje do mnoha praktických oblastí, počínaje tvorbou panoramatických fotografií, přes registraci multimodálních medicínských snímků až například po kompresi videa. Tato práce se zabývá nasazením algoritmu Particle Swarm Optimization při hledání optimálních translačních transformací pro dva související obrázky s použitím metod založených na přímém porovnávání jejich obrazových bodů. Ty lze formulovat jako úlohy hledání globálního extrému funkce kvantifikující v závislosti na použité metrice odlišnost překrývajících se oblastí. Klíčová slova Inteligence hejna, optimalizace hejnem částic, stochastická optimalizace, registrace obrazových dat, zarovnávání obrázků Abstract The problem of 2D image alignment has many practical applications starting from panorama image stitching, multi-modal image registration to video compression. This work deals with application of the Particle Swarm Optimization algorithm in finding optimal translation transformations when aligning two related images using methods based on direct pixel data comparison. Such model can be interpreted as a global optimization problem searching optima of some concrete image overlapping evaluation metrics. Keywords Swarm inteligence, Particle Swarm Optimization, stochastic optimization, image registration, image alignment Particle Swarm Optimization (dále jen PSO) je globální stochastická optimalizační metoda publikovaná v roce 1995 J. Kennedym a R. Eberhartem. Její princip je inspirován modely založenými na kooperativním řešení problémů, které lze pozorovat u řady živočišných druhů včetně člověka. Algoritmus PSO je založen
na iterativním vývoji skupiny částic, které se pohybují v n-rozměrném prostoru představujícím definiční obor účelové funkce optimalizačního problému. Částice v každé iteraci korigují svůj směr pohybu v závislosti na vlastním průběžně aktualizovaném nejlepším nalezeném řešení a současně na základě polohy doposud nejlepšího řešení nalezeného okolními částicemi. Okolí v tomto kontextu nechápeme v souvislosti s metrikou definičního oboru funkce, nýbrž jako graf určující komunikační strukturu částic, jehož konkrétní podoba má též vliv na průběh a výsledek hledání. Mezi citované aplikační oblasti algoritmu PSO patří například (viz. [3]): výroba a regulace elektrické energie, design a řízení neuronových sítí, řídící aplikace, robotika, plánování (scheduling), data mining, ekonomické a finanční aplikace. 1. Specifikace problému Tento článek shrnuje výsledky diplomové práce [2], jejímž cílem bylo navrhnout a implementovat konkrétní řešení problému zarovnávání 2D obrázků s využitím algoritmu PSO při omezení na translační transformace, řešení implementovat ve formě, která by umožňovala testovat, parametrizovat či modifikovat předložené algoritmy prostřednictvím skriptovacího jazyka přímo v realizované aplikaci, ověřit korektnost implementace PSO pomocí benchmarkových testů, porovnat výsledky PSO v navrženém řešení s některými dalšími optimalizačními metodami a testovat vliv parametrů PSO na chování algoritmu při řešení popsané úlohy. 2. Algoritmus PSO O hejnu budeme uvažovat jako o uspořádané n-tici, kdy i-té částici v čase t přisoudíme polohu i(t) a rychlost i(t). Budeme-li se odkazovat na k-tou složku vektoru i-té částice, použijeme označení pro složku polohového vektoru resp. pro složku rychlosti. Dále pro každou částici definujeme její okolí . Vyjdeme-li z [1], pak lze klíčový vztah pro výpočet složky vektoru rychlosti v diskrétním časovém okamžiku t formulovat takto:
Rovnice 1: výpočet složky vektoru rychlosti částice Po výpočtu všech složek vektoru
lze již částici aktualizovat polohu:
Rovnice 2: aktualizace polohy částice Interpretace jednotlivých symbolů je následující: je d-tá složka polohového vektoru dosavadního nejlepšího řešení, které i-tá částice sama nalezla, je d-tá složka polohového vektoru dosavadního nejlepšího řešení, které dosáhlo okolí částice, je konstanta pro korekci velikosti rychlosti částice, a jsou v každém kroku náhodně volené hodnoty z intervalu při rovnoměrném rozdělení pravděpodobnosti. Zdůrazněme (viz. [1]), že tyto hodnoty se generují náhodně pro každou složku vektoru zvlášť. 3. Metriky pro vyhodnocení překryvu obrázků Rastrovým obrazem zde rozumíme funkci . Pro kvantifikaci odlišnosti překrývajících se částí zarovnávaných obrazů existuje řada metrik, které se liší výpočetní náročností i použitelností v závislosti na typu porovnávaných obrazových dat. Tato práce se zaměřila na tři často používané metriky – součet absolutních hodnot rozdílů (SAD), normalizovanou vzájemnou korelaci (NCC) a vzájemnou informaci (MI).
Rovnice 3: součet absolutních hodnot rozdílů (SAD)
Rovnice 4: normalizovaná vzájemná korelace (NCC) kde
Rovnice 5: průměrná hodnota jasu pixelu obrázku 1
a
Rovnice 6: průměrná hodnota jasu pixelu obrázku 2
Rovnice 7: Vzájemná informace (MI) kde resp. jsou marginální pravděpodobnosti výskytu pixelu s jasem v obrázku resp. s jasem v obrázku a je pak sdružená pravděpodobnost výskytu pixelu s jasem v obrázku a současně pixelu s jasem v obrázku . 4. Realizované řešení Základní myšlenku testovaného řešení je možno vidět na obrázku 1. Pro oba zarovnávané obrázky jsou nejdříve vytvořeny postupně více a více podvzorkované varianty, a to tak, že v každém kroku je jejich výška a šířka snížena na polovinu. Tyto kroky pro každý obrázek proběhnou tolikrát, aby kratší ze stran žádného obrázku neměla délku menší než 150 pixelů. Hodnota byla zvolena empiricky s ohledem na testovanou sadu dat a rozhodně ji nelze považovat za univerzální. Jak uvádí [5], při nevhodně zvolené míře zmenšení může dojít k přílišnému úbytku detailů a následné ztrátě hledaného optima. Při zmenšování obrázků je z důvodu potlačení vyšších frekvencí v obrazových datech použita konvoluce obrazové funkce s Gaussovou funkcí.
Obr. 1: Princip řešení využívá obrazové pyramidy postupně více a více podvzorkovaných variant původních obrázků. Globální optimalizace probíhá jen na nejmenší variantě a na dalších úrovních se řešení pouze koriguje za použití jednodušších, lokálních metod.
Na nejmenších variantách vstupních obrázků proběhne hledání požadované transformace pomocí vybraných globálních optimalizačních metod a při přechodu na vyšší rozlišení je pak provedena lokální optimalizace na omezené obdélníkové oblasti 11x11 pixelů se středem v optimu nalezeném v úrovni předchozí.
Je též třeba brát v potaz skutečnost, že se zmenšující se plochou překryvu obou obrázků klesá možný počet vzájemně odlišných hodnot jasu pixelů na této společné ploše a hrozí tak nalezení numericky sice optimálního, avšak vizuálně zcela chybného řešení. Implementovaná aplikace tento problém omezuje tak, že do výpočtu metrik popsaných výrazy (3), (4) a (7) doplňuje váhovou funkci, která příliš malé společné plochy penalizuje [5]. Stejně tak byly vhodně nastaveny omezující podmínky pro prohledávaný prostor transformací v závislosti na míře očekávaného překryvu (předpokládáme-li např., že obrázky se mají v ideálním případě zcela překrývat, nemá smysl uvažovat rozsah transformací s extrémy vedoucími na překryvy velikosti v řádu pouhých jednotek procent plochy těchto obrázků). 5. Experimenty V první části byla ověřena implementace PSO v rámci realizované aplikace. Výsledky jsou k dispozici v tabulkách 1 a 2. Hledanou hodnotou účelové funkce byla vždy 0. Informace o použitých benchmarkových funkcích a podrobnostech konfigurace všech testů je možno získat v [1].
funkce Parabola Alpine Rosenbrock Griewank
doba výpočtu Swarmint Jswarm-PSO prům. čas [s] s. odchylka [s] prům. čas [s] s. odchylka [s] 26,60 0,52 13,90 0,57 13,90 0,32 8,80 0,42 12,00 0,47 5,80 1,75 4,20 0,42 5,20 0,42
Tab. 1: výsledky implementované aplikace (označena jako Swarmint) na benchmarkových funkcích z hlediska doby výpočtu ve srovnání s jinou existující implementací PSO
funkce Parabola Alpine Rosenbrock Griewank
nalezené řešení Swarmint Jswarm-PSO hodnota f-ce s. odchylka hodnota f-ce s. odchylka 0,04 0,03 3,02 1,45 0,13 0,16 1,01 0,60 3,00 1,00 75,83 116,17 0,53 0,24 0,71 0,16
Tab. 2: výsledky implementované aplikace (označena jako Swarmint) na benchmarkových funkcích z hlediska kvality řešení (optimum je 0) ve srovnání s jinou existující implementací PSO Další série testů měla porovnat několik optimalizačních algoritmů a metrik pro kvantifikaci překryvu obrázků při řešení úlohy jejich vzájemného zarovnávání. Optimalizace byla realizována metodami
PSO, Nelder-Meadovou metodou pohyblivého simplexu (byla použita hotová implementace z projektu Apache Commons), simulovaným žíháním (implementace podle [4]), metodou hrubé síly. Nelder-Meadův algoritmus se nachází na pomezí mezi lokálními a globálními optimalizačními metodami, avšak předběžné experimenty na testovacích datech ukázaly, že několik opakování z náhodně vybraných bodů definičního oboru účelové funkce je schopno problém řešit v čase a kvalitě srovnatelnými s ostatními vybranými postupy. Pro další měření byl počet těchto opakování empiricky stanoven na 5. Algoritmus PSO byl oproti výrazu (1) implementován v mírně modifikované variantě, která do výpočtu vždy vnáší i informaci o dosavadním nejlepším globálním řešení. Takový přístup lze chápat jako existenci dvou paralelních komunikačních topologií částic, kdy jedna je fixně tvořena úplným grafem, ovšem s tím rozdílem, že řešení sledované v této struktuře uvažuje každou částici jako svého vlastního souseda. Upravený vztah pro výpočet rychlosti vypadá takto:
Rovnice 8: modifikace výpočtu rychlosti částice PSO kde je doposud nejlepší globální řešení a hodnota je generována podle stejných pravidel jako a , avšak obecně z jiného rozsahu hodnot (zde ). Srovnávací testy proběhly na čtyřech dvojicích obrázků, a to všemi kombinacemi uvedených optimalizačních algoritmů a metrik. Kompletní výsledky je možné najít v [2]; zde uvádíme pouze výsledky dvou vybraných dvojic. testovací dvojice č. 1 2
optimum (x, y) (-816, -36) (0, 0)
celkem pixelů 5402727 10077696
Tab. 3: správná řešení zarovnání testovaných dvojic a celkové počty pixelů, které bylo nutno při výpočtu zpracovat Kvalita jednotlivých testovaných variant byla vyhodnocována podle euklidovské vzdálenosti nalezených zarovnání od správných hodnot (viz. tab. 3). Uvedené testované dvojice obrázků vznikly uměle (rozdělení na dvě části, vytvoření vizuálně modifikované varianty originálu) vždy z jednoho obrázku za jasně definovaných podmínek tak, aby bylo možné přesně určit správná zarovnání.
Obr. 2: testovací dvojice č. 1(použito se svolením držitele autorských práv, firmy Intel)
Obr. 3: vzdálenost výsledků jednotlivých optimalizačních metod od správného řešení u dvojice č. 1
Obr. 4: doba výpočtu u jednotlivých optimalizačních metod u dvojice č. 1
Obr. 5: testovací dvojice č. 2
Obr. 6: vzdálenost výsledků jednotlivých optimalizačních metod od správného řešení u dvojice č. 2
Obr. 7: doba výpočtu u jednotlivých optimalizačních metod u dvojice č. 2 Poslední série testů se týkala zkoumání vlivu některých parametrů na chování algoritmu PSO z hlediska řešeného problému. V následujících grafech jsou zaneseny výsledky měření vlivu počtu iterací, parametru a komunikační struktury částic. Tabulka 3 znázorňuje zrychlení aplikace dosažené paralelním zpracováním na více procesorových jádrech.
Obr. 8: vliv počtu iterací na kvalitu řešení (30 částic, bez využití obrazové pyramidy)
Obr. 9: vliv počtu iterací na kvalitu řešení (30 částic, s využitím obrazové pyramidy)
Obr. 10: závislost iterace, ve které bylo nalezeno nejlepší (v rámci daného běhu, nikoliv nutně optimální) řešení na parametru c1
Obr. 11: kvalita řešení v závislosti na parametru c1
Obr. 12: vliv topologie částic na iteraci, ve které došlo k nalezení nejlepšího (v daném běhu, nikoliv nutně optimálního) řešení
čas [s] sm. odch. [s]
Core i7 2600 Core 2 Duo 1 vlákno 4 vlákna faktor zrychlení 1 vlákno 2 vlákna faktor zrychlení 50,15 18,61 2,69 91,01 63,17 1,44 0,14 0,31 0,04 0,46 0,73 0,02
Tab. 3: škálování výkonu při použití vícevláknového výpočtu
6. Závěr Realizovaná aplikace ukázala, že PSO, byť v jedné z nejobecnějších konfigurací, dosahuje výsledků plně srovnatelných s jinými metodami používanými v oblasti zarovnávání 2D obrázků. Zajímavé je zejména srovnání se simulovaným žíháním, jehož výsledky byly téměř ve všech testech horší. Zkoumaný vliv parametrů PSO odpovídal popisu v dostupné literatuře. Z hlediska zkoumaných metrik překryvu obrázků se potvrdilo, že jejich volba je závislá především na typu zpracovávaných dat s tím, že metrika NCC se v tomto směru prezentovala jako nejvíce univerzální, zatímco metriky SAD a vzájemná informace z testů vyšly jako specializovanější vždy pro určitý typ obrazových dat. I zde tedy výsledky odpovídaly dostupným informacím o jejich využitelnosti pro specifické problémy. V dosažení univerzálnosti realizovaného řešení brání zejména nutnost hledat před použitím algoritmu řadu parametrů manuálním testováním cílové sady obrázků. Pokud by se podařilo najít vhodné parametry (zejména u obrazové pyramidy, penalizace malých překryvů obrázků a PSO) automatizovaně, použitelnost celého řešení by se nepochybně zvýšila.
Literatura [1] CLERC, Maurice. Particle Swarm Optimization. ISTE, London, 2006. [2] MACHÁLEK, Tomáš. Využití metody Particle Swarm Optimization při vzájemném zarovnávání 2D obrázků. 2011. 87 s. Diplomová práce na Fakultě informatiky a managementu Univerzity Hradec Králové. Vedoucí diplomové práce doc. RNDr. Kamila Olševičová, PhD. [3] SEDIGHIZADEH, D., MASEHIAN, E. Particle Swarm Optimization Methods, Taxonomy and Applications. International Journal of Computer Theory and Engineering, 1, No. 5, December 2009 1793-8201, 2009. [4] SEGARAN, T. Programming Collective Intelligence. O'Reilly, 2007 [5] SZELISKI, Richard. Computer Vision: Algorithms and Applications. Springer, 2010
Bc. Tomáš Machálek e-mail: [email protected]
NOVÉ VÝZVY STROJOVEJ INTELIGENCIE -
TEORETICKÉ VÝCHODISKÁ Peter Sinčák, Mária Virčíková, Marcel Hric Centrum pre inteligentné technológie, FEI, KKUI, TU Košice Slovensko www.ai-cit.sk Abstrakt Informačné systémy dnes prenikajú do všetkých oblastí technickej aj netechnickej praxe. Dnes bez informatizácie a nasadenia informačných systémov v podstate neexistujú žiadne technológie. Ich úroveň sa neustále zvyšuje s cieľom vytvorenia užívateľsky príjemných systémov, ktoré zvládajú mnohé situácie bez zásahu človeka resp. tak ako by ich riešil človek s určitými vedomosťami zo svojej báze znalostí, ktorá sa neustále zväčšuje. Informačný systém akoby ”dospieval ” a poskytuje pre človeka inteligentnú podporu v jeho práci a rozhodovacích procesoch. Takéto systémy nazývame tzv. učiace sa systémy resp. tzv. systémy so strojovou/umelou inteligenciou alebo tzv. Inteligentné technológie. Nové technológie sú očakávané hlavne v oblasti synergie 4 oblastí a to : nanotechnológií, Informačných technológii , Biotechnológii a Kognitívnych technológií. Kľúčové slova Strojová inteligencia, bio-nano-cogno-info technológie, neurónové siete, fuzzy systémy, evolučné systémy, inkrementálne učenie, distribuovaná umelá inteligencia, výpočtová inteligencia, Agent, multi-agentový systém
1. Úvod Inteligentné systémy sú predmetom výskumu už dlhé obdobie a umelá inteligencia zohráva vo vývoji Inteligentných systémov kľúčovú úlohu. História odboru umelá inteligencia sa datuje k roku 1956, keď sa na seminári v Dartmouthe (MA, USA) vedci dohodli na názve a základnej terminológii tohto odboru. Obdobie v rokoch 1956-1980 bolo poznačené rýchlym rozvojom výpočtovej techniky, ktorá má kľúčový význam pre rozvoj umelej inteligencia, a tým aj inteligentných systémov. Prelomový bol rok 1965 keď prof. Zadeh prišiel s koncepciou fuzzy množín na podporu mnohých predošlých aktivít, ďalej prof. Werbos obhájil svoji PhD prácu v roku 1973 na Harvarde, kde položil základy neurónových sietí a v neposlednej rade prof. Holland a profesori Koza a Goldberg (1975) prišli s evolučnými výpočtami ako prostriedkom pre výkonnú výpočtovú techniku. Pre
prípady, kde nevieme pre evolučný proces definovať funkciu vhodnosti, sa začínajú využívať evolučné interaktívne systémy zosumarizované prof. Takagim v roku 2001. Koalícia týchto troch prostriedkov neuro, fuzzy, evolučných (vrátane interaktívnych) systémov vytvorila oblasť, ktorá sa volá Výpočtová Inteligencia (známa aj ako subsymbolická umelá inteligencia) a je postavená na základoch tzv. spájania zdola hore a biologickej inšpirácii. Kým symbolická umelá inteligencia je založená na formálnej logike a spájania zhora dole. Základnou víziou umelej inteligencie je proces „automatizácie“ rôznych procesov, ktoré robí človek. Takým procesom je aj programovanie a jeho automatizácia. Firma Microsoft v poslednom období výrazne pokročila v tejto oblasti a napomáha aplikácii automatizácie programovania. Produkty Visual Studio 10, Silverlight 4 majú prvky umelej inteligencie a smerujú k výraznej zmene programovacích techník. V neposlednej rade umelá inteligencia preniká aj do zábavného priemyslu, kde Microsoft prichádza s projektom XBOX NATAL 2009 a jeho komerčné spustenie je vyhlásené na rok 2010. Jeho postupné zdokonaľovanie prinesie revolučné zmeny v interakcii človek – stroj. Zaujímavosťou Interaktívnych systémov je aj to, že budú prepájať reálne a virtuálne svety. Príkladom takýchto štandardizovaných platforiem je napr. RTmiddleware pre rôzne robotické platformy vytvorené pod podporou systému CORBA pre možnosť využívania rôznych programovacích jazykov. RTmidleware vznikol v Japonsku v Tsukube, kde sa snažili štandardizovať a zefektívniť vývoj technologického výskumu v oblasti mobilnej robotiky. Vedecký svet vníma nové technológie ako synergiu a následnú konvergenciu 4 časti do jedného konvergentného celku ako naznačuje obrázok 1. Tieto technológie by mali do značnej mieri ovplyvniť kvalitu života.
Obrázok 1 : Najdôležitejšie smery výskumu, ktoré budú mať dopad na kvalitu života ľudí
2. Inteligentné systémy a úloha strojovej inteligencie Definícia inteligentných systémov je nejednotná a vo vedeckom svete veľmi rôznorodá. Prof. Kasabov definoval 3 základné a podstatné vlastnosti inteligentných systémov, a to: učenie, archivácia ukladania znalostí, využívanie znalostí pri riešení problému. Opäť je tu treba potvrdiť, že názory na inteligentný systém má iný napr. expert na inteligentné domy ako expert na umelú inteligenciu. Pojem strojová resp. umelá inteligencia budeme brať ako synonymum aj keď pôvod týchto pojmov je rozdielny. Kľúčovým pojmom v oboch podobných oblastiach je pojem učenia. Učenie je imanentný a dôležitý prvok inteligentného systému. V princípe Inteligentný systém a jeho vývoj sa môže uberať tzv. Darwinovským resp. Lamarckovským prístupom. Kým vývoj biologických systémov sa uberá Darwinovským prístupom, naopak technologické systémy sa vyvíjajú Lamarckovským vývojom, kde ďalšia generácia replikuje znalosti priamo od predošlej generácie, čo nie je možne u Darwinovského prístupu. Veľmi dôležitým fenoménom je Internet a tzv. zosieťované systémy vedúce k určitej emergentnej forme distribuovaných multiagentových systémov. V dnešnej dobe nepotrebujeme vyvinúť stroj, ktorý bude vedieť „všetko“ ale stroj, ktorý možno disponuje s určitým kvantom informácií, ale bude vedieť „všetko“ nájsť aj na Internete. V princípe ide o simuláciu činnosti človeka. Dnes už je dôležité okrem určitého kvanta vedomostí hlavne vedieť, kde informáciu nájsť a hľadať súvislosti a vzájomnosti medzi znalosťami. Ako ciele uvádzaného predmetu štúdia budú prostriedky výpočtovej inteligencie demonštrované na experimentálnych systémoch NAO, AIBO ako aj iných systémoch. Tieto experimentálne systémy sú pre nás iba benchmarkovské prostriedky, kde chceme demonštrovať výhodnosť neuro, fuzzy, evolučných a interaktívnych systémov. Strojová/umelá inteligencia je na rozmedzí medzi IT, kognitívnymi technológiami a biologicky inšpirovanými technológiami. Jej význam je veľmi veľký nakoľko je schopná prinášať reálne riešenia a ekonomický zisk. Aké sú základné terminologické pojmy, ktoré by manažér pri výbere technológii mal poznať? V oblasti strojovej inteligencie je vhodné mať základnú predstavu aspoň o nasledovných prostriedkoch strojovej inteligencie: 2.1. Klasická umelá inteligencia Klasická umelá inteligencia vznikla v roku 1957 na seminári v Dartmouthe v USA, kde sa dohodli na názve odboru umelá inteligencia. Medzi základné prostriedky vtedy ako aj teraz hlavne patria :
riešenie úloh s ohraničením : riešenie úloh, zväčša založené na prehľadávaní, zahŕňa pomerne veľký problémový okruh: plánovanie, uvažovanie, rozvrhovanie, dedukcia, inferencia, dokazovanie teorém apod. Systémy pre riešenie úloh zvyčajne obsahujú tri hlavné komponenty: o databáza, ktorá obsahuje dosahovaný cieľ a súčasný stav riešenia úlohy
o množina operátorov, ktoré sa používajú na manipuláciu s databázou (napr. v šachu to môže byť množina pravidiel pre ťahanie s figúrkami) o stratégia riadenia: rozhoduje, ktorý operátor použiť, kedy a kde Pri dosahovaní stanoveného cieľa sa zvyčajne postupuje dvoma základnými spôsobmi: o priame uvažovanie (dátami riadené systémy): aplikácia operátorov na údajové štruktúry, ktoré reprezentujú aktuálnu situáciu (stav úlohy), kedy je úlohou pretransformovať počiatočnú situáciu na požadovanú cieľovú o spätné uvažovanie (cieľom riadené systémy): aplikácia operátorov na požadovanú cieľovú situáciu, kedy sa cieľ pretransformuje na jeden alebo viac pod cieľov, ktoré je jednoduchšie riešiť a ktorých riešenie je postačujúce pre vyriešenie danej úlohy. Tieto pod ciele sú potom ďalej redukované, až kým nie sú dosiahnuté triviálne úlohy. Existujú samozrejme aj spôsoby využívajúce kombináciu uvedených prístupov. Výsledky tejto oblasti si našli široké uplatnenie napr. v systémoch pre výber a spracovanie informácii (information retrieval), porozumenie prirodzeného jazyka, dokazovanie matematických teorém, ale aj v oblasti robotiky a v expertných systémoch.
expertné systémy: sú programy pre riešenie úloh, ktoré sú natoľko komplexné a špecifické, že ich je schopný uspokojivo riešiť iba špecialista v danom odbore - expert. Expertné systémy sú založené na myšlienke využiť znalosti, prevzaté od človeka, pri riešení relatívne úzko špecializovaného okruhu úloh, vyžadujúcich jeho expertné schopnosti. Pritom sa požaduje, aby riešenie, ktoré produkuje expertný systém, bolo veľmi podobné riešeniu, ku ktorému by v danom prípade dospel expert a aby expertný systém vedel odôvodniť svoje rozhodnutie. Vo všeobecnosti možno expertný systém popísať ako systém zložený z nasledujúcich komponentov: o inferenčný mechanizmus: tvorí jadro expertného systému a s využitím bázy vedomostí po každej odpovedi z bázy údajov upresňuje aktuálny model konkrétneho konzultovaného prípadu a v závislosti od stavu tohto modelu kladie ďalšiu otázku. V dialógu s používateľom je iniciatíva na strane systému a sled otázok nie je pevne naprogramovaný - systém vyberá na základe doterajších odpovedí používateľa vždy najrelevantnejšiu otázku. o báza údajov: je tvorená odpoveďami používateľa, získanými obvykle v priebehu dialógu. V niektorých aplikáciách sa časť bázy údajov získava priamo snímaním údajov z objektu, ktorý je predmetom expertízy.
o vysvetľovací mechanizmus: používateľ má možnosť kedykoľvek prevziať v dialógu iniciatívu a vyžiadať si vysvetlenie "uvažovania" systému (prečo bola položená práve táto otázka, ako dospel systém k niektorému záveru, aký je momentálny stav riešenia konkrétneho problému atď.) o báza vedomostí: vytvára ju znalostný inžinier na základe informácií, získaných od experta a predstavuje formalizované a zakódované vedomosti ľudského špecialistu z danej problémovej oblasti. Expertné systémy si našli široké uplatnenie pri riešení diagnostických, klasifikačných, rozvrhovacích a plánovacích úloh, často sú rozhodovacou súčasťou zložitých riadiacich komplexov. 2.2. Výpočtová inteligencia Výpočtová inteligencia sa začala rozvíjať hlavne v období rozvoja výpočtovej techniky nakoľko nároky na výpočtové kapacity si mimoriadne veľké. Medzi základné prostriedky výpočtovej inteligencie zaraďujeme :
neurónové siete: predstavujú zjednodušený formálny model biologických neurónov a ich sietí. Činnosť neurónových sietí možno rozdeliť do dvoch základných fáz: o fáza učenia, kedy sa do siete ukladajú znalosti modifikáciou synaptických váh (neurónových spojení) o fáza života, kedy sa získané znalosti využívajú v prospech riešenia problému, pre ktorý je sieť určená Podstatnou vlastnosťou neurónových sietí je práve učenie, ktoré možno vo všeobecnosti rozdeliť na dva základné typy: o kontrolované učenie: učenie s učiteľom (supervised learning), kedy ku každej vstupnej učiacej (trénovacej) informácii učiteľ určí príslušnú výstupnú informáciu. Neurónová sieť sa teda snaží rozpoznávať vstupy a zatrieďovať ich tak, ako to bolo povedané učiteľom o nekontrolované učenie: učenie s bez učiteľa (unsupervised learning), kedy možno sieti v procese učenia ponúknuť iba vstupné informácie a samotná sieť určuje výstup. Prakticky ide o spracovanie vstupných informácií podľa určitých zákonitostí.
Aplikovateľnosť neurónových sietí vychádza z ich základných vlastností. Jednou z najvýznamnejších je fakt, že neurónová sieť je univerzálnym aproximátorom funkcie (množstvo problémov je možné preformulovať ako neznáme funkcie so známymi výstupmi, príp. aj vstupmi; neurónovú sieť potom možno chápať ako mnoho parametrický systém, ktorý sa snaží identifikovať funkciu reprezentujúcu riešený problém nastavením a adaptáciou svojich parametrov). Neurónové siete sa efektívne využívajú pri riešenie problémov v oblastiach klasifikácie, riadenia procesov, predikcie, aproximácie, spracovania signálov apod.
fuzzy systémy: sú systémy postavené na báze fuzzy logiky nad tzv. fuzzy množinami a umožňujú "presne narábať s nepresnou informáciou". Fuzzy množina, na rozdiel od klasických množín, ktoré predstavujú presné vymedzenie, nepracuje s ostrým vymedzením. Výrazy patriť/nepatriť do množiny sú reprezentované funkciou príslušnosti, ktorá dáva fuzzy množine flexibilitu v modelovaní bežných tzv. lingvistických výrazov (napr. ak je teplota nízka, izbová, vysoká apod., funkcia príslušnosti pre konkrétnu hodnotu premennej teploty určí, do akej miery je nízka, izbová, vysoká apod. ). Fuzzy systémy vo všeobecnosti pracujú s rôznymi typmi funkcií príslušnosti (trojuholníková, lichobežníková, -funkcia, ...) a používajú špeciálne operácie (rôzne typy T-noriem a T-conoriem) pre prácu s fuzzy množinami. V praxi sa bohato uplatnili kvôli možnosti práce s pravidlami typu if-then, s bázami znalostí a dát, hlavne v podobe fuzzy regulátorov a fuzzy expertných systémov. systémy založené na evolúcii: existuje množstvo rôznych typov prístupov využívajúcich evolúciu, preto v nasledujúcom texte sa kvôli jednoduchosti budú uvedené typy označovať termínom evolučné algoritmy. Evolučné algoritmy teda patria medzi prehľadávacie algoritmy, ktoré n-bodovo prehľadávajú priestor riešení za účelom nájdenia jedného, resp. viacerých riešení, využívajúc tzv. populáciu riešení (n bodov, s ktorých každý predstavuje riešenie). Jedno riešenie je reprezentované jedným jedincom v populácii a sú na neho kladené dve základné požiadavky: o riešenie evolučného algoritmu – jedinec – musí pozostávať zo zložiek: každý jedinec reprezentuje jedno riešenie problému pomocou genetického kódu, ktorý predstavuje parametre riešenia a ich konkrétne hodnoty druhou požiadavkou je potreba určovania kvality každého riešenia, čo sa vykonáva v každom cykle riešenia úlohy, teda v každej generácii evolučného procesu. V každej generácii evolučného algoritmu sa aplikujú na jednotlivých jedincov tzv. genetické operátory (rôzne typy mutácie a kríženia; mutácia: zmena jedného parametra genetického kódu; kríženie: výmena celých častí genetického kódu), ktoré spôsobia zmenu jednotlivých riešení a zároveň zmenu ich kvality. Pomocou tzv. selekčného mechanizmu sa vyberie n najlepších riešení, ktoré postupujú do nasledujúcej generácie.
Prechod od starej množiny bodov v prehľadávanom priestore sa deje pseudonáhodne, náhodnosť nie je ponechaná "bez dozoru". Kopírujúc evolučný princíp v prírode, náhodné zmeny (zväčša malé), ktoré vykazujú "dobrý vplyv" na riešenie ostávajú, iné horšie zanikajú. Trvalé pôsobenie prirodzeného výberu a výberu odchýlok spôsobuje existenciu evolučného tlaku a umožňuje nájdenie najlepšieho, prípadne viacerých vyhovujúcich riešení. Systémy založené na evolúcii majú široké uplatnenie hlavne v oblasti optimalizačných úloh.
systémy na báze umelého života: umelý život možno definovať ako všeobecnú metódu, ktorej podstatou je generovať z chovania jednoduchých mikroskopických spolupracujúcich prvkov také chovanie na makroskopickej úrovni, ktoré je možné interpretovať ako prejav života. Umelý život prakticky poskytuje možnosť využitia širokej škály evolučných teórií, prípadne ich kombinácií pri simulácii zložitých systémov. Virtuálne prostredie simulačných prostriedkov umelého života umožňuje na základe experimentov sledovať dlhý proces evolúcie za veľmi krátky čas. Aplikácie systémov na báze umelého života využíva na riešenie simulačných a predikčných úloh množstvo disciplín, napr. biológia, ekológia, antropológia, ekonómia, geografia, ale aj priemysel.
2.3. Distribuovaná umelá inteligencia Na základe rýchleho vývoja v oblasti strojovej inteligencie sa javí byť dôležitým delenie systémov na základe stupňa centralizácie, resp. decentralizácie, s čím súvisí aj vznik distribuovanej umelej inteligencie. Táto tvorí prienik medzi distribuovanými výpočtami a umelou inteligenciou. Distribuované výpočty existujú tak dlho, ako je možné rozdeliť riešenie jedného výpočtového problému na viacero procesorov, pričom hlavnou úlohou bolo riešenie paralelizácie a synchronizácie týchto výpočtov. Distribuovaná umelá inteligencia vznikla aplikáciou distribuovaných výpočtov v prostriedkoch umelej inteligencie. Na rozdiel od distribuovaných výpočtov bola distribuovaná umelá inteligencia zameraná na riešenie problémov, koordináciu a komunikáciu oproti nízkoúrovňovej paralelizácii a synchronizácii. Rozvoj v oblasti manažmentu informácií spôsobil rozdelenie distribuovanej umelej inteligencie na paralelnú umelú inteligenciu, distribuované expertné systémy, neskôr distribuované bázy znalostí, distribuované riešenie problémov apod. V súčasnosti sa však najčastejšie možno stretnúť s delením distribuovanej umelej inteligencie na dve triedy:
distribuované riešenie problémov: súvisí s manažmentom informácií, dekompozíciou a distribuovaním úloh a/alebo syntézou riešení (v tomto type systémov sa kladú pomerne vysoké nároky na kompatibilitu jednotlivých riešiacich entít, ktorým sa čiastkové úlohy distribuujú)
multiagentové systémy: súvisia s koordináciou a manažmentom správania, v súvislosti s týmto typom systémov vzniká potreba zavedenia nového pojmu: agent, ktorý možno vo všeobecnosti popísať ako autonómnu inteligentnú riešiacu jednotku systému. Na rozdiel od systémov distribuovaného riešenia úloh, v multiagentových systémoch nie sú kladené vysoké požiadavky na jednotlivé riešiace entity-agentov, agenti majú tendenciu vzájomne komunikovať a kooperovať, správanie jedného agenta je zvyčajne omnoho jednoduchšie ako komplex vzájomných interakcií agentov a globálne správanie sa celého systému (skupiny interagujúcich agentov).
Centralizácia, resp. stupeň decentralizácie sa v súčasnosti javí byť jednou z kľúčových vlastností pri návrhu systému so strojovou inteligenciou. Vo všeobecnosti možno vymedziť:
centralizované systémy: centrálne riadené systémy (tiež systémy na báze jedného agenta). Čiastkovým riešiacim jednotkám (zvyčajne špecializovaným modulom) sa distribuujú čiastkové úlohy dekomponovaného globálneho problému, ktoré sa po vyriešení odovzdávajú opäť vyšším úrovniam riadenia, kde (ak je potrebné) sú syntetizované. distribuované systémy (tiež multi-agentové systémy): riadenie systému je distribuované jednotlivým autonómnym agentom a je realizované na báze ich vzájomných interakcií, zahŕňajúcich komunikačné a kooperatívne akty (spoločný problém je riešený kooperáciou nezávislých riešiacich jednotiek, pričom samotný priebeh riešenia spoločnej úlohy nie je riadený centrálne).
3. Nové výzvy strojovej/umelej inteligencie v Inteligentných systémoch Distribuované znalostné systémy predstavujú nové smery vývoja rozľahlých a komplexných systémov so širokým aplikačným potenciálom od robotiky až po informačné systémy nasadené napr. vo finančnom sektore. Tento fakt mení ak prístup ku strojovej/umelej inteligencii v budovaní inteligentných systémoch. Výskum sa musí orientovať na tieto prístupy s dôrazom na tzv. zosieťované systémy – networked systems. Cieľom je teda študovať inteligentné technológie s dôrazom na výpočtovú inteligenciu a ich potenciálne využitie pri vytváraní integrálneho distribuovaného znalostného systému, ktorý by bol vytváraný vo vybraných prostrediach za špeciálnych podmienok a následne tieto podmienky by sa zovšeobecňovali. Veľmi dôležitú úlohu v procese vytvárania takéhoto komplexného systému budú zohrávať interaktívne technológie medzi strojom a expertom, tvorba virtuálnych
modelov experta, fuzzy prístupu k odhadu a klasifikácii stavov, predikčné problémy, optimalizačné problémy s cieľom hľadania sub-optimálných riešení. Vo výskume chceme využívať primárne prostriedky výpočtovej inteligencie a z tohto pohľadu je vo svete ich aplikácia pre tvorbu učiacich sa distribuovaných znalostných systémov nie veľmi častá resp. pri štúdiu literatúry prichádzame nato že komunita znalostných systémov je silne zviazaná na symbolickú umelú inteligenciu. Chceli by sme študovať možnosti príspevku výpočtovej inteligencie ku tvorbe hybridného modelu budovania učiacich sa distribuovaných znalostných systémov. Na nasledujúcej schéme je naznačená základná koncepcia tvorby takéhoto systému, ktorý je postavený na „N“ Agentoch a princíp je v návrhu doménovo orientovaného systému, ktorý zbiera znalosti a následne ich poskytuje tvojim agentom. Tým sa vytvára „rodina Agentov“, ktorá vlastní svoje znalosti, inkrementálne ich vytvára a súčasne z diela. Tvorba takého to „žijúceho“ systému je komplikovaná a vo svete je veľa príkladov kde sa pokúšali takýto systém vytvoriť ale pri jeho tvorbe je veľmi veľa problémov a úskalí. Hlavne v oblasti symbolickej umelej inteligencie boli rôzne pokusy takýto systém vytvoriť a riešiť množstvo problémov s tým spojených ako je fúzia znalostí reprezentácia znalosti, ontologické systémy a pod.
Knowledge Fusion and Download to Each Agent Upload partial knowledge
Agent #1
Environ #1
Agent #2
Environ #2
Upload partial knowledge
Upload partial knowledge
Agent #N
Environ #N
Obrázok 2 : Základný popis základného konceptu distribuovaného prístupu k inteligentným systémom
Obrázok 3 : Popis humanoidnej platformy robota NAO Predmetný problém je problém základného výskumu a bude mať dopad na tvorbu integrálnych distribuovaných znalostných systémov s prvkami učenia, inkrementality a virtuálneho života vytváraného systému. Budú vybrané testovacie oblasti, kde sa vyvíjaná metodológia bude testovať a to hlavne v skupinovej robotike s dôrazom na univerzálnosť problematiky a aplikovateľnosť aj v iných oblastiach inžinierskych technológií. Výzvy sú v súlade s odbornou víziou EU, ktorá vo svojich výzvach hovorí o tvorbe tzv, „večných systémov“ (eternal systems) v oblasti ICT Dopad výskumu je veľmi dôležitý pretože štúdium tejto problematiky napomôže tvorbe inkrementálneho učiaceho systému, ktorý môže mať vysoký aplikačný potenciál od robotiky až po tvorbu inteligentných “žijúcich” informačných systémov nasadených v bankách alebo napr. v priemysle. Celý výskum je postavený na testovacej doméne mobilnej robotiky, kde sa budeme sústreďovať na tvorbu takýchto systémov a mobilná robotika bude pre nás nástrojom prezentácie testovacieho systému a schopnosti inkrementálneho systému. V súčasnosti máme k dispozícii platformy NAO pre využitie štúdia takýchto systémov. Vedecké prínosy očakávame v oblasti výpočtovej inteligencie a jej príspevku ku budovaniu inkrementálneho a učiaceho systému. Medzi najdôležitejšie problémy v tejto oblasti považujeme :
1.
Výskum v oblasti interaktívnych neuro systémov s dôrazom na reinforcement learning a tvorby HCI s cieľom modelovania experta a následného prenosu poznatkov z človeka do stroja
2. 3.
4.
5. 6. 7.
Výskum v oblasti Adaptívnych fuzzy systémov a ich možností využitia v získavaní znalostí Výskum v oblasti klasifikačných resp. rozhodovacích systémov založených na zhlukovacích procedúrach v rôznych statických ako aj dynamických príznakových priestoroch. V tejto oblasti chceme využiť fuzzy mieri na stanovovanie vzťahov medzi hľadanými triedami resp. rozhodnutiami Výskum v oblasti hľadania nových metód učenia neurónových sietí s cieľom integrácie znalostí expertov a tvorby učiaceho systému, ktorý nájde najvhodnejší systém učenia neurónových sietí typu BP na základe znalostí expertov. V tomto cieli budeme riešiť aj problém vizualizácie znalostí resp. parciálnych znalosti z neurónovej siete. Výskum v oblasti evolučných systémov a ich možností pri meniacich sa fitness funkciách alebo pri neexistencii fitness funkcie, ktorá je nahradená ľudským účastníkom experimentu. Bude snaha o identifikáciu správania sa experta a jeho simuláciu a tým, že z interaktívnych evolučných systémov sa proces bude mat snahu „postupne“ vrátiť ku klasickým evolučným výpočtom a takýmto spôsobom vyriešiť problém neexistencie fitness funkcie. Výskum v oblasti využitia výpočtovej inteligencie v spracovaní obrazovej informácie s dôrazom na problémy pri viac zdrojovej obrazovej informácii. Výskum v oblasti reprezentácie znalostí, štúdium možností využitia ontologických neurónových sietí pri reprezentácii znalostí. Problematika fúzie znalostí z rôznych informačných zdrojov Výskum v oblasti tzv. MIQ, ktorý priamo súvisí s inkrementalitou znalostí a schopnosti riešiť situácie. MIQ je dôležitý aj preto aby sme vedeli určitým spôsobom merať resp. kvantifikovať schopnosti učiaceho sa systému a jeho bazu znalostí. Súčasne ide o problém autonomity systému v globálnom meradle teda o systém, ktorý zvyšovaním MIQ ši sám zvyšuje autonomitu a znižuje operátorské resp. expertné zásahy.
5. Záver Z hore uvedeného som názoru, že výskum napomôže ku posunutia hraníc vedeckého poznania v oblasti umelej inteligencie, výpočtovej inteligencie a tvorby inteligentných systémov. Na splnenie cieľov bude sústredená činnosť Centra pre inteligentné technológie (CIT), ktoré pozostáva z dvoch laboratórií a to laboratória autonómnych systémov (CIT-LAS) a laboratória Humanoidných systémov (CITLHS). Kým CIT-LHS je sústredené na štúdium prvkov pre Humanoidné systémy, CIT-LAS je viac otvorený pre priemyselné aplikácie a tvorbu a prepojenie na prax.
Poďakovania : Táto práca bola vytvorená realizáciou projektu Rozvoj Centra informačných a komunikačných technológií pre znalostné systémy (kód ITMS projektu: 26220120030) na základe podpory operačného programu Výskum a vývoj financovaného z Európskeho fondu regionálneho rozvoja.
Literatúra : [1] SINČÁK, Peter; VAŠČÁK, Ján (Eds) Quo Vadis Computational Intelligence . Heidelberg : Physica-Verlag, 2000. 498 s. ISBN 3790813249, ISSN 14349922 [2] SINČÁK, Peter at all, (Eds) Intelligent Technologies – Theory and Applications . Amsterdam, IOS Press, 2002, 347 s., ISBN 1586032569 [3] SINČÁK, Peter at all, (Eds) Machine Intelligence – Quo Vadis, Singapur, Word Scientific, 2004, ISBN10: 981238751X, ISBN13: 9789812387516 [4] SINČÁK, Peter at all, (Eds) The State of the Art in Computational Intelligence , Heidelberg : Physica-Verlag, 2000, 401s., ISBN 3790813222, ISSN 16153871 [5] SINČÁK, Peter at all, (Eds) Quo Vadis Intelligent Systems, Košice, Elfa Press, 116s, ISBN 9788080861735 [6] FEDOR Zlatko, SINČÁK, Peter: AIBO talking procedure based on incremental learning approach, 2008. In: Acta Technica Jaurinensis. Vol. 1, no. 3 (2008), p. 413421. - ISSN 1789-6932 [7] SINČÁK, Peter Potrebujeme aj u nás inovácie na báze technológií umelej inteligencie ? - 2008. In: SOFTECON , SOFTEC, 2008 28 s. [8] SINČÁK, Peter, REIFF Tomaš, Incremental building of intelligent systems In: Kybernetika a informatika. - Bratislava : STU, 2008 5 s. - ISBN 9788022728287
UMELÁ INTELIGENCIA V METÓDACH NAVIGÁCIE ROBOTOV ARTIFICIAL INTELLIGENCE IN METHODS OF ROBOT NAVIGATION Ján Vaščák
Abstrakt Tento príspevok sa zaoberá problematikou vzťahu navigácie a prostriedkov umelej inteligencie (UI), predovšetkým časti známej ako výpočtová inteligencia. Samotný pojem navigácie je možné rozdeliť jednak na plánovanie cesty a jednak na vlastnú navigáciu, ktorá rieši najmä otázky reagovania na zmeny situácie prostredia, napr. obchádzanie prekážok a sledovania predpísanej (naplánovanej) cesty. Keďže je zrejmé, že uvedené úlohy sú odlišnej povahy, budú tieto najsamprv ozrejmené a následne budú definované všeobecné vlastnosti prístupov vhodných na ich riešenie. Napokon budú uvedené niektoré prostriedky patriace aspoň čiastočne do oblasti UI, ktoré riešia problémy navigácie hlavne pre mobilné roboty, ako sú napr. fuzzy logika, potenciálové polia a siete Neural Gas s na to nadväzujúcou ukážkou niektorých experimentov. Kľúčové slová Navigácia, plánovanie cesty, fuzzy logika, fuzzy kognitívne mapy, potenciálové polia, siete Neural Gas. Abstract This paper deals with the relation between navigation and means of artificial intelligence (AI), first of all a part known as computational intelligence. The notion navigation can be divided to the path planning and the own navigation, which solves problems of situation changes, e.g. obstacle avoidance and path tracking. It is evident the mentioned tasks are of diverse nature. Therefore, they will be at first explained and then general properties of convenient methods will be defined. Finally, some means belonging to the area of AI will be mentioned, which solve navigation problems mainly for mobile robots as e.g. fuzzy logic, potential fields and networks Neural Gas with some shown experiments. Keywords Navigation, path planning, fuzzy logic, fuzzy cognitive maps, potential fields, networks Neural Gas.
1. Úvod Vo všeobecnosti pojem navigácia predstavuje monitorovanie a riadenie pohybu vozidla (loď, lietadlo, robot a pod.) z jedného bodu v priestore do druhého. Implicitne sa teda predpokladá, že existuje nejaký plán, na základe ktorého sa vozidlo presúva po jednotlivých bodoch, ktorý je vytvorený, buď človekom, alebo nejakým systémom na základe istých cieľov a obmedzení. Pre potreby robotiky je však vhodnejšie rozdeliť širšie koncipovanú úlohu všeobecnej navigácie na plánovanie cesty a vlastnú navigáciu, ktorá zabezpečuje dodržiavanie predpísaného plánu cesty. Jedná sa tu hlavne o spracovanie údajov zo senzorov a spôsob minimalizácie vzniknutej odchýlky. Do tejto úlohy môžeme zaradiť napr. aj riešenie nepredvídateľných udalostí ako obchádzanie pohybujúcich sa prekážok, či iné havarijné stavy. Obidve časti všeobecnej navigácie sú samozrejme navzájom prepojené a v celej rade, najmä jednoduchších, metód splývajú. Ak nebude hroziť nedorozumenie, tak v ďalšom budeme všeobecnú navigáciu označovať iba ako navigáciu. Úlohou tohto príspevku je poukázať na niektoré vybrané metódy UI, ktoré sa využívajú v obidvoch typoch úloh a sa javia ako najperspektívnejšie. Vychádzame pritom z premisy, že základnou formou reprezentácie znalosti v UI je produkčné pravidlo, či už ako dvojhodnotové alebo vo forme fuzzy pravidla, ktoré umožňuje okrem iného aj priame využitie prostriedkov výpočtovej inteligencie. Práve tieto metódy niekedy vyvolávajú otázky, či daná metóda ešte zodpovedá základnej paradigme UI, t.j. že zvolená metóda má odrážať spôsob ľudského riešenia problému alebo aspoň nejaký jav živej prírody. Načrtnúť v tomto nejakú jasnú hranicu je ale častokrát nemožné a skôr sa stretávame s faktom, že málokedy má zmysel aplikovať „čistokrvnú“ UI. Skôr sa bude v budúcnosti jednať o syntézu UI a konvenčných prístupov známych napr. z teórie riadenia. Po stručnom úvode do problematiky plánovania cesty sa budeme zaoberať možnosťami využitia fuzzy logiky v riadení pohybu. Ďalej si ukážeme možnosť využitia konceptu fuzzy kognitívnych máp (FKM) v úlohách tohto typu. Na to nadviažeme konkrétnymi metódami plánovania cesty ako potenciálové polia a siete typu Neural Gas. Jednotlivé príklady budú prezentované experimentmi, ktoré sme vykonávali na našom pracovisku Centra pre inteligentné technológie na Technickej univerzite v Košiciach. 2. Základné prístupy plánovania cesty v robotike V súčasnosti jestvujú tri základné skupiny metód pre plánovanie cesty mobilných robotov [1]1, 6]: 1. heuristické, 2. exaktné, 3. mriežkové (grid) algoritmy. Typickým reprezentantom prvej skupiny sú tzv. Bug algoritmy, ktoré sú jednoduché, ale vhodné väčšinou iba pre tzv. statické prostredie, t.j. s nepohyblivými a nemennými prekážkami. Exaktné algoritmy ako grafy viditeľnosti, Voronoiove diagramy, či A* umožňujú matematicky korektným spôsobom nájsť
najlepšiu (v tomto zmysle najkratšiu) trajektóriu. V prípade nemožnosti nájsť riešenie sú dokonca schopné výpočtový proces ukončiť, a tak predísť zacykleniu algoritmu. Problémom je však to, že vyžadujú veľmi presné údaje o prekážkach, čo v praktických aplikáciách môže byť vážny problém. Preto sa tiež väčšinou využívajú pre statické prostredie, t.j. scéna rozloženia jednotlivých objektov sa nemení. Z tohto uhla pohľadu sa mriežkové algoritmy zdajú byť vhodnejšie pre reálne prevádzkové podmienky, nakoľko v závislosti na chybe snímania je možné definovať presnosť mriežky, alebo navrhnúť viacvrstvové mriežky, ktoré najprv umožnia hrubú navigáciu a po priblížení sa robota k cieľu prepnú na presnejšiu mriežku, kde iba v tomto úseku vyžadujú presné snímanie. Takto je možné okrem iného aj skrátiť dobu výpočtu. 3. Fuzzy regulátory pri riadení pohybu Veľkou výhodou fuzzy regulátorov (FR) je nielen schopnosť spracovávať neurčité znalosti o danom prostredí ako aj nepresné dáta zo snímačov, ale aj fakt, že primárne boli navrhnuté ako pravidlové systémy (ich rozšírením sú napr. fuzzy kognitívne mapy), čiže je možné na nich priamo modelovať ľudský prístup riešenia daného problému. Ich veľkou nevýhodou je neschopnosť sa učiť. Preto bola navrhnutá celá rada postupov a adaptačných algoritmov na automatickú tvorbu bázy znalostí. V ďalšom si ukážeme tzv. ProcykMamdaniho samoorganizačný FR, pôvodne navrhnutý v [8]8] a modifikovaný vo viacerých prácach ako napr. [2]5, 9], ktorého základná bloková schéma sa nachádza na obr. 1. Činnosť tohto systému je založená na bloku merania výkonnosti, ktorý vyhodnocuje na základe prepísaných kritérií kvalitu regulátora. Výstupom je pre daný krok vzorkovania k hodnota výkonnosť p(k), ktorá určuje mieru, do akej majú byť vykonané zmeny v báze znalostí. Pre tento účel je ale potrebné zadefinovať tzv. inkrementálny model M1(k), ktorý je obdobou lineárnej aproximácie prvého rádu riadenej sústavy a určuje sa z matice dynamiky jej stavového popisu. Keďže medzi vstupmi a výstupmi regulátora a sústavy existuje inverzný vzťah, tento vyjadrujeme symbolom inverznej funkcie, nakoľko potrebujeme poznať v konečnom dôsledku model regulátora M1(k) a nie sústavy M(k). Výstupom z bloku modelu je tzv. oprava r(k), ktorá priamo predpisuje hodnotu, o ktorú sa má zmeniť báza znalostí. V tomto prípade predpokladáme, že poznáme vhodné rozdelenie premenných vstupov a výstupov na jazykové hodnoty. Kombináciou všetkých možných vstupov dostaneme úplný súbor vzájomne neprotirečivých pravidiel, pomocou ktorých sú vlastne popísané všetky možné situácie. Úloha sa nám tak zjednoduší iba na nájdenie správnej výstupnej hodnoty a tá bude práve modifikovaná hodnotou r(k), kde bude upravovaný hlavne vrchol funkcií príslušnosti výstupov. Pre úplnosť je vhodné dodať, že ProcykMamdaniho samoorganizačný FR je možné implementovať pre bázu znalostí vo forme jednak fuzzy produkčných pravidiel a jednak fuzzy relácií. Bližšie informácie o tomto type regulátora sú napr. v [9]. Okrem uvedeného prístupu je možné využiť na modifikáciu bázy znalostí aj tradičné gradientové prístupy, keď sa definuje vzťah výstup – vstup daného regulátora ako funkcia závislá od n parametrov bázy znalostí a následne sa táto
parciálne derivuje podľa týchto parametrov. Takto dostaneme sústavu n rovníc o n neznámych.
Obr. 1. Bloková schéma ProcykMamdaniho samoorganizačného FR.
Kombinovaním Procyk‐Mamdaniho prístupu a gradientových metód dostávame systém, ktorý sa napr. vie učiť jednoduché úlohy plánovania pohybu z bodu A do bodu B, či už bez alebo s obchádzaním prekážky (bližšie viď [9]), ako je vidieť na obr. 2, kde je ukázané porovnanie s ručne nastaveným a adaptívnym FR. Je možné vidieť evidentný rozdiel medzi správaním sa bez a s prekážkou. Adaptívny FR vykazuje kratšiu trajektóriu v prípade bez prekážky, zatiaľ čo v prípade s prekážkou je tomu naopak. Navyše je možné pozorovať istú opatrnosť voči prekážke. Trajektória si ju najprv opatrne obchádza a v jednom bode sa začne od nej vzďaľovať najrýchlejším možným spôsobom. Toto správanie je obdobné človeku, ktorý by prekážku vnímal ako aktívne nebezpečenstvo. To je však kvalitatívne nová informácia, ktorú adaptívny FR implicitne obsahuje vo svojich pravidlách, ale ktorú mu nikto nevložil. Tento prípad je typickým príkladom emergencie nových vlastností, ktoré sa vopred nepredpokladali. Uvedieme si ešte jednu jednoduchú a pritom efektívnu možnosť využitia fuzzy logiky, kde sa práve využije ich vlastnosť, že využívajú pravdivostné hodnoty z celého rozsahu intervalu [0; 1]. Využíva sa pritom princíp tzv. sonarovej percepcie, kde získavame jednak uhol natočenia nejakej prekážky od robota a jednak jej vzdialenosť. Na základe toho sa okolo robota skonštruuje kruhový sonarový signál (viď obr. 3), ktorý je v tomto prípade reprezentovaný ako lichobežníková funkcia príslušnosti, kde jej jadro predstavuje šírku prekážky. Veľkosť nosiča je súčtom jadra a šírky samotného robota (robot je tiež istou
formou prekážky, najmä keď potrebuje prejsť pomedzi dve prekážky). Výška hgt takejto funkcie príslušnosti je závislá od dosahu sonara a sa vypočítava ako:
hgt =
dosah − vzdialenosť . dosah
(1)
Obr. 2. Ukážka tvorby trajektórií ručne navrhnutým FR (a, c) a adaptívnym FR (b, d) pre prípady bez prekážky (a, b) a s prekážkou (c, d).
Takýto sonarový signál predstavuje vlastne pravidlo indikujúce nevhodnosť voľby príslušného smeru. Čím je vyššia hodnota stupňa príslušnosti pre uhol natočenia robota, tým je tento smer menej vhodný, lebo prekážka je bližšie. Voľné smery pohybu majú nulový stupeň príslušnosti. Preto je logické takýto výrok znegovať a použiť nejaký operátor doplnku, napr. 1 – hgt, k pretransformovaniu sonarového signálu na informáciu vhodnosti daného smeru. Predpokladajme, že poznáme polohu cieľa. V takomto prípade je možné skonštruovať ďalšiu funkciu príslušnosti (napr. trojuholníkovú) nad celým univerzom s vrcholom v danom cieli. Prienikom, čiže realizovaním nejakej t‐normy (napr. minimum) medzi týmito funkciami príslušnosti bude výsledná funkcia vyjadrovať kompromis medzi polohou cieľa a priestorom bez prekážok. Defuzzifikovaním takto získanej výslednej funkcie príslušnosti získame výstupnú hodnotu S, ktorá predstavuje požadovaný smer natočenia robota v danom čase. Celý proces je potrebné si predstaviť v čase, kde pohyb a jeho prípadná zmena sa vykonávajú v jednotlivých krokoch. Využijúc viachodnotovú logiku, akou je aj fuzzy logika, kde sa rozlišuje medzi bližšími a vzdialenejšími prekážkami, sa realizuje implicitná zásada: „Najprv rieš bližšie prekážky a až potom vzdialenejšie!“ Takto
robot získava schopnosť ich obchádzať. V neposlednom rade je takýto prístup aj všeobecný vzhľadom na počet a do istej miery aj tvar prekážok.
Obr. 3. „Negovaný“ kruhový sonarový signál (plná čiara), trojuholníková funkcia príslušnosti cieľa (prerušovaná čiara) a smer natočenia S po vykonaní defuzzifikácie prieniku funkcií príslušnosti.
4. Fuzzy kognitívne mapy ako podpora rozhodovania FKM predstavujú isté zovšeobecnenie konvenčných fuzzy pravidlových systémov a môžu byť použité jednak na rovnaké úlohy pri priamom riadení pohybu robota, ako bolo ukázané v predošlej stati a jednak na podporu rozhodovania pri výbere niektorej z variant riešenia. Bližšie informácie o základoch FKM, ich využití a adaptácii je možné nájsť napr. v [2]. Prvou možnou aplikáciou je priame použitie FKM ako istého fuzzy regulátora, kde s využitím adaptačných mechanizmov si definuje funkcie príslušnosti jednotlivých uzlov ako aj váhy spojení. Vzhľadom na to, že sa jedná o v princípe zložité štruktúry, predpokladá sa, že uzly a ich významy sa zadefinujú ručne. Na obr. 4 je možné vidieť jeden príklad FKM riešiacej úlohu prechodu vozidla do cieľa so známou polohou s ohľadom na prekážky. Pomocou senzorov S1 – S5 sa zisťuje poloha a blízkosť prekážok, čo sa vyhodnocuje v uzloch C8 – C15, či prekážka je blízko (b) alebo kriticky blízko (kb). Ďalej pre rozhodnutie o akcii je potrebné poznať polohu cieľa, či je naľavo (CL), napravo (CP) alebo priamo vpredu pred vozidlom (CV) – uzly C4 – C6. Taktiež je potrebné vziať do úvahy blízkosť cieľa (Cb), čo predstavuje uzol C7, ktorý je priamo napojený na výstupný uzol C3 predstavujúci podmienku zastavenia (S), ak je táto splnená na hodnotu aspoň 0,95. Zvyšné výstupné uzly C0 – C2 sú pre akčné zásahy, či sa vozidlo má natočiť doľava (L), doprava (P), alebo ísť rovno vpred (V). Bližšie informácie o tomto type úlohy a typoch adaptačných metód pre FKM viď napr. [13]. Ďalší príklad využitia FKM ukazuje na možnosť hybridizácie, t.j. vzájomného prepojenia viacerých prostriedkov za účelom riadenia premávky robotických vozidiel, napr. v automatizovanom závode alebo pri pomoci s vyhľadávaním vhodného parkovacieho miesta pri hypermarketoch. Ak máme presne zadefinovanú komunikačnú sieť, ako je napr. parkovisko obkolesené obchodmi (obr. 5), tak na požiadavku čo najvhodnejšie zaparkovať k nejakému obchodu
môžeme využiť niektorý z grafových prehľadávacích algoritmov ako je A* [6], ktorý je schopný brať do úvahy tzv. cenu cesty, keďže na výber parkovacieho miesta nevplýva iba jeho minimálna vzdialenosť k danému obchodu, ale napr. jej zložitosť vyjadrená počtom odbočení, či doba čakania, ak by niekde vznikla zápcha. Takto sa môže stať, že najbližšie parkovacie miesto nemusí byť najvhodnejšie a že sa oplatí radšej zastaviť o niečo ďalej.
Obr. 4. Príklad fuzzy kognitívnej mapy pre navigáciu vozidla k známej polohe cieľa v prostredí s prekážkami.
Obr. 5. Príklad parkoviska so simulovanou premávkou vozidiel v nákupnom stredisku a tvorba ciest pre prichádzajúce vozidlá.
Pre výber vhodnej cesty je preto najvýhodnejšie vykonať výber pre viacero voľných parkovacích miest v blízkosti vybraného cieľa, nielen to najbližšie. Pre tieto miesta sa pomocou A* algoritmu vytvoria optimálne cesty a ich výhodnosť sa bude navzájom porovnávať. Samozrejme, každý užívateľ má rôznu prioritu ohľadom hodnotiacich kritérií. Zatiaľ čo pre mladého a zdravého človeka nie je problém prejsť peší niekoľko metrov navyše, tak pre človeka s problémami chôdze bude lepšie radšej trochu počkať v zápche. Inými slovami, tieto priority je možné popísať váhami wi a pomocou nich hodnotiace kritéria navzájom pospájať. Takto dostaneme nasledujúcu FKM (obr. 6), ktorá vypočítava mieru vhodnosti daného parkovacieho miesta a miesto s najlepšou vhodnosťou je následne vybrané [11].
Obr. 6. Príklad FKM pre výber najvhodnejšieho parkovacieho miesta.
5. Potenciálové polia Potenciálové polia (prvý krát navrhnuté v [4]) patria do skupiny mriežkových algoritmov. Vychádzajú z metafory magnetického poľa. Pomocou nich je tak možné modelovať prostredie s prekážkami ako potenciálové rozdiely a na ich základe určovať akčný zásah. Takáto reprezentácia vlastne predstavuje vytvorenie istej „krajinky“ (obr. 7a), čo je veľmi vhodná forma reprezentácie znalostí pre využitie prostriedkov výpočtovej inteligencie. V ďalšom bude táto možnosť prezentovaná na simulácii problému parkovania. V prostredí pre pohyb robotov sú v podstate dva druhy objektov: ciele a prekážky. Vo vyjadrení pomocou potenciálového poľa by ciele mali robot priťahovať a prekážky ho od seba odpudzovať, t.j. v silovom vyjadrení sa bude jednať o príťažlivé Fc a odpudivé Fp sily.
G G G F ( x , y ) = FC ( x , y ) + ∑ FPi ( x , y ).
(2)
i
Množina všetkých síl pre všetky body priestoru (x,y) vytvára vektorové pole F (viď obr. 7b). Podobne, potenciálové pole U je zobrazením všetkých potenciálov U(x,y), vypočítaných ako práca vykonaná medzi bodom (x,y) a bodom s nulovým potenciálom (x0,y0) pozdĺž cesty l: ( x, y)
U ( x, y) =
∫
G F .dl .
(3)
( x0 , y0 )
Potenciálové pole predstavuje tak priestor, ktorý pripomína istú krajinku s vrcholkami zodpovedajúcimi prekážkam a údoliami predstavujúcimi ciele. Ak umiestnime mobilný robot do ľubovoľného bodu (x,y), tak pôsobením gravitácie sa tento bude pohybovať po trajektórii s najstrmším zostupom, čo zodpovedá gradientu, a tým získame najrýchlejšiu cestu k cieľu. Okrem toho, nastavením strmosti vrcholkov je možné definovať isté bezpečnostné odstupy, ktoré slúžia ako isté tolerančné pásma pre prípad nepresného snímania alebo akčného zásahu. Takýmto spôsobom vieme modelovať istý súlad medzi rýchlosťou a bezpečnosťou pohybu.
Obr. 7. Príklad potenciálového poľa s tromi prekážkami P1, P2, P3 (čierne oblasti) a cieľom C s vypočítanou trajektóriou z bodu Š – a) a k nemu prislúchajúce vektorové pole – b).
Uvedený prístup je vhodný najmä v prípade, ak prekážky sú statické, t.j. sa nepohybujú. V praxi sa však stretávame s dynamickými prekážkami a rôznymi kolíznymi situáciami. Pre tento účel je preto systém doplnený o regulátor kolíznych stavov. Systém najsamprv zo zosnímanej situácie (napr. snímka z kamery) vypočíta potenciálové pole a určí optimálnu trajektóriu, na ktorej si v jednotlivých odstupoch vytvorí postupnosť sledovacích značiek. Sledovací mechanizmus následne riadi vozidlo od jednej značky po druhú. Meranie odchýlky a vlastná navigácia sa robí iba na základe týchto značiek. Ak do trajektórie vstúpi nejaká dynamická prekážka, tak postupnosť značiek sa naruší, t.j. sledovač nevidí nasledujúcu značku, a tým sa spustí systém na obchádzanie prekážok, ktorý bude
v činnosti dovtedy, pokiaľ nenarazíme na ďalšiu značku. Keďže postupnosť značiek je vopred známa, tak systém vie, v ktorej časti priestoru sa nachádza a prepína sa znovu na režim sledovania, viď obr. 8. Bližší popis o uvedenom systéme sa nachádza v [10].
Obr. 8. Ukážka využitia potenciálových polí v prostredí s dynamickými prekážkami.
6. Využitie neurónových sietí typu Neural Gas Neurónové siete predstavujú veľmi rozsiahlu problematiku a iba vytvorenie prehľadu metód v navigácií presahuje možnosti tohto príspevku. Na tomto mieste by sme spomenuli jednu menej známu, ale zaujímavú aplikačnú možnosť, ktorá rieši problémy popisu nesúrodej komunikačnej siete, napr. dopravnej siete nejakého mesta (viď obr. 10), kde využitie potenciálových polí by bolo problematické. Použitie ináč veľmi efektívnych mriežkových algoritmov je v takomto prípade problematické kvôli svojej heterogenite, čo by vyžadovalo konštruovanie veľmi hustej mriežky, a s tým spojenej výpočtovej zložitosti. Siete Neural Gas sú vo svojej podstate grafy, pomocou ktorých je možné modelovať tvar daných obrazcov, podobne ako Kohonenové siete, avšak na rozdiel od nich nemajú pevnú topológiu prepojení výstupnej vrstvy, čo sa ukazuje výhodným práve v nehomogénnych oblastiach. Pri určovaní zmeny polohy výstupných neurónov sa využíva taktiež princíp susednosti. Tá sa však mení v každom adaptačnom kroku v závislosti od daného vstupu [7]. Táto zvýšená miera adaptácie umožňuje, aby sa mohli neuróny navzájom relatívne volne presúvať v prostredí, ktoré majú popísať svojim vhodným rozložením, čo evokuje dojem šírenia plynu v uzatvorenom priestore. Úlohou tejto siete je vhodným spôsobom rozvrstviť svoje neuróny a navzájom ich tak pospájať, aby takáto geometrická štruktúra čo najvernejšie popisovala pôvodný obrazec. Na obr. 9 je zobrazený postup učenia sa siete Neural Gas na medzikruží, kde vhodným kombinovaním Kohonenovho a konkurenčného Hebbovho učenia sa v jednotlivých krokoch učenia postupne
pridávajú neuróny na vhodné miesta a tie sa vzájomne prepoja. Dá sa dokázať, že z výslednej štruktúry (obr. 9g) je možné vytvoriť tzv. Voronoiove oblasti, ktoré garantujú grafovým prehľadávacím algoritmom (napr. A*) nájdenie optimálnej cesty.
Obr. 9. Postup učenia sa siete Neural Gas na medzikruží.
V našom prípade môžeme túto vlastnosť sietí Neural Gas s výhodou použiť práve pri popise cestných sietí miest a obcí, kde po zosnímaní mapovej dokumentácie a spracovaní získanej snímky použitím filtrov môžeme na ne tieto siete priamo aplikovať a následne nasadiť algoritmus A* pre vyhľadávanie ciest, ako je to znázornené na obr. 10. Takto odpadne zložitá (v mnohom ručná) príprava bázy znalostí o daných komunikáciách. Bližší popis učenia sietí Neural Gas ako aj postupu ich využitia v plánovaní ciest v rámci mestských komunikácií je možné nájsť v [12].
Obr. 10. Vytvorenie topológie siete Neural Gas (svetlé čiary) na pozadí výseku cestných komunikácií (tmavá plocha).
7. Závěr Uvedený zoznam prístupov k plánovaniu cesty je len malým výberom z celej širokej škály možností, ako je možné využiť prostriedky UI. Z priestorových možností nebolo napr. možné spomenúť evolučné algoritmy, ktoré sa síce na úlohy plánovania priamo málo využívajú, môžu však byť veľmi dobrým prostriedkom pre nastavovanie parametrov plánovacích algoritmov. Z hľadiska všeobecnosti prístupu a napojenia na ďalšie prostriedky sme sa zaoberali jednak veľmi špecifickými prostriedkami ako potenciálové polia a siete typu Neural Gas ako aj fuzzy regulátormi a FKM, ktoré je možné ďalej rozvíjať a napájať na ďalšie prostriedky, v tomto prípade hlavne na pravidlové systémy a symbolickú UI ako takú. Treba si totiž uvedomiť, že plánovanie ako také je strategickou hrou, ktorá má svoje pravidlá. Práve odhaľovanie zákonitostí medzi jednotlivými objektmi a pravidiel, podľa ktorých sa skúsený plánovač riadi, je jadrom tohto typu problému. Napokon ďalším krokom v plánovaní ciest je zostavovanie sady plánov pre vzájomne kooperujúce roboty, čo je napr. aj rozšírenie úlohy riadenia premávky plánovaním ciest pre všetky vozidlá [11], či robotický futbal, alebo úloha prenasledovania koristi predátormi. Korisť predstavuje neustále sa meniaci cieľ, ktorého správanie musia predátori vedieť aspoň čiastočne odhadnúť a prispôsobiť k tomu svoj lov. Pre tento účel je ale potrebné získať pravidlá správania sa koristi a technických možností (obmedzení) predátorov, bližšie napr. [3]. Poďakovanie Táto práca bola vytvorená realizáciou projektu Rozvoj Centra informačných a komunikačných technológií pre znalostné systémy (kód ITMS projektu: 26220120030) na základe podpory operačného programu Výskum a vývoj financovaného z Európskeho fondu regionálneho rozvoja. Literatúra [1]
DUDEK, G.; JENKIN, M. Computational Principles of Mobile Robotics. Cambridge : Cambridge University Press, 2000. 280 s. ISBN 0‐521‐56021‐7.
[2]
Fuzzy Cognitive Maps : Advances in Theory, Methodologies, Tools and Applications. Edited by Michael Glykas. Berlin Heidelberg : Springer‐Verlag, 2010. 200 s. Studies in Fuzziness and Soft Computing, ISBN 978‐3‐642‐ 03219‐6.
[3]
HLÁDEK, Daniel; VAŠČÁK, Ján; SINČÁK, Peter. MULTI–ROBOT CONTROL SYSTEM FOR PURSUIT–EVASION PROBLEM. Journal of Electrical Engineering. 2009, vol. 60, no. 3, s. 143–148. Dostupný také z WWW: . ISSN 1335‐3632.
[4]
KHATIB, O. Real‐time obstacle avoidance for manipulators and mobile robots. In Proceedings of IEEE International Conference on Robotics and Automation. [s.l.] : [s.n.], 1982. s. 500‐505.
[5]
KIM, Y.T.; BIEN, Z. Robust self‐learning fuzzy controller design for a class of nonlinear MIMO systems. Int. Journal Fuzzy Sets and Systems. 2000, vol. 111, no. 2, s. 17‐135. ISSN 0165‐0114.
[6]
LAVALLE, S.M. Planning algorithms. Cambridge : Cambridge University Press, 2006. 842 s. Dostupné z WWW: . ISBN 9780521862059.
[7]
MARTINETZ, T.M.; SCHULTEN, K.J. A neural gas network learns topologies. Artificial Neural Networks. 1991, vol. 1, no. 1, s. 397‐402.
[8]
PROCYK, T.J.; MAMDANI, E.H. A linguistic self‐organizing process controller. Automatica. 1979, no. 15, s. 15‐30. ISSN 0005‐1098.
[9]
VAŠČÁK, J.; MADARÁSZ, L. Automatic adaptation of fuzzy controllers. Acta Polytechnica Hungarica : Journal of Applied Sciences at Budapest Tech Hungary. 2005, vol. 2, no. 2, s. 5‐18. Dostupný také z WWW: . ISSN 1785‐8860.
[10] VAŠČÁK, J. Navigation of Mobile Robots Using Potential Fields and Computational Intelligence Means. Acta Polytechnica Hungarica : Journal of Applied Sciences at Budapest Tech Hungary. 2007, vol. 4, no. 1, s. 63‐74. Dostupný také z WWW: . ISSN 1785‐8860. [11] VAŠČÁK, J. Fuzzy cognitive maps in path planning. Acta Technica Jaurinensis : Series Intelligentia Computatorica. 2008, vol. 1, no. 3, s. 467 ‐ 479. Dostupný také z WWW: . ISSN 1789‐ 6932. [12] VAŠČÁK, J. Using neural gas networks in traffic navigation. Acta Technica Jaurinensis : Series Intelligentia Computatorica. 2009, vol. 2, no. 2, s. 203‐215. Dostupný také z WWW: . ISSN 1789‐6932. [13] VAŠČÁK, J.; MADARÁSZ, L. Adaptation of fuzzy cognitive maps : a comparison study. Acta Polytechnica Hungarica : Journal of Applied Sciences at Budapest Tech Hungary. 2010, vol. 7, no. 3, s. 109‐122. ISSN 1785‐8860. Dr. Ing. Ján Vaščák Technická univerzita v Košiciach, Fakulta elektrotechniky a informatiky Letná 9, 042 00 Košice, Slovensko e‐mail: [email protected]
3.
Postery MONGEOVSKÉ MATICE V MAX-MIN ALGEBŘE MONGE MATRICES IN MAX-MIN ALGEBRA Alena Pozdílková
Abstrakt Max-min algebra a její různé aspekty byly studovány mnoha autory kvůli své využitelnosti v různých oblastech, jako jsou fuzzy systémy, řízení znalostí a další. Binární operace sčítání a násobení jsou nahrazeny v max-min algebře operacemi maximum a minimum. Poster je zaměřen na speciální typ matic – Mongeovské matice. Tyto matice byly studovány v max-plus algebře, kde mají mnoho aplikací. Článek popisuje Mongeovské matice v max-min algebře, nejprve speciální typ - binární Mongeovské matice a pak Mongeovské matice obecně. Mongeovské matice v max-min algebře lze využít při zjednodušení některých algoritmů. Nejprve budou popsány základní vlastnosti Mongeovských matic a uvedeny některé důležité věty. Budou také zkoumány minimální prvky Mongeovské matice a jejich umístění. Na konci článku bude popsána konstrukce Mongeovských matic. Klíčová slova Mongeovská matice, binární Mongeovská matice, max-min algebra Abstract Max-min algebra and its various aspects have been studied by many authors because of its applicability to various areas, such as fuzzy systems, knowledge management and others. Binary operations of addition and multiplication are replaced in maxmin algebra by operations of maximum and minimum. The poster is focused on the special type of matrices – Monge matrices. These matrices have been studied in maxplus algebra, in which they have various applications. Monge matrices in max-min algebra will be described in the article, at first a special type – binary Monge matrices and then general Monge matrices. Monge matrices in max-min algebra can also be useful in simplifying some problems or algorithms. The basic properties of Monge matrices will be described. Minimal elements in a Monge matrix are investigated and their position in the matrix is described for many minimal elements. Also construction of any Monge matrix will be shown. Keywords Monge matrix, binary Monge matrix, max-min algebra
14.
Max-min algebra
Max – min algebra (R , , ) je algebraická struktura s dvěma binárními operacemi , na rozšířené množině reálných čísel R R , . Operace minimum a maximum v max – min algebře jsou odvozené z lineárního uspořádání množiny reálných čísel. Operace v max – min algebře jsou definovány následovně: pro x, y
R:x
y = max (x, y), x
y = min (x, y).
15. Mongeovské matice v max – min algebře Mongeovské matice in max – min algebře jsou speciální matice, splňující následující podmínku: (1) pro všechny prvky (A je matice typu (m, n)) a všechny indexy kde i, k jsou řádkové indexy, pro které platí sloupcové indexy, pro které platí .
, a j, l jsou
Tato podmínka je zřejmě splněna pro všechny takové čtveřice prvků z dané matice, které v dané matici tvoří obdélník. Podmínka (1) může být formulována také v následujícím ekvivalentním tvaru: (2) Z formulace (2) je zřejmé, že minimum každé uvažované čtveřice je nebo , tedy je umístěno v dané čtveřici v levém horním nebo pravém spodním rohu. Z podmínky (2) vyplývá i následující tvrzení. Věta 1: Matice typu (2, 2) je Mongeovská, pokud její minimální prvek je umístěn v jejím levém horním nebo pravém spodním rohu (pozice (1, 1) nebo (2, 2)). Přímé způsoby ověřování, zda daná matice je či není Mongeovská, jsou velice časově náročné, protože je potřeba Mongeovskou podmínku ověřit pro všechny možné čtveřice prvků. K jednoduššímu určování, zda je daná matice Mongeovská, nám slouží následující věta: Věta 2: Daná matice je Mongeovská, pokud všechny její submatice typu (2, 2), skládající se ze dvou sousedních řádků a sloupců, jsou Mongeovské. Důkaz: Nejprve je potřeba dokázat, že spojením dvou Mongeovských matice typu (2, 2) vznikne opět Mongeovská matice. Mějme matice ním
matici, která vznikne jejich spoje. Lze dokázat, že M je Mongeovská matice (důkaz lze pro-
vést přímo ověřením všech možností). Stejným způsobem lze provést konstrukci
matice typu (2, n), kterou lze dále ještě rozšířit na matici typu (m, n), skládající se z daných Mongeovským matic typu (2, 2). Minimální prvky v Mongeovské matici a jejich umístění Věta 3: Pokud existuje jediný minimální prvek v dané Mongeovské matici typu (m, n), kde , pak tento prvek je umístěn v levém horním nebo pravém spodním rohu dané matice (na pozici (1, 1) nebo (m, n)). Důkaz: Na základě Mongeovské vlastnosti (2) lze dokázat sporem. Věta 4: Pokud v dané Mongeovské matici typu (m, n), kde , existuje více minimálních prvků, pak tyto prvky jsou umístěny konvexně kolem levého horního a pravého spodního rohu této matice. Minimální prvky mohou být umístěny v obou těchto oblastech či pouze v jedné z nich. Mongeovská matice kromě výše uvedeného může obsahovat jeden či více sloupců a jeden či více řádků, které obsahují pouze minimální prvky. Důkaz: Analogicky jako předchozí věta, důkaz přidání sloupce či řádku, který obsahuje pouze minimální prvky, lze provést přímým ověřením Mongeovské vlastnosti. Věta 5: Všechny submatice dané Mongeovské matice jsou také Mongeovské Důkaz: Přímo vyplývá z Mongeovské vlastnosti (2). Věta 6: Do libovolné Mongeovské matice lze přidat jeden či více řádků a jeden či více sloupců, které obsahují pouze minimální prvky. Důkaz: Vyplývá z Věty 4. Věta 7: Z libovolné Mongeovské matice typu (m, n), kde , respektive , lze odstanit řádek respektive sloupec, skládající se pouze z minimálních prvků a daní matice po této operaci zůstává Mongeovská. Důkaz: Vyplývá z Věty 5. Věta 8: Průnik libovolných Mongeovských matic je opět Mongeovská matice. Důkaz: Vyplývá z Věty 3. Konstrukce Mongeovských matic v max – min algebře V této kapitole bude popsána konstrukce Mongeovských matic, a to nejprve v binárním případě, který bude dále rozšířen na matice, které obsahují 3 různé hodnoty, i na zcela obecné Mongeovské matice Konstrukce binárních Mongeovských matic Binární Mongeovské matice lze konstruovat na základě Věty 2 tak, že prvky 0 umístíme konvexně kolem levého horního a pravého spodního rohu a zbytek matice doplníme jedničkami. Nakonec můžeme za základě Věty 4 přidat jeden či více řádků a jeden či více sloupců, obsahujících pouze minimální prvky.
Konstrukce Mongeovských matic, obsahujících prvky 0, 1, 2 Mongeovské matice, obsahující 3 různé prvky (například 0, 1, 2), se konstruují podobně jako binární Mongeovské matice. Nejprve umístíme nuly konvexně kolem levého horního a pravého spodního rohu matice, zbývajícími prvky 1 a 2 je potřeba pokrýt zbytek matice. Zbytek si rozdělíme na obdélníkové matice, které mají neprázdné průniky a tyto matice nyní zaplníme prvky 1 a 2. Začneme například seshora – první matici vyplníme stejným způsobem jako matici binární, čímž máme vyplněn i první průnik. Dále doplníme druhou matici (má předvyplněný průnik) a takto pokračujeme až do úplného pokrytí matice. Nakonec lze přidat jeden či více řádků a jeden či více sloupců, obsahujících pouze minimální prvky. Konstrukce obecných Mongeovských matic Konstrukce obecných Mongeovských matic je pouze rozšířením předchozích případů, lze ji provádět na základě následujícího algoritmu: 1. Umístíme minimální prvek konvexně kolem levého horního a pravého spodního rohu 2. Dále pokryjeme zbytek matice obdélníkovými submaticemi s neprázdnými průniky. V těchto maticích opět umístíme druhý nejmenší prvek konvexně kolem levého horního a pravého spodního rohu, musíme přitom dodržovat předvyplněné průniky jednotlivých obdélníkových matic. 3. Krok 2 opakujeme do té doby, než zbudou pouze 2 poslední prvky, které vyplníme jako u Mongeovské matice. 4. Nakonec lze přidat řádky či sloupce, obsahující pouze minimální prvky Literatura [6] Butkovič, P., Zimmermann K.: A strongly polynomial alg. for solving two-sided system of (max, plus)-linear equations. Disc. Appl. Math 154 (2006), 437-446. [7] Cunninghame-Green, R. A.: Minimax Algebra. Lecture Notes in Economics and Mathematical systems 166, Springer-Verlag, Berlin, 1979. [8] Gavalec, M., Zimmermann K., Solving systems of two sided (max,min)-linear equations, Kybernetika 46 (2010), 405-414. [9] Gavalec, M., Plavka, J.: Structure and dimension of the eigenspace of a concave Monge matrix, Disc. Appl. Math. 157 (2009), 768-773. Mgr. Alena Pozdílková Univerzita Hradec Králové, Fakulta informatiky a managementu Rokitanského 62, 500 03 Hradec Králové, Česká republika e-mail: [email protected]
Název: Letní škola „Mezioborové přístupy informatiky a kognitivní vědy“ Druh publikace: Recenzovaný sborník 1. ročníku letní školy Editor: prof. RNDr. Josef Zelenka, CSc. Počítačová sazba: Ing. Hana Šafránková Rok a místo vydání: 2011, Brno Náklad: 100 Vydání: první Vydalo nakladatelství Tribun EU s.r.o. jako svou xxx. publikaci.
ISBN
