---
tags: Společný základ
---
# SZ 1. Metody umělé inteligence
Prohledávání stavového prostoru, lokální prohledávání a metaheuristiky s jedním řešením a populacemi řešení. Plánování, reprezentace problému, plánování se stavovým prostorem. Práce s neurčitostí, odvozování v Bayesovských sítích, čas a neurčitost. Markovský rozhodovací proces, iterace hodnot, iterace strategie. Robotika, plánování pohybu robota. (IV126)
- Zdroj: https://www.fi.muni.cz/~hanka/ai/prusvitky/all_handout.pdf
- Doporučuju si kdyžtak některé kapitoly přečíst v https://en.wikipedia.org/wiki/Artificial_Intelligence:_A_Modern_Approach
:::danger
**TODO**
- Revize jestli nic nechybí, případně přeformátovat
- chybí Markovský rozhodovací proces, iterace hodnot, iterace strategie.
:::

## Prohledávání

#### Co to je?

- Jedna z metod řešení problémů.

#### Jaké jsou hlavní myšlenky?

- Předpokládáme, že **prostředí** problému je **pozorovatelné, statické** a **deterministické**.
- Prostředí popisujeme **stavovým prostorem** s **diskrétními stavy**.
- Cílem prohledávání stavového prostoru je najít řešení tj. sekvenci akcí / přechodů, pomocí které se dostaneme z počátečního stavu do cílového stavu.

#### Jaké reálné problémy se dají řešit prohledáváním stavového prostoru?
- hledání cesty z města A do města B
- problém obchodního cestujících (TSP)
- navigace auta, robota, ...
- př. stavového prostoru hledání cesty

#### Jaké různé typy prohledávání známe?

- Můžeme je rozdělit do dvou hlavních kategorií:
- **Neinformované prohledávání**
- Prohledávání do šířky (BFS)
- Prohledávání do hloubky (DFS)
- Prohledávání do hloubky s limitem (Depth-limited search)
- Prohledávání s postupným prohlubováním (Iterative Deepening DFS; IDS)
- Prohledávání podle ceny (Uniform-cost Search)
- **Informované prohledávání**
- Greedy best-first search
- A* search (čti A star)

#### Vlastnosti prohledávacích algoritmů:

- správnost (soundness) = když vrátí odpověď, tak je správná
- úplnost (completeness) = vrátí výsledek pokud existuje
- optimálnost řešení (optimality) = když vrátí řešení, tak je nejlepší možné (tzn. nejkratší, nejlevnější, ...)
- konečnost? = zastaví/skončí na každém validním vstupu

### Neinformované prohledávání stavového prostoru

#### Prohledávání do hloubky s limitem

- Klasické DFS může cyklit v nekonečné větvi
- např. hledání cesty na nekonečné mřížce
- Tento problém můžeme vyřešit přidáním **limitu hloubky** $l$, po kterém se prohledávání zastaví
- Algoritmus je tedy úplný pouze pokud se řešení nachází v hloubce $\leq l$

#### Prohledávání s postupným prohlubováním

- Opakovaně aplikuje prohledávání do hloubky s limitem a zvyšuje limit
- Obchází nevýhody BFS a DFS
- Na první pohled to vypadá, že se zbytečně prohledává moc stavů, při konstantním branchingu má každé další tolik stavů kolik všechny předchozí dohromady, takže procházet opakovaně ty první patra není taková hrůza

#### Prohledávání podle ceny

- (Uniform-cost Search)
- uvažuje cenu na hranách, nalezne nejlevnější cestu mezi počátečním a cílovým stavem
- jde o zobecnění BFS, ale používá prioritní frontu
- Uzly jsou ve frontě seřazeny podle celkové ceny od počátečního stavu
- Ceny musí být nezáporné

#### Srovnání algoritmů

- $b$ - faktor větvení
- $d$ - hloubka cíle
- $m$ - maximální hloubka větve
- $C^∗$ - cena optimálního řešení (ekvivalent hloubky cíle pro oceněné hrany)

| | DFS | DFS s limitem | DFS s postupným prohlubováním | BFS | UCS - podle ceny |
|--------------------------|---------------------|----------------------|-------------------------------|--------------------|------------------------------------|
| **úplnost** | ne | ano, pro $$l \ge d$$ | ano\* | ano\* | ano\* |
| **optimálnost řešení** | ne | ne | ano\* | ano (pro nevážené hrany) | ano (pro nezáporné ceny) |
| **časová složitost** | $$O(b^m)$$ | $$O(b^\ell)$$ | $$O(b^d)$$ | $$O(b^{d+1})$$ | $$O(b^{1+\lfloor C^*/\epsilon \rfloor})$$ |
| **prostorová složitost** | $$O(bm)$$ | $$O(b\ell)$$ | $$O(bd)$$ | $$O(b^{d+1})$$ | $$O(b^{1+\lfloor C^*/\epsilon \rfloor})$$ |

### Informované prohledávání stavového prostoru
- Každý uzel je ohodnocen funkcí $f(n)$, která se může skládat z více komponent:
- Reálná cena cesty do uzlu $n$: $g(n)$
- Heuristická cena / odhad ceny cesty z $n$ do cíle: $h(n)$
- př. pro hledání cest do cílového města *Brno*
- $g(n)$ reálná cena cesty do města $n$
- $h(n)$ odhad cesty z $n$ do *Brna* - např. vzdálenost vzdušnou čarou

#### Heuristické hladové hledání
- Greedy best-first search
- Předpokládá nezáporné ceny
- Expandujeme vždy uzly, které se zdají být k cíli nejblíže, tj. $f(n) = h(n)$
- řešení nejsou optimální

#### A* search
- Kombinuje $g(n)$ a $h(n)$ tj. $f(n) = g(n) + h(n)$.
- Expanduje uzly s nejmenší $f(n)$.
- Předpokládá nezáporné ceny
- Nalezené řešení bude optimální
- Aby fungovalo správně, $h(n)$ musí být *přípustná* heuristika
- dolní odhad ceny od n k cíli
- na mapě vzdušná vzdálenost
- může to být cena řešení relaxované verze stejného problému (tzn. méně omezení na akce)
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

## Metaheuristiky - úvod

#### Co řeší metaheuristiky?

- Jeden z přístupů k řešení optimalizačních problémů.

#### Co je optimalizační problém?

- Chceme maximalizovat / minimalizovat nějakou účelovou funkci definovanou nad prohledávaným prostorem.
- Např. naplánování nejefektivnější cesty pro doručení balíků pošťákem.

#### Co je tedy přešně metaheuristika?

- Jedná se o metodologie / šablony / techniky / guidelines vyšší obecnější úrovně, které mohou být použity k nalezení základní heuristiky pro řešení optimalizačních problémů
- Např.:
- Genetické algoritmy jsou metaheuristiky. Konkrétní zvolené způsoby mutace a křížení jsou pak nalezené heuristiky.

#### Jaké další techniky kromě metaheuristik existují?


- **Exaktní metody**
- Garantují optimalitu (globální)
- Ovšem nejsou vhodné pro velké problémy (např. reálný TSP - Travelling Salesman Problem).
- **Přibližné metody**
- **Aproximační algoritmy**
- Garance na mez kvality řešení. (např. $\frac{17}{10}opt$)
- **Heuristické** algoritmy
- Cílem je najít kvalitní řešení za rozumný čas.
- Nemá žádnou garanci optimality.

### Reprezentace řešení (kódování)
Požadujeme:
- Každé řešení lze zakódovat
- Operace pro manipulaci s reprezentací jsou efektivní

typy reprezentací:
- lineární - vektor hodnot (binární, diskrétní)
- nelineární - složitější struktury (stromy, grafy, ...)

#### Binární kódování
- lineární reprezentace, vektor složený z 0 a 1
- Příklad - problém batohu (Knapsack problem):
- batoh má danou nosnost
- je daný seznam položek, u každé hmotnost a cenu
- cíl: vybrat předměty, tak aby je batoh udržel a jejich hodnota byla co nejvyšší
- Reprezentace:
$$
s = (s_1, s_2, ..., s_n)\\\text{ , kde } s_i = 1\text{, pokud je předmět $i$ v batohu jinak $0$}
$$

#### Diskrétní kódování

- lineární reprezentace, vektor diskrétních hodnot
- Například - problém přiřazení:
- Máme *n* úloh a *m* agentů, $m \ge n$
- Přiřazení agenta $a$ úloze $u$ stojí $C(a, u)$ peněz
- Cíl: přiřadit každé úloze agenta, aby byla celková cena nejnižší. Každý agent může vykonávat pouze 1 úlohu.
- *úlohy = {1, 2, 3, 4}*
- *agenti = {A, B, C, D, E, F}*
- Reprezentace: $s = (B, C, F, E)$ odpovídá přiřazení 1-B, 2-C, 3-F, 4-E
- diskrétní kódování lze použít pro reprezentaci **permutací**
- vhodné pro seřazení, směrování, plánování.
- Každý element problému se musí v reprezentaci objevit pouze jednou.
- Např. TSP:
- Máme *n* měst, které musí pošťák projít každé přesně jednou a reprezentace nám udává pořadí průchodu.

#### Nelineární reprezentace
- Často se jedná o grafové struktury, stromy
- radši sem nezabrušovat,

### Účelová funkce
- účelová funkce specifikuje cíl, kterého chceme dosáhnout
- rozlišujeme 2 základní typy - soběstačné a směrující

#### Soběstačná účelová funkce
- Přímo vychází z formulace problému.
- Ideální situace
- účelová funkce problému lze rovnou použít pri optimalizaci
- Příklad soběstačné funkce:
- TSP: $\min \sum{ dist(x, y)}$
- Příklad nesoběstačná funkce:
- SAT problém = je formule F splnitelná?
- účelová funkce: Je formule F přiřazením splněná? $\rightarrow$ True/False

#### Směrující účelová funkce
- nahrazuje původní účelovou funkci pokud nebyla vhodná pro optimalizaci
- Pro k-SAT:
- Máme formuli F, složenou z *m* klauzulí v CNF
- **původní účelová funkce:** Je formule F přiřazením splněná? $\rightarrow$ True/False
- **směrující účelová funkce:** Kolik klauzulí je splněných?

### Manipulace s omezeními
- problémy často definují různá omezení pro řešení
- přípustné řešení = splňuje omezení, nepřípustné = nesplňuje
- jak přistupovat k nepřípustným:
- **Zamítací strategie**
- Uchováváme pouze přípustná řešení
- **Penalizující strategie**
- Rozšíříme původní účelovou funkci o penalizaci nepřípustných řešení
- **Opravné strategie**
- Opravují nepřípustná řešení

## Metaheuristiky pracující s jedním řešením

#### Jak vypadá kostra algoritmu?

Vstup: inicialni reseni s_0

t = 0
repeat
    C     := generuj mnozinu kandidatnich reseni z s_t (castecne/uplne okoli s_t)
    s_t+1 := vyber reseni z C pro nahradu aktualniho reseni s_t
    t     := t + 1
until splnena podminka ukonceni

Vystup: nejlepsi nalezene reseni

#### Jak vybrat iniciální řešení?

- Náhodné řešení
- Heuristické řešení
- Získáme ho např. pomocí hladového algoritmu.
- Částečně nebo úplně inicializované uživatelem.

#### Jak generovat nová řešení?

* Zavedeme si pojem **okolí**.
* **Co je okolí?**
- Nechť $S$ je množina řešení.
- Pak okolí je funkce $O: S → 2^S$
- To znamená, že každému řešení $s \in S$ přiřadí nějakou podmnožinu z $S$ (okolní řešení).

- **Jaká okolí můžou existovat?**

- **Malá okolí**
- **k-distance**
- Velikost okolí pro 2-distance je $n(n - 1)/2$
- Typické pro **permutační problémy.**
- Např. TSP
- k-distance zamění *k* elementů


- **k-opt**

- *k-opt* vymaže *k* hran a nahradí je dalšími *k* hranami.
- Velikost okolí pro 2-opt je $n(n-1)/2 - n$. (všechny páry hran, kromě sousedních párů).
- Typické pro **permutační problémy.** (TSP, ...)
- **Permutační okolí**

- Typické pro **rozvrhovací problémy.**
- Založené na **pozici**
- Založené na **pořadí**

* **Rozsáhlá okolí**

* Pomáhají zlepšovat kvalitu prohledávání za cenu vyšší výpočetní složitosti.
- **Ejection chain (řetězec odstranění)**
* Vehicle Routing Problem (VRP)
* **Cyclic exchange (cyklická výměna)**
- Problémy rozdělení (partitioning problem)
- Např. vyvažování závaží

### Pokročilé lokální prohledávání

- Základní lokální prohledávání:
- Nejstarší a nejjednodušším lokálním prohledáváním je **hill climbing** algoritmus.
- Hlavní myšlenka: nahraď aktuální řešení lepším řešením (sousedním).

        Vstup: inicialni reseni s0

        s := s0
        while neni splnena podminka ukonceni 
            O := generuj sousedy z okoli s
            if neexistuje lepsi soused
                break
            s := vyber lepsiho souseda z O
        end while

        Vystup: konecne nalezene reseni (lokalni optimum)

- Výběr souseda
- Metoda největšího spádu (steepest descent, saddle-point method, **gradient descent**)
- Vybere se nejlepší soused, který nejvíce zlepšuje účelovou funkci (z analýzy víme, že v opačném směru největšího stoupání tj. opačně ke gradientu funkce)
- Vybere se první zlepšující soused, který je lepší než aktuální řešení.
- Náhodný výběr mezi zlepšujícími sousedy.

- Vylepšení lokálního prohledávání
- **Umožníme vybírat horší sousedy**
- Simulované žíhání
- Algoritmy založené na přijetí prahem (threshold accepting)
- Algoritmus velké potopy (Great Deluge algorithm)
- Tabu prohledávání
- **Iterace s různými řešeními**
- Opakované (multistart) lokální prohledávání
- Iterativní (iterated) lokální prohledávání
- **Použití různých okolí**
- Prohledávání s proměnlivým okolím (variable neighborhood search)
- **Změna účelové funkce**
- Řízené lokální prohledávání (guided local search)

### Simulované žíhání (Simulated Annealing)

hlavní myšlenky:

* Akceptuje i výběr horšího souseda.
* Inspiruje se fyzikálním procesem ochlazování kovů.
- Při vyšší teplotě atomy více kmitají a pravděpodobnost změny krystalické mřížky je vysoká (energie je vysoká).
- Při postupném ochlazování se atomy usazují do stabilní polohy s nejmenší energii a pravděpodobnost změny je menší.
- Na začátku tedy přijímáme horší sousedy s větší pravděpodobnosti.

**Jak vypadá pseudokód SA?**

Vstup: Způsob chlazení, E funkce posuzujici kvalitu

s := inicialni reseni
T := inicialni teplota

Repeat

Repeat

s' := nahodne vyber souseda
ΔE = E(s') - E(s)
if je s' lepsi reseni (ΔE <= 0) then
s := s'
else
s := s' s pravdepodobnosti exp(-ΔE/T)

Until splnena podminka rovnovahy
T := update teploty

Until splnena podminka ukonceni

Vystup: Nejlepsi nalezene reseni.

#### Jaké mohou být podmínky rovnováhy (equilibrium state)?
- Dostatečný počet kroků při každé teplotě.
- Např: statický, dynamický, adaptivní

#### Jaké mohou být podmínky ukončení?
- Dosažení zvolené nižší teploty.
- Pevný počet iterací, při kterých se nezlepšilo řešení.

#### Algoritmy založené na přijetí prahem (threshold accepting)
- Akceptuje se horší řešení s **maximálním zhoršením o prahovou hodnotu Q.**
* **Pseudokód**

    s := inicialni reseni
    Q := inicialni prah

    repeat
        repeat
            s' := nahodny soused z okoli s
            ΔE := E(s') - E(s)
            if ΔE <= Q then
                s := s'
        until splnena podminka rovnovahy
        Q := aktualizace prahu
    until splnena podminka ukonceni

#### Algoritmus velké potopy (Great Deluge algorithm)
* Analogie s horolezcem, který se snaží zůstat nad zvyšující se vodní hladinou při potopě.
* Jak vypadá pseudokód pro maximalizační problém?

    Vstup: f - ucelova funkce

    s     := inicialni reseni
    up    := rychlost deste
    level := inicialni uroven vodni hladiny

    repeat
        s' := nahodny soused z okoli s
        if f(s') > level then
            s := s'
        level := level + up
    until splnena podminka ukonceni

    Vystup: Nejlepsi nalezene reseni

- Pro minimalizační problém chceme hladinu level redukovat a snažíme se zůstat pod hladinou level.

### Algoritmus tabu prohledávání
- Zavádí **tabu seznam** ("blacklist"), kam se ukládají zakázané řešení
- Např. nedávno navštívené řešení

#### Co když je řešení v tabu seznamu velmi dobré?

- Pokud splňuje tzv. **aspirační kritérium**, pak ho použijeme.
- **Pseudokód**

s := inicialni reseni
inicializace tabu seznamu

repeat
s' := nejlepsi _pripustne_ reseni v okoli s
(neni v tabu seznamu nebo plati aspiracni kriterium)
aktualizace tabu seznamu a aspiracniho kriteria
until splnena podminka ukonceni

Vystup: Nejlepsi nalezene reseni

### Opakované lokální prohledávání (Multistart local search)
- Opakuje se lokální prohledávání znovu, a to s náhodným iniciálním řešením.

### Iterativní lokální prohledávání
- Vylepšení opakovaného lokálního prohledávání
- Nalezené lokální optimum použito při další iteraci lokálního prohledávání.
- **Pseudokód**

s := inicialni reseni
s* := lokalni_prohledavani(s)

repeat
s' := nahodne zmen s* (angl. perturb)
s"* := lokalni_prohledavani(s')
s* := akceptuj nove reseni pokud je splneno kriterium prijeti
until splnena podminka ukonceni

Vystup: Nejlepsi nalezene reseni.

​
### Prohledávání s proměnlivým okolím (Variable Neighbourhood Search)
- Pro nalezení řešení se používají různá okolí.


#### Zlepšující prohledávání s proměnlivým okolím (Variable Neighbourhood Descent)
* Změní okolí při každém naleznutí lokálního optima. Končí když se řešení již nezlepšuje.
* Tedy např. zvyšuje $k$ v k-distance.
- **Pseudokód**

    s := inicialni reseni
    i = 1
    while i <= i_max do
        s' := nejlepsi soused z okoli O_i
        if f(s') < f(s) then
            s := s'
            i := 1
        else
            i := i + 1

    Vystup: Nejlepsi nalezene reseni


### Řízené lokální prohledávání (Guided local search)
- Změna účelové funkce vzhledem k nalezenému lokálnímu optimu. Charakteristiky nalezeného lokálního optima jsou použity k úpravě účelové funkce.
- Např. u routing problémů to může být cena hran atd.
#### Jak obecně účelovou funkci změnit?

$$
\begin{aligned}
f'(s) &= f(s) + \lambda \sum\limits^{m}_{i=1} p_i I_i(s) \\ I_i(s) &= 1\text{, pokud $s$ má charakteristiku $i$, jinak 0} \\ \lambda &= \text{normalizace} \\ p_i &= \text{penalizace charakteristiky $i$}
\end{aligned}
$$

- Penalizuje se vždy charakteristika *i* s nejvyšším užitkem

$$u_i(s) = I_i(s) \frac{c_i}{1 + p_i} \\ c_i = \text{cena charakteristiky $i$}$$

- **Pseudokód**

s := inicialni reseni
p_i := 0 pro vsechna i = 1,2,...,m

repeat
s' := lokalni_prohledavani(s) s upravenou ucelovou funkci
spocitej uzitek z s' pro vsechny charakteristiky
u_j := urci charakteristiku s maximalnim uzitkem
p_j := p_j + 1 (zmen ucelovou funkci penalizaci charakteristiky j)
until splnena podminka ukonceni

Vystup: Nejlepsi nalezene reseni.

## Metaheuristiky s populacemi

### Jaké jsou hlavní koncepty?
* Vylepšujeme celou populaci (množinu) řešení na rozdíl od jednoho.
* Kombinujeme nalezená řešení.
### Jak vypadá kostra algoritmu?

P := Generovani inicialni populace
t := 0
Repeat
P'_t := vygeneruj novou populaci
P_t+1 := vyber populaci z (P_t + P'_t)
t := t + 1
Until splnena podminka ukonceni

Vystup: Nejlepsi nalezene reseni.

### Jaké různé typy metaheuristik s populacemi existují?
- **Evoluční algoritmy**
- Genetické algoritmy
- Evoluční strategie
- Evoluční programování
- Genetické programování
- **Inteligence hejna (Swarm intelligence)**
- Optimalizace mravenčí kolonie (ant colony optimization)
- Optimalizace jedinců hejna (particle swarm optimization)
- Optimalizace včelím rojem (bee colony optimization)
- **Umělé imunitní systémy (Artificial immune systems)**

### Jakými způsoby můžeme vygenerovat počáteční populaci?
- Náhodné generování
- Sekvenční diversifikace
- Řešení jsou postupně generována s maximální odlišnosti
- Výpočetně náročné
- Paralelní diversifikace
- Řešení jsou generována paralelně nezávisle na sobě se snahou o maximální odlišnost.
- Může být složitější než samotný problém.
- Heuristická inicializace
- Řešení jsou generována libovolným heuristickým algoritmem.
- Hrozí malá odlišnost v populaci.

### Jaké mohou existovat podmínky ukončení?
- **Statické**
- Konec prohledávání je předem znám.
- Např:
- pevný počet iterací
- maximální počet vyhodnocení účelové funkce
- limit na CPU zdroje
- **Adaptivní**
- Konec prohledávání není předem známý.
- Např.
- pevný počet iterací bez zlepšení
- vypočítáno dostatečně kvalitní řešení
- malá odlišnost řešení v populaci

### Evoluční algoritmy

#### Jaké společné koncepty mají evoluční algoritmy?
- **Reprezentace**
- populace / generace = množina řešení
- chromozom / jedinec = jedno konkrétní zakódované řešení
- gen = rozhodovací proměnná v rámci řešení
- alely = možné hodnoty rozhodovací proměnné
- Např.
- TSP problém
- Máme města: {A, B, C, D} = alely
- Populace: {ABCDA, ADCBA, ACDBA, ...}
- Chromozom: ABCDA
- Gen: chromozom ABCDA je tvořen geny A, B, C, D, A
- **Vhodnost (fitness function) = účelová funkce**
- **Strategie výběru**
- Strategie výběru rodičů (řešení) pro vytváření nové generace.
- **Strategie reprodukce**
- Operace vytvářející nové jedince.
- Křížení
- Mutace
- **Strategie náhrady**
- Strategie výběru jedinců (ze starých a nově vytvořených) do nové generace

#### Jaké typy evolučních algoritmů známe?
- **Genetické algoritmy**
- Významná role operátorů křížení a mutace.
- **Evoluční strategie**
- Většinou používány na spojité optimalizace s vektory reálných čísel.
- Křížení je využito zřídka.
- **Evoluční programování**
- Spojitá optimalizace
- Používá se méně z důvodu podobnosti s evolučními strategiemi.
- **Genetické programování**
- Jedinci jsou programy - nelineární reprezentace založené na stromech.
- Automatické generování programů řešících danou úlohu.

#### Jak vypadá kostra evolučních algoritmů?

P := vygenerovani inicialni populace
t := 0

Repeat
vyhodnot populaci P_t
P'_t := strategie vyberu
P'_t := strategie reprodukce
vyhodnot populaci P'_t
P_t+1 := strategie nahrady
t := t + 1
Until splnena podminka ukonceni

Vystup: Nejlepsi populace ci jedinec.

#### Jaké jsou různé způsoby strategie výběru?
- **Výběr ruletovým kolem (Roulette wheel selection)**


- **Výběr rankováním (Rank-based selection)**
- Pro každého jedince je spočítán rank (pořadí) a dle něj jsou vybírání jedinci.
- Rank může být např. použit pro výpočet pravděpodobnosti zvolení. A poté být aplikován u ruletového kola.
- **Turnajový výběr (Tournament selection)**
- Náhodný výběr *k* jedinců.
- Z *k* jedinců se vybere nejlepší.
- Pro výběr *m* jedinců se aplikuje turnaj *m*-krát.
- **Jaké jsou různé způsoby strategie reprodukce?**
- **Křížení**
- *n-*ární operátor, který kombinuje *n* jedinců (rodičů)
- Rodiče se kříží s nějakou zadanou pravděpodobností.
- **Jak se mohou křížit lineárně zakódovaní jedinci?**

- k**-bodové křížení (k-point crossover)**

**1-bodové**
**2-bodové**

- **uniformní křížení (uniform crossover)**
- **Jak se mohou křížit jedinci reprezentovány permutacemi?**
- **Order crossover (OX)**
- **Mutace**
- S malou pravděpodobnosti nastane mutace jedince.
- **Jakými způsoby můžeme zmutovat jedince?**
- **Mutace v binární reprezentaci**
- Flipneme hodnoty.
- **Mutace v diskrétní reprezentaci**
- Změna genů za jinou hodnotu v abecedě.
- **Mutace v permutacích**
- vložení, výměna, inverze hodnot
- **Jaké jsou různé způsoby strategie náhrady?**
- **Úplná náhrada (generational replacement)**
- Celá popula rodičů bude nahrazena novou generací.
- **Náhrada jednotlivce (steady-state replacement)**
- Generuje se pouze jediný potomek, který nahradí např. nejhoršího jedince z populace.
- **Náhrada pevného množství jedinců**
- **Elitářský model**
- Výběr nejlepších jedinců mezi rodičemi a potomky.
- Rychlá a potenciálně předčasná konvergence.

### Optimializace mravenčí kolonie (Ant colony optimization, ACO)

#### Jaké jsou hlavní myšlenky ACO?
- Mravenčí kolonie je schopna najít nejkratší cestu mezi dvěma body.
- Mravenci zanechávají na zemi chemickou stopu (feromony).
- Feromony mravence vedou k cíli.
- Feromony se postupně vypařují.
#### Jak vypadá základní kostra algoritmu?

inicializace feromonové stopy (typicky matice / vektor)

Repeat
for kazdeho mravence do
konstrukce reseni pomoci feromonove stopy
aktualizace feromonove stopy
vyparovani
zesileni
Until splnena podminka ukonceni

Vystup: Nejlepsi nalezene reseni nebo mnozina reseni.

#### Jakým způsobem se aktualizují feromonové stopy?
- **Vypařování (Evaporation)**
- *T* je matice feromonových stop
- *T_ij = (1 - ro) T_ij*
- *ro* je z [0, 1]
- **Zesilování (Reinforcement)**
- **Online aktualizace**
- T_ij aktualizováno v **každém kroku** mravence.
- **Online pozdržená aktualizace**
- T aktualizováno po nalezení úplného řešení **jedním** mravencem.
- **Offline aktualizace**
- T aktualizováno po nalezení úplného řešení **všemi** mravenci.
- Feromony budou aktualizovány podle nejlepšího řešení.

## Plánování

### Co je cílem plánování?
- Zjistit jaké akce se mají aplikovat (a na jaké stavy), abychom dosáhli požadovaných cílů.

### Jak vypadá formální konceptuální model?
- Plánování se zabývá volbou a organizací akcí, které mění stav systému.
- **Co je součástí takového systému?**
- Množina stavů $S$
- Množina akcí $A$ (kontroluje plánovač)
- Množina událostí $E$ (mimo kontroly plánovače)
- Přechodová funkce $\gamma: S \times A \times E \to P(S)$

## Klasické plánování

### Jak zjednodušíme konceptuální model? (= klasické plánování)
- Systém je **konečný.**
- Systém je **plně pozorovatlený.**
- Máme úplné informace o stavu systému.
- Systém je **deterministický.**
- Systém je **statický.**
- Množina událostí E je prázdná.
- Cíle jsou **omezené**.
- Cílem je dosažení některého stavu z množiny cílových stavů
- Plány jsou **sekvenční.**
- Plánem je úplně uspořádaná posloupnost akcí.
- Čas je **implicitní.**
- Akce i události jsou instantní.
- Plánujeme **offline.**
- Stav systému se nemění v průběhu plánování.

### Jak můžeme reprezentovat systémy?
#### Množinová reprezentace
- Stav systému je popsan množinou výroků
- např. {onground, at2}
- Akce je syntaktický výraz specifikující:
- jaké výroky musí patřit do stavu, aby na něj byla akce aplikovatelná
- např. take: {onground}
- jaké výroky akce přidá nebo smaže, aby vytvořila nový stav
- např. take: {onground} - {holding} +

#### Klasická reprezentace
* Zobecňuje množinovou reprezentaci **směrem k predikátové logice**.
* **Stavy** jsou množiny logických atomů, které jsou TRUE/FALSE.
* **Akce** jsou reprezentovány plánovacími operátory, které mění pravdivostní hodnotu těchto atomů.
* **Přesněji**
- *L* je jazyk - konečná množina predikátových symbolů a proměnných (bez funkčních symbolů!)
- atom je predikátový symbol s argumenty
- např. *on(c3, c1)*
- můžeme používat proměnné
- **Jak vypadají plánovací operátory u klasické reprezentace?**
- Operátor *o* je trojice (*name, precond, effects*)
- name: př. *take(x1, x2, ..., xn)*
- jméno operátoru a parametry operátoru
- precond: předpoklady pro akci
- effects: důsledky (atomy, které se stanou pravdivými aplikací operátoru)


- **Jak se změní stav po aplikaci akce?**

$$\begin{aligned} S^+ &= \{\text{pozitivní atomy v $S$}\} \\ S^- &= \{\text{atomy, jejichž negace je v $S$}\} \end{aligned}$$

Akce *a* je použitelná práve když,

$$precond^+(a) \subseteq s \wedge precond^-(a) \cap s = \emptyset$$

Výsledkem je pak

$$\gamma(s, a) = (s - effects^-(a)) \cup effects^+(a)$$

### Plánování se stavovým prostorem

- **Co je prohledávaný prostor?**
- Odpovídá stavovému prostoru plánovacího problému
- Uzly odpovídají stavům
- Hrany prechodom pomocou akcií
- Cieľom je nájsť cestu medzi počiatočným a koncovým stavom

- **Co je dopředné plánování?**
- K cíli se dostáváme z počátečního stavu postupně. U zpětného plánování pak postupujeme od cíle k počátečnímu stavu.
- Je potrebné vedieť rozhodnúť či je stav **cieľový**, nájsť množinu **aplikovateľných akcií**, vypočítať stav, kde sa dostaneme po **aplikácii akcie**.
- **Pseudokód**

Vstup: (O, s0, g)

s := s0
plan := prazdny

loop
if s splnuje g then
return plan
E := vsechny proveditelne akce
if E je prazdne then
return FAIL
nedeterministicky vyber akci z E
s := proved akci
plan := plan + a
- **Vlastnosti:**
- **korektny** - ak vráti plán, tak je riešením
- **úplný** - ak existuje plán, tak ho aspoň jedna nedeterministická vetva nájde
- Deterministická implementácia: DFS, BFS, A* algortimus
- Príliš veľa možností (vetviaci faktor) => heuristika, orezávanie
- **Co je zpětné plánování?**
- Začínáme s cílem a jdeme přes podcíle k počátečnímu stavu.
- U operátorů bereme effects jako preconds.
- Je potrebné vedieť rozhodnúť či stav odpovedá **cieľu**, nájsť množinu **relevantných akcií** pre cieľ, vypočítať **podciele** umožňujúce aplikovať akciu.
- Akcia *a* je **relevantná** pre cieľ *g* práve vtedy, keď prispieva do ciela *g* a efekty nie sú v konflikte s cielom *g*.
- **Regresná množina** cieľa *g* pre relevantnú akciu *a* odstráni z *g* efekty akcie *a* a pridá podmienky akcie *a*.
- **Pseudokód**

Vstup: (O, s0, g)

plan := prazdny

loop
if s0 splnuje g then
return plan
A := vsechny relevantné akce
if A je prazdne then
return FAIL
nedeterministicky vyber akci z E
plan := a + plan
g := preved spätne akciu
(regresná množina)
- **Vlastnosti:**
- **korektny** - ak vráti plán, tak je riešením
- **úplný** - ak existuje plán, tak ho aspoň jedna nedeterministická vetva nájde
- možné implementovať deterministicky
- možné zmenšiť vetvenie pomocou **liftingu**
- **Co je STRIPS?**
- Redukuje prehľadávaný priestor zpätného prehľadávania.
- Z podcieľov rieši vždy len časť odpovedajúcu predpokladom poslednej pridanej akcie
- Ak aktuálny stav splňuje všetky predpoklady operátoru, daný operátor sa použije a záväzok sa nebude riešiť pri backtrackingu.
- Nedokáže efektívne riešit Sussmanovu anomáliu (nájde len redundantné plány), možné riešiť prelíňaním plánov alebo použitím doménovej informácie.

<!--
- **Co je plánování v prostoru plánů?**
- Podobné spätnému plánovániu v stavovom priestore
- Začína s prázdnym plánom (počiatočný stav a ciele)
- Pridávame akcie, kým sú otvorené ciele
- Pridávame väzby medzi prítomnými akciami
- **Plánovanie == Opravovanie kazov v čiastočnom pláne**
- Možné úpravy plánu:
- pridanie akcie
- zviazanie premenných
- pridanie podmienky usporiadania
- pridanie kauzálnej väzby
- **Co jsou kazy plánu?**
- **Otevřený cíl** - o predpoklade *p* operátoru *b* nebolo rozhodnuté ako ho splniť. => nájsť operátor *a* použiteľný na splnenie *p*, zviazať premenné, vytvoriť kauzálnu väzbu.
- **Hrozba** - akcia, ktorá môže porušiť kauzálnu väzbu => preusporiadať alebo naviazať premennú, aby nebola porušená kauzálna väzba
- **Pseudokód**

Vstup: (plan)

kazy := otvorene ciele planu + hrozby

if kazy je prazdne then return plan
vyber lubovolny kaz z kazy
zjemnia := mnozina moznosti
odstranujucich kaz
if zjemneni je prazdne then return fail
nedeterministicky vyber z zjemnenia
pouzi zjemnenie
rekurzivne planuj na zjemnenom plane

- Voľba kazu je deterministická, zjemnenia nie
-->

## Neurčitost

### Definice pravděpodobností

**Podmíněná pravděpodobnost**

- $P(x \mid y) = \dfrac{P(x \wedge y)}{P(y)}$ nebo v součinovém tvaru $P(x \wedge y) = P(x \mid y) \cdot P(y)$.

**Vektorová podoba**

- $\textbf{P}(X, Y) = \textbf{P}(X|Y) \cdot \textbf{P}(Y)$
- $\textbf{P}(X, Y)$ - sdružené pravděpodobnosti $P(X=x \wedge Y = y)$ pro každou kombinaci $x,y$.
- $\textbf{P}(X|Y)$ - podmíněné pravděpodobnosti $P(X = x \mid Y = y)$ pro každý možný pár $x, y$.

**Nezávislost**

- Platí $\textbf{P}(X, Y) = \textbf{P}(X) \cdot \textbf{P}(Y)$

**Marginalizace**

- $\textbf{P_X}(Y) = \sum\limits_{x}P(x, Y)$

**Bayesova věta**

- $\textbf{P}(X \mid Y) = \dfrac{\textbf{P}(Y \mid X) \cdot \textbf{P}(X)}{\textbf{P}(Y)}$
- S normalizační konstantou zanedbáme $\dfrac{1}{\textbf{P}(Y)}$ a dostaneme vztah $\alpha \cdot \textbf{P}(Y \mid X) \cdot \textbf{P}(X)$.

**Normalizace**

- Nechť $\textbf{e}$ označuje pozorované hodnoty (evidence).

- Platí $P(X \mid \textbf{e}) = \alpha \textbf{P}(X, \textbf{e}) = \alpha \sum\limits_y \textbf{P}(X, \textbf{e}, y)$, kde $y$ jsou všechny kombinace hodnot nepozorovaných veličin $Y$.

- Proč to platí? Ukážeme si to na příkladu:

- $P(cavity | toothache) = \dfrac{P(cavity \wedge toothache)}{P(toothache)} = \dfrac{1}{P(toothache) } \cdot P(cavity \wedge toothache)$

- $P(\neg cavity | toothache) = \dfrac{P(\neg cavity \wedge toothache)}{P(toothache)} = \dfrac{1}{P(toothache) } \cdot P(\neg cavity \wedge toothache)$

- $1/P(toothache)$ se používá v obou vztazích a její hodnota se nemění v závislosti na hodnotě $cavity$; můžeme jí tedy brát jako **normalizační konstantu**.

- Spojením dvou vztahů máme tedy

$$
\textbf{P}(Cavity \mid toothache) = \alpha \textbf{P}(Cavity \wedge toothache) = \alpha \textbf{P}(Cavity, toothache)
$$

- **Jaký je rozdíl mezi diagnostickou a kauzální vazbou?**
- **Diagnostická vazba**
- P(pricina | nasledek) např. P(nemoc | symptomy)
- **Kauzální vazba**
- P(nasledek | pricina) např. P(symptomy | nemoc)

## Bayesovské sítě

### Co je bayesovská síť?

- Orientovaný acyklický graf (DAG)
- Vrchol = diskrétní/spojitá náhodná proměnná
- Hrana z $X$ do $Y$ znamená, že $X$ je rodičem $Y$.
- Každý vrchol $X_i$ má podmíněné pravděpodobnostní rozdělení $P(X_i | parents(X_i))$.

### Co reprezentuje bayesovská síť?
- Úplnou sdruženou distribuci. Je dána vztahem:

$$P(x_1, x_2, ..., x_n) = \prod\limits_{i}P(x_i \mid parents(X_i))$$

- **Příklad: Máme zadánou bayesovskou síť**


* Nechť b je Burglary = true, pak ¬e znamená Earthquake = false.
* **Jak vypočítáme $P(j, m, a, ¬b, ¬e)$?**
- Podle předešlého vztahu. Tj. součin všech $P(x_i | parents(X_i))$, kde $x_i = j, m, a, ¬b, ¬e$.

$$
\begin{aligned}
P(j,m,a,\neg b, \neg e) &= P(j \mid a) \cdot P(m \mid a) \cdot P(a \mid \neg b, \neg e) \cdot P(\neg b) \cdot P(\neg e) \\ &= 0,90 \cdot 0,70 \cdot 0,001 \cdot 0,999 \cdot 0.998 \\&= 0.000628
\end{aligned}
$$

### Jak zkonstruovat algoritmicky bayesovskou síť?

1. Rozhodni, jaké náhodné proměnné jsou potřeba a uspořádej je.

- Doporučené uspořádání je takové, kdy příčiny předcházejí následky.
2. Máme uspořádané náhodné proměnné $X_1, X_2, ..., X_n$
1. Vybereme nejmenší množinu rodičů pro $X_i$ tak, že platí

$$
\textbf{P}(X_i \mid Parents(X_i)) = \textbf{P}(X_i \mid X_{i-1}, ..., X_1)
$$
* tj. rodiči $X_i$ jsou pouze ty uzly, které přímo ovlivňují $X_i$.
2. Z rodičů vedeme hranu do $X_i$.
3. Vypočteme podmíněné pravděpodobnosti pro $P(X_i | parents(X_i))$.

### Jak se odvozuje z bayesovské sítě (inference)?

- Zajímá nás výsledek $P(X | e)$, kde e jsou pozorované (evidence; známe) hodnoty.

#### Exaktně pomocí enumerace
- Víme, že platí vztah

$$P(X \mid e) = \alpha P(X, e)$$

- Příklad

Vypočítejte P(b | j, m).

$$\begin{aligned}P(b \mid j,m) &= \alpha P(b,j,m,E,A) \\&= \alpha P(b)\cdot\sum\limits_{e}\left(P(e) \cdot\sum\limits_{a}P(a \mid b, e) \cdot P(j \mid a) \cdot P(m \mid a) \right) \end{aligned}$$

- Ve výpočtu se některé vztahy opakují a vede tak k neefektivitě.

- Možné řešení: eliminace proměnných (dynamické programování)
#### Aproximačně pomocí vzorkování
- Přímé vzorkování
- Vzorkování se zamítáním
- Zamítneme vzorky, které nejsou kompatibilní s pozorovanými hodnotami $e$.
- Vážení věrohodností
- Zafixujeme hodnoty z pozorování $e$ a vzorkujeme pouze zbytek. Výsledky provážíme.

## Čas a neurčitost (Hidden Markov Model)

### Co je přechodový a senzorický model?
- Nechť dynamiku světa (čas) modelujeme pomocí časových řezů (stavů).
- Každý stav bude popsán:
- Nepozorovatelnými náhodnými proměnnými $X_t$
- Pozorovatelnými náhodnými proměnnými $E_t$
#### Přechodový model
- Popisuje jak je stav ovlivněn předchozími stavy. Tj.

$$
\textbf{P}(X_t \mid X_0, X_1, ..., X_{t-1}) = \textbf{P}(X_t \mid X_{0:t-1})
$$

#### Senzorický model
- Popisuje, na čem závisí pozorované náhodné proměnné $E_t$. Tj.

$$
\textbf{P}(E_t\mid X_{0:t}, E_{1:t-1})
$$

### Co je Markovský předpoklad?
- Současný stav závisí pouze na pevně daném konečném počtu předchozím stavů.

$$
\textbf{P}(X_t \mid X_0,X_1, ...., \color{color{red}}{X_{t-1}}) = P(X_t \mid \color{color{red}}{X_{t-1}})
$$

tj. **Markovův řetězec prvního řádu**

### Co je předpoklad stacionárního procesu?
- Distribuce $P(X_t | X_{t-1})$ je stejná pro všechny časy $t$.

### Co je Markovský senzorický předpoklad?
- Pozorované proměnné závisí pouze na nepozorovatelných proměnných $X_t$ ze stejného stavu.

$$\textbf{P}(E_t \mid X_{0:t}, E_{1:t-1}) = \textbf{P}(E_t \mid X_t)
$$

### Co je filtrace?
- Chceme zjistit pravděpodobnost aktuálního stavu na základě dosavadních pozorování

$$\textbf{P}(X_t \mid e_{1:t})$$

- Platí rekurzivní vztah

$$
\textbf{P}(X_{t+1} \mid e_{1:t+1}) = \alpha \color{color{red}}{\textbf{P}(e_{t+1} \mid X_{t+1})} \sum\limits_{x_t}\color{color{blue}}{\textbf{P}(X_{t+1} \mid x_t)} \color{green}{\textbf{P}(x_t \mid e_{1:t})}
$$

$$
\begin{aligned}&\color{color{red}}{\textbf{P}(e_{t+1} \mid X_{t+1})} & \text{známe ze senzorického modelu} \\ &\color{color{blue}}{\textbf{P}(X_{t+1} \mid x_t)}& \text{známe ze přechodového modelu} \\ &\color{green}{\textbf{P}(x_t \mid e_{1:t})} &\text{známe z rekurze}\end{aligned}
$$

### Co je predikce?
- Chceme zjistit pravděpodobnost budoucího stavu na základě dosavadních pozorování

$$
\textbf{P}(X_{t+k} \mid e_{1:t})\text{ pro $k > 0$}
$$

- Jedná se víceméně o filtraci bez přidávání dalších pozorování (et+1)

$$
\textbf{P}(X_{t+k+1} \mid e_{1:t}) = \sum\limits_{x_{t+k}}\textbf{P}(X_{t+k+1} \mid x_{t+k})\textbf{P}(x_{t+k} \mid e_{1:t})
$$

### Co je vyhlazování?

- Chceme zjistit pravděpodobnost minulého stavu na základě dosavadních pozorování

$$
\textbf{P}(X_k \mid e_{1:t}) \text{ pro $0 \leq k < t$}
$$

- Platí

$$
\begin{aligned}\textbf{P}(X_k \mid e_{1:t}) &= \textbf{P}(X_k \mid e_{1:k}, e_{k+1:t}) \\ &= \alpha \color{red}{\textbf{P}(X_k \mid e_{1:k})} \color{blue}{\textbf{P}(e_{k+1:t} \mid X_k)} \end{aligned}
$$

$$
\begin{aligned} &\color{red}{\textbf{P}(X_k\mid e_{1:k})} &\text{vztah známe již z filtrace (dopředný výpočet)} \\ &\color{blue}{\textbf{P}(e_{k+1:t} \mid X_k)} & \text{zpětný výpočet}\end{aligned}
$$

$$
\color{blue}{\textbf{P}(e_{k+1:t} \mid X_k)} = \sum\limits_{x_{k+1}}P(e_{k+1} \mid x_{k+1})P(e_{k+2:t} \mid x_{k+1})P(x_{k+1} \mid X_k)
$$

## Markovovský rozhodovací proces (MDP)

<!--
- agent se pohybuje v prostředí
- agent řeší sekvenční rozhodovací problém
- na základě současného **stavu**, jakou **akci** mám dělat, abych průměrně získal co nejvíc **rewardů**?
- chování agenta v MDP popisujeme **strategií** (policy, značená $\pi$)
- přiřazuje každému stavu akci, kterou agent udělá: $a =\pi(s)$
- případně stochastickou policy, obvykle značenou $\pi(a \mid s)$
- která pro daný stav vrací distribuci přes akce
- stav prostředí se mění na základě předchozího stavu a akce agenta
- přechody popisuje podmíněná pravděpodobnost $P(s' \mid s, a)$

-->

### Iterace hodnot

### Iterace strategie

## Robotika

- **Co je robot?**
- Fyzický agent, který vykonává úlohy manipulací s fyzickým světem.
- **Jaké typy robotů známe?**
- **Manipulátor**
- Fyzicky pripevněny k pracovnímu místu
- Např. **roboticka ruka**
- **Mobilní robot**
- Pohybují se v prostředí pomocí kol, nohou, ...
- Např. bezpilotní vozidla, letadla, ...
- **Mobilní manipulátor**
- Např. humanoidní roboti

- **Čím je vybaven robot?**
- **Efektory** = umožňují uplatnit fyzický pohyb
- **Senzory** = umožňují robotovi vnímat okolní svět
- **Pasivní**
- Slouží k pozorování prostředí.
- **Aktivní**
- Vysílají energii do prostředí
- Např. sonar
- Dále je můžeme dělit podle vnímání různých vlastností
- Prostředí
- Např. **dálkoměry** pro měření vzdálenosti od blízkých objektů
- Robotovo umístění
- **lokační senzory**
- Robotovy vnitřní konfigurace
- Např. gyroskopy, meření konfigurací robotických kloubů, motorů, ...

- **Co jsou stupně volnosti (degree of freedom, DOF)?**
- Popisuje návrh efektoru.
- Jeden DOF = nezávislý směr, ve kterém se robot / jeho efektor může pohybovat.


- **Co je kinematický a dynamický stav?**
- **Kinematický stav**
- Je určen stupněmi volnosti.
- **Dynamický stav**
- Je určen stupněmi volnosti kinematického stavu a dimenzí rychlosti změny kinematické dimenze.

- **Co je non-holonomic chování?**
- Počet ovladatelných prvků nemusí být stejný jako počet DOFs.
- Př. auto má tři skutečné DOFs (pohyb vpřed/vzad, otáčení, do strany), ale ovladatelné jsou pouze dvě DOFs
- **Co je vnímání robota a jaké problémy při něm řeší?**

- Proces, kdy robot mapuje měření senzorů na vnitřní reprezentaci prostředí.
- Protože senzory jsou zatížené šumem a prostředí je částečně pozorovatelné, nepředvídatelné a často dynamické, musíme aktuální stav odhadnout
- tj. robot řeší problémy **filtrace/odhadu stavu** $P(X_t | e_{1:t})$

kde $X$ jsou stavy světa, $Z$ jsou senzorická observations, $A$ jsou akce, které ten robot dělá.

- **Jaké typy vnímání známe?**

- Lokalizace, vnímání teploty, pachů, akustických signálů, ...

- **Co je to lokalizace a mapování?**
- Lokalizace je problém zjišťování polohy objektů včetně robota
- Pokud známe mapu prostoru, pak hledáme pozici na mapě (**mapování**)
- Mapa nemusí být k dispozici, pak je realizována současně lokalizace a mapování

- **Jak se vyhodnocuje vnímání?**
- Dynamické Bayesovské sítě
- Kalmanovy filtry
- strojové učení

- **Co jsou dynamické Bayesovské sítě?**
- Temporální pravděpodobnostní model
- Skládá se z vrstev proměnných, které se opakují (čas).
- Apriorní distribuce $P(X_0)$
- Přechodový model $P(X_1 | X_0)$
- Senzorický model $P(E_1 | X_1)$

- **Jak je možné aplikovat odhad stavu na chování robota? Popište odpovídající přechodový a senzorický model. V čem se tato úloha a výpočet liší od odhadu stavu, se kterým jsme doposud pracovali?**
- Odhadujeme pomocí filtrace
$\textbf{P}(X_{t+1} \mid e_{1:t+1}) = \alpha\color{blue}{\textbf{P}(e_{t+1} \mid X_{t+1})}\sum\limits_{x_{t}}\color{red}{\textbf{P}(X_{t+1} \mid x_{t})}\textbf{P}(x_{t} \mid e_{1:t})$
- Přechodový model $\color{red}{\textbf{P}(X_{t+1}\mid x_t, a_t)}$
- Senzorický model $\color{blue}{\textbf{P}(z_{t+1} \mid X_{t+1})}$, který popisuje na čem závisí nové pozorování $z_{t+1}$

- Zajímá nás tedy pravděpodobnost nového stavu $X_{t+1}$ na základě dosavadních pozorování pomocí senzorů $z_{1:t+1}$ a akcí $a_{1:t}$, tj. $\textbf{P}(X_{t+1}\mid z_{1:t+1}, a_{1:t})$

- Dříve uvedená filtrace je ovšem definována na diskrétních proměnných => musíme místo součtu použít integraci

$\textbf{P}(X_{t+1} \mid z_{1:t+1}, a_{1:t}) = \alpha\color{blue}{\textbf{P}(z_{t+1} \mid X_{t+1})}{\displaystyle \int}\color{red}{\textbf{P}(X_{t+1} \mid x_{t})}\textbf{P}(x_{t} \mid z_{1:t}) dx_t$

- **Uveďte příklad dynamické Bayesovské sítě pro práci s robotem vzhledem k jeho dané poloze, rychlosti a stavu baterie.**


- **Co je konfigurační a pracovní prostor? Jaký je mezi nimi rozdíl?**

- Používají se pro reprezentaci plánovacího problému (např. pohybu)
- **Konfigurační prostor**

- Prostor stavů robota definován:

- umístěním
- orientací
- úhly kloubů
- Např. reprezentace pomocí robotových kloubů
- $\varphi_s$ úhel ramena a $\varphi_e$ úhel kolena


- **Pracovní prostor**
- Popsán souřadnicemi efektorů.
- Tj. reprezentuje reálný prostor, kdy jsou sořadnice robota zadány stejným souřadným systémem jako objekty, kterými manipulujeme

- Vhodné pro kontrolu kolizí zejména robota a objektů zadaných jednoduchými polygonálními modely.


## Plánování pohybu robota

### Jak obecně vypadá postup plánování pohybu robota ve spojitém prostoru?
- Spojitá reprezentace konfiguračního prostoru ⇒ Diskretizace ⇒ Prohledávání grafu

### Jaké přístupy k plánování pohybu robota známe?

- **Kombinatorické přístupy**
- graf viditelnosti
- Voroného diagramy
- buňková dekompozice
- potenční funkce
- **Pravděpodobnostní přístupy** (založené na **vzorkování**)
- pravděpodobnostní cestovní mapa (probabilistic roadmap, PRM)
- rychlé prozkoumávající stromy (rapidly-exploring random tree, RRT)

**Příklady kombinatorických přístupů**

- **Graf viditelnosti**
1. Spojíme všechny páry vrcholů a iniciální a cílové konfigurace.
2. Eliminujeme hrany, které protínají překážky.
3. Graf viditelnosti vždy zahrnuje nejkratší cestu konfiguračním prostorem.

- Složitost konstrukce:
- naivní přístup $\mathcal{O}(n^3)$
- s pomocí rotačního stromu pro množinu segmentů $\mathcal{O}(n^2)$

- Problémy
- Cesta je moc blízko překážek.
- Komplikované ve vyšších dimenzích.

- **Voroného diagramy**

- Dělí prostor na oblasti podle zadaných objektů na "Voroného oblasti", každý bod z jednotlivé oblasti je nejblíže k objektu určující Voroného oblast
- tj. ohraničíme každý bod (překážku) tak, aby všechny body v ohraničené oblasti byly nejblíže právě té překážce
- Maximalizuje vzdálenost od překážek.
- Pohyb po hranicích.

- Problémy:
- Malé změny překážek mohou vést k velkým změnám diagramu.
- Komplikované ve vyšší dimenzi.
- **Buňková dekompozice**
- Dekompozice volného prostoru na konečný počet spojitých regionů - buněk.
- Typy:

- **Pravidelná mřížka**

- Proste rozdělení mapy na mřížku


- **Exaktní buňková dekompozice (vertikální / lichoběžníková)**

- Pomocí **plane sweep / sweep line algoritmu** z výpočetní geometrie

​ 
- **Přibližná buňková dekompozice**

- Např. oktalová (octree) dekompozice

- **Potenční funkce**
- Zavedeme si dodatečnou cenovou funkci, která narůstá se vzdálenosti od nejbližší překážky.


- **Příklady pravděpodobnostních přístupů**

- Nebudeme využívat explicitní reprezentaci překážek v konfiguračním prostoru, ale využijeme vzorkování.

- **Probabilistic RoadMap (PRM)**
- Generování jedné cestovní mapy, která je používána pro plánovací dotazy vícekrát.
1. **Učící fáze**
- Vzorkování
- Spojení náhodných konfigurací s použitím lokálního plánovače.
2. **Dotazovací fáze**
- Spojení počáteční a cílové konfigurace s PRM
- Použití prohledávání grafu k nalezení cesty.


- **Rapidly-exploring random tree**

- (Doporučuju toto [video](https://www.youtube.com/watch?v=QR3U1dgc5RE).)
- Algoritmus pro jeden dotaz.
- Inkrementální konstrukce grafu (stromu) směrem k cílové oblasti.
- Postup konstrukce:
1. Na začátku máme počáteční konfiguraci (kořen stromu).
2. Generuj (navzorkuj) náhodnou konfiguraci.
3. Nalezni nejbližší uzel stromu k vygenerované konfiguraci.
- Např. pomocí k-d trees
4. Přidej vygenerovanou konfiguraci do stromu.
- Kontrolujeme výběr tak, aby se blížil k cíli, takže pokud se na cestě do náhodné konfigurace nachází překážka, pak ji do stromu nepřidáváme.
- Pokud je cesta do náhodné konfigurace moc dlouhá, vezmeme pouze kratší kus té cesty (viz [video](https://youtu.be/QR3U1dgc5RE?t=696))
5. Skoč na krok 2, pokud nejsme v cíli.

**Jak vylepšit $A^*$ pro prohledávání grafu?**

- Rozšíříme o Jump Point Search algoritmus
- viz https://zerowidth.com/2013/a-visual-explanation-of-jump-point-search.html
- A* http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

<!--

**Jakými způsoby můžeme pohyb robota realizovat?**

- **Zkonstruováním referenční cesty pomocí referenčního regulátoru**
- Doteď jsme počítali pouze s pozicemi robota (navrhovali jsme cestu). Ve skutečnosti musíme umět namodelovat síly, kterými se bude robot řídit. Kvůli fyzikálním jevům jako je např. setrvačnost nemůžeme robotovi jednoduše přikázat, aby následoval libovolnou cestu s libovolnou rychlostí.
- Mohli bychom využít dynamický stav (viz začátek robotiky) k namodelování transition modelu pomocí diferenciálních rovnic. Dynamický model je ovšem pro tento účel velmi složitý. Využijeme proto kinematické plány, jejichž nedostatky budeme kompenzovat pomocí referenčního regulátoru.
- Příklady regulátorů:
- **P regulátor**
- řízení je proporční chybě manipulace robota tzn. robot vyvine opačnou sílu proti zaznamenané chybě
- $a_t = K_P(y(t) - x_t)$, kde
- $y(t)$ je referenční cesta
- $x_t$ je stav robota v čase $t$
- $K_P$ je parametr ovlivňující kompenzaci
- příliš naivní přístup, který způsobuje vibrace (nastavení menšího $K_P$ jen vibrace zpomalí, ale neodstraní, viz obrázek)

- **PD regulátor**
- Nedostatky P regulátoru můžeme stabilizovat pomocí derivačního členu (D), který je proporční první derivaci chyby v čase $t$. Pokud se chyba výrazně mění v čase (tedy vibruje), pak tento člen chybu stabilizuje. Viz obrázek.
- $a_t = K_P(y(t) - x_t) + K_D\dfrac{\partial(y(t) - x_t)}{\partial t}$
- **PID regulátor**
- Mnohdy potřebujeme reagovat i na systematické vnější síly, které nejsou součásti modelu (opotřebení paže, řízení). Opravuje dlouhotrvající odchylky mezi referenčním a aktuálním stavem. Tohoto docílíme přidáním třetího integračního člena (I)
- $a_t = K_P(y(t) - x_t) + K_I{\displaystyle\int(y(t) - x_t) dt} + K_D\dfrac{\partial(y(t) - x_t)}{\partial t}$

- **Pomocí potenčního pole**
- Podobně jako při plánování pohybu sestrojujeme potenční pole pomocí potenční funkce.
- Musíme definovat přitažlivou sílu, která robota nasměruje do cíle a zároveň potřebujeme definovat odpudivé síly pro překážky.
- Je vhodné spíše pro lokální než globální cesty (snadno uvízne v lokálním minimu)
- **Reaktivního řízení**
- Předešlé přístupy vyžadují model prostředí (referenční cestu nebo potenční pole). Problém nastává, že ne vždy umím/můžeme vygenerovat dostatečně kvalitní model prostředí (představ si robota s omezenými senzory nebo robota ve zvláštním prostředí např. na Marsu; generování kvalitního modelu může být navíc výpočetně náročné).
- Zkonstruujeme tak, že definujeme vzory pro akce (např. posun končetin) a definujeme konečný stavový automat (viz obrázek)

-->