TDT4136 Intro til KI

Agent

En enhet som oppfatter sitt environment gjennom sensors og påvirker det gjennom actuators.

Rational Agent

En agent som velger den action som maksimerer dens forventede performance measure, gitt dens percept sequence og innebygde kunnskap.

Percept Sequence

Den komplette historikken av alt agenten har oppfattet gjennom sine sensors frem til nå.

Agent Function

En abstrakt matematisk kartlegging fra percept sequence til en action.

Agent Program

Den konkrete implementeringen av agent function som kjører på en fysisk arkitektur.

PEAS

Akronym for: Performance measure, Environment, Actuators, Sensors.

Agent Architecture

Koblingen mellom sensors og actuators via et program.

Factored Representation

En state representert ved attributter/variabler (f.eks. GPS, batteri), i motsetning til atomic representation.

Belief State

Mengden av alle mulige fysiske states agenten tror den kan befinne seg i, gitt dens percept history.

Model-Based Agent

En agent som bruker en intern transition model for å holde styr på hvordan verden endres over tid.

Utility-Based Agent

En agent som bruker en utility function for å rangere states basert på hvor ønskelige de er.

Fully Observable vs. Partially Observable

Om agentens sensors gir tilgang til hele state av environment (Fully) eller om info mangler (Partially).

Deterministic vs. Stochastic

Om neste state er fullstendig bestemt av nåværende state/action (Deterministic) eller om det er usikkerhet (Stochastic).

Episodic vs. Sequential

Om episoder er uavhengige (Episodic) eller om nåværende action påvirker fremtidige states (Sequential).

Static vs. Dynamic

Om environment endrer seg mens agenten tenker (Dynamic) eller står stille (Static).

Discrete vs. Continuous

Om states/time/percepts har endelige verdier (Discrete) eller kontinuerlige verdier.

State Space

Mengden av alle mulige states som kan nås fra initial state gjennom en sekvens av actions.

Frontier (Open Set)

Mengden av nodes som er generert (funnet), men ennå ikke expanded (utforsket).

Expansion

Prosessen med å generere child nodes fra en node ved å bruke tilgjengelige actions.

Uninformed Search

Søkestrategier uten ekstra info om states utover problemdefinisjonen (f.eks. BFS, DFS).

Breadth-First Search (BFS)

Expands den grunneste node i frontier først (FIFO-kø). Garanterer korteste sti ved like step costs.

Depth-First Search (DFS)

Expands den dypeste node i frontier først (LIFO-kø). Ikke optimal/complete i uendelige rom.

Uniform-Cost Search (UCS)

Expands noden med lavest path cost g(n). Er optimal og complete.

Iterative Deepening Search (IDS)

Kjører Depth-Limited Search med økende dybdegrense. Kombinerer fordeler fra BFS og DFS.

Bidirectional Search

Søker samtidig fra initial state fremover og fra goal state bakover.

Heuristic function h(n)

En funksjon som estimerer cost fra node n til nærmeste goal state.

Greedy Best-First Search

Informed search som expands noden med lavest h(n).

A* Search

Informed search som bruker f(n) = g(n) + h(n). Optimal hvis h(n) er admissible/consistent.

Admissible Heuristic

En heuristikk som aldri overestimerer faktisk cost til goal (optimistisk).

Consistent (Monotonic) Heuristic

Strengere krav der h(n) <= c(n, a, n') + h(n'). Nødvendig for optimalitet i graph search.

Branching Factor (b)

Antallet successors (barn) en node har i søketreet.

Evaluation Function f(n)

Funksjonen som bestemmer hvilken node som skal expands først (f.eks. f(n) = g(n) + h(n) i A*).

Optimal Solution

Løsningen med lavest mulig path cost.

Completeness

En algoritmes garanti for at den vil finne en løsning hvis en finnes.

Local Search

Algoritmer som bruker en enkelt current state og flytter til naboer (sparer minne).

Hill Climbing

Greedy algoritme som alltid beveger seg mot en nabo med høyere value. Kan stoppe i local maxima.

Local Maximum/Optimum

En topp i state space som er høyere enn naboene, men lavere enn global maximum.

Plateau

Et flatt område i state space hvor naboene har samme value.

Simulated Annealing

Algoritme som unngår local maxima ved å tillate "dårlige trekk" basert på temperature T.

Genetic Algorithms

Variant av stochastic beam search inspirert av evolusjon (population, fitness, crossover, mutation).

Heuristic Dominance

Hvis h2(n) >= h1(n) for alle n, dominerer h2 h1 (og er mer effektiv).

Relaxed Problem

Et problem med færre constraints. Kostnaden av løsningen her brukes ofte som admissible heuristic.

Gradient Descent

Kontinuerlig variant av Hill Climbing (beveger seg i retning av bratteste endring).

Random Restart

Teknikk i Local Search hvor man starter på nytt fra tilfeldig state hvis man står fast.

CSP (Constraint Satisfaction Problem)

Problem definert av Variables, Domains og Constraints. Målet er en gyldig assignment.

Constraint Graph

Graf hvor nodes er variabler og edges er constraints.

Unary vs. Binary Constraint

Unary begrenser én variabel; Binary begrenser forholdet mellom to.

Node Consistency

Når alle verdier i en variabels domain tilfredsstiller unary constraints.

Backtracking Search

DFS for CSP hvor man velger verdier for én variabel og "backtracker" ved brudd på constraint.

Minimum Remaining Values (MRV)

Heuristikk for variabelvalg: Velg variabelen med færrest lovlige verdier (fail-first).

Degree Heuristic

Tie-breaker for MRV: Velg variabelen involvert i flest constraints.

Least Constraining Value (LCV)

Heuristikk for verdivalg: Velg verdien som utelukker færrest verdier for naboene.

Forward Checking

Inference som fjerner umulige verdier fra domains til naboer når en variabel får en verdi.

Arc Consistency (AC-3)

Inference-metode. En bue X->Y er consistent hvis hver verdi i X har en gyldig match i Y.

Min-Conflicts

Local search for CSP. Velger verdi som minimerer antall conflicts med andre variabler.

Cutset Conditioning

Metode for å løse CSP med sykluser ved å fikse verdier i et cutset så resten blir et tre.

Zero-Sum Game

Spill hvor summen av utility for alle spillere er konstant (en vinner, en taper).

Minimax Algorithm

Algoritme for å finne optimalt trekk ved å anta at motstanderen spiller optimalt (minimerer din gevinst).

Alpha-Beta Pruning

Optimalisering av Minimax som kutter grener som ikke trenger utforskes.

Evaluation Function (Games)

Heuristikk brukt når søket kuttes før terminal state. Estimerer vinnersjanse.

Chance Node

Node i spilltre som representerer tilfeldighet (f.eks. terningkast).

Expectiminimax

Minimax tilpasset spill med chance nodes (bruker vektet gjennomsnitt).

Monte Carlo Tree Search (MCTS)

Bruker random sampling (playouts) for å evaluere noder. Balanserer exploration/exploitation.

Nash Equilibrium

Tilstand hvor ingen spiller tjener på å bytte strategy alene.

Dominant Strategy

En strategy som alltid gir best resultat uansett hva motstanderen gjør.

Pareto Optimal

Utfall hvor man ikke kan gjøre det bedre for én uten å gjøre det verre for en annen.

Mixed Strategy

Strategi der spilleren velger handlinger basert på sannsynligheter (randomisering).

Prisoner's Dilemma

Spillteoretisk problem som viser hvorfor to individer kanskje ikke samarbeider selv om det lønner seg.

Knowledge Base (KB)

Et sett av sentences i et formelt språk som representerer hva agenten vet.

Entailment (KB |= a)

Forholdet at hvis KB er sann, MÅ a også være sann.

Model

En matematisk abstraksjon som fastsetter sannhetsverdien til setninger.

Soundness

En inference algorithm er sound hvis den kun utleder setninger som faktisk er entailed.

Completeness (Logic)

En inference algorithm er complete hvis den kan utlede alle setninger som er entailed.

Valid (Tautology)

En setning som er sann i alle mulige models.

Satisfiable

En setning som er sann i minst én model.

Unsatisfiable (Contradiction)

En setning som er falsk i alle models.

Conjunctive Normal Form (CNF)

Standardform for logikk: Konjunksjon (AND) av clauses (OR av literals).

Resolution

Inference rule som er sound og complete for CNF. Brukes i proof by contradiction.

Modus Ponens

Inference rule: Fra A => B og A, kan vi utlede B.

Modus Tollens

Inference rule: Fra A => B og ikke-B, kan vi utlede ikke-A.

Horn Clause

Clause med maks én positiv literal. Tillater rask inferens.

First-Order Logic (FOL)

Logikk med Objects, Relations og Quantifiers.

Atomic Sentence

Den enkleste formen for setning (f.eks. P eller Brother(John, Bob)).

Literal

En atomic sentence eller dens negasjon.

Unification

Å finne en substitution for variabler som gjør to logiske uttrykk identiske.

Skolemization

Fjerning av eksistensielle kvantorer ved å erstatte variabler med Skolem constants/functions.

PDDL

Planning Domain Definition Language. Beskriver States, Actions, Preconditions, Effects.

State-Space Search (Planning)

Planlegging ved å søke gjennom rommet av states (Forward eller Backward).

Forward (Progressive) Search

Søk fra initial state mot goal.

Backward (Regression) Search

Søk fra goal bakover mot initial state (reverserer handlinger).

Heuristics in Planning

Bruk av relaxed problems (f.eks. Ignore Preconditions) for å lage admissible heuristics.

Ignore Preconditions Heuristic

Antar at alle handlinger kan utføres når som helst (teller antall uoppfylte goals).

Ignore Delete Lists Heuristic

Antar at handlinger aldri sletter literals (problemet blir monotonic).

Partial Order Planning (POP)

Søk i plan space. Planen kan ha delvise rekkefølger (parallelle handlinger).

Hierarchical Task Network (HTN)

Planlegging ved å bryte ned High-Level Actions til primitive actions.

Sensorless Planning

Planlegging uten sensors. Må finne en plan som virker for alle mulige belief states.

Contingency Planning

Planlegging med grener (if-then) basert på observasjoner underveis.

Ontology

Formell beskrivelse av konsepter og relasjoner i et domene.

Semantic Network

Grafisk representasjon av kunnskap (noder=konsepter, kanter=relasjoner).

Reification

Å gjøre en relasjon/handling om til et objekt for å kunne si ting OM det.