Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Søk under usikkerhet, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En handling med en mengde mulige utfall, , uten sannsynligheter. Agenten får vite hvilket utfall som skjedde først etter handlingen (nondeterministic action).
En plan som forgreiner seg på utfallet av handlingene, skrevet med if–then–else, slik at den virker for alle mulige utfall (conditional plan, contingency plan).
Et søketre med OR-noder, der agenten velger én handling, og AND-noder, der hvert mulig utfall av en handling må ha en plan. En løsning er et deltre med mål i hvert blad (AND–OR search tree).
En betinget plan med en løkke som prøver en handling igjen når den mislykkes. Den er en løsning når hvert blad er et mål og målet kan nås fra hvert punkt i planen (cyclic plan).
Mengden av fysiske tilstander agenten kan være i, gitt det den har gjort og observert. Med fysiske tilstander finnes opptil slike mengder (belief state).
Et problem der agenten ikke observerer noe, så planen må virke uansett hvilken tilstand agenten startet i. Planen er en fast handlingssekvens over oppfatningstilstander (sensorless problem, conformant problem).
Å bruke handlinger som fører mange mulige tilstander til den samme, for eksempel å kjøre mot en vegg, slik at oppfatningstilstanden krymper uten observasjoner (coercion).
Steget som gir oppfatningstilstanden etter en handling: unionen av alle mulige utfall fra hver tilstand i (prediction).
Steget som filtrerer den predikerte oppfatningstilstanden med perceptet: bare tilstandene der agenten ville fått nettopp det perceptet, beholdes (update).
Å holde oppfatningstilstanden oppdatert med prediksjon og oppdatering etter hver handling og hvert percept, slik en robot gjør når den lokaliserer seg (state estimation).
Søk der agenten ikke kjenner miljøet på forhånd og må veksle mellom å handle og å planlegge, fordi den bare lærer utfallet av en handling ved å utføre den (online search).
En tilstand der målet ikke lenger kan nås, ofte etter en irreversibel handling. Ingen online algoritme kan unngå blindveier i alle tilstandsrom (dead end).
Kostnaden en online agent faktisk bruker, delt på kostnaden den ville brukt om den kjente miljøet. Med blindveier kan forholdet bli uendelig (competitive ratio).
Online søk som lagrer et lært anslag for hver besøkt tilstand og oppdaterer det etter hvert trekk; uprøvde handlinger anslås optimistisk med (learning real-time A*).
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Prediksjonssteget
Oppfatningstilstanden etter handlingen , før noe er observert. Går agenten mot en vegg og blir stående, er utfallet selv. Vanlig feil: å fjerne tilstander der handlingen ikke flytter agenten.
Oppdateringssteget
Behold bare tilstandene i den predikerte der agenten ville fått perceptet . Filtrer etter prediksjonen, aldri før.
Antall oppfatningstilstander
Med fysiske tilstander er hver oppfatningstilstand en delmengde, så det finnes delmengder, eller uten den tomme. Bare noen få er vanligvis nåbare.
Konkurranseforholdet
Mål på hvor godt en online agent gjør det. Det er minst 1, og det kan bli uendelig når miljøet har blindveier.
LRTA*-oppdateringen
Etter hvert trekk får tilstanden agenten forlot et nytt anslag. En handling som ikke er prøvd i , teller med i stedet for . Vanlig feil: å glemme kostnaden .
Kodesnutter
Kodesnutter fra kapittelet, vist literal.
Korteste sensorløse plan i et drivhus
kolonner = 3 # @param 3..6 # Drivhus: to bedrader med vegg imellom og én åpning midt på; roboten har ingen sensorer.ruter = {(r, k) for r in (0, 2) for k in range(kolonner)} | {(1, kolonner // 2)}steg = {"N": (1, 0), "S": (-1, 0), "Ø": (0, 1), "V": (0, -1)} def resultat(s, a): # mot vegg eller kant blir roboten stående q = (s[0] + steg[a][0], s[1] + steg[a][1]) return q if q in ruter else s start = frozenset(ruter)forrige, ko = {start: None}, [start]while ko: # bredde-først-søk i rommet av oppfatningstilstander b = ko.pop(0) if len(b) == 1: break for a in steg: b2 = frozenset(resultat(s, a) for s in b) # prediksjon if b2 not in forrige: forrige[b2] = (b, a) ko.append(b2)plan, sluttrute = [], min(b)while forrige[b]: b, a = forrige[b] plan.insert(0, a)storrelser, b = [len(start)], startfor a in plan: b = frozenset(resultat(s, a) for s in b) storrelser.append(len(b))print(f"Plan: {', '.join(plan)}")print(f"Antall mulige ruter underveis: {', '.join(map(str, storrelser))}")print(f"Rute til slutt: {sluttrute}")print(f"Handlinger til én tilstand: {len(plan)}")Prøv: øk kolonner fra 3 til 6 og se at linja Handlinger til én tilstand: vokser fra 5 til 9, fordi planen i Plan: først må samle roboten ved åpningen i veggen.
LRTA* over flere forsøk
forsok = 1 # @param 1..6 h = [1, 1, 2, 2, 3, 2, 1, 0] # opprinnelig anslag; målet er rute 7, start i rute 3H, resultat = {}, {} # lært restkostnad og kjente utfall (s, handling) -> s′ def kost(s, a): # LRTA*-kost: uprøvd handling anslås optimistisk med h(s) return h[s] if (s, a) not in resultat else 1 + H[resultat[(s, a)]] def handlinger(s): return [a for a in ("V", "Ø") if 0 <= s + (-1 if a == "V" else 1) < len(h)] for k in range(1, forsok + 1): s, forrige, steg = 3, None, 0 while s != 7: H.setdefault(s, h[s]) if forrige: # lær av trekket som førte hit resultat[forrige] = s H[forrige[0]] = min(kost(forrige[0], b) for b in handlinger(forrige[0])) a = min(handlinger(s), key=lambda b: kost(s, b)) # lik kost: vest først forrige, s, steg = (s, a), s + (-1 if a == "V" else 1), steg + 1 print(f"Forsøk {k}: {steg} steg")print(f"H(start) etter siste forsøk: {H[3]}")Prøv: sett forsok til 2 og se at det andre forsøket bare trenger 4 steg, fordi linja H(start) etter siste forsøk: allerede viser den sanne restkostnaden 4.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklar forskjellen på ikke-deterministiske og stokastiske handlinger, og skriv en betinget plan med if–then–else
- 02Konstruer et AND-OR-søketre og avgjør om en betinget eller syklisk plan er en løsning
- 03Regn ut oppfatningstilstanden etter prediksjon og etter oppdatering med et percept
- 04Finn en sensorløs plan som tvinger agenten til én tilstand
- 05Regn ut en LRTA*-oppdatering, og forklar konkurranseforhold og blindveier i online søk