VYSOK É U ˇCENÍ TECHNICK É V BRN ˇE BRNO UNIVERSITY OF TECHNOLOGY

(1)

VYSOK ´ E U ˇ CEN´I TECHNICK ´ E V BRN ˇ E

BRNO UNIVERSITY OF TECHNOLOGY

FAKULTA INFORMA ˇ CNÍCH TECHNOLOGIÍ USTAV INTELIGENTNÍCH SYST ´ ´ EM ˚ U

FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INTELLIGENT SYSTEMS

ALGORITMY PRO UM ˇ ELOU INTELIGENCI

DIPLOMOV ´ A PR ´ ACE

MASTER’S THESIS

AUTOR PR ´ ACE JAN PETR ˇ ZELKA

AUTHOR

BRNO 2007

(2)

VYSOK ´ E U ˇ CEN´I TECHNICK ´ E V BRN ˇ E

BRNO UNIVERSITY OF TECHNOLOGY

FAKULTA INFORMA ˇ CNÍCH TECHNOLOGIÍ USTAV INTELIGENTNÍCH SYST ´ ´ EM ˚ U

FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INTELLIGENT SYSTEMS

ALGORITMY PRO UM ˇ ELOU INTELIGENCI

AI ALGORITHMS

DIPLOMOV ´ A PR ´ ACE

MASTER’S THESIS

AUTOR PR ´ ACE JAN PETR ˇ ZELKA

AUTHOR

VEDOUC´I PR ´ ACE Ing. VLADIM´IR JANOU ˇ SEK, Ph.D.

SUPERVISOR

BRNO 2007

(3)

Abstrakt

Tato diplomová práce se zabývá algoritmy pouˇz´ıvanými v oblasti umˇelé inteligence, konkrétnˇe se jedná o algoritmy popsané v knize Artificial Inteligence: A Modern Approach autor˚u Russela a Norviga a jejich implementaci v jazyce Squeak Smalltalk. Je kladen d˚uraz na objektovˇe orientovaný pˇr´ıstup, který vyplývá z podstaty jazyka Smalltalk. Zdrojem jsou kromˇe popis˚u algoritm˚u v pseudokódu pˇr´ımo v knize také existuj´ıc´ı implementace v jazyc´ıch Lisp, Python a Java. Tato práce se vˇenuje algoritm˚um pro práci s inteligentn´ımi agenty a prostˇred´ımi pro simulaci tˇechto agent˚u, prohledáván´ı stavového prostoru, hran´ı her, plánován´ı, logice, pravdˇepodobnosti a uˇcen´ı.

Kl´ıˇ cov´ a slova

umˇelá inteligence, algoritmy, smalltalk, squeak, AIMA, prohledáván´ı, hledán´ı, plánován´ı, hran´ı her, logika, uˇcen´ı, pravdˇepodobnost, neurˇcitost, agent, prostˇred´ı, OOP

Abstract

This master’s thesis describes artificial intelligence algorithms based on the book Artifi- cial Inteligence: A Modern Approach by S. Russel and P. Norvig and implementation of the algorithms in the Squeak Smalltalk programming language with object oriented approach. Algorithms are based on pseudocode in the book and existing implementations in Lisp, Python and Java language. Main concepts are intelligent agents, agent simulation environments, state space search, game playing, planning, uncertainty and learning.

Keywords

artificial intelligence, algorithms, smalltalk, squeak, AIMA, search, planning, game playing, logic, learning, probability, uncertainty, agent, environment, OOP

Citace

Jan Petrˇzelka: Algoritmy pro umˇelou inteligenci, diplomov´a pr´ace, Brno, FIT VUT v Brnˇe, 2007

(4)

Algoritmy pro umˇ elou inteligenci Prohl´ aˇ sen´ı

Prohlaˇsuji, ˇze jsem tuto diplomovou pr´aci vypracoval samostatnˇe pod veden´ım

Ing. Vladim´ıra Janouˇska. Uvedl jsem vˇsechny liter´arn´ı prameny a publikace, ze kter´ych jsem ˇcerpal.

. . . . Jan Petrˇzelka 21. kvˇetna 2007

Podˇ ekov´ an´ı

Rád bych na tomto m´ıstˇe podˇekoval panu Ing. Vladim´ıru Janouˇskovi za odbornou pomoc poskytnutou pˇri ˇreˇsen´ı problém˚u spojených s touto prac´ı a pˇredevˇs´ım za seznámen´ı s tak výjmeˇcným programovac´ım jazykem, jakým bezesporu Squeak Smalltalk je.

c

Jan Petrˇzelka, 2007.

Tato práce vznikla jako ˇskoln´ı d´ılo na Vysokém uˇcen´ı technickém v Brnˇe, Fakultˇe in- formaˇcn´ıch technologi´ı. Práce je chránˇena autorským zákonem a jej´ı uˇzit´ı bez udˇelen´ı oprávnˇen´ı autorem je nezákonné, s výjimkou zákonem definovaných pˇr´ıpad˚u.

(5)

Obsah

1 Uvod´ 4

2 Agenti a prostˇred´ı 6

2.1 Co je to umˇel´a inteligence? . . . 6

2.2 Inteligentn´ı agent . . . 6

2.3 Prostˇred´ı . . . 6

2.3.1 Prostˇred´ı plnˇe nebo ˇc´astˇeˇcnˇe pozorovateln´e . . . 7

2.3.2 Prostˇred´ı deterministick´e nebo stochastick´e . . . 7

2.3.3 Prostˇred´ı epizodick´e nebo sekvenˇcn´ı . . . 7

2.3.4 Prostˇred´ı statick´e nebo dynamick´e . . . 7

2.3.5 Prostˇred´ı diskr´etn´ı nebo spojit´e . . . 7

2.3.6 Prostˇred´ı s jedn´ım nebo v´ıce agenty . . . 8

2.4 Implementace agent˚u a jejich prostˇred´ı . . . 8

2.4.1 Tˇr´ıda Environment . . . 8

2.4.2 Tˇr´ıda GridEnvironment . . . 9

2.4.3 Tˇr´ıda VacuumWorld . . . 9

2.4.4 Tˇr´ıda WumpusWorld . . . 9

2.4.5 Tˇr´ıda Agent . . . 9

2.4.6 Tˇr´ıda AskUserAgent . . . 10

2.4.7 Tˇr´ıdy RandomVacuumAgent a RandomWumpusAgent . . . 10

2.4.8 Tˇr´ıdy ReactiveVacuumAgent a ReactiveWumpusAgent . . . 10

2.4.9 Tˇr´ıda Object . . . 10

2.4.10 Tˇr´ıda ObstacleObject . . . 10

2.4.11 Tˇr´ıda DeadlyObject . . . 10

2.4.12 Tˇr´ıda AgentBodyObject . . . 10

2.4.13 Tˇr´ıda ObjectSpec . . . 11

3 Reˇˇ sen´ı probl´em˚u 12 3.1 Reˇˇ s´ıc´ı agent . . . 12

3.2 Hled´an´ı ˇreˇsen´ı . . . 13

3.3 Neinformovan´e metody hled´an´ı . . . 13

3.3.1 Breadth-first search . . . 13

3.3.2 Uniform-cost search . . . 14

3.3.3 Depth-first search . . . 14

3.3.4 Iterative deepening depth-first search . . . 14

3.4 Informovan´e metody hled´an´ı . . . 14

3.4.1 Best-first search . . . 15

3.4.2 Greedy best-first search . . . 15

(6)

3.4.3 A* search . . . 15

3.5 Hran´ı her . . . 15

3.5.1 Minimax . . . 16

3.5.2 Alpha-beta pruning . . . 16

3.6 Implementace . . . 16

3.6.1 Tˇr´ıda Problem . . . 16

3.6.2 Tˇr´ıda Node . . . 17

3.6.3 Tˇr´ıda Game . . . 17

3.6.4 Tˇr´ıda GameState . . . 17

3.6.5 Prostˇred´ı . . . 17

3.7 Pˇr´ıklady . . . 18

3.7.1 Mision´aˇri a kanibalov´e . . . 18

3.7.2 Piˇskvorky . . . 18

3.7.3 D´ama . . . 18

4 Logika 19 4.1 Uvod do logiky . . . .´ 19

4.2 V´yrokov´a logika . . . 20

4.2.1 Jazyk v´yrokov´e logiky . . . 20

4.2.2 Odvozov´an´ı . . . 20

4.3 Predik´atov´a logika . . . 21

4.3.1 Jazyk predik´atov´e logiky . . . 21

4.3.2 Odvozován´ı v predikátové logice . . . 21

4.4.1 Tˇr´ıdy a algoritmy v´yrokov´e logiky . . . 22

4.4.2 Tˇr´ıdy a algoritmy predik´atov´e logiky . . . 22

5 Plánován´ı 24 5.1 Jazyk plánovac´ıch problém˚u . . . 24

5.2 Reˇˇ sen´ı pl´anovac´ıch probl´em˚u . . . 25

5.3.1 Objekty . . . 25

5.3.2 Prostˇred´ı . . . 26

5.3.3 Agent . . . 26

6 Neurˇcitost a pravdˇepodobnost 27 6.1 Neurˇcit´e znalosti . . . 27

6.2 Bayesovsk´e s´ıtˇe . . . 28

6.3 Statistick´e metody . . . 29

6.4.1 Tˇr´ıda EnumerateJointAsk . . . 29

6.4.2 Tˇr´ıda BayesNetNode . . . 30

6.4.3 Tˇr´ıda BayesNet . . . 30

7 Uˇcen´ı 32 7.1 Princip uˇcen´ı . . . 32

7.2 Rozhodovac´ı stromy . . . 33

7.3 Dalˇs´ı metody uˇcen´ı . . . 34

(7)

7.4.1 Tˇr´ıda DataSet . . . 35

7.4.2 Tˇr´ıda DecisionTreeLearner . . . 35

7.4.3 Tˇr´ıda AdaBoostLearner . . . 35

7.4.4 Tˇr´ıda DecisionListLearner . . . 36

8 Z´avˇer 37

(8)

Kapitola 1

Uvod ´

Objektem zájmu této práce je kniha Artificial Inteligence: A Modern Approach (Second Edition) autor˚u Stuarta Russela a Petera Norviga [1]. Tato kniha je primárnˇe urˇcena jako uˇcebnice pro studium umˇelé inteligence.

Jelikoˇz umˇelá inteligence je velmi ˇsiroký pojem, popisuje i tato kniha mnoho pohled˚u na tuto problematiku: logiku, pravdˇepodobnost, vn´ımán´ı, logické myˇslen´ı, uˇcen´ı a mnoho jiných. Vˇsechny tyto oblasti spojuje jeden pojem – inteligentn´ı agent. Umˇelá inteligence je zde definována jako studium agent˚u, kteˇr´ı pˇrij´ımaj´ı vjemy z prostˇred´ı a na jejich základˇe konaj´ı akce. Kaˇzdý takový agent obsahuje funkci, která pˇriˇrazuje ke vjemu posloupnost akc´ı, pˇriˇcemˇz existuje mnoho zp˚usob˚u jak tuto funkci reprezentovat. Pro lepˇs´ı názornost obsahuje kniha ˇradu algoritm˚u v pseudokódu, které pˇredstavuj´ı ˇreˇsen´ı vybraných problém˚u z této oblasti. Aby bylo moˇzné pouˇz´ıt tyto algoritmy v praxi, existuj´ı v souˇcasné dobˇe jejich implementace ve tˇrech jazyc´ıch, v Lispu, Pythonu a Javˇe.

C´ılem této práce je vytvoˇrit podobnou implementaci v jazyce Squeak Smalltalk a popsat tyto algoritmy jak po teoretické stránce, tak i po stránce implementaˇcn´ı. Smalltalk, jakoˇzto ˇ

cistˇe objektovˇe orientovaný jazyk, poskytuje, d´ıky zapouzdˇren´ı, vysokou úroveˇn abstrakce a to pˇrisp´ıvá k pˇrehlednosti výsledného kódu. Ten má být urˇcen pˇredevˇs´ım pro výukové

´

uˇcely, kde pˇrehlednost a ˇcistota kódu je jedn´ım ze stˇeˇzejn´ıch faktor˚u. Squeak je open source prostˇred´ı zaloˇzené na Smalltalku-80, které se svým grafickým uˇzivatelským rozhran´ım Mor- phic je vhodné pro výuku, nav´ıc pro tento jazyk zat´ım neexistuje ˇzádná významná knihovna algoritm˚u pro umˇelou inteligenci.

Pro porozumnˇen´ı kódu se pˇredpokládaj´ı základn´ı znalosti v oblasti informatiky (algoritmy, datové struktury) a jazyka Smalltalk (napˇr. seriál Pavla Kˇrivánka na serveru root.cz [2] je dobrým úvodem do tohoto jazyka).

Tato práce navazuje na m˚uj roˇcn´ıkový projekt, ve kterém jsem zaˇcal s implementac´ı dále popsaných algoritm˚u, konkrétnˇe z kapitol 2, 3 a 5, a v rámci semestráln´ıho projektu jsem pˇridal kód ze zbývaj´ıc´ıch kapitol. Souhrn implementovaného kódu pro Smalltalk a jeho um´ıstˇen´ı v knize je sepsán v pˇr´ıloze A.

Následuj´ıc´ı kapitoly obsahuj´ı vˇzdy teoretický popis dané oblasti umˇelé inteligence a principy ˇreˇsen´ı problém˚u s nimi spojených, slouˇz´ıc´ı jako úvod do problematiky a pro lepˇs´ı porozumˇen´ı vytvoˇreného kódu, a dále konkrétn´ı popis implementace vytvoˇrených tˇr´ıd a metod ve Squeaku.

(9)

Kapitola 2 seznamuje se stˇeˇzejn´ı ˇc´ast´ı k´odu, inteligentn´ımi agenty

Kapitola 3 popisuje ˇreˇsen´ı problém˚u a algoritmy pro hledán´ı ve stavovém prostoru Kapitola 4 pˇredstavuje základy výrokové a predikátové logiky

Kapitola 5 se zabývá plánován´ım

Kapitola 6 vysvˇetluje prinicipy neurˇcitosti a pravdˇepodobnosti pˇri ˇreˇsen´ı probl´em˚u Kapitola 7 je zamˇeˇrena na uˇcen´ı

Kapitola 8 shrnuje a vyhodnocuje dosaˇzen´e v´ysledky

(10)

Kapitola 2

Agenti a prostˇ red´ı

2.1 Co je to umˇ el´ a inteligence?

Existuje nˇekolik definic toho pojmu, kter´e se odliˇsuj´ı pˇredevˇs´ım pohledem na toto t´ema.

Prvn´ı pohled rozliˇsuje zda jsou pˇredmˇetem zájmu myˇslenkové procesy a uvaˇzován´ı nebo naopak zda jde pˇredevˇs´ım o chován´ı subjektu. Z druhé strany lze posuzovat m´ıru lidskosti ˇ

ci naopak m´ıru inteligence. Systém je inteligentn´ı, pokud za daných okolnost´ı udˇelá

”tu spr´avnou vˇec“.

Výˇse zm´ınˇená kniha se vˇenuje pˇr´ıstupu inteligentn´ıho chován´ı, protoˇze inteligentn´ı pˇr´ıstup je v´ıce obecný a pˇredevˇs´ım v´ıce vˇedecký neˇz pˇr´ıstup odv´ıjej´ıc´ı se z myˇslenkových pochod˚u ˇci lidského chován´ı.

2.2 Inteligentn´ı agent

Jak jiˇz bylo zm´ınˇeno v úvodu, agent je entita, která pˇrij´ımá vjemy ze svého prostˇred´ı pomoc´ı senzor˚u a provád´ı akce v tomto prostˇred´ı. Matematicky vzato je chován´ı kaˇzdého agenta popsáno funkc´ı, která kaˇzdému vjemu pˇriˇrad´ı nˇejakou akci.

Inteligentn´ı agent je nový pojem specifikuj´ıc´ı subjekt, který se chová tak, aby dosáhl nejlepˇs´ıho výsledku. Abychom mohli urˇcit, který výsledek je ten nejlepˇs´ı, mus´ıme ohodnotit jeho ˇcinnost. Ohodnocen´ı je vˇzdy závislé na dané situaci, nicménˇe základn´ı pravidlo je, ˇze by mˇelo být urˇceno podle toho, ˇceho chceme v prostˇred´ı dosáhnout, a ne podle toho, jak si mysl´ıme, ˇze by se agent mˇel chovat. Jako pˇr´ıklad je moˇzno uvést prostˇred´ı z knihy AIMA VacuumWorld, kde agent-vysavaˇc ukl´ız´ı smet´ı na podlaze. Pokud by tento agent byl ohodnocen za kaˇzdé uklizen´ı nˇejakého mnoˇzstv´ı smet´ı, nejlepˇs´ı skóre by z´ıskal tak, ˇze vˇse uklid´ı, vysype zpˇet na podlahu a ukl´ız´ı znovu. Mnohem lepˇs´ı zp˚usob ohodnocen´ı by tedy byl za ˇcistou podlahu.

Inteligentn´ı agent by mˇel pro kaˇzdou posloupnost vjem˚u zvolit takovou akci, která podle pˇredpokladu maximalizuje jeho ohodnocen´ı v souladu s tˇemito vjemy a jakýmikoli dalˇs´ımi znalostmi, které agent má.

2.3 Prostˇ red´ı

Nejprve bychom mˇeli definovat pojemprostˇred´ı ´ulohy. To bychom mohli nazvat

”probl´emem“, ke kter´emu je inteligentn´ı agent

”ˇreˇsen´ım“. Prostˇred´ı úlohy je mnoˇzina skládaj´ıc´ı se z ohodnocen´ı, prostˇred´ı, agentových senzor˚u a jeho zaˇr´ızen´ı konaj´ıc´ıch akce. V návrhu agenta je

(11)

nutn´e jako prvn´ı krok specifikovat prostˇred´ı ´ulohy co nejpˇresnˇeji.

Protoˇze v oblasti umˇel´e inteligence je mnoho r˚uzn´ych moˇznost´ı specifikace prostˇred´ı

´

ulohy, je vhodné jej klasifikovat podle nˇekolika faktor˚u. To nám umoˇzn´ı pˇresnˇejˇs´ı a jednoduˇsˇs´ı návrh agenta.

2.3.1 Prostˇred´ı plnˇe nebo ˇc´astˇeˇcnˇe pozorovateln´e

Plnˇe pozorovatelné prostˇred´ı je takové, kdy senzory agenta maj´ı pˇr´ıstup k úplnému stavu prostˇred´ı v kaˇzdém okamˇziku. Takové prostˇred´ı je výhodné, protoˇze agent nepotˇrebuje internˇe udrˇzovat informace o aktuáln´ım stavu okol´ı. Prostˇred´ı m˚uˇze být ˇcásteˇcnˇe po- zorovatelné napˇr´ıklad protoˇze nˇekteré údaje senzory neposkytuj´ı, jako v pˇr´ıpadˇe Vacu- umWorld, kdy agent-vysavaˇc má informaci o smet´ı pouze na m´ıstˇe, kde se právˇe vyskytuje, a nev´ı, jestli je smet´ı i jinde.

2.3.2 Prostˇred´ı deterministick´e nebo stochastick´e

Pokud následuj´ıc´ı stav prostˇred´ı je pˇresnˇe urˇcen stavem souˇcasným a akc´ı konanou agentem, je toto prostˇred´ı deterministické, v opaˇcném pˇr´ıpadˇe stochastické. V podstatˇe bychom mohli ˇr´ıct, ˇze agent se v deterministickém a plnˇe pozorovatelném prostˇred´ı nemus´ı zabývat pravdˇepodobnost´ı. Pokud je prostˇred´ı pozorovatelné ˇcásteˇcnˇe, m˚uˇze se jevit jako stochastické, zejména pokud je sloˇzité a nen´ı moˇzné uchovat informace o nepozorovaných objektech. Proto je lepˇs´ı o tomto rozdˇelen´ı pˇremýˇslet z pohledu agenta. Pokud je prostˇred´ı deterministické kromˇe akc´ı ostatn´ıch agent˚u, nazývá se strategické.

2.3.3 Prostˇred´ı epizodick´e nebo sekvenˇcn´ı

V epizodickém prostˇred´ı jsou agentovy zkuˇsenosti rozdˇeleny do atomických epizod, v kaˇzdé agent vn´ımá a následnˇe provede jednu akci. Podstatné je, ˇze dalˇs´ı epizoda nijak nezávis´ı na té pˇredchoz´ı. Typický pˇr´ıklad je agent zkoumaj´ıc´ı vadné výrobky na montáˇzn´ı lince, kde kaˇzdé jeho rozhodnut´ı nemá vliv na ostatn´ı výrobky. V sekvenˇcn´ım prostˇred´ı, na druhou stranu, aktuáln´ı rozhodnut´ı m˚uˇze m´ıt vliv na vˇsechna dalˇs´ı rozhodnut´ı. Epizodická prostˇred´ı jsou mnohem jednoduˇsˇs´ı, protoˇze agent nemus´ı pˇremýˇslet dopˇredu.

2.3.4 Prostˇred´ı statick´e nebo dynamick´e

Pokud se prostˇred´ı m˚uˇze zmˇenit zat´ımco agent uvaˇzuje, je pro agenta dynamické, v opaˇcném pˇr´ıpadˇe statické. Se statickými prostˇred´ımi se jednoduˇseji pracuje, protoˇze agent nemus´ı sledovat okoln´ı svˇet ve chv´ıli, kdy uvaˇzuje nad akc´ı, ani si nemus´ı dˇelat starosti s plynut´ım ˇ

casu. Dynamická prostˇred´ı neustále po agentovi vyˇzaduj´ı nˇejakou akci a pokud se jeˇstˇe nerozhodl, nedˇelá nic. Pokud se s plynut´ım ˇcasu nemˇen´ı prostˇred´ı ale agentovo skóre, je takové prostˇred´ı semidynamické, pˇr´ıkladem takového prostˇred´ı jsou ˇsachy.

2.3.5 Prostˇred´ı diskr´etn´ı nebo spojit´e

Rozdˇelen´ı na diskrétn´ı nebo spojité m˚uˇze být pouˇzito na stav prostˇred´ı, zp˚usob jak je vn´ımán ˇcas nebo na agentovy vjemy a akce. Napˇr´ıklad ˇsachová partie má koneˇcný poˇcet diskrétn´ıch stav˚u, stejnˇe jako vjem˚u a akc´ı, narozd´ıl od ˇr´ızen´ı auta, kde rychlost i pozice jsou spojité veliˇciny. Vstup z digitáln´ı kamery je pˇresnˇe vzato diskrétn´ı, ale typicky je vn´ımán spojitˇe jako sled promˇenlivých intenzit a pozic.

(12)

2.3.6 Prostˇred´ı s jedn´ım nebo v´ıce agenty

Zdá se, ˇze je velmi jednoduché klasifikovat prostˇred´ı jako single- nebo multi-agentn´ı, nicménˇe je potˇreba urˇcit, zda ostatn´ı objekty v daném prostˇred´ı je nutné povaˇzovat za agenty, nebo stochasticky chovaj´ıc´ı-se objekty. V prostˇred´ı s agentem A a objektem B m˚uˇzeme ˇr´ıct, ˇze B je agent, pokud by se jeho chován´ı dalo popsat jako maximalizace ohodnocen´ı, jehoˇz hodnota závis´ı na chován´ı agenta A. V partii ˇsachu, napˇr´ıklad, se entita B snaˇz´ı zvýˇsit svoje ohodnocen´ı, a to, podle pravidel hry, sniˇzuje ohodnocen´ı agenta A. Takové prostˇred´ı je konkurenˇcn´ı multiagentn´ı. Naopak pˇri ˇr´ızen´ı vozidla, vyhýbán´ı se sráˇzkám vzájemnˇe skóre zvyˇsuje, proto je to ˇcásteˇcnˇe kooperativn´ı multiagentn´ı prostˇred´ı. ˇCásteˇcnˇe je to i konkurenˇcn´ı prostˇred´ı nebot’ napˇr. na jednom parkovac´ım m´ıstˇe m˚uˇze stát pouze jedno auto. V multiagentn´ıch prostˇred´ıch vyvstávaj´ı problémy s designem agent˚u, napˇr´ıklad pˇri komunikaci mezi nimi.

2.4 Implementace agent˚ u a jejich prostˇ red´ı

Vˇetˇsina kódu je postavena na principu agent˚u, kteˇr´ı konaj´ı akce na základˇe vjem˚u pˇrijatých z prostˇred´ı, a prostˇred´ı, které reflektuje tyto akce zmˇenami stavu. Vˇsechny dalˇs´ı algoritmy jsou odvozeny nebo pˇripojeny k tomuto základn´ımu principu. Ten tud´ıˇz pˇr´ımo vede k objektovˇe orientované implementaci, kde lze s úspˇechem vyuˇz´ıt abstrakci a pˇredevˇs´ım dˇediˇcnost. Pokud je napˇr´ıklad potˇreba pouˇz´ıt vyhledávac´ı algoritmus, je vytvoˇreno obecné prostˇred´ı, jeho poˇcáteˇcn´ı stav je nastaven na poˇcáteˇcn´ı stav ze kterého se vyhledává, do tohoto prostˇred´ı je um´ıstˇen obecný agent a program tohoto agenta volá zvolený vyhledávac´ı algoritmus. Agent poté provád´ı akce, postupnˇe podle vygenerované posloupnosti, vedouc´ı k c´ılovému stavu. Ve Smalltalku lze toto provést na úrovni jiˇz existuj´ıcich tˇr´ıd pouze zmˇenou jejich instanc´ı, nicménˇe ˇcistˇs´ı cesta je vytvoˇren´ı nové tˇr´ıdy pro prostˇred´ı, které je jiˇz pevnˇe svázáno s daným problémem, tzn. potomka tˇr´ıdy obecné prostˇred´ı a vytvoˇren´ı potomka tˇr´ıdy obecný agent, který je pˇr´ımo usp˚usoben k vyhledáván´ı ve stavovém prostoru. A pˇresnˇe t´ımto zp˚usobem je vytvoˇren kód tohoto projektu. Zde jsou podrobnˇe popsány tˇr´ıdy tvoˇr´ıc´ı základy kódu projektu. Vzhledem k tomu, ˇze Squeak nemá jmenné prostory, jsou jména vˇsech tˇr´ıd tohoto projektu doplnˇena prefixem

”AIMA“, aby nedoˇslo k moˇznému konfliktu s jiˇz existuj´ıc´ımi tˇr´ıdami systému. Tento prefix zde nen´ı uveden nebot’ zbyteˇcnˇe vede ke ztrátˇe pˇrehlednosti. Toto plat´ı i pro následuj´ıc´ı kapitoly.

2.4.1 Tˇr´ıda Environment

V hierarchii tˇr´ıd reprezentuj´ıc´ıch prostˇred´ı je nejvýˇse Environment. Tato tˇr´ıda poskytuje mechanizmy pro bˇeh prostˇred´ı, obsluhuje své agenty, pˇredává jim vjemy, spouˇst´ı jejich programy a provád´ı jejich akce. Rovnˇeˇz zaznamenává skóre jednotlivých agent˚u. Kaˇzdá instance této tˇr´ıdy v sobˇe uchovává kolekci agent˚u agents, kteˇr´ı v prostˇred´ı p˚usob´ı, ˇc´ıtaˇc krok˚usteps, maximáln´ı poˇcet krok˚umaxSteps, po dosaˇzen´ı tohoto poˇctu krok˚u je prostˇred´ı ukonˇceno, a sv˚uj aktuáln´ı stavstate. Základn´ı metoda této tˇr´ıdy jerun, která spust´ı proces obslouˇzen´ı jednotlivých agent˚u dokud nen´ı dosaˇzeno maximáln´ıho poˇctu krok˚u maxSteps nebo ukonˇcen´ı simulace testem isTermination. V kaˇzdém kroku metody run je kaˇzdému agentovi pˇredán jeho vjem pomoc´ı metody getPercept a následnˇe od nˇej vyˇzádána akce, ta je ve formˇe symbolu. Mnoˇzinu vˇsech moˇzných akc´ı v daném prostˇred´ı vrac´ı metoda legalActions. Potomci této tˇr´ıdy pak implementuj´ı jednotlivé akce jako metody (zprávy) a pomoc´ı Smalltalkovské metodyperform: aSymbol je tato akce provedena. Akce vˇsech agent˚u

(13)

se provádˇej´ı aˇz po vyhodnocen´ı vjem˚u vˇsech agent˚u v metodˇe executeAgentActions, ta je volána zupdate, kde se rovnˇeˇz provádˇej´ı zmˇeny prostˇred´ı pro kaˇzdý krok. Následnˇe je vˇsem agent˚um vyhodnoceno skóre pomoc´ı metody performanceMeasure. T´ım konˇc´ı cyklus krok˚u a pokud nen´ı kladnˇe vyhodnocena metodaisTermination, pokraˇcuje cyklus dalˇs´ım krokem.

2.4.2 Tˇr´ıda GridEnvironment

GridEnvironment je potomek obecného prostˇred´ı a reprezentuje prostˇred´ı s prostorem, který lze adresovat pomoc´ı souˇradnic x,y. Obecné prostˇred´ı v˚ubec pojem prostoru nezavád´ı.

Na kaˇzdé pozici v prostoru se m˚uˇze vyskytovat nˇekolik objekt˚u, ty jsou podrobnˇeji popsány n´ıˇze. V mnoˇzinˇe legalActions této tˇr´ıdy jsou akce turn, forward, grab a release, které umoˇzˇnuj´ı agentovi otoˇcit se, j´ıt dopˇredu a zvednout nebo pustit objekt vyskytuj´ıc´ı se na stejném m´ıstˇe jako agent, resp. v jeho kontejneru. Vzhledem k tomu, ˇze se zde pouˇz´ıvá prostor, je tˇreba také vytvoˇrit metody pro pohyb v nˇem, a to gridAt:, která vrac´ı kolekci objekt˚u na dané pozici, gridAt:put:, jeˇz um´ıst´ı objekt na danou pozici, a gridAt:remove:, která daný objekt ze zvolené pozice odebere. Dále je potˇreba metoda, která hledá objekt na dané pozicifindObjectIf:at:a také na sousedn´ıch pozic´ıchfindNeighborIf:at:. Jejich spojen´ım je pak metodafindObjectOrNeighborIf:at:. Pˇri vytvoˇren´ı instance této tˇr´ıdy je nastavena velikost prostˇred´ı, souˇradnice poˇcáteˇcn´ıho bodu a vytvoˇreny objekty pomoc´ı tˇr´ıdyObjectSpec, která je popsána n´ıˇze.

2.4.3 Tˇr´ıda VacuumWorld

VacuumWorld je ukázkové prostˇred´ı pro agenta-vysavaˇce, který se pohybuje v prostoru a vysává smet´ı, jeho skóre poˇc´ıtá metoda performanceMeasure v závislosti na poˇctu sesb´ıraných objekt˚u - prachových ˇcástic. Pˇri inicializaci je náhodnˇe vytvoˇren prach na vˇsech m´ıstech s pravdˇepodobnost´ı 25%. Mezi povolené akce patˇr´ı kromˇeturn aforward takésuck, která vysaje prach na pozici agenta, ashutOff, která agenta ukonˇc´ı.

2.4.4 Tˇr´ıda WumpusWorld

WumpusWorld je rovnˇeˇz ukázkové prostˇred´ı, tentokrát vˇsak jde o jeskyni obsahuj´ıc´ı kromˇe agenta také zlato, jámy a pˇr´ıˇseru zvanou Wumpus. Agent mus´ı na základˇe vjem˚u dosáhnout nejvˇetˇs´ıho skóre, v tomto pˇr´ıpadˇe to znamená naj´ıt zlato, nespadnout do jámy a nenechat se seˇzrat. V pˇredefinované metodˇegetPercept je agentovi vrácen vjem na základˇe jeho okol´ı, pokud je v jeho sousedstv´ı Wumpus, obdrˇz´ı symbol#stench, pokud je vedle jámy, dostane

#breeze v pˇr´ıpadˇe, ˇze na stejné pozici jako on je zlato, dostane#glitter, kdyˇz naraz´ı do zdi, je mu pˇredáno #bump a pokud nˇekterý objekt v jeskyni vydá nˇejaký zvuk, dostane se mu

#sound. Agentovi je pˇredána kolekce vˇsech symbol˚u, které jsou v danou chv´ıli pravdivé, a na jejich základˇe zvol´ı nˇejakou akci.

2.4.5 Tˇr´ıda Agent

Jako základn´ı tˇr´ıda pro agenty slouˇz´ıAgent. Obsahuje instanˇcn´ı promˇennou program, do které se ukládá blok s agentovým programem. Jeho nepovinným parametrem je kolekce vjem˚u a vrac´ı symbol akce. Rovnˇeˇz je moˇzné pˇr´ımo pˇret´ıˇzit metodu runProgram, která tento blok vyhodnocuje, v pˇr´ıpadných potomc´ıch se sloˇzitˇejˇs´ımi programy. Dále kaˇzdá instance uchovává v promˇenných svoje skóre, jméno, aktuáln´ı vjem, akci, která je naplnˇena programem a své tˇelo, coˇz je jeden z objekt˚u vGridEnvironment a potomc´ıch.

(14)

2.4.6 Tˇr´ıda AskUserAgent

AskUserAgent je potomek tˇr´ıdyAgent, který m´ısto proveden´ı svého programu vˇzdy vyvolá dotaz na uˇzivatele, zobraz´ı aktuáln´ı vjem a ˇceká na vloˇzen´ı akce, kterou má provést.

2.4.7 Tˇr´ıdy RandomVacuumAgent a RandomWumpusAgent

Tito potomci tˇr´ıdy Agent slouˇz´ı k testovac´ım úˇcel˚um pro VacuumWorld resp. Wumpus- World. Jejich program pouze náhodnˇe vyb´ırá akci z mnoˇziny vˇsech moˇzných akc´ı pro dané prostˇred´ı.

2.4.8 Tˇr´ıdy ReactiveVacuumAgent a ReactiveWumpusAgent

Tyto tˇr´ıdy agent˚u slouˇz´ı k uk´azce pr´ace agenta ve VacuumWorld resp. WumpusWorld.

Jejich program je v podstatˇe mapovac´ı funkce, kter´a na z´akladˇe vjem˚u zvol´ı vhodnou akci za

´

uˇcelem z´ıskán´ı nejvˇetˇs´ıho moˇzného poˇctu bod˚u. Hlavn´ı úkol agenta ReactiveVacuumAgent je vysávat smet´ı, ˇcili pokud na nˇej naraz´ı, vysaje jej. Pokud naraz´ı do stˇeny, otoˇc´ı se.

V ostatn´ıch pˇr´ıpadech náhodnˇe zvol´ı, jestli p˚ujde dopˇredu nebo se otoˇc´ı. Program agenta ReactiveWumpusAgent je trochu sloˇzitˇejˇs´ı, a to zejména z d˚uvodu plánu akc´ı, který si agent internˇe uchovává. Pokud napˇr´ıklad naraz´ı do stˇeny, otoˇc´ı se dvakrát doprava a jde kupˇredu, ˇ

cili se pohybuje od zdi pryˇc. Plán je ˇreˇsen jako kolekce akc´ı, a pokud program hledá vhodnou akci a plán nen´ı prázdný, vrát´ı prvn´ı akci z fronty. Pokud najde zlato, sebere jej. Vzhledem k tomu, ˇze v prostˇred´ıWumpusWorld vydá zvuk pouze um´ıraj´ıc´ı Wumpus, pamatuje si agent také, jestli je Wumpus jeˇstˇe naˇzivu.

2.4.9 Tˇr´ıda Object

Object je základn´ı tˇr´ıdou pro výskyt jakéhokoli objektu v prostoru prostˇred´ı. Kaˇzdý objekt má definovaný tvar, barvu, velikost, kontejner pro dalˇs´ı objekty, smˇer jakým je otoˇcen a nˇekolik dalˇs´ıch atribut˚u. Jsou nad n´ım definovány metody pro um´ıstˇen´ı v prostoru. Ob- sahuje také metodyisObstacle, isGrabable a isDeadly, které vracej´ı pouze true nebo false, a slouˇz´ı k jednoduché definici, co je objekt zaˇc, zda je pˇrekáˇzkou, jestli se dá zvednout, ˇ

ci je-li pro agenta smrt´ıc´ı. V n´asleduj´ıc´ıch potomc´ıch tˇr´ıdy jsou tyto metody jednoduˇse pˇredefinov´any.

2.4.10 Tˇr´ıda ObstacleObject

ObstacleObject je tˇr´ıda reprezentuj´ıc´ı pˇrekáˇzku, konkrétnˇe to m˚uˇze být napˇr. zed’. Agent, který se pokus´ı pˇrem´ıstit na pozici s pˇrekáˇzkou, obdrˇz´ı vjem náraz (#bump).

2.4.11 Tˇr´ıda DeadlyObject

DeadlyObject je napˇr. j´ama nebo Wumpus a pokud se agent ocitne na pozici spoleˇcnˇe s objektem t´eto tˇr´ıdy, je ukonˇcen.

2.4.12 Tˇr´ıda AgentBodyObject

Protoˇze i agent se mus´ı vyskytovat na nˇejaké pozici v prostoru, je mu vytvoˇreno tˇelo, které je instanc´ı této tˇr´ıdy. Toto tˇelo je pˇri inicializaci pˇridˇeleno agentovi do instanˇcn´ı promˇenné body.

(15)

2.4.13 Tˇr´ıda ObjectSpec

Ponˇevadˇz je potˇreba pro kaˇzdé prostˇred´ı s prostorem vytváˇret urˇcitou sadu objekt˚u, je vhodné vytvoˇrit tˇr´ıdu, která schopna tuto operaci nˇejakým zp˚usobem usnadnit. Proto je tˇr´ıda GridEnvironment vytvoˇrena tak, aby pˇri inicializaci obdrˇzela kolekci objekt˚u typu ObjectSpec a tyto specifikace postupnˇe aplikovala na sama sebe. Tˇr´ıda ObjectSpec oˇcekává vloˇzen´ı typu objektu, který má reprezentovat pomoc´ı metodywhat. Jako nepovinné údaje je moˇzno vloˇzit poˇcet, pozici ˇci pravdˇepodobnost vytvoˇren´ı objektu pomoc´ı metodcount,at aprobability. Pro zadán´ı pozice obsahuje i speciáln´ı metody, které dokáˇz´ı vytvoˇrit objekt na vˇsech pozic´ıch prostoru, po okraj´ıch, ˇci náhodnˇe: atAll,atEdge a atFree. Je tedy pomˇernˇe snadné vytvoˇrit specifikaci pro zed’ po okraj´ıch prostoru, nebo prach vˇsude s 25 procentn´ı pravdˇepodobnost´ı. Pˇri inicializaci prostˇred´ı je vˇsem instanc´ım tˇr´ıdy ObjectSpec zaslána zprávaapplyTo s parametrem prostˇred´ı a ta pomoc´ı metodymakeObject a dˇr´ıve zadaných specifikac´ı vytvoˇr´ı daný objekt. Tˇr´ıda zná pouze symbol tohoto objektu, samotné vytvoˇren´ı instance zajist´ı tˇr´ıdn´ı metoda daného prostˇred´ı, která je zavolána pomoc´ıperform. Pokud je specifikováno, ˇze objekt nen´ı lokáln´ı (metodou isLocal), ˇcili nepatˇr´ı-li pˇr´ımo k danému prostˇred´ı, pak nen´ı volána tˇr´ıdn´ı metoda prostˇred´ı, ale symbol je pˇr´ımo nalezen v globáln´ım slovn´ıkuSmalltalk a je vytvoˇrena instance této tˇr´ıdy.

(16)

Kapitola 3

Reˇ ˇ sen´ı probl´ em˚ u

V pˇredchoz´ı kapitole byl ukázán inteligentn´ı agent, který jednal na principu pˇr´ımého pˇriˇrazen´ı akce k urˇcitému stavu. Takov´ı agenti nefunguj´ı pˇr´ıliˇs dobˇre v rozsáhlých prostˇred´ıch, kde takové pˇriˇrazen´ı akc´ı ke vjem˚um by bylo pˇr´ıliˇs sloˇzité a robustn´ı. Na druhou stranu, agenti, kteˇr´ı jsou zamˇeˇren´ı na c´ıl m´ısto konkrétn´ıho vjemu, mohou uspˇet d´ıky zvaˇzován´ı budouc´ıch moˇzných akc´ı a vhodnosti výsledku tˇechto akc´ı.

3.1 Reˇ ˇ s´ıc´ı agent

Jeden druh takového agenta se nazýváˇreˇs´ıc´ı agent a ten je pˇredmˇetem zájmu této kapitoly.

Reˇˇ s´ıc´ı agenti se rozhoduj´ı co provedou na základˇe nalezen´ı posloupnosti akc´ı, které vedou k ˇzádaným stav˚um. Prvn´ım krokem pˇri tvorbˇe takového agenta je správná formulace c´ıle, který pomáhá agentovi hledat správnou cestu, vylouˇc´ı ostatn´ı moˇznosti a t´ım znaˇcnˇe zúˇz´ı mnoˇzinu stav˚u, do kterých agent m˚uˇze prostˇred´ı dostat. Za c´ıl m˚uˇzeme povaˇzovat mnoˇzinu stav˚u, kde kaˇzdý stav splˇnuje podm´ınku, ˇze problém je vyˇreˇsen. Protoˇze agent˚uv úkol je nalézt posloupnost akc´ı, které vedou k c´ılovému stavu, je nutné rozhodnout, s jakými akcemi a stavy m˚uˇze agent pracovat. To je d˚uleˇzité pro formulaci problému, zvolit urˇcitou úroveˇn abstrakce, aby poˇcet krok˚u k dosaˇzen´ı c´ıle nebyl pˇr´ıliˇs velký a bylo moˇzné nalézt ˇreˇsen´ı.

Proces hledán´ı posloupnosti akc´ı vedouc´ıch k c´ıli nen´ı pˇr´ımý, existuje mnoho stav˚u, kde agent nev´ı jak si vede, a proto je jeho úkolem vyzkouˇset r˚uzné moˇzné akce, které z daného stavu vedou, aˇz do chv´ıle, kdy se dostane do stavu známého. Potom pˇrehodnot´ı nalezené cesty a vybere tu nejlepˇs´ı. Vyhledávac´ı algoritmus obdrˇz´ı problém na vstupu a jako výstup vrac´ı ˇreˇsen´ı ve formˇe posloupnosti akc´ı. Jakmile je ˇreˇsen´ı nalezeno, nastává fáze proveden´ı tˇechto akc´ı. Po formulaci c´ıle a ˇreˇseného problému, agent tedy zavolá vyhledávac´ı algo- rtimus, a poté provád´ı akce podle navráceného ˇreˇsen´ı, vˇetˇsinou to znamená, ˇze provede prvn´ı akci z posloupnosti a odstran´ı ji. Takto pokraˇcuje dokud jsou ve frontˇe dalˇs´ı akce. To samozˇrejmˇe znamená, ˇze prostˇred´ı mus´ı splˇnovat urˇcitá kritéria. Pˇredevˇs´ım mus´ı být stat- ické, ponˇevadˇz agent pˇri hledán´ı cesty ani pˇri provádˇen´ı akc´ı jiˇz nebere ohled na prostˇred´ı.

Jelikoˇz se pˇredpokládá, ˇze poˇcáteˇcn´ı stav je znám, prostˇred´ı mus´ı být pozorovatelné. Pˇri hledán´ı je nutné vyˇc´ıslit vˇsechny stavy, prostˇred´ı tedy mus´ı být diskrétn´ı. Nejd˚uleˇzitˇejˇs´ım faktorem je, ˇze prostˇred´ı mus´ı být deterministické, protoˇze agent pˇri provádˇen´ı akc´ı ignoruje vjemy, nem˚uˇze tedy zpracovávat nepˇredv´ıdané události.

Správná definice problému se skládá ze ˇctyˇr ˇcást´ı. Prvn´ı je poˇcáteˇcn´ı stav, tj. stav prostˇred´ı, ve kterém agent zaˇc´ıná ˇreˇsit problém. Dalˇs´ı je popis moˇzných agentových akc´ı, který je nejˇcastˇeji vyjádˇren funkc´ı následovn´ıka. Tato funkce vrac´ı pro kaˇzdý stav mnoˇzinu

(17)

dvojic akce a následovn´ıka, kde kaˇzdá akce je jedna z pˇr´ıpustných akc´ı v tomto stavu a následovn´ık je stav, do kterého se prostˇred´ı dostane po proveden´ı akce. Poˇcáteˇcn´ı stav a funkce následovn´ıka dohromady definuj´ı stavový prostor problému, mnoˇzinu vˇsech stav˚u dosaˇzitelných z poˇcáteˇcn´ıho stavu. Tˇret´ı ˇcást definice problému je c´ılový test, který urˇc´ı, zda daný stav je c´ılovým stavem. Nˇekdy je c´ılových stav˚u v´ıce a tento test jednoduˇse urˇc´ı, jestli se prostˇred´ı nacház´ı v jednom z nich. Ne vˇzdy je c´ıl vyjádˇren jako vyjmenovaná mnoˇzina stav˚u, napˇr´ıklad v ˇsachové partii nastane c´ılový stav vˇzdy kdyˇz král je ohroˇzen a nemá kam se schovat. Posledn´ı ˇcást´ı definice je funkce urˇcuj´ıc´ı cenu cesty. ˇReˇs´ıc´ı agent má obvykle funkci ceny zaloˇzenou na jeho vlastn´ım ohodnocen´ı. M˚uˇzeme pˇredpokládat, ˇze cena cesty je souˇctem cen jednotlivých krok˚u, a funkci ceny kroku m˚uˇzeme definovat jako c(x,a,y), která vrac´ı cenu proveden´ı akcea ze stavux do stavuy. Tyto ˇcásti definice m˚uˇzeme uloˇzit do jedné datove struktury a pˇredat je jako parametr algoritmu ˇreˇs´ıc´ımu daný problém.

Výsledkem je pak cesta z poˇcáteˇcn´ıho do c´ılového stavu. Kvalita ˇreˇsen´ı je mˇeˇrena pomoc´ı funkce ceny cesty a ˇreˇsen´ı s nejniˇzˇs´ı cenou je ˇreˇsen´ım optimáln´ım.

3.2 Hled´ an´ı ˇ reˇ sen´ı

Jakmile máme problém formulován, potˇrebujeme jej vyˇreˇsit. To je provedeno prohledán´ım stavového prostoru. Následuj´ıc´ı zp˚usoby hledán´ı vyuˇz´ıvaj´ı vyhledávac´ı strom nebo vyh- ledávac´ı graf, pokud je moˇzné dosáhnout stejného stavu nˇekolika cestami. Koˇrenem tohoto stromu je uzel odpov´ıdaj´ıc´ı poˇcáteˇcn´ımu stavu. Prvn´ım krokem je kontrola, zda nejde o c´ılový stav, protoˇze je nutné oˇsetˇrit i takové pˇr´ıpady. V naprosté vˇetˇsinˇe pˇr´ıpad˚u tomu tak nen´ı, a proto se pokraˇcuje rozˇs´ıˇren´ım aktuáln´ıho stavu aplikován´ım funkce následn´ıka na tento stav a t´ım vygenerován´ım nové mnoˇziny stav˚u. T´ımto jsme z´ıskali nˇekolik cest a mus´ıme zvolit, kterou cestou se budeme nadále ub´ırat. Tato volba závis´ı na metodˇe hledán´ı, jednotlivé zp˚usoby budou popsány dále. Takto by se dal popsat obecný algoritmus pro prohledáván´ı stavového prostoru. Jednotlivé uzly vyhledávac´ıho stromu uchovávaj´ı tyto informace: stav, jeden z mnoˇziny stavového prostoru problému, rodiˇcovský uzel, ze kterého byl tento uzel vygenerován, akce, která byla aplikována na rodiˇce a vedla k vytvoˇren´ı tohoto uzlu, cena cesty z poˇcáteˇcn´ıho stavu aˇz do tohoto uzlu a hloubka zanoˇren´ı, tj. poˇcet krok˚u z poˇcáteˇcn´ıho stavu. Výsledkem algoritmu pro ˇreˇsen´ı problém˚u je bud’ ˇreˇsen´ı nebo chyba, ˇze ˇreˇsen´ı nebylo nalezeno, nˇekteré algoritmy mohou také skonˇcit v nekoneˇcné smyˇcˇce a v˚ubec nevrátit výsledek. Hodnocen´ı algoritmu lze rozdˇelit do ˇctyˇr kritéri´ı: úplnost, ˇcili jestli algoritmus najde ˇreˇsen´ı pokud nˇejaké existuje, optimálnost, jestli najde nejlepˇs´ı ˇreˇsen´ı, ˇcasová sloˇzitost a pamˇet’ová nároˇcnost.

3.3 Neinformovan´ e metody hled´ an´ı

Neinformované metody, nebo také slepé metody hledán´ı, nemaj´ı o stavech ˇzádné dalˇs´ı informace, kromˇe zadán´ı problému. Jediné co vˇed´ı o kaˇzdém stavu je to, zda je ˇci nen´ı c´ılový.

3.3.1 Breadth-first search

Breadth-first search (BFS), neboli slepé prohledáván´ı do ˇs´ıˇrky, je jednoduchá metoda, pracuj´ıc´ı na principu expandován´ı stromu postupnˇe po úrovn´ıch, ˇcili vˇsechny uzly v dané hloubce jsou expandovány dˇr´ıve, neˇz uzly dalˇs´ı úrovnˇe. Je zˇrejmé, ˇze tato metoda je úplná, optimáln´ı pouze v pˇr´ıpadˇe, ˇze s nar˚ustaj´ıc´ı hloubkou se nesniˇzuje cena kroku (napˇr´ıklad pˇri

(18)

stejných cenách krok˚u), avˇsak je dost nároˇcná na pamˇet nebot’ mus´ı uchovávat mnoˇzinu uzl˚u, ketré je tˇreba expandovat.

3.3.2 Uniform-cost search

Uniform-cost search (UCS)je narozd´ıl od pˇredchoz´ı metody optimáln´ı vˇzdy, protoˇze neex- panduje uzly v poˇrad´ı podle jejich hloubky, nýbrˇz podle nejniˇzˇs´ı ceny cesty. Z toho vyplývá, ˇ

ze pˇr´ıpadˇe stejn´e ceny kroku u vˇsech krok˚u je tato metoda identick´a s pˇredchoz´ı metodou.

V pˇr´ıpadˇe, ˇze by nˇejaký krok mˇel nulovou cenu, skonˇcil by tento algoritmus v nekoneˇcné smyˇcˇce. Nevýhoda této metody je, ˇze ˇcasto nejdˇr´ıve expanduje mnoho uzl˚u s malými ce- nami pˇred prozkoumán´ım ostatn´ıch cest s vˇetˇs´ı cenou, které mohou vést k ˇreˇsen´ı, coˇz se odráˇz´ı ve velké pamˇet’ové nároˇcnosti.

3.3.3 Depth-first search

Depth-first search (DFS), neboli slepé prohledáván´ı do hloubky, vˇzdy expanduje nejhloubˇeji postavený uzel tak dlouho, dokud takový uzel nemá ˇzádného následn´ıka. Potom se metoda vrát´ı zpˇet ke druhému nejhlubˇs´ımu uzlu. Z toho vyplývaj´ı nevýhody této metody, m˚uˇze expandovat pˇr´ıliˇs hluboko, nebo i nekoneˇcnˇe hluboko, i kdyˇz ˇreˇsen´ı se nalézá mnohem výˇse ve stromu v jiné vˇetvi. Metoda tedy nen´ı úplná ani optimáln´ı. Má vˇsak velmi skromné pamˇet’ové nároky. Jej´ı variantaDepth-limited search (DLS) je zaloˇzena na stejném pricipu, akorát obshauje omezen´ı pro expanzi jen do urˇcité hloubky. To znamená, ˇze pokud je ˇreˇsen´ı n´ıˇze, v˚ubec jej nenalezne. Obvykle se vˇsak dá urˇcit kolik krok˚u je maximálnˇe potˇreba, a zamez´ı se t´ım moˇznost nekoneˇcného expandován´ı nˇekteré vˇetve vyhledávac´ıho stromu.

3.3.4 Iterative deepening depth-first search

Iterative deepening depth-first search (IDS) je metoda postupného zanoˇrován´ı zaloˇzena na slepém prohledáván´ı do hloubky. Pracuje na principu postupného zvyˇsován´ı limitu zanoˇren´ı a uˇzit´ıDLS, kombinuje výhody slepého prohledáván´ı do hloubky i do ˇs´ıˇrky, nen´ı pˇr´ıliˇs pamˇet’ovˇe nároˇcná, je úplná a za stejných podm´ınek jako BFS je i optimáln´ı. Vzhledem k tomu, ˇze stále postupnˇe volá DLS pro stále vˇetˇs´ı limit hloubky zanoˇren´ı, zdá se, ˇze nen´ı pˇr´ıliˇs efektivn´ı z d˚uvodu neustálého opakován´ı expanze vyˇsˇs´ıch uzl˚u, pravda je ovˇsem taková, ˇze ˇcasová sloˇzitostIDS je menˇs´ı neˇzBFS, je tedy mnohem rychlejˇs´ı. Obecnˇe plat´ı, ˇ

ze tato metoda je pro úlohy s velkým stavovým prostorem a neznámou hloubkou ˇreˇsen´ı ze vˇsech neinformovaných metod nejlepˇs´ı volbou.

Vˇsechny tyto metody mohou pˇri hledán´ı narazit na významnou komplikaci - plýtván´ı ˇ

casu nalézán´ım jiˇz známých stav˚u. V nˇekterých problémech tato moˇznost nikdy nenastane, ale v ˇradˇe pˇr´ıpad˚u jsou akce vratné, jako napˇr´ıklad pˇri hledán´ı trasy. Stavové stromy jsou v tˇechto pˇr´ıpadech nekoneˇcné, ale pokud budeme ignorovat jiˇz jednou expandované stavy, m˚uˇzeme je zmˇenˇsit na koneˇcnou velikost. To ovˇsem znamená uchovat vˇsechny jiˇz navˇst´ıvené stavy v pamˇeti, abychom je mohli porovnat s aktuáln´ım stavem prostˇred´ı.

3.4 Informovan´ e metody hled´ an´ı

Narozd´ıl od slepých metod prohledáván´ı stavového prostoru, informované metody pouˇz´ıvaj´ı znalosti, které nejsou v definici problému, a mohou nalézt ˇreˇsen´ı mnohem efektivnˇeji.

(19)

3.4.1 Best-first search

Best-first search (BestFS) je obecná metoda, která vyb´ırá uzel pro expanzi na základˇe evaluaˇcn´ı funkcef(n). Obvykle je vybrán uzel s nejniˇzˇs´ı hodnotou, protoˇze evaluaˇcn´ı funkce vyjadˇruje vzdálenost od c´ıle. Aˇckoli je v názvu slovo best, nevyb´ırá vˇzdy ten nejlepˇs´ı uzel, pokud by to tak bylo, nebylo by to hledán´ı, ale pˇr´ımá cesta k c´ıli. Ovˇsem ne vˇzdy je evaluaˇcn´ı funkce pˇresná, a tak je vˇzdy vybrán ten uzel, o kterém se pˇredpokládá, ˇze je nejlepˇs´ı. Základem metody je heuristická funkce h(n), která vrac´ı onu pˇredpokládanou vzdálenost od c´ıle. Pokud jen c´ılový stav, pakh(n) = 0.

3.4.2 Greedy best-first search

Prvn´ı variantou této metody je metodagreedy best-first search. Ta expanduje uzly pouze na základˇe jejich vzdálenosti od c´ıle, ohodnocuje tedy uzly pouze pomoc´ı heuristické funkce, ˇ

cili f(n) = h(n). Aˇckoli tato metoda ve vˇetˇsinˇe pˇr´ıpad˚u pouˇz´ıvá pouze minimáln´ı velikost vyhledávac´ıho stromu, nen´ı optimáln´ı ani úplná.

3.4.3 A* search

Nejznámˇejˇs´ı variantouBestFS metodou jeA* search, která ohodnocuje uzly kombinac´ıg(n), ceny cesty k uzlu, sh(n), pˇredpokládané ceny cesty z uzlu do c´ıle. Znamená to, ˇzef(n)= g(n) + h(n)a evaluaˇcn´ı funkce vrac´ı pˇredpokládanou cenu ˇreˇsen´ı procházej´ıc´ıho uzlemn. Pokud heuristická funkce nikdy nepˇrecen´ı cestu k c´ıli, nalezne tato metoda vˇzdy optimáln´ı ˇreˇsen´ı.

Jej´ı ˇcasová sloˇzitost nen´ı pˇr´ıliˇs velká, ale klade velké nároky na pamˇet nebot’ si uchovává vˇsechny uzly, nehod´ı se proto pro ˇreˇsen´ı problém˚u pˇr´ıliˇs velkých rozmˇer˚u.

3.5 Hran´ı her

V minulé kapitole byla zm´ınˇena multiagentn´ı prostˇred´ı, ve kterých kaˇzdý agent mus´ı zváˇzit akce ostatn´ıch agent˚u a jak tyto akce ovlivn´ı jeho hodnocen´ı. V oblasti hran´ı her se pˇreváˇznˇe jedná o deterministické, plnˇe pozorovatelné, konkurenˇcn´ı prostˇred´ı, kde se dva agenti stˇr´ıdaj´ı ve svých akc´ıch, a výsledné ohodnocen´ı jednoho je opaˇcné k hodnocen´ı druhého agenta.

Napˇr´ıklad, pokud prvn´ı hráˇc vyhraje partii ˇsachu, druhý nutnˇe prohrál. Hru jako takovou lze formálnˇe definovat jako druh problému s následuj´ıc´ımi prvky: poˇcáteˇcn´ı stav, který udává stav hrac´ı desky a který hráˇc je na tahu; funkci následn´ıka, která vrac´ı seznam pár˚u [tah, stav], kde kaˇzdý pár vyjadˇruje jeden z moˇzných tah˚u a výsledný stav; test na konec hry a hodnot´ıc´ı funkce, která vrac´ı ˇc´ıselné vyjádˇren´ı koncového stavu. V ˇsachu napˇr´ıklad tato funkce pro výhru, prohru nebo rem´ızu vrac´ı hodnoty +1, -1 nebo 0. V kla- sickém problému zaloˇzeném na prohledáván´ı stavového prostoru by optimáln´ım ˇreˇsen´ım byla posloupnost tah˚u vedouc´ıch k c´ılovému stavu, nicménˇe pˇri hˇre má k tomu co ˇr´ıct i druhý hráˇc. Hráˇc A tedy mus´ı naj´ıt strategii, která urˇcuje jeho tah z poˇcáteˇcn´ıho stavu, pak tahy ze vˇsech stav˚u, které mohly vzniknout tahem hráˇce B, dále tahy ze vˇsech stav˚u, které mohly vzniknout tahem B na kaˇzdý moˇzný pˇredchoz´ı tah, a tak dále. Jinými slovy, optimáln´ı strategie vede k výsledk˚um ne horˇs´ım neˇz jakákoli jiná strategie, pˇri které hráˇc hraje proti dokonalému protivn´ıkovi.

(20)

3.5.1 Minimax

Metoda minimax vyb´ırá nejlepˇs´ı tah podle hern´ıho stromu, vytvoˇreného výˇse zm´ınˇeným hledán´ım vˇsech moˇzných tah˚u hráˇce i soupeˇre. Listy tohoto stromu jsou c´ılové stavy a kaˇzdý je ohodnocen hodnot´ıc´ı funkc´ı. Potom je kaˇzdý uzel stromu ohodnocen podle pravidla, ˇze pokud se jedná o uzel hráˇce A, je mu pˇriˇrazena nejvyˇsˇs´ı hodnota z ohodnocen´ı následných uzl˚u, v pˇr´ıpadˇe uzlu soupeˇre B je to hodnota minimáln´ı, ponˇevadˇz plat´ı, ˇze ˇc´ım vyˇsˇs´ı ohodnocen´ı, t´ım l´ıp pro A, a naopak, ˇc´ım niˇzˇs´ı, t´ım l´ıp je na tom B. T´ım se ohodnocen´ı dostane aˇz ke koˇrenu stromu a podle nˇej hráˇc rozhodne, který tah provede. Jelikoˇz je tˇreba vytvoˇrit strom pro celou hru, je pro jiné neˇz ty nejjednoduˇsˇs´ı hry obrovský a tato metoda prakticky nepouˇzitelná, nicménˇe slouˇz´ı jako analytický základ pro pouˇzitelnˇejˇs´ı algoritmy.

3.5.2 Alpha-beta pruning

Metoda alfa-beta ˇrezu dokáˇze eliminovat nˇekteré vˇetve stromu a je tedy podstatnˇe efek- tivnˇejˇs´ı neˇz pˇredchoz´ı algoritmus. Vycház´ı pˇr´ımo z nˇej, nicménˇe vˇetve, které nemohou ovlivnit ohodnocen´ı uzlu, jsou z výpoˇctu vypuˇstˇeny. Pokud ve stromu existuje uzelntakový, ˇ

ze hráˇc m˚uˇze táhnout na tento uzel, a zároveˇn existuje lepˇs´ı volba m bud’ u pˇredka uzlu n nebo kdekoli výˇse ve stromu, pak uzlu n nebude pˇri hˇre nikdy dosáhnuto. Metoda z´ıskala jméno podle dvou promˇenných,alfa a beta, které uchováváj´ı hodnoty doposud nalezených nejlepˇs´ıch hodnot, alfa obsahuje pro hráˇce A nejvyˇsˇs´ı hodnotu a beta nejlepˇs´ı pro hráˇce B, ˇcili nejniˇzˇs´ı. Metoda postupnˇe upravuje hodnoty alfa a beta jak procház´ı stromem a odˇreˇze zbývaj´ıc´ı vˇetve uzlu pokud zjist´ı, ˇze ohodnocen´ı aktuáln´ıho uzlu je horˇs´ı, neˇz aktuáln´ı alfa resp. beta pro hráˇce A resp. B. Efektivita metody je znaˇcnˇe závislá na poˇrad´ı prohledáván´ı jednotlivých uzl˚u. Pokud jsou nejdˇr´ıve vyhodnoceny cesty, které se zdaj´ı být dobrým tahem, m˚uˇze tato metoda ve srovnán´ı s minimaxem za stejný ˇcas dosáhnout aˇz dvojnásobné hloubky stromu.

3.6 Implementace

3.6.1 Tˇr´ıda Problem

Základn´ı tˇr´ıdou pro ˇreˇsen´ı problém˚u pomoc´ı prohledáván´ı stavového prostoru je Problem.

Obsahuje instanˇcn´ı promˇenné initialState, ve které je uloˇzen poˇcáteˇcn´ı stav, a goal, ve které je uloˇzen stav c´ılový. Problém je vyˇreˇsen, pokud metoda goalTest vrac´ıtrue, coˇz je pˇri shodnosti pˇredávaného a c´ılového stavu. Pokud nelze pˇresnˇe definovat c´ılový stav je moˇzné tuto metodu pˇret´ıˇzit v potomku tˇr´ıdy. Tˇr´ıda sama o sobˇe je v podstatˇe abstraktn´ı, protoˇze nemá definovanou metodu successors, která vrac´ı následné moˇzné stavy ve dvojici s akc´ı. Tuto metodu si mus´ı kaˇzdý konkrétn´ı problém, potomek této tˇr´ıdy, pˇredefinovat.

Reˇˇ sen´ı problému se spouˇst´ı volán´ım metodysolve. Tato tˇr´ıda rovnˇeˇz obsahuje prohledávac´ı algoritmy. Ty jsou implementovány pomoc´ı kolekce uzl˚u, instanc´ı tˇr´ıdy Node, ke které je pˇristupováno jako ke frontˇe, a kaˇzdý algoritmus pˇredepisuje v jakém poˇrad´ı je k uzl˚um ve frontˇe pˇristupováno. Tˇr´ıda zná následuj´ıc´ı algoritmy.

Slepé prohledáván´ı do ˇs´ıˇrky provád´ı metoda breadthFirstSearch, která pouˇz´ıvá frontu typu FIFO. Stejný algoritmus, který ale nav´ıc eliminuje návraty do pˇredchoz´ıho stavu, je napsán pod názvem noReturnsBreadthFirstSearch. Test na opakován´ı pˇredchoz´ıho stavu zajiˇst’uje tˇr´ıda Node metodou isReturning. Pro vynechán´ı nejen opakuj´ıc´ıch se stav˚u, ale

´

uplnˇe vˇsech duplicitn´ıch stav˚u ve vyhledávac´ım stromu slouˇz´ı metodanoDuplicatesBreadth- FirstSearch. Slepé prohledáván´ı do hloubky zajiˇst’uje metodadepthFirstSearch, ta vyuˇz´ıvá

(21)

fronty s uzly jako zásobn´ıku - LIFO. Jelikoˇz se m˚uˇze snadno zacyklit, existuje jej´ı varianta s eliminac´ı vˇsech cykl˚u, která podobnˇe jako v pˇredchoz´ım pˇr´ıpadˇe vyuˇz´ıvá funkˇcnosti tˇr´ıdy Node, ale metodyisLooping, která kontroluje nejen pˇredchoz´ı na stav, ale vˇsechny pˇredchoz´ı stavy a t´ım bezpeˇcnˇe detekuje jakýkoli cyklus. Tato metoda má název noCyclesDepthFirst- Search. Jako základ informovaných algoritm˚u vyhledáván´ı je metodabestFirstSearch, která pˇrij´ımá jako parametr blok s evaluaˇcn´ı funkc´ı. AˇckoliuniformCostSearch patˇr´ı mezi nein- formované algorimy, vyuˇz´ıvábestFirstSearch tak, ˇze j´ı pˇredává funkci vracej´ıc´ı cenu kroku.

MetodagreedySearch vyb´ırá uzly na základˇe pˇredpokládané ceny cesty k c´ıli, pˇredává tedy bestFirstSearch jako parametr heuristickou funkci. AlgoritmusaStarSearch je na bázibest- FirstSearch, kde evaluaˇcn´ı funkce sˇc´ıtá aktuáln´ı cenu cesty a pˇredpokládanou cenu do c´ıle.

3.6.2 Tˇr´ıda Node

Jednotlivé uzly jsou základn´ımi prvky pro uchován´ı stavového prostoru a jeho procházen´ı.

Kaˇzdý uzel pˇredstavuje stav a má metoduexpand, která vygeneruje uzly, ke kterým lze doj´ıt z jeho stavu. Uchovává rovnˇeˇz cenu aktuáln´ı cesty, pˇrepokládanou cenu do c´ıle, aktuáln´ı hloubku zanoˇren´ı a odkazy na následuj´ıc´ı uzly. Instance této tˇr´ıdy tvoˇr´ı vyhledávac´ı strom.

3.6.3 Tˇr´ıda Game

Game je tˇr´ıda urˇcená pro popis a nalezen´ı ˇreˇsen´ı pˇri hran´ı her. Podobnˇe jako pro problém, pro konkrétn´ı hru je nutné vytvoˇrit potomka a nadefinovat metody makeMove,legalMoves aisGameOver. Prvn´ı z nich urˇcuje jak se urˇcitým tahem zmˇen´ı stav hry, druhá vrac´ı kolekci povolených tah˚u pro daný stav a tˇret´ı testuje zda existuje v´ıtˇez nebo je rem´ıza. S touto tˇr´ıdou je pevnˇe svázána tˇr´ıda GameState urˇcuj´ıc´ı stav hry. Sama tˇr´ıda Game obsahuje implementaci nˇekolika algoritm˚u pro hran´ı her. Následuj´ı názvy jejich metod.

Metoda minimaxDecision je základn´ı algoritmus, který prohledává postupnˇe vˇsechny stavy dokud nedojde k c´ıli a podle tˇechto informac´ı vybere nejlepˇs´ı tah. Aˇckoli dojde vˇzdy k nejlepˇs´ımu výsledku, vzhledem k jeho neefektivnosti je pro netriviáln´ı hry nepouˇzitelný.

Metoda minimaxCutoffDecision prohledává stavový prostor podobnˇe jako minimax ale pouze do n úrovn´ı, poté na koncové stavy aplikuje evaluaˇcn´ı funkci a na základˇe tˇechto informac´ı rozhodne, jak táhnout. Podobnˇe jako omezený minimax prohledává metoda al- phaBetaDecision jen do urˇcené úrovnˇe a vrát´ı také stejný výsledek, ale prohledá ménˇe uzl˚u, je tud´ıˇz efektivnˇejˇs´ı. Náhodný výbˇer z mnoˇziny moˇzných tah˚u provád´ı metodapickRandom- Move. Aby mohl do hry zasahovat i uˇzivatel, existuje metoda askGameUser, která vyzve uˇzivatele, aby vybral jeden z mnoˇziny moˇzných tah˚u.

3.6.4 Tˇr´ıda GameState

Tˇr´ıda GameState je urˇcena pro uloˇzen´ı aktuáln´ıho stavu hry. Ve svých instanˇcn´ıch promˇenných uchovává hrac´ı desku, seznam hráˇc˚u, jejich skóre a tah, který tento stav vytvoˇril. Seznam hráˇc˚u obsahuje na prvn´ım m´ıstˇe vˇzdy aktuáln´ıho hráˇce, tud´ıˇz postupnˇe rotuje doleva jak se hráˇci stˇr´ıdaj´ı.

3.6.5 Prostˇred´ı

ProblemSolvingEnvironment je tˇr´ıda urˇcená k ˇreˇsen´ı problém˚u. Kaˇzdý problém má metodu asEnvironment, která vytvoˇr´ı instanci tohoto prostˇred´ı. ProblemSolvingAgent je urˇcen pro práci v prostˇred´ı pro ˇreˇsen´ı problém˚u, vlastn´ı promˇennou algorithm a pˇri inicializaci

(22)

prostˇred´ı je jeho program definován tak, aby nejprve nalezl ˇreˇsen´ı daného problému a poté vykonával krok po kroku aˇz do c´ılového stavu. Tˇr´ıdaGameEnvironment je vytvoˇrena jako prostˇred´ı pro hran´ı her. Kaˇzdá hra má metoduasEnvironment, která vytvoˇr´ı instanci tohoto prostˇred´ı. GameAgent je urˇcen pro hran´ı her, vlastn´ı promˇennou algorithm a pˇret´ıˇzenou metodurunProgram, která je upravena pro komunikaci s hrou a pˇr´ımé volán´ı algoritmu pro výpoˇcet tahu podle agenta.HumanGameAgent a RandomGameAgent jsou tˇr´ıdy odvozené odGameAgent, pouˇz´ıvaj´ıc´ı algoritmus pro výbˇer tahu podle volby uˇzivatele resp. náhodné volby.

3.7 Pˇ r´ıklady

3.7.1 Mision´aˇri a kanibalov´e

Pro ukázku ˇreˇsen´ı problém˚u byla zvolena klasická úloha, ve které je nutné pˇrepravit z jedno bˇrehu na druhý 3 misionáˇre a 3 kanibaly, pˇriˇcemˇz lod’ka unese 2 osoby a na ˇzádném bˇrehu nesm´ı kanibalové nikdy pˇreˇc´ıslit misionáˇre. Pro tento problém byla vytvoˇrena tˇr´ıda Can- nibalProblem, která je potomkem tˇr´ıdy Problem. Pro jednoduˇsˇs´ı reprezentaci stav˚u byla vytvoˇrena tˇr´ıdaCannibalState, která popisuje poˇcet jednotlivých osob na obou bˇrez´ıch.

3.7.2 Piˇskvorky

Jako ukázka hran´ı her byly zvoleny piˇskvorky (Tic-Tac-Toe). Tˇr´ıda TTTGame definuje potˇrebné funkce pro zjiˇstˇen´ı moˇzných tah˚u, vykonán´ı tahu a testu na konec hry, rovnˇeˇz evaluaˇcn´ı funkci pro algoritmus alfa-beta. AlphaBetaTTTAgent vyuˇz´ıvá tohoto algoritmu pro výbˇer tahu.

3.7.3 D´ama

Dalˇs´ı ukázkou hry vyuˇz´ıvaj´ıc´ı tento kód je Dáma (Checkers). Hra vyuˇz´ıvá alfa-beta ˇrezu a je schopná hledat aˇz 10 p˚ultah˚u dopˇredu bez výrazného zpomalen´ı hry. Kaˇzdý stav ˇsachovnice je ohodnocen podle poˇctu a polohy b´ılých a ˇcerných kamen˚u a dam, nebot’ hern´ı strom nen´ı dopoˇc´ıtán aˇz do konce hry a je tedy nezbytné listy omezeného stromu nˇejak ohodnotit. Hra obsahuje pomˇernˇe vydaˇrené grafické prostˇred´ı, inspirované ˇsachy, které jsou ve Squeaku standardnˇe. Základn´ı funkˇcnost zajiˇst’uje tˇr´ıdaCheckers, hra se spouˇst´ı proveden´ım výrazu Checkers new.

(23)

Kapitola 4

Logika

Tato kapitola se zabývá reprezentac´ı znalost´ı a logickým myˇslen´ım, coˇz jsou nezbytné souˇcásti umˇelé inteligence. Agent, který vyuˇz´ıvá znalost´ı, je schopen dosáhnout svého c´ıle i v komplexn´ıch prostˇred´ıch. ˇReˇs´ıc´ı agenti sice znaj´ı výsledek svých akc´ı a d´ıky nˇemu hledaj´ı ˇreˇsen´ı, ovˇsem takové znalosti jsou velmi specifické. ˇSachový program dokáˇze spoˇc´ıtat moˇzné tahy krále, nicménˇe nemá ani ponˇet´ı o tom, ˇze ˇzádná figurka nem˚uˇze být na dvou m´ıstech zároveˇn. Oproti tomulogický agent m˚uˇze tˇeˇzit ze svých znalost´ı mnohem obecnˇeji. Znalosti také hraj´ı velkou roli v ˇcásteˇcnˇe pozorovatelných prostˇred´ıch, kde je agent m˚uˇze kombinovat s aktuáln´ımi vjemy a odvodit tak nˇekteré skryté aspekty souˇcasného stavu okol´ı pˇred volbou své akce.

4.1 Uvod do logiky ´

Základn´ı souˇcást´ı logického agenta je báze znalost´ı, coˇz je mnoˇzina vˇet, které jsou vyjádˇreny v jazyce pro reprezentaci znalost´ı a obsahuj´ı nˇejaké tvrzen´ı o okoln´ım svˇetˇe. Jelikoˇz potˇrebujeme zp˚usob, jak do báze znalost´ı pˇridávat vˇety a jak z n´ı zjiˇst’ovat, co je známo, existuj´ı metody tell a ask. Obˇe tyto metody mohou vyuˇz´ıt odvozen´ı pro vytvoˇren´ı nových vˇet z jiˇz existuj´ıc´ıch v bázi znalost´ı. Logický agent mus´ı pˇri odvozován´ı dodrˇzet pravidlo, ˇ

ze jakákoli odpovˇed’ na otázku mus´ı logicky vyplývat z toho, co bylo do báze znalost´ı vloˇzeno dˇr´ıve. Kdykoli agent odvod´ı závˇer z dostupných informac´ı, je zaruˇceno, ˇze tento závˇer je správný, pokud jsou správné dostupné infomace. To je stˇeˇzejn´ı vlastnost logického myˇslen´ı. Obecný program logického agenta je zaloˇzen na následuj´ıc´ım principu. Jako kaˇzdý jiný agent pˇrij´ımá vjem na vstupu a jeho výstupem je akce. Vjem je nejprve uloˇzen do báze znalost´ı metodoutell. Následnˇe je proveden dotaz do báze (ask) a po vyhodnocen´ı dotazu je navrácena akce. Tato akce je pˇred proveden´ım uloˇzena do báze znalost´ı, jelikoˇz je nutné zaz- namenat, ˇze tato akce skuteˇcnˇe byla provedena. Z uvedeného postupu vyplývá, ˇze je moˇzné vytvoˇrit agenta pouze vloˇzen´ım vˇet do báze znalost´ı, coˇz pˇri vhodném reprezentaˇcn´ım jazyce m˚uˇze velmi zjednoduˇsit návrh systému. Takový pˇr´ıstup se nazývá deklarativn´ı. Oproti tomu proceduráln´ı pˇr´ıstup pˇr´ımo ukládá poˇzadované chován´ı agenta jako kód programu, coˇz m˚uˇze podstatnˇe zlepˇsit efektivitu systému. V souˇcasné dobˇe je zˇrejmé, ˇze návrh úspˇeˇsného agenta mus´ı kombinovat oba tyto pˇr´ıstupy.

Jak jiˇz bylo ˇreˇceno, báze znalost´ı je mnoˇzina vˇet. Kaˇzdá vˇeta mus´ı být ve správném tvaru, který je urˇcen syntax´ı reprezentaˇcn´ıho jazyka. Logika také definuje sématiku jazyka, tj. význam kaˇzdé vˇety. Podle definice, sémantika jazyka definuje pravdivost kaˇzdé vˇety pro kaˇzdé moˇzné prostˇred´ı. Napˇr´ıklad v aritmetice je vˇeta x+y= 4 pravdivá v prostˇred´ı, kde

(24)

x je 2 a y je 2, ale nen´ı pravdivá v prostˇred´ı s x= 1 a y = 1. To znamená, ˇze kaˇzdá vˇeta v logice mus´ı být pro jakékoli prostˇred´ı pravdivá ˇci nepravdivá. Logické myˇslen´ı agenta je zaloˇzeno na logických d˚usledc´ıch. Z vˇety A logicky vyplývá vˇeta B, coˇz znamená, ˇze pro kaˇzdý model (prostˇred´ı), ve kterém je A pravdivá, je B rovnˇeˇz pravdivá. Nejjednoduˇsˇs´ım algoritmem pro odvozován´ı je kontrola model˚u, coˇz je vlastnˇe vyjádˇren´ı vˇsech moˇzných model˚u a porovnán´ı, zda vˇetaAje pravdivá ve vˇsech modelech, ve kterých je pravdivá báze znalost´ı. Odvozovac´ı algoritmus je bezesporný (sound), jestliˇze odvozené vˇety jsou vˇzdy logickým d˚usledkem jiˇz známé vˇety, a úplný (complete), pokud dokáˇze odvodit kaˇzdou logicky vyplývaj´ıc´ı vˇetu z jiˇz známých vˇet v bázi znalost´ı.

4.2 V´ yrokov´ a logika

4.2.1 Jazyk v´yrokov´e logiky

Výroková logika je velmi jednoduchá, poslouˇz´ı tedy dobˇre k vysvˇetlen´ı základn´ıch prvk˚u této oblasti. Jako prvn´ı bude popsán jazyk výrokové logiky.

Syntaxe tohoto jazyka definuje správný tvar vˇet - formul´ı výrokové logiky. Nejmenˇs´ı element jazyka je atomická formule (atom), coˇz je výrokový symbol, který je bud’ pravdivý nebo nepravdivý. Existuj´ı dva symboly se zvláˇstn´ım významem, vˇzdy pravdivý - True a vˇzdy nepravdivý - False. Formule se skládaj´ı z atomických formul´ı a logických spojek (negace, konjunkce, disjunkce, implikace a ekvivalence).

S´emantika jazyka definuje pravidla pro urˇcen´ı pravdivosti formule pro dan´y model, tj.

nastav´ı hodnotu pravdivosti pro kaˇzdý výrokový symbol. Hodnota prvotn´ıch formul´ı je dána modelem, jednoduché formule jsou vyhodnoceny podle pravdivostn´ı tabulky a komplexn´ı formule jsou pomoc´ı rekurze rozloˇzeny na jednoduché a vyhodnoceny podle pˇredchoz´ıch pravidel.

P Q ¬P P∧Q P∨Q P ⇒Q P ⇔Q

f alse f alse true f alse f alse true true f alse true true f alse true true f alse

true f alse f alse f alse true f alse f alse true true f alse true true true true

Tabulka 4.1: Pravdivostn´ı tabulka

Báze znalost´ı obsahuje formule, které urˇcuj´ı pravdivost báze pro daný model. Jelikoˇz je nutné, aby vˇsechny formule byly splnˇeny, m˚uˇzeme bázi brát jako jedinou formuli, která je konjunkc´ı formul´ı v bázi obsaˇzených.

4.2.2 Odvozov´an´ı

C´ılem odvozen´ı je zjistit, zda daná formule logicky vyplývá z báze znalost´ı. Nejjednoduˇsˇs´ı algoritmus vycház´ı pˇr´ımo z principu logického d˚usledku, vyˇc´ıslen´ı vˇsech moˇzných model˚u a následná kontrola, jestli daná formule je platná v kaˇzdém modelu, ve kterém je platná báze znalost´ı. Ve výrokové logice lze model vyjádˇrit jako pˇriˇrazen´ı hodnoty pravda nebo nepravda pro kaˇzdý výrokový symbol vyskytuj´ıc´ı se v bázi znalost´ı. Algoritmus pro kontrolu model˚u tedy rekurzivnˇe vyˇc´ısl´ı vˇsechna moˇzná pˇriˇrazen´ı hodnot k promˇenným a pro kaˇzdou variantu zkontroluje platnost formule a báze znalost´ı. Tento algoritmus je bezesporný, jelikoˇz je

(25)

zaloˇzen pˇr´ımo na definici logického d˚usledku, a úplný, protoˇze vˇzdy skonˇc´ı, model˚u je vˇzdy koneˇcný poˇcet.

Výroková logika je pro mnoho úloh pouˇzitelná, n´ıcménˇe nen´ı optimáln´ı pro prostˇred´ı neomezené velikosti, protoˇze postrádá výrazové schopnosti pro vyjádˇren´ı ˇcasu, prostoru a vztah˚u mezi objekty. V takových pˇr´ıpadech je vhodné vyuˇz´ıt logiku prvn´ıho ˇrádu (logiku predikátovou).

4.3 Predik´ atov´ a logika

4.3.1 Jazyk predik´atov´e logiky

Výrazové prostˇredky výrokové logiky, jak jiˇz bylo ˇreˇceno, nejsou bohaté natolik, aby s jejich pomoc´ı bylo moˇzno vyjádˇrit znalosti o komplexn´ıch prostˇred´ıch. Jazyk predikátové logiky nám vˇsak umoˇzˇnuje reprezentaci fakt˚u ve srozumitelnˇejˇs´ı a mnohdy pˇresnˇejˇs´ı podobˇe.

Narozd´ıl od modelu ve výrokové logice, který je mnoˇzinou pravdivostn´ıch hodnot kaˇzdého výrokového symbolu, obsahuje model predikátové logiky objekty. Tyto objekty mohou m´ıt mezi sebou r˚uzné vztahy, nˇekteré z tˇechto vztah˚u jsou funkcemi, takové, kde existuje pouze jedna

”hodnota“ pro dan´y

”vstup“. Tyto relace mezi objekty jsou vlastnˇe jen mnoˇziny n-tic objekt˚u, které maj´ı mezi sebou nˇejaký vztah. Základn´ı sloˇzkou jazyka jsou symboly reprezentuj´ıc´ı objekty, vztahy a funkce. Tyto symboly jsou tedy rozdˇeleny na individuové konstanty, predikátové a funkˇcn´ı symboly. Dalˇs´ı souˇcást´ı jazyka jsou termy, kaˇzdý term je logický výraz pro urˇcitý objekt. Kaˇzdá individuová konstanta je tedy term, nicménˇe ne vˇzdy máme zvláˇstn´ı symbol pro kaˇzdý objekt, a proto je term moˇzné vyjádˇrit funkˇcn´ım sym- bolem následovaným mnoˇzinou term˚u v závorce, coˇz jsou argumenty dané funkce. Narozd´ıl od proceduráln´ıch programovac´ıch jazyk˚u, fuknˇcn´ı symbol neznamená ˇzádné volán´ı pod- programu, který pˇredává návratovou hodnotu, je to pouze komplikovaný název pro objekt a umoˇzˇnuje nám odvozovat fakta aniˇz bychom nˇejakou funkci definovali. Termy, které od- kazuj´ı na objekty, a predikátové symboly, které znaˇc´ı relace, tvoˇr´ı atomické formule, vy- jadˇruj´ıc´ı fakta. Atomická formule je pravdivá v daném modelu, pokud relace, ke které se vztahuje predikátový symbol, obsahuje objekty, ke kterým se vztahuj´ı argumenty tohoto symbolu. Stejnˇe jako ve výrokové logice, sloˇzitˇejˇs´ı formule lze vytvoˇrit pomoc´ı logických spojek (negace, konjunkce, disjunkce, implikace a ekvivalence). Abychom mohli vyjadˇrovat vlastnosti nejen jednotlivých objekt˚u, ale i kolekc´ı objekt˚u, potˇrebujeme kvantifikátory. Uni- verzáln´ı kvantifikátor∀xuplatˇnuje daný výrok pro kaˇzdý objekt v bázi znalost´ı nahrazen´ım promˇennéxve formuli za jednotlivé objekty. Umoˇzn´ı tak vyjádˇrit obecná fakta o prostˇred´ı, jako napˇr.∀x(medved(x)∧bily(x))⇒ledni_medved(x). Podobnˇe tak lze pomoc´ı existenˇcn´ıho kvantifikátoru∃xuˇcinit tvrzen´ı o nˇejakém objektu aniˇz bychom jej jmenovali. Toto tvrzen´ı je pak pravdivé, pokud v daném modelu existuje alespoˇn jeden objekt, po jehoˇz pˇriˇrazen´ı do promˇenné x je formule kvantifikátoru platná.

4.3.2 Odvozován´ı v predikátové logice

Prvn´ı moˇznost´ı, jak vyhodnotit výraz predikátové logiky, je pˇrevést jej na výraz výrokové logiky. K tomu je zapotˇreb´ı pravidel pro odstranˇen´ı kvantifikátor˚u a predikátových symbol˚u.

Univerzáln´ı kvantifikátor m˚uˇzeme odstranit tak, ˇze z dané formule substituc´ı volného termu za promˇennou z´ıskáme mnoˇzinu formul´ı logicky vyplývaj´ıch z kvanfitifikované formule. Ex- istenˇcn´ı kvantifikátor odstran´ıme nahrazen´ım promˇenné za symbol, který se doposud v bázi znalost´ı nevyskytuje. Posledn´ım rozd´ılem od formul´ı výrokové logiky jsou predikátové sym-

(26)

boly, ty vˇsak m˚uˇzeme brát jako obyˇcejné výrokové symboly. Nyn´ı jiˇz staˇc´ı nˇekterá z metod pro ˇreˇsen´ı výraz˚u výrokové logiky.

Tento pˇr´ıstup je vˇsak neefektivn´ı, a proto jsou ˇcastˇeji pouˇz´ıvána pˇr´ımo pravidla pro odvozen´ı výraz˚u predikátové logiky. Jedn´ım z nejd˚uleˇzitˇejˇs´ıch je unifikace, coˇz je vlastnˇe nalezen´ı a substituce term˚u za promˇenné. Vstupem algoritmu jsou dvˇe klauzule a úkolem je naj´ıt substituci takovou, aby po jej´ım proveden´ı byly klauzule shodné. Pokud je nen´ı moˇzné unifikovat, vrac´ı metoda prázdný výsledek.

Jednoduchou a úˇcinnou metodou jak ˇreˇsit výrazy predikátové logiky je algoritmus forward-chaining. Tato metoda je schopna efektivnˇe vyhodnotit systém sloˇzený z Hornových klauzul´ı, coˇz jsou disjunkce literál˚u, které obsahuj´ı nejvýˇse jeden pozitivn´ı literál. Tyto literály mohou obsahovat promˇenné, v tom pˇr´ıpadˇe jsou povaˇzovány za univerzálnˇe kvan- tifikovné. Algoritmus pracuje na principu postupného vytváˇren´ı nových fakt˚u v bázi znalost´ı. Nejprve procház´ı vˇsechny známá pravidla a pokud jsou jejich premisy splnˇeny, je pˇridán nový fakt, který je výsledkem daného pravidla. Takto se pokraˇcuje dokud nen´ı dotaz zodpovˇezen nebo dokud jiˇz nelze pˇridat nový fakt.

4.4 Implementace

4.4.1 Tˇr´ıdy a algoritmy v´yrokov´e logiky

Základn´ı prvek výrokové logiky – báze znalost´ı, je zastoupen tˇr´ıdou KnowledgeBase. Ob- sahuje kolekci vˇet, které jsou vkládány metodou tell:. Jelikoˇz jsou vˇety vkládány ve formˇe ˇretˇezc˚u, je tˇreba je zpracovat, aby byly pouˇzitelné v implementovaných algoritmech. To provád´ı lexikáln´ı analyzátor Lexer ve spojen´ı se syntaktickým analyzátorem Parser. Pro výrokovou logiku se pouˇz´ıvaj´ı potomci tˇechto tˇr´ıdPELexer aPEParser. Výstupem parseru je instance tˇr´ıdySentencenebo nˇekterý z jej´ıch potomk˚u. Jsou toTrueSentence aFalseSen- tence pro vˇzdy pravdivé a vˇzdy nepravdivé formule, AtomicSentence pro atomické formule,UnarySentencepro unárn´ı výrazy (negace) aBinarySentence pro reprezenci formul´ı s binárn´ım operátorem. V pˇr´ıpadˇeUnarySentenceaBinarySentencejsou jejich operandy opˇet instancemi nˇekteré z potomk˚u Sentence a t´ımto zp˚usobem je sloˇzena jakákoli komplexn´ı formule výrokové logiky. Abychom mohli bázi znalost´ı vyuˇz´ıt pro z´ıskáván´ı fakt˚u, je im- plementována metoda askWithTTEntails:, která vyhodnot´ı zadaný výraz pomoc´ı kontroly model˚u na základˇe pravdivostn´ı tabulky. Samotný algoritmus implementuje tˇr´ıdaTTEntails a jej´ı rekurzivn´ı metoda ttCheckAll:querySentence:symList:model:, která vytvoˇr´ı vˇsechny kombinace hodnot vˇsech symbol˚u báze znalost´ı a ty postupnˇe testuje, zda zadaná formule je platná v modelu, ve kterém je zároveˇn platná báze znalost´ı. Pˇr´ıklad vyhodnocen´ı formule výrokové logiky pomoc´ı této metody lze spustit tˇr´ıdn´ı metodouLogicDemo ttEntailsDemo.

4.4.2 Tˇr´ıdy a algoritmy predik´atov´e logiky

Pro pˇridáván´ı fakt˚u do báze znalost´ı predikátové logiky DLKnowledgeBase metodou add:

je nejprve nutné nadefinovat symboly, které se bázi budou vyskytovat, prostˇrednictv´ım tˇr´ıdy FOLDomain a jejich metod addConstant:, addFunction: a addPredicate:. Kolekce tˇechto symbol˚u pak vyuˇz´ıvá lexikáln´ı analyzátor FOLLexer pro správné rozpoznán´ı jed- notlivých token˚u, syntaktický analyzátor FOLParser pak podle tˇechto token˚u zpracuje zadaný výraz jako instanciFOLSentence nebo jej´ıho potomka. Stejnˇe jako ve výrokové logice, existuj´ı zde tˇr´ıdy pro jednotlivé typy výraz˚u (nebo jejich ˇcásti): FOLPredicate,FOL- NotSentence,FOLParanthizedSentence,FOLConnectedSentence,FOLQuantifiedSentence a

(27)

FOLTermEquality. Algoritmus pro vyhodnocen´ı výrazu dopˇredným ˇretˇezen´ım je implemen- tován jako metodaforwardChain:na tˇr´ıdˇe báze znalost´ıDLKnowledgeBase, která postupnˇe odvozuje nová fakta z jiˇz existuj´ıch pravidel a vyuˇz´ıvá pomoci unifikátoruUnifier. Pˇr´ıklady obsaˇzené v knize AIMA [1] je moˇzné spustit pomoc´ı tˇr´ıdn´ıch metodFOLDemo kingsDemo a FOLDemo weaponsDemo.