AI Search & Planning

Question 1

Hur ser ett typiskt search problem ut? (sök problem)

Answer 1

Ett typiskt sökproblem definieras av ett initialt tillstånd och ett måltillstånd. Till exempel: Initial: A, Goal: F.

Question 2

Hur ser lösningen ut för ett search problem (sökproblem)?

Answer 2

Lösningen är en sekvens av åtgärder eller tillstånd som leder från det initiala tillståndet till måltillståndet.

Question 3

Vad är ett search tree (sökträd) och vad används det till?

Answer 3

Ett sökträd representerar sökutrymmet och visar möjliga lösningar från det initiala tillståndet. Det används för att organisera och visualisera sökprocessen.

Question 4

Vad är en tree search och hur fungerar det?

Answer 4

Tree search är en algoritm som söker igenom ett sökträd genom att expandera noder och generera deras barn. Det använder en lista av noder som väntar på att kontrolleras, kallad fringe.

Question 5

Vilka steg behövs för att bygga ett system som löser ett specifikt problem?

Answer 5

Definiera problemet med precisa specifikationer av initialt och slutligt tillstånd.
Analysera problemet för att identifiera viktiga egenskaper.
Isolera och representera dessa egenskaper i en kunskapsrepresentation.
Välj och tillämpa den bästa problemslösningstekniken.

Question 6

Vilka typiska frågor behöver besvaras i en problemslösningsprocess?

Answer 6

Är problemslösaren garanterad att hitta en lösning?
Kommer systemet alltid att avslutas eller fastna i en oändlig loop?
Är den funna lösningen optimal?
Vad är komplexiteten i sökprocessen?
Hur kan systemet reducera sökkomplexiteten?
Hur kan det effektivt använda representationsparadigmet?

Question 7

Vad är viktiga termer inom search problem (sökproblem) och deras betydelse?

Answer 7

Search space: Möjliga tillstånd och lösningar.
Initial state: Starttillstånd för sökprocessen.
Goal state: Sluttillståndet för sökprocessen.
Problem space: Vad som ska lösas.
Searching strategy: Strategi för att kontrollera sökningen.
Search tree: Trädrepresentation av sökutrymmet.

Question 8

Vad är målet i 8-pusslet och hur kan det lösas? Vilka är de viktiga komponenterna i 8-pusslet?

Answer 8

Målet är att arrangera brickorna i en specifik ordning. Lösningen innebär att flytta den tomma rutan tills brickorna är i rätt ordning.

States: Positioner för brickor.
Actions: Flytta den tomma rutan vänster, höger, upp eller ner.
Goal test: Målkonfigurationen.
Path cost: 1 per flytt.

Question 9

Vilka är de viktiga komponenterna i ett robotmonteringsproblem?

Answer 9

States: Realtidskoordinater för robotens ledvinklar och delar som ska monteras.
Actions: Kontinuerliga rörelser av robotens leder.
Goal test: Färdig montering.
Path cost: Tid att utföra.

Question 10

Vad illustrerar “rice and the chess board” historien?

Answer 10

Historien illustrerar exponentiell tillväxt och hur snabbt antalet stater kan växa i ett sökproblem. På den 64:e rutan skulle kungen behöva placera över 18 kvintiljoner riskorn, vilket motsvarar ungefär 350 års global risproduktion.

Question 11

Vad är den grundläggande idén med tree search-algoritmer?

Answer 11

Den grundläggande idén är offline, simulerad utforskning av sökutrymmet genom att generera efterföljare till redan utforskade tillstånd.

Question 12

Vad är målet och problemet i Romania-exemplet?

Answer 12

Målet är att resa från Arad till Bukarest. Problemet är att formulera tillstånd (städer) och åtgärder (kör mellan städer) för att hitta en lösning (sekvens av städer).
Problemet är att hitta den kortaste körvägen mellan två städer (Arad och Bukarest) genom att använda en sökstrategi som utforskar olika vägar och kostnader.

Question 13

Hur definieras en search strategy (sökstrategi) och hur utvärderas den?

Answer 13

En sökstrategi definieras genom att välja ordningen för nodexpansion. Den utvärderas utifrån fullständighet, tidskomplexitet, minneskomplexitet och optimalitet.

Question 14

Vad är uninformed search strategies och vilka exempel finns?

Answer 14

Uninformed search strategies använder endast information tillgänglig i problemdefinitionen. Exempel inkluderar:

Breadth-first search
Uniform-cost search
Depth-first search
Depth-limited search
Iterative deepening search

Question 15

Hur fungerar breadth-first search och hur implementeras det?

Answer 15

Breadth-first search expanderar den grundaste oexpanderade noden först. Det implementeras med en FIFO-kö, där nya efterföljare placeras i slutet av kön.
Breadth-first search (BFS) explores all the neighboring nodes at the
current depth before moving on to the nodes at the next depth level.

Question 16

Vad är egenskaperna hos breadth-first search?

Answer 16

Fullständighet: Ja, om trädet är ändligt.
Minne: Behåller varje nod i minnet.
Optimalitet: Ja, om kostnaden är 1 per steg.
Problem: Hög minnesanvändning.

Question 17

Hur fungerar depth-first search och hur implementeras det?

Answer 17

Depth-first search expanderar den djupaste oexpanderade noden först. Det implementeras med en LIFO-kö, där efterföljare placeras i början av kön.
Depth-first search (DFS) explores as far as possible along each branch
before backtracking.

Question 18

Vad är egenskaperna hos depth-first search?

Answer 18

Fullständighet: Nej, misslyckas i oändliga djuputrymmen eller med loopar.
Optimalitet: Nej.

Question 19

Vilka faktorer avgör valet mellan breadth-first och depth-first search?

Answer 19

Breadth-first: Bäst för att hitta den kortaste vägen eller alla möjliga lösningar.
Depth-first: Bättre för problem där vilken lösning som helst är acceptabel eller där lösningen troligtvis finns nära startpunkten.
Valet beror på det specifika problemet och dess krav.

Question 20

Vad är uniform-cost search och hur fungerar det?

Answer 20

Uniform-cost search expanderar noder baserat på den lägsta kostnaden hittills. Det använder en prioritetskö där noder med lägst kostnad expanderas först.

Question 21

Hur används en prioritetskö i uniform-cost search?

Answer 21

En prioritetskö används för att hantera och ordna noder baserat på deras kostnad, där noder med lägst kostnad expanderas först.

Question 22

Hur bestäms vilken barnnod som är mest lovande i en sökning?

Answer 22

Den mest lovande barnnoden bestäms genom att utvärdera kostnaden för att nå varje barnnod och välja den med lägst kostnad.

Question 23

Vad är informed search och hur skiljer det sig från uninformed search?

Answer 23

Informed search använder ytterligare information utöver problemdefinitionen för att vägleda sökningen mot målet mer effektivt. Det utnyttjar heuristiska funktioner som ger en uppskattning av kostnaden att nå målet från ett givet tillstånd, vilket hjälper algoritmen att fokusera på de mest lovande vägarna.

Question 24

Vad är en heuristisk funktion och hur används den i informed search?

Answer 24

En heuristisk funktion är en funktion som uppskattar kostnaden för att nå ett måltillstånd från ett givet tillstånd. Den används i informed search för att vägleda sökningen och hjälpa algoritmen att fokusera på de mest lovande vägarna.

Question 25

Är A*-algoritmen en informed eller uninformed search-algoritm?

Answer 25

A*-algoritmen är en informed search-algoritm eftersom den använder en heuristisk funktion för att uppskatta kostnaden för att nå måltillståndet och kombinera detta med den faktiska kostnaden hittills.

Question 26

Hur uppskattar A*-algoritmen löftet av en barnnod?

Answer 26

A*-algoritmen använder en utvärderingsfunktion f(n) = g(n) + h(n), där:

g(n) är kostnaden hittills för att nå n.
h(n) är den uppskattade kostnaden från n till målet.
f(n) är den uppskattade totala kostnaden för vägen genom n till målet.

Question 27

Hur används A* för att hitta rutter?

Answer 27

A* använder en kombination av faktisk kostnad hittills och en heuristisk uppskattning av återstående kostnad för att hitta den mest kostnadseffektiva vägen. Till exempel, f(n) = cost(start, n) + straight-line-distance(n, goal).

Question 28

Hur fungerar A*-algoritmen steg för steg?

Answer 28

Initialisering: Lägg startnoden i en prioritetskö, där noder prioriteras baserat på f(n).
Expansion: Ta bort noden med lägst f(n) från kön och expandera den, vilket innebär att generera dess barnnoder.
Utvärdering: Beräkna f(n) för varje barnnod och lägg dem i prioritetskön.
Kontroll: Om en barnnod är målnoden, stoppa och returnera lösningen. Om inte, upprepa från steg 2.
Optimalitet: A* garanterar att hitta den kortaste vägen om den heuristiska funktionen är admissible (dvs. aldrig överstiger den faktiska kostnaden till målet).

Question 29

Hur går A*-algoritmen tillväga för att hitta den kortaste vägen?

Answer 29

A* expanderar ständigt den nod som för närvarande har den lägsta f(n) värdet. Det betyder att den prioriterar de vägar som verkar mest lovande baserat på både den hittills ackumulerade kostnaden och den uppskattade återstående kostnaden till målet.

Question 30

Vad är resultatet av att använda A*-algoritmen?

Answer 30

A* (med straight-line distance som heuristisk funktion) kommer alltid att hitta den kortaste vägen till målet. Det är därför den används i navigationssystem för bilar och båtar. Det är en typ av Best-First-Search algoritm.

Question 31

Varför är A*-algoritmen effektiv?

Answer 31

Kombinerar fördelar: A* kombinerar fördelarna med både breadth-first och depth-first search, samtidigt som den undviker deras nackdelar.
Heuristik: A* använder en heuristisk funktion för att uppskatta kostnaden från nuvarande nod till målnoden, vilket fokuserar sökningen på de mest lovande vägarna.
Effektivitet: A* är mer effektiv än breadth-first search eftersom den använder heuristisk vägledning för att undvika onödiga vägar.
Optimalitet: A* garanterar att hitta den kortaste vägen om den heuristiska funktionen är admissible.
Anpassningsbarhet: A* kan anpassas till olika typer av problem genom att använda olika heuristiska funktioner, vilket gör den mångsidig och användbar i många olika scenarier.

Question 32

Vad är syftet med lokala sökalgoritmer? (Local Search Algorithms)

Answer 32

Lokala sökalgoritmer används i optimeringsproblem där vägen till målet är irrelevant och endast måltillståndet är lösningen. De hittar tillstånd som uppfyller vissa begränsningar, såsom att placera dambrädet i n-damer problem.

Local search-algoritmer är uninformed search eftersom de inte använder någon global information om sökutrymmet eller heuristiska funktioner för att vägleda sökningen. De använder bara lokal information, såsom nuvarande tillstånd och dess omedelbara grannar, för att hitta lösningar.

Question 33

Vad är hill-climbing search och vilka problem kan den stöta på?

Answer 33

Hill-climbing search är en lokal sökalgoritm som startar från ett initialt tillstånd och upprepade gånger rör sig till ett närliggande tillstånd som förbättrar målfunktionen tills ett lokalt maximum eller minimum nås. Problemet är att den kan fastna i lokala maxima, platåer eller ridged tillstånd.

Question 34

Hur illustreras hill-climbing search visuellt?

Answer 34

Hill-climbing search illustreras ofta som att bestiga en kulle, där varje steg är en rörelse till ett närliggande tillstånd med högre värde. Problemet är att det kan fastna på lokala toppar och aldrig nå den globala toppen.

Question 35

Vilka variationer av hill-climbing algoritmen finns?

Answer 35

Variationer inkluderar stokastisk hill-climbing, simulerad glödgning (simulated annealing) och genetiska algoritmer.

Question 36

Vad är simulated annealing och hur fungerar det?

Answer 36

Simulated annealing är en variation av hill-climbing som ibland tillåter nedåtgående steg för att undvika att fastna i lokala maxima. Det efterliknar processen för att kyla metall långsamt för att nå en lågenergikonfiguration.

Question 37

Vad är genetiska algoritmer och hur fungerar de?

Answer 37

Genetiska algoritmer använder principer från evolution, såsom mutation, crossover och selektion, för att hitta lösningar. En population av lösningar utvecklas över tid, där de bästa lösningarna selekteras för att producera nästa generation.

Question 38

Vad är iterative deepening search och hur fungerar det?

Answer 38

Iterative deepening search kombinerar fördelarna med depth-first och breadth-first search genom att utföra en serie av depth-limited searches med ökande gränser tills en lösning hittas. Det är komplett och minnesmässigt effektivt.

Question 39

Vad gör iterative deepening search på djup 0, på djup 1, på djup 2 och på djup 3?

Answer 39

På djup 0 expanderar den endast startnoden
På djup 1 expanderar den startnoden och dess direkta barnnoder.
På djup 2 expanderar den startnoden, dess direkta barnnoder och deras barnnoder.
På djup 3 expanderar den startnoden, dess direkta barnnoder, deras barnnoder och deras barnnoder.

Question 40

Vad är exempel på problem-solving agents?

Answer 40

Ett exempel är en agent som planerar en rutt från en stad till en annan genom att använda en sökalgoritm som A* för att hitta den mest kostnadseffektiva vägen.

Question 41

Vilka är de olika typerna av problem inom AI-sökning?

Answer 41

Deterministic, fully observable: Single-state problem där agenten vet exakt vilket tillstånd den kommer att vara i; lösningen är en sekvens av åtgärder.

Non-observable: Sensorless problem (conformant problem) där agenten inte har någon aning om var den är; lösningen är en sekvens av åtgärder.

Nondeterministic and/or partially observable: Contingency problem där perceptioner ger ny information om nuvarande tillstånd; ofta kombineras sökning och utförande.

Unknown state space: Exploration problem där agenten måste utforska och lära sig tillståndsrymden.

Question 42

Varför är AI-sökalgoritmer viktiga?

Answer 42

AI-sökalgoritmer hjälper maskiner att navigera genom komplexa sökutrymmen för att hitta optimala lösningar på ett brett spektrum av problem. De förbättrar effektiviteten, automatiserar repetitiva uppgifter, hjälper till med beslutsfattande och främjar innovation.

Question 43

Vad är skillnaden mellan deterministiska och icke-deterministiska algoritmer?

Answer 43

Deterministic algorithm: För en given input kommer datorn alltid att producera samma output genom att gå igenom samma tillstånd.
Non-deterministic algorithm: För samma input kan kompilatorn producera olika output vid olika körningar, den kan visa olika beteenden för samma input vid olika exekveringar.

Question 44

Vad är (Nondeterministic Polynomial) NP-fullständiga problem och varför är de svåra att lösa?

Answer 44

NP-fullständiga problem är en klass av matematiska problem för vilka effektiva lösningar saknas. Lösningen kräver i princip att man går igenom alla tänkbara lösningar och jämför dem, vilket är ogenomförbart för stora problem. Verifiering av en lösning tar polynomisk tid, men att hitta en lösning växer exponentiellt med problemets storlek.

Question 45

Vad är constraint programming (CP)?

Answer 45

Constraint programming är ett kraftfullt paradigm inom AI och datavetenskap för att lösa kombinatoriska problem. Det modellerar ett problem som en uppsättning variabler med möjliga värden och en uppsättning begränsningar som specificerar relationer mellan variablerna. Målet är att hitta en lösning som uppfyller alla begränsningar.

Question 46

Hur kan constraint programming användas i ett Lego-exempel?

Answer 46

En företag tillverkar bord och stolar. Varje bord ger $20 i vinst och varje stol ger $16 i vinst. Varje bord kräver två stora och två små Lego, och varje stol kräver en stor och två små Lego. Företaget har sex stora och åtta små Lego tillgängliga varje dag. Constraint programming kan användas för att maximera vinsten inom dessa begränsningar.

Question 47

Vad är schemaläggning i kontexten av constraint programming?

Answer 47

Schemaläggning innebär att allokera resurser över tid för att slutföra en uppsättning uppgifter. Constraint programming används för att modellera och lösa schemaläggningsproblem genom att definiera variabler, domäner och begränsningar för att hitta en optimal lösning.

Question 48

Vad är en planning agent?

Answer 48

En planning agent är en agent som använder planeringsalgoritmer för att välja åtgärder som uppnår ett visst mål. Agenten använder sensorer för att samla in information om sin omgivning och aktorer för att utföra åtgärder.

Question 49

Vad är målet med planering?

Answer 49

Målet med planering är att välja åtgärder som uppnår ett visst mål. Detta innebär att hitta en sekvens av åtgärder som kan transformera ett initialt tillstånd till ett måltillstånd.

Question 50

Varför är planering svårt?

Answer 50

Planering är svårt på grund av osäkerhet om omgivningen (t.ex. initialt tillstånd), osäkerhet om åtgärdernas effekter, påverkan av andra agenter eller externa händelser, agentens egna åtgärder kan ha negativa effekter och tids- och resursbegränsningar.

Question 51

Hur kan man göra planering enklare?

Answer 51

Genom att dra nytta av problemets egenskaper, använda explicita representationer av tillstånd, mål, åtgärder och planer, fokusera sökningen på åtgärder som uppfyller delmål, använda specialiserade algoritmer och använda måluppdelning (divide and conquer).

Question 52

Hur används representationer i planering?

Answer 52

Planering öppnar upp “black-boxes” genom att använda logik för att representera åtgärder (actions), tillstånd (states) och mål (goal). Ett exempel på ett språk som används för detta är STRIPS (STanford Research Institute Problem Solver).

Question 53

Hur representeras tillstånd i STRIPS?

Answer 53

Tillstånd representeras som en konjunktion av propositioner, till exempel: BLOCK(A), BLOCK(B), ON(A,TABLE), CLEAR(B), HANDEMPTY.

Question 54

Hur representeras mål i STRIPS?

Answer 54

Mål representeras som en konjunktion av propositioner, till exempel: ON(A,TABLE), ON(B,A), ON(C,B). Målet är uppnått i ett tillstånd om alla propositioner i målet också finns i tillståndet.

Question 55

Hur representeras åtgärder i STRIPS?

Answer 55

Åtgärder representeras med precondition och effect. Till exempel, för åtgärden Unstack(C,A):

Precondition: HANDEMPTY, BLOCK(C), BLOCK(A), CLEAR(C), ON(C,A)
Effect: ¬HANDEMPTY, ¬CLEAR(C), HOLDING(C), ¬ON(C,A), CLEAR(A)

Question 56

Ge ett exempel på hur åtgärder representeras i STRIPS.

Answer 56

För åtgärden Pickup(x):

Precondition: HANDEMPTY, BLOCK(x), CLEAR(x), ON(x,TABLE)
Effect: ¬HANDEMPTY, ¬CLEAR(x), HOLDING(x), ¬ON(x,TABLE)

Question 57

Vilka är utmaningarna med AI och planering?

Answer 57

En stor utmaning är “closed world assumption” som antar att världsmodellen innehåller all nödvändig information, vilket innebär att det inte kan finnas några överraskningar. Ett annat problem är frame-problemet, som handlar om att representera verkliga världssituationer på ett sätt som är beräkningsmässigt hanterbart.

Question 58

Vad är några av huvuddragen i STRIPS-språket?

Answer 58

Representation av tillstånd: Tillstånd representeras som en konjunktion av positiva litteraler. Antagandet om en sluten värld gäller, vilket innebär att om en tillståndsvariabel inte nämns, antas den vara falsk.
Representation av mål: Mål representeras som en konjunktion av positiva grundlitteraler. Ett mål är uppnått om alla litteraler i målet är sanna i tillståndet.
Representation av åtgärder: Åtgärder representeras med namn, parameterlista, precondition (konjunktion av funktionfria litteraler) och effect (konjunktion av funktionfria litteraler).

Question 59

Hur representeras ett planeringsproblem för luftfrakt i STRIPS?

Answer 59

Init (state): At(C1, SFO) ∧ At(C2, JFK) ∧ At(P1, SFO) ∧ At(P2, JFK) ∧ Cargo(C1) ∧ Cargo(C2) ∧ Plane(P1) ∧ Plane(P2) ∧ Airport(JFK) ∧ Airport(SFO)

Goal: At(C1, JFK) ∧ At(C2, SFO)

Actions: Load, Unload, Fly

Question 60

Vilka är åtgärderna för luftfrakt i STRIPS och deras preconditions och effects?

Answer 60

Load(c, p, a)
Precondition: At(c, a) ∧ At(p, a) ∧ Cargo(c) ∧ Plane(p) ∧ Airport(a)
Effect: ¬At(c, a) ∧ In(c, p)
Unload(c, p, a)
Precondition: In(c, p) ∧ At(p, a) ∧ Cargo(c) ∧ Plane(p) ∧ Airport(a)
Effect: At(c, a) ∧ ¬In(c, p)
Fly(p, from, to)
Precondition: At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to)
Effect: ¬At(p, from) ∧ At(p, to)

Question 61

Vilka två typer av sökningar kan användas för planering i tillståndsrymden? Planning with state-space search

Answer 61

Progression planners (forward state-space search): Utforskar effekten av alla möjliga åtgärder i ett givet tillstånd.
Regression planners (backward state-space search): Arbetar bakåt från målet genom att bestämma vilka tillstånd som måste ha varit sanna tidigare.

Question 62

Hur fungerar progression och regression i planeringssökning?

Answer 62

Progression (Forward Planning): Utforskar framåt från initialt tillstånd genom att tillämpa åtgärder och generera efterföljande tillstånd tills måltillståndet uppnås.
Regression (Backward Planning): Arbetar bakåt från måltillståndet genom att bestämma vilka tillstånd och åtgärder som skulle ha lett till det aktuella tillståndet.

Question 63

Vad innebär progression (forward) planning?

Answer 63

Progression planning innebär att man börjar från det initiala tillståndet och utforskar alla möjliga åtgärder och deras effekter framåt i tiden tills man når måltillståndet.

Question 64

Vad är partial-order planning och hur skiljer det sig från progression och regression?

Answer 64

Partial-order planning är en planeringsalgoritm som kan placera två åtgärder i en plan utan att specificera vilken som kommer först. Detta skiljer sig från progression och regression som är helt ordnade planeringssökformer och kräver sekvensering av alla åtgärder.

Question 65

Vad är STRIPS och vad används det till?

Answer 65

STRIPS (Stanford Research Institute Problem Solver) är ett språk som används för att representera och lösa planeringsproblem inom AI. Det utvecklades på 1960-talet vid Stanford Research Institute av Richard Fikes och Nils Nilsson. STRIPS används i automatiserad planering och schemaläggningssystem.