Klassisk planlegging

En drivhusrobot skal vanne to bed. Den kan gå mellom kranen og bedene, fylle kanna ved kranen og vanne bedet den står ved, og én fylling holder til ett bed. Oppgaven er å finne en rekke handlinger som gjør begge bedene vannet. Dette er klassisk planlegging (classical planning): å finne en handlingsrekke i et miljø som er fullt observerbart, deterministisk, statisk og diskret, med én agent.

Hvorfor ikke bare bruke søkealgoritmene fra kapittel 2 og 3? Det kan vi, men der var en tilstand en svart boks med et navn. Søket visste ikke hva tilstanden besto av, og heuristikken måtte lages for hånd for hvert nytt problem. En planlegger bruker en faktorisert representasjon: en tilstand er en samling fakta, som «roboten står ved kranen» og «kanna er full», og en handling beskrives ved hvilke fakta den krever og hvilke den endrer. Planleggeren kan dermed se inne i tilstandene. Den kan lage heuristikker som virker i alle domener, og én beskrivelse av en handling dekker mange tilstander.

Faktoriseringen er også kompakt. I stedet for å liste alle tilstandene beskriver vi dem med noen få fakta, mens antallet tilstander vokser eksponentielt med antallet fakta.

De fire antagelsene betyr noe konkret i drivhuset. Roboten vet hvor den står og om kanna er full (fullt observerbart). Vann(B1) vanner alltid bedet og tømmer alltid kanna (deterministisk). Ingenting skjer mens roboten tenker, for eksempel tørker ikke bedene ut igjen (statisk). Og det finnes et endelig antall tilstander og handlinger (diskret). Bryter en av antagelsene, trengs metodene i neste kapittel. En løsning er en plan: en rekke handlinger som fører fra starttilstanden til en tilstand der målet holder.

Planleggingsproblemer skrives i PDDL (Planning Domain Definition Language). En tilstand er en konjunksjon av grunne atomer uten variabler og funksjoner. Hvert slikt atom er en fluent, som $\text{Ved(Kran)}$ eller $\text{Full}$. Under lukket-verden-antagelsen (closed-world assumption) er alt som ikke står i tilstanden, usant. Starttilstanden Init er derfor bare positive atomer, og at kanna er tom, sier vi ved å utelate $\text{Full}$.

Handlingene skrives som et handlingsskjema (action schema) med variabler. Skjemaet har en forutsetning (precondition), som må holde for at handlingen kan utføres, og en effekt (effect), som sier hva den endrer. De positive literalene i effekten utgjør en add-liste (add list), og atomene i de negative literalene utgjør en sletteliste (delete list). I tabellen under er add-lista til TilBed(b) altså $\{\text{Ved}(b)\}$ og slettelista $\{\text{Ved(Kran)}\}$. Alt som ikke står i effekten, er som før. Den siste regelen er viktigere enn den ser ut. I ren førsteordens logikk måtte vi skrevet egne aksiomer for alt en handling ikke endrer, for eksempel at Vann(B1) ikke flytter roboten og ikke tørker ut B2. PDDL slipper det, fordi bare effekten endrer tilstanden. Tabellen viser hele drivhusdomenet.

$\text{Bed}(b)$ er et typepredikat. Det står i Init for hvert bed og i forutsetningene, slik at variabelen $b$ bare kan bindes til et bed. Uten det ville TilBed(Kran) også vært en lovlig handling. Et predikat skal ha samme antall argumenter overalt: Ved har ett argument i hele domenet. Negative literaler er lov i forutsetninger, som $\neg \text{Full}$ i Fyll, i effekter og i målet, men ikke i Init. Målet er en konjunksjon av literaler, og en tilstand oppfyller målet når hver av dem holder.

Når variablene byttes ut med konstanter, får vi grunne handlinger: TilBed(B1), TilBed(B2), Fyll, Vann(B1) og så videre. Med to bed gir de tre skjemaene med én variabel to grunne handlinger hver, og Fyll gir én, til sammen sju. Et skjema med to variabler over $n$ objekter gir opptil $n^2$ grunne handlinger, så antallet vokser fort. Typepredikatene er sanne i alle tilstander og kan tas ut av de grunne handlingene, og det gjør vi i figurene videre.

Den enkleste måten å finne en plan på er å søke forover fra Init. En anvendbar handling (applicable action) i tilstanden $s$ er en handling der hver positiv forutsetning står i $s$, og der ingen av atomene i de negative forutsetningene gjør det. Det er ƒbetingelsen for anvendbarhet:

Tilstanden etter handlingen regnes ut med ƒresultattilstanden ved progresjon: fjern slettelista, og legg til add-lista.

Søket kalles progresjon (progression, forward search), og det er et vanlig grafsøk i tilstandsrommet med denne etterfølgerfunksjonen. Alle algoritmene fra kapittel 2 og 3 kan brukes. Problemet er forgreningsfaktoren. I et lager med tusen varer og hundre hyller er nesten alle handlinger anvendbare, og de fleste har ingenting med målet å gjøre. Uten en god heuristikk drukner søket i dem. Med de domeneuavhengige heuristikkene i siste steg av kapitlet er progresjon likevel den vanligste metoden i moderne planleggere, fordi en tilstand er lett å sjekke og lett å lage heuristikker for.

Figuren spiller av en plan for drivhuset med to bed fra $\text{Init}=\{\text{Ved(Kran)}\}$.

Koden under finner en korteste plan med bredde-først-progresjon, for så mange bed du vil.

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 = 0
while 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}")

Progresjon prøver alt som er mulig. Med regresjon (regression, backward search) prøver søket bare det som hjelper. Det starter i målet og spør: hvilken handling kan ha vært den siste, og hva måtte holde før den? En relevant handling (relevant action) for delmålet $g$ har minst én effekt i $g$ og ingen effekt som negerer en literal i $g$. Det er ƒbetingelsen for relevans:

Her er $\text{EFF}(a)$ alle literalene $a$ gjør sanne, positive og negative, og $\bar{\ell }$ er komplementet til $\ell$. Delmålet før handlingen er ƒdelmålet ved regresjon:

Fjern alt handlingen ordner, og legg til det den krever. Søket stopper når Init oppfyller delmålet. Et delmål er ikke en tilstand. Det beskriver alle tilstandene der literalene holder, og det kan inneholde negative literaler, som $\neg \text{Full}$.

Regresjon kan også arbeide direkte med skjemaene, uten å gjøre alt grunt først. Står $\text{Vannet(B2)}$ i delmålet, er det bare skjemaet $\text{Vann}(b)$ med $b=\text{B2}$ som er aktuelt, og variabler som ikke trenger en verdi ennå, kan stå åpne. Det holder forgreningsfaktoren nede også når domenet har mange objekter.

Regresjon har ofte lavere forgreningsfaktor enn progresjon, fordi bare relevante handlinger vurderes. Til gjengjeld er det vanskeligere å lage gode heuristikker for delmål enn for tilstander, og derfor bruker mange planleggere likevel progresjon. Planen skrives i planrekkefølge, selv om den er funnet bakfra: den siste handlingen som regresseres, er den første som utføres.

Figuren regresserer målet for drivhuset med to bed gjennom den samme planen som i forrige steg.

Både progresjon og regresjon trenger en heuristikk, og her har planlegging en stor fordel. Fordi tilstandene er faktoriserte, kan heuristikken lages automatisk ved å relaksere problemet. Den optimale kostnaden i det relakserte problemet er admissibel, fordi hver løsning av det opprinnelige problemet også løser det relakserte. Det er ƒgrensen for relakserte heuristikker:

Den første relakseringen, ignorer-forutsetninger-heuristikken (ignore-preconditions heuristic), stryker alle forutsetninger og lar effektene stå. I drivhuset kan roboten da vanne et bed uten å stå ved det og uten vann i kanna. Fra $s_1=\{\text{Ved(Kran)}\}$ holder det med Vann(B1) og Vann(B2), så den relakserte kostnaden er 2, mens den sanne er 7. Her gir det samme tall som å telle mållitteralene som mangler, men det skyldes domenet: hver Vann(b) oppfyller nøyaktig ett mål, og ingen av dem river ned et annet mål. Eksempelet under viser hva som skjer når den første betingelsen faller bort.

Den andre betingelsen kan svikte motsatt vei. La roboten starte med full kanne, og la målet være at begge bed er vannet og at kanna er full igjen. Da mangler bare de to Vannet-literalene, men hver Vann(b) sletter $\text{Full}$, så Fyll må med til slutt også i det relakserte problemet, og kostnaden blir 3. Tellingen kan altså bomme begge veier, og når den bommer oppover, som med sprederne, er den ikke admissibel. Den relakserte kostnaden må derfor regnes ut, og det har sin pris. Tar vi i tillegg bort alle effekter som ikke står i målet, blir oppgaven å velge færrest mulig handlinger som til sammen dekker alle mållitteralene. Det er mengdedekning (set cover), og det er NP-hardt. En grådig metode som hver gang tar handlingen som dekker flest gjenværende mål, er rask, men kan ende med flere handlinger enn nødvendig. Da kan den overvurdere, og admissibiliteten er borte.

Den andre relakseringen, ignorer-slettelister-heuristikken (ignore-delete-lists heuristic), beholder forutsetningene, men stryker alle slettelister, og negative forutsetninger som $\neg \text{Full}$ i Fyll ses bort fra. Et atom som først er blitt sant, forblir sant. I drivhuset tømmes ikke kanna når roboten vanner, og $\text{Ved(Kran)}$ blir stående etter TilBed(B1). Fra $s_1$ er [Fyll, TilBed(B1), Vann(B1), TilBed(B2), Vann(B2)] nok, med kostnad 5 mot den sanne kostnaden 7. Siden tilstanden bare vokser, gjør søket monoton fremgang mot målet. Den korteste relakserte planen er likevel NP-hard å finne. I praksis lar planleggeren bakkeklatring finne en kort relaksert plan raskt og bruker lengden som anslag, men den planen er ikke nødvendigvis den korteste, så heller ikke dette anslaget er garantert admissibelt.