UMĚLÁ INTELIGENCE 2. Umělá inteligence může být jako obor chápána různě, například:

UMĚLÁ INTELIGENCE 2 ►

Umělá inteligence může být jako obor chápána různě, například: 1. Systém myslící jako člověk – souvislost s psychologií a poznáváním 2. Systém chovající se jako člověk – východisko je Turingův test 3. Systém myslící racionálně – popis řešení logikou (sylogismus, aj.) 4. Systém chovající se racionálně – poskytuje co nejlepší řešení

►

Zde se budeme zabývat především agenty, kteří se chovají racionálně, neboli agenty, kteří se snaží vždy poskytnout správné řešení, tj. dělat správné věci.

►

Racionálně se chovající (dále jen “racionální”) agenti v současnosti představují preferovaný směr.

►

Racionální agenti nezaručují dokonalou racionalitu jimi nalezeného řešení. To může být dáno např. složitostí prostředí, v němž působí (výpočetní složitost).

►

Ideálem je vždy dosažení dokonalého racionálního agenta, ale je nutno mít na paměti, že v realitě mívá agent svou racionalitu omezenou, a to z nejrůznějších důvodů.


K základům umělé inteligence (UI) přispělo a přispívá mnoho různých oborů (filosofie, matematika, neurologie, psychologie, konstrukce počítačů, teorie řízení a kybernetika, lingvistika, aj.).

►

Ekonomie od roku 1776 (Adam Smith) také slouží pro inspiraci rozvoje umělé inteligence (Smith tehdy publikoval ideu, že ekonomie se má považovat za vědu – vystupují zde agenti maximalizující svůj blahobyt): ►

Jak rozhodovat, aby byl maximalizován zisk?

►

Jak toho dosáhnout, když ostatní mohou postupovat jinak?

►

Jak toho dosáhnout, když ten zisk může být k dispozici až v daleké budoucnosti?

►

Za zrod umělé inteligence se považuje rok 1956 (John McCarthy na universitě Princetown je údajně autorem termínu artificial intelligence, přestože vhodnějším názvem by snad bylo computational rationality).

►

Umělá inteligence prošla obdobími jak nadneseného vyzvedávání, tak odmítání. Od roku 1987 je již považována za samostatný vědní obor.

►

Inteligentní agenti se v UI objevují přibližně od roku 1995.


V současnosti oblast umělé inteligence zahrnuje mnoho nejrůznějších druhů aktivit, například: ►

Autonomní plánování a časové rozvržení činností

►

Hraní her (jako modelů vysoce složitých činností)

►

Samočinné řízení procesů

►

Diagnostika

►

Logistické plánování

►

Robotika

►

Porozumění přirozenému (lidskému) jazyku

►

A mnoho dalších

►

Umělá inteligence se uplatňuje především tam, kde není možno využít exaktních matematických postupů vlivem složitosti problémů, a přesto je potřeba tyto problémy řešit.

►

Je nutno tolerovat určitý stupeň nedokonalosti nalezených řešení.

UMĚLÁ INTELIGENCE 2 Inteligentní agenti ►

Agentem zde rozumíme cokoliv, co vnímá své prostředí pomocí sensorů 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 sensory; dále má ruce, nohy, ústa a další části těla jako efektory.

►

Robot-agent nahrazuje kamerami a infračervenými detektory sensory.

►

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í.

UMĚLÁ INTELIGENCE 2 Č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 z vně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 do úvahy faktor spotřeby el. 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.


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říklad 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 ho 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: 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...)

UMĚLÁ INTELIGENCE 2 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ř. metodou Newtona.)

UMĚLÁ INTELIGENCE 2 Autonomie ►

Ideální racionální agent by měl obsahovat nějakou “vestavěnou” znalost.

►

Pokud takovou znalost 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í či 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 úspěšné činnosti v širokém rozsahu různých prostředí, a to za předpokladu, že má dost času k adaptaci.

UMĚLÁ INTELIGENCE 2 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 = 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í.

►

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 Boening 747, softbot pro prohlížení on-line zpráv a výběr zajímavých pro zákazníky, a podobně).

UMĚLÁ INTELIGENCE 2 Příklady typů agentů TYP AGENTA

VNÍMÁNÍ

AKCE

CÍLE

PROSTŘEDÍ

medicínský diagnostický systém

symptomy, nálezy, pacientovy odpovědi

otázky, testy, léčba

zdravý pacient, minimální náklady

pacient, nemocnice

systém analýzy satelitních snímků

pixely různé intensity, barva

tisk kategorie záběru

správná kategorizace

obrazy z obíhajícího satelitu

pixely různé intensity

zvednutí součástky a její uložení do přihrádky

umístění součástek do správných přihrádek

pás přepravující součástky

teplota, tlak

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

maximalizace čistoty, vydatnosti, bezpečnosti

čistička

napsaná slova

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

maximalizace studentových výsledků v testech

soubor studentů

robot sbírající součástky

řízení čističky

interaktivní učitel angličtiny

UMĚLÁ INTELIGENCE 2 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 ← Update-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.

UMĚLÁ INTELIGENCE 2 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á sekvencemi // vnímání, na počátku daná

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í, která 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: ● Tabulka potřebná pro jednoduchého agenta, jehož úkolem je pouze hrát šachy, by potřebovala přibližně 35100 buněk. ● Pro návrháře by to znamenalo velice dlouhý čas pro vytvoření tabulky. ● 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 zcela 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ší při vyhnutí se 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. TYP AGENTA

řidič taxíku

VJEMY

AKCE

CÍLE

PROSTŘEDÍ

kamery, rychloměr, GPS, sonar, mikrofon

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

bezpečná, rychlá, předpisová a pohodlná jízda, maximální zisk

silnice, další doprava, chodci, zákazníci


Příklad (pokračování):

►

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, rychloměr, 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íce-mé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.


Příklad (pokračování): 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 omezování 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.

UMĚLÁ INTELIGENCE 2 Stačí pouze hledat odpovědi? Jednoduší reflexní agenti ►

Explicitní vyhledávací tabulky nepřicházejí do úvahy: visuální vstup z jednoduché kamery přichází v množství 50 MB/s (25 obrázků za vteřinu, 1000x1000 pixelů s 8 bity na barvy a 8 bity informace o intensitě).

►

Tabulka by pak musela mít pro jednu hodinu 260x60x50M 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í vstup/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).

UMĚLÁ INTELIGENCE 2 Stačí pouze hledat odpovědi? Jednoduší reflexní agenti (pokračování) ►

Lidé takovýchto vstup/výstupních asociací rovněž používají 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 agentovi pravidla umožňují propojit vjemy s akcemi:

Agent

Sensory Jaký je svět nyní

IF-THEN

Jaká akce má být provedena Efektory

UMĚLÁ INTELIGENCE 2 Stačí pouze hledat odpovědi? Jednoduší reflexní agenti (pokračování) ►

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

UMĚLÁ INTELIGENCE 2 Stačí pouze hledat odpovědi? 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 jen předchozí snímek kamery k určení stavů, kdy se co rozsvítí nebo nějak změní na autě vpředu při jeho brzdění, ukazování změny směru jízdy (blinkr, nebo mechanická ručka, ...), apod.

UMĚLÁ INTELIGENCE 2 Stačí pouze hledat odpovědi? Agenti sledující svět (pokračování) ►

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ř. (1) nejede-li ve vedlejším pruhu auto nebo (2) není-li vidět, generuje tentýž vstup, avšak 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 stroj-agenta je nutno takto uvažovat).


Schema reflexního agenta s interním stavem:

Sensory stav vývoj světa účinek akcí IF-THEN

Agent

Jaký je svět nyní Jaká akce má být provedena Efektory


Příslušná funkce v pseudokódu: function Reflex-Agent-With-State(percept) returns action static: rules // soubor IF-THEN pravidel 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

UMĚLÁ INTELIGENCE 2 Stačí pouze hledat odpovědi? Agenti zaměření na cíl ►

Znalost okamžitého stavu prostředí nemusí ve všech případech postačovat k rozhodnutí o činnosti. Na křižovatce může taxi jet doleva, doprava, nebo rovně. Správné rozhodnutí 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á různé metody pro vyhledávání a plánování k tomuto účelu.

UMĚLÁ INTELIGENCE 2 Stačí pouze hledat odpovědi? Agenti zaměření na cíl (pokračová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 může zdát méně efektivní, ale je daleko flexibilnější.

►

Začne-li např. pršet, cílový agent může aktualizovat svou znalost o efektivnosti jeho 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:

sensory stav vývoj světa

jaký je svět nyní

účinek akcí

co se stane po akci A

cíle

Agent

jaká akce by měla být provedena

efektory

UMĚLÁ INTELIGENCE 2 Stačí pouze hledat odpovědi? Užitkově zaměření agenti ►

Cíle samy o sobě nepostačují 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.)

UMĚLÁ INTELIGENCE 2 Stačí pouze hledat odpovědi? Užitkově zaměření agenti (pokračování) ►

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 nějaké potíže s dosažením cílů: 1. Pokud existují konfliktní cíle, pak pouze některé mohou být dosaženy (např. rychlost a bezpečnost). Funkce užitku zde stanoví vhodný kompromis. 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 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:

sensory stav vývoj světa

jaký je svět nyní

účinek akcí

co se stane po akci A

užitek

jaký užitek takový stav přinese

Agent

jaká akce by měla být provedena

efektory

UMĚLÁ INTELIGENCE 2 Prostředí Vlastnosti prostředí ►

Prostředí má několik charakteristik. Základní odlišnosti: ● Přístupné a nepřístupné: zda agentovy sensory umožňují poskytnout kompletní informaci o stavu prostředí. Pokud ano, je prostředí přístupné, jinak je nepřístupné. Sensory 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.

UMĚLÁ INTELIGENCE 2 Prostředí Vlastnosti prostředí (pokračování) ● Episodické a neepisodické: v episodickém prostředí je agentova znalost/zkušenost rozdělena mexi “episody”. Každá episoda se skládá z agentových vnímání následovaných akcemi. Kvalita agentovy akce závisí pouze na dané episodě, protože následné episody na předcházejicích nezávisejí co do jejich vlastní kvality. Episodická 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í.

UMĚLÁ INTELIGENCE 2 Prostředí Vlastnosti prostředí (pokračování) ● 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.: 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é, neepisodické 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.

UMĚLÁ INTELIGENCE 2 Prostředí Vlastnosti prostředí (pokračování) Následující tabulka ukazuje některé známější typy prostředí: přístupné

deterministické

episodické

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 (vrhcáby)

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

PROSTŘEDÍ

UMĚLÁ INTELIGENCE 2 Prostředí Vlastnosti prostředí (pokračování) Následující tabulka ukazuje některé známější typy prostředí (pokračování):

přístupné

deterministické

episodické

statické

diskrétní

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

PROSTŘEDÍ

UMĚLÁ INTELIGENCE 2 Prostředí Vlastnosti prostředí (pokračování) ►

Hodnoty v tabulce mohou ovšem záviset na tom, jak je vytvořen pojem (tzv. konceptualizace) prostředí a agentů.

►

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 episodické na vyšší úrovni, než se odehrávají agentovy jednotlivé akce.

►

Např. šachový turnaj se skládá z posloupnosti her (partií). Každá partie je episoda, 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 uvažovat fakt, ž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.

UMĚLÁ INTELIGENCE 2 Prostředí Programy pro prostředí ►

Obecný program pro 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 state ← Update-Fn (actions, agents, state) until termination(state)

UMĚLÁ INTELIGENCE 2 Prostředí Programy pro prostředí (pokračování) ►

Uvedený základní program pracuje v principu tak, že předává každému agentovi jeho vjemy (percepce), od každého agenta získává jeho akci, 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) agenta 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ě vlivu dalších dynamických procesů (které však nejsou agenty, např. déšť).

►

Prostředí je tedy definováno počátečním stavem a aktualizační funkcí.

►

(Pozn.: Každý agent pracující v simulovaném prostředí by samozřejmě měl fungovat 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členuje nějaký kód pro měření výkonnosti.

►

Může to být např. funkce Run-Eval-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 (viz následujcí funkci Run-Eval-Environment):

UMĚLÁ INTELIGENCE 2 Prostředí Programy pro prostředí (pokračování) function Run-Eval-Environment(state, Update-Fn, agents, termination, Performance-Fn) 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) scores ← Performance-Fn(scores, 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 použití maxima). Např. 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-Eval-Environment vrací míru výkonnosti pro jedno prostředí, definované jedním počátečním stavem a konkrétní aktualizační funkcí.


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 protihráčů. 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 (viz Deep Blue pro Garry Kasparova).

►

Z toho plyne zřejmý požadavek: pro měření výkonnosti agenta je zapotřebí generátor prostředí, který (s určitou pravděpodobností) vybírá konkrétní prostředí, 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í.

►

Agentova stavová proměnná může pouze nabývat hodnot na základě agentových vjemů, bez kompletního přístupu k informacím.

UMĚLÁ INTELIGENCE 2 Prostředí Příklad prostředí a agentů ve světě vysávání špíny Uvedený svět lze popsat následovně: ►

►

►

►

Vjemy: každý vysavačový agent dostává tříprvkový vektor vjemů pro každé kolo vysávání. První element (z dotykového sensoru) dává 1 pokud stroj do něčeho vrazí, jinak 0. Druhý element (fotosensor 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: pět akcí je k dispozici – jdi vpřed, otoč se doprava o 90°, otoč se doleva o 90°, vysaj smetí, vypni se. Cíle: Cílem 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, -1000 bodů pokud se agent vypne jinde než doma. Prostředí: je dáno mřížkou se čtverci. Některé čtverce obsahují překážky (zdi, nábytek, apod.), 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 odstraní detekovaný kus smetí. “Vypni se” vždy zcela ukončí simulaci.

UMĚLÁ INTELIGENCE 2 Prostředí Příklad prostředí a agentů ve světě vysávání špíny (pokračování) Složitost prostředí lze měnit ve třech směrech: ►

►

►

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 agentavysavače nemusí vjem rozlišovat mezi zdí a kusem nábytku, obojí aktivuje sensor 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, apod.).

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů ►

Řešení úloh (problémů) – 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.

►

Řešený problém zde představuje cíl a soubor prostředků pro dosažení cíle.

►

Proces prozkoumávání prostředků (tj. co 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říklad jednoduchý reflexní agent je příliš omezen (kvůli svým vlastnostem nemůže uvažovat směrem do budoucna).


Agenti, kteří řeší problémy, rozhodují o své činnosti tím, že se snaží nalézt 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ě: z hlediska účinnosti agenta splnit vybraný cíl).

►

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 nalézt vhodné akce k dosažení cílového stavu.


Obecně nelze uvažovat o akcích na určité detailní úrovni. Například 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, apod. Pokud není k dispozici dostatek informací a k cíli se lze dostat více možnostmi, pak agent nemá 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.

►

Na výstupu poskytuje řešení ve formě sekvence akcí. Jakmile je řešení nalezeno, je doporučeno (nabídnuto) k provedení – tzv. výkonná fáze.

►

Z toho plyne jedna z možností, jak navrhnout agenta na základě trojice pojmů: 1) formuluj, 2) vyhledej, 3) proveď.

►

Po provedení zvolené sekvence akcí pak agent zvolí nový cíl a vše se pro aktuální situaci opakuje znovu.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů 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 (goal), na počátku prázdný 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) s ← Search(problem) // hledání sekvence akcí action ← Recommendation(s, state) // 1. akce v sekvenci s ← Remainder(s, state) // ostatní akce v sekvenci return action

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů 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ů: 1) problémy pro jeden stav, 2) problémy pro více stavů, 3) problémy nahodilé, 4) problémy k prozkoumání.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Formulace problémů (pokračování) Typy problémů ►

Uvažme opět svět vysávání nečistoty:

►

Nechť pro jednoduchost obsahuje pouze dvě místa.

►

Každé z míst může nebo nemusí obsahovat nečistotu.

►

Agent se může zpočátku nacházet v libovolném z obou míst.

►

Existuje celkem 8 možných stavů světa, {1, 2, 3, 4, 5, 6, 7, 8}, viz následující obrázek. Agent má k dispozici tři možné akce (v této verzi světa): Doleva, Doprava, Vysávat. Dále předpokládejme, že vysávání je účinné na 100%. Cílem je zlikvidovat veškerou nečistotu, tj. cíl je ekvivalentní s dosažením množiny stavů {7, 8}.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Formulace problémů (pokračování) Agent-vysavač a jeho svět s osmi možnými stavy: 1

2

3

4

5

6

7

8

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Formulace problémů (pokračování) ►

Předpokládejme dále, že agentovy sensory mu poskytují dostatek informace k tomu, aby přesně věděl, v jakém stavu se nachází (svět je přístupný) a dále, že agent ví, co každá jeho akce udělá. Pak je možné exaktně spočítat, v jakém stavu bude po jakékoliv sekvenci akcí.

►

Pokud je např. počáteční stav 5, pak lze určit, že po sekvenci akcí [Doprava, Vysávat] bude dosaženo cílového stavu. To je nejjednodušší případ, zvaný problém jednoho stavu.


Uvažujme dále agenta, který zná všechny důsledky svých akcí, ale má omezený přístup ke stavům světa (např. v extrémním případě nemusí mít žádné sensory). V takovém případě jediné, co agent ví, je, že jeho počátečním stavem je jeden z množiny stavů {1, 2, 3, 4, 5, 6, 7, 8}.

►

Kupodivu agentova kritická situace není beznadějná – protože ví, k čemu po jeho akcích dochází, pak může určit, že např. po akci Doprava se ocitne v jednom ze stavů {2, 4, 6, 8}. Ve skutečnosti může agent odhalit, že po akční sekvenci [Doprava, Vysávat, Doleva, Vysávat] je zaručeno dosažení cíle bez ohledu na počáteční stav.

►

Shrnutí: Pokud není svět plně přístupný, pak agent musí uvažovat o množině stavů, do nichž se může dostat, nikoliv o jednotlivých stavech. Uvedená situace se nazývá vícestavový problém.


Případ neznalosti důsledku akcí lze řešit obdobným způsobem. Uvažujme situaci, kdy prostředí se jeví nedeterministické (a splňuje Murphyho pravidlo): Akce zvaná Vysávání někdy umístí nečistotu na koberec, ale pouze v tom případě, že tam ještě není žádná nečistota.

►

Pokud agent tedy ví, že se nachází např. ve stavu 4, pak také ví, že bude-li vysávat, dosáhne jednoho ze stavů {2, 4}.

►

Pro jakýkoliv známý počáteční stav existuje posloupnost akcí, která zaručuje dosažení cílového stavu.


Někdy ovšem neznalost zabraňuje agentovi nalézt sekvenci zaručující dosažení cíle. Dejme tomu, že agent je ve světě Murphyho pravidla, má poziční sensor a sensor pro lokaci nečistoty, ale nemá sensor schopný detekovat nečistotu v jiných místech (čtvercích). Řekněme, že sensory poskytují informaci, že agent je v jednom ze stavů {1, 3}.

? ?


Agent může formulovat sekvenci akcí [Vysát, Doprava, Vysát]. Vysátí změní stav na jeden z {5, 7}, pohyb doprava na jeden z {6, 8}. Je-li skutečným stavem 6, pak sekvence akcí je úspěšná; pokud 8, pak plán selhal.

►

Pokud by agent vybral jednodušší sekvenci akcí [Vysát], pak to někdy může uspět, ale ne vždy. Ukazuje se, že neexistuje žádná fixní posloupnost akcí, která by zaručila řešení problému.


V uvedeném případě má agent cestu k řešení problému z jednoho stavu {1, 3}: vysát, zatočit doprava, a pak vysát pouze pokud tam je nečistota.

►

Tento postup ovšem vyžaduje možnost vnímání během exekuční fáze. V tomto případě musí agent spočítat celý strom akcí (nikoliv jen sekvenci pro jednu akci).

►

Obecně se každá z větví stromu zabývá možnou nahodilostí, která se může objevit. Proto se tato situace nazývá problém nahodilosti.

►

V realitě k těmto problémům patří velké množství situací, protože přesná predikce je nemožná – z tohoto důvodu např. lidé obvykle důkladně sledují situaci při přecházení silnice nebo při řízení.


Problémy jednoho stavu a více stavů mohou být zpracovávány podobnými vyhledávacími technikami.

►

Problémy s nahodilostí však vyžadují mnohem složitější algoritmy a často vedou ke změně návrhu agenta, kdy agent může provést akci před nalezením zaručeného plánu.

►

To je užitečné proto, že může být snazší nebo lepší prostě něco začít dělat a teprve pak zjišťovat, jaké nahodilosti se objevily, ve srovnání s postupem, kdy se předem uvažuje každá možná nahodilost, která by se mohla vyskytnout během exekuční fáze.

►

Agent pak může pokračovat v řešení problému za předpokladu získání přídavné informace. Tento postup se nazývá prokládání činnosti vyhledávání a exekuce.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Dobře definované problémy a řešení ►

Pod pojmem problém zde budeme rozumět souhrn informací, které agent použije k rozhodnutí o své činnosti.

►

Základními prvky definice problému jsou stavy a akce: ●

Počáteční stav – stav, o němž agent ví, že v něm je.

●

Operátor – soubor agentových možných akcí. Termín operátor se používá k popisu akce, a to pomocí pojmů, jakých stavů lze docílit provedením akce z konkrétního stavu. Někdy se používá formulace následnická funkce S: je-li dán konkrétní stav x, pak S(x) vrací soubor stavů dosažitelných z x libovolnou jednou akcí.

●

Stavový prostor problému – soubor všech stavů dosažitelných z počátečního stavu libovolnou sekvencí akcí.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Dobře definované problémy a řešení (pokračování) ●

Cesta – ve stavovém prostoru jde prostě o jakoukoliv sekvenci akcí, která vede z jednoho stavu do druhého.

●

Test cíle – test aplikovaný agentem na popis jednoho z cílů, zda jde o cílový stav. Pokud je cílových stavů více, test cíle rozezná, zda se o jeden z nich jedná či nikoliv. Pozn.: Někdy je cíl specifikován nějakou abstraktní vlastností spíše než explicitně vyjmenovaným seznamem stavů. Např. v šachu jde o dosažení cíle mat (protivníkův král je napaden figurou a nemá kam ustoupit, a ani to napadení nelze zlikvidovat, tj. dalším tahem lze krále vzít bez ohledu na to, co oponent vlastnící daného krále udělá).

●

Funkce ceny cesty g – funkce g přiřazující dané cestě nějaké náklady (nebo cenu). Nadále budeme uvažovat o ceně cesty jako o sumě cen za jednotlivé akce podél dané cesty.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Dobře definované problémy a řešení (pokračování) ►

Počáteční stav, soubor operátorů, test cíle a cena cesty dohromady definují problém. Typ dat representující problém: datatype Problem components: Initial-State, Operators, Goal-Test, Path-Cost-Function

►

Instance uvedeného typu dat slouží jako vstup vyhledávacího algoritmu; výstupem je řešení, tj. cesta z počátečního stavu do stavu vyhovujícímu cílovému testu. Pro zpracování vícestavových problémů se provede jednoduchá modifikace: problém je složen z počátečního souboru stavů a dále ze souboru operátorů. Test cíle a funkce ceny cesty zůstávají jako předtím. Cesta nyní propojuje soubor stavů a řešením se nyní rozumí cesta vedoucí do souboru těch stavů, které vyhovují cílovým stavům. Stavový prostor je nahrazen prostorem souboru stavů.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Měření výkonnosti řešení problémů ►

Tři možnosti: 1. Bylo vůbec nalezeno řešení? 2. Je řešení dobré (tj. cesta s nízkou cenou)? 3. Jaká byla cena za nalezené řešení vzhledem k požadované paměti a času?

►

Celková cena vyhledávání je tvořena součtem ceny cesty a ceny vyhledávání (v robotice se cena vyhledávání, tj. části prováděné před interakcí s prostředím, nazývá offline cena a cena cesty online cena).

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Měření výkonnosti řešení problémů (pokračování) ►

Např. cesta z města A do města B: cena cesty může být úměrná počtu kilometrů plus náklady za opotřebení na různých typech silnic.

►

Cena vyhledávání závisí na okolnostech: ●

Ve statickém prostředí je nulová (nezávislost na čase).

●

Je-li nějaká urgentní potřeba dojet do B, pak je prostředí semidynamické, protože delší uvažování o cestě cenu zvýší (můžeme uvažovat o přibližně lineární závislosti na době výběru, přinejmenším pro kratší časové úseky). Zde je tedy nutno dát dohromady kilometry a sekundy (cenu cesty a cenu vyhledávání, což není obecně snadný problém. Navíc pro velmi malé stavové prostory je snadné najít řešení s minimální cenou cesty. Pro rozsáhlé a komplikované problémy je nutno nalézt kompromis.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Měření výkonnosti řešení problémů (pokračování) ►

Výběr stavů a akcí Příklad: dojet z města Arad do města Bucharest, přičemž k dispozici je mapa cest: O ra d e a N eam t Z e rin d Ia s i A ra d S ib iu

F a g a ra s V a s lu i R im n ic u V ilc e a

T im is o a ra

P ite s t i

Lu goj

H irs o v a M e h a d ia

U r z ic e n i B u ch a re st

D o b reta C ra io v a G iu r g i u

E fo rie

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Měření výkonnosti řešení problémů (pokračování)

►

Odpovídající stavový prostor má 20 stavů (měst), každý stav je definován pouze polohou specifikovanou jako město. Počáteční stav je tedy “v Aradu”, test cíle je “je to Bucharest?”. Operátory odpovídají jízdě po silnicích mezi městy.

►

Jedno možné řešení: Arad➝Sibiu➝Rimnicu Vilcea➝Pitesti➝Bucharest.

►

►

(Je mnoho dalších řešení.) K rozhodnutí o tom, které řešení je lepší, je nutno znát, co měří funkce ceny: celkovou délku cesty nebo celkový čas cesty?

►

Daná mapa neobsahuje ani jedno, takže se použije počet kroků (průjezdních silnic mezi městy): to je 3 přes Sibiu a Fagaras, tedy nejlepší řešení.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Příklady problémů ►

Obvykle je vhodné uvažovat o problémech her a o problémech reálných (které jsou opravdové, avšak obvykle mnohem obtížnější pro hledání řešení). U problémů her je ale snadnější vytvořit jasný a exaktní popis, takže mohou být snadněji použity pro srovnání různých metod apod.

►

Problémy her

►

8-hlavolam:

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Příklady problémů (pokračování) ►

Při řešení problému seřazení posuvných kosteček je vhodné použít určité “triky”, které řešení usnadní.

►

Příklad: místo použití operátorů typu přesun kostky s číslem 4 na volnou pozici je mnohem rozumnější použít operátory typu volná pozice mění místo s kostkou nalevo, apod. (Vede to k menšímu počtu operátorů.)

►

Lze vytvořit následující formulaci: ● ● ● ●

Stavy: popis stavu specifikuje umístění každé z osmi kosteček na jednom z devíti polí (je užitečné zahrnout i pozici volného místa). Operátory: volné místo se pohybuje doleva, doprava, nahoru, dolů. Test cíle: stav se shoduje s cílovou konfigurací na obrázku. Cena cesty: každý krok stojí 1 (cesta stojí totéž, co je její délka).


8-hlavolam patří ke skupině úloh přemísťování bloků, což obecně jsou NP-kompletní problémy, kde nelze očekávat, že bude nalezeno řešení lepší než pomocí vyhledávacího algoritmu.

►

Principiálně stejná, avšak značně složitější úloha 15-hlavolam se spolu s 8-hlavolamem používá často k testování nových vyhledávacích algoritmů v umělé inteligenci.


Osm dam na šachovnici 8x8 (resp. N dam na šachovnici NxN) patří do skupiny tzv. dobře definovaných problémů.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Algoritmy iterativního vylepšování ►

Pro řadu dobře definovaných problémů (např. 8 dam, VLSI) 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 obvodu VLSI. 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í.

►

Ideou je začít s kompletní konfigurací a modifikacemi zlepšit kvalitu.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Algoritmy iterativního vylepšování (pokračování) ►

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): e v a lu a ti o n

current s ta te


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é nedostaky 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 hill-climbing, 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 ← 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


Ve smyčce se hledající 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. 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 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 nějaký přijatelný výsledek dosažený po nepříliš velkém počtu iterací – praktické hledisko hraje často výraznou roli (např. časové omezení na vyřešení úlohy).

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů 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:

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Aplikace pro problémy vyhovující omezením (CSP) (pokračování) 2

3

2

3

1 2

2

3

3

1

2

2

3 0

►

Problém je zde vyřešen ve dvou krocích. Čísla ve sloupci s dámou, jejíž postavení se vylepšuje (Dh8 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.

UMĚLÁ INTELIGENCE 2 Řešení úloh pomocí agentů Aplikace pro problémy vyhovující omezením (CSP) (pokračování) ►

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).

Metody informovaného hledání 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), 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 jako hledání prvního nejlepšího (best-first search). Ilustrace možné implementace této funkce je na následujícím obrázku.

-59-

function Best-First-Search(problem, Eval-Fn) returns sekvence øešení inputs: problem // problém Eval-Fn // vyhodnocovací funkce Queuing-Fn w funkce seøazující uzly pomocí Eval-Fn return General-Search(problem, Queuing-Fn)

Pozn.: Název “vyhledej první nejlepší” ve skuteènosti znamená jen to, že získáme uzel, ketrý se zdá být nejlepším (jinak by cesta k øešení byla snadná 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.

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í použitá míra v sobì 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í.

-60-

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 prvnì 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 opìt cestování z mìsta Arad do Bucharest. Mapka je stejná jako døíve, avšak pøídavná informace je zde k dispozici 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.

-61-

hSLD lze zde 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:

-62-

Pomocí heuristiky SLD se expanduje jako první uzel z Aradu do Sibiu, protože je bližší (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 expanse 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 positivum 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í expansi 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, což z hlediska heuristiky jsou zbyteèné expanse uzlù, 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í prvnì do hloubky v tom, ž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 také závisí na konkrétním problému. -63-

Minimalizace celkové ceny cesty: hledání A* 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é prvnì 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ž je 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).

-64-

Obrázek ukazuje nìkolik prvních krokù hledání A* pøi použití heuristiky hSLD. Za povšimnutí stojí, že A* preferuje expansi z Rimnicu Vilcea pøed expansí z Fagarasu. Pøestože Fagaras je blíže Bucharesti, cesta do Fagarasu není tak efektivní v pøiblížení se 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):

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í).

-65-

Pokud by heuristika nebyla monotónní, lze ji upravit na monotónnost: 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 fcena 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á, lze ve stavovém prostoru vytvoøit tzv. obrysy:

-66-

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í f-ceny nižší než je hodnota daného obrysu. 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—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).

-67-

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—uzel n je uzel na cestì k optimálnímu øešení G).

Ukážeme, že k uvedenému závìru—suboptimálnímu výbìru—nemùže dojít. Pøedpokládejme, že uzel n je v daném okamžiku listem na optimální cestì do G (nìjaký takový uzel musí existovat, ledaže by již cesta byla zcela expandována—zde by ovšem bylo vráceno G). Protože h je pøijatelná heuristika, pak: f * $ f(n). Dále, pokud n není vybrán pro expansi pøes G2, platí: f(n) $ f(G2). Z toho plyne: f * $ f(G2).

-68-

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). To je ale v rozporu s pøedpokladem, že G2 je suboptimální, takže A* nikdy nevybere pro expansi suboptimální cíl. Protože vrací jedinì øešení vybrané pro expansi, 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 expansi 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 pro to, že exponenciální nárùst se 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. Pozn.: pro A* není rozhodující èas, nýbrž pamì, protože udržuje v pamìti všechny generované uzly. -69-

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á h1 = 7; je to pøijatelná heuristika, protože každý chybnì umístìný ètvereèek musí být alespoò jednou posunut.

-70-

!

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.

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. Pro 100 náhodnì vygenerovaných pozic hlavolamu s 8 ètvereèky (a za použití iterativního hloubkového hledání Iterative-Deepening-Search IDS s A*, h1 a h2) lze získat srovnání pro prùmìrné hodnoty poètu expandovaných uzlù: cena hledání

efektivní faktor vìtvení

d ID S

A * (h 1 )

A * (h 2 )

ID S

A * (h 1 )

A * (h 2 )

2

10

6

6

2.45

1.79

1.79

4

112

13

12

2.87

1.48

1.45

6

680

20

18

2.73

1.34

1.30

8

6384

39

25

2.80

1.33

1.24

10

47127

93

39

2.79

1.38

1.22

12

364404

227

73

2.78

1.42

1.24

14

3473941

539

113

2.83

1.44

1.23

16

—

1301

211

—

1.45

1.25

18

—

3056

363

—

1.46

1.26

20

—

7276

676

—

1.47

1.27

22

—

18094

1219

—

1.48

1.28

24

—

39135

1641

—

1.48

1.26

-71-

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:

Bylo již døíve uvedeno, že expandovány budou uzly, pro nìž 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, nebo 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é nalézt vlastnosti nutné pro øešení, což mùže pøispìt k heuristické vyhodnocovací funkci (v šachu k dosažení matu je zapotøebí mít urèitý poèet urèitých figur apod.). -72-

Algoritmy iterativního vylepšování Pro øadu tzv. dobøe definovaných problémù (8 dam, VLSI) 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 obvodu. Pak mùžeme pohybovat dámami ve snaze redukovat poèet vzájemného napadání, nebo pøemísovat 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):

-73-

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é nedostaky 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 w následný uzel s nejvyšší hodnotou if Value[next] < Value[current] then return current current w next end

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.

-74-

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.

-75-

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 minkonflikt ú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). -76-

Komunikace agentů Komunikací se zde rozumí úmyslná výměna informací pomocí vytváření a příjmu znamení, odvozených ze sdíleného systému konvenčních znamení. Lidé používají omezené množství konvenčních znamení (úsměv, potřásání rukou...) ve srovnání se zvířaty, na druhé straně vyvinuli komplexní, strukturovaný systém znamení, známý pod názvem jazyk, který jim umožňuje komunikovat o většině věcí, které znají o světě (prostředí, v němž se nacházejí). Přestože šimpanzi, delfíni a jiní savci používají slovník se stovkami znamení a mají schopnost je řetězit, lidé jsou jediní tvorové, kteří spolehlivě komunikují pomocí neomezeného množství kvalitativně odlišných zpráv. Turingův test schopnosti umělé inteligence je založen právě na použití jazyka.

Komunikace jako akce Agenti mohou mít jako jednu z dostupných akcí také schopnost produkovat jazyk. Tato činnost se nazývá akce řeči (komunikace), přičemž pojem “řeč” má význam “volná řeč”, nikoliv jen “mluvení”, takže k akci řeči se také počítá např. psaní, znaková řeč, apod. Z tohoto hlediska také pojem slovo má širší význam. Důvodem pro to, aby agent komunikoval při obvyklé činnosti je potřeba spolupráce s jinými agenty při řešení nějakého problému. Skupina agentů pak může kolektivně nebo individuálně získávat nějaké výhody, pokud může dělat např. něco z následujících činností: ! ! ! ! ! ! !

Informovat jeden druhého o části prozkoumaného světa, takže mají k dalšímu zkoumání menší část světa. Dotazovat se na konkrétní vlastnosti světa. Odpovídat na dotazy. Žádat (přikazovat) jiné agenty, aby vykonali nějakou akci. Slibovat provedení nějaké akce nebo nabízet podmínky. Potvrzovat žádosti a nabídky. Sdílet dojmy a zkušenosti (získané znalosti) s jinými.

124

Obtížné je pro agenta určit, kdy provést akci komunikace (aby komunikace byla opravdu zapotřebí) a jaká komunikační akce se má udělat. Z určitého hlediska se jedná o plánovací problém—agent si může vybrat ze souboru možných akcí a nějak musí otestovat, kterou akci vybrat k dosažení cíle (předání informace jinému agentovi). Všechny plánovací potíže se projevují i při výběru komunikační akce. Není např. možné plánovat konversaci na úrovni individuálních pohybů úst a jazyka, takže je nutné použít několik úrovní hierarchické abstrakce—přinejmenším slova, fráze a věty. Dalším problémem je nedeterminismus: příkaz/žádost jednoho agenta může nebo nemusí být proveden/provedena, takže je zapotřebí mít k dispozici podmíněné plány. Konversace se nedá naplánovat od začátku do konce, pouze je možné zkonstruovat obecný plán pro konversaci, vygenerovat první větu, pak počkat na vjem odpovědi, a reagovat na odpověď. Problém porozumění akce řeči je podobný jiným problémům porozumění (porozumění obrazovému vjemu, medicínské diagnóze, apod.). K dispozici je soubor nejednoznačných vstupů, z nichž je nutno zpětně vypracovat rozlišení stavu světa, který vstup vyprodukoval. Část problému porozumění je závislá na jazyku—je nutno znát syntaxi a sémantiku jazyka k pochopení důvodu, proč jiný agent vykonal konkrétní komunikační akci. Problém porozumění zahrnuje i obecnější problém rozpoznání plánu. Pozorování agenta, který se otáčí a pohybuje směrem ke zlatu, může vést k vytvoření závěru, že agent má jako cíl získat zlato. Podobný druh vytváření mentálního modelu se vyžaduje také v situacích, kdy se určitý agent otočí směrem ke zlatu a řekne: “Seberu to.” I když v okolí budou také jiné objekty, mělo by být jasné, že “to” zde znamená “zlato”. Část problému porozumění lze řešit pomocí logického usuzování (logické implikace jsou vhodným způsobem pro popis možností kombinovat slova a fráze na delší fráze). Jiná část problému se dá řešit technikami nejistého (přibližného) usuzování, např. fuzzy logikou aj. Obvykle existuje několik stavů světa, které všechny vedou k téže komunikační akci, takže příjemce zprávy musí rozhodnout, které stavy jsou pravděpodobnější. Uvedené záležitosti jsou spojeny s tzv. vědou zabývající se přirozenými záležitostmi—např. porozumění přirozenému jazyku a jeho zpracování. 125

Podstata jazyka V zásadě lze odlišovat formální jazyky—např. C++ a logika prvního řádu jsou rigidně definovány—a přirozené jazyky—např. čínština, angličtina, čeština, používané lidmi ke vzájemné komunikaci. Umělá inteligence využívá pro formální jazyky notaci v tzv. Backus-Naurově formě (BNF). Formální jazyk je soubor řetězců složených ze sekvencí symbolů, které jsou převzaty z konečné množiny terminálních symbolů. Určitou potíží při práci s formálními a přirozenými jazyky je velké množství různých formalismů a notací pro zápis gramatik—většina je však založena na myšlence frázové struktury, tj. řetězce jsou složeny z podřetězců zvaných fráze z různých kategorií (podstatná jména – noun phrases NP, slovesa – verb phrases VP, atd.). Fráze jsou vhodným prostředkem, jemuž lze přiřazovat významy (sémantika). Kategorizace frází napomáhá popsat přípustné řetězce jazyka. Lze říci, že jakákoliv fráze podst. jména NP může být kombinována (při dodržení určitých podmínek) se slovesnou frází VP pro vytvoření fráze z kategorie věta (sentence S). Bez těchto pojmů a pravidel by bylo velmi obtížné (nebo i nemožné) vysvětlit, proč např. “v zásadě lze odlišovat formální jazyky a přirozené jazyky” je věta a např. “odlišovat v a jazyky jazyky formální lze přirozené” věta není. V angličtině např. “the wumpus is dead” je věta a “wumpus the dead is” věta není. V různých jazycích existují ovšem různé gramatiky také vlivem odlišné podstaty (v angličtině je slovosled vázán mnohem přísnějšími pravidly než v češtině, takže přehození slov v češtině nemusí zrušit správnost kategorie věty, v angličtině však ano). Gramatické kategorie a pravidla jsou součástí jazykovědy. Kategorie typu NP, VP a S jsou neterminální symboly. V notaci BNF se přepisovací pravidla skládají z jednoho neterminálního symbolu na levé straně a sekvence terminálů či neterminálů na pravé straně. Význam pravidla typu S v NP VP

je v tom, že dává možnost vzít jakoukoliv frázi NP, připojit ji k jakékoliv frázi VP a výsledkem je fráze typu S.

126

Komponenty komunikace Typická komunikační episoda, kdy řečník (speaker) S chce sdělit proposici P naslouchajícímu (hearer) H pomocí slov (words) W, se skládá ze sedmi procesů. Tři procesy souvisejí s řečníkem: Intence: Generace: Syntéza:

S chce, aby H uvěřil P (typicky S sám věří P). S vybere slova W (protože vyjadřují význam P). S vysloví slova W (a obvykle je adresuje na H).

Čtyři procesy souvisejí s naslouchajícím: Percepce:

H vnímá W’ (ideálně W’ = W, ale je možné nějaké zkreslení vjemu apod.). Analýza: H inferuje, že W’ má možné významy P1, ... , Pn (slova a fráze mohou mít několik významů). Desambiguace: H inferuje, že S měl v úmyslu sdělit Pi (ideálně Pi = P, ale je možná chybná interpretace vjemu). Inkorporace: H se rozhodne uvěřit (přijmout) Pi (nebo Pi odmítne, pokud je mimo to, čemu již věří).

127

Předchozí obrázek ukazuje sedm procesů v kontextu příkladu (je použit příklad anglické fráze “The wumpus is dead”, přičemž “wumpus” byla kdysi jedna z prvních počítačových her, kde agent prohledává jeskyni skládající se z částí propojených chodbami—samotný wumpus byla bestie, skrývající se v některé části a sežrala každého, kdo k ní vlezl; navíc v některých částech byly bezedné šachty, do nichž bylo možno se propadnout, ovšem wumpus byl tak velký, že se do šachty nevešel, takže se nemohl propadnout; jediným zmírněním potíží byla občasná možnost nalézt hroudu zlata). Intence:

Z nějakého důvodu chce řečník sdělit něco potřebného naslouchajícímu—zde řečník S má důvod informovat H, že wupmus již dále není živ.

Generace:

S použije znalost jazyka k rozhodnutí, co a jak říci o daném faktu úmrtí wumpuse. Výběr slov a jejich uspořádání je zatím větší problém než inverse, tj. rozumět sdělení, protože dosud bylo věnováno větší úsilí pochopit sdělení než vygenerovat sdělení ve srozumitelné formě.

Syntéza:

Většina systémů umělé inteligence syntetizuje tištěný výstup, což je v podstatě triviální úloha. Syntéza řeči (aby zněla jako od člověka) nyní patří k populárním výzkumným úkolům. Na obrázku agent syntetizuje řeč pomocí řetězce zvuků přepsaného do jednoho z možných typů fonetické abecedy pro angličtinu: [thaxwahmpahsihzdeyd]. Detaily zde nejsou důležité; podstatné je, že syntetizované zvuky jsou něco odlišného od toho, co agent generuje. Fonetický řetězec je navíc nepřerušován mezerami, aby realizoval skutečnou rychlou řeč.

Percepce:

Je-li médiem řeč, pak krok percepce se nazývá rozpoznání řeči; je-li médiem tisk, pak jde o optické rozpoznání znaků. Obě oblasti se již staly běžnými počítačovými záležitostmi. Zde předpokládáme perfektní schopnost H přijmout a dekódovat slova ze zvuku.

Analýza:

Analýza zde má dvě hlavní části: syntaktickou interpretaci (rozbor) a sémantickou interpretaci. Sémantická interpretace zahrnuje jak porozumění významu slov, tak i pragmatickou interpretaci (znalost o současné situaci). Rozbor znamená proces přiřazování části jazyka (podstat128

né jméno, sloveso, atd.) každému ze slov ve větě a seskupením slov do frází. Jednou z možností je vytvoření stromu rozboru (viz předchozí obrázek). V tomto stromu vnitřní uzly representují fráze, hrany použití gramatických pravidel, a listy představují slova. Sémantická interpretace je proces získání významu výroku vyjádřeného v nějakém representačním jazyku. Na předchozím obrázku jsou dvě možné sémantické interpretace: wumpus je mrtev a wumpus je unaven (viz různé významy anglického slova dead). Výroky s několika možnými interpretacemi jsou tzv. nejednoznačné. Zde je použita logika pro representaci, ale používají se i jiné representace. Pragmatická interpretace je část sémantické interpretace, která bere do úvahy okamžitý stav—zde je konstanta Now (nyní) nahrazena jinou, S3, pro danou situaci. Desambiguace: Většina řečníků nemusí být úmyslně nejednoznačná, ale mnoho výroků přirozeného jazyka má několik legálních interpretací. Komunikace funguje proto, že H odhaduje, která interpretace odpovídá sdělení přijímanému od S. Desambiguace je založena na pravděpodobnosti a přibližném usuzování (vliv nejistoty). Analýza vytváří možné interpretace; desambiguace vybírá tu nejlepší. Inkorporace:

Zcela naivní agent může věřit všemu, co je mu sdělováno, ale důmyslnější agent zachází se slovy W a odvozenou interpretací Pi jako s přídavnými částmi uvažovanými spolu s dalšími.

Předpokladem komunikace je, že a) agenti používají stejný jazyk, b) sdílejí stejný kontext a c) jsou alespoň částečně racionální (aby správně reagovali na vjem řeči).

129

Dva modely komunikace K současným nejvýznamnějším směrům studia komunikace agentů patří způsoby změny representace “vnitřních názorů” agentů na slova, a naopak změny přijímaných slov na “vnitřní názory” agentů, kde vnitřní názor znamená znalost uloženou v nějaké vhodné formě v agentově znalostní bázi (znalostní bází se zde opět rozumí soubor representací faktů o světě—znalostní báze poskytuje odpovědi na dotazy např. přes dříve zmíněné funkce Tell a Ask v kapitole Plánování). Dva z existujících modelů jsou následující: 1.

Kódované zprávy: řečník S má na mysli určitou proposici P a zakóduje ji do slov (nebo nějakých jiných příznaků) W. Naslouchající H se pokusí dekódovat zprávu W k získání původní proposice P (např. Morseův kód—z teček a čárek, používaný kdysi pro výměnu zpráv). V tomto modelu se v ideálním případě přenáší původní význam z hlavy S prostřednictvím přenášené zprávy a interpretace H, aniž by došlo k jakékoliv změně obsahu. Změnu obsahu však může způsobit např. šum komunikačního kanálu nebo chyba při kódování/dekódování.

Limitace modelu kódovaných a dekódovaných zpráv vedla k jinému modelu: 2.

Situační jazyk: význam zprávy závisí jak na slovech, tak i na situaci v níž jsou slova vyslovena. Funkce kódování/dekódování zde mají navíc argument, který representuje konkrétní, okamžitou situaci. Souvisí to se skutečností, že tatáž slova mohou mít v různých situacích zcela různé významy: “Já jsem teď zde” znamená pro Pepu v Praze v pondělí něco zcela jiného než pro Frantu v úterý v Ostravě, apod. Situační jazykový model má rovněž možný zdroj selhání komunikace: mají-li S i H odlišné představy o aktuální situaci, pak nemusí být zpráva předána na základě původního úmyslu.

Agenti mohou také komunikovat dvěma různými způsoby: oba sdílejí společný vnitřní representační jazyk, nepotřebují tedy žádný externí jazyk. Jiní agenti nemusí splňovat žádný předpoklad o vzájemném vnitřním jazyku, ale sdílejí komunikační jazyk (např. podmnožinu angličtiny).

130

Komunikace pomocí Tell a Ask Při tomto typu komunikace agenti sdílejí tentýž vnitřní representační jazyk a mají přímý přístup ke svým znalostním bázím přes rozhraní Tell a Ask. Agent A může předat proposici P agentovi B pomocí Tell (KBB , “P”) stejně, jako by přidal P do své znalostní báze pomocí Tell (KBA , “P”). Obdobně A může zjistit, zda B zná Q pomocí Ask (KBB , “Q”). V umělé inteligenci, zabývající se uvedeným způsobem komunikace, se daný model nazývá telepatické spojení. Schématický diagram ukazuje modifikaci agentů (pro umožnění vzájemného přístupu ke svým znalostním bázím) přidáním vstup-výstupního zařízení ke KB, tj. navíc k potřebným zařízením pro vstup/výstup vjemů a akcí:

Lidé nemají schopnosti telepatické komunikace, takže uvedený způsob komunikace nemohou používat, ale je zcela možné naprogramovat skupinu robotů pomocí společné interní representace a vybavit je rádiovými nebo infračervenými propojeními pro přímý přenos vnitřní representace znalostí mezi jejich znalostními bázemi přes Tell a Ask. V takovém případě je nutné, aby agenti kromě stejného vnitřního formátu representace jazyka sdíleli mnoho symbolů. Některé symboly jsou statické: lze předem pevně stanovit význam (konstanty, popis neproměnné části světa, apod.). Jiné symboly jsou dynamické: vytvářejí je agenti tehdy, když začnou prozkoumávat svět. Se statickými symboly potíže nevznikají, ale obtížné bývá synchronizovat použití dynamických symbolů.

131

Tři potíže se synchronizací dynamických symbolů: 1.

2.

3.

Musí existovat takový postup přidělování názvů, aby A i B simultánně nezaváděli tentýž symbol pro věci s různým významem. Jednou možností je zavedení agentova jména jako indexu nově zaváděného symbolu, např. “At(HomeA)” znamená “doma u agenta A”. Je zapotřebí, aby existoval způsob stanovení relace pro symboly zavedené různými agenty, např. aby určitý agent byl schopen říci, zda PA1 a třeba PB2 znamená stejné místo nebo ne. Problém narůstá s počtem agentů. Není snadné uvést v soulad rozdíly mezi znalostními bázemi různých agentů. Pokud je komunikace volná a bezprostřední, pak všichni agenti mohou postupovat tak, že rozešlou sdělení o nové skutečnosti všem ostatním hned, jak se skutečnost dozví, takže každý bude mít stejnou znalost. V realitě je však taková komunikace omezená, např. šířkou pásma přenosu nebo tím, že nejsou neustále v propojení. Když se dostanou zpět do kontaktu, nastává problém s určením toho, co z nové informace stojí za komunikaci a která zajímavá fakta ostatní agenti znají.

Existuje přirozeně mnoho dalších problémů, např. telepatičtí agenti, jak byli popsáni, jsou zranitelní sabotáží (nějaký protřelý agent použije Tell k šíření lží a naivní agent všemu uvěří).

Komunikace pomocí formálního jazyka Z důvodů možnosti sabotáže a/nebo nemožnosti používat tentýž vnitřní jazyk komunikuje většina agentů pomocí jazyka než prostřednictvím přímého přístupu do znalostní báze. Následující diagram ukazuje typ komunikace pomocí jazyka: agenti provádějí akce, které produkují jazyk, který mohou ostatní agenti přijímat (vnímat). Externí komunikační jazyk se může samozřejmě lišit od interního representačního jazyka, a každý agent může mít rozdílný vnitřní jazyk. Nemusí se shodnout na žádném interním symbolu, pokud každý z agentů je schopen spolehlivě mapovat z externího jazyka do svých interních symbolů.

132

Externí komunikační jazyk s sebou přináší problémy spojené s generováním a analýzou, a řada výsledků výzkumu z oblasti zpracování přirozeného jazyka (NLP) se zde využívá. Nejobtížnější na komunikaci pomocí jazyka je stále problém č. 3 z předchozí podkapitoly: uvést rozdíly ve znalostních bázích agentů v soulad. To, co říká agent A a jak agent B interpretuje výrok od A, závisí velmi silně na vnitřních “názorech” obou agentů (včetně toho, jaký mají “názor” na “názor” toho druhého agenta). Znamená to, že agenti mající tentýž interní a externí jazyk nemusí mít potíže s generováním a analýzou sdělení, ale stále pro ně může být obtížné rozhodnout, co si navzájem sdělit. V dalších úvahách se předpokládá využití omezené podmnožiny angličtiny pro komunikaci agentů pomocí externího jazyka.

Formální gramatika pro podmnožinu angličtiny Nechť je pro komunikaci použita omezená podmnožina angličtiny g0 (např. pro komunikaci agentů ve zmíněném světě wumpus). Komunikační jazyk lze do značné míry popsat pomocí technik pro formální jazyky, např. využití pevné množiny písmen (pro psaný jazyk) nebo zvuků (pro mluvený jazyk). Symboly jsou formovány do řetězců, řetězce do frází apod. Ne celý jazyk lze takto popsat, protože např. není jasné, co vše do jazyka patří (existují dialekty, rozdíly např. v kanadské, britské, australské a americké angličtině, vznikají přirozené časové změny—angličtina ze středověku je odlišná od současné, přičemž obdobné záležitosti platí i pro jiné jazyky, definice lingvistů se mohou lišit, apod.). Kromě toho existuje mnoho negramatických výroků, kterým lze bez problémů porozumět.

133

Řada frází a vět nemusí být správných na vyšší gramatické úrovni, ale z části jsou správné, a pro různé mluvčí se mohou pohybovat od správného k nesprávnému; příklady z angličtiny: To whom did you send the letter? Next to whom did you stand? Of whom did you meet a friend? Of whom did you see the dealer that bought the picture that Vincent painted? Skutečně obtížnou částí zpracování přirozeného jazyka je sémantická interpretace (stanovení významu) a desambiguace (odstranění mnohovýznamnosti). V programovacích jazycích je v principu každé vyjádření příkazem, zatímco v přirozeném jazyce musí naslouchající rozpoznat, zda jde o příkaz, dotaz, sdělení, slib... Dále bude jako příklad použita formální definice jazyka g0. Lexikon g0 Lexikon je seznam povolených slov, která jsou seskupována do kategorií či částí řeči srozumitelné uživatelům slovníku: podst. jména, zájmena, názvy označují věci, slovesa označují události, příd. jména modifikují podstatná jména, a příslovce modifikují slovesa. Dalšími kategoriemi jsou členy (a, an, the), předložky (in, on, at, ...), a spojky (and, or, ...). Příklad ukazuje malý lexikon pro svět hry wumpus: podstatné jméno v stench | breeze | glitter | nothing | wumpus | pit | pits | gold | east | ... sloveso v is | see | smell | shoot | feel | stinks | go | grab | carry | kill | turn | ...

přídavné jméno v right | left | east | south | back | smelly | ...

příslovce v here | there | nearby | ahead | right | left | east | south | back | ... zájmeno v me | you | I | it | ...

název v John | Mary | Boston | Aristotle | ... člen v the | a | an | ...

předložka v to | in | on | near | ... spojka v and | or | but | ...

číslice v 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Každá kategorie v zobrazeném příkladu má na konci tři tečky ... k tomu, aby bylo zjevné, že existují i další slova v kategorii. Pro chybějící slova jsou dva důvody: 134

1) podst. jména, slovesa, příd. jména a příslovce: nelze je vyjmenovat všechny, protože je jich veliké množství v každé třídě a navíc jich neustále přibývá (např. slovo fax je běžně používáno teprve omezenou dobu); tyto čtyři kategorie tvoří tzv. otevřenou třídu. 2) Ostatní uvedené kategorie tvoří tzv. uzavřenou třídu: mají malý počet slov, které v principu lze vyjmenovat a mění se spíše během staletí než měsíců (např. zájmena thee a thou byla obecně užívána v 17. století, v 19. byla na ústupu a v současnosti je lze nalézt jen v poezii a některých regionálních dialektech). Gramatika g0 Slova je nutno kombinovat do frází. V g0 se použije pět neterminálních symbolů k definici různých druhů frází: věta S (sentence), fráze podst. jména NP (noun phrase), fráze slovesná VP (verb phrase), předložková fráze PP (prepositional phrase), a vztažná věta RelClause (relative clause)—následuje a modifikuje NP, např. The agent who gave me the gold is there. Například pro svět wumpus: S v NP VP |

S spojka S

NP v zájmeno

I + feel a breeze I feel a breeze + and + I smell a wumpus I

|

podst. jméno

|

člen podst. jméno the + wumpus

|

číslice číslice

34

|

NP PP

the wumpus + to the east

|

NP RelClause

the wumpus + that is smelly

VP v sloveso

pits

stinks

|

VP NP

feel + a breeze

|

VP příd. jméno

is + smelly

|

VP PP

turn + to the east

|

VP příslovce

go + ahead

PP v předložka NP RelClause v that VP

to + the east

that + is smelly

135

Syntaktická analýza (rozbor) Existuje mnoho algoritmů pro syntaktickou analýzu. Zde je uveden velmi jednoduchý algoritmus, který nedeterministicky vybírá jeden možný strom rozboru (parse tree), pokud existuje. Zpracovává seznam slov jako les rozborů (parse forest): uspořádaný seznam stromů rozboru. V každém kroku hlavní smyčky nalézá nějakou posloupnost elementů lesa, která odpovídá pravé straně některého gramatického pravidla. Pak nahradí posloupnost jednoduchým stromem rozboru, jehož kategorie je na levé straně pravidla a jehož potomci jsou uzly v původní posloupnosti:

Pro ukázku je uvedeno, jak by rozbor probíhal pro řetězec “the wumpus is dead”:

(Detailní informace o využívání gramatiky poskytuje oblast NLP.) 136

Sémantická interpretace Sémantika formálních jazyků je na rozdíl od jazyků přirozených poměrně snadná. Není obtížné zjistit význam zápisů “X+Y” v aritmetice nebo “X v Y” v logice, protože mají tzv. kompoziční sémantiku: sémantika libovolné fráze je funkcí sémantiky sub-frází; nezáleží na jakékoliv jiné frázi před, po nebo zahrnuté v dané frázi. Je-li znám význam X a Y (a také +), pak je jasný význam celé fráze. Mimo jednoduchý jazyk aritmetiky nebo logiky je situace mnohem složitější. Např. v nějakém programovacím jazyku může mít výraz “10+10” sémantickou interpretaci 4, pokud se výraz vyskytne v delším řetězci: Base(2); x w 10+10; Ovšem i zde lze obhájit kompoziční sémantiku, pokud se vyjde z tvrzení, že sémantická funkce asociovaná s “x+y” je sečíst x a y pro daný číselný základ. Velkou výhodou kompoziční sémantiky je totéž jako u tzv. bezkontextových gramatik: umožňuje zpracovávat nekonečnou gramatiku pomocí konečné (a často malé) množiny pravidel. Z povrchního pohledu by se zdálo, že přirozené jazyky nemají kompoziční sémantiku. Ve frázi “The batter hit the ball” (pálkař trefil míček) lze očekávat sémantickou interpretaci slova “batter” jako “někdo, kdo máchá pálkou” a “ball” jako “sférický sportovní předmět”. Ale ve frázi “The chef mixed the batter to be served at the ball” (kuchař namíchal těsto tak, aby se podávalo jako kuličky) se dá očekávat, že dvě slova mají jiný význam. Z toho by se dalo usoudit, že “ball” a “batter” závisí nekompozičně na okolním kontextu. Tyto sémantické interpretace jsou však pouze předpokládané a preferované, nikoliv jediné možné. Slovo “ball” také znamená “ples, bál”. Je zcela možné, že “The batter hit the ball” se vztahuje k tomu, že směs koláčů vypadala velkolepě na formálním tanci—při dostatečném úsilí lze vytvořit příběh, kde uvedený význam je preferovaný. Shrnutí: Samotná sémantická interpretace nemůže zajistit správnou interpretaci fráze nebo věty. Kompoziční přístup je v moderních systémech zabývajících se přirozenými jazyky jeden z nejpoužívanějších.

137

Je ale zapotřebí použít dva kroky: sémantická interpretace odpovídá za kombinaci významů kompozičně tak, aby byly získány možné interpretace, a desambiguace (odstranění nejednoznačnosti) odpovídá za výběr nejlepší interpretace. Sémantika výrazu “John loves Mary” Následující popis se týká vytvoření gramatiky pro velmi malou podmnožinu angličtiny. Prvním krokem je stanovení faktů—jaké sémantické representace s kterými frázemi mají být asociovány. Bude použita jednoduchá věta “John loves Mary” asociována se sémantickou interpretací Loves(John,Mary). Ve větě je snadné vidět, z kterých slov pocházejí které části sémantické interpretace. Komplikovanější částí je rozhodnutí, jak ty části dát dohromady, zejména pro mezifráze typu VP “loves Mary”, kde VP je slovesná fráze. Sémantická interpretace dané fráze není ani logický výraz, ani kompletní logická věta. Intuitivně, “loves Mary” je popis, který lze nebo nelze aplikovat na konkrétní osobu (v tomto případě se vztahuje k osobě John). Znamená to, že “loves Mary” je predikát, který v kombinaci s termem representujícím osobu (která miluje) dává kompletní logický výraz. Za použití 8-notace lze representovat “loves Mary” jako predikát:

8x Loves(x, Mary). (8-operátor se používá k zápisu funkce z výrazu, např. výraz x2-y2 se přepíše na 8x,y x2-y2, např. (8x,y x2-y2)(25, 24) = 252-242 =49; funkce popisuje, co jsou argumenty a že se má udělat rozdíl druhé mocniny prvního a druhého argumentu; viz případně i jazyk Lisp.) NP “Mary” lze representovat logickou konstantou Mary. To vede k definici pravidla “NP se sémantikou obj následováno VP se sémantikou rel dává větu S, jejíž sémantika je výsledkem aplikace relace rel na objekt obj”: S(rel(obj)) v NP(obj) VP(rel) Pravidlo říká, že sémantická interpretace “John loves Mary” je (8x Loves(x, Mary))(John) což je ekvivalentní Loves(John,Mary).

138

Protože slovesné fráze VP jsou representovány jako predikáty, je vhodné konsistentně representovat rovněž slovesa jako predikáty. Slovo “loves” je representováno jako

8y 8x Loves(x,y), což je predikát, který s argumentem y = Mary vrací predikát 8x Loves(x, Mary). Pravidlo VP v Verb NP (verb phrase=slovesná fráze, verb=sloveso) aplikuje predikát [který je sémantickou interpretací slovesa na objekt, který je sémantickou interpretací NP (noun phrase=podstatné jméno)] k získání sémantické interpretace celé slovesné fráze VP. Gramatika a strom rozboru (se sémantickými interpretacemi pro řetězec “John loves Mary”) jsou následující: S(rel(obj)) v NP(obj) VP(rel) VP(rel(obj)) v Verb(rel) NP(obj) NP(obj) v Name(obj) Name(John) v John Name(Mary) v Mary Verb(8x 8y Loves(x,y)) v loves

139

Nejednoznačnost a její odstraňování Nejednoznačnost (ambiguita) a její odstraňování (desambiguace) hraje výraznou roli v procesu komunikace (interpretační fáze). V ideálním případě má řečník S na mysli sdělení P a provede akci mluvení, která však může mít několik interpretací, a je otázkou, kterou z interpretací lze v dané situaci považovat za nejlepší vzhledem k předávání výroku P. Naslouchající H si je možné nejednoznačnosti vědom a P interpretuje—odstraňuje víceznačnost. Někdy může H být zmaten a požádat o vyjasnění, to ale při častém opakování vede ke zdržování komunikace, zejména pokud dojde k dalšímu, vícenásobnému “vyjasňování vyjasňovaného”. Existuje velmi mnoho narušení plynulé komunikace, ale ukazuje se, že největším problémem je to, že většina toho, co je vyřčeno, je nejednoznačné. Typickým příkladem jsou např. titulky zpráv (známým příkladem je novinový titulek z doby druhé světové války: Americans pushes bottle up Germans: i z hlediska překladu nelze přesně říci, co je významem—např. bottle může znamenat láhev, odvaha, otýpka, a nahromadění nejednoznačných pojmů do fráze činí interpretaci často nemožnou). Lexikální ambiguita je nejjednodušším typem ambiguity, kde nějaké jedno slovo má více významů. Např. anglické přídavné jméno hot znamená horký, kořeněný, nejnovější, nesnesitelný, dychtivý, rozčilený, skvělý, čerstvý, radioaktivní, sexy, populární, ukradený aj. (v kterémkoliv přirozeném jazyce lze nalézt obdobné příklady). Lexikální ambiguita zahrnuje také nejednoznačnost kategorie slova: back je příslovce v go back, přídavné jméno v back door, podstatné jméno v the back of the room, a sloveso v back up your files. Syntaktická ambiguita (strukturální ambiguita) se může vyskytnout jak s lexikální nejednoznačností, tak i bez ní. Např. I smelled a wumpus in 2,2 (kde 2,2 znamená označení koordinát výskytu wumpuse v dané hře) má dva výsledky rozboru: v jednom propoziční fráze modifikuje podstatné jméno, v druhém modifikuje sloveso. Syntaktická ambiguita vede k další ambiguitě, k sémantické. Sémantická ambiguita v uvedeném příkladu znamená, že buď wumpus je v 2,2 a je odtud cítit nebo zápach je cítit v 2,2 a wumpus je někde jinde (cítil jsem (wumpuse v 2,2) nebo (v 2,2 jsem cítil) wumpuse). Zde by chybná interpretace mohla být osudovou chybou vzhledem k zaměření wumpuse. Rovněž může dojít k tomu, že se sémantická nejednoznačnost objeví i ve frázích, kde není lexikální nebo syntaktická ambiguita. Např. fráze coast road (pobřežní silnice) může znamenat silnici vedoucí po pobřeží nebo silnici vedoucí k pobřeží.

140

Referenční ambiguita je všudypřítomná forma nejednoznačnosti. Anaforické (odkazové na předchozí kontext) výrazy typu it se mohou odkazovat téměř na vše. Referenční ambiguita se vyskytuje v komunikaci proto, že přirozené jazyky obsahují v silně převažující míře slova pro kategorie, nikoliv pro individuální objekty [neexistuje slovo pro the-apple-I-had-for-lunch-today (jablko, které jsem měl dnes k obědu), pouze kategorie typu apple (jablko)]. Pragmatická ambiguita se objevuje tehdy, když promlouvající S a naslouchající H se neshodnou na tom, co je okamžitá situace. S říká “setkám se s tebou příští čtvrtek” za předpokladu, že se mluví o 12. dni měsíce, ale H si myslí, že se jedná o 19., takže dojde k chybné komunikaci. Jiný příklad je výše v podkapitole Dva modely komunikace ve zmínce o situačním jazyku (slovo “zde”). Lokální ambiguita se někdy objevuje ve frázi či větě, kde lze udělat rozbor podřetězce několika způsoby, ale pouze jeden z nich se shoduje s širším kontextem celého řetězce. Např. v programovacím jazyce C je význam řetězce “*c” buď “pointer na c”, pokud se řetězec vyskytuje v deklaraci char *c; nebo “vynásob hodnotou c” pokud se vyskytuje ve výrazu “2*c”. Podobně v angličtině je podřetězec “the radio broadcasts” fráze NP v širším kontextu “the radio broadcasts inform”, zatímco v jiném kontextu “the radio broadcasts information” jde o frázi NP “the radio” následovanou další frází VP “broadcasts information” (broadcasts je vysílání jako podstatné jméno v množném čísle nebo vysílá jako sloveso, tj. rozhlasová vysílání informují nebo rozhlas vysílá informace). Fráze či věta může být syntakticky nejednoznačná, ale sémanticky jednoznačná. Např. “S1 a S2 a S3” má dva různé rozbory “(S1 a S2) a S3” a “S1 a (S2 a S3)”, ale stejný význam vzhledem k asociativnosti konjunkce a (to ale nemusí být obecně platné a může záležet na typu jazyka a gramatiky). Vágnost (ve smyslu nejasnost, neurčitost, nejistota) je v přirozených jazycích obvyklá. Výrok “Venku je horko” se týká teploty, ale termín “horko” je vágní, takže je možná vcelku široká interpretace (pro někoho je venku horko při 25/C, pro jiného při 32/C, apod.). Nejednoznačnost může vyplynout i z typu akce řeči: Na dotaz “Víš, kolik je hodin?” odpoví H “ano” nebo může odpovědět hodnotou času, např. “půl sedmé a tři minuty”. Obojí může být pro tentýž dotaz správné, ovšem v závislosti na typu otázky (a např. kontextu, apod.).

141

Desambiguace Desambiguace je v principu problém diagnózy, tj. rozboru a rozpoznání. Naslouchající H si udržuje model světa a na základě vyslechnutí nové akce řeči přidá možné interpretace toho, co slyšel, k modelu jako hypotézy. K interpretacím lze využít různé techniky zpracování nejistoty a přibližnosti (logika monotonická a nemonotonická, pravděpodobnosti, shlukování, stochastická simulace, Bayesovy metody, tvorba a zpracování pravidel, Dempster-Shaferova metoda, znalostní inženýrství, fuzzy usuzování, aj.). K úspěšnému výsledku je zapotřebí, aby svět obsahoval co nejvíce informací o světě. Např. ke korektnímu vyřešení syntaktické ambiguity v anglické větě “Joseph saw the Grand Canyon flying to New York” (Josef viděl Grand Canyon při letu do New Yorku) je nutno vědět, že je mnohem pravděpodobnější, že Josef—a nikoliv Grand Canyon—letěl letadlem (a tedy že Josef neviděl Grand Canyon letící do New Yorku). Je také zapotřebí mít dobrý model o názorech S a H, aby se dalo uřčit, co měl S v úmyslu říci. Např. obvyklá interpretace anglického sdělení “I am not a crook” je, že “nejsem zloděj”, i když lze sdělení také přeložit jako “nejsem pastýřská berla”. Podobně slovo “bank” znamená mj. “břeh, lavice, banka”, ale je značně pravděpodobné, o co jde ve výroku “Jimmi keeps his money in the bank”, tj. Jimmi asi nezahrabává své peníze do břehu (i když i to je možné). Desambiguace obecně vyžaduje kombinaci čtyř modelů: 1. 2.

3. 4.

Model světa: pravděpodobnost výskytu faktu ve světě. Mentální model: pravděpodobnost, že řečník S má úmysl sdělit fakt naslouchajícímu H, a to za předpokladu, že k výskytu faktu došlo (je vhodné uvážit i případy, kdy k faktu nedošlo a S o tom nemá správnou informaci nebo úmyslně lže). Zde se rovněž kombinuje model názorů S s modelem toho, jaký má S názor na názory H, atd. Model jazyka: pravděpodobnost toho, že bude zvolen určitý řetězec slov za předpokladu, že S má intenci komunikace o určitém faktu. Akustický model: pravděpodobnost vygenerování konkrétní sekvence zvuků za předpokladu, že S vybral daný řetězec slov (problém obecně souvisí s řešením úloh v oblasti příjmu a vysílání signálů—zpracování visuálních a sluchových vjemů, jejich zpracování, vytváření a předávání—to je mimo rozsah předmětu).

142

Zcela jistým a posledním důvodem, proč správná interpretace je tak velmi obtížný problém, je skutečnost, že může existovat několik správných interpretací. Např. vtipy jsou často založeny na tom, že H se pobaví pomocí dvou současně platných interpretací. Většina programů, schopných porozumění, zatím ignoruje tyto skutečnosti (možnost současného výskytu několika případů). Bezkontextové gramatiky neposkytují příliš užitečný jazykový model, protože gramatika neříká, který řetězec je pravděpodobnější než jiný—prostě dělí řetězce do dvou tříd: gramatické a negramatické. Nejjednodušší formou je poskytnout pravděpodobnostní rozdělení pomocí pravděpodobnostní bezkontextové gramatiky (tzv. PCFG—probabilistic contextfree grammar). V jazykovém modelu PCFG má každé přepisovací pravidlo asociovanou pravděpodobnost, a součet pravděpodobností pro všechna pravidla, mající tutéž levou stranu, je 1. Např.: S v NP VP S v S konjunkce S

(0.9) (0.1).

V modelu PCFG je pravděpodobnost řetězce, P(words), pouhou sumou pravděpodobností jeho stromů rozboru (parsing trees)—jeden strom pro jednoznačný řetězec, žádné stromy pro negramatický řetězec a několik stromů pro nejednoznačný řetězec. Pravděpodobnost daného stromu je součinem pravděpodobností všech pravidel, která tvoří uzly stromu. Problémem PCFG je bezkontextovost, neboli rozdíl mezi např. P(“I ate a banana”) a P(“I ate a bandana”) [tj. “jedl jsem banán” a “jedl jsem šátek” (bandana je typ barevného bavlněného nebo hedvábného šátku)], záleží výhradně na P(“banana”) versus P(“bandana”), a nikoliv na relaci mezi slovesem “ate” a odpovídajícími podstatnými jmény. K získání takového vztahu je zapotřebí nějaký druh kontextově závislého modelu. Pozn.: V současnosti zřejmě převažují pravděpodobnostní techniky desambiguace, které vycházejí z existence tzv. textových korpusů, z nichž se odvozují příslušné statistiky a pravděpodobnosti. Existují i korpusy pro český jazyk. Samozřejmě záleží na tom, kdy a z čeho je korpus sestavován a jak je rozsáhlý, takže různé korpusy mohou vést k více čí méně odlišným výsledkům.

143

Plánování jako logické fungování Agent m$åe na základ struktury problému vytvoit sloåité plány své þinnosti. Jednoduchý plánující agent je velmi podobný agentovi ešícímu problémy (zmín nému díve) v tom, åe konstruuje plány k dosaåení svých cíl$, a po vytvoení plán$ je provede. Další, tzv. þásteþn uspoádané plánování, je komplikovan jší, prohledává prostor plán$, aby našlo plán zaruþující úsp ch. Zde je zárove navíc flexibilita, umoåující zvládnout zcela sloåité domény.

Jednoduchý plánující agent Pokud je stav sv ta pístupný, m$åe agent pouåít vjemy poskytované okolím (prostedím) k vytvoení kompletního a korektního modelu okamåitého stavu sv ta. Potom m$åe vzhledem k cíli vyvolat vhodný plánovací algoritmus (Ideal-Planner) k vytvoení plánu þinností. Plán je vykonáván po krocích, jedna akce v jednom þasovém kroku. Agent pouåívá znalostní bázi. Algoritmus (vyuåívající bázi znalostí) pro jednoduchého plánujícího agenta: function Simple-Planning-Agent(percept) returns action static:

KB // znalostní báze, obsahuje popis akcí p // plán (na poþátku åádný plán) t // þítaþ þasových krok, na poþátku 0

local variables:

// cíl G current // popis okamåitého stavu

Tell(KB,Make-Percept-Sentence(percept,t)) current Z State-Description(KB,t) if p = NoPlan then G Z Ask(KB,Make-Goal-Query(t)) p Z Ideal-Planner(current,G,KB) if p = NoPlan or p is empty then action Z NoOp else action Z First(p) p Z Rest(p) Tell(KB,Make-Action-Sentence(action,t)) t Z t+1 return action

91

Funkce Tell zde vkládá do znalostní báze KB informaci o tom, co se objevilo jako vjem (k þemu po sd lení údaj$ znalostní bázi pak dojde, je záleåitost inference). Make-Percept-Sentence dostane pro daný þasový okamåik t vjem (percept) a vrací representaci vjemu (fakt$ o sv t ); individuální representace fakt$ se nazývají sentence nebo tvrzení—tato (logická) tvrzení jsou vyjádena v jazyku, kterému znalostní báze rozumí, tj. jazyk representace znalosti. Funkce Ask se ptá znalostní báze, jaká akce (po sd lení pes Tell, jaká je okamåitá situace) by se pro daný stav m la ud lat. Jde tedy o jakýsi dialog typu poskytnutí informace o skuteþnosti (Tell)—dotaz co za t chto podmínek d lat (Ask). Funkce State-Description dostane vjem jako vstup a vrací popis poþáteþního stavu ve formátu vyåadovaném plánovaþem (generátorem plán$). Funkce Make-Goal-Query je pouåita v dotazu v$þi znalostní bázi na to, co by m lo být dalším cílem agenta. Ideal-Planner m$åe být jakýkoliv vhodný plánovaþ (viz dále).

Od ešení problém$ k plánování Plánování a ešení problém$ povaåuje moderní um lá inteligence za odlišné záleåitosti, protoåe representace cíl$, stav$, akcí a sekvencí akcí jsou odlišné. ešení problém$ zaloåené na vyhledávání:

Representace akcí: akce jsou popsány programy, které generují popisy následných stav$. Representace stav$: je dán kompletní popis poþáteþního stavu; akce jsou representovány programem, který generuje kompletní popisy stav$. Proto jsou všechny representace stav$ kompletní. Ve v tšin problém$ je stav jednoduchá datová struktura—permutace þtvereþk$ v hlavolamu s 8 þtvereþky, pozice agenta v problému hledání trasy, nebo pozice šesti osob v problému kanibal$ a misioná$ s lokou. Representace stav$ se pouåívají pouze pro generovaní následník$, pro heuristickou vyhodnocovací funkci a pro testování cíle. 92

Representace cíl$: jediná informace, kterou má ešící agent o svém cíli, je ve form testu na cíl a heuristické funkci. Oba prostedky mohou být aplikovány na stavy k rozhodnutí, zda jsou stavy vhodné þi potebné, ale zárove jsou oba prostedky pouåívány ve form “þerné skíky” (agent ešící problém nemá moånost se podívat dovnit nástroje pi výb ru akcí, které mohou být uåiteþné z hlediska dosaåení cíle). Representace plán$: pi ešení problém$ jsou výsledkem sekvence akcí typu “je z Aradu do Sibiu, dále do Fagarasu a pak do Buchuresti”. B hem konstrukce ešení uvaåují vyhledávací algoritmy pouze neperušené sekvence akcí vedoucích z poþáteþního stavu (pi obousm rném hledání akce konþící v koneþném stavu).

Jako píklad lze uvést návrh ešení, ovlivujících agentovu schopnost vyešit jednoduchý problém “získej litr mléka, trs banán$ a bezdrátovou vrtaþku s m nitelnou rychlostí otáþek”. Pro ešení je nutno specifikovat poþáteþní stav: agent je doma bez poåadovaných pedm t$, a soubor operátor$: vše, co agent m$åe d lat. Lze pípadn pouåít i n jakou heuristiku, nap. poþet pedm t$, které dosud nebyly získány. Na následujícím obrázku je velmi malá a symbolicky omezená þást prvních dvou úrovní prohledávaného prostoru pro ešení zadaného problému a náznak cesty vedoucí k cíli. Skuteþný faktor v tvení závisí na tom, jak jsou akce specifikovány (b mohou být tisíce nebo miliony), a délka ešení m$åe být v desítkách krok$—existuje píliš mnoho akcí a stav$. Heuristická vyhodnocovací funkce m$åe pouze vybrat mezi mnoha stavy k rozhodnutí, který stav je blíåe k cíli; neumí z úvah vylouþit akce. I kdyå se agent dostane do supermarketu, nezbývá mu, neå hádat. Agent pi pokusu o uhodnutí uvaåuje akce (koupit pomeranþe, rybu, brambory, mléko) a jejich ohodnocení evaluaþní funkcí (chybné, chybné, chybné, správné). Agent pak ví, åe koupit mléko je správná þinnost, ale nemá moånost zjistit, co ud lat pak a musí proces pokus$ zahájit znovu. K potíåím agenta tedy pispívá také fakt, åe musí vådy uvaåovat sekvenci akcí z poþáteþního stavu—musí tedy se naped rozhodnout, co ud lat v poþáteþním stavu, kde relevantní výb r mezi þinnostmi je jít na n jaké z mnoha moåných míst. Pokud agent neví, jak získat r$zné poloåky (zakoupení, zap$jþení, pronajatí, vyp stování, vyrobení, ukradení...), pak se nem$åe fakticky rozhodnout, kam jít. 93

Mluv na papouška Jdi do obchodu se zvíøaty

Zaèátek

Kup psa

Jdi do školy

Jdi do tøídy

Jdi do supermarketu

Kup rybu

Jdi spát

Kup mrkev

Èti si kníku

Kup mléko

Posaï se na idli

Atd. atd. ...

...

Konec

Seï nadále

...

Èti kníku

Z uvedených problém$ plyne, åe agent potebuje mnohem flexibiln jší zp$sob ke strukturalizaci svého uvaåování tak, aby mohl zpracovat kteroukoliv þást problému, která je—za pedpokladu okamåité informace—nejpravd podobn jší k vyešení. Základní a klíþová idea pro plánování je “otevení þerné skíky”, tj. representací stav$, cíl$ a akcí. Plánovací algoritmy pouåívají popisy ve formálních jazycích, nap. pomocí logiky prvního ádu (viz píslušnou kapitolu matematické logiky: výrazy, termy, konstanty, prom nné, predikáty, funkce, spojky <, Y, Z, @, kvantifikátory ~, }) nebo její podmnoåiny. Stavy a cíle jsou representovány soubory výraz$, akce jsou representovány logickým popisem pedpoklad$ a d$sledk$—to umoåuje agentovi pímé propojení mezi stavy a akcemi: Ví-li agent, åe cílem je konjunkce zahrnující konjunkt Mít(Mléko) a åe Koupit(x) docílí Mít(x), pak také ví, åe stojí za úvahu plán, v n må je Koupit(Mléko). Nemusí uvaåovat irelevantní akce jako jsou nap. Koupit(Šlehaþku) nebo JítSpát.

94

Další ideou plánování je skuteþnost, åe plánovaþ má volnost v pidávání akcí k plánu, kdykoliv jsou ty akce zapotebí—na rozdíl od postupu, kde se pouåívá inkrementální sekvence zaþínající v poþáteþním stavu. Nap. agent se m$åe rozhodnout, åe pouåije Koupit(Mléko), i kdyå ješt se nerozhodl kde, jak se tam dostat, nebo co d lat pak. Není nutná spojitost mezi poadím plánování a poadím uskuteþování. Prvn se stanoví rozhodnutí, která jsou “zejmá” nebo “d$leåitá”, a pak m$åe plánovaþ redukovat faktor v tvení pro budoucí výb ry a dále redukovat nutnost sledování všech libovolných rozhodnutí. Representace stav$ jako soubor$ logických výraz$ je podstatná, protoåe umoåuje tuto volnost výb ru: pidání akce Koupit(Mléko) má representaci stavu, kde se akce vykoná, jako Být_v(Supermarketu), coå ve skuteþnosti representuje celou tídu stav$: s banány a bez banán$, s vrtaþkou a bez vrtaþky, apod. Prohledávací algoritmy, vyåadující kompletní popis stav$, tuto moånost nemají. Poslední podstatnou ideou pro plánování je skuteþnost, åe v tšina þástí reálného sv ta je nezávislá na v tšin ostatních þástí. Proto je uskuteþnitelné vzít konjunktivní cíl typu “získej litr mléka Y trs banán$ Y vrtaþku...” a ešit ho pomocí strategie “rozd l a panuj” (viz níåe potíåe s hlavolamy). První dva konjunkty vyeší sub-plán obsahující cestu do supermarketu, další subplán (jít do åelezáství nebo p$jþit si u souseda) vyeší spln ní tetího konjunktu. Sub-plán zahrnující supermarket lze dále rozd lit na sub-plán koup mléka a subplán koup banán$. Sjednocením všech sub-plán$ dohromady je ešen celý problém. Funguje to práv z d$vodu velmi malé interakce mezi dv ma sub-plány: cesta do supermarketu nepekáåí p$jþce od souseda, koup mléka nepekáåí koupi banán$ (pokud samozejm agent nevyþerpá n jaké zdroje k provád ní akcí, nap. po koupi mléka namá na banány). Strategie rozd l a panuj je úþinná proto, åe je tém vådy snadn jší ešit problém rozd lením na menší podproblémy. M$åe selhat v pípadech, kdy cena kombinací ešení všech podproblém$ je píliš vysoká. Tuto vlastnost má mnoho hlavolam$, nap. 8-hlavolam má cílový stav, který je konjunktivním cílem: pesunout þtvereþek 1 na pozici A ; þtvereþek 2 na pozici B ; ... aå do þtvereþku 8. Z hlediska plánování lze pouåít rozd lení na nezávislé sub-problémy, ale potíå s hlavolamy je práv v obtíånosti dát sub-plány dohromady k dosaåení cíle (1 lze pesunout na A, ale 2 na B m$åe vyåadovat odsunutí 1 z A). 95

Plánování v situaþním kalkulu Problém plánování je v tomto pípad pedstavován logickými výrazy (pouåívá se logika prvního ádu), které popisují ti hlavní þásti problému:

Poþáteþní stav: libovolný logický výraz o situaci S0. Pro problém nákupu to m$åe nap. být:

Být_v(Doma,S0 ) Y ¬Mít(Mléko,S0) Y ¬Mít(Banány,S0) Y ¬Mít(Vrtaþka,S0)

Cílový stav: logický dotaz na vhodné situace s, nap.:

} s Být_v(Doma,s) Y Mít(Mléko,s) Y Mít(Banány,s) Y Mít(Vrtaþka,s)

Operátory: soubor popis$ akcí a pomocí logiky prvního ádu, nap.:

~ a,s Mít(Mléko,Result(a,s))

@ Z

[(a = Koupit(Mléko) Y Být_v(Supermarket,s) (Mít(Mléko,s) Y a =/ Vylít(Mléko))]

Pozn.: Situaþní kalkul je zaloåen na myšlence, åe akce m ní stavy: Result(a,s) pojmenovává situaci vzniklou po provedení akce a v situaci s. Pro úþely plánování m$åe být uåiteþné manipulovat se sekvencemi akcí stejn jako s jednotlivými akcemi. Result'(l,s) znamená situaci vzniklou provedením sekvence akcí l poþínaje situací s. Result' je stanoven tím, åe prázdná sekvence akcí nemá vliv na situaci, a výsledkem neprázdné sekvence akcí je totéå jako aplikace první akce a pak zbytku akcí z poþáteþní situace. Problém s dobrými teoretickými ešeními a formálními zápisy je þasto v tom, åe nezaruþují dobrá praktická ešení (k nimå um lá inteligence ovšem sm uje—to byl i d$vod vzniku oboru). D$vodem je nap. exponenciální þasová závislost na délce ešení (v nejhorším pípad ), nebo existující problémy s logickou inferencí (nap. modus ponens) pro adu reálných problém$, nap. z d$vodu odlišnosti zp$sobu uvaåování lidí od formáln logického pístupu (problém typický pro mnoho aplikací expertních systém$). Další potíå pro um lou inteligenci zp$sobuje problém tzv. semi-rozhodnutelnosti, vztahující se k výsledk$m inference v logice prvního ádu: lze ukázat, åe výrazy vyplývají z premis, pokud z nich vyplynuly—ale nem$åeme vådy ukázat, åe vyplynou, pokud z nich nevyplynuly (detaily viz v píslušných kapitolách matematiky). 96

Základní representace pro plánování Aby plánování agent$ bylo pouåitelné v praktických situacích, um lá inteligence pouåívá dva speciální pístupy: (1) (2)

Restrikce jazyka pro definici problém$—výsledkem je mén moåných ešení, mezi nimiå je nutno hledat. Pouåití specialisovaného algoritmu plánovaþ místo obecn zam eného algoritmu dokazování teorém$ pro nalezení ešení problému.

Oba pístupy jsou spojeny: nový definiþní jazyk vyåaduje nový plánovací algoritmus pro zpracování popisu problému daného jazykem. V souþasnosti se pro velkou v tšinu plánovaþ$ vyuåívá jazyk zvaný Strips (STanford Research Institute Problem Solver). Stavy ve Strips jsou representovány konjunkcemi funkþn nezávislými základními literály, tj. predikáty aplikovanými na konstatní symboly, s pípadnou negací. Nap. poþáteþní stav problému s mlékem apod. m$åe být popsán jako Být_v(Doma) Y ¬Mít(Mléko) Y ¬Mít(Banány) Y ¬Mít(Vrtaþka) Y ... Popis stav$ nemusí být úplný—neúplný popis (získaný nap. agentem v ne zcela pístupném prostedí) odpovídá mnoåin moåných kompletních stav$, pro n å by agent cht l získat úsp šný plán. Mnoho plánovacích systém$ pouåívá konvenci, která v pípad , åe popis stavu nezmiuje daný positivní literál, povaåuje literál za negativní (v logickém programování je to “negace jako neúsp ch”). Cíle jsou rovn å popisovány jako konjunkce literál$: Být_v(Doma) Y Mít(Mléko) Y Mít(Banány) Y Mít(Vrtaþka). Cíle mohou také obsahovat prom nné. Nap. cíl být v obchod , který prodává mléko m$åe být representován jako Být_v(x) Y Prodávat(x,Mléko).

97

Prom nné mohou být existenþn kvantifikované. Zde je ale rozdíl mezi cílem pro plánovaþ a dotazem pro dokazovaþ teorém$. Plánovaþ vyåaduje sekvenci akcí, která vede ke spln nému cíli, pokud je provedena. Dokazovaþ vyåaduje údaj o tom, zda dotazovací sekvence je pravdivá za pedpokladu pravdivosti výrok$ ve znalostní bázi.

Representace akcí Operátory Strips se skládají ze tí þástí:

Popis akce agent vrací prostedí (aby n co ud lal). Plánovaþ pouåívá popis jenom jako název moåné akce. Pedpoklad je konjunkce atom$ (positivních literál$), která íká, co musí být pravdivé ped aplikací operátoru. Úþinek (efekt) operátoru je konjunkce literál$ (positivních nebo negativních), která popisuje, jak se situace m ní pi aplikaci operátoru.

Píklad syntaxe pouåité pro vytvoení operátoru Strips pro pesun z jednoho místa na druhé: Op(Action: Go(there), Precond: (At(there) Y Path(here, there), Effect: At(there) Y ¬At(here)) Grafická notace pro Go(there). Pedpoklad je nad akcí, efekt pod akcí:

At(here), Path(here, there) Go(there) At(here)

L

At(there),

Operátor s prom nnými se nazývá operátorové schéma, protoåe neodpovídá jediné proveditelné akci, nýbrå skupin akcí, kde kaådá je r$znou instancí (specifickým výskytem) prom nných. Obvykle lze provád t pouze operátory s úplnou moåností specifikace (plánovací algoritmy musí zajistit, aby kaådá prom nná m la hodnotu v okamåiku þinnosti plánovaþe). 98

Pedpoklady musí být konjunkcí positivních literál$. Efekt musí být konjunkcí positivních a/nebo negativních literál$. O všech prom nných se pedpokládá, åe jsou universáln kvantifikovatelné a åe nejsou åádné pídavné kvantifikátory (tyto poåadavky mohou být za urþitých okolností zmírn ny). Operátor o je aplikovatelný ve stavu s pokud existuje n jaký zp$sob specifikace prom nných v operátoru o tak, åe kaådý pedpoklad o je pravdivý v s (tj. kdyå Precond(o) / s). Ve výsledném stavu platí všechny positivní literály v Effect(o) tak, jako platí všechny literály platné v s, krom t ch, které jsou negativními literály v Effect(o). Nap. pokud poþáteþní situace zahrnuje literály At(Doma), Path(Doma, Supermarket), ... pak akce Go(Supermarket) je aplikovatelná a výsledná situace obsahuje literály ¬At(Doma), At(Supermarket), Path(Doma, Supermarket), ...

Prostor situace a prostor plánu Na obrázku stromu v tvení þinností pi poåadavku na obstarání mléka apod. je ilustrován prohledávací prostor situací ve sv t (zde sv t nakupování). Cesta tímto prostorem z poþáteþního do cílového stavu vytváí plán pro problém nákupu. Plánovaþ, který daný prostor prohledává z hlediska moåných situací, je plánovaþ situaþního prostoru. Zárove jde o progresívní plánovaþ, protoåe hledá sm rem vped z výchozího stavu do cílového. Hlavním problémem je vysoký faktor v tvení a tím velký rozm r prohledávaného prostoru. Jednou moåností pokusit se sníåit faktor v tvení je hledání zp tným sm rem (z cíle k poþátku)—tzv. regresní plánování. Takový pístup je moåný, protoåe operátory obsahují dosti informace k regresi z þásteþného popisu výsledného stavu k þásteþnému popisu stavu ped aplikací operátoru. Obecn není moåné tímto zp$sobem získat kompletní popis stav$, ale to není zapotebí. 99

Uvedený regresní pístup je åádoucí, protoåe v typických problémech má cílový stav pouze n kolik konjunkt$, kde kaådý z nich má jenom n kolik vhodných operátor$, zatímco poþáteþní stav obvykle má mnoho aplikovatelných operátor$ (vhodným operátorem rozumíme takový, který je vhodný pro cíl pokud cíl je efektem toho operátoru). Bohuåel zp tné hledání je komplikováno faktem, åe þasto je nutno dosáhnout konjunkce cíl$, nikoliv jen jednoho. To m$åe snadno vést k nekompletnosti, jejíå odstran ní však zase vede k vysoké neúþinnosti algoritmu. Alternativou je hledání pes prostor plán$ místo pes prostor situací. Znamená to, åe se zaþne s jednoduchým, nekompletním plánem—tzv. þásteþný plán. Dále jsou zvaåovány cesty k rozšíení plánu, dokud není nalezen kompletní plán ešící problém. Operátory v tomto hledání jsou operátory nad plány: pidání kroku; zavedení takového poadí, které vloåí n jaký krok ped jiný; specifikace dosud neomezené prom nné; apod. ešením je finální plán a cesta, která vede k dosaåení cíle, je irelevantní. Operace nad plány jsou ze dvou kategorií: Zdokonalovací operátory pidávají omezení k danému plánu—jednou z moåností pohledu na þásteþný plán je jako na representaci souboru kompletních, pln omezených plán$. Operátory zdokonalování eliminují n které plány z tohoto souboru, ale åádné nepidávají. Jakýkoliv jiný, neå zdokonalovací operátor, je operátor modifikaþní. N které plánovaþe pracují tak, åe konstruují potenciáln nekorektní plány a pak je “odlaují” pomocí modifikaþních operátor$. V dalším jsou popisovány jen operátory zdokonalovací.

Representace plán$ Pro prohledávání prostoru plán$ je zapotebí jejich representace. Jako píklad poslouåí jednoduchý problém: obutí si páru bot. Cílem je konjunkce sloåená z PraváBotaObuta Y LeváBotaObuta, poþáteþní stav nemá åádné literály.

100

K dispozici jsou þtyi operátory: Op(Action: PraváBota, Precond: PraváPonoåkaObleþena, Effect: PraváBotaObuta) Op(Action: PraváPonoåka, Effect: PraváPonoåkaObleþena) Op(Action: LeváBota, Precond: LeváPonoåkaObleþena, Effect: LeváBotaObuta) Op(Action: LeváPonoåka, Effect: LeváPonoåkaObleþena) ýásteþný plán pro daný problém má dva kroky: PraváBota a LeváBota. Otázka je, který krok se má ud lat jako první? Mnoho plánovaþ$ pouåívá pístup zvaný nejmenší závazek, podle n jå se má vybrat k þinnosti jen to, co je práv na starosti, a ostatní v ci nechat na pozd ji. To je pro hledání vhodná metoda, protoåe pi okamåitém výb ru n þeho, co není práv aktuální, m$åe dojít k chyb , která si pozd ji vynutí návrat. Plánovaþ s nejmenším závazkem by mohl poadí obou þinností (PraváBota a LeváBota) nechat nespecifikované. Tetím krokem je PraváPonoåka, a pi pidání k plánu je teba zajistit, aby tento cíl byl spln n ped zahájením pln ní cíle PraváBota. Vzhledem k levé bot to ale nehraje roli. Plánovaþ, který representuje plány, v nichå n které kroky jsou dávány do poadí (ped a po) vzhledem ke vzájemnému vztahu, piþemå jiné kroky do poadí dávány nejsou, se nazývá plánovaþ þásteþného poadí. Alternativou je plánovaþ úplného poadí, v jehoå plánech je jednoduchý seznam krok$. Plán s úplným poadím, který je odvozen z plánu P pidáním omezení na poadí, se nazývá linearisací P. Plánovaþe musí také brát ohled na vazby prom nných v operátorech. To v problému bot a ponoåek není ukázáno, ale nap. jedním z cíl$ m$åe být Mít(Mléko), a k dispozici nech" je akce Koupit(poloåka, obchod). Rozumným závazkem k výb ru této akce je poloåku svázat s Mlékem. Zde však není dán dobrý d$vod k vazb obchodu, takåe princip nejmenšího závazku ponechává výb r na pozd ji. Tato strategie pomáhá zbavit se špatných plán$ a vynechat celé v tve stromu. Pokud je kaådá prom nná vázána na konstantu, pak plán se nazývá pln konkretizovaný plán. 101

Plán je formáln definován jako datová struktura skládající se z t chto sloåek:

Soubor krok$ plánu. Kaådý krok je jeden z operátor$ pro daný problém. Soubor omezení pro uspoádání krok$. Kaådé omezení, urþující poadí, má formu Si y Sj, coå znamená “Si je ped Sj”, neboli krok Si musí n kdy pedcházet krok Sj (ale nikoliv bezprostedn ). Pozn.: notace A y B y C znamená (A y B) Y (B y C). Soubor omezení pro vazby prom nných. Kaådé omezení prom nné má formu v = x, kde v je prom nná n jakého kroku a x je bu konstanta nebo jiná prom nná. c Soubor píþinných propojení. Píþinné propojení Si  → S j znamená “Si dosáhne c pro Sj”. Píþinná propojení slouåí k záznamu úþelu/úþel$ krok$ v plánu: zde je úþelem Si dosáhnout pedpoklad pro Sj.

Ped zahájením jakéhokoliv zlepšování popisuje jednoduše poþáteþní plán nevyešený problém. Poþáteþní plán se skládá ze dvou krok$ Zaþátek (nebo Start) a Konec (nebo Finish), s omezením na poadí Zaþátek y Konec. Oba tyto kroky mají asociované prázdné akce, takåe kdyå dojde na provád ní plánu, jsou ignorovány. Krok Start nemá åádné pedpoklady a jeho efektem je pidání všech proposic pravdivých v poþáteþním stavu. Krok Konec má jako pedpoklad cílový stav a åádné efekty. Plánovaþe tedy mohou zaþít s poþáteþním plánem a manipulovat s ním, dokud nedojdou k plánu, jenå je ešením.Problém boty-a-ponoåky je definován díve uvedenými þtymi operátory a poþáteþním plánem, který lze zapsat takto:

Plan (Steps: { S1: Op(Action: Start), S2: Op(Action: Finish, Precond: PraváBotaObuta Y LeváBotaObuta)}, Orderings: { S1 y S2 }, Bindings: {}, Links: {}) Následující obrázek (a) ukazuje grafickou notaci popisující plány, podobn jako u individuálních operátor$. Další obrázek (b) ilustruje poþáteþní plán pro problém boty-a-ponoåky: 102

Zaèátek

Zaèátek

Poèáteèní stav Koncový stav

LeváBotaObuta, PraváBotaObuta

Konec

Konec

(a)

(b)

V þásti (a) jsou problémy definovány þásteþnými plány obsahujícími pouze kroky Zaþátek a Konec. Do poþáteþního stavu se vstupuje vlivem efektu kroku Zaþátek, cílový stav je pedpokladem kroku Konec. Omezení na poadí je ukázáno šipkami mezi bloky. V þásti (b) je poþáteþní plán pro problém boty-a-ponoåky. Následující obrázek ukazuje plán s þásteþným uspoádáním, který je ešením daného problému, a dále šest linearisací plánu: Plán èásteèného poøadí:

Start

Levá Ponoka

Pravá Ponoka

LeváPonokaObleèena PraváPonokaObleèena

Pravá Bota

Levá Bota

Plán úplného poøadí:

Start

Start

Start

Start

Start

Start

Pravá Pono.

Pravá

Levá Pono.

Pravá Pono.

Levá

Pono.

Levá Pono.

Levá

Levá

Pravá

Pravá

Pono.

Pono.

Pono.

Pono.

Pravá

Levá

Pravá

Levá

Bota

Bota

Bota

Levá Bota

Pravá Bota

Konec

Konec

Pono.

Pravá Bota

Levá

Pravá

Bota

Levá Pono.

Levá Bota

Pravá Bota

Levá Bota

Pravá

Konec

Konec

Konec

Konec

Bota

Pono.

Bota

LeváBotaObuta, PraváBotaObuta

Konec

Zde je vid t, åe plán þásteþného uspoádání je silný, protoåe umoåuje plánovaþi ignorovat výb ry, které nemají åádný vliv na korektnost plánu. S nar$stajícím poþtem krok$ roste poþet moåných výb r$ uspoádání exponenciáln .

103

ešení ešení je plán, který m$åe agent provést a který zaruþuje dosaåení cíle. Pro kontrolu, zda plán je ešením, by bylo nutno trvat na tom, åe pouze pln specifikované a zcela uspoádané plány mohou být ešeními. To je však nevyhovující ze tí d$vod$: (1)

(2) (3)

Pro problémy typu z posledního obrázku je plánovaþ$m pirozen jší vracet plán s þásteþným uspoádáním neå libovoln vybírat jednu z mnoha linearisací plánu. N kteí agenti jsou schopni provád t akce paraleln , takže dává smysl umoånit ešení s paralelními akcemi. Pi vytváení plán$, které mohou pozd ji být kombinovány s jinými plány pi ešení rozsáhlejších problém$, se vyplácí uchovávat flexibilitu poskytovanou þásteþným uspoádáním akcí.

Proto se umoåují þásteþn uspoádané plány jako ešení pi pouåití jednoduché definice: ešení je kompletní a konsistentní plán: Kompletní plán je ten, v n må kaådý pedpoklad kaådého kroku je dosaåen n jakým jiným krokem. Krok dosáhne pedpokladu, pokud pedpoklad je jedním z efekt$ kroku a pokud åádný jiný krok nem$åe zrušit platnost pedpokladu. Formáln ji vzato, krok Si dosáhne pedpokladu c kroku Sj pokud: 1. 2.

Si y Sj a c Effects(Si); neexistuje åádný krok Sk takový, åe (¬c) Effects(Sk), piþemå platí Si y Sk y Sj v n které linearisaci plánu. "

Konsistentní plán je ten, v n må nejsou åádné kontradikce v uspoádání nebo vázání prom nných. Kontradikce vznikne, kdyå platí jak Si y Sj tak Sj y Si nebo platí jak v = A a v = B (pro dv r$zné konstanty A a B). Zárove platí, åe jak y tak = jsou transitivní, takåe nap. plány s S1 y S2, S2 y S3 a S3 y S1 jsou nekonsistentní. " ýásteþný plán z posledního obrázku je ešením, protoåe všechny pedpoklady jsou dosaåeny. Z uvedených definic je zejmé, åe libovolná z linearisací ešení je také ešením. Agent m$åe provád t kroky v libovolném poadí s omezeními a vådy má zaruþeno dosaåení cíle. 104

Pi þásteþném regresívním plánování plánovaþ prohledává prostor plán$. Zaþíná s poþáteþním plánem, kde jsou representovány kroky zaþátku a konce, a pak iteraþn pidává jednotlivé kroky. Pokud je dosaåeno nekonsistentního plánu, plánovaþ se vrátí a zkouší jinou v tev v prohledávaném prostoru. Aby bylo hledání sm rováno k poåadovanému cíli, plánovaþ pouze uvaåuje pidání krok$, které slouåí k dosaåení pedpokladu, který doposud nebyl spln n. Pozn.: Je zejmé, åe plánovaþ musí udråovat záznam o cest , aby se mohl v pípad nutnosti vracet. Píklad vyešení problému s mlékem, banány a vrtaþkou (cílem je mít všechno doma): Start

At(Home) Go(HWS) At(HWS) Sells(HWS,Drill) Buy(Drill) At(HWS) Go(SM)

At(SM) Sells(SM,Milk)

At(SM) Sells(SM,Ban.)

Buy(Milk)

Buy(Ban.) At(SM) Go(Home)

Have(Milk) At(Home) Have(Ban.) Have(Drill) Finish

(At(home) je doma, Go(HWS) je Jdi_do(äelezáství), tj. HardWare Shop, At(x) je být v x, SM je SuperMarket, Sells(SM,Milk) je Prodává(Supermarket,Mléko) apod., Buy(Drill) je Kup(Vrtaþku) apod.). Jediná nejednoznaþnost v plánu je moånost zvolit jakékoliv poadí Buy(Milk) a Buy(Bananas), protoåe na tom poadí nezáleåí vzhledem k míst nákupu. 105

Znalostní inåenýrství pro plánování Metodologii ešení problém$ s plánováním lze vyjádit takto: 1. 2. 3. 4. 5.

Definice problému. Definice podmínek, operátor$ a objekt$. Zakódování operátor$ do domény. Zakódování popisu výskytu specifického problému. Pedloåení problému plánovaþi a získání plán$.

Píklad pro tzv. problém blok$: 1.

2.

3.

Definice problému: doména obsahuje soubor blok$ (kostek) na stole. Kostky mohou být kladeny na sebe, ale pouze jedna urþitá kostka m$åe být umíst na na jinou. Ruka robota m$åe zvednout n jakou kostku a pesunout ji do jiné polohy (na st$l nebo na jinou kostku). V jednom þasovém kroku m$åe být manipulováno s jednou kostkou, nelze manipulovat s kostkou, která má další kostku/kostky na sob . Cílem je vådy vybudovat jeden nebo více sloupk$ z kostek, piþemå sloupky jsou popsány pomocí toho, jaké kostky jsou na jiných kostkách—nap. cílem m$åe být vytvoit dva sloupky, jeden s kostkou A na kostce B a druhý s kostkou C na D. Definice podmínek, operátor$ a objekt$: Objekty v této domén jsou kostky a st$l. Representovány jsou konstantami. K indikaci, åe kostka b je na x (x je bu jiná kostka nebo st$l) se pouåije On(b,x). Operátor pro pesun kostky b z pozice na x na y je Move(b,x,y). Jednou z podmínek pesunu b je, åe na ní není åádná jiná kostka, tedy v logice prvního ádu: ¬}x On(x,b) nebo alternativn ~x ¬On(x,b). Vzhledem k representaci plán$ (viz výše) je zapotebí vytvoit predikát representující fakt, åe åádná kostka není na b a pak zajistit, åe operátory korektn tento predikát zpracují—nap. zde Clear(x) bude znamenat, åe na x není nic. Operátory: operátor Move pesune jednu kostku b z x na y pokud na b a na y není nic; jakmile je pesun hotový, x je volné (nic na n m není), ale y jiå nadále volné není (je na n m kostka). Formáln jší zápis operátoru Move:

106

Op(Action: Move(b,x,y), Precond: On(b,x) Y Clear(b) Y Clear(y), Effect: On(b,y) Y Clear(x) Y ¬On(b,x) Y ¬Clear(y)) Zde ale operátor nezpracovává Clear správn , pokud x nebo y je na stole. Pokud x = Table, výsledkem je Clear(Table), ale st$l nem$åe být zbaven kostek. Pokud y = Table, pak má podmínku Clear(Table), ale st$l nemusí být bez niþeho, aby se na n j dala umístit kostka. K vyešení uvedených potíåí se zavede další operátor MoveToTable pro pesun kostky b z x na Table: Op(Action: MoveToTable(b,x), Precond: On(b,x) Y Clear(b), Effect: On(b,Table) Y Clear(x) Y ¬On(b,x)) K tomu je nutno zavést ješt interpretaci Clear(x) ve smyslu “na x je volno a lze tam uloåit kostku”. Clear(Table) pak vådy bude souþástí poþáteþní situace a je korektní, åe Move(b,Table,y) má jako výsledek Clear(Table). Jedinou nedokonalostí je nyní fakt, åe nic nem$åe zabránit plánovaþi v pouåití Move(b,x,Table) místo MoveToTable(b,x). V pípad uskuteþn ní to vede k v tšímu prostoru prohledávání, neå je nutno, ale nevede to k nekorektním odpov dím. Lze to odstranit zavedením dalšího predikátu Block a pidat Block(b) Y Block(y) k podmínkám v Move (zajistit, åe jak b tak y jsou kostky, nikoliv pipustit, åe by se pro y mohlo jednat taky o st$l zpracovávaný jako kostka, pestoåe má urþité odlišnosti—nap. m$åe na n m být více kostek, na kostce ale nikoliv). Dalším problémem by mohla být vcelku neopodstatn ná operace Move(B,C,C), která by m la kontradiktorické výsledky. Obecn se tyto problémy ignorují, protoåe nemají åádný vliv na vytvoené plány (pesun kostky B z C na C je v podstat prázdná operace). Bylo-li by nutno zajistit, aby k tomu nedocházelo, pak by se do podmínek musely zavést nerovnosti: b =/ x =/ y, tj. všechny objekty jsou r$zné.

107

Píklad pro tzv. Shakeyho problém: P$vodní program v Strips byl navråen k ízení robota jménem Shakey (jméno pochází z faktu, åe jeho motory ho pi pohybu þinily pon kud nestabilním—to shake = kymácet se, tást se). Robot Shakey byl vyvinut jako souþást robotického projektu ve SRI (Stanford Research Institute) v Kalifornii poþátkem 70. let a potuloval se v institutu po místnostech a chodbách. V tšina Shakeyho þinností byly simulace, ale obþas se skuteþn pohyboval v prostorách institutu s cílem vzít n co nebo pemístit n co. Obrázek ukazuje Shakeyho sv t, který se skládal ze þty místností, podél nichå vedla chodba spojená s místnostmi dvemi. Shakeyho úkolem bylo se pohybovat z místnosti do místnosti, posunovat pohyblivými objekty (krabicemi), vylézt na pevný objekt a slézt dol$ (op t krabice), a zapnout/vypnout sv tlo v místnosti: Ls4

Místnost 4

Dveøe 4

Ls3

Místnost 3

Dveøe 3

Shakey

Chodba Ls2

Místnost 2

Box3

Dveøe 2

Box2

Ls1

Místnost 1

Dveøe 1

Box4

Box1

Pozn. 1: Ls je zapínaþ/vypínaþ osv tlení místnosti (light switch). Pozn. 2: Shakey nebyl mechanicky dost obratný ke skuteþnému lezení po krabicích a ovládání vypínaþe sv tla, ale Strips byl schopen vytvoit plány. 108

Pro Shakeyho lze urþit následující literály a operátory: 1.

2.

3.

4. 5.

6.

Jdi ze souþasné pozice na jinou pozici y: Go(y). Podmínka At(Shakey,x) stanovuje okamåitou pozici a je vhodné, aby x i y bylo v téåe místnosti r: In(x,r) Y In(y,r). Aby bylo moåné naplánovat cestu z jedné místnosti do druhé, povaåují se tytéå dvee za souþást obou místností z hlediska In. Posu objekt b z místa x na místo y: Push(b,x,y). Zde mohou op t být x i y v téåe místnosti. Zavést je nutno predikát Pushable(b), tj. pemístitelnosti, ale jinak je situace obdobná Go. Vylez na box b: Climb(b). Je nutno zavést predikát On (kde robot je) a konstantu Floor (podlaha), a zajistit, aby podmínka pro Go byla On(Shakey,Floor), tj. aby robot lezl z podlahy na krabici (a resp. zp t), nikoliv nap. skákal z krabice na krabici. Pro Climb(b) musí být podmíka, åe Shakey je At na tomåe míst jako je b, a b musí být tzv. Climbable (tj. b je pedm t, na n jå lze vylézt, tedy vylezitelný). Slez dol$ z boxu b: Down(b). V principu zrušení efektu vylezení Climb. Zapni sv tlo: TurnOn(ls). Vzhledem k tomu, åe Shakey na vypínaþ ze zem nedosáhl, musel pro rozsvícení sv tla v místnosti vylézt na krabici b u vypínaþe ls. Vypni sv tlo: TurnOff(ls). Obdoba Zapni. Jazyk plánování by musel mít k dispozici podmínku pro urþení stavu sv tla, aby se dalo urþit, zda sv tlo je zapnuto nebo vypnuto kv$li schopnosti pepínání z jednoho stavu do druhého.

V jazyce Strips bylo nutno pro kaådý box pidat individuální literál do poþáteþního stavu, zatímco v situaþním kalkulu se napíše axiom, který íká, åe kaådý box lze posunout a na kaådý lze vylézt. Rovn å by bylo zapotebí zaþlenit kompletní mapu sv ta v poþáteþním stavu—pomocí term$, které objekty jsou v které místnosti, tj. pomocí In. Stejn by se popsalo pomocí At, kde který objekt pesn je. Jazyk Strips (a jemu obdobné) umoåují representovat jednoduché domény pomocí operátor$ Strips, ale návrh mnoåiny správných a potebných operátor$ a predikát$ není v$bec snadný.

109

Praktické plánování V této èásti bude zmínka o existujících plánovaèích, které jsou používány ve složitých, reálných doménách.

Montáž, integrace a verifikace kosmické lodi European Space Agency používá plánovaè nazvaný Optimum-AIV na pomoc montáži, integraci a verifikaci kosmických lodí (AIV = Assembly, Integration, and Verification). Systém se používá pro generování plánù a monitorování jejich provádìní. Bìhem monitorování systém upozoròuje uživatele na pøipravované èinnosti a je schopen navrhovat úpravy plánu, když je nìjaká èinnost provedena pozdì, zrušena, nebo se objeví nìco neoèekávaného. Je to zejména schopnost systému zmìnit plán, co jej èiní principiálnì význaèným. Systém sám neprovádí plány; ty jsou provádìny lidmi pomocí standardních konstrukèních a testovacích zaøízení. V podobnì složitých projektech se obecnì používají plánovací nástroje pocházející z oblasti operaèního plánování, napø. diagramy PERT nebo metoda kritické cesty. Tyto nástroje v zásadì používají jako vstup ruènì navržený kompletní plán rozdìlený na sub-plány v poøadí rozdìleném na èásti a generují pro to optimální rozvrh èinností. Akce jsou považovány za objekty, které vyžadují nìjaký èas a mají omezení vzhledem k poøadí èinností; jejich efekty se neuvažují. Tím se lze vyhnout použití znalostního inženýrství a pro jednorázové problémy to mùže obyèejnì být zcela pøimìøené øešení. Avšak pro vìtšinu praktických aplikací existuje mnoho souvisejících problémù k øešení, takže se obvykle vyplácí popis domény a pak automatické generování plánù. To je dùležité zejména bìhem provádìní plánù—pokud krok plánu selže, je obyèejnì nutno plán rychle zmìnit (upravit), aby se projekt znovu uvedl v život. Diagramy metody PERT neobsahují pøíèinná propojení a další informaci potøebnou pro to, aby bylo zjevné, jak zmìnit plán, a lidmi provádìné zmìny jsou èasto pøíliš pomalé.

110

Úspìch systémù umìlé inteligence z reálného svìta vyžaduje integraci do prostøedí, v nìmž jsou aktivní. Plánovaè musí být schopen pøístupu do existujících databází s informacemi o projektu, nezávisle na formì v níž mohou informace být. Zároveò representace vstupù a výstupù plánovaèe by mìly být ve formì, která je jak expresívní, tak snadno srozumitelná uživateli. Døíve (velmi struènì) zmínìný jazyk Strips je pro doménu AIV nedostaèující, protože nedokáže vyjádøit ètyøi základní koncepty: 1.

Hierarchické plánování: Je zjevné, že vypuštìní kosmické lodi je mnohem složitìjší než nakupování potravin v obchodì. Jednou ze schùdných cest zvládnutí složitosti je specifikace plánù na rùzných úrovních detailù. Plán na vrcholné úrovni mùže zahrnovat: pøíprava raketového stupnì, pøíprava kosmické kabiny, naložení kosmické lodi potøebnými vìcmi, vypuštìní. K tomu mùže být velké množství meziúrovní pøed tím, než se dojde k úrovni zcela konkrétních provádìcích akcí: vlož matici A do otvoru B a sešroubuj se šroubem C. Pøidání schopnosti representovat hierarchické plány mùže tvoøit rozdíl mezi uskuteènitelnou a neuskuteènitelnou akcí a mùže zpùsobit snadnìjší porozumìní výslednému plánu. Také pomáhá dovolit uživateli, aby poskytl plánovaèi vodítko ve formì èásteènì specifikovaného, abstraktního plánu, pro nìjž plánovaè doplní detaily.

2.

Komplexní podmínky: Operátory Strips jsou v principu proposièní—umožòují promìnné, ale jejich použití je velmi limitované. Neexistuje universální kvantifikace, bez níž není možno vyjádøit fakt, že operátor Launch (Vypuštìní) zpùsobí pøemístìní všech objektù lodi na obìžnou dráhu. Podobnì tomu, operátory Strips jsou nepodmínìné: nelze vyjádøit fakt, že pokud všechny systémy jsou vypuštìny, Launch umístí loï na obìžnou dráhu, jinak loï skonèí v oceánu.

111

3.

Èas: Jazyk Strips je založen na situaèním kalkulu, proto pøedpokládá, že všechny akce se vyskytnou bezprostøednì a že každá akce následuje po nìjaké jiné bez pøerušení. Problémy reálného svìta vyžadují lepší model èasu—musí representovat fakt, že projekty mají koneèné termíny (napø. loï musí být vypuštìna 17. èervna), akce nìjaký èas trvají (testování montáže XYZ trvá 6 hodin) a jednotlivé kroky plánu vyžadují èasová okna (napø. stroj pro testování montáže XYZ je k dispozici od 1. kvìtna do 1. èervna vyjma víkendù, ale musí se reservovat týden dopøedu). Tradièní techniky operaèního plánování mìly jako hlavní pøínos uspokojování èasových omezení pro kompletní plán rozdìlený na èásti.

4.

Zdroje: Projekt má normálnì rozpoèet, který nelze pøekroèit, takže plán musí být omezený na spotøebu èástky, která je k dispozici. Podobnì existují limity na poèet pracovníkù k dispozici a na poèet montážních a testovacích stanic. Omezení zdrojù se mùže týkat vìcí potøebných v urèitý èas (napø. lidé) nebo celkového použitelného množství (napø. peníze). Popis akcí proto vyžaduje zahrnutí spotøeby a vytváøení zdrojù, stejnì jako plánovací algoritmy musí být schopny zpracovat úèinnì omezení zdrojù.

Optimum-AIV je založen na plánovací architektuøe z r. 1991, zvané O-Plan, která umožòuje používat jazyka se znaènou možností výrazù pro representaci èasu, zdrojù a hierarchických plánù. Rovnìž pøijímá heuristiky pro vedení vyhledávání a zaznamenává dùvody každého výbìru, což usnadòuje pozdìjší úpravy plánu, pokud je zapotøebí. O-Plan byl použit na mnoho problémù, napø. opatøování software v Price Waterhouse, plánování procesu montáže zadní osy u aut zn. Jaguar, a kompletní plánování produkce továrny Hitachi.

Plánování èinnosti pracovištì Problémy øešené rùznými pracovišti spoèívají v obstarání surovin a dílù a jejich smontováním do koneèných výrobkù. Problém lze rozdìlit na plánovací úlohu (rozhodnutí, které montážní kroky budou uskuteènìny) a rozvrhovou úlohu (rozhodnutí, kdy a kde bude každý krok uskuteènìn). V mnoha výrobních zaøízeních se plánuje manuálnì a rozvrh se dìlá pomocí automatizovaného nástroje.

112

V Hitachi se O-Plan používá v plánovacím a rozvrhovém systému zvaném Tosca. Typický problém zahrnuje výrobu 350 rùzných výrobkù, 35 montážních strojù a pøes 2000 rùzných operací. Plánovaè poskytuje rozvrhy na 30 dní pro osmihodinové smìny. Obecnì Tosca sleduje plán rozdìlený na èásti, s nejmenším závazkem. Umožòuje také “nízkozávazková” rozhodování: volby, které kladou omezení na plán nebo na nìjaký jeho konkrétní krok. Napø. systém mùže vybrat rozvrh akce pro urèitou tøídu strojù bez konkretizace stroje. Továrny s menší diversitou výroby èasto sledují pevný plán, ale stále potøebují automatizované rozvrhování. Systém ISIS z r. 1984 byl navržen speciálnì pro rozvrhování a poprvé testován na výrobì èástí turbíny firmy Westinghouse. Továrna produkuje tísíce rùzných lopatek turbín a pro každý typ existuje jeden èi více plánù zvaných smìrování procesu. Pøi obdržení objednávky je vybrán jeden z plánù a je pro nìj vytvoøen èasový rozvrh. Èas závisí na kritiènosti objednávky: zda jde o urgentní výmìnu lopatky èinného zaøízení, plánovanou údržbovou souèástku se spoustou èasu, avšak s nutností pøesnì splnit datum, nebo prostì objednávka zásob k vytvoøení reservy. Tradièní metody plánování, jako PERT, jsou schopny najít vyhovující poøadí krokù vzhledem k èasovým omezením, ale ukazuje se, že lidé-plánovaèi používající PERT spotøebují 80-90% svého èasu na komunikaci s pracovníky o tom, co jsou skuteèná omezení. Úspìšný automatický plánovaè potøebuje být schopen representovat a zdùvodnit tato pøídavná omezení. Dùležité faktory zahrnují cenu surovin, které jsou k dispozici, hodnotu vyrobeného, ale zatím neprodaného zboží, pøesné pøedpovìdi budoucích potøeb, a minimální narušení existujících postupù. ISIS používá hierarchické hledání s minimálním závazkem pro nalezení vysoce kvalitních plánù, které uspokojují všechny uvedené požadavky (minimální závazek—viz døíve uvedený popis representace plánù—v podstatì odklad ne právì v daném okamžiku aktuálních záležitostí do jiné fáze).

Plánování kosmických letù Plánovací a rozvrhové systémy jsou v této oblasti využívány rozsáhle, a to jak pro plánování výprav lodí, tak i pro jejich konstrukci. Dùvodem je pøedevším to, že kosmické lodì jsou mimoøádnì nákladné a také nìkdy obsahují lidi, což v pøípadì havárie mùže mít extrémnì vysokou cenu škody a pøinést nenahraditelné ztráty. Kromì toho se lety uskuteèòují v prostoru neobsahujícím mnoho dalších agentù, kteøí by mohli narušit oèekávané výsledky. 113

Plánovaèe byly a jsou používány pozemními týmy pro Hubblùv teleskop a nejménì pro tøi lodì: Voyager, UOSAT-II a ERS-1. V každém pøípadì je cílem organizace pozorovacího zaøízení, pøenašeèù signálù a kontrola mechanismù pro nastavení a udržování výšky a rychlosti, aby se maximalisovala informace získaná z pozorování za pøedpokladu dodržování omezení na èas a energii. Plánování misí èasto zahrnuje velmi složitá èasová omezení, zejména ty mise, které obsahují periodické události. Napø. ERS-1 (satelit vypuštìný z European Earth Resource Observation) uskuteèní jeden obìh Zemì za 100 minut a do téhož bodu se vrátí každých 72 hodin. Pozorování každého bodu na zemském povrchu mùže být provedeno v libovolném z mnoha èasových okamžikù, navzájem oddìlených 72 hodinami, ale v jiných èasech nikoliv. Satelity mají omezení zdrojù výstupní energie—nemohou pøekroèit pevnì stanovené maximum a musí se zajistit, aby nevyèerpaly pøíliš mnoho energie za èasovou periodu. Satelity lze považovat za typ pracovištì s plánovaným rozvrhem èinností, kde teleskopy a další zaøízení jsou výrobní stroje a pozorování jsou výrobky. Hubblùv teleskop je dobrým pøíkladem potøeby automatického plánování a rozvrhování. Po svém vypuštìní v dubnu 1990 bylo objeveno, že primární zrcadlo má chybu v nastavení ohniska. Pomocí Bayesových technik pro rekonstrukci obrazu byl pozemský tým schopen chybu kompensovat do stupnì, který umožnil pøedávání nových a dùležitých informací o Plutu, o gravitaèních èoèkách, o supernovì, atd. V r. 1993 astronauti z raketoplánu opravili vìtšinu problémù primárního zrcadla, èímž otevøeli nové možnosti pozorování. Pozemní tým neustále objevuje více možností, které má èi nemá HST k dispozici a bylo by zcela nemožné aktualisovat plány pozorování bez automatických nástrojù. Kterýkoliv astronom mùže pøedložit žádost. Žádosti jsou dìleny na vysokoprioritní (70% pozorovacího èasu), nízkoprioritní (podle èasových možností) a zamítnuté. Návrhy pøicházejí v poètu cca 1 za den, což znamená, že je jich více, než je možno uskuteènit. Každý návrh obsahuje specifikaci, který pozorovací nástroj by mìl být namíøen na urèitý nebeský objekt a jaký druh snímku by se mìl udìlat. Nìkterá pozorování lze udìlat kdykoliv, jiná závisejí na faktorech jako postavení planet a zda HST je v zemském stínu. Existují unikátní omezení pro tuto doménu—napø. astronom mùže žádat o periodická pozorování quasaru (velmi vzdálená raná vývojová fáze galaxie) po nìkolik mìsícù nebo let za stejných podmínek stínu Zemì.

114

Plánovací systém HST je rozdìlen na dvì èásti. Dlouhodobý plánovaè SPIKE prvnì dìlá rozvrh pozorování v segmentech po jednom týdnu. Heuristikou je pøiøazování vysokoprioritních návrhù tak, aby mohly být všechny provedeny, dokud zbývá nejménì 20% kapacity. To se dìlá asi rok pøedem. Mnohaletý rozvrh s pøibližnì 5000 pozorováními lze vytvoøit za ménì než hodinu, takže zmìna plánu je snadná. Po naplánování každého segmentu se použije krátkodobý plánovaè SPSS, jenž dìlá detailní plánování pro každý segment a naplòuje èas mezi vysokoprioritními úlohami mnoha nízkoprioritními podle možností. Systém rovnìž vytváøí pøíkazy pro nastavení polohy základny tak, aby se pozorování mohla provést. Kontroluje proveditelnost návrhù a detailních rozvrhù mnohem rychleji, než dokáží lidé-experti.

Budovy, letadla a pivovary SIPE (System for Interactive Planning and Execution monitoring—systém pro interaktivní plánování a sledování výkonu èinností) byl prvním plánovaèem, který se zabýval problémem zmìny plánu, a také prvním, který použil nìkteré dùležité kroky vùèi expresívním operátorùm. Je podobný systému O-Plan v rozsahu vlastnosti a aplikovatelnosti. Byl použit v nìkterých demonstraèních projektech pro nìkolik domén, vèetnì plánování operací na palubì letadla a plánování výroby pro jeden pivovar v Austrálii. Jiná studie použila SIPE pro plánování konstrukce výškových budov—jedna z nejsložitìjších domén, do které se plánovaè pustil. SIPE umožòuje deduktivním pravidlùm operovat nad stavy, takže uživatel nemusí specifikovat všechny relevantní literály jako výsledky pro každý operátor. Tento systém je aplikovatelný na široký rozsah domén, ale jeho obecnost je spojena s velkými náklady. Napø. v doménì konstrukce budov se zjistilo, že SIPE potøebuje èas úmìrný O(n 2.5) pro n-poschoïovou budovu. Z toho plyne vysoký stupeò interakce mezi poschodími, pøièemž ve skuteènosti je ten stupeò mnohem nižší: pøi sledování linie stavby od zemì nahoru a zajištìní toho, aby výtahové šachty byly propojeny je možné získat výkonnost mnohem bližší složitosti O(n). Uvedené pøíklady poukazují na souèasnou ideu plánovacích systémù. Jsou dost dobré pro modelování složitých domén, ale dosud nebyly zcela prakticky pøijaty mimo omezený poèet pilotních projektù. Je zapotøebí dále zvýšit stupeò flexibility a výkonnosti, aby se tyto systémy staly bìžným nástrojem. 115

Hierarchická dekomposice Problém s nákupem, popsaný døíve, lze vyøešit použitím vhodných metod tak, že je získáno øešení na pomìrnì vysoké úrovni abstrakce (pro agenta). Napøíklad plán typu: [Go(Supermarket), Buy(Milk), Buy(Bananas), Go(Home)] je dobrý popis toho, co dìlat, na vysoké úrovni, ale je velmi daleko od toho, co je zapotøebí agentovi pøedat formou instrukcí do jeho efektorù. Pro agenta je to nedostateèné z hlediska toho, co by mìl skuteènì udìlat. Na druhé stranì by nízko-úrovòový plán typu: [Forward (1cm), Turn (1deg), Forward (1cm), ...] obsahoval mnoho tisíc krokù a øešení problému nákupu by bylo nesmírnì dlouhé. Zejména by vznikl problém extrémnì velikého prostoru plánù velké délky a je pravdìpodobné, že by metody hledání nenašly øešení v rozumném èase. Uvedené dilema se v praktických plánovaèích øeší pomocí myšlenky zavedení hierarchické dekomposice, která vychází z dekomposice abstraktních operátorù na skupinu krokù, které vytváøejí plán, který implementuje operátor. Jako pøíklad lze uvážit problém stavby domu. Abstraktní operátor Build(House) (postav dùm) lze rozložit na plán, který se skládá za ètyø krokù: Obtain Permit (získej povolení), Hire Builder (najmi stavitele), Construction (stavba), a Pay Builder (zapla staviteli). Kroky ukázaného vysokoúrovòového plánu lze dále rozložit na ještì specifiètìjší plány. Na obrázku je znázornìna dekomposice kroku stavby domu. V dekomposici lze pokraèovat tak dlouho, až je dosažena nejnižší úroveò typu Hammer(Nail) [Zatlouci(Høebík)]. Plán je kompletní v okamžiku, kdy je každý krok ve formì primitivního operátoru, tj. operátoru, který mùže být pøímo proveden agentem. Hierarchická dekomposice je nejúèinnìjší, pokud lze operátory dekomponovat nìkolika zpùsoby. Napø. operátor Build(Walls), èili Postav(Zdi), lze rozložit na plán zahrnující døevo, cihly, beton nebo vinyl (zdi lze stavìt z rùzného materiálu a plán by to mìl respektovat).

116

K uskuteènìní nastínìné myšlenky dekomposice je nutno udìlat dvì vìci:

!

Do jazyka typu Strips dát rozšíøení, která umožòují neprimitivní operátory.

!

Modifikace plánovacích algoritmù tak, aby bylo možné nahradit neprimitivní operátory jejich dekomposicemi.

117

Rozšíøení jazyka Pro zaèlenìní hierarcické dekomposice je zapotøebí pøi popisu každé problémové domény upravit dvì vìci:

!

!

Rozdìlení souboru operátorù na primitivní a neprimitivní. V doménì stavby domù je Zatlouci(Høebík) operátor primitivní a Postavit(Dùm) neprimitivní. Obecnì je rozdíl mezi primitivními a neprimitivními operátory relativní a záleží na agentovi, který bude plán vykonávat. Pro dodavatele stavby je operátor typu Namontovat(PodlahováPrkna) primitivní (protože pouze objedná dìlníka k montáži podlahy), pro dìlníka neprimitivní (a pro nìj bude primitivní Zatlouci(Høebík)). Pøidání souboru dekomposièních metod. Každá metoda je výraz typu Decompose(o,p), což znamená, že neprimitivní operátor, který je spojen s o, mùže být rozložen do plánu p. Dekomposice Stavby (Construction) z pøedchozího obrázku: Decompose(Construction, Plan(Steps:{S 1: Build(Foundation), S 2: Build(Frame), S 3: Build(Roof), S 4: Build(Walls), S5: Build(Interior)} Orderings: {S 1 S 2 S 3 S 5, S 2 S 4 S 5}, Bindings: {}, Links: { }))

Dekomposièní metoda je v podstatì procedura nebo makro definující operátor. Musí být zajištìno, aby dekomposice byla korektní implementací operátoru. Platí, že plán p korektnì implementuje operátor o, pokud se jedná o kompletní a konsistentní plán pro daný problém k dosažení úèinkù o za pøedpokladù pro o:

! !

!

p musí být konsistentní (tj. neexistuje žádná kontradikce v uspoøádáních nebo vazbách promìnných). Každý úèinek (efekt) operátoru o musí být prosazen nejménì jedním krokem plánu p (a není popøen nìjakým jiným, pozdìjším krokem plánu p). Každá podmínka krokù v p musí být dosažena nìjakým krokem v p nebo být jednou z podmínek operátoru o. 118

Tím je zaruèeno, že je možné nahradit neprimitivní operátor jeho složkami (dekomposicemi) a vše je správnì navázáno na sebe. Je samozøejme vždy nutné zkontrolovat možná ohrožení pocházející z interakcí mezi novì zavedenými kroky s podmínkami a již existujícími kroky s podmínkami—není ale nutno si dìlat starosti s interakcemi mezi kroky obsaženými v samotné dekomposici (ta musí být sama o sobì udìlána zcela korektnì). Za pøedpokladu, že není pøíliš mnoho interakcí mezi rùznými èástmi plánu, hierarchické plánování umožòuje vybudovat velmi složité plány kumulativnì z jednodušších sub-plánù. Je také umožnìno vygenerovat plány, uložit je, a pak znovu použít v pozdìjších plánovacích problémech. Následující obrázek ukazuje detailnìjší diagram pøíkladu dekomposice kroku plánu v kontextu rozsáhlejšího plánu:

Analýza hierarchické dekomposice Hierarchiská dekomposice zde byla ukázána struènì, ve své základní èásti. Je založena na obdobné myšlence jako použití maker nebo procedur v programování—umožnit programátorovi nebo znalostnímu inženýrovi specifikaci problému po èástech majících rozumnou velikost. Èásti mohou pak být hierarchicky kombinovány pro vytváøení velkých plánù, aniž by vznikaly enormní kombinatorické náklady spojené s konstrukcí z primitivních operátorù. 119

Pøedpokládejme, že existuje zpùsob vzájemného propojení ètyø abstraktních operátorù k postavení domu (viz obrázek z podkapitoly Hierarchická dekomposice). Tento zpùsob se nazývá abstraktní øešení—konsistentní a kompletní plán obsahující abstraktní operátory. Nalezení malého abstraktního øešení (pokud existuje), by nemìlo být pøíliš nároèné. Pokraèování tohoto procesu by mìlo vést k dosažení primitivního plánu bez pøílišného navracení se zpìt po cestách hledání. Zde se ovšem pøedpokládá, že hledání abstraktního øešení—a odmítání jiných abstraktních plánù jako nekonsistentních—je úèelné. Mìly by platit tyto vlastnosti:

!

!

Je-li plán p abstraktním øešením, pak existuje primitivní øešení, pro nìž je p abstrakcí. Pokud to skuteènì platí, pak jakmile je nalezeno abstraktní øešení, lze odstranit z vyhledávacího stromu všechny ostatní abstraktní plány.Tato vlastnost se nazývá øešení smìrem dolù. Je-li abstraktní plán nekonsistentní, pak neexistuje primitivní øešení, pro nìž je ten plán abstrakcí. Pokud to skuteènì platí, pak lze odøíznout veškeré potomky libovolného nekonsistentního abstraktního plánu. Tato vlastnost se nazývá øešení smìrem nahoru, protože to rovnìž znamená, že všechny kompletní abstrakce primitivních øešení jsou abstraktními øešeními.

Tyto dvì vlastnosti lze znázornit graficky:

Každý uzel representuje celý plán (nikoliv pouze jeden krok), každá hrana representuje dekomposièní krok, v nìmž je abstraktní operátor expandován.

120

V koøeni stromu je velmi abstraktní plán, v listech jsou plány s pouze primitivními kroky. Uzly s tuènì znázornìnými obrysy jsou (abstraktními) øešeními. Uzly s teèkovanými obrysy jsou nekonsistentní (tj. nejsou bezesporné). Plány oznaèené X nemusí být plánovacím algoritmem zkontrolovány. Mohou být (hledáním zleva doprava) odøíznuty. Pøedpokládejme pro pøíklad jednoduchý model prohledávaného prostoru. Nech existuje nejménì 1 øešení s n primitivními kroky a dále, že možná ohrožení a omezení lze øešit v zanedbatelném èase—vše, co bude nutno uvažovat, je pouze èas potøebný k výbìru správné množiny krokù. Obrázek ukazuje prostor hledání z hlediska parametrù b, s, a d:

Øešení bude mít n = sd krokù (zde je n = 64). Pøedpokladem je 1/b dekomposic vedoucích k øešení.

121

Nehierarchický plánovaè by vygeneroval plán s n-kroky, pøièemž by pro každý krok vybíral z b možností (pøedpokládejme zde, že poèet dekomposic pro každý neprimitivní krok, b, je tentýž jako poèet aplikovatelných nových operátorù pro podmínku primitivního kroku). V nejhorším pøípadì je tedy složitost O(b n). Pro hierarchické plánovaèe lze použít strategii hledání pouze tìch dekomposic, které vedou k abstraktním øešením (v ukázaném zjednodušeném modelu na obrázku je právì 1 z každých b dekomposic øešením—v mnohem realistiètìjších modelech je zapotøebí uvážit, co dìlat, když je poèet øešení nulový nebo je jich více než 1). Plánovaè musí prohlédnout sb krokù v hloubce d = 1. V hloubce d = 2 je to dalších sb krokù pro každý dekomponovaný krok, ale zde musí dekomponovat jen 1/b z disponibilních krokù pro celkové množství bs2. Celkový poèet uvažovaných plánù je tedy

Rozdíl mezi nehierarchickým a hierarchickým plánovaèem je v nutnosti prohlédnout 3×10 30 plánù (nehierarchický) oproti 252 (hierarchický). Øešení smìrem vzhùru a dolù se jeví jako enormì výkonná—pokud ovšem není žádná ze tøí vlastností pro o (uvedených v podkapitole o rozšíøení jazyka) garantována, pak hierarchický plánovaè nebude lepší než nehierarchický v nejhorším pøípadì (v prùmìru mùže být lepší). Jako shrnutí lze øíci, že pùvodní plánovací jazyk umìlé inteligence vycházel z representace stavù a operátorù. Pro jednoduché èi umìle sestavené problémy je takový pøístup použitelný, avšak pro zpracování složitìjších a realistiètìjších domén je zapotøebí plánovací jazyk rozšíøit.

122

Existuje celá øada rozšíøení, každé z nich vyžaduje odpovídající zmìny v plánovacím algoritmu a vìtšinou dochází k obtížnému kompromisu mezi schopností vyjadøovat výrazy (expresivitou) a výkonností z hlediska nejhoršího pøípadu. V dosud existujících experimentech se ukázalo, že expresívnìjší representace, použité uvážlivì a s rozmyslem, mohou vést k nárùstu efektivnosti, pøestože se jedná o pomìrnì složitou úlohu. Situaèní kalkul a dokazování teorémù jsou z praktického hlediska nepoužitelné, ale vedly ke vzniku srozumitelného paradigmatu (plánování typu Strips). Jazyk Strips je pøíliš omezený pro komplexní, realistické domény, ale lze jej rozšíøit nìkolika smìry:

!

Plánovaèe, založené na rozšíøených versích Strips a na algoritmech používajících èásteèné uspoøádání a nejmenší závazek, se dosud ukázaly jako schopné zpracovat složité domény typu výprava kosmické lodi nebo výroba.

!

Hierarchická dekomposice umožòuje zahrnutí neprimitivních operátorù do plánù (je ovšem nutno znát dekomposici na primitivnìjší kroky).

!

Hierarchická dekomposice je nejúèinnìjší tehdy, pokud slouží ke zmenšení prohledávaného prostoru. Zmenšování (proøezávání stromu) je garantováno, pokud platí buï øešení smìrem dolù (každé abstraktní øešení mùže být dekomponováno do primitivních øešení) nebo øešení smìrem nahoru (nekonsistentní abstraktní plány nemají žádná primitivní øešení).

Oblast plánování patøí v souèasnosti mezi oblasti umìlé inteligence, kterým je v ìnováno význaèné výzkumné úsilí vzhledem k potøebnosti rychlých a efektivních plánování v množství praktických problémù reálného svìta.

123

Připravil: Ing. Jiří Lýsek, Ph.D. Verze: 10.12.2014

Umělá inteligence Evoluční metody

strana 2

Časová složitost úloh

• notace O() – O(k), O(log n), O(n), O(nk), O(n!), O(kn), …

• vyjadřuje počet operací potřebných pro zpracování vstupního souboru o velikosti n

strana 3

200 O(n) O(log n)

180

O(n2) O(n3)

160

O(2n)

140

O(3n) O(n!)

120 100 80 60 40 20 0

5

10

15

20

25

strana 4

Kdy použít umělou inteligenci

• řešení složitých úloh – je potřeba projít mnoho stavů – úloha má mnoho řešení

• řešení úloh, kde nedokážeme definovat algoritmem přesný postup

strana 5

Evoluční metody

• skupina algoritmů inspirovaných procesem evoluce v přírodě • používá populaci jedinců, kteří se v čase vyvíjí – Genetický algoritmus – Gramatická evoluce – Diferenciální evoluce –…

strana 6

Evoluční metody

• metaheuristika – strategie pro řízení procesu prohledávání – nedeterministické algoritmy hledající přibližná řešení – neřeší konkrétní problém = framework

strana 7

Evoluční metody - vlastnosti

• iterativní • přímé – nevyžaduje derivaci, pracuje pouze s aktuální množinou řešení

• stochastické (náhodné) – nelze zaručit 2x stejný výsledek

• heuristické – výsledek je rychlý odhad dobrého řešení

strana 8

Jiné metody inspirované přírodou

• PSO • Simulované žíhání • Ant colony • …

strana 9

Základní pojmy evolučních metod

• Jedinec – chromozom - genotyp - fenotyp – gen – alela

• • • •

Populace Selekce Křížení Mutace

strana 10

Algoritmus evoluční metody

• Inicializace • Iterativně – Ohodnocení populace – Selekce • náhodně, podle fitness

– Křížení • pravděpodobnost

– Mutace • pravděpodobnost

strana 11

Ohodnocení populace - fitness

• každý jedinec je ohodnocen číslem – hodnota fitness – F(m) = … – vzorec je nutné navrhnout • někdy velmi složité

• hledáme max nebo min

strana 12

Selekce

• • • •

Náhodně Ruleta - pouze pro maximalizaci Turnaj - lepší vyhrává … – různá pravidla bránící křížení podobných jedinců

strana 13

Operace křížení

• výměna částí chromozomů mezi jedinci • prohledává prostor řešení daný aktuálním stavem populace

strana 14

Operace mutace

• náhodná změna jednoho nebo více genů • přidává do populace nová řešení, která bychom křížením nemuseli objevit – mění diverzitu populace

strana 15

Genetický algoritmus - obecně

• chromozom definuje úlohu – kóduje řešení

• kódování – binární – celočíselné –…

strana 16

Nevýhody

• lokální minima • nezaručuje nalezení opravdového optima • algoritmus optimalizuje proti funkci fitness, nikoliv přímo řešení

strana 17

Hledání minima funkce

• binární chromozom - 16 bit • Grayův kód

strana 18

Grayův kód

• 2 následující hodnoty se liší pouze 1 bitem

strana 19

Obchodní cestující

• Chromozom = ID měst • křížení = záměna sekvence z určitého města + oprava • mutace = otočení části chromozomu

strana 20

Gramatická evoluce

• chromozom je celočíselný, náhodná inicializace • překlad chromozomu pomocí bezkontextové gramatiky • vzniká program ve stromové struktuře

strana 21

strana 22

Gramatická evoluce - křížení

• záměna podstromů

strana 23

Gramatická evoluce - mutace

• nestrukturální • strukturální

strana 24

Gramatická evoluce - Santa-Fe Ant Trail • Generování algoritmu pro řízení mravence – musí sbírat potravu

• <expr> ::= move | turnLeft | turnRight | ifFood(<expr>,<expr>) | semic(<expr>,<expr>) | semic3(<expr>,<expr>,<expr>)

strana 25

Diferenciální evoluce

• určena pro optimalizaci sady reálných hodnot • pro křížení je dán vzorec – mutace není

strana 26

Gramatická + diferenciální

• Dvoufázová metoda – Každý jedinec spouští vlastní optimalizaci – obecně lze druhou fázi realizovat libovolnou jinou optimalizační metodou

strana 27


• regrese • optimalizuje fitness!

strana 28


<expr> ::= | | <math_fun>(<expr>) | <math_op>(<expr>,<expr>) <math_fun> ::= sin | cos | pow | abs | negate <math_op> ::= add | sub | mul ::= x ::= … strana 29 Zdroje • Vlastní DisP • Internet • Wikipedie

UMĚLÁ INTELIGENCE 2. Umělá inteligence může být jako obor chápána různě, například:

Recommend Documents