PREVENT Artificial Intellignece Practical Session (UVIGO) - SW

Artificiell intelligens - PREVENT-projekt

Översvämningar

Start

Praktisk session om artificiell intelligens

Övningarna som genomförs i denna session är utformade för att bygga en omfattande förståelse av AI – från grundläggande sökalgoritmer till avancerade maskininlärningstekniker – allt medan eleverna hålls engagerade med visuell feedback och utmanande problem som speglar verkliga tillämpningar. Den är baserad på UC Berkeley CS188 Introduktion till AI -- Kursmaterial.

På grund av tidsbegränsningar kommer labbar att ledas/demonstreras av professorerna.

Projektfilosofi & Mål

Visualisering

Projekt gör det möjligt för elever att direkt visualisera resultaten av deras implementerade AI-tekniker i praktiken, vilket ger omedelbar feedback och bättre intuition om abstrakta koncept.

Minimal Stödstruktur

Varje projekt innehåller tydliga instruktioner och kodexempel utan överdrivet startkod, vilket uppmuntrar elever att utveckla och förstå sina egna lösningar.

Verklighetsutmaning

Pac-Man presenterar en verkligt utmanande miljö som kräver kreativa lösningar, vilket speglar komplexiteten i verkliga AI-applikationer.

Dessa principer skapar en miljö där elever inte bara implementerar algoritmer—de utvecklar intuition för hur AI-tekniker fungerar i praktiken, och bygger färdigheter som överförs till naturlig språkbehandling, datorseende, robotik och andra banbrytande områden.

Komma igång: UNIX/Python tutorial

Python-grunder

UNIX-miljö

Introduktion till Python-programmeringsspråkets grunder med betoning på funktioner som används i hela Pac-Man-projekten, inklusive datastrukturer och objektorienterad programmering.

Väsentliga UNIX-kommandon och miljöinställningar för att effektivt utveckla, testa och felsöka AI-implementeringar som krävs för efterföljande projekt.

Utvecklingsarbetsflöde

Bästa praxis för att hantera kod, köra experiment och analysera resultat på ett systematiskt sätt som förbereder studenter för den iterativa naturen av AI-utveckling.

Denna preliminära tutorial säkerställer att alla studenter har den tekniska grunden som behövs innan de dyker in i AI-koncept. Genom att standardisera på Python utan externa beroenden behåller kursen tillgängligheten samtidigt som den lär ut praktiska programmeringsfärdigheter som är relevanta i modern AI-utveckling.

Sökningsalgoritmer

Djupet-First Sökning

Studenter implementerar denna grundläggande algoritm där Pac-Man utforskar så långt som möjligt längs varje gren innan den backar, och lär sig om stackbaserade fronter och grafgenomgång.

Bredden-First Sökning

Implementeringen fokuserar på att hitta den kortaste vägen i termer av rörelser, med hjälp av köbaserade fronter för att utforska alla grannar på varje djupnivå innan den fortsätter.

Enhetskostnadsökning

Studenter utökar sina implementationer för att ta hänsyn till olika rörelsekostnader, och introducerar prioriteringsköer och optimalitetsgarantier.

A* Sökning

Projektet kulminerar med att implementera denna informerade sökalgoritm, vilket kräver att studenter designar tillåtande heuristiker som avsevärt förbättrar sökeffektiviteten.

Genom dessa implementationer ser studenter Pac-Man navigera labyrinter av ökande komplexitet, och visualiserar konkret hur olika algoritmer utforskar tillståndsrymden. Variationen av försäljningsresenärsproblemet utmanar studenter att optimera vägar för att samla prickar, och introducerar dem till beräkningsmässigt intractabla problem.

Fleragentssökning

Alpha-Beta beskärning

Motstridiga sökningar

Implementeringen av denna optimeringsteknik förbättrar dramatiskt effektiviteten av minimax-sökning genom att eliminera grenar som inte påverkar det slutgiltiga beslutet.

Elever modellerar Pac-Man och spöken som konkurrerande agenter, och implementerar minimax-sökningsstrategier där Pac-Man maximerar poängen medan spöken minimerar den.

Expectimax

Utvärderingsfunktioner

Elever utvecklar algoritmer för stokastiska miljöer där spöken rör sig slumpmässigt, vilket kräver probabilistiskt resonemang snarare än att anta värsta fall- motståndarbeteende.

Projektet utmanar elever att designa och implementera egna tillståndsbedömningsfunktioner som kvantifierar "godheten" av spelpositioner när förutseelsen är begränsad.

Detta projekt förenar klassisk spelteori med praktisk implementering och visar hur tekniker från tvåspelarspel som schack kan tillämpas på Pac-Man. Elever får insikt i beskärningstekniker och avvägningarna mellan olika modeller av motståndarbeteende, vilket är centrala koncept inom modern spel-AI och beslutsfattande under osäkerhet.

Förstärkningsinlärning

Värdeiteration

Elever implementerar denna modellbaserade algoritm som beräknar den optimala policyn givet en fullständig modell av miljön, och lär sig hur Markov-beslutsprocesser formaliserar sekventiella beslutsproblem.

Q-inlärning

Går över till modellfri inlärning, elever implementerar denna tidsdifferensalgoritm där Pac-Man lär sig optimalt beteende genom trial-and-error-interaktion med miljön.

Approximerad Q-inlärning

Elever utökar sin implementation för att använda funktionsbaserade representationer, vilket möjliggör inlärning i hela Pac-Man-spelet där tillståndsrymden är för stor för tabellmetoder.

Crawling Robot

Projektet tillämpar samma tekniker på en simulerad robotarm, vilket visar hur förstärkningsinlärning generaliserar bortom spel till fysiska kontrolluppgifter.

Detta projekt visar hur förstärkningsinlärning—paradigmet bakom många senaste AI-genombrott—fungerar i praktiken. Elever får se agenter som börjar med slumpmässigt beteende och gradvis förbättras genom erfarenhet, vilket ger insikt i utforsknings-utnyttjandebalansen och kraften i funktionsapproximation i komplexa miljöer.

Probabilistisk inferens: Ghostbusters

Dolda Markovmodeller

Exakt inferens

Partikelfiltrering

Studenter implementerar probabilistisk inferens i en dold Markovmodell där Pac-Man måste spåra osynliga spöken baserat på brusiga sensorsignaler, och lär sig om trostillstånd och rekursiv tillståndsestimering.

Implementering av framåt-algoritmen gör att Pac-Man kan behålla en exakt sannolikhetsfördelning över spökens positioner, vilket visar hur Bayes regel möjliggör för agenter att resonera under osäkerhet.

Studenter implementerar denna approximativa inferensmetod där trostillstånd representeras av prover, och lär sig om de beräkningsmässiga avvägningarna som möjliggör inferens i komplexa, verkliga domäner.

Detta projekt ger liv åt probabilistiska modeller genom att visa hur de möjliggör intelligent beslutsfattande med ofullständig information. Studenter får uppleva på egen hand hur explicit representation av osäkerhet leder till mer robust agentbeteende—en nyckelinsikt som ligger till grund för modern robotik, taligenkänning och andra AI-system.

Maskininlärningsklassificering

I detta slutprojekt implementerar eleverna kärnalgoritmer för maskininlärning för att klassificera siffror, inklusive Naiv Bayes (en generativ probabilistisk modell), Perceptron (en diskriminerande online-algoritm) och MIRA (en marginalbaserad metod).

Klimaxet kommer när eleverna tillämpar dessa tekniker för att skapa en beteende-klonande Pac-Man-agent som lär sig genom att observera expertspel. Detta kopplar klassificering till beslutsfattande och visar hur övervakad inlärning gör det möjligt för agenter att efterlikna mänskligt beteende—en teknik som i allt större utsträckning används i tillämpningar från autonoma fordon till virtuella assistenter.

Genom dessa projekt får eleverna både teoretisk förståelse och praktisk erfarenhet av grundläggande AI-tekniker som driver moderna teknologiska innovationer.

Praktisk session om artificiell intelligens

Implementering

Pacman-projektet

Pacman-projekten utvecklades för UC Berkeleys introduktionskurs i artificiell intelligens. Den inkluderar de olika projekten som presenterades tidigare:

• Sök: Studenter implementerar djup-först, bredd-först, enhetskostnad och A*-sökalgoritmer. Dessa algoritmer används för att lösa navigations- och resande försäljarproblem i Pacman-världen.
• Multi-Agent Sök: Klassisk Pacman modelleras som både en adversarial och en stokastisk sökproblem. Studenter implementerar multiagent minimax och expectimax-algoritmer, samt utformar utvärderingsfunktioner.
• Förstärkningsinlärning: Studenter implementerar modellbaserade och modellfria förstärkningsinlärningsalgoritmer.
• Ghostbusters: Probabilistisk inferens i en dold Markovmodell spårar rörelsen av dolda spöken i Pacman-världen. Studenter implementerar exakt inferens med hjälp av framåt-algoritmen och approximativ inferens via partikelfilter.
• Klassificering: Studenter implementerar standard maskininlärningsklassificeringsalgoritmer med Naive Bayes, Perceptron och MIRA-modeller för att klassificera siffror. Studenter utökar detta genom att implementera en beteendeklonings-Pacman-agent.

Sökning (I)

• Planeringsagenter:

• Fråga "vad händer om"
• Beslut baserade på (hypotetiska) konsekvenser av handlingar
• Måste ha en modell av hur världen utvecklas som svar på handlingar
• Måste formulera ett mål (test)
• Överväg hur världen SKULLE VARA
• Optimal vs. fullständig planering

Search (II)

• Ett sökproblem består av:
• Ett tillståndsrum
• En efterföljarfunktion(med handlingar, kostnader)

• Ett starttillstånd och ett måltest
• Ett lösning är en sekvens av handlingar (en plan) som förvandlar starttillståndet till ett mål

“N”, 1.0

“E”, 1.0

Sökning (III): Exempel: Resa i Rumänien

• Tillståndsrum:
• Städer
• Efterföljarfunktion:
• Vägar: Gå till närliggande stad med kostnad = avstånd
• Starttillstånd:
• Arad
• Måttest:
• Är tillstånd == Bukarest?
• Lösning?

Sökning (IV): Tillståndsrum

Världen inkluderar varje detalj av miljön

Ett sökstatus behåller endast de detaljer som behövs för planering (abstraktion)

• Problem: Pathfinding
• States: (x,y) plats
• Actions: NÖV
• Successor: uppdatera platsen endast
• Måttest: är (x,y)=SLUT

• Problem: Ät-Alla-Punkter
• States: {(x,y), punkt-booleanar}
• Actions: NÖV
• Successor: uppdatera plats och eventuellt en punkt-boolean
• Måttest: alla punkter är falska

Sökning (V): Tillståndsrumsgrafer

• Tillståndsrumsgraf: En matematisk representation av ett sökproblem
• Noder är (abstrakta) världskonfigurationer
• Bågar representerar efterföljare (aktionsresultat)
• Måttestet är en uppsättning mål noder (kanske bara en)

• I ett tillståndsrumsgraf uppstår varje tillstånd bara en gång!

• Vi kan sällan bygga detta fullständiga graf i minnet (det är för stort), men det är en användbar idé

Sökning (VI): Sökträd

Detta är nu / start

“E”, 1.0

“N”, 1.0

Möjliga framtider

• En sökträd:
• Ett ”vad om” träd av planer och deras resultat
• Starttillståndet är rotknuten
• Barnen motsvarar efterföljare
• Noder visar tillstånd, men motsvarar PLANER som uppnår dessa tillstånd
• För de flesta problem kan vi aldrig faktiskt bygga hela trädet

Sök (VII): Sök med ett sökträd

• Sök:
• Expandera potentiella planer (trädnoder)
• Håll ett fringe av delplaner under övervägande
• Försök att expandera så få trädnoder som möjligt

Sökning (VIII): Djupet-First Sökning

Sökning (IX): Bredden-först-sökning

Kod för implementering av sökalgoritmen

Ladda ner koden:

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

Använd Python 2, testa spelet:

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

Pacman lever i en glänsande blå värld av vridande korridorer och smakrika runda godsaker. Att navigera denna värld effektivt är Pacmans första steg mot att bemästra sitt område. Den enklaste agenten i searchAgents.py heter GoWestAgent, som alltid går västerut (en trivial reflexagent). Denna agent kan ibland vinna:

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

Men, saker och ting blir otrevliga för denna agent när vändningar krävs:

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

Om Pacman fastnar kan du avsluta spelet genom att skriva CTRL-c i din terminal. Observera att pacman.py stöder ett antal alternativ som kan uttryckas antingen i lång form (t.ex. --layout) eller i kort form (t.ex. -l). Du kan se listan över alla alternativ och deras standardvärden via:

• python pacman.py -h

Hitta en Fast Matpunkt med djupet-först-sökning (I)

I searchAgents.py hittar du en fullt implementerad SearchAgent, som planerar en väg genom Pacmans värld och sedan utför den steg för steg. Sökalgoritmerna för att formulera en plan är inte implementerade — det är ditt jobb. Först, testa att SearchAgent fungerar korrekt genom att köra:

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

Kommandot ovan instruerar SearchAgent att använda tinyMazeSearch som sin sökalgoritm, vilket är implementerat i search.py. Pacman bör navigera genom labyrinten framgångsrikt. Alla dina sökfunktioner måste returnera en lista av åtgärder som leder agenten från start till mål. Dessa åtgärder måste vara lagliga rörelser (giltiga riktningar, ingen genomgång av väggar). Se till att använda Stack, Queue och PriorityQueue datastrukturerna som tillhandahålls i util.py! Implementera djup-först-sökning (DFS) algoritmen i funktionen depthFirstSearch i search.py. För att göra din algoritm komplett, skriv graf-sökversionen av DFS, som undviker att expandera redan besökta tillstånd.

Hitta en Fast Matpunkt med djupförst sökning (II)

ALGORITM procedur DFS(G,v): /* G  Graf, v  startpunkt */ låt S vara en stack S.push(v) medan S inte är tom v = S.pop() om v inte är märkt som upptäckt: märk v som upptäckt för alla kanter från v till w i G.adjacentEdges(v) gör 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

Hitta en Fast Matpunkt med djupförstsökning (III)

def depthFirstSearch(problem): # Nödvändiga datastrukturer st = util.Stack() parent = dict() steps = list() have_visited = set() start_state = (problem.getStartState(), None, None) st.push(start_state) while (inte not st.isEmpty()): state = st.pop() have_visited.add(state[0]) # Besök det aktuella tillståndet # Hittade mål tillstånd if (problem.isGoalState(state[0])): # Spåra tillbaka vägen och vänd den för att få rätt sekvens av steg while (state != start_state): steps.append(state[1]) state = parent[state] steps.reverse() return steps # Expandera efterföljare successors = problem.getSuccessors(state[0]) for successor in successors: if (successor[0] not in have_visited): parent[successor] = state st.push(successor) # Lösning/Path existerar inte return None

Hitta en Fast Matpunkt med hjälp av Bredden Först Sökning

ALGORITM nod ← en nod med TILLSTÅND = problem.INITIAL-STATE, VÄG-KOSTNAD = 0 om problem.GOAL-TEST(nod.TILLSTÅND) då returnera LÖSNING(nod) frontier ← en FIFO-kö med nod som det enda elementet utforskad ← en tom mängd loopa om FRONTIER? då returnera misslyckande nod ← POP(frontier) /*väljer den grundaste noden i frontiern*/ lägg till nod.TILLSTÅND i utforskad för varje handling i problem.ACTIONS(nod.TILLSTÅND) gör barn ← BARN-NOD(problem, nod, handling) om barn.TILLSTÅND inte är i utforskad eller fronten då om problem.GOAL-TEST(barn.TILLSTÅND) då returnera LÖSNING(barn) frontier ← INFÖR (barn, frontier)