UMĚLÁ INTELIGENCE 2. Cvičebnice pro samostudium. Ústav Informatiky PEF MENDELU. Pracovní skupina: Modelování a vizualizace

UMĚLÁ INTELIGENCE 2

Cvičebnice pro samostudium Ústav Informatiky PEF MENDELU Pracovní skupina: Modelování a vizualizace Ondřej Popelka, Jan Žižka, Oldřich Trenz, Jiří Šťastný

Cvičebnice pro samostudium Umělá inteligence II

Obsah Obsah ................................................................................................................ 2 Úvod .................................................................................................................. 4 Motivace .....................................................................................................................4 Poučení .......................................................................................................................4 Návaznost ...................................................................................................................5 Cíl ...............................................................................................................................5 Poznámka autorů .........................................................................................................5

Metody hraní her ............................................................................................. 6 Úvod ...........................................................................................................................6 Řešení úkolu z minulé kapitoly ...................................................................................7 Piškvorky ..................................................................................................................11 Piškvorky – strategie .................................................................................................14 Piškvorky - umělá inteligence ...................................................................................16 Časová složitost ........................................................................................................18 Stavová reprezentace úlohy .......................................................................................23 Minimaxová metoda..................................................................................................29 Minimaxová metoda - vizualizace .............................................................................31

Další metody procházení stavového prostoru ............................................... 32 Úvod .........................................................................................................................32 Hledání prvního nejlepšího........................................................................................32 A* algoritmus ...........................................................................................................37 Heuristické funkce ....................................................................................................42 Algoritmy iterativního vylepšování ...........................................................................44 Kontrolní otázky .......................................................................................................46

Inteligentní agenti .......................................................................................... 47 Úvod .........................................................................................................................47 Typy agentů ..............................................................................................................52 Vlastnosti prostředí ...................................................................................................57 Multiagentní systémy (MAS) ....................................................................................62 Komunikace v MAS..................................................................................................70 Strojové učení v MAS ...............................................................................................78 Shrnutí ......................................................................................................................82 Kontrolní otázky .......................................................................................................82

Řešení problémů ............................................................................................. 85 Úvod .........................................................................................................................85 Kontrolní otázky .......................................................................................................86

Učící se algoritmy ........................................................................................... 87 Úvod .........................................................................................................................87 Evoluční algoritmy ....................................................................................................88 Genetické algoritmy ..................................................................................................89 Princip genetického algoritmu ...................................................................................91 Operace genetického algoritmu .................................................................................93 Shrnutí ......................................................................................................................98 Diferenciální evoluce ................................................................................................99 Stránka 2/122

Cvičebnice pro samostudium Umělá inteligence II Neuronové sítě ........................................................................................................ 102 Aplikace.................................................................................................................. 103 Prioritní řízení síťového prvku ................................................................................ 103 Shrnutí .................................................................................................................... 110 Kontrolní otázky ..................................................................................................... 111

Závěr ............................................................................................................. 112 Doporučené studijní zdroje ......................................................................... 113 Přílohy........................................................................................................... 114 Sbírka úloh pro samostatné vypracování.................................................................. 115 Seznam obrázků ...................................................................................................... 121 Seznam tabulek ....................................................................................................... 122

Stránka 3/122


Úvod Následující studijní text má sloužit zejména pro podporu výuky předmětu Umělá Inteligence II. Pokud studujete na PEF MENDELU a předmět nemáte zapsaný, tak si ho prosím zapište. Nenechte se zmást tím, že sem tam zde narazíte na ukázku nějakého programu, toto není text jen pro programátory. Pokud chcete vědět co je to umělá inteligence, jak se tvoří anebo vám prostě jen vrtá hlavou, proč jsou online hry tak populární, tak má smysl tohle číst. V tomto textu potkáte dva druhy kapitol. Běžné kapitoly a podkapitoly obsahují neformální popis úlohy, jejich snahou je vysvětlit věc tak, aby byla pochopitelná i za cenu toho, že se dopustíme nějakých nepřesností. Kapitoly označené písmenem F pak obsahují formální popis problému a měli byste jim věnovat pozornost, pokud se chcete danou oblastí dál zabývat (pokud je přeskočíte, tak nezoufejte, text pokračuje dál). Všechny kapitoly obsahují na konci krátké shrnutí, abyste věděli, o co přicházíte. Předtím než začneme mluvit o umělé inteligenci, měli bychom se zamyslet nad tím, co vůbec znamená slovo inteligence (doufám, že se shodneme na tom, co znamená slovo umělá). Úkol 1: Zavřete oči (anebo jděte koukat z okna — pokud máte pěkný výhled) a zkuste vymyslet nějakou definici slova inteligence. Jak vysvětlíte někomu, kdo to slovo nikdy neslyšel, co to je inteligence?

Motivace Hlavní motivací pro studium umělé inteligence je to, že nám umožňuje posouvat se dál. S umělou inteligencí se setkáváme v oblasti software — automatické překladače, zpracování obrovského množství dat (např. vyhledávání na internetu), hry a podobně. Ale také v oblasti hardware — automatické vysavače, průzkumné roboty, vojenská technika a podobně. Tato opora se snaží alespoň částečně odhalit magii, která za tím je.

Poučení Umělá inteligence je velmi komplexní a nesourodá oblast. Je zrádná v tom, že se velmi mění. Některé technologie, které před 20 lety byly vrcholem umělé inteligence, dnes najdete ve vysavači nebo v pračce. Umělá inteligence obsahuje obrovské množství metod, některé z nich jsou jednodušší, některé jsou složitější. Všechny z nich se dále vyvíjí. Umělá inteligence prostě neposkytuje příliš mnoho řešení "na klíč". Spíš než řešení na klíč očekávejte od umělé inteligence jiný pohled na věci. Umělá inteligence se snaží řešit problémy, které jinak řešit nelze. Někdy se to daří, jindy se to nedaří. Tato opora se právě snaží nabídnout cestu k tomuto pohledu a představit některé obtížně řešitelné problémy.

Stránka 4/122


Návaznost Tato opora je určena zejména pro předmět Umělá inteligence II na PEF MENDELU. Předmět Umělá inteligence II navazuje na Umělá inteligence I. Tento eLearningový kurz nemá žádné speciální prerekvizity. Čtenář by měl základní znalosti z matematiky (funkce jedné proměnné). Část opory se věnuje také programování a je proto vhodné (ale není to nutné), aby čtenář měl povědomí o tom, co je to počítačový program.

Cíl Cílem této Cvičebnice pro samostudium je neformálně představit filozofii a základní přístupy umělé inteligence co nejsrozumitelněji a bez nutnosti předchozích znalostí této oblasti. Cvičebnice je určena jak pro studenty informatických oborů a předmětů umělé inteligence, tak pro ostatní zájemce o tento obor. Chceme vysvětlit co to umělá inteligence je, k čemu je dobrá a kdy je vhodné ji použít.

Poznámka autorů Pokud najdete v textu chyby nebo nejasnosti, nebo pokud vás napadne cokoliv, čím by se dala vylepšit — neváhejte a napište nám. Cvičebnice pro samostudium je stále ve vývoji a budeme ji postupně doplňovat o další příklady a průběžně upravovat. Neboť jako distribuční forma byla zvolena elektronická distribuce dokumentu ve formátu PDF, tak jakékoliv úpravy a doplnění jsou snadnější než ve verzi tištěné. Cvičebnice pro samostudium navazuje koncepčně na eLearningové opory předmětu Umělá inteligence II – elektronická skripta, jež jsou uveřejněny ve veřejné části v rámci Informačního systému (UIS) Mendelovy univerzity v Brně (http://is.mendelu.cz/eknihovna/opory/index.pl?opora=2108). Po obsahové stránce Cvičebnice pro samostudium tvoří ucelený soubor studijních materiálů pokrývající z větší části problematiku vyučovanou v předmětu Umělá inteligence II. Kromě základního učebního textu obsahuje podklady k samostatným úkolům, projektům, taktéž kontrolní otázky a nadhledy testů. Svou podstatou je určena pro samostudium a distanční studium, potažmo po vytisknutí off-line studium, uceleně doplňuje eLearningovou oporu. Autoři doporučují, v rámci přípravy na jednotlivé partie předmětu, kontrolní testy a zkoušku používat taktéž interaktivní eLearningový materiál uveřejněný v UIS. Tato elektronická studijní opora, svým obsahem suplující elektronická skripta, obsahuje interaktivní aplikace, elektronický zkušební modul a taktéž elektronickou verzi přednášek ve formátu pptx.

Stránka 5/122


Metody hraní her Úvod V předchozí kapitole jsme použili pojem "složitá úloha", zkusíme ho nyní vysvětlit neformálně na dvou příkladech. Prvním příkladem je seřazení několika čísel (což složitá úloha není), druhým příkladem je hra piškvorky (což složitá úloha je). Pokusíme se tedy dojít k odpovědi na otázku "Jak to přijde, že něco musíme řešit pomocí umělé inteligence?". Předpokládejme na chvíli, že jsme opuštění inženýři na pustém ostrově bez internetu a snažíme se vytvořit počítač, který bude řadit celá čísla podle velikosti, nemáme k dispozici žádné existující příklady řadících algoritmů a všechny knížky o programování spálila zlá inkvizice. Úkol 2: Seřaďte ručně 5 náhodně vybraných celých čísel (0…1000) podle velikosti od nejmenšího po největší. Můžete použít buď papírovou šablonu v příloze nebo program Příklad na seřazení.exe1.

1

Program na seřazení naleznete v eLearningové opoře v UIS, sekce Metody hraní her, Řazení — řešení.

Stránka 6/122


Řešení úkolu z minulé kapitoly Při malém počtu položek (přesná hodnota je individuální, obvykle je to 5 - 20 položek) většina lidí seřadí položky jakýmsi zvláštním chaotickým způsobem, kdy téměř současně přehodí všechny kartičky s čísly na správná místa. Na obrázku dole je příklad takového seřazení.

Obrázek 1: Řazení - ruční postup.

Pokud byste vyslýchali osobu, která čísla seřadila postupem uvedeným na obrázku, obvykle se nedozvíte žádné konkrétní důvody pro její kroky. V nejlepším případě můžeme získat přibližně následující popis: 1. krok • • •

Vybral jsem 1, protože je nejmenší a dal ji na začátek. Vybral jsem 274, protože se mi zdá největší a dal jsem ji na konec. Padlo mi do oka, že 98 a 68 jsou prohozené, tak jsem je přehodil.

2. krok •

Zařadil jsem 57 na správné místo. Stránka 7/122

Cvičebnice pro samostudium Umělá inteligence II Poznámka: Všimněte si, že v jednom kroku řazení jsme provedli několik různých akcí nalezení nejmenšího čísla, nalezení největšího čísla, přehození hodnot, zařazení na správné místo (v tomto konkrétním případě až ve druhém kroku). Tohle bude za chvíli důležité. Kdybychom se pokusili tento postup naprogramovat, tak narazíme na nepřekonatelný problém. Nedokážeme přesně specifikovat výrazy „jako zdá se mi největší“ a „padlo mi do oka“. Abychom mohli vytvořit program pro seřazení čísel, musíme se pokusit najít nebo vymyslet nějaký systematický postup k řešení této úlohy. Je tedy nutné každý provedený krok zdůvodnit a najít nějaký v nich společné prvky. Velmi často (a tato úloha seřazení čísel není výjimkou) je dobré vycházet z toho, co člověk sám umí. Úkol 3: Seřaďte ručně alespoň 30 celých čísel podle velikosti od nejmenšího po největší. Můžete použít buď papírovou šablonu v příloze nebo prográmek (Příklad na seřazení.exe) v příloze. Zkuste postupovat přirozeně a přitom systematicky. Nápověda: zkuste použít takový postup, který se skládá z opakování jednoho jednoduchého neměnného kroku. Pravděpodobně se vám při splnění úkolu podařilo objevit systematický postup k seřazení čísel. Pravděpodobně je to jeden z dvou níže uvedených postupů. Pokud ne, tak nezoufejte, buď se vám podařilo objevit ještě další systematický postup, anebo se vám prostě žádný systematický postup nezjevil (v tom případě to zkuste někdy jindy, až nebude takový such.

Varianta 1 Najdeme v nesetříděném seznamu nejmenší hodnotu a vložíme ji na konec setříděného seznamu.

Obrázek 2: Postup řazení.

Varianta 2 Vezmeme v nesetříděném seznamu libovolnou položku (třeba první, ta je po ruce) a vložíme ji na správné místo. V setříděném seznamu správné místo poznáme tak, že předcházející položka je menší než vkládaná hodnota a následující položka je větší nebo rovna aktuální hodnotě.

Stránka 8/122


Obrázek 3: Postup řazení.

Obě uvedené varianty můžeme již poměrně snadno převést do procedurálního programovacího jazyka. Stejně jako na obrázcích je dobré využít dvou seznamů setříděného a nesetříděného, ale není to nutné. V pseudokódu můžeme obě varianty zapsat například takto:

Varianta 1 //vše zopakujeme tolikrát, kolik máme položek FOR i FROM 0 TO PočetPoložek //najdeme nejmenší položku //index položky s minimální hodnotou //zatím je minimální položka první Index = 0 Minimum = NesetříděnýSeznam[0] //projdeme zbytek seznamu FOR j FROM 1 TO NesetříděnýPočet //pokud je akt. položka menší IF NesetříděnýPočet[j] < Mininmum THEN //považujeme ji za nové minimum Minimum = NesetříděnýSeznam[j] //zaznamenáme index nejmenší položky Index = j //hotovo, prošli jsme celý seznam a našli nejmenší položku //smažeme ji z nesetříděného seznamu NesetříděnýSeznam.SmažPoložku(Index) //vložíme na konec setříděného seznamu hodnotu SetříděnýSeznam.PřidejNaKonec(Minimum) //celý postup opakujeme pro nějakou další položku

Varianta 2 //zopakujeme to tolikrát, kolik máme položek FOR i FROM 0 TO PočetPoložek //vezmeme první hodnotu Hodnota = NesetříděnýSeznam[0]; //projdeme setříděný seznam FOR j FROM 0 TO SetříděnýPočet //pokud je j-tá položka menší IF Setříděný[j] < Hodnota THEN //a j+1-tá položka větší IF Hodnota < Setříděný[j+1] THEN //tak mezi ně (před j+1) vložíme hodnotu SetříděnýSeznam.VložPředPrvek(J+1, Hodnota)

Stránka 9/122

Cvičebnice pro samostudium Umělá inteligence II //celý postup opakujeme pro další položku setříděného seznamu //celý postup opakujeme pro nějakou další položku

Poznámka: Pseudokód je zápis programu v neexistujícím velmi zjednodušeném programovacím jazyce, od normálního zdrojového kódu programu se liší tím, že nedodržuje řadu formálních podmínek a obsahuje pouze hrubý nástin algoritmu. Pokud jste nikdy neviděli kus programu, tak FOR i FROM 0 TO PočetPoložek znamená, že následující blok (všechno odsazené víc něž aktuální řádek) se provede pro každou hodnotu i od 0 do PočetPoložek a IF něco THEN znamená, že následující blok se provede, pouze pokud je splněno něco. Uvedený příklad s řazením je ukázka toho, jak lze řešení nějakého problému, které zvládne každý inteligentní člověk, převést do postupu (algoritmu), který lze naprogramovat. V tomto případě sice algoritmus není příliš efektivní (provede spoustu zbytečných operací), ale to nás teď nemusí trápit. Poměrně snadno se můžeme přesvědčit, že lze seřadit libovolná data a můžeme takto v principu naprogramovat vcelku libovolný stroj. Zásadním problémem je to, že ne každý problém lze takto řešit. Tedy existují úlohy, které sice každý inteligentní člověk zvládne vyřešit, ale přesto pro ně není možné (nebo se to zatím nikomu nepovedlo) vytvořit algoritmus, a následně potom počítačový program, který bude tyto úlohy řešit. Velmi jednoduchým příkladem takové úlohy je hra piškvorky. Tuto hru se většina lidí bez problémů naučí hrát na prvním stupni základky, přesto udělat počítačový program, který bude hrát alespoň tak dobře jako průměrný člověk je téměř neřešitelný problém.

Stránka 10/122


Piškvorky Začneme s jednoduchou hrou piškvorek na hrací ploše 3×3. Průběh hry dvou schopných hráčů pak bude vypadat přibližně takto:

Obrázek 4: Hra piškvorky, rozehráno.

Když v hrací ploše označíme sloupce písmeny a řádky čísly, můžeme popsat tahy uvedené na obrázku jako: • •

X (první hráč): B2, A1, B3, C2, C1 O (druhý hráč): A3, C3, B1, A2

Obrázek 5: Piškvorky – šachovnice.

Pokusíme se nyní prvního hráče nahradit počítačem. Podobně jako v předchozím příkladu je nejprve nutné zdůvodnit každý krok a objasnit průběh hry. Pokud bychom se zeptali hráče – člověka, dostali bychom vysvětlení podobné následujícímu: 1. Táhl jsem na B2, protože první tah doprostřed bývá nejvýhodnější. 2. Táhl jsem na A1, protože tah na rohové pole vede k výhře (resp. tah na ne-rohové pole vede k prohře). 3. Táhl jsem na B3 pro zablokování řady protihráče. 4. Táhl jsem na C2, protože odsud lze ještě vytvořit řadu. 5. Táhl jsem na C1, protože to je poslední volné pole. 6. (Táhl jsem „dopryč“, protože piškvorky jsou pro malá děcka) Stránka 11/122

Cvičebnice pro samostudium Umělá inteligence II Všimněte si, že na rozdíl od předchozího příkladu s řazením, zde na první pohled nemáme žádné neurčité informace ve stylu – protože mi padlo do oka?. Nicméně v uvedeném postupu se vyskytují znalosti. Například první tah na střed hrací plochy – každý ví, že je to tah obecně nejvýhodnější a hráč, který začíná, o tomto tahu zpravidla nepřemýšlí, ale hraje automaticky. Dalším velmi významným rozdílem oproti předchozímu příkladu je to, že nemáme přesně dán – správný – konec hry. V příkladu s řazením je jednoznačně definováno v jakém pořadí mají položky po skončení řazení být. V případě piškvorek existuje několik koncových stavů hrací plochy, které jsou pro hráče výhodné, nebo přinejmenším přijatelné (remíza). Dále je zřejmé, že naše rozhodování je závislé na aktuálním stavu hrací plochy – tedy na tazích protihráče. Jedná se o „online“ úlohu – nelze dopředu shromáždit všechna data a pak vypočítat řešení. Chování hráče tedy nelze popsat jako jednoduchou posloupnost kroků: B2, A1, B3, C2, C1, přesto z cvičných důvodů ukážeme program, který by takto hrál piškvorky.

Tah(B2) IF Volno(A1) THEN Tah(A1) ELSE IF Volno(B3) THEN Tah(B3) ELSE IF Volno(C2) THEN Tah(C2) ELSE IF Volno(C1) THEN Tah(C1) ELSE Chyba(‘Nevím kam táhnout dál ‘)

U předchozího příkladu s řazením jsme takovýto postup ani neuvažovali, protože považujeme za zřejmé, že instrukcemi typu – přesuň pátou položku před druhou – nelze seřadit náhodně vytvořenou posloupnost čísel. Stejně tak uvedeným naivním algoritmem nelze dobře hrát piškvorky. Uvádíme ho ze dvou důvodů: 1. Představuje častou začátečnickou chybu – pokud někdo začne řešit složitou úlohu bez přemýšlení, obvykle se jí snaží vyřešit použitím analogie. Vyřeší nejprve tedy úlohu na jednoduchém případu a pak se snaží analogicky řešit složitější varianty. V následujících odstavcích ukážeme, proč to u složitých úloh obvykle nevede k cíli. 2. Pokud se vcítíte do role začátečníka, tak zjistíte, že uvedený algoritmus nehraje zase tak špatně, neboli začátečník (v tomto případě se to rovná dítěti předškolního věku) nerozpozná, že hraje se strojem a nikoliv s člověkem. Z pohledu teorie nám toto ukazuje slabinu Turingova testu. Z pohledu praxe to znamená, že pokud se snažíme řešit složitou úlohu, musíme ji sami umět poměrně obstojně řešit (respektive musíme mít někoho, kdo nám to zkontroluje). Jinak hrozí, že nerozpoznáme, že se vytvořený program chová idiotsky. Stránka 12/122

Cvičebnice pro samostudium Umělá inteligence II Úkol 4: Použije program Piškvorky1 a vyzkoušejte si zahnat program do úzkých (nebo uvedený algoritmus).

Pokročilejší úkol pro informatiky: Zkuste přidáním několika podmínek upravit algoritmus tak, aby se tak snadno nedal zahnat do úzkých.

Poznámka: Řešení naleznete v eLearningové opoře v UIS, v sekci Metody hraní her, Piškvorky1 – naivní řešení, Piškvorky1 – naivní řešení (zdrojový kód).

Stránka 13/122


Piškvorky – strategie Slabina předchozího algoritmu je nepochybně v tom, že nevyužívá žádným způsobem znalosti o problému, které se vyskytují v postupu pozorovaného u lidského hráče, ale pouze tento postup tupě reprodukuje. Výhodnější je tedy tyto znalosti využít a pokusit se je navíc ještě nějakým způsobem zobecnit. Podívejme se na následující strategii: 1. 2. 3. 4. 5. 6.

Tah na střed Tah na roh, kde je volná diagonála Pokud můžeme dokončit řadu, dokončeme ji Pokud může protihráč dokončit řadu, zablokujme ji Tah na hranu, kde zablokujeme protihráče a současně můžeme vytvořit řadu Tah na volnou hranu, pokud není volná hrana, tah na roh.

Tuto strategii můžeme převést do postupu, který se dá zapsat následujícím pseudokódem: IF PrvníTah THEN Tah(B2) ELSE IF DruhýTah THEN // máme provést druhý tah - najdeme volnou diagonálu IF Volno(A1) AND Volno(C3) THEN // je volné pole A1 i pole C1 Tah(A1) ELSE Tah(A3) ELSE IF TřetíTah THEN IF Soupeř(A1) THEN // musíme blokovat soupeře tahem na stranu IF Soupeř(A3) THEN Tah(A2) ELSE IF Soupeř(C1) THEN Tah(B1) ELSE IF Soupeř(C3) THEN // musíme blokovat soupeře tahem na stranu IF Soupeř(A3) THEN Tah(B3) ELSE IF Soupeř(C1) THEN Tah(C2) IF TahNeProveden THEN // nenašli jsme soupeřovu nedokončenou řadu, soupeř táhl špatně IF Můj(A1) THEN //vlastníme pole A1, dokončíme diagonální řadu Tah(C3) ELSE Tah(C1) ELSE //čtvrtý tah //podle předchozího tahu zkusíme vždy nejprve dokončit vodorovnou nebo svislou řadu, potom //zkusíme tah na stranu, kde je poslední možnost vytvořit řadu, pro každý směr je jedno pravidlo IF PředchozíTah = A2 THEN IF Volno(C2) THEN

Stránka 14/122

Cvičebnice pro samostudium Umělá inteligence II Tah(C2) ELSE Tah(B1) ELSE IF PředchozíTah = B1 THEN IF Volno(B3) THEN Tah(B3) ELSE Tah(C2) ELSE IF PředchozíTah = B3 THEN IF Volno(B1) THEN Tah(B1) ELSE Tah(A2) ELSE IF PředchozíTah = C2 THEN IF Volno(A2) THEN Tah(A2) ELSE Tah(B3)

Přestože se to na první pohled nezdá, je druhý program o mnoho lepší než první. Zejména proto, že nyní algoritmus reaguje na jednotlivé stavy hrací plochy, zatímco první program reprezentoval pouze tupou sekvenci kroků v jedné hře. Kromě toho nyní postupujeme podle nějaké obecné strategie a ne pouze podle analogie s nějakou odehranou partií. Také se tento program chová na hrací ploše 3×3 poměrně inteligentně (i když má stále své mouchy). Čili, právě jsme vytvořili umělou inteligenci, i když zatím dost hloupou. Podstatné je zde však to, že se nám nepodařilo (zatím se to nepodařilo nikomu na světě) převést řešení hry piškvorky na stále se opakující sekvenci jednoduchých kroků tak, jako jsme to poměrně snadno dokázali při řešení úlohy o řazení. Praktickým důsledkem je to, že délka programu pro piškvorky roste se složitostí úlohy (velikostí hracího pole). Analogie v případě řadícího algoritmu by byla, že by pro delší seznam čísel byl potřeba delší program. To samozřejmě není pravda (bylo by to hodně nepraktické), kterýmkoliv z programů v kapitole 2.1 můžeme řadit libovolný seznam, pouze budeme déle čekat. Uvedený program je na první pohled docela složitý (je potřeba si uvědomit, že je to navíc jen pseudokód, čili skutečný program je o mnoho složitější) a přitom stále nepokrývá všechny možnosti, které ve hře můžou nastat. Navíc ve výše uvedeném postupu chybí poslední tah, ve skutečném programu v úkolu je i poslední tah ošetřen. První program, který jsme napsali je schopný provést 5 různých tahů, druhý pseudokód postihuje 17 možných tahů počítače, ve skutečném programu (piskvorky2) je celkem ošetřeno celkem 27 tahů a algoritmus zabírá přibližně 90 řádků zdrojového kódu. Úkol 5: Program piškvorky2 zahrnuje 27 stavů hrací plochy (a hraje poměrně slušně), kolik existuje ve hře možných tahů pro počítač, za předpokladu, že začíná?

Poznámka: Řešení naleznete v eLearningové opoře v UIS, v sekci Metody hraní her, Piškvork1 – strategie. Stránka 15/122


Piškvorky - umělá inteligence Řešení úkolu z předchozí kapitoly je pro další text velmi významné. Pokud jste ho lenivě přeskočili, tak se k němu zkuste vrátit a zapřemýšlet, je to opravdu důležité. Počet tahů se dá odvodit všelijak, asi nejjednodušší varianta vede přes stavy hrací plochy – spočítáme, co se vůbec může na hrací ploše objevit. Prázdná hrací plocha obsahuje 9 prázdných políček, tedy v prvním tahu se počítač musí rozhodnout mezi 9 tahy. Po prvním tahu člověka zbude v ploše 7 prázdných políček. Vzhledem k tomu, že obecně záleží na pořadí, v jakém jsou tahy provedeny, tak v prvních dvou krocích může počítač provést 9.7 tahů. Celkem může počítač hrát 9.7.5.3.1 = 945 tahů. Nebo 105 tahů, pokud je první tah daný (v našem případě je první tah pevně daný doprostřed a žádné rozhodování neřešíme). Odpověď na otázku v úkolu je tedy 945 (nebo 105, nebo ještě něco jiného – viz dále). Je podstatné, že pro zpracování tohoto množství (945) tahů nám stačí v programu definovat pouze kolem 30 tahů, tedy přibližně 3 % (program piškvorky 2 není dokonalý a je nutné do něj některé možnosti ještě doplnit). Toto silné zjednodušení (ve smyslu ulehčení) úlohy je možné, protože řešenou úlohu známe velmi dobře a známe strategii vedoucí k výhře. Současně jsme také vyčíslili efektivitu uvedené strategie – když půjdeme na piškvorky 3×3 „od lesa“, stačí nám udělat jen 3 % práce a máme hotovo. To, že dobrá strategie věci hodně zjednodušuje, platí velmi obecně pro jakýkoliv problém. Vykřičník značí funkci faktoriál, faktoriál 5 se značí 5! a je to 5! = 5 . 4 . 3 . 2 . 1 Pro úspěšné zvládnutí hry je však ještě nutné ošetřit jednotlivé stavy hrací plochy v případě, že začíná člověk. V obou variantách hry existuje 9 . 8 . 7 . 6 . 5 . 4 . 3 . 2 . 1 = 9! = 362 880 . Ve skutečnosti některé kombinace tahů nejsou možné, protože hra skončí, ve hře tedy existuje 255 168 tahů. S využitím symetrie a dalších strategických zjednodušení je možné toto číslo snížit přibližně na 26 830. Prakticky však existuje pouze 1 145 „realistických“ tahů, které může normální zkušený hráč udělat. K jinému zjednodušení hry můžeme dojít díky tomu, že se soupeři střídají, tedy počítač je buď sudý, nebo lichý hráč (nikdy nemůže hrát jako oba současně). Pokud se budeme držet předchozího schématu algoritmu, kdy nezkoumáme tah protihráče, ale pouze na dané hrací ploše hledáme co nejlepší tah, je možné algoritmus rozdělit a pak stačí zpracovávat pouze 9 . 7 . 5 . 3 . 1 + 8 . 6 . 4 . 2 = 945 + 384 = 1329 tahů (ve skutečnosti opět o něco méně protože hra může být dokončena dříve, než se hrací plocha zaplní). Tento možná až zdlouhavý rozbor hry piškvorky demonstruje několik důležitých věcí. První věc, která snad i někoho překvapí je časová složitost (rychlost, s jakou roste celkový počet tahů) této primitivní hry. Vzhledem k tomu, že počet kombinací tahů roste faktoriálem, tak přestože pro hrací plochu 3×3 dostaneme ještě poměrně stravitelných 362 880 kombinací, pro Stránka 16/122

Cvičebnice pro samostudium Umělá inteligence II hrací plochu 4×4 je to 16! ≈ 20 922 789 888 000 hrací plochu 4×4 je to 16! ≈ 2 0 922 789 888 000 ≈ 2,09 . 1013 kombinací a pro hrací plochu 5×5 je to 15! ≈ 15 511 210 043 330 985 984 000 00 0 ≈ 1,55 . 1025 kombinací. V případě, že by šlo jednotlivé tahy od sebe oddělit a bylo by nutné v programu zpracovat opět pouhá 3 % tahů (což není vůbec jisté) dostaneme 25 . 23. 21 … 1 + 24 . 22 . 20… 2 = 7,90.1012 + 1,96 . 1012 ≈ 9,9 . 1012 , celkem tedy 9,9 . 1012 . 0,03 = 2,9 . 1011 tahů. To je sice o hodně méně než celkový počet kombinací (zhruba o 14 řádů), ale program, který bude mít 290 miliard řádků kódu je trošku náročný na údržbu. Mimochodem čtverečkovaný papír A5 má přibližně 42. 30 = 1260 polí, což představuje zhruba 1,6 . 103361 kombinací. Poznámka: Pokud se vám 16! pořád nezdá jako dost velké číslo, tak ho zkusme převést do praxe. Pokud bychom všechny stavy hrací plochy chtěli někam uložit a velmi optimisticky budeme předpokládat, že nám na uložení hrací plochy bude stačit jeden bajt (přestože hrací plocha má 16 políček a bajt má pouze 8 bitů), tak 20 922 789 888 000B = 20 432 412 000 KB ≈ 19 953 527 MB ≈ 19 485 GB ≈ 19,5TB. Největší HDD, který pořídíte v době psaní tohoto textu je 1TB, a to máme hrací plochu jen 4×4? Druhým velmi významným poznatkem je to, že počet skutečně zpracovávaných tahů se dá radikálně snížit, pokud známe dobré strategie, nebo obecněji, pokud máme o řešeném problému dobré znalosti. Problém je v tom, že znalosti, které jsme využili pro řešení hry 3×3 nejsou příliš využitelné pro hry na větším poli, kde se počítá s delšími řadami koleček nebo křížků. Třetím důležitým bodem je kombinace obou předchozích. Pokud se rozhodneme programovat piškvorky, máme na výběr mezi špatným a ještě horším. Buď použijeme algoritmus, který v sobě nese znalosti o problému a jistou strategii, ale zvětšuje se pro každé přidané pole do hrací plochy, což znamená, že jej pro větší hrací plochy nelze použít. Anebo použijeme algoritmus, který problém bude zkoušet všechny možnosti (řešení „hrubou silou“), který však pro jeho paměťovou a výpočetní náročnost nelze použít pro větší hrací plochy. Poznámka: Tato kapitola obsahuje jednu velmi závažnou radu do života, která zní: „Nezatracujte teorii“. Všimněte si, že naivní programátor (který patrně zvolí stejnou cestu jako my) začne programovat hru pro hraní piškvorek a jak bude zkoušet nové a nové hry (případně zvětšovat hrací plochu), bude stále zvětšovat svůj algoritmus a stále mu bude připadat, že je to „skoro hotové“, až do okamžiku kdy se v tom naprosto ztratí a bude vyhozen z práce a umře hlady, protože nedostane podporu v nezaměstnanosti. Krátkou (a nepřesnou – viz příslušné odkazy) úvahou o počtu tahů jsme došli k tomu, že prezentovaný přístup je pro větší hrací plochy od začátku odsouzen k neúspěchu a řešení vyžaduje úplně jiný přístup (umělou inteligenci).

Stránka 17/122


Časová složitost V předchozích kapitolách byly použity pojmy časová složitost a složité úlohy, v této kapitole se je pokusíme přesněji definovat. Paměťová náročnost/složitost (space complexity) jsou paměťové (přičemž nerozlišujeme mezi dočasnou a trvalou pamětí) nároky programu jako funkce velikosti vstupu. Velikost vstupu je například v případě řadícího algoritmu počet položek, které se mají seřadit.

Časová složitost (time complexity) je nejdelší čas výpočtu, který algoritmus zabere při vstupu velikosti n. Čas výpočtu při nejméně příznivém vstupu je funkcí velikosti vstupu f (n). Co je příznivý a nepříznivý vstup? Například u řadícího algoritmu záleží na tom jak moc je seznam „rozházený“. Pokud stačí přehodit jedinou položku, je to příznivý vstup. Pokud je potřeba provést velké množství operací, aby se seznam seřadil, pak je to nepříznivý vstup. Přesné určení funkce f(n) může být velmi složité, proto se při hledání funkce zaměřujeme na dominantní složky funkce, které pro velká n reprezentují téměř celý čas výpočtu a funkci f(n) nahradíme jednoduší funkcí g(n) – odhadem časové složitosti. Odhad časové složitosti se určuje Θ-notací nebo O-notací. Théta notace (Θ-notace) je asymptotická horní nebo dolní mez časové složitosti algoritmu: řekneme, že f (n) = Θ (g(n)) to znamená, že f(n) se asymptoticky blíží k funkci g(n) , pokud platí: c1 , c2 , n 0 > 0 : ∀ n ≥ n0 ( 0 ≤ c1 g (n) ≤ f(n) ≤ c2 g (n)) . Přeloženo do češtiny to znamená, že existuji () nějaké hodnoty c1, c2, a n takové, že pro libovolné n větší jak 0 (velikost vstupu) platí, že hodnota funkce f (n) je vždy větší než hodnota funkce g (n) vynásobená konstantou c1 a současně menší než hodnota funkce g(n) vynásobená konstantou c2. Například dejme tomu, že čas výpočtu závisí na velikosti vstupu funkce f(n) = 4.n, tuto „složitou“ funkci nahradíme odhadem – Jednodušší funkcí g(n) = n.2 . Nyní musíme ověřit, že je výše uvedená podmínka splněná. Zkusíme proto najít nějaké konstanty c1, c2 pro které platí. Dejme tomu c1 = 2 a c2 = 7 . Podmínka je splněna, výsledek je vidět na obrázku dole, tedy funkce f(n) je omezena funkcemi c1 g(n) a c2 g(n) , tedy funkce f(n) se asymptoticky blíží k funkci g(n).

Stránka 18/122


Obrázek 6: Odhad časová složitost

Požadujeme, aby hodnoty f(n) a g(n) byly nezáporné, protože se jedná o počet (respektive odhad počtu) operací. Vzhledem k tomu, že prakticky může být obtížné najít funkci g(n), která funkci f(n) omezuje shora i zdola současně (jejíž násobky reprezentují asymptotickou horní i dolní mez), soustřeďujeme se častěji pouze na asymptotickou horní mez. Koneckonců zajímáme se o nejhorší možný stav – tedy: 1. horní mez – nejdelší čas algoritmu v nehorším možném případě – pro nejhorší možná data bude algoritmus hotov nejpozději za čas X 2. dolní mez – nejkratší čas algoritmu v nejhorším možném případě – tedy pro nejhorší data bude algoritmus hotov nejdříve za čas X Horní mez je často prakticky užitečnější, proto se používá O – notace (Order notation, Big O notation). Řekneme, že f (n) = O(g(n)) (f(n) se asymptoticky zdola blíží ke g(n)), pokud c , n0 >0 : ∀ n ≥ n 0 ( 0 ≤ f ( n ) ≤ c . g (n)) . Když se f(n) blíží zdola ke g(n), tak g(n) je tím pádem horní mez pro f(n). Pro O-notaci platí: 1. O-notace je reflexivní, tj. f(n) = O(f(n)) . 2. O-notace je tranzitivní, tj. jestliže x(n) = O(y(n)) a y(n) = O(z(n)) , pak x(n) = O(z(n)) . 3. Konstanty, kterými se násobí celý výraz, lze zanedbat, například 0,5 ve výrazu 0,5 . ( n 2 − n ) . 4. O-notace je multiplikativní, tj. jestliže a(n) = O(x(n)) a b ( n ) = O ( y ( n ) ) , pak a(n) . b(n) = O(x(n) . y(n )) . Stránka 19/122

Cvičebnice pro samostudium Umělá inteligence II 5. Všechny logaritmy rostou stejně rychle, to znamená, že log a n = O ( log b n ) a log b n = O ( log a n ) . 6. Jestliže f (n) je polynom stupně k, pak f (n) = O(n k) (O-notace součtu je rovna nejrychleji rostoucímu sčítanci), tedy například O(n2+45n+3 = O(n2) . 7. Vyšší mocnina n roste rychleji než nižší mocnina n, tj. O(n 3) > O( 2) . 8. Exponenciální funkce roste rychleji než mocninná funkce, tj. O(kn) > O( n k ) . 9. Kladná mocnina n roste rychleji než logaritmus n, tj. O(n2) > O (ln n) . Z uvedených pravidel lze sestavit následující orientační hierarchii rychlostí růstu různých funkcí: O(1) < O( log n ) < O() < O (n . log n) < O ( n 2 ) < O (n 3 ) < … < O ( n k ∈ ℕ +) < O (2n) < O(n!) Následující obrázky ukazují totéž graficky.

Obrázek 7: Znázornění časové složitosti zvolené funkce.

Stránka 20/122


Obrázek 8: Znázornění časové složitosti zvolené funkce.

Oba řadící algoritmy uvedené v předchozí kapitole mají časovou složitost v nejhorším případě O(n2) . Je to dané tím, že algoritmus se skládá ze dvou vnořených cyklů a každý z nich se provede v nejhorším případě n-krát a . n ? n = n 2 Pro insert-sort řazení je nejhorším případem situace, kdy je vstupní seznam seřazen v opačném pořadí, než je požadováno. Možná se teď zdá, že je to spousta pouček bez reálného využití, ale hned vysvětlíme k čemu to celé je. Podstata určování časových složitostí je v tom, že nám dávají alespoň řádovou představu o tom, jak se bude program chovat. Dejme tomu, že jsme právě vytvořili nějaký program, který implementuje insert-sort algoritmus. Zkusíme ho spustit na testovacím seznamu, který má 100 položek, tedy n = 100. Zjistíme, že program řadil 0,001 sekundy, tedy 1ms. Nyní chceme vědět, jak dlouho bude program řadit 1 000 000 položek. Pokud má program časovou složitost O(n2), tak to znamená, že pro seřazení 100 položek provede 100 2 = 10 000 operací. Jedna operace v průměru trvá 0,001 / 10 000 = 1 . 10 -7 s . Pro 1 000 000 položek je potřeba provést 1 000 000 2 = 1 . 10 12 operací, celkový čas bude v nejhorším případě 10 . 7 . 10 12 = 105 =100 000 s ≈ 1 667 min ≈ 28 h . Překvapivé? Musíte si uvědomit, že procesor počítače provádí operace a je tedy nutné počítat čas jedné operace, nikoliv čas jedné položky a dále že počet operací roste s počtem položek nelineárně. Současně si všimněte, že nás až tak

Stránka 21/122

Cvičebnice pro samostudium Umělá inteligence II nemusí trápit, že jsme spoustu věcí zanedbali, podstatné je, že algoritmus poběží řádově hodiny a nikoliv milisekundy. Poznámka: Pro zajímavost se podívejme, jak dlouho by milion položek řadil algoritmus s časovou složitostí n!. Dejme tomu, že pro 100 položek je čas stejný -0,001 sekundy (to znamená, že implementace je mnohem rychlejší, protože dokáže za stejný čas místo 104 operací provést 10157 operací), čas na operaci je tedy ( 10-3 / 100 ! ) a celkový čas je tedy ( 103 / 100 ! ) . 1 000 000 = 10-3 . 10157 . 1055654538 s = 10 55654538 let… Vzhledem k tomu, že stáří vesmíru je snad něco kolem 1010 let, tak až půjde vesmír do důchodu tak na našem progressbaru možná bude svítit „0,1 % hotovo, čekejte prosím“. Vesmír našemu skvělému faktoriálnímu algoritmu jistě s radostí zamává, udělá: „pop“ a zmizí. No snad je teď jasné, proč se faktoriál značí vykřičníkem, když člověk vidí ty čísla tak mu nezbývá nic jiného než křičet.

Stránka 22/122


Stavová reprezentace úlohy Úvod Tato kapitola se zaměřuje na jeden z nejpoužívanějších způsobů řešení složitých úloh v rámci umělé inteligence. Jedná se o transformaci libovolné úlohy do stavového prostoru. Při řešení úlohy pak pracujeme pouze se stavy a s přechody mezi stavy – jedná se tedy o abstrakci od původního problému. Velká část umělé inteligence se pak soustředí „pouze“ na to, aby v prohledávaném prostoru nalezla co „nejlepší“ řešení. Na prohledávání stavového prostoru jsou založeny například všechny metody popsané v kapitole Učící se algoritmy.

Stavový prostor V kapitole 2 jsme prezentovali některé možné přístupy pro vytvoření „inteligentního“ programu pro hraní piškvorek. Všimněte si, že pro hrací plochu 3×3 se nejedná v zásadě o nic složitého a vystačíme si s několika podmínkami. Žádná magie ani mnozí efektové se nekonají a nehledejte ji. Současně jsme také ukázali, že oba (programování strategie a řešení hrubou silou) uvedené naivní přístupy jsou prakticky nepoužitelné pro větší hrací plochy. Zmiňujeme se o tom znovu, protože toto je velmi častá chyba při uvažování o složitých úlohách. Je nutné si uvědomit, že to, že program funguje na jedné konkrétní instanci problému, ještě zdaleka neznamená, že ho lze použít na libovolnou instanci problému. Programátoři o takových programech říkají, že nejsou škálovatelné (anglicky „program does not scale“), protože to je neduh, který může potkat libovolný – nejen „inteligentní“ program. Nicméně v oblasti umělé inteligence se s ním setkáváme velmi často. To je způsobeno tím, že umělá inteligence řeší obtížně řešitelné složité úlohy. Pro inteligentního člověka toto bývá až nepochopitelné, protože lidské myšlení je ve škálování velmi dobré. Současně platí, že pokud algoritmus není škálovatelný tak s ním nic zvláštního nenaděláme – optimalizací programu se nároky dají snižovat o procenta, možná o desítky procent, ale pokud se potřebujeme posunout o řády, musíme použít úplně jiný přístup. Definice: Instance problému – jedna konkrétní podoba jedné konkrétní úlohy. Například hraní piškvorek 3×3 v případě, že začínáme, je jedna instance problému hraní piškvorek. V kapitole 2 jsme již několikrát použili pojem stav hry (respektive stav hrací plochy). Stavem hrací plochy rozumíme jednu konkrétní libovolnou kombinací křížků, koleček a prázdných polí. V předchozí kapitole jsme také ukázali, že počet stavů hrací plochy roste s faktoriálem počtu hracích polí. Pokud vezme v úvahu celou množinu stavů hry, tak zjistíme, že pouze mezi některými z nich existují přechody. Přechod mezi stavy reprezentuje nějakou akci, která umožňuje transformovat jeden stav na druhý – v případě piškvorek jsou přechody mezi stavy

Stránka 23/122

Cvičebnice pro samostudium Umělá inteligence II jednotlivé tahy hráčů. Přechody mezi stavy mají pevně daná pravidla (vycházející z pravidel hry jako takové): 1. hráči se v tazích střídají 2. lze táhnout pouze na prázdné pole 3. umístěnou značku nelze změnit/odebrat Z těchto pravidel přechodů mezi stavy lze vytvořit graf stavů hry. Grafem myslíme to, co popisuje teorie grafů, tedy objekt, který se skládá z vrcholů (uzlů) a hran. Grafy se používají k modelování a abstrakci mnoha různých problémů, grafem je možné reprezentovat například dálniční síť republiky, organizační strukturu společnosti, plán stavby budovy a podobě.

Stránka 24/122


Obrázek 9: Ukázka grafové struktury, uzly jsou stanice, hrany jsou trasy mezi každými dvěma stanicemi.

Stránka 25/122

Cvičebnice pro samostudium Umělá inteligence II V případě hry piškvorky jsou uzly grafu tvořeny jednotlivými stavy hrací plochy a hrany odpovídají přechodům mezi stavy, tedy jednotlivým tahům (viz Obrázek 10). Na obrázku je znázorněna část grafu hry piškvorky, pokud začíná hráč s křížky (počítač). Zcela identický graf bychom získali, pokud by začínal hráč s kolečky, pouze by byly značky přehozené (resp. k jednotlivým stavům bychom dospěli v jiném pořadí).

Obrázek 10: Rozklad hracího pole u hry piškvorky.

Vzhledem k pravidlům hry má graf hry jistý přesně daný tvar, který se nazývá stromový graf. Toto grafové zobrazení má řadu výhod, protože má řadu známých vlastností a dobře se s ním pracuje. Musíme zdůraznit, že možnost reprezentovat hru stromovým grafem není automatická, ale vyplývá z pravidel této hry. Zejména pravidlo, že již umístěné značky nelze měnit je z tohoto pohledu velice významné. Například hru šachy nebo go a množství dalších her nelze reprezentovat stromovým grafem (přesněji ne konečným stromovým grafem), a musí se pro ně používat obecnější a složitější struktury (a pochopitelně i složitější varianty dále popsaných algoritmů). Než se dostaneme k tomu, jak nám tato změna přístupu pomůže při programování strategického chování, musíme uvést některé pojmy pro tento model hry a současně se podíváme na vlastnosti stavů hrací plochy, které z této reprezentace vyplývají. Prázdná hrací plocha představuje kořen grafu, stromový graf obsahuje vždy pouze jeden kořenový vrchol. Tahem na A1 (transformací stavů) můžeme přejít do zvýrazněného stavu, zvýrazněný stav je následovník (potomek) kořenového stavu. Předchůdce (rodič) zvýrazněného stavu je Stránka 26/122

Cvičebnice pro samostudium Umělá inteligence II kořenový uzel grafu. Potomek libovolného uzlu má hloubku o jednu větší než je jeho předchůdce, kořen grafu má hloubku 0. V případě aktuálně používané reprezentace má každý uzel pouze jednoho předchůdce a počet následovníků každého uzlu se zmenšuje o dva. V hloubce 0 máme tedy jeden vrchol; v hloubce 1 je to 9 vrcholů pro každý uzel, celkem tedy 9; v hloubce 2 je to 7 vrcholů pro každý uzel, celkem tedy 63 vrcholů v hloubce 2. Jak probíhají jednotlivé tahy hry, tak se mění aktuální stav hry, hloubka aktuálního stavu se s každým tahem zvětší o 1. Časový průběh hry odpovídá hloubce stavu v grafu, můžeme tedy říct například, že druhý tah počítače leží v hloubce 3. Nyní jsme vytvořili jistý popis (model, abstrakci) celé libovolné partie hry piškvorky a na tomto popisu můžeme postavit zcela odlišný postup pro řešení této úlohy. Podstatu tohoto postupu můžeme shrnout do věty: „Snažíme se najít co nejlepší stav, do kterého můžeme z aktuálního stavu přejít“. Úlohu jsme tedy převedli na problém jak určit nejlepšího následníka aktuálního stavu. Přestože se může na první pohled zdát, že se jedná jen o nějaké slovíčkaření a že to na podstatě úlohy nic nemění, opak je pravdou (viz kapitola 4.2) Obecná formulace problému, ze které se vytratil jakýkoliv odkaz na hru piškvorky, není vůbec náhodná. Popsaný model úlohy se nazývá stavová reprezentace úlohy a patří k jednomu ze základních a velmi univerzálních nástrojů (nikoliv řešení) umělé inteligence. Samotná reprezentace úlohy nicméně nestačí k řešení problému, k řešení problému je nutné vytvořit program, který vhodným (inteligentním?) způsobem najde stav, do kterého bychom měli přejít (tedy určí další tah). Tyto programy jsou algoritmy prohledávání stavového prostoru a obecněji pak algoritmy prohledávání (search algorithms) a v podstatě celý zbývající text se věnuje právě jim. Nový přístup k řešení úlohy jsme popsali jako „Snažíme se najít co nejlepší stav, do kterého můžeme z aktuálního stavu přejít“. Samotný přechod se stavu do stavu nepředstavuje žádný zvláštní problém (v dříve uvedených algoritmech ho představuje funkce Tah ()). Aktuální stav je prostě stav hrací plochy, ve kterém jsme zrovna na tahu, hledat také umíme, a tedy jediná neznámá je „nejlepší stav“. Abychom mohli určovat lepší a horší stavy, musíme definovat hodnocení stavu, prozatím nám bude stačit „lepší“ a „horší“. Pokud vám připadá, že neděláme nic zvláštního, protože člověčí hráč piškvorek dělá přesně totéž (tedy snaží se najít nejlepší tah z aktuálního stavu hrací plochy), tak je to naprosto v pořádku, protože přesně tak to je. Upozornění: Nezaměňujte slovní spojení algoritmy prohledávání (search algorithms) s vyhledávácími algoritmy (string search/matching algorithms), ty druhé slouží k prohledávání textu a nemají s těmi prvními mnoho společného. Prohledáváním zde rozumíme spíš něco jako pokus „zorientovat se“ v jakémsi obrovském prostoru.

Stránka 27/122

Cvičebnice pro samostudium Umělá inteligence II Dále popsaným způsobem lze řešit obrovské množství úloh (nejen her) a velké množství algoritmů umělé inteligence postaveno na principu prohledávání prostoru řešení. Při popisu metod prohledávání stavového prostoru se budeme dále držet příkladu s piškvorkami, protože je to relativně jednoduchá úloha (z pohledu člověka) a každému dobře známá a přesto dostatečně složitá pro umělou inteligenci, takže nás má smysl tyto algoritmy k jejímu řešení používat. Dále uvedené metody nemá smysl používat pro úlohy, které lze řešit známým algoritmem s rozumnou časovou složitostí.

Shrnutí V této kapitole jsme popsali transformaci piškvorek z hraní piškvorek na prohledávání abstraktního prostoru stavů, přesněji na nalezení nejlepšího následovníka aktuálního stavu. Měli byste vědět co je stav, uzel, vrchol, graf, hodnocení, předchůdce, následovník, prohledávání, hodnocení stavu. Následující kapitola přesněji popisuje, co jsou to grafy. Dále se zabývá popisem jejich vlastnosti, které jsou zajímavé při prohledávání grafů a nakonec popisem základních algoritmů, které lze k prohledávání grafu použít. K neformálnímu textu se vrátíme v kapitole „Metoda minimaxu“ 4.3.

Stránka 28/122


Minimaxová metoda Minimaxová metoda se využívá pro vytvoření strategie. Metoda je založená na teorému formulovaném pro hru pro dva hráče s nulovou sumou. Hra s nulovou sumou je taková hra, kde správný tah jednoho hráče je automaticky nevýhodný pro druhého hráče. Respektive, hráč nemůže provést takový tah, který by byl výhodný pro oba hráče současně (laicky řečeno, když sečteme "výdělek" prvního a druhého hráče dostaneme nulu). Prakticky se jedná o většinu deskových her a mnoho her karetních. Naopak třeba obyčejný obchod je obvykle hra s nenulovou sumou, protože na něm obě strany obchodu "vydělají". Minimaxovou strategii lze zobecnit na hry pro více hráčů Minimaxová strategie se používá k řízení prohledávání stavového prostoru tak, aby bylo prohledávání schopné reagovat na neznámé tahy protihráče. Pokud se rozhodujeme (jako počítač) jaký tah provést, musíme předvídat tahy, které provede soupeř. Předpokládáme, že soupeř se bude snažit vyhrát a tedy bude táhnout tak, aby to pro nás bylo nevýhodné. Princip minimaxové metody demonstruje následující animace Prázdná plocha představuje stavový prostor nějaké hry pro dva hráče. Každý uzel představuje jeden z možných stavů hrací plochy. Kořen stromu je počáteční stav hry (například prázdná hrací deska). Listové uzly (kolečka) představují koncové stavy hry – tedy jeden z hráčů vyhrává. Čísla v uzlech představují hodnocení stavů, tedy nějaké score dosažné na konci hry. Kladná čísla jsou score pro počítač, záporná čísla jsou score pro protihráče – člověka. Počítač se tedy snaží dosáhnout co nejvyšší hodnoty hodnocení. Člověk se snaží dosáhnout co nejnižší hodnoty. První na tahu je počítač – začíná z jediného bodu (kořen stromu) a má na výběr mezi dvěma tahy (levá větev stromu a pravá větev stromu), nyní je potřeba určit, který z tahů zvolit (hodnocení uzlů v první úrovni neznáme – nevíme kam bude táhnout soupeř). Vzhledem k tomu, že počítač se snaží dostat do stavu hry s maximálním hodnocením, označují se tahy (rozhodovaní) počítače jako MAX. Tahy člověka jsou naopak MIN (v pravém sloupci je tedy vidět kdo je ve které úrovni na tahu). Aby se počítač mohl v prvním tahu rozhodnout, je nutné určit hodnocení následovníků kořenového uzlu. Abychom ho zjistili, musíme se zanořit až k prvnímu stavu, jehož hodnocení jsme schopni určit (první 4 kroky animace) – to je buď koncový stav hry (výhra jednoho z hráčů nebo „plichta“), nebo maximální povolená hloubka prohledávání (v tom případě je hodnocení pouze odhad hodnocení a celá věc se stává mnohem více nejistou). Poslední na tahu je člověk, vybírá minimum, a tedy hodnota 37 se stane momentálně nejlepším výsledkem, kterého může dosáhnout. Má však ještě možnost ještě jiného tahu – do uzlu s hodnocením 34, které se vzápětí stane momentálně nelepším výsledkem (4: 34). Oba výsledky představují pro člověka sice prohru, ale předpokládáme, že zvolí menší zlo Celou věc můžeme interpretovat taky tak, že "pokud se hra dostane do uzlu označeného 4: min = 34, tak člověk bude táhnout do uzlu s hodnocením 34, ve kterém my (jako počítač) Stránka 29/122

Cvičebnice pro samostudium Umělá inteligence II vyhrajeme. Pokud do tohoto uzlu táhnout nebude, tak výsledek může být pro nás (jako počítač) jedině lepší." Vrátíme se do nadřazeného uzlu, kde je na tahu počítač. Jediné známé hodnocení potomků tohoto uzlu je právě vypočítaná hodnota 34, proto se tato hodnota stává momentálně nejlepším tahem, kterého můžeme dosáhnout. Máme však ještě alternativní tah (druhého potomka uzlu 5: max = 34), jehož hodnotu určíme úplně stejně jako pro prvního potomka (tedy tak, že najdeme minimum jeho potomků). Minimum je -34, což je menší jak 34, tedy Pokud se hra dostane do uzlu 5: max = 34, pak my, jako počítač musíme zvolit první tah, protože to je jediná možnost výhry (opět předpokládáme, že pokud by se hra dostala do uzlu 7: min = 24, tak člověk bude hrát do uzlu s hodnocením -24). Maximum, uzlu 5: max = 34 tedy zůstává 34. Tímto postupem projdeme celý strom stavů a ohodnotíme všechny uzly (možné tahy), nakonec se vrátíme ke kořenu a můžeme určit nejlepší tah. Potom může hrát soupeř, a jakmile je počítač znovu na tahu, opět vygeneruje nový stavový strom, kde kořenem je aktuální stav hry (například hrací desky v piškvorkách). Každá vodorovná úroveň stromu tedy reprezentuje jednoho hráče, na obrázku jsou ve svislém směru vždy pouze dva uzly, což znamená, že se jedná o velmi jednoduchou hru, kde se vždy rozhodujeme mezi dvěma tahy.

Stránka 30/122


Minimaxová metoda - vizualizace Poznámka: Pro grafickou animaci průběhu minimaxové metody se přepněte do UIS, sekce Metody hrani her, kapitola Minimaxová metoda – vizualizace.

Shrnutí V této části jsme prezentovali dvě reálné úlohy – program pro seřazení čísel a program pro hraní piškvorek a pokusili jsme se na příkladu řazení čísel ukázat, jak se dá vytvořit algoritmus. Na příkladu piškvorek jsme se pokusili ukázat, jak se algoritmus vytvořit nedá, respektive, že se jedná o úlohu, u které je délka algoritmu závislá na složitosti úlohy. Umělá inteligence je soubor metod a přístupů, které je možné použít k řešení takových úloh. Je dobré připomenout, že na úlohy, které nejsou složité naopak umělá inteligence není vhodná (to je například řazení na které máme řadu hotových univerzálních algoritmů). V následujících kapitolách se budeme věnovat tomu, jak lze složité úlohy řešit s pomocí umělé inteligence. Postupně přejdeme od piškvorek ke složitějším problémům. V kapitole "Časová složitost" je formálněji popsáno, co znamenají pojmy složitá úloha a časová složitost a jak se s nimi pracuje. Jedním ze způsobů vyjádření časové složitosti je Onotace. Na příkladu jsme ukázali, že časová složitost je zatraceně důležitá, protože nám umožňuje alespoň přibližně určit, jak dlouho bude algoritmus pracovat v závislosti na počtu položek, které bude zpracovávat. Toto je poměrně důležité při vytváření algoritmů umělé inteligence.

Kontrolní otázky 1. Jaké znáte řadící algoritmy? 2. Jak je definováno procházení do šířky? 3. Jak je definováno procházení do hloubky?

Stránka 31/122


Další metody procházení stavového prostoru Úvod Podstatou metod informovaného vyhledávání je snaha zabránit hledacím algoritmům, aby zabloudily. Neinformované hledání, diskutované dříve, je schopno najít řešení problémů systematickým generováním nových stavů a testováním, zda splňují cílové podmínky. Potíž je v tom, že ve většině případů jsou vysoce neefektivní (čas, prostor, optimalita,…). Informované hledání je založeno na strategii, která využívá znalost specifickou pro daný problém, a nalezení cíle je mnohem efektivnější, včetně lepší možnosti dosáhnout optimálního řešení.

Hledání prvního nejlepšího Doposud bylo obecně možné, po formulaci problému v termínech stavů a operátorů, nějakým způsobem určitou znalost aplikovat pro hledání cíle. Avšak pokud je problém tzv. dobře definovaný, volby jsou omezené. Např. při použití algoritmu General-Search se dá znalost použít na jediném místě – ve funkci zařazování do fronty, kde se určuje, který uzel má být expandován jako příští. Obvykle se znalost toho, jak určit uzel, stanovuje vyhodnocovací funkcí (evaluation function, Eval-Fn), která vrací číslo určující míru (nebo nedostatek) potřeby expandovat uzel. Pokud jsou uzly uspořádány tak, že ty s nejlepším ohodnocením jsou expandovány jako první, nazývá se tato strategie hledání prvního nejlepšího (best-first search). function Best-First-Search(problem, Eval-Fn) returns sekvence řešení inputs: problem // problém Eval-Fn // vyhodnocovací funkce Queuing-Fn <-- funkce seřazující uzly pomocí Eval-Fn return General-Search(problem, Queuing-Fn) Poznámka: „Vyhledej první nejlepší“ ve skutečnosti znamená jen to, že získáme uzel, který se zdá být nejlepším (jinak by cesta k řešení byla snadná a přímočará, což obecně neexistuje). Vzhledem k tomu, že funkce hledání nejlepšího uzlu není vševědoucí, může být hledání samozřejmě svedeno z cesty. Správný název by tedy měl být spíše hledání zdánlivě prvního nejlepšího.

Stránka 32/122

Cvičebnice pro samostudium Umělá inteligence II Obdobně jako existuje skupina algoritmů General-Search pro různé funkce zařazování do fronty, je k dispozici skupina Best-First-Search algoritmů s různými vyhodnocovacími funkcemi. Tyto Best-First-Search algoritmy se snaží najít nenákladná řešení, typicky používají nějakou odhadovací míru pro cenu řešení a snaží se ji minimalizovat. Jednou z již ukázaných možností byla cena cesty g k rozhodnutí, kterou cestu prodloužit (viz předchozí diskuse k tzv. dobře definovaným problémům a řešením). Míra g však přímo nesměřuje k cíli. Aby bylo hledání přímo zaměřeno na cíl, musí v sobě použitá míra zahrnovat nějaký odhad ceny cesty z nějakého stavu do nejbližšího cílového stavu. Lze použít nejméně dva základní přístupy k uvedenému řešení: pokus expandovat uzel nejbližší k cíli a pokus expandovat uzel na nejlevnější cestě k řešení. Lačné vyhledávání minimalizující odhadovanou cenu dosažení cíle Jednou z nejjednodušších strategií hledání prvního nejlepšího je minimalizace odhadované ceny dosažení cíle. Znamená to, že vždy je nejdřív expandován uzel, který se zdá být nejblíže cíli. Pro většinu (reálných) problémů lze náklady na dosažení cíle z nějakého okamžitého stavu jen odhadnout, nikoliv určit přesně. Funkce, která počítá takové odhady nákladů, se nazývá heuristická funkce, obyčejně označovaná jako h: h(n) = odhadnutá cena nejlevnější cesty ze stavu v uzlu n do stavu cílového. Hledání prvního nejlepšího, které používá h k výběru dalšího expandovaného uzlu, se nazývá lačné hledání (greedy search). Symbolický kód pro lačné hledání s danou funkcí h: function Greedy-Search(problem) returns řešení nebo neúspěch return Best-First-Search(problem, h) Formálně vzato, h může být jakoukoliv funkcí. Jediným požadavkem je, aby h(n) = 0, jestliže n je cíl. Heuristické funkce jsou vždy specifické pro daný problém, tj. aplikačně závislé. Pro příklad uvažme cestování v Rumunsku z města Arad do Bucharest .

Stránka 33/122


Obrázek 11: Hledání cesty v grafu – Straight-Line Distance. Mapka má přídavnou informaci ve formě kilometrové vzdálenosti tras mezi jednotlivými městy. Pro obdobné problémy je dobrou heuristickou funkcí přímočará vzdálenost v řadě k cíli neboli SLD (Straight-Line Distance): hSLD(n) = přímočará řadová vzdálenost mezi n a cílovým místem. hSLD lze spočítat jen tehdy, jsou-li známy souřadnice měst v Rumunsku. Kromě toho zde platí, že cesta z A do B je převážně vždy správným směrem, takže tento druh přídavné informace umožňuje heuristice pomoci v redukci ceny vyhledávání. Další obrázek ukazuje pokrok lačného vyhledávání při hledání cesty z Aradu do Bucharesti:

Stránka 34/122


Obrázek 12: Hledání cesty v grafu – Lačné prohledávání.

Pomocí heuristiky SLD se expanduje jako první uzel z Aradu do Sibiu, protože je blíže (dle přídavné informace) Bucharesti než Zerind nebo Timisoara (viz vzdálenosti různých měst od Bucharesti). Dalším uzlem je ze stejného důvodu Fagaras, a odtud už to je přímo do Bucharesti (ta je cílem, protože její vzdálenost od sebe sama je nula). V tomto příkladě funguje heuristika skvěle, protože našla řešení bez expanze uzlů, které nejsou na cestě. Je však cesta optimální? Optimální není, protože nalezená cesta je o 32 km delší než cesta přes Rimnicu Vilcea a Pitesti. Optimální cesta nebyla heuristikou nalezena, protože Faragas je Buchuresti blíže z hlediska SLD než Rimnicu Vilcea, proto cesta přes Faragas byla expandována jako první. Ukázaná heuristická strategie preferuje největší nalezený kus cesty k cíli vzhledem k tomu, že tento velký kus odebere největší část ze zbývající cesty do cíle (Fagaras –Bucharest = 211 km, Rimnicu Vilcea-Pitesti-Bucharest = 97 + 101 km, a 97 odebere méně ze zbytku než 211), aniž by se starala o to, zda je to nejlepší vzhledem k délce cesty – proto je název hledání „lačné, hltavé“ (greedy). Přesto praxe ukazuje, že lačnost přináší velmi dobré výsledky (i když se jedná o jeden ze sedmi smrtelných hříchů). Lačnost přináší jako pozitivum rychlé nalezení cíle, i když ne vždy optimální. Optimalita by vyžadovala důkladnější analýzu z hlediska uvažování o celé dlouhé vzdálenosti, nikoliv pouze bezprostřední nejlepší výběr. Lačné hledání je citlivé na chybný počátek. Uvažme problém cesty z Iasi do Fagarasu: heuristika nabízí první expanzi uzlu Neamt, což je ovšem slepá ulička. Řešením je expanze Vaslui,

což

je

ale

z hlediska

heuristiky

do

cíle

dále.

Z Vaslui pak

do Urziceni, Bucharesti a Fagarasu, ale to jsou z hlediska heuristiky zbytečné expanze uzlů, Stránka 35/122

Cvičebnice pro samostudium Umělá inteligence II pokud je okamžitý stav v Neamtu. Navíc, při zanedbání opatrnosti vzhledem k detekci opakovaných stavů může dojít k nekonečným oscilacím mezi Neamtem a Iasi. Lačné hledání připomíná hledání nejdřív do hloubky, protože preferuje jednu cestu do cíle, ale při objevení slepé uličky se vrací zpět. Rovněž má stejné neduhy: není optimální a není kompletní (může se vydat na nekonečnou cestu a nikdy se nevrátit k vyzkoušení odlišné možnosti). Nejhorší časová složitost je O (bm), kde m je max. hloubka hledání. Stejná je i prostorová složitost (uzly jsou uchovávány v paměti). Podstatná redukce složitosti vyžaduje kvalitní heuristiku h a závisí také na konkrétním problému.

Stránka 36/122


A* algoritmus Lačné

hledání h(n) má

uvedené

přednosti

a nedostatky.

Uniformně-cenové

hledání g(n) minimalizuje cenu cesty do daného okamžiku; je optimální a kompletní, ale může být velmi neefektivní. Kombinací výhod obou strategií lze získat alternativní funkci, přičemž postačuje prostě jejich hodnoty sečíst: f(n) = g(n) + h(n). Protože g(n) dává cenu cesty od startu do n a h(n) odhaduje cenu nejlevnější cesty z n do cíle, pak platí f(n) = odhadnutá cena nejlevnějšího řešení přes n. Při hledání nejlevnějšího řešení je tedy rozumné napřed zkusit uzel s nejmenší hodnotou f. Existuje dokonce důkaz, že tato strategie je kompletní a optimální za předpokladu určitého omezení pro h. Omezením je výběr funkce h takové, která nikdy nepřecení cenu dosažení cíle. Taková funkce h se nazývá přijatelná heuristika. Přijatelné heuristiky jsou v principu optimistické, protože předpokládají, že cena řešení problému je menší, než ve skutečnosti. Tento předpoklad se přenáší do funkce f. Je-li h přijatelná,

pak f

(n) nikdy

nepřecení

skutečnou

cestu

nejlepšího

řešení

přes n (při přecenění ceny by pak cesta nebyla vybrána, i když je správným řešením). Hledání prvního nejlepšího s použitím f jako vyhodnocovací funkce a h jako přijatelné funkce se nazývá hledání A*. Symbolický zápis funkce: function A*-Search(problem) returns řešení nebo neúspěch return Best-First-Search(problem, g + h) Příkladem přijatelné heuristiky je výše uvedená hSLD (nejkratší cesta mezi dvěma body je přímá cesta – úsečka). Obrázek ukazuje několik prvních kroků hledání A* při použití heuristiky hSLD. Za povšimnutí stojí, že A* preferuje expanzi z Rimnicu Vilcea před expanzí z Fagarasu. Přestože Fagaras je blíže Bucharesti, cesta do Fagarasu není tak efektivní z hlediska přiblížení se k Bucharesti jako cesta do Rimnicu Vilcea (uzly mají označení f = g+h, přičemž hodnoty h jsou SLD vzdálenosti do Bucharesti z dříve uvedeného obrázku):

Stránka 37/122


Obrázek 13: Hledání cesty v grafu – A*.

Vlastnosti hledání A* Obrázek hledání pomocí A* demonstruje jednu základní věc: podél libovolné cesty z kořene f-cena nikdy neklesá. To není náhodou a heuristiky, které tuto vlastnost nenarušují, se nazývají monotónní (v r. 1984 bylo dokázáno, že heuristika je monotónní tehdy a jen tehdy, pokud splňuje pravidlo tzv. trojúhelníkové nerovnosti – přímočaré vzdálenosti tuto podmínku samozřejmě splňují, takže SLD je monotónní). Pokud by heuristika nebyla monotónní, lze ji na monotónnost upravit: Uvažujme dva uzly n a n', kde n je rodičovský uzel n'. Dále nechť např. g(n) = 3 a h(n) = 4, takže f(n) = g(n) + h(n) = 7. Víme tedy, že skutečná cena cesty k řešení je nejméně 7. Předpokládejme ještě, že g(n') = 4 a h(n') = 2, takže f(n') = g(n') + h(n') = 6. Z uvedeného je zřejmé, že se jedná o nemonotónní heuristiku h. Je ale zřejmé, že libovolná cesta přes n' je také cestou přes n, tedy hodnota 6 je bezvýznamná, neboť již víme, že skutečná cena musí být nejméně 7. Musíme tedy kontrolovat při generování nového uzlu, zda jeho f-cena je menší než f-cena jeho rodiče; pokud je cena u potomka menší, použije se prostě cena rodiče: f(n') = max[f(n), g(n') + h(n')]. Takto se ignorují hodnoty, které se mohou vyskytnout s nemonotónními heuristikami a uvedený stav se nazývá rovnice max-cesty (pathmax equation). Pokud vztah max-cesty použijeme, pak f bude vždy neklesající podél každé cesty z kořene, za předpokladu přijatelnosti h. Z toho vyplývá další vlastnost A*, tj. pokud f nikdy cestou z kořene neklesá, Stránka 38/122

Cvičebnice pro samostudium Umělá inteligence II lze ve stavovém prostoru vytvořit tzv. obrysy: Na mapce (stavovém prostoru) jsou obrysy pro f = 380, f =400 a f = 420, kde Arad je počáteční stav. Uzly uvnitř daného obrysu mají fceny nižší, než je hodnota daného obrysu.

Obrázek 14: Hledání cesty v grafu – obrysy.

A* expanduje uzly s nejnižší f, tedy hledání postupuje koncentricky v pásmech podle narůstání f. Při hledání s uniformní cenou (A*-hledání za použití h = 0) jsou pásma „cirkulární“ kolem počátečního stavu. Se vzrůstající přesností heuristiky se pásma začínají protahovat směrem k cílovému stavu a zužují se kolem optimální cesty. Nechť f * je cena optimální cesty k řešení. Pak lze o A* říci následující: • •

A* expanduje všechny uzly, pro něž platí f(n) < f *. A* může dále expandovat některé uzly přímo na ?cílovém obrysu?, kde platí f(n) = f *, před výběrem cílového uzlu

Intuitivně je zřejmé, že první řešení musí být optimální, protože uzly ve všech následujících obrysech mají vyšší f-cenu a tudíž vyšší g-cenu (důvodem je, že všechny cílové stavy mají h(n) = 0, takže zdražení způsobí g). Dále je intuitivně zřejmé, že A*-hledání je kompletní. Přidáváním pásem s rostoucími hodnotami f se nakonec dostaneme do pásma, kde f je rovno ceně cesty do cílového stavu. Kromě uvedeného stojí za zmínku, že mezi optimálními algoritmy tohoto typu – tj. algoritmy, které prodlužují vyhledávací cesty z kořene Stránka 39/122


– je A* optimálně účinný pro jakoukoliv danou heuristickou funkci: libovolný algoritmus, který neexpanduje všechny uzly v pásmech mezi kořenovým a cílovým pásmem, musí počítat s rizikem opominutí optimálního řešení (rozsáhlý důkaz byl podán v r. 1985).

Důkaz optimality A* Nechť G je optimální cílový stav s cenou cesty f *. Nechť G2 je suboptimální cílové řešení, tj. cílový stav s cenou cesty g (G2) > f *. Uvažujme situaci, kdy A* vybral G2 z fronty. Protože G2 je cílovým stavem, ukončí hledání se suboptimálním řešením (viz obrázek 15 uzel n je uzel na cestě k optimálnímu řešení G).

Obrázek 15: Důkaz optimality algoritmu A*.

f * ≥ f(n). Pokud n není vybrán pro expanzi přes G2, platí: f(n) ≥ f(G2). Z toho plyne: f * ≥ f(G2). Protože G2 je cílovým stavem, platí: h(G2) = 0, z čehož zjevně plyne f(G2) = g(G2). Tím bylo s použitím předpokladů dokázáno, že: f * ≥ g(G2). Stránka 40/122

Cvičebnice pro samostudium Umělá inteligence II To je ale v rozporu s předpokladem, že G2 je suboptimální, takže A* nikdy nevybere pro expanzi suboptimální cíl. Protože vrací jedině řešení vybrané pro expanzi, musí A* být optimálním algoritmem.

Důkaz úplnosti A* A* expanduje uzly v pořadí vzrůstající f, takže nakonec musí dojít k expanzi k dosažení cílového stavu. To platí s výjimkou případu, kdy je nekonečně mnoho uzlů s f (n) < f *. Důvod k existenci nekonečného počtu uzlů je buď: a) existuje uzel s nekonečně velkým počtem větvení, nebo b) existuje cesta s konečnou cenou, ale s nekonečným počtem uzlů podél ní (starý paradox typu „zajíc nikdy nedožene želvu“). Z toho plyne, že A* je kompletní v lokálně konečných grafech (tj. grafech s konečným faktorem větvení) za předpokladu, že existuje nějaká kladná konstanta δ taková, že každý operátor stojí nejméně δ.

Složitost A* Z hlediska kompletnosti, optimálnosti a optimální efektivnosti A* není odpovědí na všechny požadavky hledání ? pro většinu problémů je totiž počet cílových uzlů uvnitř obrysu, vymezujícího cílový prostor vyhledávání, stále exponenciální vzhledem k délce řešení. Komplikovaný důkaz byl však vytvořen proto, že se exponenciální nárůst objevuje, pokud ovšem chyba heuristické funkce neroste rychleji než logaritmus skutečné ceny cesty. Podmínka pro sub-exponenciální nárůst je: | h(n) − h*(n) | ≤ O(log h*(n)), kde h*(n) je skutečná cena cesty z n do cíle. Pro A* není rozhodující čas, nýbrž paměť, protože udržuje v paměti všechny generované uzly.

Stránka 41/122


Heuristické funkce Hlavolam s posouváním osmi čtverečků v devíti polích patří k nejstarším problémům s heuristickým vyhledáváním:

Obrázek 16: Hlavolam - desková hra.

Typické řešení má zhruba 20 kroků (závisí to na počátečním stavu). Faktor větvení je cca 3 (je-li prázdné pole uprostřed, pak b = 4; v rohu je b = 2; podél hran je b = 3). Prohledávání, které vyčerpá všechny možnosti do hloubky 20, zkoumá přibližně 320 = 3.5×109 stavů. Pokud by se důsledně testovaly stavy opakování, lze redukovat počet stavů radikálně, protože existuje pouze 9! = 362 880 různých rozmístění pro 9 polí. To je stále velmi mnoho, proto je vhodné najít dobrou heuristiku. Pokud je cílem nalezení nejkratšího řešení, je zapotřebí mít heuristickou funkci, která nikdy nepřecení počet kroků do cíle. Dvě možnosti: h1 = počet čtverečků na chybných pozicích. Na obrázku je umístěno 7 z 8 chybně, takže počáteční stav má h1 = 7; je to přijatelná heuristika, protože každý chybně umístěný čtvereček musí být alespoň jednou posunut. h2 = součet vzdáleností čtverečků od jejich koncových pozic. Čtverečky se nemohou pohybovat diagonálně, takže se sečtou vzdálenosti vertikální a horizontální (tento typ výpočtu vzdáleností je znám jako vzdálenost městských bloků nebo manhattanská vzdálenost). h2 je rovněž přijatelná, protože jakýkoliv posun pohne pouze jedním čtverečkem o jeden krok směrem k cíli. Čtverečky 1 až 8 z počátečního stavu na obrázku mají celkovou délku manhattanské cesty h2 = 2 + 3 + 3 + 2 + 4 + 2 + 0 + 2 = 18. Stránka 42/122


Vliv přesnosti heuristiky na efektivitu Jednou možností pro stanovení kvality heuristiky je efektivní faktor větvení, označovaný b*. Je-li N celkový počet uzlů expandovaných pomocí A* a hloubka řešení je d, pak b* je faktor větvení, který by měl rovnoměrně vyvážený strom hloubky d, aby obsahoval N uzlů: N = 1 + b* + (b*)2 + . . . + (b*)d. Např. když A* najde řešení v hloubce 5 za použití 52 uzlů, pak b* = 1.91. Dobrá heuristika by se měla blížit b* = 1. Otázkou může být, zda h2 je vždy lepší než h1. Protože z definic obou heuristik platí pro libovolný uzel, že h2(n) ≥ h1(n), pak odpověď zní ano, tedy h2 dominuje h1. Dominace je převedena do efektivnosti přímočaře, protože A* s h2 expanduje průměrně méně uzlů než s h1. Např. pro již uvedený problém: Jak již dříve bylo uvedeno, expandovány budou uzly, pro které platí f(n) < f *. To je totéž jako

tvrzení,

že

budou

expandovány

uzly

s h(n)

<

f

*

-

g(n) vzhledem

k definici f(n). Protože h2 je přinejmenším tak velká jako h1 pro všechny uzly, pak každý uzel expandovaný pomocí hledání A* s h2 bude rovněž expandován s h1 a h1 může ještě způsobit expanzi jiných uzlů. Z toho plyne určitý závěr či doporučení: Je lépe použít heuristiku s vyššími hodnotami, protože nedojde k přecenění (konečný výsledek jednoduše může být takový nebo lepší). Hledání vhodné heuristiky vyžaduje velmi často experimentování, např. náhodné generování počátečních konfigurací, z nichž se vyzkouší vyhledávání s různými možnými heuristikami, a výsledná statistika doporučí nejvhodnější z nich. Vzhledem k zavedení pravděpodobnosti výběru ovšem dochází ke ztrátě záruky na přijatelnost heuristiky ve výše zmíněném smyslu; výhodou je šance expandovat méně uzlů, tj. levnější řešení. Poměrně často je možné najít vlastnosti nutné pro řešení, což může přispět k heuristické vyhodnocovací funkci (v šachu je k dosažení matu zapotřebí určitý počet určitých figur apod.).

Stránka 43/122


Algoritmy iterativního vylepšování Pro řadu tzv. dobře definovaných problémů (8 vzájemně se nenapadajících dam na šachovnici, VLSI, apod.) platí, že popis stavu sám o sobě obsahuje veškerou informaci potřebnou pro řešení. Konkrétní cesta k řešení (zda je řešení dosaženo tak či jinak) nemusí být (a často není) relevantní. V těchto případech poskytují algoritmy s iterativním vylepšováním nejpraktičtější přístup. Např. lze začít se všemi 8 dámami na šachovnici nebo všemi vodiči v konkrétních spojovacích kanálech řešeného VLSI obvodu. Pak můžeme pohybovat dámami ve snaze redukovat počet vzájemného napadání, nebo přemísťovat vodič z jednoho kanálu do druhého ve snaze redukovat zahlcení. Obecnou ideou je začít s kompletní konfigurací a modifikacemi zlepšit kvalitu. Pro představu lze uvažovat o stavech umístěných na povrchu nějaké krajiny. Výška povrchu v nějakém místě odpovídá vyhodnocovací funkci (evaluation) pro stav v daném bodě (current state). Podle myšlenky iterativního vylepšování je vhodné se v krajině pohybovat a hledat nejvyšší vrcholek, tj. optimální řešení. Iterativní vylepšování obvykle udržuje údaje pouze o cestě aktuálního uzlu a nehledí dále než k bezprostředním sousedům daného stavu (hledání vrcholku hory v mlze zároveň s postižením zapomnětlivostí). Přes zmíněné nedostatky je tento postup v řadě velmi obtížných případů praktický – typickou ukázkou použití zmíněného postupu jsou umělé neuronové sítě. Jednou ze skupin zmíněných algoritmů je tzv. slézání kopce (v originále hillclimbing, někdy pojmenované také jako gradient descent, tj. gradientní sestup). Další skupinou jsou algoritmy tzv. simulovaného žíhání (simmulated annealing). Zde se zmíníme o lezení po kopcích.

Slézání kopce (gradientní sestup) Algoritmus je symbolicky popsán následovně: function Hill-Climbing(problem) returns stav řešení inputs: problem // problém local variables: current // aktuální stav-uzel next // další stav-uzel current w Make-Node(Initial-State[problem]) loop do next <-- následný uzel s nejvyšší hodnotou if Value[next] < Value[current] then return current current <-- next end Stránka 44/122

Cvičebnice pro samostudium Umělá inteligence II Ve smyčce se hledající jednoduše pohybuje směrem ke vzrůstající hodnotě (do kopce). Algoritmus nepracuje s vyhledávacím stromem, takže datová struktura pro uzel musí pouze zaznamenávat stav a jeho hodnotu Value. Je-li na cestě vzhůru několik ekvivalentně nejlepších uzlů, pak se obvykle vybírá náhodně jeden z nich. Uvedený jednoduchý postup má tři známé nedostatky: Lokální maxima: po dosažení lokálního maxima se algoritmus zastaví, přestože globální maximum (neznámo kde v krajině je) je mnohem lepší. Roviny: ve všech směrech poskytuje vyhodnocovací funkce stejnou hodnotu, takže postup krajinou vede k náhodné cestě. Hřebeny: hřeben má strmě klesající strany, takže se na něj lze dostat snadno, ale další stoupání hřebenu k vrcholku je velmi mírné a dochází k oscilaci hledání ze strany na stranu se zanedbatelným pokrokem v přibližování se k maximu. V každém případě se algoritmus dostane do bodu, odkud se nelze dostat výš. V takových případech se lze pokusit znovu z jiného startovacího bodu – k tomu se používá metoda zvaná slézání kopce s náhodným počátkem, takže dochází k sérii hledání z náhodně vybraných různých míst a nejlepší dosažené řešení se uchovává. Ukončení vyhledávání pak závisí na tom, zda byl stanoven maximální předem stanovený počet těchto hledání nebo zda doposud dosažený nejlepší výsledek nebyl po nějaký počet iterací zlepšen. Pro dostatečný počet iterací může (ovšem i nemusí) hledání s náhodným restartem nakonec najít optimální řešení. Úspěch zmíněného typu hledání velmi silně závisí na tvaru povrchu, který je dán prostorem uvažovaných stavů. S malým počtem lokálních maxim je řešení nalezeno rychle. Realistické problémy však představují spíše podobu povrchu dikobraza. Pro NP-kompletní problémy nelze dosáhnout lepší než exponenciální časové závislosti. Přesto jsou takto založené metody velmi často úspěšné proto, že poskytují velmi dobré řešení, i když to nemusí být zrovna optimum (a často není možné ani zjistit, jaké to optimum vlastně je). Proto se použije přijatelný výsledek dosažený po nepříliš velkém počtu iterací – praktické hledisko hraje často výraznou roli.

Aplikace pro problémy vyhovující omezením (CSP) Problémy vyhovující omezením (Constraint Satisfaction Problems) mohou být řešeny metodami iterativního zlepšování tak, že napřed jsou všem proměnným dosazeny nějaké hodnoty, a pak za použití modifikačních operátorů se konfigurace pohybuje směrem k řešení. Modifikační operátory jednoduše přiřazují jiné hodnoty proměnným. Např. pro problém 8 dam je počátečním stavem 8 dam nějak rozestavených na šachovnici a modifikační operátor může dámou pohnout o políčko vedle. Tyto algoritmy se nazývají heuristické opravování, protože

napravují

nekonzistence

aktuální

konfigurace.

Při výběru

nové

hodnoty

Stránka 45/122

Cvičebnice pro samostudium Umělá inteligence II proměnné se (heuristicky) vybírají takové hodnoty, které jako výsledek dávají minimální konflikty s ostatními proměnnými – tzv. heuristika min-konflikt: V nedávné době byla min-konflikt použita pro plánování pozorování vesmírného teleskopu Hubble (HST, Hubble Space Telescope), kde redukovala čas nutný pro naplánování týdenního pozorování ze tří týdnů na přibližně 10 minut (astronomové si mohou podávat žádosti o pozorování pomocí HST a velké množství velmi různých žádostí vyžaduje velmi dobrý rozvrh).

Kontrolní otázky 1. 2. 3.

Vysvětlete princip Lačného vyhledávání. Vysvětlete princip algoritmu A*. Popište základní charakteristiky algoritmu A*.

Stránka 46/122


Inteligentní agenti Úvod Agentem zde rozumíme cokoliv, co vnímá své prostředí pomocí senzorů a působí na to prostředí pomocí efektorů. Člověk-agent z tohoto hlediska má oči, uši a další orgány jako senzory; dále má ruce, nohy, ústa a další části těla jako efektory. Robot-agent nahrazuje senzory kamerami a infračervenými detektory. Efektory jsou vlastně tvořeny různými motory. Softwarový agent pro vnímání a působení na prostředí disponuje bitovými řetězci. Cílem je návrh (umělých) agentů, kteří jsou inteligentně a výkonně schopni působit na své prostředí.

Činnost agentů Za racionálního agenta budeme považovat takového, který provádí správné věci. V prvním přiblížení je správná věc taková věc, která umožňuje agentovi nejlepší úspěch. Jak a kdy se měří výkonnost agenta? Pro různé agenty neexistuje stejný způsob měření úspěšnosti. Měření (a vyhodnocení) míry úspěšnosti není vhodné provádět subjektivně (tedy přímo agentem), např. agent to není schopen udělat apod. Proto se používá objektivní míra úspěšnosti, kdy je agent pozorován např. námi zvnějšku v jeho prostředí. Např. (libovolný) agent, jehož úkolem je vysávat nečistotu z podlahy, může být jednoduše posuzován z hlediska množství odstraněné špíny během osmi hodin. Komplexnější posouzení může vzít v úvahu faktor spotřeby elektrického proudu, množství produkovaného hluku apod. Další otázkou je, kdy agentovu výkonnost vyhodnocovat. Na začátku vysávání může některý agent vysávat usilovně a za hodinu polevit, jiný může pracovat rovnoměrně celou pracovní dobu, další např. celou dobu své existence. Tomu je nutno přizpůsobit měření. Je nutno také rozlišovat mezi racionalitou a vševědoucností (zde agent zná skutečný výsledek svých akcí a tomu může přizpůsobit svou činnost – to je však v realitě nemožné docílit). Racionalita je zaměřena na očekávaný úspěch na základě toho, co je agentem vnímáno (mnoho věcí nelze předvídat a vnímat). Racionalita závisí v libovolném čase na těchto čtyřech věcech: • •

• •

na měření výkonnosti, které definuje stupeň úspěchu na všem, co agent vnímal do daného okamžiku (tzv. sekvence vnímání, což je kompletní historie agentova vnímání) na znalostech agenta o jeho prostředí na akcích, které agent může provádět

Stránka 47/122

Cvičebnice pro samostudium Umělá inteligence II Definice ideálního racionálního agenta: Pro jakoukoliv sekvenci vnímání, ideální racionální agent učiní vše, co se od něj očekává pro maximalizaci míry jeho výkonnosti, a to na základě evidence poskytnuté sekvencí vnímání a znalosti, kterou agent disponuje. Např. před přechodem křižovatky by se měl robot rozhlédnout doleva a doprava; bez toho jeho (post mortem zkoumaná) sekvence vnímání neodhalí, že vkročil do silnice bez rozhlédnutí a srazilo jej auto – takový robot ovšem není racionální a jeho akce přejít křižovatku má nízkou míru výkonnosti. Důležitou součástí racionality (tj. „rozumnosti“) je získávání užitečné informace. Otázka 6: Lze považovat normální hodinky za jednoduchého racionálního agenta? Proč ano či ne? (vnímání, úprava času při přechodu do jiné časové zóny, …).

Ideální mapování ze sekvence vnímání do akcí Pokud tedy závisí chování agenta na jeho sekvenci vnímání do určitého okamžiku, lze každého agenta popsat pomocí tabulky akcí, které vykonává jako odezvu na každou (doposud) možnou sekvenci vnímání (pro mnoho agentů by byl seznam velice dlouhý). Tento seznam budeme nazývat mapováním ze sekvencí vnímání do akcí. Mapování popisuje agenta a ideální mapování ideálního agenta. Specifikace akcí, které má agent provádět jako odezvu na dané sekvence vnímání, dává možnost vzniku ideálního agenta. Není ovšem nutno vytvářet explicitní tabulku s buňkou pro každou možnou sekvenci vnímání – lze často definovat specifikaci bez vyčerpávajícího výčtu. (Např. výpočet druhé mocniny na kalkulačce nepotřebuje znát hodnotu pro každou možnou kombinaci stlačení tlačítek – mapování lze vytvořit např. Newtonovou metodou.)

Autonomie Ideální racionální agent by měl obsahovat nějakou „vestavěnou“ znalost. Pokud takovou má a je založen výhradně na ní, pak ovšem postrádá autonomii (jeho akce pak nezávisí na vnímání). Autonomie systému je dána vlastní zkušeností/znalostí agenta. Nelze ovšem např. požadovat kompletní autonomii agenta na slovo „jdi“, a je nutno se vyhnout jeho nahodilé činnosti. Agent by měl mít schopnost se učit (získávat znalost). Skutečně autonomní inteligentní agent musí být schopen provádět úspěšnou činnost v širokém rozsahu různých prostředí, za předpokladu, že má dost času k adaptaci.

Struktura inteligentního agenta Návrh programu pro umělého agenta je úkolem moderní umělé inteligence. Programem zde rozumíme funkci, která implementuje agentovo mapování z vnímání na akce. Program obvykle běží na určitém typu počítače, tj. vyžaduje se určitá architektura: agent = Stránka 48/122

Cvičebnice pro samostudium Umělá inteligence II architektura + program. Před návrhem a implementací programu je nutno dobře znát možná vnímání a akce. Rovněž je nutno znát očekávanou výkonnost a cíle činnosti agenta, a také v jakém prostředí bude agent aktivní. Příklady typů agentů: Tabulka 1: Popis struktury agenta.

Typ agenta

Vnímání

Akce

Cíle

Medicínský diagnostický systém

Symptomy, náleZdravý pacient, zy, pacientovy Otázky, testy, léčba minimální náklady odpovědi

Prostředí Pacient, nemocnice

Systém analýzy Pixely různé satelitních intensity, barva snímků

Tisk kategorie záběru

Robot sbírající součástky

Zvednutí součástky Umístění součástek Pás přepravující a její uložení do do správných součástky přihrádky přihrádek

Pixely různé intenzity

Správná kategorizace

Obrazy z obíhajícího satelitu

Řízení čističky Teplota, tlak

Otevření, zavření ventilů; přizpůsobení teploty

Maximalizace čistoty, vydatnosti, bezpečnosti

Čistička

Interaktivní Napsaná slova učitel angličtiny

Tisk cvičení, nápověda, opravy

Maximalizace studentových výsledků v testech

Soubor studentů

Některá reálná prostředí mohou být ve skutečnosti velmi jednoduchá (robot pro třídění součástek). Oproti tomu někteří softwaroví agenti (softbot = software robot) existují ve složitých, neomezených doménách (např. softbot navržený pro létání na leteckém simulátoru pro Boeing 747, softbot pro prohlížení a výběr on-line zpráv zajímavých pro zákazníky…).

Programy agentů Jednoduchá základní kostra vnímá prostředí a generuje akce, např.: function Skeleton-Agent(percept) returns action static: memory // agentova paměť světa memory <-- Update-Memory(memory, percept) action <-- Choose-Best-Action(memory) memory wUpdate-Memory(memory, action) return action Po každém vyvolání funkce je agentova paměť aktualizována vzhledem k novému vjemu (vstup funkce); je vybrána nejlepší akce a skutečnost o výběru akce je rovněž uložena do paměti. Paměť setrvává mezi jednotlivými vyvoláními funkce.

Stránka 49/122


Stačí pouze hledat odpovědi? K napsání jednoduchého agentova programu stačí např. vytvořit vyhledávací tabulku: function Table-Driven-Agent(percept) returns action static: percepts // na počátku prázdná sekvence table // tabulka indexovaná sekvencem // vnímání, na počátku stanovená append percept to the end of percepts action <-- Lookup(percepts, table) return action Agent je založen na předem stanovené tabulce. Hlídá si sekvenci vnímání a pouze vyhledá nejlepší akci. V paměti se uchovává celková sekvence vnímání, a ta slouží jako index do tabulky, která obsahuje příslušné akce pro všechny možné sekvence. Metoda hledání odpovědí pro vjemy může selhat, pokud: •

• •

•

Tabulka potřebná pro jednoduchého agenta, jehož úkolem je pouze hrát šachy, by potřebovala přibližně 35 100 buněk. Pro návrháře by to znamenalo velice dlouhý čas, než by vytvořil tabulku. Agent nemá žádnou autonomii, protože výpočet (výběr) nejlepší akce je zcela zabudován. Se změnou prostředí nějakým neočekávaným způsobem by mohl agent naprosto zhavarovat. I kdybychom agenta vybavili nějakým učícím mechanismem, aby měl nějaký stupeň autonomie, trvalo by nesmírně dlouho se naučit správné hodnoty pro všechny buňky tabulky.

Přesto ukázaná funkce Table-Driven-Agent implementuje požadované mapování. Je ovšem nutno pochopit, proč usuzující agent – na rozdíl od pouze vyhledávajícího – může být lepší, jestliže se vyhne uvedeným čtyřem nedostatkům.

Příklad Předpokládejme agenta – umělého řidiče taxi. Úloha řízení není uzavřená: neexistuje limit pro možné nové kombinace okolností, které mohou nastat. Tabulka 2: Příklad agenta.

Typ Vjemy agenta Kamery, Řidič rychloměr, GPS, taxíku sonar, mikrofon

Akce

Cíle

Prostředí

Točení volantem, akcelerace, brzdění, mluvení k pasažérovi

Bezpečná, rychlá, Silnice, další předpisová a pohodlná doprava, chodci, jízda, maximální zisk zákazníci Stránka 50/122


Polohu, účast ostatních objektů na silnici, rychlost…, potřebuje taxi znát; to lze získat z vjemů poskytovaných příslušnými zařízeními (kamery atd.). Znalost projíždění zatáčkami vyžaduje akcelerometr. Stav vozidla je dán senzory v motoru, v elektrické výbavě… Akce jsou víceméně tytéž jako u řidiče-člověka: kontrola motoru plynovým pedálem, kontrola řízení volantem a brzdami. Navíc komunikace s dalšími vozidly, syntezátor hlasu pro mluvení na pasažéry. Míra výkonnosti: dojetí na správné místo; minimalizace spotřeby a opotřebení; minimalizace času a ceny cesty; minimalizace narušení dopravních pravidel a rušení dalších řidičů; maximalizace bezpečnosti a pohodlí pasažérů; maximalizace zisku; Je zřejmé, že některé požadavky jsou konfliktní, takže je nutno nalézt kompromisy. Prostředí: může být na lokálních silnicích, na dálnicích? V oblasti se sněhem nebo bez? Jízda vždy vpravo nebo i vlevo (Británie, Japonsko)? Čím větší omezení, tím snadnější návrh. Nyní je nutno rozhodnout, jak vytvořit reálný program pro mapování vjemů na akce. Různá hlediska řízení mohou vyžadovat různé typy programů. Zde budeme uvažovat čtyři typy: • • • •

Jednoduší reflexní agenti. Agenti sledující svět. Agenti zaměření na cíl. Užitkově zaměření agenti.

Stránka 51/122


Typy agentů Jednoduší reflexní agenti Explicitní vyhledávací tabulky nepřicházejí v úvahu: vizuální vstup z jednoduché kamery přichází v množství 50 MB/s (25 obrázků za vteřinu, 1 000 x 1 000 pixelů s 8 bity na barvy a s 8 bity informace o intenzitě). Tabulka by pak musela mít pro jednu hodinu 260 x 60 x 50 M buněk, což je zjevně přílišný paměťový požadavek. Je ovšem možné sloučit části tabulky – existují některé obecně se vyskytující vstupní/výstupní asociace, např. brzdí-li automobil před námi a jeho brzdová světla se rozsvítí, naše auto by mělo rovněž začít brzdit. To vede k možnosti použití pravidel typu IF – THEN (pravidlo typu podmínka-akce, antecedentkonsekvent). Lidé používají takovýchto asociací rovněž mnoho (některá pravidla se naučí, jiná pocházejí z reflexů). Obrázek ukazuje strukturu jednoduchého reflexního agenta ve schematické formě, a ukazuje, jak pravidla umožňují propojit jeho vjemy s akcemi.

Obrázek 17: Struktura jednoduchého agenta.

Jednoduchý reflexní agent hledá pravidlo, jehož podmínka odpovídá současné situaci (určené vjemem), a pak provede akci s tím pravidlem asociovanou: function Simple-Reflex-Agent(percept) returns action static: rules // soubor IF-THEN pravidel state <-- Interpret-Input (percept) rule <-- Rule-Match (state, rules) action <-- Rule-Action[rule] return action Stránka 52/122


Agenti sledující svět Jednoduchý reflexní agent pracuje pouze tehdy, když správné rozhodnutí může být vytvořeno na základě okamžitého vjemu. Pokud auto vpředu je současný model, je možné z jednoduchého obrázku z kamery poznat, zda svítí brzdová světla či ne. Starší modely mohou mít jiná uspořádání a jejich brzdění nemusí být detekováno. Proto musí agent-řidič udržovat určitý druh vnitřního stavu pro správný výběr akce. Zde není vnitřní stav příliš rozsáhlý – potřebuje předchozí snímek kamery k určení stavů, kdy se co rozsvítí nebo změní na autě vepředu při jeho brzdění, ukazování změny směru jízdy (blinkr, mechanická ručka, …) apod. Obdobně je nutno uvážit, že senzory nemusejí vždy poskytnout kompletní informaci o stavu na silnici, v jízdních pruzích apod. V takových případech musí agent udržovat nějakou vnitřní stavovou informaci k odlišení stavů světa, které generují stejný perceptuální vstup, ale jsou výrazně odlišné (tj. jsou zapotřebí výrazně odlišné akce). Např. nejede-li ve vedlejším pruhu auto nebo není-li vidět, generuje tentýž vstup, ale ve druhém případě je správnou akcí pokračování v původním pruhu, v prvním případě možnost přejetí do vedlejšího. Aktualizace vnitřní stavové informace vyžaduje dva druhy znalosti zakódované do agentova programu: 1. Je nutno znát, jak se svět vyvíjí nezávisle na agentovi ? např. předjíždějící automobil bude obecně blíže za námi než před okamžikem. 2. Je nutno znát, jak vlastní agentovy akce ovlivňují svět ? přejíždí-li agent do pravého pruhu, vzniká po něm přinejmenším dočasně mezera v původním pruhu, nebo že po cca pěti minutách jízdy směrem na sever se nachází cca pět kilometrů severně od místa, kde byl před pěti minutami (věci zdánlivě triviální pro člověka, ale pro strojagenta je nutno takto uvažovat). Schéma reflexního agenta s interním stavem:

Stránka 53/122


Obrázek 18: Inteligentní agent s rozšířením o indikaci vnitřního stavu.

function Reflex-Agent-With-State(percept) returns action static: rules // soubor IF-THEN pravide state // popis stavu současného světa state <-- Update-State (state, percept) rule <-- Rule-Match (state, rules) action <-- Rule-Action[rule] state <-- Update-State (state, action) return action

Agenti zaměření na cíl Znalost okamžitého stavu prostředí nemusí vždy stačit k rozhodnutí o činnosti. Na křižovatce může taxi jet doleva, doprava nebo rovně. Správné rozhodnutí zde závisí na tom, jaký je cíl jízdy. Agent tedy potřebuje ještě informaci o cíli jízdy. Agentův program pak může zkombinovat tuto informaci s informací o výsledcích možných akcí (tatáž informace byla použita k aktualizaci vnitřního stavu u reflexního agenta) k rozhodnutí o výběru správné akce k dosažení cíle. Někdy je to jednoduché (jedna akce), jindy složité (dlouhá posloupnost zatáčení apod. pro nalezení cesty k dosažení cíle). Umělá inteligence používá k tomuto účelu metody vyhledávání a plánování. Je dobré si povšimnout, že tento typ rozhodování se fundamentálně liší od používání pravidel typu IF – THEN v tom, že zahrnuje úvahy o budoucnosti: Co se stane, když udělám to-a-to? a Pomůže mi to nějak? U návrhů reflexních agentů se tato informace explicitně nepoužívá, protože návrhář předem stanovil správné akce pro různé případy. Reflexní agent brzdí, když před sebou uvidí svítit brzdová světla. Cílově zaměřený agent v principu může uvažovat o tom, že pokud má auto před ním rozsvícená brzdová světla, tak zpomalí. Z toho, jak se obvykle svět vyvíjí, plyne, že jediná akce k zamezení nárazu (dosažení cíle nesrazit se) je brzdit. Cílově zaměřený agent se Stránka 54/122

Cvičebnice pro samostudium Umělá inteligence II může zdát méně efektivní, ale je daleko flexibilnější. Začne-li např. pršet, agent může aktualizovat svou znalost o efektivnosti svých brzd – to může automaticky ovlivnit změny relevantních chování, aby se vyhovělo novým podmínkám. U reflexního agenta by bylo nutno přepsat velké množství pravidel typu podmínka-akce. Dále je cílově zaměřený agent také mnohem flexibilnější vzhledem k dosažení různých cílů. Jednoduchou specifikací nového cíle dojezdu lze získat agenta s novým/aktualizovaným chováním. Pravidla reflexního agenta, kdy zatočit a kdy jet přímo, fungují pouze pro jeden cíl dojezdu. Pro dojezd jinam musí být všechna vyměněna. Cílově zaměřený agent:

Obrázek 19: Struktura inteligentního agenta – cílově zaměřený agent.

Užitkově zaměření agenti Cíle samy o sobě nestačí ke generování vysoce kvalitního chování agenta. Např. existuje mnoho sekvencí akcí, které dostanou taxík do jeho určeného cíle – tím je tedy dosaženo cíle. Na druhé straně lze cíl ovšem dosáhnout za různých okolností: rychleji, bezpečněji, spolehlivěji, levněji apod. Cíle pouze poskytují hrubé rozlišení mezi přínosnými a nepřínosnými stavy. Obecnější míra výkonnosti by měla poskytnout exaktní srovnání různých stavů světa (nebo sekvencí stavů) podle toho, do jaké míry jsou pro agenta přínosné, pokud jich dosáhne. (Pro přínosnost se používá termín agentův užitek.) Užitek je tedy funkce, která mapuje určitý stav na reálné číslo, které dále slouží pro určení asociovaného stupně přínosnosti. Kompletní specifikace funkce užitku umožňuje racionální rozhodování ve dvou případech, nastanou-li potíže s cíli: 1. Pokud existují konfliktní cíle, pak pouze některých může být dosaženo (např. rychlost a bezpečnost). Funkce užitku zde stanoví vhodný kompromis. Stránka 55/122

Cvičebnice pro samostudium Umělá inteligence II 2. Pokud existuje několik cílů, na jejichž splnění se agent může zaměřit a žádného z nich nelze dosáhnout s jistotou, pak užitečnost poskytuje způsob, jak přiřadit váhu pravděpodobnosti úspěchu vzhledem k důležitosti dosažení cílů. Agent, který vlastní explicitní funkci užitku, může tedy vytvářet racionální rozhodnutí, ale musí porovnávat potenciálně dosažitelné užitky, k nimž vedou různé posloupnosti akcí. Cíle, i když jsou z tohoto hlediska hrubější, umožňují agentovi výběr akce přímo, a to za předpokladu, že akce vyhovují pro dosažení cíle. Existují také případy, kdy lze převést funkci užitku na soubor cílů takovým způsobem, že cílově zaměřený agent při použití těchto cílů dosáhne stejného rozhodnutí o činnosti jako užitkově zaměřený agent používající danou funkci. Jiným příkladem užitkově zaměřeného agenta je např. agent hrající nějakou hru (šachy), který musí vytvářet značně „jemná“ rozlišování mezi různými pozicemi vznikajícími na šachovnici. Užitkově zaměřený agent:

Obrázek 20: Struktura inteligentního agenta – užitkově zaměřený agent.

Stránka 56/122


Vlastnosti prostředí Prostředí mají několik charakteristik. Základní odlišnosti: Přístupné a nepřístupné: zda agentovy senzory umožňují poskytnout kompletní informaci o stavu prostředí. Pokud ano, je prostředí přístupné, jinak je nepřístupné. Senzory by měly umožnit získat údaje relevantní pro výběr akce. Přístupné prostředí má tu výhodu, že si agent nemusí udržovat vnitřní stavy sledovaného světa. Deterministické a nedeterministické: je-li následující stav prostředí zcela určen současným stavem a akcemi zvolenými agentem, pak se jedná o deterministické prostředí. V principu nemá agent starosti s nejistotou v přístupném a deterministickém prostředí. Zda je prostředí deterministické se obvykle musí určit přímo z hlediska agenta. Epizodické a neepizodické: v epizodickém prostředí je agentova znalost/zkušenost rozdělena mezi tzv. „epizody“. Každá epizoda se skládá z agentových vnímání následovaných akcemi. Kvalita agentovy akce závisí pouze na dané epizodě, protože následné epizody na předcházejících nezávisejí, co do jejich vlastní kvality. Epizodická prostředí mají výhodu v tom, že agent nemusí myslet dopředu. Statické a dynamické: pokud se prostředí mění během agentova uvažování, pak je prostředí z jeho hlediska dynamické, jinak je statické. Statická prostředí mají výhodu v tom, že během svého uvažování nemusí agent sledovat svět, a také se nemusí zabývat časem. Semidynamické: pokud se prostředí nemění v čase, ale agentova výkonnost na čase záleží, mluvíme o semidynamickém prostředí. Diskrétní a kontinuální: existuje-li omezené množství odlišných a jasně určených vnímání a akcí, pak se jedná o diskrétní prostředí (např. šachy jsou diskrétní prostředí – existuje pevné množství možných tahů v každé pozici). Řízení taxíku je kontinuální-rychlost a poloha taxíku včetně ostatních vozidel se mění v intervalu spojitých hodnot. Poznámka: Při dostatečně jemné úrovni granularity může dokonce i prostředí taxíku být diskrétní, protože obraz kamery je digitalizován na diskrétní hodnoty pixelů, ale smysluplný program agenta je normálně na abstraktnější úrovni, tj. na úrovni, kde je granularita považována za spojitou záležitost. Zjevně nejobtížnější případ nastane, když je prostředí nepřístupné, neepizodické a dynamické; obdobně je to i v případě prostředí dynamického. Rovněž se ukazuje, že většina reálných situací je tak složitá, že to, zda je prostředí doopravdy deterministické, je záležitost sporná a pro praktické účely se zachází se situací jako s nedeterministickou. Následující tabulka ukazuje typy prostředí pro některá známější prostředí. Stránka 57/122

Cvičebnice pro samostudium Umělá inteligence II Tabulka 3: Typy prostředí.

Prostředí

Přístupné Deterministické Epizodické Statické Diskrétní

Šachy s hodinami

ano

ano

ne

semi

ano

Šachy bez hodin

ano

ano

ne

ano

ano

Poker

ne

ne

ne

ano

ano

Backgammon

ano

ne

ne

ano

ano

Řízení taxi

ne

ne

ne

ne

ne

Medicínská diagnostika

ne

ne

ne

ne

ne

Analýza obrazů

ano

ano

ano

semi

ne

Robot třídící součástky

ne

ne

ano

ne

ne

Řízení čističky

ne

ne

ne

ne

ne

Interaktivní učitel angličtiny ne

ne

ne

ne

ano

Hodnoty v tabulce mohou ovšem záviset na tom, jak je vytvořen pojem (tzv. konceptualizace) prostředí a agentů. Např. poker je deterministický, pokud si agent může udržovat údaje o sledování pořadí karet v balíčku, jinak bude poker nedeterministický. Obdobně může dojít k tomu, že prostředí je epizodické na vyšší úrovni, než se odehrávají agentovy jednotlivé akce. Např. šachový turnaj se skládá z posloupnosti her (partií). Každá partie je epizoda, protože přínos tahů, provedených agentem v jedné partii, pro celkovou úroveň agentovy výkonnosti není ovlivněn tahy z příští partie. Na druhé straně je nutno třeba brát v úvahu, že během jedné partie jsou jednotlivé tahy spolu určitým způsobem provázány, takže agent je musí promýšlet v nějakém počtu dopředu.

Programy pro prostředí Obecný program prostředí ilustruje základní vztah mezi agenty a prostředími: procedure Run-Environment(state, Update-Fn,agents, termination) inputs: state // počáteční stav prostřed Update-Fn // funkce pro modifikaci prostředí agents // soubor agentů termination // predikát k otestování na závěr repeat for each agent in agents do Percept[agent] <-- Get-Percept(agent, state) end for each agent in agents do Action[agent] <-- Program[agent]Percept([agent]) end

Stránka 58/122

Cvičebnice pro samostudium Umělá inteligence II state <-- Update-Fn (actions, agents, state) until termination(state) Uvedený

základní

program

jeho vjemy (percepce),

od

pracuje každého

v principu

tak,

že předává každému

agenta získává jeho akci,

agentovi

a pak aktualizuje

prostředí. Simulátory prostředí mohou být založeny na uvedené programové kostře: Simulátor dostane jako vstup jednoho či více agentů a zařídí, aby opakovaně každý agent obdržel správné vjemy; poté získá akce agentů. Následně simulátor aktualizuje prostředí na základě akcí, případně na vlivu dalších dynamických procesů v prostředí, které nejsou agenty (např. déšť). Prostředí je tedy definováno počátečním stavem a aktualizační funkcí. Poznámka: každý agent pracující v simulovaném prostředí by samozřejmě měl pracovat i v reálném prostředí, které poskytuje tytéž druhy vjemů a přijímá tytéž druhy akcí. Procedura Run-Environment musí korektním způsobem testovat agenty v prostředí. Pro některé druhy agentů (např. takové, kteří se účastní dialogu v přirozeném jazyce) může postačovat pouhé sledování jejich chování. Pro získání detailnějších informací o agentově výkonnosti se začleňuje nějaký kód pro měření výkonnosti. Může to být např. funkce RunEval-Environment

měří výkonnost každého agenta a vrací seznam výsledných skóre.

Proměnná score obsahuje sledování skóre pro každého agenta: function Run-Eval-Environment(state, Update-Fn,agents, termination, PerformanceFn) returns scores local variables: scores // vektor daný počtem agentů // na počátku vše 0 repeat for each agent in agents do Percept[agent] <-- Get-Percept(agent, state) end for each agent in agents do Action[agent] <-- Program[agent]Percept([agent]) end state <-- Update-Fn (actions, agents, state) until termination(state) return scores Měření výkonnosti obecně může záviset na celkové posloupnosti stavů prostředí generovaných během činnosti programu. Obvykle se však používá jednoduchá akumulace (součet, výpočet průměru, nebo vzetí maxima). Například uvážíme-li měření výkonnosti agenta vysávajícího podlahy a použijeme-li jako míru celkové množství odstraněné špíny, pak scores jednoduše udržuje hodnotu o tom, kolik špíny již bylo doposud vysáto. Run-EvalStránka 59/122

Cvičebnice pro samostudium Umělá inteligence II vrací míru výkonnosti pro jedno prostředí, definované jedním počátečním stavem a konkrétní aktualizační funkcí. Environment

Agent je však obvykle navržen pro práci ve třídě prostředí, čímž se rozumí celý soubor různých prostředí. Například se může jednat o šachový program, který hraje proti širokému souboru lidských a strojových oponentů. Pokud bychom takový program navrhli proti jedinému protihráči, pak by mohlo dojít k tomu, že se sice využijí konkrétní slabosti daného protivníka, ale nemuseli bychom získat program hrající obecně dobře. Z toho plyne zřejmý požadavek: pro měření výkonnosti agenta je zapotřebí generátor prostředí, který vybírá konkrétní prostředí (s určitou pravděpodobností) v němž je agent testován. Nás pak zajímá průměrná agentova výkonnost přes celou třídu prostředí. Je nutno ovšem při realizaci simulátoru prostředí dbát na rozdíl mezi stavovou proměnnou simulátoru prostředí a stavovou proměnnou v agentovi: agent nesmí vidět stavovou proměnnou simulátoru prostředí, jeho stavová proměnná může pouze nabývat hodnot na základě agentových vjemů, bez kompletního přístupu k informacím.

Příklad prostředí a agentů ve světě vysávání špíny Uvedený svět lze popsat takto: Vjemy: každý vysavačový agent dostává tříprvkový vektor vjemů pro každé kolo vysávání. První element (z dotykového senzoru) dává 1, pokud stroj do něčeho vrazí, jinak 0. Druhý element (foto senzor na spodku stroje) dává 1, pokud je zjištěno smetí, jinak 0. Třetí element dává 1, pokud je agent ve výchozím místě („doma“), jinak 0. Akce: je k dispozici pět akcí – jdi vpřed, otoč se doprava o 90°, otoč se doleva o 90°, vysaj smetí, vypni se. Cíle: cílem pro každého agenta je odstranit smetí a vrátit se domů. Exaktnější zadání: 100 bodů za každý vysátý kus smetí, -1 bod za každou akci, -1 000 bodů pokud se agent vypne jinde než doma. Prostředí: prostředí je dáno mřížkou se čtverci. Některé čtverce obsahují překážky (zdi, nábytek, …), jiné obsahují volný prostor. Některé volné čtverce obsahují smetí. Každá akce „jdi vpřed“, je přesun na další čtverec, pokud tam není překážka – v tom případě agent zůstane stát v původním čtverci, ale dotykový senzor je nadále aktivní. „Vysaj smetí“ vždy zlikviduje (odstraní) detekovaný kus smetí. „Vypni se“ vždy ukončí simulaci. Složitost prostředí lze měnit ve třech směrech:

Stránka 60/122


Tvar místnosti: v nejjednodušším případě má místnost n × n čtverců (pro nějaké pevné n). Obtížnější případ nastane změnou na tvar obdélníka, tvar písmene L, nebo nepravidelný tvar, případně série místností spojených chodbami. Nábytek: umístění nábytku vytváří složitější problém. Z hlediska agenta-vysavače nemusí vjem rozlišovat mezi zdí a kusem nábytku, obojí aktivuje senzor tak, že vydá hodnotu 1. Rozmístění smetí: nejjednodušší je smetí rozmístit rovnoměrně v místnosti. Realističtější je více smetí umístit v určitých lokacích (např. dlouhá a velmi používaná cesta do další místnosti nebo kolem židle u jídelního stolu).

Stránka 61/122


Multiagentní systémy (MAS) Základní pojmy Za počátečním rozvojem a vývojem agentních systémů) lze hledat podporu v rámci distribuovaná umělá inteligence. Podstatou je vytvořit decentralizované nebo distribuované inteligentní jednotky – inteligentní agenty. Snahou je, aby tyto autonomní jednotky byly schopné řešit určité problémy (lokálního, nebo globálního charakteru). Původně se tyto jednotky nazývaly aktéři, z nich se následně vyvinulo označení agenti. Princip autonomního agenta (tzv. reaktivního agenta) popsal jako první Rodney Brooks, pracovník laboratoří umělé inteligence z MIT. Princip inteligentních agentů (Intelligent Agents) popsal následně M. J. Wooldridge. Ve většině případů se agent rozhoduje na základě svých aktivně dostupných znalostí. Pak hovoříme o tzv. racionálním agentovi. V intenčním systému (intence – záměr) sestavuje agent plán k dosažení vytyčeného cíle (systém počátek, cíl), nebo užitím BDI principu (Beliefes, Desires and Intention) se pak jednání agenta řídí jistým druhem mentálního stavu a pozorujícím své okolí. Zde se zavádějí další dva stavy agentovy mysli, a to jsou důvěra (v informace o okolním prostředí a ve výsledky svých akcí) a přání (tužby, záměry). Zatím nejpopulárnějším přístupem k řešení tohoto pojetí je PRS (Procedural Reasoning Systém). Jedná se o systémy schopné se projevovat v dynamicky se měnícím prostředí. Distribuovaná umělá inteligence Některé úlohy je z výpočetního hlediska výhodnější rozdělit na několik dílčích (separátních) procesů, které řeší problémy z dané oblasti podle úrovně kompetence, za pomoci vzájemné kooperace, s cílem dosáhnout cíle v řešení konkrétního "globálního" problému. Agenti veškeré své činnosti podřizují takto specifikovanému výsledku, tomuto přístupu se říká předpoklad benevolence. Koordinace společenství, ve kterém je splněna tato podmínka se říká kolaborace. Takový přístup se nazývá distribuované řešení problému a spadá do oblasti distribuované umělé inteligence. Decentralizovaná umělá inteligence Decentralizovaná umělá inteligence je v protikladu s inteligencí distribuovanou. Sice zde agent taktéž je konstruován k působení v multiagentním prostředí, jeho vazba k ostatním agentům je volnější, zaměřen je na plnění zejména individuálních cílů. Omezené zdroje a schopnosti nutí agenty vytvářet koalice a kooperující skupiny. Ústup od benevolence, tvorba reálnějších otevřených systémů. Problémem u tohoto typu systémů je jeho koordinace skrz chybějící centrální řídící mechanizmus takto utvořeného společenství.

Stránka 62/122


Motivace Řešení složitých a rozsáhlých úloh: • zvýšením flexibility a adaptability na měnící se okolní prostředí, • zvýšením autonomnosti jednotlivých zdrojů znalostí v rámci modulární architektury (pro řešení problémů, kde selhává centralizované řízení), • volnou integrací modulů pomocí komunikace formou vzájemného zasílání zpráv „peer-to-peer“ (pro propojení různých systémů a to ať již na úrovni softwaru, nebo struktury řízení), • pro efektivní využití prostorově dislokovaných informačních zdrojů (sítě senzorů, získávání dat ze sítí, internetu), • redukcí role centrálního prvku a posílení role jedince. Na základě těchto předpokladů vznikly tzv. multiagentní systémy (Multi-agent system, MAS). Definice: Multiagentní systém je možno popsat jako skupinu diskrétních volně propojených autonomních systémů (agentů), které spolupracují v zájmu dosažení společného cíle. V určitém přeneseném smyslu se jedná o simulování lidského společenství. Použití těchto systémů ve formě technického řešení přináší podobné výhody jako u týmové práce. S ohledem na paralelizaci přístupu lze rapidně zkrátit dobu řešení problému. Taktéž lze snížit komunikační režii, protože jednotliví členové týmu si nepředávají dál všechny zjištěné údaje, ale především své závěry o nich, jen co je potřeba k řešení (přesně naopak je tomu u centrálně řízeného distribuovaného systému). Zvyšuje se tak operativnost a spolehlivost, protože komunita může přibírat další členy, tvoří se specialisté (správa rolí), popřípadě se mohou jednotliví jedinci zastupovat. Stejně jako v lidské populaci se u MAS zkoumají vzájemné sociální interakce. Tyto vzájemné vazby lze rozdělit na: • koordinaci, • kooperaci, • komunikaci. Mnohdy se jednotlivé vazby vzájemně funkčně prolínají. Koordinací chápejme aktivity spojené se snahou dosáhnout efektivně cíle. Kooperace zasahuje do problematiky vzájemné výpomoci více diskrétních skupin při řešení stejného problému. Spadá sem i časová a prostorová synchronizace. Následně komunikace je velmi důležitým prvkem všech činností agentů. Předpokládá se vhodný komunikační jazyk s dobře definovanou sémantikou a vyšší úrovní abstrakce.

Stránka 63/122

Cvičebnice pro samostudium Umělá inteligence II Agent je definován jako aktivní prvek systému (systému tvořeného mnoha obdobnými objekty) vytvořený člověkem za určitým účelem. Výsledkem činnosti agenta je pak transformace AS z aktuálního do cílového stavu (stavu žádaného – cíle řešení). Rozeznáváme tři přístupy umožňující tuto transformaci: • postupná transformace do požadovaného stavu, • konzultace s expertem (člověkem) a pak postupná transformace do požadovaného stavu, • zkoumání systému, hledání vnitřních zákonitostí, získání nových poznatků a pak postupná transformace do požadovaného stavu. • Individuálního agenta lze charakterizovat také podle toho, zda a jak je schopen reagovat různé varianty řešení při naplňování globálního cíle.

Základní charakteristiky agenta Autonomnost – agenti jsou samostatné na cíl orientované moduly, schopné samostatného řešení specifických úloh bez nutnosti komunikovat s okolím, schopnost komunikace je však zachována, mohou koordinovat činnosti a kooperovat s jinými agenty v rámci dané komunity. Mají možnost vstupovat do komunity, opouštět ji, poskytovat výsledky nebo o členství v komunitě požádat. Sociálního chování – agenti vytváří sociální vazby za účelem dosažení společných cílů, udržování informace o jiných agentech a vytváření úsudků o nich, sdružování do koalic a týmů, od nichž očekávají vzájemný prospěch. Nutnou podmínkou je schopnost upravovat model pohledu na okolní svět a to na základě obměňujících se vzájemných vazeb. Reaktivita – agenti jsou aktivováni událostmi (obdoba událostního programování), schopni reakce v souladu s vnímáním reálného času. K dispozici má předem známou množinu akcí. Výběr obslužné akce je silně závislý na splnění podmínek, jak agent vnímá vnější svět. Intencionalita – schopnost mít na paměti dlouhodobé cíle, rozklad problému na podproblém (strategie), organizace chování k dosahování těchto cílů, formulace vlastních plánů a využití svých úsudků v dalším rozhodování při dosahování cíle. Do volby cíle se promítá i osobní motivace agenta pro jeho dosažení. Agenty lze rozlišit na následující typy: • Agent inteligentní – má schopnost plnit cíle s využitím vnitřní logiky, metodou dedukce. • Agent reaktivní – má schopnost reakce na podněty z okolí. • Agent deliberativní – rozvážný – má schopnost plánovat postup svých akcí, ovlivňovat prostředí a to takovým způsobem, aby získal strategickou a taktickou výhodu.

Stránka 64/122

Cvičebnice pro samostudium Umělá inteligence II • Agent kognitivní – schopnost vyvozovat logické závěry z pozorování okolí, ukládání tohoto pozorování do interní báze znalostí. Taktéž sem patří schopnost mapování a vyhodnocování okolního prostoru (scény). • Agent racionální – má výše specifikované vlastnosti. Na základě získaných poznatků je schopen učit se a plánovat svou činnost s ohledem na dosažení známého cíle. Na základě předchozí specifikace agentního systému a vlastností agenta je zřejmé, že není možné vytvořit jednoznačnou definici popisující element agentního systému – agenta. V následujícím textu je uvedeno několik nejčastějších definic agenta a to vzhledem k aplikačnímu nasazení. Definice: Agent je výpočetní proces s jedním centrem řízení a s určitým (lokálním) cílem. Agenti koordinují hlavně své znalosti, cíle, schopnosti a plány tak, aby je mohli využívat společně při akcích a řešení úloh. Agenti v multiagentovém systému mohou ve své činnosti směřovat k jednomu globálnímu cíli nebo k jednotlivým odděleným cílům, které spolu mohou, ale nemusejí souviset. Agenti sdílejí znalosti o úlohách a řešeních (Bond, Gasser, 1988). Definice dle Wooldridge a Jenningse (Wooldridge a Jennings, 1995) se dělí na obecnější a specifičtější. Následuje jejich zkrácená podoba. a) Agent (obecnější verze) je hardwarový nebo častěji softwarový systém, který je: autonomní, sociální, reaktivní, proaktivní. b) Agent (specifičtější definice) v tomto případě, krom již vyjmenovaných kritérií, je autonomní, reaktivní a proaktivní počítačový systém, jehož jednání vychází z předpokladu, že jde o systém, který je i: mobilní, korektní, benevolentní, racionální. Pod pojmem použitými pojmy je v tomto případě chápáno následující. Autonomnost je schopnost agenta pracovat bez zásahu člověka, schopnost řídit svoje akce a do jisté míry i vnitřní stav. Sociální adaptabilita je schopnost interagovat s ostatními agenty a to za pomoci jazyka určeného pro komunikaci agentů. Reaktivnost se projevuje uvědomováním si svého okolí a včasnou reakcí na jeho změny. Pod pojmem proaktivnost je schopnost reagovat na podněty z okolí ne na základě aktuálního rozpoložení agenta, ale v rámci dlouhodobé strategie. Následně mobilností se míní schopnost pohybovat se elektronickou sítí, korektnost je vlastnost agenta, kdy vědomě nepředává nepravdivé informace dál v rámci řetězce. Benevolentnost je snaha udělat vše o co je žádán, v rámci svých možností. Racionálnost je jednání s ohledem na dosažení svých cílů, nikoliv aby zklamal. Agenty na obecné rovině lze do následujících oblastí: • Biologičtí agenti – lidé • Techničtí agenti – roboti • Programoví agenti – softboti Stránka 65/122

Cvičebnice pro samostudium Umělá inteligence II • agenti v počítačových hrách (simulování soupeře), o počítačové viry, o agenti pro specifické úkoly (rezidentní), o agenti – entity umělého života (simulace, umělé světy).

Znalosti a jejich úloha Agent musí disponovat znalostmi o svém prostředí, ve kterém je aktivní složkou. Získané znalosti na základě své interakce inovuje, aby byly stále aktuální, vzhledem k měnícím se vzájemným vztahům a rozvoji. Neboť agent je součástí většího uskupení, proto poměrná většina znalostí je orientována do sociální oblasti. Znalosti agenta lze rozdělit na: • Problémově-orientované znalosti – „asociální“ typ znalostí, sloužící k lokálnímu řešení úloh (tvorba expertíz, hledání ve vlastní znalostní databázi agenta). • Znalosti o sobě samém – znalosti o vlastním chování, vnitřním stavu, závazcích, omezeních atp. • Sociální znalosti – znalosti o chování jiných agentů, o jejich schopnostech, zatížení, zkušenostech, závazcích, o jejich znalostech, záměrech a víře. Sociální znalosti umožňují agentům: • • • • •

delegovat odpovědnost, provádět řízení, snížit složitost řešeného problému, rozklad na podproblém, provádět kontrolu výstupů členů uskupení, utvářet uskupení, partnerství, získávat informace.

Adaptace (učení) je nedílnou vlastností všech živých organismů. Taktéž agent by měl být schopen rozhodovat se na základě dřívějších zkušeností. S ohledem na tuto skutečnost se rozvíjí matematické modely podporující rozhodování a výběr vhodné strategie a v neposlední řadě i přístupy rozvíjející schopnost strojového učení. Okolní prostředí agenta Definice: Prostředí je vše, s čím agent přichází do styku a co s tím bezprostředně interaguje. Prostředí může být: • Plně nebo částečně pozorovatelné – plně pozorovatelné okolí je v tom případě, kdy lze vyhodnotit ucelený stav. • Statické nebo dynamické – statické prostředí se může měnit pouze s akcemi agenta, dynamické se proměňuje nezávisle na agentovi.

Stránka 66/122

Cvičebnice pro samostudium Umělá inteligence II • Deterministické nebo nedeterministické – v deterministickém prostředí je následující stav dán stavem předchozím. Změna je na základě vykonané akce. Toto prostředí je na rozdíl od nedeterministického silně předvídatelné. • Diskrétní nebo spojité – diskrétní prostředí má konečnou nebo spočetnou množinu stavů. V tomto případě se může jednat o popis prostředí na úrovni dat ze senzorů. Nástroje pro návrh Pro účely popisu mentálních stavů agenta se používají např. formální BDI logiky. Tato zkratka vznikla složením představ o prostředí (Beliefs), tužeb (Desires) a záměrů (Intentions). Jak je zjevné z popisu, velmi dobře je schopna vystihnout stavy agentů. Algoritmus podle Wooldridge: Plán je posloupnost akcí, které vedou k dosažení nějakého záměru. Záměr je vybrán podle agentova přání v závislosti na aktuálním stavu prostředí. Může docházet k přehodnocování plánu, filtraci záměrů, kontrole, zda plán odpovídá záměru, atd. Základní algoritmus: opakuj { přijmi vjem z okolí uprav vnitřní model prostředí vyber záměr sestav plán pro dosažení záměru spusť plán } Tento základní algoritmus je jeden z mnoha algoritmů vystavění agenta jako jednotky řízené nekonečným cyklem. Jako vhodný nástroj pro návrh se používá PRS architektura (Procedural Reasoning System). V rámci této architektury je zavedena knihovna procesů (seznam obslužných plánů), které se využívají pro sestavení sledu při řešení úkolu naleznutí vhodné cesty z počátečního stavu do požadovaného cíle řešení. Plán se sestává z podmínky zpuštění, posloupnosti akcí (těla plánu), výsledku.

Sociální aspekty v multiagentních systémech Multiagentní systémy jsou takové systémy, kde se v prostředí pohybuje více než jeden agent. Z této opětovně specifikované definice multiagentního systému je zřejmé, že v prostředí s více prvky, agenty, bude nutné řešit jejich vzájemnou koexistenci. Multiagentní problematika s sebou přináší nová témata, například témata sociální (analogie lidského společenství). S tím souvisí třeba vytváření skupin na základě společných zájmů a cílů. Proto musí nutně docházet ke spolupráci agentů, a je tedy zapotřebí vytvořit prostředky pro vzájemnou komunikaci. Stránka 67/122


Společné schopnosti agentů a jejich zájmy Společné vlastnosti agentů: • vnímaní pojmů (terminologie), • pravidla vzájemné komunikace (komunikační protokol), • jazyk. Agenti mohou navzájem ovlivňovat svoje chování, působit na ostatní agenty, být s nimi v souladu, nebo působit proti nim. Další hledisko klasifikace agentů: • kooperativní – mají shodné cíle, • kompetitivní – mají protichůdné cíle, • kolaborativní – navzájem spolupracující. Koordinace je proces probíhající v multiagentovém společenství, kterým se dosahuje takového propojení jednotlivých komponent v systému, které umožňuje řešení daného problému dosažením decentralizace vykonávaných úkolů. Kooperace je řízenou formou koordinace s účelovým uspořádaním agentů ve skupině s cílem dosáhnout společného řešení problému. Nejčastěji mají agenti partikulární zájmy a dochází pak velmi často k souladu nebo ke kolizím záměrů jednotlivých agentů.

Strategie agentů Strategie agenta udává, která akce z báze akcí bude vykonána jako reakce na aktuální stav prostředí. Dominantní strategie je ta nejlepší strategie z výběru. Nashova rovnováha Strategií skupiny je tzv. Nashova rovnováha, pokud každá ze strategií je nejlepší individuální strategií příslušného agenta vzhledem k ostatním strategiím zvoleným ostatními agenty ve skupině. Pro výběr strategie optimální pro celou skupinu agentů je nutná vzájemná komunikace. Dalším předpokladem je nutnost vědět o problému výběru strategie, spolupodílet se na výsledku. V procesu výběru dochází taktéž k ústupkům nutným k dosažení cíle.

Stránka 68/122


Dohody a koalice Základem pro vytváření dohod a koalic jsou společné postoje a zaměření členů skupiny. Skupinu pak tvoří agenti, kteří přijmou závazky a obecná pravidla (normy) skupiny a řídí se svými zájmy. Důraz je kladen na vzájemnou komunikaci. Bez této důležité složky nelze zajistit koordinaci vzájemně uceleného záměru. Racionálně orientovaný agent do vzájemného vztahu (závazku) vstoupí jen tehdy, pokud očekává zisk. Závazky Agenti vyjadřují vůli spolupracovat prostřednictvím vzájemných závazků. Závazkem je udržování mentálního postoje (uvědomění si dluhu). Typy závazků: • dosažení cíle – např. nalezení protiopatření na riziko, • status quo – např. závazek informovat při zjištění rizika, • obecně podmíněný. Ve většině případů jsou mezi agenty sjednávány podmíněné závazky. Výjimku tvoří normy skupiny, které jsou jednoznačně dané. Sociální skupinu agentů lze definovat i tak, že je dána normami, závazky, strategií a agenty, kteří tyto spojitosti sdílejí po celou dobu své existence v této skupině. Skupiny lze kategorizovat podle důvodů zájmů o spolupráci na: • skupiny se sdílením cílů, • skupiny se sdílením prostředků, • skupiny s poskytováním informací.

Stránka 69/122


Komunikace v MAS Komunikace v rámci MAS je vzájemná interakce. V rámci této komunikace dochází také k vzájemné koordinaci mezi agenty a kooperaci při naplňování cíle. Důraz v této kapitole bude dán na decentralizované, distribuované řešení na úrovni inteligentních agentů. Neboť součástí komunikace je základním prvkem okolí agenta, je nutné si okolí náležitě vymezit. Definice: V multiagentních systémech tvoří okolí agenta i ostatní agenti, kteří jsou součástí systému. Záměrem agenta tedy může být i ovlivnění vnitřního stavu jiného agenta, jež je součástí okolí. Způsoby ovlivnění: • Nepřímé – agent mění stav okolí jiného agenta, na základě této změny dochází i k jeho ovlivnění. • Přímé – agent působí přímo a to ve formě vzájemné komunikace.

Dialogy a zprávy Důvodů ke vzájemné komunikaci může být více, lze rozlišit následující typy dialogů: • Dotazování – hledání informace tam, kde se předpokládá její nalezení (u zdroje). • Hledání informace – společné pátrání více agentů po informaci, kterou nemají v daný čas k dispozici. • Přesvědčování – snaha agenta o získání jiného agenta na svou stranu s předem definovanou strategií jeho využití. • Vyjednávání – agenti vyjednávají o podmínkách sdílení prostředků nebo poskytnutí služeb a to tak, aby všichni dosáhli maximálního užitku z této transakce. • Porada – cílem je nalezení řešení problému, které je v zájmu celé skupiny. Agenti sdílí své znalosti a schopnosti a radí se na dalším postupu. • Eristický dialog – je dialog s expresivní výměnou informace (hádka) za účelem dosažení cíle. Definice: Komunikace je proces výměny informací ve formě výměny elementárních zpráv. Obdobně jako u e-mailu má také zpráva svého odesílatele, příjemce, svůj obsah. Součástí je i identifikace typu zprávy (otázka, informace, nabídka). Pokud se bude brát v potaz taktéž reálnost komunikace (usazení komunikace v čase), nutné použít časová razítka. Jen takto jde určit, zda je daná zpráva, vzhledem ke svému obsahu, stále aktuální. Pro vzájemnou komunikaci, výměnu informací, musí agent najít partnera. Zde je nutné taktéž vybrat vhodné komunikační rozhraní. Zde se může jednat o tzv. "vysílání" – broadcasting, nástěnku, diskuse aj. Stránka 70/122


Nedílnou součástí komunikace je i komunikační strategie. Tedy do komunikace se prolíná i komunikační zabarvení zprávy. Stejně jako v lidské komunikaci, informace, žádost, lze sdělit několika způsoby a pokaždé s jiným výsledkem, odezvou z druhé strany. Součástí každé komunikace je tedy i psychologie této komunikace. Rozdělení komunikačních aktů: • • • • •

oznamovací ("Průchod je volný."), přikazovací ("Zavřete!"), zavazující (Zítra to zařídím."), expresivní ("Je mi líto, že průchod není volný!"), deklarační ("Stanovuji hodnotu atributu na xy!").

Příklad: Úkolem je zmapovat vyhrazený prostor a sesbírat na něm vzorky potravy k další analýze. Rozmístění potenciální potravy není předem známo. Předpokládá se, že potraviny se ve vymezeném prostoru shlukují (aleje, farmy, atd.). O mapových podkladech není dopředu nic známo. Lze si představit jako prozkoumávání mapy v počítačové hře. Rozbor úlohy: Klasický přístup je vytvořit zařízení, které v prvním kroku zmapuje vymezený prostor a to včetně nalezených zdrojů potravy a následně bude tyto potravinové zdroje shlukovat – sbírat. Tento přístup má však svá omezení. • Časová náročnost, hardwarová a softwarová složitost (ekonomicky náročné). • Rychlost sběru, s ohledem na prvotní mapování terénu a následný sběr, nebude velká (časová náročnost). • Vlastní sběr ovlivní i potenciální poruchovost "jednoho" sběrného zařízení (velká pravděpodobnost selhání). Tento problém lze vyřešit vytvořením skupinky reaktivních agentů. Tito agenti se rozptýlí po vymezeném prostoru, sesbírají vzorky potravy a přesunou je do centrálního uložiště. Na této základně je vhodné zprovoznit vysílání rádiového, popřípadě jiného signálu, za pomoci kterého lze identifikovat základnu a určit vzdálenost od ní. Již prozkoumaný prostor lze označit nějakou značkou. Tato značka by měla vyjadřovat, zda v daném prostoru byl nalezen vzorek potravy (silnější signalizace – větší značka). Vlastnosti zvoleného řešení: • Systém je robustní (stabilní). Selhání jednoho agenta neohrozí sběr vzorků. • Systém je adaptivní a flexibilní. Změna okolního prostředí (terénu) nemá zásadní vliv na řešení. • Agenti maji jednoduchý program obsluhy (hledání vzorků, návrat na základnu). Stránka 71/122

Cvičebnice pro samostudium Umělá inteligence II • Komunikace a vzájemná koordinace mezi agenty je zabezpečena za pomoci značek. • Jednoduché na vytvoření a naprogramování. Nepřipadá vám uvedená úloha povědomá? Podobného přístupu používají i mravenci pro organizování svých činností. U MAS se člověk snaží o jejich zdárné napodobení, ale vlastní základ je obdobný. Jedná se o další přístup, kdy se bere již vývojem v přírodě ověřená věc a aplikuje se na podobné problémy z jiné roviny lidského společenství.

Jazyky určené ke komunikaci Nesmí se zapomínat, že by nebylo žádné komunikace bez určení komunikačního protokolu a vymezení komunikačního jazyka. Následně jako prostředek komunikace se může použít např. posílání zpráv. Každý jazyk je dán svou abecedou, syntaxí a sémantikou. Sdílení informace probíhá na následujících třech úrovních: • syntaktická – problém je jednoduchý, syntaxi lze snadno definovat; • sémantická – tvorba znalostních ontologií; • pragmatická – s kým hovořit, kde ho najít, jak iniciovat komunikaci – není složité. V současné době se rozvíjí specifikace dvou jazyků založených na myšlence komunikačních aktů – jazyk KQML (Knowledge Query Manipulation Language) a ACL (Agent Communication Language) organizace FIPA (Foundations for Intelligent Physical Agents). Oba dva jazyky jsou si velmi podobné v používání komunikačních aktů a ve filosofii používání zpráv.

KQML Jazyk KQML neexistuje v podobě interpretovaného nebo kompilovaného jazyka běžícího na konkrétních počítačových platformách. Jedná se o knihovnu komunikačních aktů s jasně vymezenými významy a cílem stanovit ucelený rámec pro meziagentovou komunikaci. Jazyk vyjadřuje konkrétní řečový akt, který se liší dle typu (dotaz, nabídka, otázka, souhlas, odmítnutí). Každá zpráva obsahuje identifikátor řečového aktu a následně prvky zprávy ve formě dvojice (identifikátor – obsah). Implementace tohoto jazyka obsahuje několik vrstev, které jsou navzájem nezávislé. Nejvyšší vrstvu tvoří přenosová vrstva založená zejména na protokolech TCP/IP, na rozšíření elektronické pošty MIME a protokolu UDP. Jedná se o přenosový rámec. Druhou vrstvu tvoří vlastní komunikační akt., poslední vrstvou je vlastní komunikovaný obsah. Obsah zprávy je doplněn identifikaci příjemce, odesílatele, ontologii atp.

Stránka 72/122

Cvičebnice pro samostudium Umělá inteligence II Každá zpráva se skládá ze jména performativu a příslušících parametrů. Vlastní obsah zprávy může být zaznamenán v libovolném jazyce a je uveden jako jeden parametr této zprávy. Typická zpráva: (ask-if :sender agent A :receiver agent B :language PROLOG :ontology blocks :content “pozice(X,Y)”) Obsahem performativu může být další perfomativ ve formě požadované odpovědi a může dokonce docházet k vícenásobnému (rekurzivnímu) vnořování.

Tři typy performativů • Performativy pro vedení diskuse: o ask-if, ask-all, ask-one, tell, untell, deny, insert, uninsert, delete-one, o delete-all, undelete, advertise, unadvertise, subscribe • Performativy pro zasahování do diskuse: o error, sorry, standby, ready, next, rest, discard • Performativy pro síťování a podporu facilitátora: o register, unregister, broadcast, forward, transport-address, broker-one, o broker-all, recommend-one, recommend-all, recruit-one, recruit-all Jazyk KQML předpokládá, že většina komunikačních procedur mezi agenty probíhá nepřímo za pomoci facilitátora. Každý facilitátor zodpovídá za jednu předmětnou doménu. Veškerá komunikace vně domény jde výlučně přes příslušné facilitátory.

Budoucnost KQML a ACL Výhody komunikačních jazyků KQML a ACL lze shrnout do následujících bodů: • • • •

oddělení obsahové vrstvy od komunikačního aktu, nezávislost jazyka obsahu zpráv od komunikačního jazyka, snaha o formální definici sémantky komunikačního jazyka, deklarativní forma.

Mezi nevýhody lze zahrnout následující: • neexistuje (kromě roviny akademického výzkumu) implementace žádného z obou jazyků pro přímé počítačové zpracování, • sémantika je založena na jazyku, který používá modálních operátorů, které namají zakotvení v existujících teoriích využívající modální logiky, • absence řešení na úrovni přenosových protokolů a bezpečnosti.

Stránka 73/122

Cvičebnice pro samostudium Umělá inteligence II V současné době narůstají snahy skloubit výhody jazyků KQML a ACL s výhodami jazyka XML (Extensible Markup Language), který se stává standardem pro komunikační výměnu v oblasti internetu. Takto vytvořené zprávy mohou využívat komunikačního rozhraní (HTTP) i zabezpečení, které může poskytovat SSL. Následně zprávu může interpretovat XML parser, již netřeba implementoval překladač jazyka KQML. XML nemá definovanou sémantiku, neřeší se ani použití RDF (Resource Description Framework), proto zápis minulé ukázky v XML může vypadat následovně: <xml-kqml> sender = "agent A" receiver = "agent B" pozice(X,Y) Nepřímá komunikace Vlastní komunikace lze rozdělit do několika kategorií, podle zvoleného kritéria dělení. Základním kritériem je způsob, jakým se dostane zpráva od odesílatele k příjemci. Zprávu je možné doručit přímo (přímá komunikace), nebo za pomoci zprostředkovatele (nepřímá komunikace.

Metody navazování vzájemné komunikace Definice: Komunikace – agent má k dispozici svůj vlastní komunikační jazyk, dokáže formulovat zprávu a určit její význam. Možné metody navazování komunikace: • • • •

vysílání - vzájemná interaktivní komunikace, nástěnka - pasivní forma komunikace, komunikace pomocí prostředníka - zprostředkovaná volba předávání zpráv, sociální model - vzájemné sdílení.

Vysílání (broadcasting) Používá se v distribuovaných systémech, podstatou je rozesílání zpráv všem dostupným účastníkům. V multiagentním systému agent rozešle žádost o navázání komunikace všem známým agentům, s nimiž má k dispozici (má aktivní) komunikační kanál. Nevýhodou je Stránka 74/122

Cvičebnice pro samostudium Umělá inteligence II přehlcení informačního kanálu zprávami (mnohdy nevyžádaná komunikace) a zpracování zprávy příjemci zpomaluje činnost systému. Lze ale najít vhodného partnera vždy, když partner existuje (všichni jsou osloveni). Nástěnka (Black Board) Nástěnka je pasivní komunikační prostředek, agenti mohou na nástěnku informace umísťovat a taktéž tyto zprávy číst. Lze taktéž provádět monitoring nástěnky (jak často čtena, kdo přistupuje). Nevýhodou je off-line komunikace, tedy vznikají prodlevy ve vlastní komunikaci, proto se tento prvek moc často nepoužívá. Komunikace pomocí prostředníka Prostředníkem může být mediator, broker nebo facilitator. Role takového agenta je zprostředkovávat komunikaci mezi vhodnými partnery (vzájemně vybranými protějšky). Prostředník identifikuje požadavky komunikujícího a v součinnosti se znalostí ostatních potenciálně komunikujících agentů (schopnosti, znalosti, zaměření) zvolí komunikační protějšek. Prostředník může řídit i diskusi, hlasování, dražbu. Sociální model Sociální model spojuje vysílání a roli prostředníka dohromady. Snahou agenta je najít vhodného partnera pro komunikaci v rámci vlastní skupiny. Nalezení partnera lze provést následujícím způsobem: • vysíláním v rámci zvolené skupiny, • přijetím závazku – role prostředníka, • šířením požadavku v jiných, dostupných, sociálních skupinách. Prvotně agent hledá partnera uvnitř vlastní skupiny, pokud k nalezení adekvátního protějšku nedojde, poskytne mu prostředník možnost komunikace s agentem v jiné skupině. Skupiny kam prostředník požadavek na partnerství vysílá je omezen členstvím v této skupině. Interakční protokoly Agent zná vybraný komunikační jazyk, má k dispozici prostředky pro navázání komunikace. Následně je nutné stanovit "kostru" vlastní komunikace. Interakční protokoly definují pravidla komunikace mezi agenty. Obsahem je soubor možných dialogů, jak tento dialog započne, jak je ukončen, nutný výsledek z komunikace. Pokud se vyjednává o nabídce prostředků a služeb, jako komunikační prostředek je brán model dražby, tomu je podřízen i vlastní interakční protokol. Využívané typy interakčních protokolů: • kontraktní síť, • dražba, • hlasování, • argumentace. Stránka 75/122

Cvičebnice pro samostudium Umělá inteligence II Kontraktní síť Tento protokol je zaměřen na diskusi o vykonání služby. Ve své podobě je podobný vysílání. Požadavek na poptávanou službu je vyslán iniciátorem do skupiny, někteří agenti reagují s návrhem ceny. Iniciátor osloví vybrané agenty s návrhem ceny. Někteří agenti cenu akceptují, jiní odmítnou. Aukce Aukce je interaktivní přístup k určení ceny prostředků. Problém ceny a její úhrady se modeluje způsobem přidělení počáteční sumy prostředků agentovi (startovní částku, s kterou hospodaří), za úplatu využívá nebo poskytuje služby a prostředky. Specifikace protokolu aukcí vychází z principu aukcí, známých z reálného života: • Anglická aukce, • Holandská aukce, • Vickreyova aukce. V případě Anglické aukce se určí vyvolávací cena a účastníci dražby postupným přihazováním tuto cenu navyšují. Protokol popisuje dražbu tak, že na začátku jsou agenti informováni o zahájení dražby a jsou požádáni o spuštění přihazování. Dražba pokračuje až do okamžiku, kdy již nikdo nenavyšuje nabídku. Pokud se dražená cena nemění, tak se dražba ukončí, účastníci jsou informováni o jejím výsledku, provede se vyrozumění vítězi. V případě Holandské aukce je na počátku cena nadsazena, následně se snižuje a to tak dlouho, dokud se nenajde zájemce nebo dokud cena nedosáhne úrovně, pod kterou už dražitel nesmí jít (cena již není rentabilní). Tento typ dražby lze hodnotit jako méně výnosný. Taktéž Vickreyova aukce je založena na jednom kole nabídek. Agenti konkurenční agentské nabídky neznají. Aukci vyhrává agent s nejvyšší nabídkou. Zajímavostí této akce je, že vítěz aukci vyhrává za částku druhou nejvyšší. Hlasování Hlasování řeší problém rozhodování v rámci skupiny (určení strategie). Hlasování předpokládá, že existuje množina různých variant a cílem skupiny je vybrat jednu z nich. Hlasování je rozděleno do dvou etap: • shromažďování dostupných návrhů, • hlasování o návrzích. V rámci hlasování se rozhoduje o výběru strategie skupiny, kdypo přijetí dané strategie dostanou jednotliví agenti jednotlivé provozní plány, jež jsou v souladu s vytýčeným cílem Stránka 76/122

Cvičebnice pro samostudium Umělá inteligence II skupiny. V rámci hlasování je určen jeden agent (elektor), jež řídí volbu. Následně vyhlásí volbu, požádá o návrhy strategií, následně informuje o výsledku. Elektor rozhoduje v patové situaci rozhodování. Argumentace Argumentace je vzájemný dialog, kdy agenti diskutují o pravdivosti dané informace. Tuto (svoji) informaci podporují, popřípadě vyvracejí, postupnou argumentací. Spolu s argumentem je nutné specifikovat podmínky přijetí, odmítnutí informace. Argumentace končí v momentě přesvědčení druhé strany o své správné argumentaci a popření protiargumentace.

Stránka 77/122


Strojové učení v MAS Strojové učení je nedílnou součástí zlepšování schopností (funkcionality) agenta po dobu jeho života. Jedná se o důležitou partii umělé inteligence a po funkční stránce ovlivňuje také MAS a agenty i jednotlivě. Umožňuje "racionalizovat" chování agentů a ve výsledku dokáže zefektivnit a zlevnit jejich činnost. V první řadě je nutné definovat jaký smysl učení má, co při nasazení na daný systém přináší. Definice: Učení je schopnost agentů během své existence zdokonalovat své chování a to s ohledem na lepší adaptabilitu a efektivitu při řešení cíle. Podstatu zdokonalování můžeme chápat jako schopnost v průběhu času snižovat chybovost u úloh řešených s podobným zadáním. Další úroveň pohledu je schopnost, ve spojení s učením, vyřešit ten stejný úkol s využitím menšího počtu zdrojů, než při jeho prvním řešení. Vlastní proces učení je spojen se schopností a formou ukládání poznatků. Podoba, v jaké jsou znalosti uloženy, jednoznačně ovlivňuje i schopnost jejich opětovného využití (vůbec schopnost je efektivně využít). Samostatnou kapitolou je učení multiagentních systémů jako celku, kde se projevuje na proces učení vliv celého společenství.

Strojové učení – rozdělení Je velké množství kritérií, za pomoci kterých můžeme strojové učení dělit. Pokud vezmeme v potaz základní přístup, tj. možnost zpětné vazby z okolí při procesu učení (obdobně jako u neuronových sítí), tak rozeznáváme učení s učitelem a učení bez učitele. Dalším způsobem učení je učení na základě podobnosti. Kdy se v potaz bere analogie s již řešeným úkolem (již je známé řešení). Pokud agent nalézá společné rysy již řešených úloh a na základě této skutečnosti je schopen vytvořit si obecný popis řešení těchto úloh, tak se jedná o učení formou generalizace. Zajímavým přístupem je i učení formou „pokus – omyl“. Zde je však nutná zpětná vazba z okolí.

Popis strojového učení Bez vlivu na formu strojového učení je nutné zohlednit následující základní oblasti, které vlastní učení ovlivňují: Cíl učení – je popis stavu, do kterého se jedinec (společenství) má dostat, popřípadě dosáhnutí určité funkcionality (schopnosti) a to v pevně vymezeném čase. Pod cílem lze chápat algoritmus řešení zvoleného problému, schopnost rozeznat skupinu objektů na základě určitých vlastností, nebo schopnost průchodu daným terénem.

Stránka 78/122

Cvičebnice pro samostudium Umělá inteligence II Učící data (tréninková data) – jsou data obsahující příklady, analogie, ukázky. Pocházet mohou od učitele (učení s učitelem), jsou náhodně generována, získaná na základě měření, dřívější zkušenosti. Ukládání znalostí (poznatků) – je ústřední prvek strojového učení. Poznatky mohou být uloženy ve formě pravidel, sémantických sítí, rámců, scénářů, v podobě databáze s jednotlivými atributy. Ne vždy však je nutná explicitní forma uložení poznatků. Jako součást poznatků může být brána i neuronová síť, včetně její topologie a nastavení, řešící nějaký problém.

Popis učení deliberativního agenta Jak bylo již zmíněno, pod skupinou deliberativních agentů můžeme chápat skupinu entit, jež mají taktické chování vůči svému okolí. Na určité úrovni typ tohoto agenta dokáže modelovat autonomní chování lidí. Agent má symbolickou reprezentaci svého okolí a je schopen racionálního chování. Je obdarován schopností mentálních stavů a vytváří postoje vůči svému okolí. Jako vhodným způsobem učení se zde jeví „učení na základě symbolické reprezentace“. Je to obdoba učení malého dítěte. Znalosti jsou ve zvolené podobě ukládány nejlépe do asociativní sítě2. Formou příkladů shody s daným prvkem, nebo právě neshody s prvky v dané množině, probíhá vlastní učení. Jedná se o přístup učení s učitelem. Obdobně tomu tak je i u jiných zde použitelných metod a to konkrétně u rozhodovacích stromů, učení založeném na analogii, shlukování pojmů. Podstatou učení na základě symbolické reprezentace je začleňování objektů (jejich kategorizace). Určuje se tedy, za pomoci identifikace vlastností, zda daný prvek do skupiny patří, či nikoliv. Do učení se promítá princip specializace a generalizace. Generalizací se v této spojitostí myslí identifikace vlastností, jež mají objekty dané skupiny. Doplněno může být i ukázkou objektů, které do dané skupiny nepatří. Příklad Ve formě učení „začleňováním“ lze agentovi ukazovat např. různé podoby aut, kombi, sedan, mini, nákladní verze rozličných vozů (pozitivní příklad). Na této ukázce se učí zatřiďování a řízené selekci. Následně je možné ukázat objekty, které lze potkat na silnici a mezi auta nepatří (negativní příklad). Zde by se mohlo jednat o volský povoz, cyklista, člověk na inline. Na základě analogie zde dochází k učení ve formě učení s učitelem. Již na tomto příkladu je zřejmé, že k identifikaci do skupin dochází na základě identifikace základních prvků objektu a principu analogie. Na základě vizuálního ztvárnění je následně 2

Asociativní sítě vznikly na popud popisu anglické gramatiky, vychází z povahového ukládání v rámci lidské paměti.

Stránka 79/122

Cvičebnice pro samostudium Umělá inteligence II možné vytvořit popis ve formě sémantické sítě a to ať již pro pozitivní i negativní příklady – formy objektů. V součinnosti se sémantickou sítí popisující jednotlivé objekty vzniká adekvátní popis na úrovni predikátového zápisu.

Obrázek 21: Objekt - proces učení3

Na Obrázek 21 je jeden z potenciálních objektů určených k učení ve formě pozitivního příkladu. Pokud bude tento objekt podrobněji analyzován, lze vytvořit sémantickou síť následujícího tvaru (viz Obrázek 22). Jedná se o popis objektu, na jehož základě lze provádět analýzu dalších objektů a jejich zatřiďování.

Obrázek 22: Sémantická síť - osobní automobil 3

Zdroj obrázku: http://www.detskeomalovanky.cz/600/rodinne-auto/

Stránka 80/122

Cvičebnice pro samostudium Umělá inteligence II Asociativní síť je formou grafu, obsahující pojmenované vrcholy a přechody mezi nimi. Každý přechod, hrana, vyjadřuje vzájemný vztah příslušnosti. Asociativní sítě lze konstruovat na základě utvořených vět v predikátové logice prvního řádu, proto je zde možný vzájemný přechod mezi oběma formami vyjádření. Tomuto odpovídá následující zápis: JE(x, osobní auto) => JE(x, vozidlo) JE(x, vozidlo) => MÁ(x, motor) JE(x, spalovací motor) => JE(x, motor) JE(x, osobní auto) => MÁ(x, kola) JE(x, osobní auto) => MÁ(x, převodovka) JE(x, Škoda Octavia) => MÁ(x, čtyřdobý benzínový motor)

Po vlastním procesu učení nastupuje další úroveň uvědomění a to generalizace a specializace znalostí. Jedná se o analogii s lidským Popis učení reaktivního agenta Reaktivní agenti jsou nejjednodušší formou agentů. Jako samostatná entita vykonává svou interakci (činnost) s okolím na základě podnětů z okolí. Neobsahuje schopnost plánování ani podporu rozhodování. Bývá součástí kompetenčních modulů, tj. modulu, který reaguje na základě podnětu (aktivuje se) a následně vykoná určitou činnost. Může taktéž obsahovat vnitřní stavy, které v určité podobě mohou ovlivňovat jeho chování. Reaktivnost se v případě tohoto agenta projevuje adaptabilností na změny okolí s ohledem na splnění známého cíle. Učení posilováním Princip učení je založen na pozitivní motivaci, při učení ve formě pokusu a omylu. Pokud agent zdárně vybere vhodnou alternativu, tak je odměněn, v opačném případě penalizován. Mezi nejznámější přístupy z této oblasti patří: • • •

Q – učení Nenasytná strategie Lineární metoda odměny a trestu

Stránka 81/122


Shrnutí Oblast multiagentních systémů se v poslední době rapidně rozvíjí a to s ohledem na distribuovanou umělou inteligenci a její nasazení v rozsáhlých systémech. Propojení jednotlivých modulů systému je jen jednou z možných aplikací, simulace umělých světů a to i s ohledem na predikci chování jednou z dalších variací. V souladu s tímto je v soupisce zdrojů k této kapitole uvedeno velké množství informačních kanálů a to ať na výzkumné skupiny, tak i jednotlivé aplikace multiagentních systémů v lidském životě.

Kontrolní otázky 1. 2. 3. 4. 5. 6. 7.

Jak je definován inteligentní agent? Jaká je základní struktura agenta? Definuj základní rysy MAS (Multiagentních systémů). Definuj prostředí, v němž se agenti pohybují. Vysvětli princip vzájemné komunikace agentů. Jaké základní typy agentů se rozlišují? Vysvětli pojem strojové učení.

Inteligentní agenti - seznam doplňujících zdrojů Knížní zdroje informací Základní literatura •

•

•

RusselL, S., Norvig, P. Artificial Intelligence: A Modern Approach (3nd Edition). Prentice Hall, 2010. 1132 s. ISBN 0-13-207148-7. Kubík, A. Inteligentní agenty. 1. vyd. Brno: Computer Press, 2004. 280 s. ISBN 80251-0323-4. Mařík, V., Štěpánková, O., Lažanský, J. a kol. Umělá inteligence 3. 1. vyd. Praha: Academia, 2001. 328 s. ISBN 80-200-0472-6.

Doplňující literatura •

•

• • •

• •

Michael Wooldridge: An Introduction to MultiAgent Systems. Willey (2002) 1st ed. (nebo 2nd ed. v rozsahu 1st ed. Gerhard Weiss (editor): Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. David J. Sweatt: Mechanisms of memory, Elsevier Academic Press, 2003 Brenner, W., Zarnekow, R., Wittig, H.: Intelligent Software Agents. Springer, 1999 Ferber, J.: Multi-Agent Systems : An Introduction to Distributed Artificial Intelligence. Addison-Wesley Pub Co; 1999 Fisher,K., Fisher,M.D.: The Distributed Mind. AMACOM, 1997 Huhns,M.N., Singh,M.P.: Readings in Agents. Morgan Kaufmann 1997 Stránka 82/122

Cvičebnice pro samostudium Umělá inteligence II • •

• • •

•

•

• •

•

•

Jennings,N.R., Wooldridge,M.J.: Agent Technology. Springer-Verlag, 1998 Kirn, S., O?Hare,G. (eds.): Cooperative Knowledge Processing. Springer-Verlag, London, 1997 Murch,R., Johnson,T.: Intelligent Software Agents. Prentice-Hall, 1999 Nilsson,N.J.: Artificial Intelligence: A New Synthesis. Morgan Kaufmann, 1998 Russel,S., Norvig, P.: Artificial Intelligence ? A Modern Approach. Lawrence Erlbaum, Hillsdale, 1995 Tecuci, G.: Building Intelligent Agents: An Apprenticeship Multistrategy Learning Theory, Methodology, Tool and Case Studies. Academic Press, 1998 Turban, E., Aronson, J.E.: Decision Support Systems and Intelligent Systems. 5th ed., Prentice-Hall, 1998 Weiss, G. (Ed.): Multiagent Systems. The MIT Press, 1999 Inteligentní agenti pro detekci útoků v sítích – Martin Rehák, Diplomová práce http://km.fjfi.cvut.cz/vyzkum/temata-praci/205. Hodík J.: Multi-agentní systém jako model tržního hospodářství, Diplomová práce, ČVUT Praha, 2001. Zbořil F.: Plánování a komunikace v multiagentních systémech, Disertační práce, FIT VUT Brno, 2004.

Portály, asociace, konference •

•

•

•

•

•

Software Agents group – na této stránce se můžete seznámit s projekty nových agentů, kteří jsou určeni například pro určování topologie sítě. apod. http://www.media.mit.edu/research/groups/software-agents UMBC Agent Web – zde je shromážděna kolekce příspěvků, které zájemci poskytnou úvod a přehled klíčových konceptů a technologií, které se týkají informačních agentů a příbuzných témat. http://agents.umbc.edu/ The Agent Society – je nová mezinárodní nezisková organizace. Její členové pracují pro instituce a komerční firmy, které mají vedoucí postavení na poli technologií spojených s problematikou informačních agentů. http://www.acronymfinder.com/Agent-Society-(International-Society-onIntelligent-Agent-Technologies)-(AS).html Human - Computer Interaction and Intelligent Software Agents – tato stránka obsahuje stručný přehled problematiky informačních agentů, a nabídne spoustu odkazů na www stránky nebo konference apod. http://www.conferenceservice.com/conferences/human-computer-interaction.html Workshop on Multiagent Planning and Scheduling – The 15th International Conference on Automated Planning & Scheduling Monterey, California, USA, 2005. http://ai.jpl.nasa.gov/public/home/bclement/icaps05-workshop-map.html Multiagentní systémy – informační portál o problematice multiagentních systémů. http://multiagent.tym.cz/nicoolas/Home.php

Stránka 83/122

Cvičebnice pro samostudium Umělá inteligence II •

•

Agent technology center – Výzkumná skupina zaměřující se výzkumem na oblast multi-agentních systémů, technologií agentů. Důraz je zaměřen na průmyslové aplikace výzkumu. http://agents.felk.cvut.cz/ Výzkumná skupina inteligentních systémů – Skupina se věnuje teoretickému i aplikačnímu výzkumu inteligentních systémů v oblastech soft-computing, multiagentních systémů, biometrických systémů. http://www.fit.vutbr.cz/research/groups/intsys/.cs

Zajímavé články a zdroje •

•

•

•

Časopis o autonomních agentech a multiagentních systémech (Springer) http://www.springer.com/computer/ai/journal/10458 Rao & Georgeff: Modeling Rational Agents within a BDIArchitecture http://joshis.iprofil.cz/resources/education/06_RaoGeorgeff.pdf John-Jules Meyer: Modal Logics for Intelligent Agents http://joshis.iprofil.cz/resources/education/01_Handbook.modal.pdf Multi-agent Planning An introduction to planning and coordination http://www.st.ewi.tudelft.nl/~mathijs/publications/easss05.pdf

Stránka 84/122


Řešení problémů Úvod Řešení problémů zde – z hlediska inteligentních agentů – znamená, jak může agent dosáhnout cílů a jaké by měly být sekvence akcí, které mohou k daným cílům vést. Cíl a soubor prostředků pro dosažení cíle je řešený problém. Proces prozkoumávání prostředků (tj. čeho mohou prostředky, které jsou k dispozici, dosáhnout), se nazývá vyhledávání (či prohledávání, pátrání). Agent řešící problémy – typ agenta zaměřeného na cíle. Např. jednoduchý reflexní agent je příliš omezen (kvůli svým vlastnostem nemůže uvažovat směrem do budoucna). Agenti řešící problémy rozhodují o své činnosti tím, že se snaží najít sekvence akcí, které vedou k požadovaným stavům. Obecně se o inteligentních agentech předpokládá, že provádějí akce tak, aby prostředí procházelo posloupností stavů z hlediska maximalizace měřené výkonnosti (méně obecně: účinnosti agenta splnit vybraný cíl).

Řešení problémů Prvním krokem k řešení problému je formulace cíle, založená na okamžité situaci. Za cíl lze např. považovat soubor stavů světa – a to takové stavy, v nichž je cíl splněn. Na akce pak lze hledět jako na činnosti, které způsobí přechody mezi jednotlivými stavy světa, takže úkolem agenta je najít vhodné akce k dosažení cílového stavu. Obecně nelze uvažovat o akcích na určité úrovni, např. při požadavku vyjet z parkoviště není pro agenta vhodné usuzovat o akcích typu „natoč volant 6 stupňů doleva“ apod., protože generace řešení na takovéto úrovni detailů by mohla být ve většině případů nezvládnutelným problémem (člověk také neusuzuje tímto způsobem). Formulace problému je proces rozhodnutí, jaké akce a stavy uvažovat; tato formulace následuje po formulaci cíle. Dostatečná znalost: lze dojet z jednoho města do druhého, výběr z více cest,… Pokud není k dispozici dostatek informací a k cíli se lze dostat více možnostmi, pak agent nemůže udělat nic lepšího, než náhodně zvolit. Obecně platí, že pokud má agent několik možností neznámé hodnoty, pak k rozhodnutí o své činnosti potřebuje napřed prozkoumat různé možné posloupnosti akcí vedoucích do stavů o známé hodnotě, a pak prostě vybrat tu nejlepší sekvenci. Tento proces se nazývá vyhledávání. Algoritmus vyhledávání má jako vstup řešený problém a na výstupu poskytuje řešení ve formě sekvence akcí. Jakmile je řešení nalezeno, je doporučeno k provedení – tzv. výkonná fáze. Z toho plyne jedna z možností, jak navrhnout agenta na základě trojice pojmů „formuluj,

Stránka 85/122

Cvičebnice pro samostudium Umělá inteligence II vyhledej, proveď“. Po provedení zvolené sekvence akcí pak agent zvolí nový cíl a vše se pro aktuální situaci opakuje znovu. Jednoduchý agent řešící problém: function Simple-Problem-Solving-Agent (p) returns action inputs: p // vjem (percepce) static: s // sekvence akcí, na počátku prázdné state // popis stavu současného světa g // cíl, na počátku prázdný (žádný) problem // formulace problému state <-- Update-State(state, p) // aktualizace stavu if s is empty then g <-- Formulate-Goal(state) // formulace cíle problem <-- Formulate-Problem(state, g) // formulace problému s <-- Search(problem) // vyhledání problému action <-- Recommendation(s, state) // doporučená akce s <-- Remainder(s, state) return action

Formulace problémů Formulace problémů závisí na množství znalostí, které má agent k dispozici, aby bylo možno uvažovat jeho akce a stavy, v nichž se ocitne. To závisí na propojení agenta s prostředím pomocí jeho vjemů a akcí. Existují čtyři základní různé typy problémů: • • • •

problémy pro jeden stav, problémy pro více stavů, problémy nahodilé, a problémy k prozkoumání.

Kontrolní otázky 1. 2. 3.

Jakým způsobem lze definovat počáteční okrajové podmínky? Jak lze popsat řešení úlohy, sled následujících kroků? Jak lze rozlišit řešitelnost problému dle jeho výpočetní náročnosti?

Stránka 86/122


Učící se algoritmy Úvod Učící se algoritmy představují zcela odlišný přístup, než se kterým jsme pracovali v předchozích kapitolách. Zatím jsme umělou inteligenci vytvářeli tak, že jsme do programu vkládali známá pravidla, znalosti a strategie, které jsme se v průběhu našeho života sami naučili. Někteří lidé tento přístup dokonce odmítají uznávat jako umělou inteligenci, vzhledem k tomu, že programu „přesně nadiktujeme co má dělat“. Při vytváření učících se programů definujeme jen jakýsi obecný postup učení a vlastní řešení úlohy necháme na programu samotném. Tedy uděláme obecný „mozek“, který se sám naučí řešit úlohu, kterou chceme řešit a vyřeší ji za nás. Myšlenka je to jistě velmi lákavá, nicméně její realizace není tak jednoduchá jak by se mohlo zdát. Poměrně zásadní překážka je to, že nevíme, jak funguje proces lidského učení (něco víme, ale algoritmus učení neznáme). Proto i v této oblasti umělé inteligence existuje celá řada nesourodých přístupů a metod, tak jak postupně různí lidé zkoušeli realizovat myšlenku stroje, který se bude sám učit. Žádný z učících se algoritmů není nejlepší, a proto prostě představíme několik nejznámějších. Poznámka: V češtině se často používá výraz učící algoritmy, který se používá ve stejném významu jako „učící se algoritmy“ (chápeme to pak jako „algoritmy, které učí počítač“). Tady se budeme raději držet výrazu „učící se algoritmy“, protože jednoznačně odpovídá anglickému learning algorithms. Před vlastním použitím učících se algoritmů je nutné analyzovat vlastnosti řešeného problému a zvolit případné transformace tak, aby byl problém řešitelný pomocí učícího se algoritmu. Jedná se především o vlastní povahu proměnných, které v úloze vystupují. Je nutné odpovědět na následující otázky a následně zvolit vhodné dílčí algoritmy (topologie neuronové sítě, učící algoritmus neuronové sítě, kódování genetického algoritmu, a podobně). • • • • • • • •

Kolik je vstupních proměnných (jaká je dimenze úlohy)? Jsou všechny proměnné stejného typu a rozsahu? Jsou proměnné diskrétní nebo spojité? Jsou známy meze hodnot vstupních proměnných? Mohou být parametry optimalizovány nezávisle? Je kriteriální funkce multimodální (má více minim)? Je optimální hodnota časově nezávislá (statická úloha)? Objevuje se v úloze šum (liší se výsledky pro stejné vstupní hodnoty)?

Stránka 87/122


Evoluční algoritmy Úvod V přírodě biologičtí jedinci jedné populace mezi sebou soutěží o přežití a možnost reprodukce na základě toho, jak dobře jsou přizpůsobeni prostředí (adaptabilita). V průběhu mnoha generací se "struktura" dané populace vyvíjí na základě Darwinovy evoluční teorie o přirozeném výběru a přežívají jen ti nejsilnější. Ohodnocení síly jedince je prováděno termínem fitness (označení používané v anglosaských zemích). Evoluční algoritmy se snaží využít modelů evolučních procesů, aby tak nalezly řešení náročných a rozsáhlých úloh. Všechny tyto modely mají několik společných rysů: • • •

Pracují zároveň s celou skupinou (množinou) možných řešení zadaného problému místo hledání jednotlivého řešení Vygenerovaná řešení postupně vylepšují zařazováním nových řešení, získaných kombinací původních Kombinace řešení jsou následovány náhodnými změnami a vyřazováním nevýhodných řešení.

Stránka 88/122


Genetické algoritmy Úvod Genetické algoritmy jsou prohledávací algoritmy, optimalizační úlohy tedy řeší jako úlohu prohledávání stavového prostoru. Cílem je najít stav, který splňuje omezující podmínky optimalizace a současně poskytuje minimální hodnotu optimalizované funkce. Algoritmus tedy pracuje numericky bez ohledu na znalost přesného tvaru optimalizované funkce. Algoritmus vyžaduje pouze znalost výsledných hodnot v daném bodě stavového prostoru. Tyto hodnoty jsou pak předány kriteriální funkci, která stavy porovná a určí „lepší“ stav. Výhodou této numerické reprezentace úlohy je snížení nároků na matematický model úlohy. Při klasické optimalizaci je nutné dodržet množství podmínek, aby úloha byla vůbec řešitelná (například hladká spojitá funkce, hladká spojitá derivace, konvexní funkce, atd.). Při stavové reprezentaci úlohy zpravidla nejsou na matematický model úlohy tak přísné požadavky. Za určitých okolností je možné řešit i problémy, jejichž matematický model není funkce. Tento přístup je výhodný pro úlohy s nepolynomiální časovou složitostí, u nichž je však možné řešení ověřit v polynomiálním čase. Mechanismus genetického algoritmu je natolik výkonný, že umožňuje paralelně prohledávat ve více směrech stavové prostory úloh s desítkami až stovkami proměnných a nevyžaduje další pomocné údaje o problému (např. gradient nebo zakřivení funkce). Je zřejmé, že pokud jsou další údaje o problému známé, je vhodné je využít ke zrychlení výpočtu. Důležitou kladnou vlastností je také schopnost najít řešení ze zcela náhodného počátečního stavu. Genetické algoritmy je tedy možné využít i pro úlohy, které je sice teoreticky možné řešit klasickými metodami, není u nich však možné nalézt počáteční podmínky. Hlavní nevýhodou genetických algoritmů je jejich značná časová náročnost, především při vyhodnocování kriteriální funkce. Dále pak potíže s nalezením přesného řešení a s ukončením výpočtu, které jsou společné všem evolučním algoritmům.

Základní pojmy Genetický algoritmus pracuje s řadou pojmů z oblasti genetiky, které se používají k popisu datových a programových struktur algoritmu.

Jedinec Jedinec (hypotéza) h představuje jedno z možných řešení úlohy. Jedinec se skládá z genotypu a z fenotypu (těla jedince). Genotyp jsou data potřebná pro vytvoření fenotypu a fenotyp je vlastní řešení zadané úlohy. Genotyp zahrnuje veškerou genetickou informaci něčeho (buňky, živočicha, rostliny). U genetických algoritmů se obvykle redukuje pouze na jediný chromozom.

Stránka 89/122


Fitness Fitness F je hodnocení jedince, tedy každé hypotézy, která je v průběhu výpočtu vytvořena. Fitness je přiřazeno všem jedincům v populaci na konci nebo na začátku každého populačního cyklu pomocí kriteriální funkce. Fitness jedince vyjadřuje vzdálenost hypotézy od skutečného optimálního řešení a určuje tak, které řešení je lepší a které je horší. Kriteriální funkce tedy transformuje úlohu do stavového prostoru. Z hlediska genetického algoritmu tedy v podstatě není nutné znát matematický model optimalizovaného problému. Je nutné znát pouze kriteriální funkci, která umožní určit lepší či horší řešení, aby bylo možné jednotlivé hypotézy porovnat.

Gen Gen je jednotka genetické výbavy jedince. Její konkrétní význam závisí na řešeném problému a na použitém kódování. Může se jednat například o jeden bit, nebo třeba o celé číslo, znak a podobně.

Chromozom Chromozom je vektor genů. Chromozom je část genetické výbavy jedince, kterou je možné přenášet na potomky jedince.

Genotyp Genotyp je kompletní genetická výbava jedince. Soubor chromozomů jedince se označuje genom, v genetických algoritmech je zpravidla veškerá genetická výbava jedince obsažena v chromozomech, a genotyp se tedy shoduje s genomem. Většina genetických algoritmů navíc používá pouze jeden chromozom, pak tedy chromozom odpovídá genotypu.

Fenotyp Fenotyp je množina vnějších znaků a vlastností jedince. Z hlediska genetických algoritmů se tedy jedná o vlastní řešení úlohy. Fenotyp může tedy být naprosto libovolný, jeho tvar závisí pouze na řešené úloze. V operacích křížení a mutace genetického algoritmu se zpravidla fenotyp nevyužívá, uvažují se v nich pouze chromozomy.

Populace Populace p je množina jedinců v okamžiku t. Populace představuje soubor hypotéz, které jsou v daném okamžiku v genetickém algoritmu k dispozici. Z těchto hypotéz se v každé iteraci výpočtu vyberou nejvhodnější řešení, která jsou dále rozvíjena. Genetický algoritmus může využívat jednu populaci, častější je však užití více populací současně. Populace pak mohou být organizované do dalších struktur (stromů, sítí). Ve struktuře pak v pravidelných Stránka 90/122

Cvičebnice pro samostudium Umělá inteligence II intervalech dochází k výměně informací o dosaženém řešení, které mohou být dále využity v ostatních populacích. Strukturované populace mají větší diverzitu než populace nestrukturované, a přispívají tedy k omezení rizika předčasné konvergence.

Princip genetického algoritmu Základní myšlenkou genetických algoritmů je napodobování evolučního procesu. V genetickém algoritmu je vytvořeno několik počátečních hypotéz (jedinců), které se působením operátorů selekce, křížení a mutace vyvíjí tak, aby co nejlépe splňovaly požadavky kriteriální funkce (vnějšího prostředí). Kriteriální funkce není jedincům známá a současně s omezenou velikostí populace a s omezeným věkem jedince v populaci vytváří selekční tlak. Důležité je, že vývoj hypotéz je řízený a že k jeho řízení jsou využívány informace z celé populace, tedy všech hypotéz. Díky tomu jsou genetické algoritmy obecně efektivnější než metody založené na náhodném prohledávání (nejsou řízené) nebo paralelně spouštěné klasické metody s jedním hledacím bodem (nedochází k předávání informací mezi hledajícími body). Klíčovou součástí genetického algoritmu je kriteriální funkce, která všem jedincům (řešením) přiřazuje hodnocení (fitness), a představuje tedy zdroj informací pro ostatní operace genetického algoritmu.

Stránka 91/122


Obrázek 23: Princip genetického algoritmu.

Na obrázku je příklad vývojového diagramu obecného genetického algoritmu. Existuje celá řada modifikací obecného genetického algoritmu, které nemusí obsahovat všechny operace, nebo naopak mohou obsahovat nové operace, specifické pro daný problém. Základem všech genetických algoritmů je populační cyklus, který se opakuje, dokud není dosažena požadovaná přesnost řešení (fitness). V průběhu cyklu jsou na populaci aplikovány operátory selekce, křížení a mutace a následně se vytvoří nová populace. Na počátku nebo na konci populačního cyklu se všichni jedinci v populaci vyhodnotí a znovu se ověřuje přesnost dosažených řešení. Poznámka: Existují dva základní typy genetických algoritmů – generational a steady-state. V genetickém algoritmu typu se v každém cyklu vytváří populace zcela znovu. Někdy se zavádí operátor kopírování, v jiných variantách se do nové populace jedinci dostanou pouze aplikací operátorů křížení nebo mutace. V tomto typu genetických algoritmů se nepracuje s věkem jedince. U algoritmů type steady-state dochází v každém cyklu pouze k výměně části populace. V každém cyklu se tedy některým selekčním algoritmem vygeneruje určitý počet potomků, kteří mohou nahradit nejhorší jedince v populaci. V algoritmech typu steady-state se pracuje s věkem jedince a kromě odstraňování na základě fitness je možné odstraňovat Stránka 92/122

Cvičebnice pro samostudium Umělá inteligence II jedince z populace i na základě věku. Z praktického pohledu jsou oba typy v téměř rovnocenné a volba jednoho či druhého typu je spíš otázkou osobních preferencí.

Operace genetického algoritmu Následující podkapitoly popisují hlavní principy základních operací genetického algoritmu. Pro ilustraci uvažujeme jednoduchý příklad nalezení minima (optimalizace) funkce jedné proměnné y = g (x ). Průběh funkce je ukázán na obrázku, samozřejmě pokud známe grafické nebo matematické vyjádření průběhu funkce, tak nepotřebujeme genetický algoritmus na její optimalizaci. Reálně však optimalizujeme funkce více proměnných, které není možné jednoduše zobrazit anebo funkce u kterých neznáme jejich matematické vyjádření. Operace genetického algoritmu jsou definovány velice obecně, a proto jsou obvykle mezi různými implementacemi genetických algoritmů výrazné rozdíly. Často se také využívají modifikace specifické pro doménu konkrétního problému, někdy i pro konkrétní úlohu. Cílem následujících podkapitol je tedy pouze ilustrovat principy a hlavní využití jednotlivých operací.

Obrázek 24: Grafický průběh funkce.

Stránka 93/122


Kódování Způsob kódování řešení do chromozomu je závislý na konkrétním řešeném problému, v závislosti na použitém kódování se dále mohou lišit implementace operace křížení a mutace. V případě optimalizace funkce jedné proměnné stačí zakódovat pouze jednu informaci polohu jedince na ose x. Chromozom může být tvořen například jediným celočíselným genem nebo například vektorem jednobitových genů. Kódování definuje způsob uložení konkrétního řešení do chromozomu. Kódování je závislé na konkrétním řešeném problému, v závislosti na použitém kódování se dále mohou lišit implementace operace křížení a mutace. V případě optimalizace funkce jedné proměnné stačí zakódovat pouze jednu informaci – polohu jedince na ose x. Chromozom může být tvořen například jediným celočíselným genem Binární kódování Binární kódování je nejběžněji používaným kódováním, jeho výhodou je především jednoduchost a přirozená reprezentace na počítači. Celočíselné kódování je vhodnější pro úlohy, které jsou přímo definované na množině celých čísel. Prohledávaný prostor [] Reálné kódování Kódování pomocí reálných čísel je vhodné použít při řešení úloh, které optimalizují proměnné v oboru reálných čísel, zejména proto, že nedochází k problémům se ztrátou přesnosti. Stejně jako v předchozím případě je i zde nutné stanovit horní a dolní mez hodnot, kterých může hodnota genu nabývat a minimální krok (přesnost). Prohledávaný prostor [] kde [] a [] je dolní, respektive horní mez prohledávaného intervalu, s je nejmenší krok, se kterým je možné se v intervalu pohybovat a k je délka chromozomu. Tento způsob kódování se používá zejména pro genetické algoritmy typu generational, tedy algoritmy založené spíše na aplikaci mutačního operátoru, případně pro metody na pomezí genetických algoritmů a evolučních strategií. Příkladem takového algoritmu je diferenciální evoluce. Způsob kódování je tedy silně závislý na řešené úloze. Měl by být zvolen tak, aby bylo zkreslení v kódování minimální (zůstala zachována blízkost fenotypů). Pokud není, dochází k tomu, že se v interním prohledávaném prostoru algoritmu vytvářejí lokální minima, která v prohledávaném prostoru nejsou. Tím se zbytečně zvyšuje složitost a časová náročnost. Je také možné používat i value encoding – kódování hodnotou, tedy ukládat do chromozomu přímo hodnoty fenotypu bez kódování. Výhoda tohoto způsobu je v tom, že interní prohledávaný prostor je totožný s prostorem řešení, a nedochází tedy k vytváření více lokálních extrémů, než je v původní úloze. V závislosti na řešeném problému je možné za Stránka 94/122

Cvičebnice pro samostudium Umělá inteligence II kódování hodnotou považovat i výše uvedené způsoby. Pro jiné typy proměnných však způsob reprezentace fenotypu obvykle vyžaduje velmi specifické operátory křížení a mutace.

Inicializace Velkou výhodou genetických algoritmů je nenáročnost na počáteční podmínky, genetické algoritmy mají unikátní schopnost najít řešení úlohy, i pokud jsou počáteční hypotézy zcela náhodné. Nejčastěji se tedy používá vytvoření počáteční populace s rovnoměrným rozdělením v celém definičním oboru kriteriální funkce tak, aby byl celý prostor řešení rovnoměrně pokrytý hledajícími body. Rovnoměrné rozdělení je nejspolehlivější v tom smyslu, že dává každému spuštění algoritmu stejnou šanci uspět. Pokud je například možné předpokládat interval, ve kterém se nachází řešení, je vhodné jej použít pro inicializaci populace s normálním rozdělením. Rychlost algoritmu se tak zvýší, ale současně je stále možné nalézt řešení i mimo původní předpokládanou oblast. Obrázek ukazuje příklad počáteční populace s pěti náhodně vygenerovanými jedinci (h1 až h5). Ve skutečnosti se zpravidla využívají populace větší, se stovkami až tisíci jedinců. Více jedinců v populaci zpravidla vede k rychlejší konvergenci a současně snižuje riziko uváznutí výpočtu v lokálním extrému. Protože je však časová složitost ostatních operátorů genetického algoritmu funkcí velikosti populace, je nutné zvolit vhodnou kompromisní velikost, při které je vyvážená doba výpočtu jednoho populačního cyklu a celková doba výpočtu.

Výpočet fitness Pro výpočet fitness je nutné definovat kriteriální (účelovou) funkci. Protože genetický algoritmus hledá ve stavovém prostoru bod s maximální hodnotou fitness funkce, je její volba a správné nastavení klíčové. Měla by být konstruována tak, aby zahrnovala všechna požadovaná kritéria, podle nichž se stanoví kvalita jedince. Dejme tomu, že bychom chtěli genetickým algoritmem hrát piškvorky. V tom případě je kriteriální funkce zdánlivě triviální – výherní stav je 1, nevýherní stav je 0 – algoritmus se snaží dostat do nejlepšího stavu. Problém je v tom, že aby se genetický algoritmus něco naučil, nestačí pouze cukr a bič, ale je potřeba definovat i nějaké mezistavy „toto je dobrý tah“, „toto je horší tah“. Vracíme se tedy opět k začátku, k prohledávání stavového prostoru a heuristickým funkcím. Kriteriální funkce genetického algoritmu je obyčejně právě taková nějaká funkce.

Selekce Úkolem operace selekce je vybrat z populace množinu jedinců, kteří budou přeneseni do nové populace, tedy množinu řešení, která budou dále rozvíjena. Selekce je hlavní nástroj genetického algoritmu, který zajišťuje konvergenci algoritmu. Selekční algoritmus musí jednak vybírat jedince s největší hodnotou fitness a současně musí zachovávat dostatečnou různorodost populace. Selekční tlak musí být dobře vyvážen, na jedné straně je požadována Stránka 95/122

Cvičebnice pro samostudium Umělá inteligence II co nejrychlejší konvergence, na straně druhé je snaha vyhnout se předčasné konvergenci. Předčasná konvergence (uváznutí výpočtu v lokálním extrému) může nastat, pokud je selekční tlak příliš vysoký, tedy pokud nadějné řešení zahltí celou populaci a ztratí se genetická informace z ostatních jedinců. Pro operaci selekce byla vyvinuta celá řada metod a jejich modifikací, některé metody se snaží o co nejvěrnější simulaci přírodní selekce, jiné se zaměřují spíše na optimální konvergenci a časovou složitost. Selekční tlak je možné ovlivnit volbou metody a nastavením jejích parametrů a také mírou mutace, která působí proti selekčnímu tlaku tím, že zvyšuje různorodost populace. Selekční tlak posouvá všechny body k nejlepšímu řešení a snižuje tak různorodost populace. Pokud však není populace dostatečně různorodá, tedy pokud není celý definiční obor řešeného modelu rovnoměrně pokrytý, hrozí předčasná konvergence a uváznutí v lokálním extrému. Kromě jedno kriteriálních selekčních metod, které vybírají jedince pouze podle hodnoty fitness, existují také vícekriteriální metody, které zohledňují další parametry (např. stáří jedince, složitost,…). Jinou možností je započítat tyto parametry přímo do fitness a následně použít standardní jedno kriteriální selekci.

Turnajová selekce Metoda tournament selection (turnajová selekce) náhodně vybere z původní populace o n jedincích množinu jedinců Ptmp o velikosti t. Vybraná množina představuje skupinu jedinců, kteří se utkají v turnaji. Do nové populace P t + 1 je přenesen vítěz, tedy nejlepší jedinec z vybrané množiny, nebo m nejlepších jedinců. Turnajová selekce umožňuje plynulé nastavení selekčního tlaku vhodnou volbou parametrů t a m. Největší selekční tlak je v případě t = n, což odpovídá výběru pouze nejlepších jedinců z populace. Naopak nejmenší selekční tlak vzniká při t = 1, což odpovídá náhodnému výběru. Tato metoda dosahuje dobrých výsledků, přitom má však nízkou časovou náročnost O ( n ) a nevyžaduje seřazení populace.

Křížení Operace křížení (cross-over) je charakteristickým nástrojem genetických algoritmů pro vytváření nových řešení, tedy pro zajištění konvergence. Křížení je silně závislé na použité metodě kódování, protože pracuje přímo s chromozomy a geny. Pro křížení jsou náhodně vybráni dva jedinci jako rodiče, kombinací jejich genů vznikne potomek. V ideálním případě by fitness potomka mělo být vyšší než fitness každého z jeho rodičů, v tom případě genetický algoritmus postupuje ve směru gradientu kriteriální funkce. Je však přípustný i stav, kdy potomek je horší než některý z rodičů, pak genetický algoritmus postupuje proti směru gradientu kriteriální funkce, a může tedy překonávat lokální extrémy účelové funkce. Křížení je současně hlavní způsob výměny informací mezi jedinci, tedy mezi jednotlivými hledajícími body optimalizace.

Stránka 96/122

Cvičebnice pro samostudium Umělá inteligence II Na příkladu optimalizace funkce jedné proměnné je možné jednoduché křížení definovat například jako střed intervalu vymezeného oběma rodiči h new = h r 1 + h r 2 2. Vznikne tak nový jedinec h6, jehož hodnota se blíží optimu víc než hodnota kteréhokoliv z jeho rodičů. Přesto je z obrázku patrné, že pouze pomocí křížení by minimum nebylo nalezeno. Tento problém je možné řešit buď použitím sofistikovanějšího operátoru křížení, nebo zavedením mutace, nebo kompenzovat použitím více hledajících bodů, tedy větší populace.

Obrázek 25: Genetický algoritmus, generování jedinců v populaci.

Mutace Operace mutace je obvykle zcela náhodná změna několika náhodně vybraných jedinců. Její účinek je obvykle destruktivní. Smyslem mutace je vytváření zcela nových jedinců, tedy zvyšování různorodosti populace a prevence uváznutí v lokálním extrému kriteriální funkce. Pravděpodobnost mutace se volí obvykle nízká p m < 1 %. Při neúměrně vysoké mutaci dochází k narušování slibných řešení dříve, než mají čas se vyvinout, a algoritmus přestává konvergovat. Pokud je pravděpodobnost příliš nízká, hrozí naopak nebezpečí, že populace bude zahlcena jedním typem řešení, které bude pouze lokální optimum. Z praktického pohledu je problematické, že tyto dva stavy jsou obtížně rozeznatelné, protože se projevují podobně.

Stránka 97/122

Cvičebnice pro samostudium Umělá inteligence II Na obrázku má jedinec h7 vzniklý mutací horší fitness než jedinec, ze kterého vznikl (h4), v daném okamžiku je však jediným řešením, které má šanci dostat se prostřednictvím dříve definovaného selekčního operátoru do globálního extrému funkce. Jedinec h6 vzniklý křížením je dočasně nejlepší řešení, které však po několika iteracích uvázne. Operaci mutace zde můžeme definovat například takto: a mut = a orig + r, kde r je náhodně zvolené číslo.

Shrnutí V této kapitole jsme popsali základní pojmy z oblasti genetických algoritmů a princip této metody umělé inteligence. Na modelové úloze optimalizace funkce jedné proměnné jsme také předvedli, jak jednotlivé operace genetického algoritmu mohou fungovat. Možná se to zdá neuvěřitelné, že taková věc funguje a že to určitě používá nějakou temnou magii. Funguje to i bez magie, více o tom najdete v části příklady.

Stránka 98/122


Diferenciální evoluce Úvod Diferenciální evoluce je varianta genetického algoritmu, navržená pro optimalizaci parametrů v oboru reálných čísel. Jedná se o genetický algoritmus typu generational, který je však pro svou odlišnost od genetických algoritmů často zařazován také mezi evoluční strategie nebo přímo mezi evoluční algoritmy. Výhodou diferenciální evoluce je jednoduchost implementace, rychlost a efektivita. Mezi nevýhody patří zejména vazba na reálná čísla, která neumožňuje řešit jiné úlohy.

Aplikace evolučních algoritmů Model výnosu Pomocí dvoufázové gramatické evoluce byla řešena úloha hledání regresního modelu pro výnos cibule Brown Imperial Spanish na dvou lokalitách Austrálie. Vstupní data představuje množina dvojic Tabulka obsahuje zadaná vstupní data. Podmínka zastavení algoritmu byla stanovena jako N < 10, kde N je počet cyklů hlavní populace gramatické evoluce. Hodnota RSS pro referenční model je 5099,3, stanovená kritéria tedy požadují, aby byl nalezen model přesnější. Omezení na 10 cyklů je sice poměrně přísné, ale jedná se o účinný způsob jak eliminovat přeučení. Po zkušebních spuštěních se navíc ukázalo, že algoritmus i při tomto omezení konverguje ve 100% spuštění. Referenční model je dán vztahem: [] kde [] jsou empirické parametry s odhady [] a []. (Meloun, 1996) uvádí tři další srovnatelné modely, z nichž některé mají dva a některé tři parametry. Byla proto použita gramatika, která umožňuje vytvoření modelu až se třemi parametry.

Stránka 99/122


Obrázek 26: Srovnání použitých modelů na problém "výnosu cibule". Tabulka 4: Vstupní hodnoty pro lokalitu Uraidla

1.

2.

3.

4.

5.

6.

7.

8.

9.

x 22,30 25,86 29,09 29,47 31,68 31,68 32,00 32,32 32,32 y 148,57 125,30 150,69 147,42 117,10 116,64 129,66 131,54 151,50 10.

11

12.

13.

14.

15.

16.

17.

18.

x 34,91 35,23 38,47 39,44 41,05 41,70 44,28 45,90 46,55 y 121,80 125,67 117,78 101,50 113,22 136,43 117,54 87,20 107,41 19.

20.

21

22

23.

24.

25.

26.

27.

x 48,16 48,49 48,81 49,78 50,43 51,72 61,42 65,29 67,23 y 129,68 104,63 114,15 99,80 111,65 98,00 87,80 75,400 87,00 . 28.

29.

30.

31.

32.

33.

34.

35.

36.

x 71,44 73,05 86,63 96,00 98,91 103,44 105,05 111,19 113,78 y 90,10 81,00 65,30 58,40 65,60 67,10 54,00 60,90 53,40 37.

38.

39.

40.

41.

42.

x 119,92 120,89 126,71 138,99 146,7 160,97 y 61,60 26,30 61,20 41,60 45,2

46,4

Stránka 100/122

Cvičebnice pro samostudium Umělá inteligence II Ze srovnání (viz obrázek) referenčního modelu a vybraného vygenerovaného modelu je patrné, že gramatická diferenciální evoluce je schopná generovat model přesnější. Tabulka 4 obsahuje výsledky deseti spuštění, nejlepšího výsledku, co se týče kriteriální funkce, bylo dosaženo ve spuštění číslo 8. Je však patrné, že se jedná o stav přeučení, funkce je velice složitá a ztratilo se zobecnění. Zabránit tomuto jevu je možné buď testováním na více datových souborech současně, nebo zavedením dalšího kritéria sledujícího složitost funkce.

Stránka 101/122


Neuronové sítě Úvod Neuronové sítě jsou nejčastěji připodobňovány k lidským neuronům a z nich vzniklé zjednodušené neuronové soustavě. Existuje mnoho definic neuronových sítí a každá z nich poukazuje na jinou stránku neuronových sítí. To v čem se shodují lze shrnout do následujícího popisu. Neuronovou síť lze chápat jako distribuovaný, paralelní systém zpracovávající informace, který je složený ze vzájemně spojených jednotek. Tyto jednotky mají vlastní paměť, jsou schopny provádět operace s informacemi a říkáme jim neurony. Definice: Neuronová síť je síť mnoha jednoduchých procesorů, navzájem bohatě propojených. Graf propojení se často nazývá topologie sítě. Procesory nazýváme neurony proto, že velice zjednodušeně modelují skutečné neurony v centrální nerovové soustavě a jejich formální návrh je inspirován vlastnostmi mozku a periferního nervstva. Definice (1) prof. Hořejše je absolutně výstižná a formálně shrnuje předchozí části. Většina materiálů v tomto místě uvádí obrázek nejjednoduššího modelu neuronových sítí, perceptronu a odkazuje se na další srovnání s lidskou nervovou soustavou. Právě z tohoto důvodu si můžeme dovolit zaměřit se nejdříve na základní pojmy a následně uvést k čemu to tedy je dobré. Jaké typy neuronových sítí znáte? Neuronové sítě lze dělit z mnoha hledisek. Zde si je rozdělíme právě podle jednotlivých aplikací. Zjednodušeně lze rozdělit aplikace do tří typů úloh – aproximace, predikce a klasifikace. Nelze však zapomenout ani na kompresi dat, řízení, optimalizační úlohy nebo rozpoznávání obrazu. Již z výše zmíněných oblastí lze dedukovat princip fungování neuronových sítí. Naučenou síť si můžeme představit jako black box (černou skříňku), které předložíme vstupní data, a síť provede výpočet výstupních hodnot. Vrátí nám tedy výstupní hodnoty, u kterých však neznáme na základě, jakého vztahu vznikly. Postupným odkrýváním se dostáváme k topologii sítě, učení sítě a jednotlivým konfiguracím sítě. Ve výsledku jsme tyto „vlastnosti“ schopni nastavit, ale opět nejsme schopni přesně formalizovat vztah na základě, kterého dochází k přepočtu vstupů na výstupy. Naučená neuronová síť je velmi výkonný pracovní nástroj. Problém je při zobecňování, kdy neuronové sítě jsou určeny spíše na konkrétní úlohy. Ty pak řeší podle přesnosti na výstupu, kterou si sami určíme. Při použití na jiný typ úlohy nám síť bude ve zcela výjimečných případech vracet kvalitní výstupy.

Stránka 102/122


Aplikace Prioritní řízení síťového prvku Model síťového přepínače se čtyřmi porty (viz Obrázek 27) byl vytvořen pomocí základních bloků, Stateflow Toolboxu, Neural Network Toolboxu programu Simulink a Packet generátoru, který simuluje vstupní data. Data jsou generována náhodně s ohledem na využitelné vlastnosti paketu.

Obrázek 27: Prioritní řízení síťového prvku.

Každý vstup síťového přepínače má vlastní paměť typu FIFO (viz Obrázek 28) pro ukládání vstupních dat. Z paměti jsou pak přečteny vektory priorit (viz Obrázek 31), které jsou vstupem pro neuronovou síť. Po zpracování neuronovou sítí (viz Obrázek 34) jsou pakety přesměrovány pomocí konfiguračního vektoru (viz Obrázek 35) na určitý výstup přepínače. Průchod dat ze všech vstupů na všechny výstupy je tak řešen s optimálním využitím priorit.

Stránka 103/122


Obrázek 28: Paměť typu FIFO.

Paměť typu FIFO (viz Obrázek 28) představuje speciální datovou frontu, z níž lze číst potřebná data (priority paketů) prvního paketu ve frontě. Subsystém FIFO obsahuje 4 vstupní a 3 výstupní proměnné. Generátor paketů (viz Obrázek 29) je jedním ze subsystémů modelu. Počet generátorů je dán počtem portů přepínače (v našem případě tedy 4). Nemá žádný vstup a disponuje pouze jedním výstupem. Plní funkci odesílatele dat v reálné struktuře datové sítě.

Obrázek 29: Generátor paketů.

Jedním z klíčových prvků vytvořeného modelu je subsystém Data Manager (viz Obrázek 30), který pracuje se čtyřmi vstupy (diskrétní spouštění funkce podle taktu simulace, vstupní data, připravenost konfiguračního vektoru, vlastní konfigurační vektor z bloku Hopfield) a třemi výstupy (výstupní data vybraného paketu, hodnoty výstupního vektoru priorit, připravenost vektoru priorit). Počet těchto subsystémů je dán počtem portů přepínače (v našem případě tedy 4).

Stránka 104/122


Obrázek 30: Schéma přepínače.

Detailní model vytvořeného bloku Main Data Manager je na Obrázek 31, z něhož jsou zřejmé jeho dvě hlavní funkce. První funkce spočívá v přijetí příchozího paketu a jeho umístění do jedné ze čtyř pamětí typu FIFO podle požadovaného výstupu. Druhou klíčovou funkcí bloku Main Data Manager je výběr požadovaného paketu z některé fronty FIFO podle konfiguračního vektoru získaného z bloku Hopfield (viz Obrázek 34).

Obrázek 31: Model bloku bloku Main Data Manageru.

Vlastní řízení činnosti přepínače je řešeno pomocí Stateflow diagramu (Stateflow Chart), který je součástí Stateflow Toolboxu prostředí MATLAB – Simulink. Tabulka Chart bloku Paket generátor obsahuje 7 stavů (viz Obrázek 32), které generují signál příchozího paketu. Stránka 105/122

Cvičebnice pro samostudium Umělá inteligence II Každý ze stavů tabulky Chart bloku Paket generátor se provede na začátku nové události, která má označení Tick. To znamená, že při příchodu signálu do tabulky dojde k přechodu na následující stav tabulky. Tímto způsobem je zajištěna posloupnost a časování dat.

Obrázek 32: Tabulka Chart bloku Paket generátoru.

Stránka 106/122

Cvičebnice pro samostudium Umělá inteligence II V modelu přepínače byl vytvořen blok Standard Computing (viz Obrázek 33) pro standardní sériový výpočet konfiguračního vektoru z vektoru priorit, který provádí optimální výběr paketů z matice vzorů.

Obrázek 33: Blok Standard Computing.

Stejná úloha (optimální výběr paketů podle priorit) je řešena pomocí Hopfieldovy neuronové sítě (blok Hopfield – viz Obrázek 34), kde vstupní data představují priority čekajících paketů (prioritní vektor). Po naučení neuronové sítě probíhá výpočet rekurentně a je ukončen po ustálení výstupních dat (Product Ready – viz Obrázek 35).

Obrázek 34: Blok Hopfieldovy neuronové sítě.

Počáteční data pro neuronovou síť jsou interpretována adaptovaným vektorem priorit, z nichž je rekurentně počítán konfigurační vektor. Postupný výpočet konfiguračního vektoru v závislosti na čase je na Obrázek 35. Každý prvek vektoru je zobrazen jedinou křivkou. Možnost použití konfiguračního vektoru určuje počátek stability výpočtu (Product Ready).

Stránka 107/122


Obrázek 35: Sled prováděných paketů.

Výpočet optimálního konfiguračního vektoru lze řešit pomocí bloku Standard Computing i pomocí bloku Hopfield s možností porovnání rychlosti řešení.Pomocí simulačních experimentů v prostředí Simulink byla zjištěna rychlost výpočtu standardní metodou (Standard Computing) a Hopfieldovou neuronovou sítí (viz Chyba! Nenalezen zdroj odkazů.). Tabulka 5: Hodnoty modelu.

Č. výpočtu 1 2 3 4 5 6 7 8 9

tNNN

382

tHop 17 35 18 12 18 18 22 13 31

α 22,47059 10,91429 21,22222 31,83333 21,22222 21,22222 17,36364 29,38462 12,32258

Průměrné α

20,88397

Parametr tHop udává simulační čas výpočtu Hopfieldovou sítí, parametr tNNN simulační čas výpočtu blokem Standard Computing a parametr ? představuje poměr obou časů, určuje tedy kolikrát je výpočet Hopfieldovou neuronovou sítí rychlejší než metodou Standard Computing. Stránka 108/122

Cvičebnice pro samostudium Umělá inteligence II Simulační čas výpočtu standardní metodou (Standard Computing) je vždy stejný, zatímco simulační čas výpočtu Hopfieldovou neuronovou sítí se mění v závislosti na vstupních hodnotách vektoru priorit, a proto byla pro porovnání rychlostí obou výpočtů použita průměrná hodnota simulačního času tHop a určena průměrná hodnota parametru α (viz Chyba! Nenalezen zdroj odkazů.). Simulační experimenty s vytvořeným modelem v prostředí MATLAB – Simulink prokázaly, že síťový přepínač s implementovanou neuronovou sítí pro prioritní řízení je asi 20 x rychlejší (průměrná hodnota parametru α z Chyba! Nenalezen zdroj odkazů.je 20.88397) než při standardním výpočtu. Model síťového prvku pro optimalizaci prioritního řízení byl navržen s ohledem na možnost snadné implementace dalších optimalizačních prvků (zejména jiných typů neuronových sítí a učících algoritmů) s možností porovnání rychlosti řešení se standardním výpočtem (jako ve výše uvedeném případě). Navržený model lze rovněž využít při technické konstrukci reálného přepínače. Alternativně bude možné použít implementované neuronové sítě pro optimalizaci prioritního řízení programovatelného logického pole FPGA, Xilinx Virtex se čtyřmi vstupy.

Stránka 109/122


Shrnutí V první části této opory jsme popsali, jak se vytváří inteligentní systémy přístupem "zdola nahoru". Ve zkratce to reprezentuje to, že do programu vkládáme naši vlastní inteligenci ve formě znalostí, postupů a pravidel. Výsledný program je obyčejně deterministický. To znamená, že na jeden vstup poskytuje vždy stejný výstup. Lidově řečeno: "chová se pořád stejně". Takto vytvořená umělá inteligence nás (jak tvůrce) v zásadě nemůže ničím překvapit, protože obsahuje přesně to, co jsme do ní vložili. Může však překvapit uživatele a to jak svou "chytrostí", tak "tupostí". Současně to také znamená, že se v programu nemohou objevit žádné jiné chyby, než které jsme udělali při jeho vytváření. Tedy, program dělá v zásadě (ne úplně, protože v každém programu jsou chyby) to správné. V této kapitole jsme popsali druhý přístup k umělé inteligenci, který spočívá ve vytváření systémů, které se samy něco naučí. Programátor vytvoří jen jakousi kostru a nechá systém, aby sám určil správná pravidla, postupy a znalosti ze zadaných příkladů. Výsledný program je obyčejně (během učení) nedeterministický. Tedy při zadání jednoho vstupu můžeme postupně získávat různé výstupy. Potíž je v tom, že jako tvůrci programu nemáme žádnou záruku, že se program naučí to správné řešení. To je bohužel neoddělitelná součást procesu učení. Příklad z reality - když jde student na zkoušku a naučí se nazpaměť několik definic a zkoušku udělá je to problém, protože se nenaučil to, co měl (pochopit látku). Kontrolní mechanismus (zkoušející) selhal v tom, že neodhalil, že to student neumí. Problém nastane v případě, že má student to, co se naučil někde aplikovat, teprve pak se přijde na to, že se vlastně naučil něco jiného. Například použijeme učící se spamový filtr, který se bude na základě emailů zařazených do složky Spam, učit rozpoznávat nevyžádané zprávy. Tento filtr se může velmi snadno naučit, že každá zpráva obsahující slova viagra, lottery a penis je nevyžádaná. Stejně tak se ale může naučit, že každá zpráva psaná anglicky je nevyžádaná. Pokud uživatel bude dostávat do 5% anglicky psaných zpráv, budou se oba filtry chovat skoro stejně. Občas přijde do spamu něco co tam přijít nemá, nicméně uživatel bude v zásadě spokojený. Jakmile se však (i dočasně) zvýší množství anglických zpráv na 50%, bude druhý spam filtr naučený na angličtinu naprosto k ničemu. První spam filtr naučený jen na některá slova bude mít pořád stejnou chybovost. Toto je poměrně charakteristický problém učících se systémů. Chybu, která při učení nastala, neodhalíme při učení, ale až v okamžiku kdy nastane nějaká nová, neočekávaná situace se kterou jsme při kontrole učení nepočítali. Z toho důvodu se pořád dává přednost programům a strojům, které se neučí, ale jsou nějak fixně neprogramovány. Tedy – problém není udělat učící se stroj, problém je udělat spolehlivý učící se stroj. A to je také důvod proč je „onlinovka“ pořád nesrovnatelně lepší než umělá inteligence. Učení v počítačových hrách nejde použít, anebo musí být velmi omezené. Zaprvé – hra by musela být již naučená dopředu (jinak by si hráč prvních 600 hodin moc nezahrál). A největším problémem pak je to, že hráč může během hry velmi výrazně změnit strategii, v tu chvíli nikdo není schopen zaručit, že se naučený algoritmus bude chovat racionálně. V konečné fázi si tedy výrobce netroufne Stránka 110/122

Cvičebnice pro samostudium Umělá inteligence II prodávat učící se hry, protože při prvním selhání procesu učení by mu to zákazníci hodili na hlavu.

Kontrolní otázky 1. 2. 3. 4. 5. 6. 7.

Jak je definován pojem učící algoritmus? Jak lze definovat evoluční algoritmy? Co chápeme pod pojmem umělé neuronové sítě? Vysvětlete princip genetického algoritmu. Jaké základní typy umělých neuronových sítí rozlišujeme? Jaké aplikační využití mají umělé neuronové sítě? Jaké aplikační využití mají genetické algoritmy?

Stránka 111/122


Závěr V tomto textu jsme se pokusili snad alespoň trochu stravitelně představit umělou inteligenci. Jak jsme uvedli na začátku, umělá inteligence je velmi široký a nesourodý obor. Kvůli tomu je prakticky nemožné vytvořit úplný přehled všeho, co je v umělé inteligenci obsaženo a do značné míry to ani nemá smysl. Jednotlivé metody umělé inteligence se používají tam, kde jsou zrovna vhodné. Jeden univerzální recept na umělou inteligenci prostě neexistuje.

Stránka 112/122


Doporučené studijní zdroje RUSSELL, S. – NORVIG, P. Artificial Intelligence: A Modern Approach (3nd Edition). Prentice Hall, 2010. 1132 s. ISBN 0-13-207148-7. MAŘÍK, V. – ŠTĚPÁNKOVÁ, O. – LAŽANSKÝ, J. a kol. Umělá inteligence 1. 1. vyd. Praha: Academia, 1993. 264 s. ISBN 80-200-0496-3. MAŘÍK, V. – ŠTĚPÁNKOVÁ, O. – LAŽANSKÝ, J. a kol. Umělá inteligence 2. 1. vyd. Praha: Academia, 1997. 373 s. ISBN 80-200-0504-8. MAŘÍK, V. – ŠTĚPÁNKOVÁ, O. – LAŽANSKÝ, J. a kol. Umělá inteligence 3. 1. vyd. Praha: Academia, 2001. 328 s. ISBN 80-200-0472-6. MAŘÍK, V. – ŠTĚPÁNKOVÁ, O. – LAŽANSKÝ, J. a kol. Umělá inteligence 4. 1. vyd. Praha: Academia, 2003. 476 s. ISBN 80-200-1044-0. SEKAJ, I. Evolučné výpočty a ich využitie v praxi. 1. vyd. Bratislava: Iris, 2005. 159 s. ISBN 80-89018-87-4.

Stránka 113/122


Přílohy

Stránka 114/122


Sbírka úloh pro samostatné vypracování Součástí této přílohy je seznam několika úkolů k řešení. Jedná se o zadání, na kterých si student může ověřit získané znalosti. Každá úloha má specifické parametry, proto je nutné si projít všechny dílčí kroky specifikace. Zpracování alespoň jedné vybrané úlohy je nutná podmínka účasti na zkoušce. Úlohy k vypracování: • • • •

Misionáři a kanibalové Problém rozestavění osmi dam na šachovnici Seřazení osmi čtverečků Volná úloha, nutná úvodní konzultace

Některé úlohy mají formou přílohy nápovědu. Nechte se inspirovat!

Stránka 115/122

Cvičebnice pro samostudium Umělá inteligence II Misionáři a kanibalové: úloha č. 1 pro cvičení k předmětu Umělá inteligence II Zadání: Implementujte vlastní řešení problému zvaného Misionáři a kanibalové (problém je popsán na konci tohoto textu). Pro implementaci použijte prohledávání stromu do šířky, kde strom representuje prostor všech možných řešení (implementace zahrnuje vygenerování a prohledání tohoto stromu). Účelem cvičení je vyzkoušet si řešení typické jednoduché úlohy z oblasti umělé inteligence. Řešení obdobných úloh výrazně pomáhá proniknutí do větší hloubky a pochopení některých záležitostí umělé inteligence. Studenti a studentky vypracují řešení každý zcela samostatně, programovací jazyk si mohou sami zvolit. Stručné zhodnocení problému a dosažených výsledků (stačí text v ASCII/ANSI) zašlou e-mailem na adresu <[email protected]>; subject (předmět) e-mailu musí obsahovat text KANIBALOVE a dále příjmení a jméno autorky/autora řešení (např. KANIBALOVE Novakova Josefa) pro jednoznačné přiřazení výsledku autorovi řešení. E-mail musí v příloze obsahovat kromě spustitelné (*.exe, resp. jiné) formy také zdrojový kód programu včetně kopie případných výpisů programu apod., aby bylo možno řešení zhodnotit. Řešení musí být založeno na běžně dostupných prostředcích pro vytvoření programu, aby mohlo být bez zvláštních požadavků na SW/HW vybavení ověřeno (nelze požadovat instalaci specifických SW nástrojů). Termín odevzdání úlohy dle zadaných požadavků je nejpozději do půlnoci 14. 10. 2012, později to není možné (vzhledem k dostatečnému času na řešení nelze přijmout žádné omluvy, proto doporučuji splnit zadání co nejdříve). Pokud nebude úkol splněn, nelze obdržet z předmětu zápočet a absolvovat zkoušku. Uvedený termín znamená, že úlohu lze odevzdat libovolně dřív. Popis úlohy Misionáři a kanibalové Tři misionáři a tři kanibalové jsou na jedné straně řeky a mají k dispozici jednu loďku, která uveze jednoho nebo dva lidi. Úkolem je najít způsob přepravy všech šesti lidí na druhou stranu řeky tak, aby nikdy nezůstala skupina misionářů s číselnou převahou kanibalů na jednom místě (břehu). Tento problém patří mezi proslulé problémy v oblasti umělé inteligence, protože byl jako první v literatuře formulován z analytického hlediska (v r. 1968). Zde je nutno napřed výrazně abstrahovat, tj. zbavit úlohu nepotřebných detailů (které by se pravděpodobně v reálné situaci vyskytly). Číselná převaha není v loďce možná, takže zbývají pouze oba břehy jako možnosti. Čas dopravy není nutno uvažovat. Pokud má do loďky nastoupit cestující, je jedno, který kanibal či misionář to je, nezáleží, na kterém břehu se začíná, apod. a) Stavy: stav se skládá z uspořádané sekvence tří čísel reprezentujících počet misionářů, počet kanibalů, a počet loděk na každém břehu. Tedy počáteční stav je (3, 3, 1) na výchozím břehu, (0, 0, 0) na cílovém, koncový (0, 0, 0) na výchozím a (3, 3, 1) na cílovém břehu. b) Operátory: z každého stavu existuje max. 5 možných operátorů: (1) do loďky 1 misionář, (2) do loďky 2 misionáři, (3) do loďky 1 kanibal, (4) do loďky 2 kanibalové, (5) do loďky 1 misionář a 1 kanibal. Ve většině stavů bude zřejmě méně operátorů k dispozici kvůli vyhnutí se nepřípustným stavům – převaze počtu kanibalů nad misionáři na libovolném z obou břehů. (Pozn.: kdybychom rozlišovali jednotlivce jako různé osoby, pak bychom měli celkem 27 operátorů, ale v úloze netřeba rozlišovat jednotlivce.) c) Test cíle: dosažení stavu (0, 0, 0) na výchozím břehu, (3, 3, 1) na cílovém. d) Cena cesty: počet přejezdů přes řeku (cílem je minimální počet přejezdů, tj. co nejlacinější řešení). Uvedený stavový prostor je dostatečně malý, takže pro počítač je nalezení výsledku triviální (pomocí “hrubé síly”), pro lidi je problém o dost obtížnější, zejména proto, že některé nezbytné kroky se zdají být retrográdní (zpětné, tj. je možné, aby kanibal nebo misionář cestovali i zpět na břeh, kde již předtím byli). e) Po vyřešení úlohy tři kanibalové a tři misionáři upravte zadání na problém dva misionáři a dva kanibalové, ostatní parametry zůstávají stejné. Podařilo se úlohu vyřešit? Pokud ne, vysvětlete důvody. Pokud ano, je úloha 2+2 z hlediska řešení výrazně jednodušší než 3+3, přibližně stejná, nebo složitější? Proč? f) Po vyřešení úlohy dva kanibalové a dva misionáři upravte zadání na složitý problém čtyři misionáři a čtyři kanibalové, ostatní parametry zůstávají stejné. Podařilo se úlohu vyřešit? Pokuste se o vysvětlení úspěchu či neúspěchu. Je úloha 4+4 z hlediska řešení výrazně jednodušší než 3+3 a 2+2, přibližně stejná, nebo složitější? Proč?

Stránka 116/122

Cvičebnice pro samostudium Umělá inteligence II Problém rozestavění osmi dam na šachovnici úloha č. 2 pro cvičení k předmětu Umělá inteligence II Zadání: Implementujte v libovolném programovacím jazyce heuristiku min-konflikt, zmíněnou na přednášce, pro uspořádání osmi vzájemně se nenapadajících dam na šachovnici 8x8. Své řešení otestujte na příkladu uvedeném v přednáškách a dále navrhněte ještě nějakou jinou testovací pozici (dle vlastního uvážení, nikoliv něco triviálního – je nutno si vyzkoušet a ukázat funkčnost heuristiky). Nakonec se pokuste vyřešit několik pozic vygenerovaných náhodně (na každém sloupci smí být ve výchozí pozici pouze jedna dáma a aspoň jedna dvojice by se měla na začátku vzájemně napadat – zajímavé je zkusit heuristiku min-konflikt pro více vzájemně se napadajících dvojic dam). Vyhodnoťte svá řešení – např. zjistěte průměrný počet kroků pro nalezení výsledku, nárůst jejich počtu při výskytu 2, 3 nebo více konfliktů, apod. V popisu svého řešení úlohy uveďte použité pozice dam na šachovnici (diagram, nebo lze např. použít běžnou šachovou notaci: sloupce označované zleva doprava písmeny a, b, ..., h, řady zdola nahoru čísly 1, 2, ..., 8, např. postavení v přednášce je Da7, Db4, Dc2, Dd5, De8, Df6, Dg3, Dh1; lze vynechat “D” označující figuru). Dále uveďte, jaké kroky, v jakém pořadí a počtu heuristika vytvořila a zda předložené pozice vyřešila či ne. Pokud ne, pokuste se neúspěch vysvětlit (heuristika nemusí vždy fungovat).

Pozice z přednášky s jednou dvojicí napadajících se dam (povinné)

Jedna z možných pozic s mnoha napadajícími se dámami (zájemci si mohou zkusit)

Pozn.: Heuristika min-konflikt se používá ve velmi mnoha reálných aplikacích, např. při automatizované podpoře návrhu VLSI (very large-scale integration) obvodů na mikročipech. Při vytváření počátečních konfigurací problémů je vhodné nepoužívat zcela náhodné generování (pozic dam, rozvrhu hodin, rozložení a propojení elektronických součástek, apod.), nýbrž se hned od začátku snažit vyhýbat se možným konfliktům (např. rozestavovat dámy jako “konfliktní” jezdce, protože dáma neatakuje jako jezdec). Tím lze dosáhnout až pouze lineární časové složitosti v odstraňování konfliktů z úvodní konfigurace. Studenti a studentky vypracují řešení každý zcela samostatně, programovací jazyk si mohou sami zvolit. Vše, co bylo pro řešení úlohy vytvořeno a použito, včetně stručného zhodnocení problému a dosažených výsledků, se odevzdá formou e-mailu s přílohou na adresu <[email protected]>. Předmět (subject) e-mailu MUSÍ obsahovat text složený ze slova 8-DAM a z příjmení a jména autora (např. 8 DAM Novakova Josefa). V emailu a jeho příloze by mělo být vše relevantní k zadané úloze (např. zdrojový kód programu včetně kopie případných výpisů programu, spustitelná verze programu, vytvořené náhodné počáteční pozice apod., aby bylo možno řešení zhodnotit). Spustitelnou *.exe formu posílejte v příloze jako komprimovanou verzi pomocí např. ZIP, protože některé servery odmítají z bezpečnostních důvodů posílat *.exe (kvůli automatické možnosti spuštění). Termín odevzdání úlohy dle zadaných požadavků je do půlnoci 16. 12. 2012, později to není možné (vzhledem k dostatečnému času na řešení nelze přijmout žádné omluvy, proto doporučuji splnit zadání co nejdříve). Pokud nebude úkol splněn, nelze obdržet z předmětu zápočet a absolvovat zkoušku.

Stránka 117/122

Cvičebnice pro samostudium Umělá inteligence II Seřazení osmi čtverečků: Úloha č. 3 pro cvičení k předmětu Umělá inteligence II Zadání: Implementujte v libovolném programovacím jazyce heuristiky h1 a h2 zmíněné na přednášce (viz také nápověda Heuristické funkce) pro uspořádání osmi čtverečků na ploše s devíti pozicemi (plocha 3×3, viz obrázek níže), kde konečné pořadí čtverečků označených čísly je 1, 2, 3, 4, 5, 6, 7, 8, přičemž volné políčko zůstane uprostřed. Požadované heuristiky jsou tzv. chybné umístění (h1) a manhattanská vzdálenost (h2). Vždy vygenerujte náhodně nejméně 10 počátečních pozic (rozmístění čtverečků) a pro každou počáteční pozici vyzkoušejte obě heuristiky h1 a h2. Na závěr spočítejte průměrnou účinnost (počet vyřešených a nevyřešených pozic a průměrný počet kroků na vyřešení pro vyřešené pozice) pro každou heuristiku (každá by měla mít min. 10 pokusů dle zadání). Srovnejte oba výsledky a určete, která z obou heuristik je účinnější. Účinnost vyjádřete v počtu kroků nutných k dosažení cílového stavu (jeden krok je jedno posunutí čtverečku). V každém případě uveďte závěr z poznatků získaných při řešení úlohy (tj. co vám z toho vyplynulo, zdali a jak se dá zvolený postup zobecnit, apod.). Pozn.: V případě, kdy některá z heuristik ani po mnoha pokusech nebude schopna najít řešení, pokuste se neúspěch zdůvodnit (nezapomeňte, že jde “pouze” o heuristiku). K neúspěchu může někdy dojít a pak lze udělat další pokus s dalšími náhodnými počátečními pozicemi. V případě zájmu doporučuji si dobrovolně udělat pokusy s více než 10 počátečními pozicemi (není povinné, ale poskytne věrohodnější výsledky). Může se snadno stát, že některé pozice (nebo mnoho z nich) žádná z obou heuristik nevyřeší – to je typický problém heuristik nejen v umělé inteligenci. Studenti a studentky vypracují řešení každý zcela samostatně, programovací jazyk si mohou sami zvolit. Vše, co bylo pro řešení úlohy vytvořeno, včetně stručného zhodnocení problému a dosažených výsledků, se odevzdá do odevzdávárny v UIS. Součástí odevzdaných výsledků musí být vše relevantní k řešení zadané úlohy (např. zdrojový kód programu včetně kopie případných výpisů programu, spustitelná verze programu, vytvořené náhodné počáteční pozice apod., aby bylo možno řešení vyhodnotit). Termín odevzdání úlohy dle zadaných požadavků je do půlnoci 21. 11. 2012, později to není možné (vzhledem k dostatečnému času na řešení nelze přijmout žádné omluvy, proto doporučuji splnit zadání co nejdříve). Pokud nebude úkol splněn, nelze obdržet z předmětu zápočet a absolvovat zkoušku. Upozornění: implementační i výpočetní doba může být relativně dlouhá, proto doporučuji začít řešit zadanou úlohu co nejdříve.

Stránka 118/122


Nápověda – Heuristické funkce Hlavolam s posouváním osmi čtverečků v devíti polích patří k nejstarším problémům s heuristickým vyhledáváním:

Typické řešení má zhruba 20 kroků (závisí to na počátečním stavu). Faktor větvení je cca 3 (je-li prázdné pole uprostřed, pak b = 4; v rohu je b = 2; podél hran je b = 3). Prohledávání vyčerpávající všechny možnosti do hloubky 20 zkoumá přibližně 320 = 3.5×109 stavů. Pokud by se důsledně testovaly stavy opakování, lze redukovat počet stavů radikálně, nebo existuje pouze 9! = 362 880 různých rozmístění pro 9 polí. To je stále velmi mnoho, proto je vhodné najít dobrou heuristiku. Pokud je cílem nalezení nejkratšího řešení, je zapotřebí mít heuristickou funkci, která nikdy nepřecení počet kroků do cíle. Dvě možnosti: •

•

h1 = počet čtverečků na chybných pozicích. Na obrázku je umístěno 7 z 8 chybně, takže počáteční stav má h = 7; je to přijatelná heuristika, protože každý chybně umístěný čtvereček musí být alespoň jednou posunut! h2 = součet vzdáleností čtverečků od jejich koncových pozicí. Čtverečky se nemohou pohybovat diagonálně, takže se sečtou vzdálenosti vertikální a horizontální (tento typ výpočtu vzdáleností je znám jako vzdálenost městských bloků nebo manhattanská vzdálenost). h2 je rovněž přijatelná, protože jakýkoliv posun pohne pouze jedním čtverečkem o jeden krok směrem k cíli. Čtverečky 1 až 8 z počátečního stavu na obrázku mají celkovou délku manhattanské cesty h2 = 2 + 3 + 3 + 2 + 4 + 2 + 0 + 2 = 18.

Stránka 119/122


Nápověda – Aplikace pro problémy vyhovující omezením (CSP) Problémy vyhovující omezením (Constraint Satisfaction Problems) mohou být řešeny metodami iterativního zlepšování tak, že napřed jsou všem proměnným dosazeny nějaké hodnoty a pak za použití modifikačních operátorů se konfigurace pohybuje směrem k řešení. Modifikační operátory jednoduše přiřazují jiné hodnoty proměnným. Např. pro problém 8 dam je počátečním stavem 8 dam nějak rozestavených na šachovnici a modifikační operátor může dámou pohnout o políčko vedle. Tyto algoritmy se nazývají heuristické opravování, nebo napravují nekonsistence aktuální konfigurace. Při výběru nové hodnoty proměnné se (heuristicky) vybírají takové hodnoty, které jako výsledek dávají minimální konflikty s ostatními proměnnými — tzv. heuristika min-konflikt:

Problém je zde vyřešen ve dvou krocích. Čísla ve sloupci s dámou, jejíž postavení se vylepšuje (Dh1 v pravém dolním rohu), udávají, s kolika jinými dámami je v konfliktu. Dáma je přesunuta na pole h6 (prostřední diagram), kde má konflikt s Df6. Dáma z pole f6 našla nekonfliktní místo na poli f1 a protože další konflikty nejsou, úloha je vyřešena. Překvapivě je metoda min-konflikt úspěšná pro mnoho problémů s omezením (CPS), např. problém s milionem dam má průměrné řešení v méně než 50 krocích. V nedávné době byla min-konflikt použita pro plánování pozorování vesmírného teleskopu Hubble (HST, Hubble Space Telescope), kde redukovala čas nutný pro naplánování týdenního pozorování ze tří týdnů na přibližnì 10 minut (astronomové si mohou podávat žádosti o pozorování pomocí HST a velké množství velmi různých žádostí vyžaduje velmi dobrý rozvrh).

Stránka 120/122


Seznam obrázků Obrázek 1: Řazení - ruční postup. ...........................................................................................7 Obrázek 2: Postup řazení. .......................................................................................................8 Obrázek 3: Postup řazení. .......................................................................................................9 Obrázek 4: Hra piškvorky, rozehráno....................................................................................11 Obrázek 5: Piškvorky – šachovnice. .....................................................................................11 Obrázek 6: Odhad časová složitost .......................................................................................19 Obrázek 7: Znázornění časové složitosti zvolené funkce. ......................................................20 Obrázek 8: Znázornění časové složitosti zvolené funkce. ......................................................21 Obrázek 9: Ukázka grafové struktury, uzly jsou stanice, hrany jsou trasy mezi každými dvěma stanicemi. .............................................................................................................................25 Obrázek 10: Rozklad hracího pole u hry piškvorky. ..............................................................26 Obrázek 11: Hledání cesty v grafu – Straight-Line Distance. ................................................34 Obrázek 12: Hledání cesty v grafu – Lačné prohledávání. .....................................................35 Obrázek 13: Hledání cesty v grafu – A*. ..............................................................................38 Obrázek 14: Hledání cesty v grafu – obrysy. .........................................................................39 Obrázek 15: Důkaz optimality algoritmu A*.........................................................................40 Obrázek 16: Hlavolam - desková hra. ...................................................................................42 Obrázek 17: Struktura jednoduchého agenta. ........................................................................52 Obrázek 18: Inteligentní agent s rozšířením o indikaci vnitřního stavu. .................................54 Obrázek 19: Struktura inteligentního agenta – cílově zaměřený agent. ..................................55 Obrázek 20: Struktura inteligentního agenta – užitkově zaměřený agent. ..............................56 Obrázek 21: Objekt - proces učení ........................................................................................80 Obrázek 22: Princip genetického algoritmu. .........................................................................92 Obrázek 23: Grafický průběh funkce. ...................................................................................93 Obrázek 24: Genetický algoritmus, generování jedinců v populaci. ......................................97 Obrázek 25: Srovnání použitých modelů na problém "výnosu cibule"................................. 100 Obrázek 26: Prioritní řízení síťového prvku. ....................................................................... 103 Obrázek 27: Paměť typu FIFO. ........................................................................................... 104 Obrázek 28: Generátor paketů. ........................................................................................... 104 Obrázek 29: Schéma přepínače. .......................................................................................... 105 Obrázek 30: Model bloku bloku Main Data Manageru. ....................................................... 105 Obrázek 31: Tabulka Chart bloku Paket generátoru. ........................................................... 106 Obrázek 32: Blok Standard Computing............................................................................... 107 Obrázek 33: Blok Hopfieldovy neuronové sítě.................................................................... 107 Obrázek 34: Sled prováděných paketů. ............................................................................... 108

Stránka 121/122


Seznam tabulek Tabulka 1: Popis struktury agenta. ........................................................................................49 Tabulka 2: Příklad agenta. ....................................................................................................50 Tabulka 3: Typy prostředí.....................................................................................................58 Tabulka 4: Vstupní hodnoty pro lokalitu Uraidla ................................................................ 100 Tabulka 5: Hodnoty modelu. .............................................................................................. 108

Stránka 122/122

UMĚLÁ INTELIGENCE 2. Cvičebnice pro samostudium. Ústav Informatiky PEF MENDELU. Pracovní skupina: Modelování a vizualizace

Recommend Documents