Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Klassisk planlegging, 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.
Å finne en rekke handlinger fra en kjent starttilstand til et mål i et miljø som er fullt observerbart, deterministisk, statisk og diskret, med én agent. Tilstander og handlinger beskrives faktorisert, med logiske atomer (classical planning).
Språket klassiske planleggingsproblemer skrives i: en starttilstand, et mål og handlingsskjemaer med forutsetninger og effekter (Planning Domain Definition Language).
Et grunt atom uten variabler og funksjoner, som eller . En tilstand er en konjunksjon av fluentene som er sanne (fluent).
Antagelsen om at en fluent som ikke står i tilstanden, er usann. Derfor består Init bare av positive grunne atomer (closed-world assumption).
En beskrivelse av en hel familie av handlinger med variabler: navn og argumenter, forutsetning og effekt. Når variablene byttes ut med konstanter, får vi grunne handlinger (action schema).
Konjunksjonen av literaler som må holde i tilstanden for at handlingen skal kunne utføres. Negative literaler er lov, som (precondition).
Konjunksjonen av literaler som sier hva handlingen endrer: positive literaler blir sanne, negative blir usanne, og alt annet er som før (effect).
Atomene i de positive literalene i effekten, : det handlingen gjør sant (add list).
Atomene i de negative literalene i effekten, : det handlingen gjør usant (delete list).
En handling er anvendbar i en tilstand når hver positiv forutsetning står i tilstanden og ingen av atomene i de negative forutsetningene gjør det (applicable action).
Fremoversøk i tilstandsrommet: start i Init, bruk anvendbare handlinger og regn ut neste tilstand med , til målet holder (progression, forward search).
Bakoversøk fra målet: velg en relevant handling og regn ut delmålet som må holde før den, til starttilstanden oppfyller delmålet (regression, backward search).
En handling er relevant for et delmål når minst én av effektene står i delmålet og ingen effekt negerer en literal i det (relevant action).
En relaksering der alle forutsetninger fjernes, så hver handling kan brukes i alle tilstander. Den optimale kostnaden i det relakserte problemet er en admissibel heuristikk (ignore-preconditions heuristic).
En relaksering der alle slettelister fjernes, så ingen handling kan gjøre noe usant. Den optimale kostnaden i det relakserte problemet er admissibel, men NP-hard å finne (ignore-delete-lists heuristic).
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Resultattilstanden ved progresjon
Brukes for hver handling i fremoversøk, etter at du har sjekket at handlingen er anvendbar. Fjern først slettelista, legg så til add-lista. Vanlig feil: å glemme å fjerne slettelista, slik at roboten står to steder samtidig.
Betingelsen for anvendbarhet
Sjekkes før en handling brukes i progresjon. De positive forutsetningene må stå i tilstanden, og atomene i de negative må mangle. Vanlig feil: å overse en negativ forutsetning, som i Fyll.
Delmålet ved regresjon
Brukes bare for relevante handlinger. er alle literalene gjør sanne, både positive og negative, så en negativ målliteral som fjernes av en handling som sletter Full. Vanlig feil: å bare fjerne add-lista.
Betingelsen for relevans
Sjekkes før en handling regresseres: minst én effekt må bidra til delmålet, og ingen effekt kan ødelegge en literal i det. Vanlig feil: å regressere over en handling som oppfyller én målliteral, men sletter en annen.
Grensen for relakserte heuristikker
Den optimale kostnaden i et relaksert problem er aldri større enn den sanne kostnaden, fordi hver plan for det opprinnelige problemet også løser det relakserte. Bare den optimale kostnaden er garantert admissibel; grådig set cover, bakkeklatring på ignorer-slettelister og antall uoppfylte mål er det ikke.
Kodesnutter
Kodesnutter fra kapittelet, vist literal.
Progresjon med bredde-først-søk i drivhuset
from collections import deque antall_bed = 3 # @param 1..4 bed = [f"B{i}" for i in range(1, antall_bed + 1)]# Grunne handlinger: navn -> (positive forutsetninger, negative forutsetninger, ADD, DEL)handlinger = {"Fyll": ({"Ved(Kran)"}, {"Full"}, {"Full"}, set())}for b in bed: handlinger[f"TilBed({b})"] = ({"Ved(Kran)"}, set(), {f"Ved({b})"}, {"Ved(Kran)"}) handlinger[f"TilKran({b})"] = ({f"Ved({b})"}, set(), {"Ved(Kran)"}, {f"Ved({b})"}) handlinger[f"Vann({b})"] = ({f"Ved({b})", "Full"}, set(), {f"Vannet({b})"}, {"Full"})init = frozenset({"Ved(Kran)"})maal = {f"Vannet({b})" for b in bed} # Progresjon med bredde-først-søk: Result(s, a) = (s - DEL(a)) | ADD(a)forelder = {init: None}ko = deque([init])utforsket = 0while ko: s = ko.popleft() utforsket += 1 if maal <= s: break for navn, (pos, neg, add, dele) in handlinger.items(): if pos <= s and not (neg & s): # anvendbar i s t = frozenset((s - dele) | add) if t not in forelder: forelder[t] = (s, navn) ko.append(t) plan = []while forelder[s] is not None: s, navn = forelder[s] plan.insert(0, navn)print(f"Plan: {', '.join(plan)}")print(f"Planlengde: {len(plan)}")print(f"Tilstander utforsket: {utforsket}")Prøv: sett antall_bed til 4 og se at linja Planlengde: øker med 4 for hvert nye bed, mens Tilstander utforsket: går fra 57 til 151.
Regresjon med bredde-først-søk fra målet
from collections import deque antall_maal = 2 # @param 1..3 # Grunne handlinger: navn -> (PRECOND, EFF), der ¬ markerer en negativ literalH = {"Fyll": ({"Ved(Kran)", "¬Full"}, {"Full"})}for b in ["B1", "B2"]: 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"})init = {"Ved(Kran)", "Full"}maal = frozenset(["Vannet(B1)", "Vannet(B2)", "Ved(Kran)"][:antall_maal]) neg = lambda l: l[1:] if l[0] == "¬" else "¬" + lholder = lambda g: all((neg(l) not in init) if l[0] == "¬" else (l in init) for l in g)vis = lambda g: "{" + ", ".join(sorted(g)) + "}" # Bredde-først regresjon: relevant a gir g' = (g - EFF(a)) | PRECOND(a)forrige, ko, g = {maal: None}, deque([maal]), maalwhile not holder(g): for navn, (pre, eff) in H.items(): if eff & g and not {neg(l) for l in eff} & g: g2 = frozenset((g - eff) | pre) if g2 not in forrige and not any(neg(l) in g2 for l in g2): forrige[g2] = (g, navn) ko.append(g2) g = ko.popleft() steg = []while forrige[g] is not None: steg.insert(0, (forrige[g][0], forrige[g][1], g)) g = forrige[g][0]for k, (foer, navn, etter) in enumerate(steg, 1): print(f"Steg {k}: {vis(foer)} gjennom {navn} gir {vis(etter)}")print(f"Starttilstanden oppfyller målet: ja, etter {len(steg)} steg")Prøv: sett antall_maal til 3 og se at første steg nå regresserer gjennom TilKran(B1), fordi Ved(Kran) må bli sant til slutt, og at linja Starttilstanden oppfyller målet: sier 7 steg.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Formaliser et planleggingsproblem i PDDL med Init, Goal og handlingsskjemaer med forutsetning og effekt
- 02Avgjør om en handling er anvendbar, og regn ut
- 03Avgjør om en handling er relevant, og regresser et delmål med
- 04Finn en plan med progresjon, og skriv den som
- 05Sammenlign progresjon og regresjon med hensyn på forgreningsfaktor og heuristikker
- 06Forklar hvorfor den optimale kostnaden i et relaksert problem er admissibel, mens grådige tilnærminger ikke er det