PREVENT Artificial Intelligence Practical Session (UVIGO) - RO

Inteligență artificială - ProiectUL PREVENT

Inundații

Începe

Sesiune practică de inteligență artificială

Exercițiile realizate în această sesiune sunt concepute pentru a construi o înțelegere cuprinzătoare a AI-ului — de la algoritmi de căutare de bază până la tehnici sofisticate de învățare automată — toate menținând elevii implicați cu feedback vizual și probleme provocatoare care reflectă aplicații din lumea reală. Bazat pe materialele cursului UC Berkeley CS188 Intro to AI.

Din cauza constrângerilor de timp, laboratoarele vor fi ghidate/demonstrate de profesori.

Filozofia & Obiectivele Proiectului

Vizualizare

Proiectele permit elevilor să vizualizeze direct rezultatele tehnicilor AI implementate în acțiune, oferind feedback imediat și o intuiție mai bună despre conceptele abstracte.

Structură Minimă

Fiecare proiect conține instrucțiuni clare și exemple de cod fără un cod de pornire excesiv, încurajând elevii să-și dezvolte și să înțeleagă propriile soluții.

Provocare din Lumea Reală

Pac-Man oferă un mediu cu adevărat provocator care necesită soluții creative, reflectând complexitatea întâlnită în aplicațiile AI din lumea reală.

Aceste principii creează un mediu în care elevii nu doar implementează algoritmi — ci dezvoltă intuiție despre modul în care tehnicile AI funcționează în practică, construind abilități care se transferă în procesarea limbajului natural, viziune computerizată, robotică și alte domenii de vârf.

Începere: Tutorial UNIX/Python

Bazele Python

Mediul UNIX

Introducere în elementele de bază ale limbajului de programare Python, cu accent pe caracteristicile utilizate pe parcursul proiectelor Pac-Man, inclusiv structuri de date și programare orientată pe obiecte.

Comenzi esențiale UNIX și configurarea mediului pentru a dezvolta, testa și depana eficient implementările AI necesare pentru proiectele ulterioare.

Flux de lucru în dezvoltare

Cele mai bune practici pentru gestionarea codului, rularea experimentelor și analizarea rezultatelor într-un mod sistematic, pregătind studenții pentru natura iterativă a dezvoltării AI.

Acest tutorial preliminar asigură că toți studenții au baza tehnică necesară înainte de a se aprofunda în conceptele AI. Standardizând pe Python fără dependențe externe, cursul menține accesibilitatea și predă abilități practice de programare relevante în dezvoltarea modernă AI.

Algoritmi de Căutare

Căutare în Profunzime

Elevii implementează acest algoritm fundamental, în care Pac-Man explorează cât mai departe de fiecare ramură înainte de a reveni, învățând despre frontiere bazate pe stivă și traversarea graficelor.

Căutare în Lățime

Implementarea se concentrează pe găsirea celui mai scurt drum în termeni de mutări, folosind frontiere bazate pe coadă pentru a explora toți vecinii la fiecare nivel de adâncime înainte de a continua.

Căutare cu Cost Uniform

Elevii își extind implementările pentru a ține cont de costurile diferite de mișcare, introducând cozi de prioritate și garanții de optimalitate.

Căutare A*

Proiectul se încheie cu implementarea acestui algoritm de căutare informată, solicitând elevilor să proiecteze heuristici admisibile care îmbunătățesc semnificativ eficiența căutării.

Prin aceste implementări, elevii urmăresc modul în care Pac-Man navighează prin labirinturi din ce în ce mai complexe, vizualizând concret modul în care diferite algoritmi explorează spațiul de stare. Varianta problemei comis-voiajorului provoacă elevii să optimizeze traseele de colectare a punctelor, introducându-i în probleme computațional intractabile.

Căutare Multi-Agent

Întreruperea Alpha-Beta

Căutare Adversarială

Implementarea acestei tehnici de optimizare îmbunătățește semnificativ eficiența căutării minimax prin eliminarea ramurilor care nu vor influența decizia finală.

Studenții modelează Pac-Man și fantomele ca agenți competitori, implementând strategii de căutare minimax în care Pac-Man maximizează scorul, iar fantomele îl minimizează.

Expectimax

Funcții de evaluare

Studenții dezvoltă algoritmi pentru medii stocastice în care fantomele se mișcă aleatoriu, necesitând raționament probabilistic în loc de presupunerea unui adversar cu comportament maxim negativ.

Proiectul provoacă studenții să proiecteze și să implementeze funcții personalizate de evaluare a stării care cuantifică "bunătatea" pozițiilor de joc atunci când anticiparea este limitată.

Acest proiect leagă teoria clasică a jocurilor de implementarea practică, demonstrând cum tehnicile din jocurile pentru doi jucători, precum șahul, se aplică în Pac-Man. Studenții dobândesc intuiție despre tehnicile de tăiere și compromisurile între diferite modele de comportament ale adversarului, concepte esențiale în inteligența artificială modernă pentru jocuri și luarea deciziilor în condiții de incertitudine.

Învățarea prin întărire

Iterarea valorii

Elevii implementează acest algoritm bazat pe model, care calculează politica optimă având un model complet al mediului, învățând cum formalizează procesele decizionale Markov.

Învățarea Q

Trecând la învățarea fără model, elevii implementează acest algoritm de diferență temporală în care Pac-Man învață comportamentul optim prin încercare și eroare în interacțiune cu mediul.

Învățarea Q aproximativă

Elevii își extind implementarea pentru a utiliza reprezentări bazate pe caracteristici, permițând învățarea în jocul complet Pac-Man, unde spațiul de stare este prea mare pentru metode tabulare.

Robot de târât

Proiectul aplică aceleași tehnici unui braț robot simulat, demonstrând cum învățarea prin întărire se extinde dincolo de jocuri către sarcini de control fizic.

Acest proiect demonstrează modul în care învățarea prin întărire — paradigma din spatele multor recente descoperiri AI — funcționează în practică. Elevii asistă la agenți care încep cu comportament aleator și se îmbunătățesc treptat prin experiență, câștigând înțelegere despre compromisurile explorare-exploatare și puterea aproximației funcțiilor în medii complexe.

Inferența probabilistică: Vânătorii de fantome

Modele Markov ascunse

Inferența exactă

Filtrarea prin particule

Studenții implementează inferența probabilistică într-un model Markov ascuns în care Pac-Man trebuie să urmărească fantome invizibile bazându-se pe citiri zgomotoase ale senzorilor, învățând despre stările de credință și estimarea recursivă a stării.

Implementarea algoritmului înainte permite lui Pac-Man să mențină o distribuție precisă de probabilitate asupra locațiilor fantomelor, demonstrând cum regula lui Bayes permite agenților să raționeze în condiții de incertitudine.

Studenții implementează această metodă de inferență aproximativă în care credințele sunt reprezentate prin mostre, învățând despre compromisurile computaționale care permit inferența în domenii complexe și din lumea reală.

Acest proiect aduce modelele probabilistice la viață arătând cum permit luarea deciziilor inteligente cu informații incomplete. Studenții experimentează direct cum reprezentarea incertitudinii în mod explicit duce la comportament mai robust al agentului — o idee esențială care stă la baza roboticii moderne, recunoașterii vocale și altor sisteme AI.

Clasificare în Învățare Automată

În acest proiect final, studenții implementează algoritmi de bază în învățarea automată pentru clasificarea cifrelor, inclusiv Naive Bayes (un model generativ probabilistic), Perceptron (un algoritm discriminativ online) și MIRA (o abordare bazată pe margine).

Concluzia apare când studenții aplică aceste tehnici pentru a crea un agent Pac-Man de clonare comportamentală care învață observând jocul expert. Acest lucru leagă clasificarea de luarea deciziilor și demonstrează cum învățarea supravegheată permite agenților să imite comportamentul uman — o tehnică din ce în ce mai utilizată în aplicații de la vehicule autonome la asistenți virtuali.

Prin aceste proiecte, studenții obțin atât înțelegere teoretică, cât și experiență practică în implementarea tehnicilor fundamentale AI care alimentează inovațiile tehnologice moderne.

Sesiune practică de inteligență artificială

Implementare

Proiectul Pacman

Proiectele Pac-Man au fost dezvoltate pentru cursul introductiv de inteligență artificială de la UC Berkeley. Include diferitele proiecte prezentate anterior:

• Căutare: Studenții implementează algoritmi de căutare în adâncime, în lățime, cost uniform și A*. Acești algoritmi sunt folosiți pentru rezolvarea problemelor de navigare și ale vânzătorului ambulant în lumea Pacman.
• Căutare Multi-Agent: Pacman clasic este modelat ca o problemă de căutare adversarială și stocastică. Studenții implementează algoritmi minimax multiagent și expectimax, precum și proiectează funcții de evaluare.
• Învățare prin Întărire: Studenții implementează algoritmi de învățare prin întărire bazată pe model și fără model.
• Ghostbusters: Inferența probabilistică într-un model Markov ascuns urmărește mișcarea fantomelor ascunse în lumea Pacman. Studenții implementează inferența exactă folosind algoritmul înainte și inferența aproximativă prin filtre de particule.
• Clasificare: Studenții implementează algoritmi standard de clasificare în învățarea automată folosind modele Naive Bayes, Perceptron și MIRA pentru clasificarea cifrelor. Studenții extind acest lucru implementând un agent Pacman de clonare comportamentală.

Căutare (I)

• Agenți de planificare:

• Întreabă „ce-ar fi dacă”
• Decizii bazate pe (ipoteticele) consecințe ale acțiunilor
• Trebuie să aibă un model al modului în care lumea evoluează ca răspuns la acțiuni
• Trebuie să formuleze un scop (test)
• Să ia în considerare cum AR FI lumea
• Planificare optimă vs. completă

Căutare (II)

• O problemă de căutare constă în:
• Un spațiu de stare
• O funcție de succesori(cu acțiuni, costuri)

• O stare de început și un test de țintă
• O soluție este o secvență de acțiuni (un plan) care transformă starea de început într-o stare țintă

“N”, 1.0

“E”, 1.0

Căutare (III): Exemplu: Călătorie în România

• Spațiu de stare:
• Orașe
• Funcția succesor:
• Drumuri: Mergi în orașul adiacent cu cost = distanță
• Stare de start:
• Arad
• Testul de scop:
• Este starea == București?
• Soluție?

Căutare (IV): Spațiu de stare

Starea lumii include fiecare detaliu al mediului

O stare de căutare păstrează doar detaliile necesare pentru planificare (abstracție)

• Problema: Rutare
• Stări: poziția (x,y)
• Acțiuni: N S E V
• Succesor: actualizează doar poziția
• Testul de scop: este (x,y)=SFÂRȘIT

• Problema: Mănâncă-Toate-Pelete
• Stări: {(x,y), boolean pentru pete}
• Acțiuni: N S E V
• Succesor: actualizează poziția și eventual boolean-ul pentru pete
• Testul de scop: toate petele false

Căutare (V): Grafice ale spațiului de stare

• Graficul spațiului de stare: O reprezentare matematică a unei probleme de căutare
• Nodurile sunt configurații (abstracte) ale lumii
• Arcele reprezintă succesorii (rezultatele acțiunilor)
• Testul de scop este un set de noduri scop (poate doar unul)

• Într-un grafic de spațiu de stare, fiecare stare apare o singură dată!

• Putem construi rar acest grafic complet în memorie (este prea mare), dar este o idee utilă

Căutare (VI): Arbori de căutare

Acum / start

“E”, 1.0

“N”, 1.0

Futures posibile

• Un arbore de căutare:
• Un „ce-ar fi dacă” arbore de planuri și rezultatele lor
• Starea de start este nodul rădăcină
• Copiii corespund succesorilor
• Nodurile arată stări, dar corespund PLANURILOR care ating acele stări
• Pentru cele mai multe probleme, nu vom putea construi niciodată întregul arbore

Căutare (VII): Căutare cu un Arbore de Căutare

• Căutare:
• Extinde potențialii pași (noduri de arbore)
• Menține o frunză a planurilor parțiale în considerare
• Încearcă să extinzi cât mai puține noduri de arbore

Căutare (VIII): Căutare în adâncime

Căutare (IX): Căutare în lățime

Cod pentru implementarea algoritmului de căutare

Descărcați codul:

• git clone https://github.com/felipexil/pacman.git

Utilizând Python 2, testați jocul:

• cd pacman/search/search
• python pacman.py

Pacman trăiește într-o lume albastră strălucitoare, cu coridoare învârtite și gustări rotunde delicioase. Navigarea eficientă în această lume va fi primul pas al lui Pacman în stăpânirea domeniului său. Agentul cel mai simplu din searchAgents.py se numește GoWestAgent, care merge mereu spre Vest (un agent reflex trivial). Acest agent poate câștiga ocazional:

• python pacman.py --layout testMaze --pacman GoWestAgent

Dar, lucrurile devin urâte pentru acest agent atunci când este nevoie de schimbarea direcției:

• python pacman.py --layout tinyMaze --pacman GoWestAgent

Dacă Pacman se blochează, puteți ieși din joc tastând CTRL-c în terminalul dvs. Rețineți că pacman.py suportă o serie de opțiuni, care pot fi exprimate fie în mod lung (de exemplu, --layout), fie în mod scurt (de exemplu, -l). Puteți vedea lista tuturor opțiunilor și valorile lor implicite folosind:

• python pacman.py -h

Găsirea unui punct fix de alimentare folosind căutarea în adâncime (I)

În fișierul searchAgents.py, vei găsi un agent de căutare complet implementat, care planifică o cale prin lumea lui Pacman și apoi execută acea cale pas cu pas. Algoritmii de căutare pentru formularea unui plan nu sunt implementați — asta îți revine ție. Mai întâi, testează dacă agentul de căutare funcționează corect rulând:

• python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch

Comanda de mai sus indică agentului de căutare să folosească tinyMazeSearch ca algoritm de căutare, care este implementat în search.py. Pacman ar trebui să navigheze cu succes prin labirint. Toate funcțiile tale de căutare trebuie să returneze o listă de acțiuni care să conducă agentul de la început la țintă. Aceste acțiuni trebuie să fie toate mutări legale (direcții valide, fără a trece prin pereți). Asigură-te că utilizezi structurile de date Stack, Queue și PriorityQueue furnizate în util.py! Implementează algoritmul de căutare în adâncime (DFS) în funcția depthFirstSearch din search.py. Pentru ca algoritmul tău să fie complet, scrie versiunea de căutare în graf, care evită expandarea oricăror stări deja vizitate.

Găsirea unui punct fix de mâncare folosind căutarea în adâncime (II)

ALGORITM procedură DFS(G,v): /* G  Graf, v  v de start */ lasă S ca fiind o stivă S.push(v) în timp ce S nu este goală v = S.pop() dacă v nu este etichetat ca descoperit: etichetază v ca fiind descoperit pentru toate muchiile din v spre w în G.adjacentEdges(v) do S.push(w)

• python pacman.py -l tinyMaze -p SearchAgent -a fn=bfs
• python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
• python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=bfs

Găsirea unui punct de hrană fix folosind căutarea în adâncime (III)

def depthFirstSearch(problem): # Structuri de date necesare st = util.Stack() parent = dict steps = list have_visited = set start_state = (problem.getStartState(), None, None) st.push(start_state) while (nu st.isEmpty()): state = st.pop() have_visited.add(state[0]) # Vizitează starea curentă # Găsit starea țintă if (problem.isGoalState(state[0])): # Trasă înapoi drumul și inversează-l pentru a obține secvența corectă de pași while (state != start_state): steps.append(state[1]) state = parent[state] steps.reverse() return steps # Extinde succesorii successors = problem.getSuccessors(state[0]) for successor in successors: if (successor[0] nu în have_visited): parent[successor] = state st.push(successor) # Soluție/Drum nu există return None

Găsirea unui punct fix de alimentare folosind căutarea în lățime

ALGORITM nod ← un nod cu STARE = problem.INITIAL-STATE, COST-DRUM = 0 dacă problem.GOAL-TEST(nod.STARE) atunci returnează SOLUȚIE(nod) frontiera ← o coadă FIFO cu nodul ca singur element explorat ← un set gol buclă do dacă ESTE GOAL?(frontiera) atunci returnează eșec nod ← POP(frontiera) /*alege cel mai superficial nod din frontieră*/ adaugă nod.STARE în explored pentru fiecare acțiune în problem.ACTIONS(nod.STARE) do copil ← CHILD-NODE(problem, nod, acțiune) dacă copil.STARE nu este în explored sau frontieră atunci dacă problem.GOAL-TEST(copil.STARE) atunci returnează SOLUȚIE(copil) reinseră (copil, frontieră)