Spațiul Stărilor Problemei

• Voi genera notițe de studiu detaliate din textul furnizat.

Spațiul Stărilor Problemei

• O metodă de a rezolva o problemă pleacă de la o configurație inițială pentru a obține o soluție cu anumite proprietăți
• Exemple de astfel de probleme includ labirinturi, satisfacerea restricțiilor, jocuri și construirea unui plan.
• Reprezentarea implică un graf al stărilor posibile în procesul de rezolvare, unde starea se schimbă prin acțiuni/mutări.
• O soluție este o cale din starea inițială la cea finală.
• Spațiul stărilor este un graf care poate fi reprezentat explicit sau implicit.
• Rezolvarea problemei înseamnă o căutare în acest graf.

Mediul Problemei

• Mediul problemei poate fi observabil sau parțial observabil, discret sau continuu, finit sau infinit, determinist sau nedeterminist, static sau dinamic.
• Observabilitatea se referă la perceperea completă a mediului.
• Caracterul discret/continuu se referă la distincția clară între stări.
• Finitudinea/infinitudinea se referă la natura grafului de stări.
• Determinismul/nedeterminismul se referă la consecvența acțiunilor, iar statismul/dinamismul se referă la influența agenților asupra stării mediului.

Căutare

• Soluția este starea finală sau drumul de la starea inițială la starea finală.
• Se poate cunoaște sau nu starea inițială.
• Se poate cunoaște sau nu starea finală dar doar proprietățile ei.
• Poate interesa drumul către starea finală sau doar starea finală în sine.

Caracteristici ale Strategiilor de Căutare

• Completitudinea garantează găsirea unei soluții în timp finit, dacă există una.
• Optimalitatea asigură găsirea celei mai bune soluții într-un timp finit.
• Complexitatea se referă la dependența de timp și spațiu față de dimensiunea intrărilor.
• Capacitatea de revenire permite revizitarea stărilor anterioare.
• Informarea utilizează metode pentru a prioritiza explorarea stărilor.
• Se pot avea informații despre calitatea stărilor.

Algoritmi de Căutare

• Pentru grafuri explicit reprezentate, se pot folosi Dijkstra și Bellman-Ford.
• Pentru grafuri implicit reprezentate, se folosesc căutarea pe lățime/adâncime (BFS/DFS), Iterative Deepening, Backtracking și Bidirectional search.
• Frontiera/OPEN: structura pentru nodurile/stările ce urmează a fi vizitate.
• Domeniu/CLOSED: structura pentru nodurile/stările vizitate deja, cărora le-am calculat vecinii.
• La alegerea unui nod de explorat, sunt calculați vecinii/succesorii săi, accesibili prin acțiuni din starea respectivă.
• Adâncimea unei stări s (Ad(s)) este lungimea celui mai scurt drum de la starea inițială si până în starea s.
• Vectorul de părinți p ∈ S × (S ∪ {⊥}) indică părintele unei stări s ca fiind p[s], cu p[s0] = ⊥.
• Soluția este reprezentată ca o cale de la starea inițială (s0) la starea finală (sf).
• Funcția cale(s, p) obține calea de la s0 la s.

Algoritmi de Căutare: BFS/DFS

• BFS/DFS: Algoritmi de căutare în graf.
• OPEN: Mulțimea nodurilor de vizitat.
• CLOSED: Mulțimea nodurilor vizitate.
• Intrare: Starea inițială (si), AdMax (pentru DFS).
• Ieșire: Soluția sau INSUCCES.
• Algoritmul extrage primul nod din OPEN.
• Dacă nodul este deja în CLOSED, se trece la următorul nod.
• Se calculează succesorii nodului curent.
• Pentru fiecare succesor, se setează părintele și se verifică dacă este starea finală.
• Dacă se folosește BFS, succesorii sunt inserați în OPEN la sfârșit.
• Dacă se folosește DFS, succesorii sunt inserați în OPEN la început.

Algoritmul Iterative Deepening DFS

• Algoritmul efectuează căutări DFS iterative cu adâncime limitată.
• Intrare: Starea inițială (s¡).
• Ieșire: Soluția sau INSUCCES.
• Se incrementează limita de adâncime (AdMax) de la 0 la infinit.
• Se apelează DFS cu limita de adâncime curentă.
• Când funcția DFS returnează o valoare diferită de INSUCCES, acea valoare este întoarsă.

Complexitatea Algoritmilor

• B este factorul de ramificare al spațiului de căutare.
• d este adâncimea soluției optime.
• m este lungimea maximă a unei căi în spațiul de căutare.
• Un algoritm este complet dacă găsește întotdeauna soluția, dacă aceasta există.
• Optimitatea se referă la lungimea căii până la soluție.

Căutare Informata

• Informarea utilizează o funcție w(s, cale) pentru calitatea unei stări s și a drumului din s0 până în s.
• Scopul e găsirea unei stări cât mai aproape de soluție.
• Căutarea de tip best-first alege din frontieră starea s cu w(s) minim.

Algoritmul Best-First

• Intrare: Starea inițială si și funcția w(s, cale).
• Ieșire: Soluția sau INSUCCES.
• Algoritmul menține o listă deschisă (OPEN) și una închisă (CLOSED) cu stările vizitate.
• Se extrage starea s din OPEN cu cea mai mică valoare w(s, cale(s, p)).
• Dacă s este starea finală, se returnează soluția.
• Se calculează succesorii stării s.
• Dacă un succesor sj este în CLOSED sau OPEN și are o valoare w mai mică, se actualizează părintele, starea sj fiind adăugată în OPEN.
• În caz contrar, starea sj este adăugată în OPEN cu părintele s.

Căutarea Best-First, Cazuri Particulare

• Best-first cu w(s) = Ad(s) este BFS.
• Best-first cu w(s) = -Ad(s) este DFS.
• Best-first cu w(sj) = suma costurilor arcelor este Dijkstra.
• Best-first cu w(s) = f(s) este A*.

Algoritmul A*

• În algoritmul A*, starea de explorat este aleasă pe baza funcției f(s) = g(s) + h(s), unde:

  • f(s) este costul total estimat al celui mai bun drum de la starea inițială la o stare finală, trecând prin s.
  • g(s) este costul celui mai bun drum de la starea inițială la s.
  • h(s) este costul estimat al celui mai bun drum de la s la o stare finală.

• Dacă algoritmul este consistent, atunci g(s) = g*(s) este costul real al celui mai bun drum de la s0 la s.

• Dacă algoritmul este admisibil, atunci g(s) = g*(s) pentru stările de pe drumul optim către starea finală.

• Funcția heuristică h(s) estimează h*(s).

Proprietățile Funcției Heuristice h(s)

• h(s) este admisibilă dacă h(s) este mereu mai mică sau egală cu distanța reală până la scop h*(s).
• h(sf) = 0, costul până la starea finală e zero.
• algoritmul A* este admisibil - este garantat că primul drum găsit de la și la este și cel optim (din punct de vedere al costului).
• Un algoritm A1 este mai informat decât A2 dacă ∀s ∈ S, h1(s) ≥ h2(s).
• O funcție euristică este consistentă dacă h(s') ≤ h(s'') + cost_arc(s', s'') pentru ∀s', s'' ∈ S.

Admisibilitatea funcției h

• h (s) ≤ h* (s) - (h este o euristică optimistă).
• h (sf) = 0.
• funct ,ia h (s) este admisibilă, s ,i cost (s′, s″) > 0, ∀s′, s″ ∈ S.
• algoritmul A* este admisibil garantat că primul drum găsit de la si la sf este s, i cel optim (din punct de vedere al costului).

Algoritmul A*: Intrare și Ieșire

• Intrare: si, functia h(s).
• Ies, ire: solut ,ia, sau I NSUCCES.
• H[sprev ] ← minb∈actiuni(sprev ){c(sprev ,s') + H[s']
• Dacă există s' = Rezultat[sprev , b], altfel h(sprev ).

Algoritmi A* și Variații

• A* este mai eficient dacă este folosită o euristică mai bine informată.
• Dacă h(s) = 0, ∀s ∈ S, A* devine Dijkstra.
• Un algoritm A* este ponderat dacă favorizează euristica.
• Algoritmițele A* ponderate va favoriza stările (estimate ca fiind) mai apropiate de scop.
• O funcție h este ɛ-admisibilă,algoritmul găsește o soluție cu cel mult ɛ peste optim.

Memorie Limitată în Algoritmii de Căutare

• A* poate necesita o cantitate mare de memorie.
• Strategii care explorează un număr mai mic de stări: Beam search, Iterative deepening A* (IDA*), Memory-bound A* (MA*), Simplified MA* (SMA*).

Beam Search

• Combină BFS cu o abordare greedy folosind o euristică.
• Se păstrează în frontieră doar un număr limitat de stări (B).
• Se adaugă succesorii la frontieră.
• Apoi se selectează cele mai bune stări din frontieră menținânduse limita B.
• B este lățimea fasciculului.
• Algoritmul nu este optimal sau complet, dar este utilizat în traducerea automată.
• Poate deveni complet dacă este combinat cu DFS, beam stack search sau limited discrepancy search.

Implementarea Beam Search

• Primeste ca input: starea de inceput (start), latimea benzii (B), functia euristica (h), limita de iteratii (limita)
• Initializeaza: setul de stari curente (beam) cu starea de inceput si setul de stari vizitate (vizitat) tot cu starea de inceput
• Algoritmul continua atata timp cat exista stari in beam si numarul de stari vizitate e mai mic decat limita impusa
• Calculeaza succesorii pentru fiecare stare din beam si ii adauga in setul succ
• Daca exista un succesor care e stare finala, algoritmul s-a terminat cu succes
• Altfel, selecteaza cele mai bune B stari din succ, pe baza functiei euristice h
• Aceste stari selectate sunt adaugate in setul de stari vizitate si devin noul set de stari curente (beam)

IDA

• Combină ID-DFS cu A*, limitând adâncimea explorării.
• Explorarea se face doar până la o adâncime fixată, initial f (s0).
• Când această limită este atinsă, se extinde până la f (s*), cu s* cea mai bună stare găsită până acum.
• Algoritmul explorează mai mult în direcția soluției decât DFS.
• Consumă mai puțină memorie decât A*, nu menține structurile OPEN și CLOSED.

Căutare Locală

• Se bazează pe mutarea dintr-o stare curentă într-o stare vecină utilă când spațiul de căutare este mare sau memoria este limitată.
• Se concentrează pe starea finală, nu pe drumul până la soluție.
• E folosită în probleme de tip CSP.

Algoritmul Hill Climbing (HC)

• Alege întotdeauna o stare vecină pentru care funcția de evaluare este mai bună.
• Algoritmul se oprește dacă atinge o stare finală sau nu găsește o stare vecină mai bună.
• Acesta poate fi implementat cu first-choice sau steepest ascent.
• Alte variante de Hill Climbing: stochastic HC (alegere aleatorie), first-choice HC (alegere primul cu eval mai bun).
• Hill climbing găsește soluția doar dacă funcția eval este convexă pe spațiul stărilor.
• Problema celor 8 regine e un exemplu.

Probleme ale Hill Climbing

• Poate rămâne blocat în maxime locale.
• Nu poate trece de platouri.

Random Restart Hill Climbing

• Se repetă Hill Climbing de mai multe ori(N) cu stări inițiale aleatorii.
• Dacă HC are o probabilitate de reușită p, se poate alege N = 1/p.

Simulated Annealing

• Inspirat de procesul de călire din metalurgie.
• Se consideră că stările au o anumită energie.
• Se caută starea de energie minimă globală.
• Se poate merge într-o stare vecină mai proastă cu o anumită probabilitate.
• Probabilitatea de a alege o stare mai proastă scade pe măsură ce algoritmul progresează.
• Pentru generarea succesorilor, este util ca stările să fie de energie apropiată cu starea curentă.

Vulnerabilități

• Algoritmul este vulnerabil la seturi mari de stări cu energie foarte mică față de vecinii lor, dar nu global minimă (spații de stări numite "bazine").
• Se pot folosi reporniri - reveniri la stări de energie mică obținute în trecut, dacă au trecut un număr de pași în stări cu energie semnificativ mai mare decât minima găsită.
• Graful stărilor trebuie să aibă un diametru redus.

Local Beam Search

• Se începe cu B stări generate aleator.
• Stochastic Local Beam Search – alege stochastic cele B stări de păstrat în beam , cu o probabilitate proporțională cu calitatea stărilor ajută la evitarea maximelor locale.

Căutarea în Spații Continue

• Discretizarea spațiului.
• Realizarea de mutări cu un pas fix (sau cu un pas preogresiv mai mic).
• O problemă suplimentară apare când există "culmi" (ridges) nealiniate cu una dintre axe.
• Pentru urmat directia cu cel mai mare beneficiu se poate deriva local functia de evaluare.

Căutarea OnLine vs. OffLine

• Agentul are acces la informații în timpul căutării
• Căutarea "off-line": agentul are acces la toate stările problemei.
• Căutarea "on-line": agentul poate alege ca stare următoare doar o stare vecină cu starea curentă.

Particularitățile Căutării On-Line

• Într-o problemă de căutare online, Hill Climbing nu poate fi folosit în conjuncție cu Random Restart.
• Simulated Annealing funcționează doar dacă alege_succesor alege o stare vecină.
• BFS nu se poate aplica.
• La DFS, revenirea aduce un cost.
• La A*, nu putem alege orice nod pentru a fi explorat la următoarea iterație.

Căutarea On-Line: On-Line DFS

• Varianta de backtracking iterativ unde revenirea se face tot prin acțiuni care trebuie realizate în mediu.
• Utilizează tabele pentru a memora rezultatele acțiunilor întreprinse deja:

Căutarea On-Line: Asynchronous Dynamic Programming (ADP)

• Se lucrează prin obținerea soluției la diverse sub-probleme.
• Se poate obține drumul optim dacă am cunoas, te h pentru fiecare nod.
• Putem actualiza asincron estimarea h[s] pentru fiecare stare astfel.
• ADP e baza pentru Real-time A*.
• Obținem convergență pentru costuri pozitive.
• Este nepractică spațiile de stări mari.

Căutare On-Line: Real-time A* (LRTA*)

• Folosește o tabelă cu valorile estimate H[s] pentru fiecare stare.
• Actualizăm valorile pe măsură ce explorăm.
• Trebuie să considerăm costul pentru orice revenire.
• Revenim doar dacă costul estimat pe calea curentă depășește costul implicat de revenire.
• LRTA* se apropie de soluția optimă la parcurgeri succesive.
• Este completă dacă avem: toate costurile pozitive, există o cale de la orice stare la starea finală și funcția h este admisibilă.