Exercise session index

1. Search problem modeling: $\bold{P} = < \bold{S}, s_0, G>$, $\bold{S} = <S, A, Action, Result, Cost>$

2. Search strategies

   • Uninformed strategies:

     • DFS

     • BFS

     • Depth limited search

     • Iterative deepening search

     • UCS

     • Properties:

       • $T(n), S(n)$

       • Completeness, optimality

   • Informed strategies:

     • Greedy BFS

     • A*

     • Properties:

       • $h(n)$, admissibility, consistent

3. Adversarial search: $\bold{P} = <S, A, players, actions, result, terminal, utility>$

   • Problem modeling

   • MINIMAX

   • $\alpha/\beta$ pruning

4. Reinforcement learning: $\bold{P} = (S, A, P, R, [\gamma, \mu_0])$

   • Problem modeling

   • Discrete Bellman equation, Q-Tables:

     $Q^{*}(s, a) \leftarrow(1-\alpha) Q^{*}(s, a)+\alpha\left(r+\gamma \times \max _{a^{\prime} \in A} Q^{*}\left(s, a^{\prime}\right)\right)$

5. CSP: $\bold{P} = (X, B, C)$

   • Problem modeling

   • AC-3

   • Backtracking search

   • BTS + FC + MRV + LCV

6. Propositional Logic

   • PL

   • FOL

   • Derivation via resolution calculus

   • FOL to PL conversion

   • DPLL algorithm

7. Planning: $\bold{P} = (Cond, Section, Init, Goal)$

   • Problem modeling

   • STRIPS, PDDL

   • Forward search

   • Backward search