Introduksjon til kunstig intelligens Hjem

CMD + K

Introduksjon til kunstig intelligensTDT4136

CMD + K

Introduksjon til kunstig intelligensKapittel 17Hierarkisk planlegging og planlegging under usikkerhet

10 min lesing

Hierarkisk planlegging og planlegging under usikkerhet

Store oppgaver planlegges best ovenfra: en høynivåhandling forfines steg for steg til primitive handlinger. Når agenten ikke vet alt om verden, lager du sensorløse og betingede planer, og overvåker utførelsen slik at agenten kan planlegge på nytt når noe går galt.

Læringsmål

01Forklar høynivåhandling, forfining og implementasjon, og finn implementasjonene til en høynivåhandling i et hierarki
02Regn ut antall implementasjoner med $r^{(d - 1) / (k - 1)}$ , og sammenlign med $b^{d}$ for primitivt søk
03Spor oppfatningstilstanden gjennom en sensorløs plan, også med betingede effekter
04Sammenlign sensorløs, betinget og online planlegging, og velg riktig form for et gitt miljø
05Forklar handlings-, plan- og målovervåking, og avgjør når planovervåking utløser replanlegging

0 av 17 aktiviteter

Kjerneidé

Store oppgaver planlegges ovenfra. «Klargjør hytta» blir til «varm opp» og «gjør rent», og først helt nederst til enkle handlinger som «hent ved». Planer møter dessuten virkeligheten: agenten vet ikke alt, og ting går galt underveis. En god turleder har en plan B for regnvær og sjekker hele dagen om resten av planen fortsatt holder.

Steg 1 av 6

Høynivåhandlinger og forfininger

Konsept

En utleier skal klargjøre en hytte før neste gjest. Hun planlegger ikke «gå tre skritt mot vedskjulet». Hun tenker «varm opp» og «gjør rent», og fyller inn detaljene etterpå. Hierarkisk planlegging gjør det samme.

En primitiv handling (primitive action) kan utføres direkte, som «hent ved», og har forutsetning og effekt som i PDDL. En høynivåhandling (high-level action, HLA) er abstrakt, som «varm opp», og kan ikke utføres direkte. Den må erstattes med én av forfiningene sine. En forfining (refinement) er en rekke handlinger høynivåhandlingen kan erstattes med, og den kan selv inneholde høynivåhandlinger. Hierarkiet kan derfor ha mange nivåer.

En rekke av bare primitive handlinger som en høynivåhandling kan forfines til, er en implementasjon (implementation). En høynivåhandling har ofte mange implementasjoner, én for hver kombinasjon av valg nedover. Den når målet fra en tilstand hvis minst én av implementasjonene gjør det, og planleggeren velger hvilken.

Høynivåhandlinger med to forfininger hver
Høynivåhandling	Forfining 1	Forfining 2
Klargjør hytta	Uthevet: Varm opp, Gjør rent	Bestill vask, Slå på varmepumpa
Varm opp	Hent ved, Fyr i ovnen	Uthevet: Slå på varmepumpa
Gjør rent	Uthevet: Feie, Vaske gulv	Bestill vask

Klargjør hytta, Varm opp og Gjør rent er høynivåhandlinger; de andre handlingene i tabellen er primitive.

Laster interaktiv figur …

Figur 17.1Klargjør hytta som hierarki. De uthevede valgene gir implementasjonen Slå på varmepumpa, Feie, Vaske gulv.

Hierarkiet er kunnskap om domenet. Det forteller hvilke kombinasjoner av handlinger som gir mening, og det kan gjenbrukes: «varm opp» brukes også før en vinterhelg der ingen trenger å vaske. Forfiningene kan ha egne krav til tilstanden. «Hent ved» krever at det er ved i skjulet, så forfining 1 av Varm opp virker bare når vedskjulet ikke er tomt. Er det tomt, må planleggeren velge varmepumpa. Slik velges forfining etter hvilken tilstand agenten står i.

RegneeksempelList alle implementasjonene av Klargjør hytta i tabellen.Vis løsning

Steg 1. Forfining 2. Den er allerede primitiv: [Bestill vask, Slå på varmepumpa].

Steg 2. Forfining 1. Varm opp har to implementasjoner og Gjør rent har to, så det gir $2 \cdot 2 = 4$ : [Hent ved, Fyr i ovnen, Feie, Vaske gulv], [Hent ved, Fyr i ovnen, Bestill vask], [Slå på varmepumpa, Feie, Vaske gulv] og [Slå på varmepumpa, Bestill vask].

Steg 3. Til sammen har Klargjør hytta $1 + 4 = 5$ implementasjoner. [Varm opp, Gjør rent] er en forfining, men ikke en implementasjon.

Øving 1 av 3Flervalg

Hva skiller en høynivåhandling fra en primitiv handling?

Øving 2 av 3Flervalg

Høynivåhandlingen Varm opp har forfiningene [Hent ved, Fyr i ovnen] og [Slå på varmepumpa]. Klargjør hytta har forfiningen [Varm opp, Gjør rent]. Gjør rent er også en høynivåhandling, mens Hent ved, Fyr i ovnen og Slå på varmepumpa er primitive. Hvilken påstand stemmer?

Øving 3 av 3Rekkefølge

Hierarkiet under har fire høynivåhandlinger. Velg alltid den første forfiningen. Skriv implementasjonen av ArrangerKonsert som primitive handlinger i rekkefølge, adskilt med komma.

ArrangerKonsert:  [Forbered, Gjennomfør]
Forbered:         [LeiSal, Annonser]      eller  [LånAula]
Gjennomfør:       [Rigg, Spill, Rydd]
Annonser:         [Plakat]                eller  [Nettside, Epost]

Steg 2 av 6

Hierarkisk søk

Konsept

Et hierarkisk søk (hierarchical search, HTN planning) starter med en plan som bare inneholder toppnivåhandlingen. I hver runde velges en høynivåhandling i planen og en av forfiningene dens, og høynivåhandlingen erstattes med stegene. Når planen bare har primitive handlinger, sjekkes det om den når målet. Hvert valg av forfining gir et nytt alternativ, så søket er et vanlig søk i rommet av delvis forfinede planer, for eksempel bredde-først.

nei, forfin videre 1 Start med planen [HLA] 2 Velg en HLA i planen 3 Velg en forfining hver forfining gir ett nytt alternativ i køen 4 Erstatt HLA-en med stegene 5 ja Er planen primitiv? (nei, forfin videre: tilbake til steg 2) 6 Når planen målet? ja : Plan funnet nei : Forkast, ta neste alternativ 1 Start med planen [HLA] 2 Velg en HLA i planen 3 Velg en forfining hver forfining gir ett nytt alternativ i køen 4 Erstatt HLA-en med stegene 5 Er planen primitiv? (nei, forfin videre: tilbake til steg 2) ja 6 Når planen målet? ja : Plan funnet nei : Forkast, ta neste alternativ nei, forfin videre

Laster interaktiv figur …

Figur 17.2Løkken i hierarkisk søk. Køen holder delvis forfinede planer, og den første primitive planen som når målet, er svaret.

Hva sparer det? Et primitivt søk velger blant $b$ handlinger i hver tilstand, og en plan med $d$ handlinger har $b^{d}$ mulige rekkefølger. Det hierarkiske søket velger bare forfininger. Har hver høynivåhandling $r$ forfininger med $k$ steg hver, har forfiningstreet til en plan med $d$ primitive handlinger $(d - 1) / (k - 1)$ indre noder. Antallet mulige trær er ƒantall forfiningstrær:

r^{(d - 1) / (k - 1)} mot b^{d}

Med få og lange forfininger er forskjellen enorm. Prisen er at hierarkiet må lages av noen som kjenner domenet, og at søket bare finner planer som hierarkiet tillater. Finnes det en kortere plan som hierarkiet ikke har med, ser søket den aldri. En forfining kan også inneholde høynivåhandlingen selv, for eksempel «vask ett rom, så vask resten». Det gir planer av vilkårlig lengde, men da må søket være bredde-først eller ha en dybdegrense, ellers kan det forfine i det uendelige. I praksis bygges hierarkiene ofte som biblioteker av forfininger som ble laget for én oppgave og brukes om igjen i neste.

RegneeksempelEn plan skal ha

d = 9

primitive handlinger. Hver høynivåhandling har

r = 2

forfininger med

k = 3

steg, og et primitivt søk har

b = 4

handlinger per tilstand. Sammenlign antallet planer.Vis løsning

Steg 1. Indre noder. $(9 - 1) / (3 - 1) = 4$ høynivåhandlinger må forfines.

Steg 2. Hierarkisk. $2^{4} = 16$ forfiningstrær.

Steg 3. Primitivt. $4^{9} = 262144$ handlingsrekker, altså over 16 000 ganger så mange.

Playground

Implementasjoner mot primitive planer

Prøv: sett nivaaer til 4 og se at linja Antall implementasjoner blir 32 768, mens det primitive søket får over to billioner planer å velge mellom.

forfininger2nivaaer3

Pythonkap17-implementasjoner.py

forfininger = 2  # @param 1..4
nivaaer = 3  # @param 1..4
k = 2  # steg i hver forfining
b = 6  # handlinger per tilstand i et primitivt søk

d = k ** nivaaer  # primitive handlinger i en ferdig plan
indre = (d - 1) // (k - 1)  # høynivåhandlinger som forfines (indre noder i treet)
tall = lambda x: f"{x:,}".replace(",", " ")
print(f"HLA-er som forfines: {indre}")
print(f"Primitive handlinger per implementasjon: {d}")
print(f"Antall implementasjoner: {tall(forfininger ** indre)}")
print(f"Planer i primitivt søk med b = {b}: {tall(b ** d)}")

Ctrl/Cmd + Enter kjører

Øving 1 av 2Flervalg

Hva sparer hierarkisk søk sammenlignet med å søke blant primitive handlinger?

Øving 2 av 2Tallsvar

En plan skal ende med $d = 16$ primitive handlinger. Hver høynivåhandling har $r = 3$ forfininger, og hver forfining har $k = 4$ steg. Hvor mange ulike forfiningstrær, og dermed implementasjoner, finnes?

Steg 3 av 6

Sensorløs planlegging

Konsept

Klassisk planlegging antar at agenten kjenner starttilstanden, og at handlingene alltid gjør det de skal. Uten de antagelsene må agenten planlegge i oppfatningstilstander (belief states), som i kapittel 5. En oppfatningstilstand $b$ skrives som en konjunksjon av literaler agenten vet holder. En fluent som ikke står i $b$ , er ukjent, ikke usann. Lukket verden gjelder altså ikke her.

I sensorløs planlegging (sensorless planning) har agenten ingen percepter. Planen må da nå målet fra alle fysiske tilstander i start-oppfatningstilstanden, og en handling kan bare brukes når $b ⊨ PRECOND (a)$ . Oppfatningstilstanden etter en handling er ƒoppfatningstilstanden etter en handling:

b^{'} = (b ∖ {\overset{ˉ}{ℓ} : ℓ \in EFF (a)}) \cup EFF (a)

Mange handlinger gjør ulike ting i ulike tilstander. En betinget effekt (conditional effect) skrives $when C : E$ . Er $C$ kjent sann i $b$ , gjelder $E$ . Er $C$ kjent usann, skjer ingenting. Er $C$ ukjent, blir fluentene i $E$ ukjente, og de fjernes fra $b$ . Planen er en løsning når ƒkravet til en sensorløs løsning holder:

GOAL \subseteq b_{n}

Regelen for ukjente betingelser er en forenkling. Tenk på en handling Koble med effekten $when Lys(R1) : Lys(R2)$ , utført når begge lampene er ukjente. Etterpå vet agenten egentlig at $Lys(R1) \Rightarrow Lys(R2)$ : lyser R1, lyser også R2. En liste med kjente literaler kan ikke uttrykke en slik sammenheng mellom to fluenter, så regelen lar $Lys(R2)$ være ukjent og kaster kunnskapen. Vi kaster heller kunnskap enn å påstå noe som kanskje er usant. Planen kan da bli lengre enn nødvendig, men en plan som virker for den forenklede oppfatningstilstanden, virker også i alle de fysiske tilstandene.

Tenk på to rom med hver sin lampe og ukjent bryterstand. Vipp(r) bytter lampa i rom $r$ , og knappen AltAv slår av alle lampene. Tabellen viser hvordan AltAv gjør verden kjent, slik at hver Vipp får en kjent effekt. Det er den typiske strategien i sensorløs planlegging: først en handling som tvinger verden inn i en kjent tilstand uansett hvor den startet, deretter handlinger med kjente effekter.

Kjente literaler etter hver handling
Etter	Kjente literaler i b	Fysiske tilstander
Start	ingen	4
Vipp(R1)	ingen	4
AltAv	¬Lys(R1), ¬Lys(R2)	1
Vipp(R1)	Lys(R1), ¬Lys(R2)	1
Vipp(R2)	Uthevet: Lys(R1), Lys(R2)	1

Vipp(r) har effektene when Lys(r): ¬Lys(r) og when ¬Lys(r): Lys(r). AltAv slår av alle lampene.

Laster interaktiv figur …

Figur 17.3Lysene i to rom uten sensorer. Den første Vipp(R1) gir ingenting fordi betingelsen er ukjent, mens AltAv gjør alt kjent.

RegneeksempelLampa i R1 er kjent av, og lampa i R2 er ukjent:

b_{0} = {\neg Lys(R1)}

. Virker planen [Vipp(R1), Vipp(R2)] for målet

Lys(R1) \land Lys(R2)

?Vis løsning

Steg 1. Vipp(R1): betingelsen $\neg Lys(R1)$ er kjent sann, så $b_{1} = {Lys(R1)}$ .

Steg 2. Vipp(R2): betingelsen for R2 er ukjent, så $Lys(R2)$ forblir ukjent, og $b_{2} = {Lys(R1)}$ .

Steg 3. $Lys(R2) \in / b_{2}$ , så planen er ingen løsning. $b_{0}$ har to fysiske tilstander, og planen svikter i den der lampa i R2 var på fra før.

Playground

En sensorløs plan for lysene i flere rom

Prøv: sett alt_av til 0 og se at hver Vipp etterlater en tom mengde kjente literaler, og at linja Planen virker i alle starttilstander blir nei.

antall_rom3alt_av1

Pythonkap17-sensorlos-kode.py

from itertools import product

antall_rom = 3  # @param 2..5
alt_av = 1  # @param 0..1

rom = [f"R{i}" for i in range(1, antall_rom + 1)]
plan = (["AltAv"] if alt_av else []) + [f"Vipp({r})" for r in rom]

def utfor(lyser, a):  # lyser = mengden rom der lampa er på
    if a == "AltAv":
        return frozenset()
    r = a[5:-1]  # Vipp(r) bytter lampa i r: betinget effekt
    return lyser - {r} if r in lyser else lyser | {r}

def kjente(b):  # literaler som er sanne i alle fysiske tilstander i b
    paa = [f"Lys({r})" for r in rom if all(r in s for s in b)]
    av = [f"¬Lys({r})" for r in rom if all(r not in s for s in b)]
    return "{" + ", ".join(paa + av) + "}"

# Oppfatningstilstanden som mengde av fysiske tilstander: alle 2^n i starten
b = {frozenset(r for r, p in zip(rom, bits) if p) for bits in product([0, 1], repeat=antall_rom)}
print(f"Fysiske tilstander i starten: {len(b)}")
for a in plan:
    b = {utfor(s, a) for s in b}
    print(f"Etter {a}: {kjente(b)}, fysiske tilstander = {len(b)}")
print(f"Planen virker i alle starttilstander: {'ja' if b == {frozenset(rom)} else 'nei'}")

from itertools import product

antall_rom = 3  # @param 2..5
alt_av = 1  # @param 0..1

rom = [f"R{i}" for i in range(1, antall_rom + 1)]
plan = (["AltAv"] if alt_av else []) + [f"Vipp({r})" for r in rom]

def utfor(lyser, a):  # lyser = mengden rom der lampa er på
    if a == "AltAv":
        return frozenset()
    r = a[5:-1]  # Vipp(r) bytter lampa i r: betinget effekt
    return lyser - {r} if r in lyser else lyser | {r}

def kjente(b):  # literaler som er sanne i alle fysiske tilstander i b
    paa = [f"Lys({r})" for r in rom if all(r in s for s in b)]
    av = [f"¬Lys({r})" for r in rom if all(r not in s for s in b)]
    return "{" + ", ".join(paa + av) + "}"

# Oppfatningstilstanden som mengde av fysiske tilstander: alle 2^n i starten
b = {frozenset(r for r, p in zip(rom, bits) if p) for bits in product([0, 1], repeat=antall_rom)}
print(f"Fysiske tilstander i starten: {len(b)}")
for a in plan:
    b = {utfor(s, a) for s in b}
    print(f"Etter {a}: {kjente(b)}, fysiske tilstander = {len(b)}")
print(f"Planen virker i alle starttilstander: {'ja' if b == {frozenset(rom)} else 'nei'}")

Ctrl/Cmd + Enter kjører

Øving 1 av 3Tallsvar

Huset har fire rom, R1 til R4, med én lampe hver. Agenten vet bare at lampa i R1 er av: $b_{0} = {\neg Lys(R1)}$ . Hvor mange fysiske tilstander inneholder $b_{0}$ ?

Øving 2 av 3Flervalg

Starttilstanden er ukjent, og agenten har ingen sensorer. Når er en plan en løsning?

Øving 3 av 3Liste

Hvilke literaler står i oppfatningstilstanden etter Vipp(R1)? Skriv dem adskilt med komma, i hvilken som helst rekkefølge.

b = {¬Lys(R1), Lys(R2)}
Vipp(r): when Lys(r): ¬Lys(r)
         when ¬Lys(r): Lys(r)

Steg 4 av 6

Betinget planlegging

Konsept

Har agenten sensorer, kan planen bruke det den ser. Ved betinget planlegging (contingent planning) forgrener planen seg på percepter: hvis jorda i bedet er tørr, vann; ellers gå videre. Planen er et tre, og under utførelsen følger agenten én gren, avhengig av hva den observerer. Det passer når miljøet er delvis observerbart eller ikke-deterministisk, men de mulige utfallene er kjent på forhånd.

Drivhusroboten har fått en fuktmåler og skal bare vanne bed som er tørre. Den starter ved kranen med full kanne.

Laster interaktiv figur …

Figur 17.4En betinget plan for drivhuset. Roboten starter ved kranen med full kanne og vanner bare de bedene som måles tørre.

Skrevet ut som tekst ser planen slik ut: [TilBed(B1), hvis $Tørr(B1)$ så [Vann(B1), TilKran(B1), Fyll, TilBed(B2)] ellers [TilKran(B1), TilBed(B2)], hvis $Tørr(B2)$ så [Vann(B2)]]. Målingen er en sensorhandling: den endrer ikke verden, men gjør en ukjent fluent kjent.

En betinget plan kan finnes med AND-OR-søk fra kapittel 5. OR-nodene er agentens valg av handling, og AND-nodene er de mulige perceptene: planen må ha en gren for hvert av dem. Søket regner med oppfatningstilstander, og et percept deler en oppfatningstilstand i én for hvert mulig utfall.

RegneeksempelFølg den betingede planen i figuren når B1 er fuktig og B2 er tørr. Hvor mange handlinger utføres?Vis løsning

Steg 1. TilBed(B1), så viser målingen at B1 er fuktig.

Steg 2. Grenen for fuktig: TilKran(B1) og TilBed(B2), så viser målingen at B2 er tørr.

Steg 3. Grenen for tørr: Vann(B2). Roboten utfører TilBed(B1), TilKran(B1), TilBed(B2) og Vann(B2), altså fire handlinger. Målingene regnes ikke som handlinger her.

Konsept

Noen ganger holder ikke en betinget plan, fordi agenten ikke kjenner alle utfall på forhånd eller verden endrer seg. Ved online planlegging (online planning) veves planlegging og utførelse sammen: agenten planlegger, handler, observerer og planlegger på nytt ved behov. Drivhusroboten vet for eksempel ikke på forhånd at kranen kan bli tett. Den lager en vanlig plan, setter i gang, og planlegger på nytt først når noe uventet skjer. Det er tema for neste steg.

Øving 1 av 3Flervalg

Vipp(r) har de betingede effektene $when Lys (r) : \neg Lys (r)$ og $when \neg Lys (r) : Lys (r)$ . Oppfatningstilstanden er $b = {Lys(R2)}$ , og ingenting er kjent om R1. Hva er $b$ etter Vipp(R1)?

Øving 2 av 3Flervalg

Hva kjennetegner en betinget plan?

Øving 3 av 3Flervalg

Hvordan henger betinget planlegging sammen med AND-OR-søk fra kapittel 5?

Steg 5 av 6

Overvåking og replanlegging

Konsept

Selv en god plan kan møte noe modellen ikke forutså. Med utførelsesovervåking (execution monitoring) sjekker agenten underveis om planen fortsatt virker, i tre styrker:

Ved handlingsovervåking (action monitoring) sjekker agenten før hver handling bare at forutsetningen for neste handling holder.
Ved planovervåking (plan monitoring) sjekker agenten før hver handling at hele resten av planen fortsatt virker.
Ved målovervåking (goal monitoring) ser agenten etter om et bedre mål har dukket opp.

Målovervåking sjekker ikke selve planen, men den kan spare mye arbeid: kommer det melding om regn mens roboten vanner, er målet om vannede bed ikke lenger verdt turene. Planovervåking bruker regresjon fra kapittel 16. Målet regresseres gjennom resten av planen, og tilstanden $s$ må oppfylle resultatet. Det er ƒkravet i planovervåking:

s ⊨ Regress (GOAL, [a_{i}, \dots, a_{n}])

Svikter sjekken, utløses replanlegging (replanning): agenten lager en ny plan fra tilstanden den faktisk er i. Ofte holder en kort reparasjon som fører tilbake til et punkt i den gamle planen, slik at resten kan brukes som den er. Hvis en handling kan svikte gang på gang, gir replanleggingen en løkke som prøver til den lykkes, og det virker så lenge feilene er tilfeldige. Er kranen helt ødelagt, hjelper ingen løkke, og agenten må finne en plan uten kranen eller gi opp målet.

ja, fortsett 1 Lag en plan fra tilstanden s 2 Utfør neste handling 3 Observer tilstanden s 4 Oppfyller s målet regressert gjennom resten? (ja, fortsett: tilbake til steg 2) nei : Replanlegg fra s ferdig : Planen er tom: mål nådd 1 Lag en plan fra tilstanden s 2 Utfør neste handling 3 Observer tilstanden s 4 Oppfyller s målet regressert gjennom resten? (ja, fortsett: tilbake til steg 2) nei : Replanlegg fra s ferdig : Planen er tom: mål nådd ja, fortsett

Laster interaktiv figur …

Figur 17.5Utførelse med planovervåking. Handlingsovervåking ville bare sjekket forutsetningen til neste handling i det siste steget.

Interaktiv figur

Drivhusroboten skal vanne tre bed. B1 er vannet, men så svikter kranen, og Fyll gir ikke vann.

Prøv: regresser målet gjennom resten av planen og se at det siste delmålet krever Full, som tilstanden mangler, selv om TilBed(B2) er anvendbar.

Trinn 1 av 4 · Finn relevanteFor $g_{0}$ er 3 handlinger relevante: Vann(B1), Vann(B2) og Vann(B3).

Handling1av 6Relevante3for g₀

Forklar hvert trinn

Vis utregning

g₁ = (g₀ − EFF) ∪ PRECOND = ({Vannet(B1), Vannet(B2), Vannet(B3)} − {Vannet(B3), ¬Full}) ∪ {Ved(B3), Full} = {Vannet(B1), Vannet(B2), Ved(B3), Full}
P = []
Relevant: en effekt står i g, og ingen effekt negerer en literal i g. g′ = (g − EFF) ∪ PRECOND.

Laster figur …

Figur 17.6Planovervåking etter at kranen sviktet. Init er tilstanden etter at Fyll sviktet, og planen er det som var igjen av den opprinnelige planen.

Interaktiv

Konsept

Handlingsovervåking ville latt roboten gå til B2, fordi TilBed(B2) er anvendbar, og først oppdaget feilen ved Vann(B2). Planovervåking ser feilen før roboten går. Den kan også utnytte flaks: har noe uventet gjort en senere del av planen mulig med en gang, kan agenten hoppe dit.

RegneeksempelPlanen er [Fyll, TilBed(B1), Vann(B1), TilKran(B1), Fyll, TilBed(B2), Vann(B2)], men en kollega har allerede fylt kanna:

s = {Ved(Kran), Full}

. Hva gjør planovervåking?Vis løsning

Steg 1. Hele planen krever ${Ved(Kran), \neg Full}$ , som er målet regressert gjennom alle sju handlingene. $s$ har $Full$ , så planen virker ikke fra starten: Fyll er ikke anvendbar.

Steg 2. Resten av planen etter den første Fyll krever ${Ved(Kran), Full}$ , og det holder i $s$ .

Steg 3. Agenten hopper over den første Fyll og fortsetter med TilBed(B1). Handlingsovervåking ville bare sett at Fyll ikke er anvendbar, og replanlagt.

Playground

Planovervåking når kranen kan svikte

Prøv: sett p_feil til 0 og se at Replanlegginger er 0 og Utførte handlinger er 11, og øk den så til 0.5: hver mislykket fylling koster én handling og én replanlegging.

p_feil0.30

Pythonkap17-replan-kode.py

import random

p_feil = 0.30  # @param 0.00..0.60 0.05
random.seed(4)

H = {"Fyll": ({"Ved(Kran)", "¬Full"}, {"Full"}, set())}  # navn -> (PRECOND, ADD, DEL)
for b in ["B1", "B2", "B3"]:
    H[f"TilBed({b})"] = ({"Ved(Kran)"}, {f"Ved({b})"}, {"Ved(Kran)"})
    H[f"TilKran({b})"] = ({f"Ved({b})"}, {"Ved(Kran)"}, {f"Ved({b})"})
    H[f"Vann({b})"] = ({f"Ved({b})", "Full"}, {f"Vannet({b})"}, {"Full"})
maal = {"Vannet(B1)", "Vannet(B2)", "Vannet(B3)"}
res = lambda s, a: frozenset((s - H[a][2]) | H[a][1])
ok = lambda s, a: all((l[1:] not in s) if l[0] == "¬" else (l in s) for l in H[a][0])

def planlegg(s):  # bredde-først progresjon: korteste plan fra s
    forelder, i = {s: []}, 0  # forelder er også køen: nøklene i innsettingsrekkefølge
    while not maal <= (s := list(forelder)[i]):
        forelder |= {res(s, a): forelder[s] + [a] for a in H if ok(s, a) and res(s, a) not in forelder}
        i += 1
    return forelder[s]

def utfor(s, plan):  # kjør resten av planen; en handling som ikke er anvendbar, stopper alt
    for a in plan:
        s = res(s, a) if ok(s, a) else frozenset()
    return s

s, plan, utfort, replan = frozenset({"Ved(Kran)"}), [], 0, 0
while not maal <= s and utfort < 60:
    if not maal <= utfor(s, plan):  # planovervåking: når resten av planen målet?
        plan, replan = planlegg(s), replan + (utfort > 0)
    a, plan, utfort = plan[0], plan[1:], utfort + 1
    s = res(s, a) if a != "Fyll" or random.random() >= p_feil else s  # kranen kan svikte
print(f"Utførte handlinger: {utfort}")
print(f"Replanlegginger: {replan}")
print(f"Mål nådd: {'ja' if maal <= s else 'nei, stoppet etter 60 handlinger'}")

import random

p_feil = 0.30  # @param 0.00..0.60 0.05
random.seed(4)

H = {"Fyll": ({"Ved(Kran)", "¬Full"}, {"Full"}, set())}  # navn -> (PRECOND, ADD, DEL)
for b in ["B1", "B2", "B3"]:
    H[f"TilBed({b})"] = ({"Ved(Kran)"}, {f"Ved({b})"}, {"Ved(Kran)"})
    H[f"TilKran({b})"] = ({f"Ved({b})"}, {"Ved(Kran)"}, {f"Ved({b})"})
    H[f"Vann({b})"] = ({f"Ved({b})", "Full"}, {f"Vannet({b})"}, {"Full"})
maal = {"Vannet(B1)", "Vannet(B2)", "Vannet(B3)"}
res = lambda s, a: frozenset((s - H[a][2]) | H[a][1])
ok = lambda s, a: all((l[1:] not in s) if l[0] == "¬" else (l in s) for l in H[a][0])

def planlegg(s):  # bredde-først progresjon: korteste plan fra s
    forelder, i = {s: []}, 0  # forelder er også køen: nøklene i innsettingsrekkefølge
    while not maal <= (s := list(forelder)[i]):
        forelder |= {res(s, a): forelder[s] + [a] for a in H if ok(s, a) and res(s, a) not in forelder}
        i += 1
    return forelder[s]

def utfor(s, plan):  # kjør resten av planen; en handling som ikke er anvendbar, stopper alt
    for a in plan:
        s = res(s, a) if ok(s, a) else frozenset()
    return s

s, plan, utfort, replan = frozenset({"Ved(Kran)"}), [], 0, 0
while not maal <= s and utfort < 60:
    if not maal <= utfor(s, plan):  # planovervåking: når resten av planen målet?
        plan, replan = planlegg(s), replan + (utfort > 0)
    a, plan, utfort = plan[0], plan[1:], utfort + 1
    s = res(s, a) if a != "Fyll" or random.random() >= p_feil else s  # kranen kan svikte
print(f"Utførte handlinger: {utfort}")
print(f"Replanlegginger: {replan}")
print(f"Mål nådd: {'ja' if maal <= s else 'nei, stoppet etter 60 handlinger'}")

Ctrl/Cmd + Enter kjører

Øving 1 av 2Flervalg

Roboten har nettopp utført Vann(B1), men kanna lakk, så B1 ble ikke vannet og kanna er tom. Resten av planen er [TilKran(B1), Fyll, TilBed(B2), Vann(B2)], og målet er $Vannet(B1) \land Vannet(B2)$ . Hva oppdager handlingsovervåking og planovervåking?

Øving 2 av 2Flervalg

Når utløser planovervåking replanlegging?

Steg 6 av 6

Eksamensfokus

Slik spørres det

Oppgavene om hierarkisk planlegging og usikkerhet er mest teori og flervalg. Typisk skal du forklare høynivåhandling, forfining og implementasjon med et eget eksempel, telle implementasjoner i et oppgitt hierarki, sammenligne sensorløs og betinget planlegging, og si hva handlings-, plan- og målovervåking sjekker. Svarmal for en implementasjon: forfin én høynivåhandling om gangen · skriv lista etter hvert steg · stopp når alt er primitivt. For oppfatningstilstander: list de kjente literalene etter hver handling, og si hvordan hver betinget effekt slo ut.

Vanlig felleEn forfining med en høynivåhandling er ikke en implementasjon

[Varm opp, Gjør rent] er en forfining av Klargjør hytta, men ingen implementasjon før begge høynivåhandlingene er forfinet ned til primitive handlinger.

Vanlig felleEn sensorløs plan testet fra én starttilstand

At planen virker når alle lampene er av fra starten, sier ingenting om de andre starttilstandene. En sensorløs plan må virke fra alle fysiske tilstander i oppfatningstilstanden.

Vanlig felleUkjent er ikke usant

I en oppfatningstilstand betyr en fluent som mangler, at agenten ikke vet. Lukket verden gjelder bare i klassisk planlegging. Den som leser en manglende $Lys(R2)$ som $\neg Lys(R2)$ , tror at Vipp(R2) slår lampa på.

Sjekk deg selvHva er forskjellen på sensorløs og betinget planlegging?Vis svar

Sensorløs planlegging har ingen percepter, så planen er én fast rekke handlinger som må virke i alle starttilstander. Betinget planlegging bruker percepter, og planen forgrener seg etter hva agenten observerer.

Sjekk deg selvHva sjekker planovervåking som handlingsovervåking ikke sjekker?Vis svar

At hele resten av planen fortsatt når målet, ikke bare at neste handling kan utføres. Den oppdager derfor feil som først ville stoppet planen senere, og feil som aldri stopper den, men gjør at målet ikke nås.

Øving 1 av 1Flervalg

En robot skal hente en pakke i et bygg der den kjenner kartet. Én dør på veien kan være låst eller ulåst, og roboten ser det først når den står foran døra. Hvilken planleggingsform passer best?

Mine notater

Skriv egne notater for dette kapittelet. De lagres automatisk og dukker opp i «Mine notater»-oversikten paa fag-siden.

Laster…

Test deg selv

Tar du quizen på kapittel 17?

14 spørsmål satt sammen til dette kapittelet — den beste måten å sjekke at det sitter.

Start quiz

Begreper & referanser

14 begreper · 4 formler · 3 referanser i kapittelet

Naturlig språkbehandling

Kap 18