Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b36zui [2025/05/29 15:56] – [CSP - Problémy splnění omezení (Constraint Satisfaction Problems)] mistrjirkastatnice:bakalar:b4b36zui [2026/05/29 15:25] (current) – [Policy Improvement] knedl1k
Line 65: Line 65:
  
   * **Akce**: $A = \{a_1, \dots, a_k\}$   * **Akce**: $A = \{a_1, \dots, a_k\}$
-  * **Odměny**: pro každé $a_i$ náhodná proměnná $r_t^{(i)} \sim \nu_i$ s očekáváním $\mu_i$+  * **Odměny**: pro každé $a_i$ náhodná proměnná $r_t^{(i)} \sim \nu_i$ s očekáváním $Q(a) = \mu_i$ 
   * **Očekávaná hodnota akce**:     * **Očekávaná hodnota akce**:  
     $$     $$
Line 321: Line 321:
  
   * **Heuristiky**:   * **Heuristiky**:
-    - **Admisibilní** – nikdy nepřeceňuje skutečné náklady (tj. $h(n) \leq h^*(n)$), což zaručuje optimálnost. +    - **Admisibilní (přípustná)** – nikdy nepřeceňuje skutečné náklady (tj. $h(n) \leq h^*(n)$), což zaručuje optimálnost. 
-    - **Konzistentní (monotónní)** – platí $h(n) \leq c(n, n') + h(n')$, což zajišťuje, že se $f$ hodnoty uzlů nemohou zmenšovat při cestě stromem.+    - **Konzistentní (monotónní, consistent)** – platí $h(n) \leq c(n, n') + h(n')$, což zajišťuje, že se $f$ hodnoty uzlů nemohou zmenšovat při cestě stromem.
     - **Inadmisibilní** – rychlejší, ale nemusí najít optimální řešení.     - **Inadmisibilní** – rychlejší, ale nemusí najít optimální řešení.
  
Line 351: Line 351:
   * Příliš silná heuristika (např. $h(n) > h^*(n)$) může zrychlit výpočet, ale ztrácí optimálnost.   * Příliš silná heuristika (např. $h(n) > h^*(n)$) může zrychlit výpočet, ale ztrácí optimálnost.
  
-====== 4. Algoritmy posilovaného učení ======+===== 4. Algoritmy posilovaného učení =====
  
 **policy evaluation, policy improvement, policy iteration, value iteration, Q-learning** **policy evaluation, policy improvement, policy iteration, value iteration, Q-learning**
Line 401: Line 401:
  
 $$ $$
-\pi'(s) = \arg\max_{a}\sum_{s'} P(s'|s,a),\bigl[R(s,a,s') + \gamma V^\pi(s')\bigr].+\pi'(s) = \arg\max_{a}\sum_{s'} P(s'|s,a)\bigl[R(s,a,s') + \gamma V^\pi(s')\bigr].
 $$ $$
  
Line 458: Line 458:
  
 $$ $$
-V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a),\bigl[R(s,a,s') + \gamma V_k(s')\bigr].+V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V_k(s')\right].
 $$ $$
  
Line 464: Line 464:
  
 $$ $$
-\pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a),\bigl[R(s,a,s') + \gamma V(s')\bigr].+\pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a)\bigl[R(s,a,s') + \gamma V(s')\bigr].
 $$ $$
  
Line 635: Line 635:
     * Hry s nulovým součtem, kde jsou hodnoty pro oba hráče přesně opačné.     * Hry s nulovým součtem, kde jsou hodnoty pro oba hráče přesně opačné.
  
-==== Negascout (Principal Variation Search, PVS) ====+==== NegaScout (Principal Variation Search, PVS) ====
  
 Další vylepšení algoritmu Alpha-Beta (resp. Negamax), které využívá předpoklad, že akce jsou předem dobře seřazené (např. pomocí heuristiky). Tím výrazně urychluje prohledávání. Další vylepšení algoritmu Alpha-Beta (resp. Negamax), které využívá předpoklad, že akce jsou předem dobře seřazené (např. pomocí heuristiky). Tím výrazně urychluje prohledávání.
Line 681: Line 681:
 === Definice === === Definice ===
  
-CSP jsou definovány jako trojice **(X, D, C)**, kde:  +CSP (constraint satisfaction problems) jsou úlohy, ve kterých hledáme přiřazení hodnot proměnným tak, aby byla splněna všechna zadaná omezení. 
-  * **X** je množina proměnných  + 
-  * **D** je množina domén (každá proměnná má svou doménu možných hodnot)  +Formálně je CSP definováno jako trojice **(X, D, C)**, kde: 
-  * **C** je množina omezení, která specifikují povolené kombinace hodnot pro podmnožiny proměnných+  * **X** je množina proměnných: {X₁, X₂, ..., Xₙ} 
 +  * **D** je množina domén: každá proměnná Xᵢ má svou doménu Dᵢ možných hodnot 
 +  * **C** je množina omezení: každé omezení specifikuje povolené kombinace hodnot pro podmnožinu proměnných
  
 **Cíl:** Nalézt přiřazení hodnot proměnným tak, aby byla všechna omezení splněna. **Cíl:** Nalézt přiřazení hodnot proměnným tak, aby byla všechna omezení splněna.
Line 706: Line 708:
 **Proměnné:** X = {A, B, C} **Proměnné:** X = {A, B, C}
  
-**Domény:** - $D_A$ = {červená, zelená, modrá} - $D_B$ = {červená, zelená, modrá}\\ +**Domény:**  
-- $D_C$ = {červená, zelená, modrá}+  * $D_A$ = {červená, zelená, modrá}  
 +  * $D_B$ = {červená, zelená, modrá}\\ 
 +  * $D_C$ = {červená, zelená, modrá}
  
-**Omezení:** C = {A $\neq$ B, B $\neq$ C, A $\neq$ C} - A a B musí mít různé barvy (jsou sousední) - B a C musí mít různé barvy (jsou sousední) - A a C musí mít různé barvy (jsou sousední)+**Omezení:**  
 +  * C = {A $\neq$ B, B $\neq$ C, A $\neq$ C}  
 +  * A a B musí mít různé barvy (jsou sousední)  
 +  * B a C musí mít různé barvy (jsou sousední)  
 +  * A a C musí mít různé barvy (jsou sousední)
  
 === Řešení pomocí backtrackingu === === Řešení pomocí backtrackingu ===
  
-**Krok 1:** Přiřadíme A = červená - Současné přiřazení: {A: červená} +**Krok 1:**  
 +  * Přiřadíme A = červená  
 +  * Současné přiřazení: {A: červená} 
   * Splněná omezení: žádná (zatím nemáme hodnoty pro B, C)   * Splněná omezení: žádná (zatím nemáme hodnoty pro B, C)
  
-**Krok 2:** Zkusíme B = červená - Současné přiřazení: {A: červená, B: červená} +**Krok 2:**  
 +  * Zkusíme B = červená  
 +  * Současné přiřazení: {A: červená, B: červená} 
   * Kontrola omezení A $\neq$ B: NESPLNĚNO (červená = červená) **Backtrack**    * Kontrola omezení A $\neq$ B: NESPLNĚNO (červená = červená) **Backtrack** 
   * zrušíme B = červená   * zrušíme B = červená
  
-**Krok 3:** Zkusíme B = zelená +**Krok 3:**  
 +  * Zkusíme B = zelená 
   * Současné přiřazení: {A: červená, B: zelená}    * Současné přiřazení: {A: červená, B: zelená} 
   * Kontrola omezení A $\neq$ B: SPLNĚNO (červená $\neq$ zelená)   * Kontrola omezení A $\neq$ B: SPLNĚNO (červená $\neq$ zelená)
  
-**Krok 4:** Zkusíme C = červená  +**Krok 4:**  
 +  * Zkusíme C = červená  
   * Současné přiřazení: {A: červená, B: zelená, C: červená}    * Současné přiřazení: {A: červená, B: zelená, C: červená} 
-  * Kontrola omezení: - A $\neq$ B: SPLNĚNO (červená $\neq$ zelená)  +  * Kontrola omezení:  
-  * B $\neq$ C: SPLNĚNO (zelená $\neq$ červená)  +    * A $\neq$ B: SPLNĚNO (červená $\neq$ zelená)  
-  * A $\neq$ C: NESPLNĚNO (červená = červená) **Backtrack**  +    * B $\neq$ C: SPLNĚNO (zelená $\neq$ červená)  
-  * zrušíme C = červená+    * A $\neq$ C: NESPLNĚNO (červená = červená) **Backtrack**  
 +    * zrušíme C = červená
  
-**Krok 5:** Zkusíme C = zelená - Současné přiřazení: {A: červená, B: zelená, C: zelená}  +**Krok 5:**  
-  * Kontrola omezení B $\neq$ C: NESPLNĚNO (zelená = zelená) - **Backtrack**+  * Zkusíme C = zelená  
 +  * Současné přiřazení: {A: červená, B: zelená, C: zelená}  
 +  * Kontrola omezení B $\neq$ C: NESPLNĚNO (zelená = zelená **Backtrack**
   * zrušíme C = zelená   * zrušíme C = zelená
  
-**Krok 6:** Zkusíme C = modrá - Současné přiřazení: {A: červená, B: zelená, C: modrá} +**Krok 6:**  
 +  * Zkusíme C = modrá 
 +  * Současné přiřazení: {A: červená, B: zelená, C: modrá} 
   * Kontrola všech omezení:    * Kontrola všech omezení: 
   * A $\neq$ B: SPLNĚNO (červená $\neq$ zelená)   * A $\neq$ B: SPLNĚNO (červená $\neq$ zelená)
Line 746: Line 765:
   * **C = modrá**   * **C = modrá**
  
-== Další možná řešení ==+== Inference techniky ==  
 +  * **Forward checking:** Po každém přiřazení odstraní ze sousedních proměnných hodnoty, které by porušovaly omezení. 
 +  * **Arc consistency (AC):** Pro každou dvojici proměnných (X, Y) zajišťuje, že pro každou hodnotu X existuje nějaká hodnota Y, která neporušuje omezení.
  
-Tento problém má více řešení. Některá další: - A = červená, B = modrá, C = zelená - A = zelená, B = červená, C = modrá - A = zelená, B = modrá, C = červená - A = modrá, B = červená, C = zelená - A = modrá, B = zelená, C = červená+AC-3 algoritmus využívá arc consistency, asi nejlepší vysvětlení je zde: 
 +{{youtube>4cCS8rrYT14?}} 
 + 
 +=== AC-3 algoritmus === 
 + 
 +Algoritmus pro dosažení lokální konzistence (arc consistency): 
 + 
 +  * Inicializuj frontu všech hran (omezení mezi proměnnými). 
 +  * Iterativně kontroluj každou hranu (X, Y): 
 +    * Pokud odstraníš nějakou hodnotu z domény X, znovu přidej všechny hrany směřující do X. 
 +  * Pokud některá doména zůstane prázdná → CSP nemá řešení. 
 +  * Nezaručuje nalezení řešení, jen redukuje prostor. 
 + 
 +=== Heuristiky === 
 + 
 +  * **Minimum Remaining Values (MRV):** Vyber proměnnou s nejmenším počtem možných hodnot – nejdřív se řeší „nejtěžší“ proměnné. 
 +  * **Least Constraining Value:** Vyber hodnotu, která ponechává nejvíce možností ostatním proměnným. 
 +  * **Backjumping, Dynamic Backtracking:** Chytřejší návraty při backtrackingu – vrací se více „na jistotu“.
  
 === Další příklady CSP === === Další příklady CSP ===
Line 758: Line 796:
 ==== Scheduling ==== ==== Scheduling ====
  
-Plánování je specifický typ CSP, kde je cílem přiřadit činnosti časovým slotům s ohledem na omezení jako kapacity zdrojů a precedenční vztahy.+Plánování (scheduling) je speciální případ CSP, kde proměnné reprezentují **aktivity** a domény představují **časové sloty** nebo **zdroje**, které lze k těmto aktivitám přiřadit.
  
-**Ukázka – rozvrh**: Aktivity: $X = \{\text{matematika}, \text{angličtina}\}$\\ +=== Charakteristika === 
-Domény: časové sloty $\{8:00, 9:00\}$\\ + 
-Omezení: nelze mít matematiku a angličtinu zároveň → $\text{matematika} \neq \text{angličtina}$+  * Proměnné: jednotlivé aktivity nebo úlohy 
 +  * Domény: možné časy nebo dostupné zdroje 
 +  * Omezení:  
 +    * **tvrdá omezení** (např. kapacita učeben, nepřekrývání aktivit, precedenční vztahy) 
 +    * **měkká omezení** (např. preferované časy, minimalizace přechodů nebo náročnosti) 
 + 
 +**Ukázka – rozvrh**:  
 +  * Aktivity: $X = \{\text{matematika}, \text{angličtina}\}$\\ 
 +  * Domény: časové sloty $\{8:00, 9:00\}$\\ 
 +  * Omezení: nelze mít matematiku a angličtinu zároveň → $\text{matematika} \neq \text{angličtina}$
  
 ==== Situation Calculus ==== ==== Situation Calculus ====
  
-Situation calculus je formální jazyk pro popis dynamických systémů. Používá se k popisu efektů akcí a plánování.+Situation Calculus je formální jazyk založený na predikátové logice, určený pro reprezentaci **měnících se světů**, zejména v kontextu **akcí a jejich efektů**. Často se používá pro plánování v AI.
  
-**Základní notace**: - $do(a, s)$: výsledek vykonání akce $a$ ve stavu $s$, - $Holds(p, s)$: predikát $p$ platí ve stavu $s$, - $Poss(a, s)$: akce $a$ je možná ve stavu $s$+=== Základní prvky === 
 + 
 +  * **Situace** – abstraktní reprezentace historie provedených akcí (počáteční situace = S0) 
 +  * **Akce** – operace, které mění stav světa (např. Move, PickUp) 
 +  * **Fluentní predikáty** – závisí na situaci, reprezentují stav světa (např. `At(Robot, Room)`) 
 +  * **Rigidní predikáty** – nezávisí na situaci (např. `Room(Room1)`) 
 +  * **Výsledková funkce:** `do(a, s)` – situace, která vznikne provedením akce `a` ve stavu `s` 
 + 
 +=== Standardní predikáty === 
 + 
 +  * `Holds(f, s)` – fluent `f` platí ve stavu `s` 
 +  * `Poss(a, s)` – akce `a` je možná ve stavu `s` 
 +  * `do(a, s)` – výsledek vykonání akce `a` ve stavu `s`
  
 **Ukázka**: **Ukázka**:
Line 781: Line 840:
 ==== STRIPS ==== ==== STRIPS ====
  
-STRIPS (Stanford Research Institute Problem Solver) je formalismus pro reprezentaci plánovacích problémů. Každá akce má:+**STRIPS (Stanford Research Institute Problem Solver)** je formalismus pro reprezentaci plánovacích problémů ve formální logice. Byl původně vyvinut pro robota Shakey. 
 + 
 +=== Formální definice === 
 + 
 +STRIPS problém je definován čtveřicí **(P, A, I, G)**, kde: 
 +  * **P** je množina všech atomických predikátů (např. `At(Robot, Room1)`) – booleovské proměnné 
 +  * **A** je množina všech akcí, každá ve tvaru `a = ⟨pre(a), add(a), del(a)⟩`: 
 +    * `pre(a)` – předpoklady, které musí být splněny pro použití akce 
 +    * `add(a)` – predikáty, které po akci začnou platit 
 +    * `del(a)` – predikáty, které po akci přestanou platit 
 +  * **I** je počáteční stav – množina predikátů platných na začátku 
 +  * **G** je cílový stav – množina predikátů, které chceme dosáhnout 
 + 
 +Každá akce má:
  
   * **Preconditions**: podmínky pro použití akce   * **Preconditions**: podmínky pro použití akce
Line 797: Line 869:
 </code> </code>
  
-Cílem je najít posloupnost akcí, která převede výchozí stav na cílový (např. Robot je v místnosti C).+=== Cíl plánování === 
 + 
 +Cílem je najít posloupnost akcí `a₁, a₂, ..., aₖ`, která při aplikaci na počáteční stav `I` postupně převede systém do stavu, kde `G ⊆ sₖ`. 
 + 
 +=== Řešení pomocí A* === 
 + 
 +STRIPS problémy lze řešit algoritmem **A***, kde: 
 +  * **stav** je aktuální množina pravdivých predikátů 
 +  *  **heuristika** může být například `h(s) = |G \ s|` – počet cílů, které ještě nejsou splněny 
 + 
 +=== Heuristiky a relaxace === 
 + 
 +  * **Relaxace problému**: ignorujeme `del(a)`, tedy předpokládáme, že akce nic neodstraňují 
 +    * Relaxovaná akce: `a⁺ = ⟨pre(a), add(a), ∅⟩` 
 +  * **Abstrakce**: např. odstranění některých predikátů nebo predikátové argumenty zjednodušíme 
 + 
 +=== Plánovací graf (relaxovaný plánovací graf) === 
 + 
 +Graf dosažitelnosti: 
 +  * Střídají se úrovně predikátů `Pᵢ` a akcí `Aᵢ` 
 +  * `Aᵢ = {a ∈ A | pre(a) ⊆ Pᵢ}` 
 +  * `Pᵢ₊₁ = Pᵢ ∪ {p ∈ add(a) | a ∈ Aᵢ}` 
 +  * Konstrukce končí, pokud `G ⊆ Pᵢ` 
 + 
 +Stejný graf se dá použít k výpočtu optimální heuristiky hmax  
 +  * Vrchol, který náleží počátečnímu stavu se inicializuje na nulu  
 +  * Všechny vrcholy s akcemi jsou pak rovny maximu hodnot z předpokladů dané akce  
 +  * Do vrcholů se stavy (propozicemi) se pak zapíše nejlevnější akce, která do daného stavu vedla 
 + 
 +{{:statnice:bakalar:pasted:20250603-113233.png?400}}
  
 ===== 7. Neurčitost v AI ===== ===== 7. Neurčitost v AI =====
Line 813: Line 914:
 $$ $$
  
-kde: - $H$ je hypotéza, - $D$ jsou data, - $P(H|D)$ je posteriorní pravděpodobnost, - $P(D|H)$ je pravděpodobnost dat za předpokladu platnosti hypotézy (likelihood), - $P(H)$ je apriorní pravděpodobnost hypotézy, - $P(D)$ je marginální pravděpodobnost dat.+kde: 
 +  * $H$ – hypotéza, 
 +  * $D$ – pozorovaná data, 
 +  * $P(H|D)$ – posteriorní pravděpodobnost, 
 +  * $P(D|H)$ – pravděpodobnost dat za předpokladu hypotézy (likelihood), 
 +  * $P(H)$ – apriorní pravděpodobnost hypotézy, 
 +  * $P(D)$ – celková pravděpodobnost dat (normalizační konstanta).
  
 ==== Maximalizace očekávané utility ==== ==== Maximalizace očekávané utility ====
  
-Cílem rozhodování pod neurčitostí je zvolit akci, která maximalizuje očekávanou užitečnost:+Racionální agent by měl volit takovou akci, která maximalizuje **očekávanou užitečnost**:
  
 $$ $$
Line 823: Line 930:
 $$ $$
  
-kde: - $a$ je akce, - $s$ je možný stav světa, - $P(s|a)$ je pravděpodobnost stavu $s$ za předpokladu akce $a$, - $U(s,a)$ je užitečnost akce $a$ ve stavu $s$.+kde: 
 +  * $a$ – akce, 
 +  * $s$ – možný stav světa, 
 +  * $P(s|a)$ – pravděpodobnost stavu $s$ po provedení akce $a$, 
 +  * $U(s,a)$ – užitečnost výsledného stavu $s$ při akci $a$. 
 + 
 +Používá se v rozhodovacích sítích a obecně ve všech situacích, kde je třeba rozhodovat pod neurčitostí.
  
 ==== Bayesovské sítě ==== ==== Bayesovské sítě ====
  
-Bayesovské sítě (též grafické modely) jsou orientované acyklické grafy, ve kterých: - vrcholy reprezentují náhodné proměnné, - hrany reprezentují podmíněné závislosti mezi proměnnými, - každá proměnná má přidruženou podmíněnou pravděpodobnostní tabulku (CPT).+Bayesovské sítě jsou **orientované acyklické grafy (DAG)**, kde: 
 +  * uzly reprezentují náhodné proměnné, 
 +  * hrany vyjadřují podmíněnou závislost (rodič ovlivňuje potomka), 
 +  * každá proměnná má tabulku podmíněných pravděpodobností (CPT).
  
-Sítě umožňují efektivní reprezentaci a výpočet složitých pravděpodobnostních modelů a jsou základem pro inferenci (zjištění pravděpodobností nepozorovaných proměnných) a rozhodování.+Bayesovské sítě umožňují efektivní inferenci, tj. výpočet pravděpodobností nepozorovaných proměnných. 
 + 
 +**Celková distribuční pravděpodobnost** v síti se rozpadá podle struktury grafu: 
 + 
 +$$ 
 +P(X_1, ..., X_n) = \prod_{i=1}^{n} P(X_i \mid \text{rodiče}(X_i)) 
 +$$
  
 === Příklad Bayesovské sítě === === Příklad Bayesovské sítě ===
Line 849: Line 971:
 \end{document} \end{document}
 </tikzjax> </tikzjax>
 +
 Tato Bayesovská síť ilustruje následující závislosti mezi náhodnými proměnnými: Tato Bayesovská síť ilustruje následující závislosti mezi náhodnými proměnnými:
  
Line 888: Line 1011:
 $$ $$
  
-Použití: - textová klasifikace (spam, sentiment), - diagnostika v medicíně, - doporučovací systémy. +**Použití:** 
- +  * detekce spamu, 
 +  * analýza sentimentu, 
 +  * lékařská diagnostika.
  
 ==== Skrytý Markovův model (Hidden Markov Model, HMM) ==== ==== Skrytý Markovův model (Hidden Markov Model, HMM) ====
Line 907: Line 1031:
 $$ $$
  
-Použití: - rozpoznávání řeči, - analýza časových řad, - strojový překlad, - sledování objektů.+**Algoritmy:** 
 +  * **Forward-backward** – výpočet marginálních pravděpodobností, 
 +  * **Viterbi** – nalezení nejpravděpodobnější sekvence skrytých stavů, 
 +  * **Baum-Welch** – EM algoritmus pro trénink HMM.
  
-Hlavní algoritmy: - **Forward-backward** (výpočet pravděpodobností), - **Viterbiho algoritmus** (nejpravděpodobnější posloupnost), - **Baum-Welch** (EM algoritmus pro trénink).+**Použití:** 
 +  * rozpoznávání řeči, 
 +  * strojový překlad, 
 +  * analýza časových řad, 
 +  * sledování objektů.
  
 ===== 8. Řešení POMDP ===== ===== 8. Řešení POMDP =====
Line 915: Line 1046:
 **PBVI, HSVI** **PBVI, HSVI**
  
-Řešení problémů částečně pozorovatelných Markovových rozhodovacích procesů (POMDP) spočívá v nalezení optimální politiky, která maximalizuje očekávaný výnos na základě neúplné informace o stavu systému. V POMDP je totiž skutečný stav systému skrytý (latentní) a rozhodnutí je činěno na základě tzv. věrohodnostního rozdělení (belief state) – pravděpodobnostního rozdělení přes možné stavy daného systému.+==== Řešení POMDP ====
  
-POMDP je formálně definován jako sedmice $⟨S, A, T, R, Ω, O, \gamma⟩$, kde: - $S$ je množina stavů, - $A$ je množina akcí, - $T(s'|s,a)$ je přechodová pravděpodobnost, - $R(s,a)$ je funkce odměny, - $Ω$ je množina možných pozorování, - $O(o|s',a)$ je pravděpodobnost pozorování $o$ po provedení akce $a$ a přechodu do stavu $s'$, - $\gamma$ je diskontní faktor.+**Řešení částečně pozorovatelných Markovových rozhodovacích procesů (POMDP)** spočívá v nalezení optimální politiky na základě neúplné informace o stavu systému. V POMDP není stav přímo pozorovatelný – rozhodování se děje na základě tzv. **belief state** – pravděpodobnostního rozdělení přes možné stavy. 
 + 
 +=== Formální definice === 
 + 
 +POMDP je definován jako sedmice **⟨S, A, T, R, Ω, O, γ⟩**, kde: 
 +  * **S** – množina stavů 
 +  * **A** – množina akcí 
 +  * **T(s'|s,a)** – přechodová pravděpodobnost 
 +  * **R(s,a)** – odměnová funkce 
 +  * **Ω** – množina pozorování 
 +  * **O(o|s',a)** – pravděpodobnost pozorování $o$ po akci $a$ a přechodu do stavu $s'$ 
 +  * **γ** – diskontní faktor 
 + 
 +Hodnotová funkce je definovaná nad belief space a je konvexní. Přesné řešení je výpočetně náročné, proto používáme aproximační algoritmy. 
 + 
 +Řešení problémů částečně pozorovatelných Markovových rozhodovacích procesů (POMDP) spočívá v nalezení optimální politiky, která maximalizuje očekávaný výnos na základě neúplné informace o stavu systému. V POMDP je totiž skutečný stav systému skrytý (latentní) a rozhodnutí je činěno na základě tzv. věrohodnostního rozdělení (belief state) – pravděpodobnostního rozdělení přes možné stavy daného systému.
  
 Hodnotová funkce pro POMDP je definována nad věrohodnostními stavy a je konvexní. Přesné řešení POMDP je výpočetně neproveditelné pro větší problémy, proto se používají aproximační metody. Mezi ně patří: Hodnotová funkce pro POMDP je definována nad věrohodnostními stavy a je konvexní. Přesné řešení POMDP je výpočetně neproveditelné pro větší problémy, proto se používají aproximační metody. Mezi ně patří:
Line 923: Line 1069:
 ==== Point-Based Value Iteration (PBVI) ==== ==== Point-Based Value Iteration (PBVI) ====
  
-PBVI aproximuje hodnotovou funkci výběrem reprezentativní množiny víry (belief points) $B = \{b_1, b_2, ..., b_n\}$, a iterativně aktualizuje hodnotovou funkci pouze v těchto bodech.+PBVI aproximuje hodnotovou funkci pouze v konečné množině **belief pointů** $B = \{b_1, b_2, ..., b_n\}$. Pro tyto body iterativně provádí Bellmanovy aktualizace:
  
-Algoritmus PBVI: 1. Inicializuj hodnotovou funkci $V_0$ jako nulovou. 2. Pro každou víru $b \in B$ prováděj: - $V_{i+1}(b) = \max_{a \in A} \left[ R(b, a) + \gamma \sum_{o \in Ω} P(o|b,a) V_i(b_{a,o}) \right]$, kde $b_{a,o}$ je aktualizovaná víra po akci $a$ a pozorování $o$.+1. Inicializace hodnotové funkce $V_0$. 
 +2. Iterace pro každý $b \in B$: 
 +$$ 
 +V_{i+1}(b) = \max_{a \in A} \left[ R(b, a) + \gamma \sum_{o \in Ω} P(o|b,a) \cdot V_i(b_{a,o}) \right]  
 +$$ 
 + 
 +  * $b_{a,o}$ je nová víra (belief) po akci $a$ a pozorování $o$ 
 +  * Hodnotová funkce se reprezentuje pomocí **α-vektorů**, které aproximují výnos pro jednotlivé akce a stavy
  
 Tímto způsobem PBVI konstruuje aproximaci optimality pomocí hodnotové funkce složené z tzv. $\alpha$-vektorů. Tímto způsobem PBVI konstruuje aproximaci optimality pomocí hodnotové funkce složené z tzv. $\alpha$-vektorů.
 +
 +PBVI výrazně zjednodušuje výpočet tím, že nepočítá hodnotu v celém belief prostoru.
  
 ==== Heuristic Search Value Iteration (HSVI) ==== ==== Heuristic Search Value Iteration (HSVI) ====
  
-HSVI je vylepšením PBVI, které využívá heuristické řízení výpočtu pro zlepšení efektivity. HSVI zachovává horní a dolní meze hodnotové funkce a iterativně je zpřesňuje pouze v místech, která ovlivňují politiku.+HSVI kombinuje heuristické řízení a aproximaci hodnotové funkce pomocí horní a dolní meze: 
 + 
 +1. **Inicializace:** 
 +   * Dolní mez $V^-$: jednoduché politiky (např. fixní akce) 
 +   * Horní mez $V^+$: řešení odpovídající plně pozorovatelnému MDP 
 + 
 +2. **Heuristické prohledávání:** 
 +   * Vybíráme beliefy, kde je největší rozdíl mezi $V^+$ a $V^-$ 
 +   * Průchod stromem víry (belief tree) řízený rozdílem mezi odhady 
 + 
 +3. **Update:** 
 +   * Dolní mez – přidání nových α-vektorů 
 +   * Horní mez – konvexní obálka a přepočet odhadu
  
 Algoritmus HSVI: 1. Udržuje dolní odhad $V^-$ a horní odhad $V^+$ hodnotové funkce. 2. Používá hloubkové prohledávání stromu víry řízené heuristikou k výběru větví, kde je největší rozdíl mezi $V^+$ a $V^-$. 3. Provádí zálohování hodnot a zpřesňuje odhady na cestě k listům stromu. Algoritmus HSVI: 1. Udržuje dolní odhad $V^-$ a horní odhad $V^+$ hodnotové funkce. 2. Používá hloubkové prohledávání stromu víry řízené heuristikou k výběru větví, kde je největší rozdíl mezi $V^+$ a $V^-$. 3. Provádí zálohování hodnot a zpřesňuje odhady na cestě k listům stromu.
 +
 +HSVI garantuje ε-optimalitu: algoritmus konverguje, když rozdíl mezi $V^+$ a $V^-$ je menší než dané ε.
 +
 +HSVI zachovává horní a dolní meze hodnotové funkce a iterativně je zpřesňuje pouze v místech, která ovlivňují politiku.
  
 HSVI kombinuje výpočetní efektivitu s garancemi na kvalitu aproximace: algoritmus konverguje k ε-optimální politice, pokud se rozdíl mezi horním a dolním odhadem zmenší pod ε. HSVI kombinuje výpočetní efektivitu s garancemi na kvalitu aproximace: algoritmus konverguje k ε-optimální politice, pokud se rozdíl mezi horním a dolním odhadem zmenší pod ε.

Trace: • b4b35psr • b0b01ma2 • b0b01ma2 • playground • b0b01lgr • b0b36dbs • b4b33rpz • b0b39pgr • b4b36zui

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b36zui (generated for current page)