The wiki page is under active construction, expect bugs.

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:50] – [CSP - Problémy splnění omezení (Constraint Satisfaction Problems)] mistrjirkastatnice:bakalar:b4b36zui [2025/06/03 12:40] (current) – zapleka3
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 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á} - Splněná omezení: žádná (zatím nemáme hodnoty pro B, C)+**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)
  
-**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** - zrušíme 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**  
 +  * zrušíme B = červená
  
-**Krok 3:** Zkusíme B = zelená - Současné přiřazení: {A: červená, B: zelená} - Kontrola omezení A $\neq$ B: SPLNĚNO (červená $\neq$ zelená)+**Krok 3:**  
 +  * Zkusíme B = zelená  
 +  * Současné přiřazení: {A: červená, B: zelená}  
 +  * Kontrola omezení A $\neq$ B: SPLNĚNO (červená $\neq$ zelená)
  
-**Krok 4:** Zkusíme C = červená - Současné přiřazení: {A: červená, B: zelená, C: červená} - Kontrola omezení: - A $\neq$ B: SPLNĚNO (červená $\neq$ zelená) - B $\neq$ C: SPLNĚNO (zelená $\neq$ červená) - A $\neq$ C: NESPLNĚNO (červená = červená) - **Backtrack** - zrušíme C = červená+**Krok 4:**  
 +  * Zkusíme C = červená   
 +  * Současné přiřazení: {A: červená, B: zelená, C: červená}  
 +  * Kontrola omezení:  
 +    * A $\neq$ B: SPLNĚNO (červená $\neq$ zelená)  
 +    * B $\neq$ C: SPLNĚNO (zelená $\neq$ č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á} - Kontrola omezení B $\neq$ C: NESPLNĚNO (zelená = zelená) - **Backtrack** - zrušíme C = zelená+**Krok 5:**  
 +  * 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á
  
-**Krok 6:** Zkusíme C = modrá - Současné přiřazení: {A: červená, B: zelená, C: modrá} - Kontrola všech omezení: - A $\neq$ B: SPLNĚNO (červená $\neq$ zelená) - B $\neq$ C: SPLNĚNO (zelená $\neq$ modrá) - A $\neq$ C: SPLNĚNO (červená $\neq$ modrá) - **ŘEŠENÍ NALEZENO!**+**Krok 6:**  
 +  * Zkusíme C = modrá 
 +  * Současné přiřazení: {A: červená, B: zelená, C: modrá}  
 +  * Kontrola všech omezení:  
 +  * A $\neq$ B: SPLNĚNO (červená $\neq$ zelená) 
 +  * B $\neq$ C: SPLNĚNO (zelená $\neq$ modrá)  
 +  * A $\neq$ C: SPLNĚNO (červená $\neq$ modrá) - **ŘEŠENÍ NALEZENO!**
  
 == Nalezené řešení == == Nalezené řešení ==
- 
   * **A = červená**   * **A = červená**
   * **B = zelená**   * **B = zelená**
   * **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?}}
  
-=== Optimalizace ===+=== AC-3 algoritmus ===
  
-**Heuristiky pro výběr proměnných:** - **MRV (Minimum Remaining Values):** Vybírej proměnnou s nejmenším počtem zbývajících hodnot - **Degree heuristic:** Vybírej proměnnou zapojenou do nejvíce omezení+Algoritmus pro dosažení lokální konzistence (arc consistency):
  
-**Heuristiky pro výběr hodnot:** - **LCV (Least Constraining Value):** Vybírej hodnotu, která nejméně omezuje ostatní proměnné+  * 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.
  
-**Inference techniky:** - **Forward checking:** Po přiřazení hodnoty odstraň nekompatibilní hodnoty ze sousedních proměnných - **Arc consistency:** Zajisti, aby pro každou hodnotu v doméně existovala kompatibilní hodnota v sousedních proměnných+=== Heuristiky ===
  
-===== Další příklady CSP =====+  * **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 ===
  
   * **Sudoku:** Proměnné = políčka, domény = čísla 1-9, omezení = unikátnost v řádcích/sloupcích/čtvercích   * **Sudoku:** Proměnné = políčka, domény = čísla 1-9, omezení = unikátnost v řádcích/sloupcích/čtvercích
Line 751: 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. 
 + 
 +=== Charakteristika === 
 + 
 +  * 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}\}$\\ +**Ukázka – rozvrh**:  
-Domény: časové sloty $\{8:00, 9:00\}$\\ +  * Aktivity: $X = \{\text{matematika}, \text{angličtina}\}$\\ 
-Omezení: nelze mít matematiku a angličtinu zároveň → $\text{matematika} \neq \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 774: 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 790: 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 806: 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 816: 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 842: 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 881: 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 900: 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 908: 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 916: 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: • b4b33alg

Navigation

Playground

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