Inteligentní agent je cokoli, co používá umělou inteligenci k rozhodování a provádění úkolů. Skládá se ze senzorů a akčních členů, které mu umožňují interagovat s prostředím. Jeho strategii můžeme brát jako funkci z hodnoty senzorů do množiny akčních členů. V cyklu provede pozorování a na základě strategie vybere akci.
Prostředí může být
úplně pozorovatelné nebo částečně pozorovatelné podle toho, jestli má agent přístup ke všem informacím;
deterministické nebo stochastické podle toho, jestli ho je možné jednoznačně předvídat;
diskrétní nobo spojité podle toho, jakými parametry je popisováno;
statické nobo dynamické podle toho, jestli se situace průběžně mění
neutrální nebo nepřátelské podle toho, jestli se aktivně snaží bránit zájmům agenta.
Příklad Šachy jsou prostředí úplně pozorovatelné, deterministické, diskrétní a nepřátelské.Příklad Hra Hledání min je prostředí částečně pozorovatelné, deterministické, diskrétní a neutrální.Příklad Řízení auta je prostředí částečně pozorovatelné, stochastické, spojité a neutrální.Definice Algoritmus je sada přesných instrukcí, které říkají nějakému procesoru, jak řešit daný problém. Měl by být
deterministický – v každém kroku je jasné, jak pokračovat;
korektní – vždy vrátí správný výsledek;
konečný – vždy skončí v konečném počtu kroků;
elementální – sestává z elementárních kroků;
obecný – funguje pro všechny možné vstupy;
pokud možno rychlý (v nějakém smyslu).
Algoritmy můžeme navrhovat shora dolů (vzít celý problém a rozdělit ho na jednodušší části) nebo zdola nahoru (postupně budovat složitější procedury).
Příklad Mějme dvě místnosti, které mohou být čisté nebo špinavé, a čisticího robota, který je v jedné z nich. Celkem je tedy 8 možných stavů:
Algoritmus pro čištění by mohl vypadat například takto:
Je-li místnost špinavá, vyčisti ji.
Přesuň se do druhé místnosti.
Je-li místnost špinavá, vyčisti ji.
Prohledávání grafu
Máme graf a chceme najít cestu z do . Budeme udržovat rozdělení , kde jsou prozkoumané vrcholy, jsou hraniční vrcholy a jsou neprozkoumané vrcholy.
TBD: algoritmus
Existují různé přístupy, jak z hranice zvolit vrchol:
přidáme nejlevnější hranu (Dijkstrův algoritmus)
prodloužíme nejkratší cestu (prohledávání do šířky)
prodloužíme nejdelší cestu (prohledávání do hloubky)
vybereme cestu, která nejvíc sníží odhadovanou vzdálenost od cíle (hladové prohledávání)
vybereme cestu s nejmenším součtem délky a odhadované vzdálenosti od cíle (A*)
K odhadu vzdálenosti do cíle v algoritmu A* potřebujeme nějakou heuristickou funkci na odhad vzdálenosti do cíle. Funkce by měla být optimistická, tedy odhadnutá vzdálenost by neměla převýšit skutečnou vzdálenost. Pokud jako heuristiku vezmeme nulovou funkci, dostaneme jako speciální případ Dijkstrův algoritmus.
Za domácí úkol máme implementovat prohledávání grafu v mřížce (možné různé typy mřížky) s různými algoritmy a heuristikami.
místo, kde je, musí sousedit s místem, kam ji přesouváme;
místo, kam ji přesouváme, musí být prázdné.
Můžeme si to představit jako problém prohledávání grafu. Chceme-li použít A*, nabízí se dvě heuristiky:
počet špatně umístěných dlaždic;
součet manhattanských vzdáleností dlaždic od jejich správné pozice.
Všimněme si, že první heuristiku dostaneme odstraněním obou omezení, zatímco druhou heuristiku dostaneme odstraněním druhého omezení. To je obecně dobrý způsob, jak vymýšlet heuristiky.
Adamátor
Zápisky
Hlášky