Søk under usikkerhet

I et deterministisk miljø gir hver handling én bestemt tilstand, $\text{Result}(s,a)$. En ikke-deterministisk handling (nondeterministic action) har i stedet en mengde mulige utfall, $\text{Results}(s,a)$, og agenten får først vite hvilket som skjedde etter at handlingen er utført. En drone i en smal korridor er et eksempel: «fly øst» fra rute 1 kan ende i rute 2, eller i rute 3 hvis et vindkast tar den.

Ikke-deterministisk er ikke det samme som stokastisk. En stokastisk modell gir hvert utfall en sannsynlighet. En ikke-deterministisk modell sier bare hvilke utfall som er mulige, og en løsning må derfor virke for alle.

En fast sekvens av handlinger holder ikke da, fordi neste handling avhenger av hva som skjedde. Løsningen er en betinget plan (conditional plan), der planen forgreiner seg på utfallet:

[Fly øst, if Rute = 2 then [Fly øst] else []]

Planen er et tre, ikke en liste. Les den slik: fly øst; havner dronen i rute 2, fly øst én gang til; havner den i rute 3, er den framme. Planen forutsetter at agenten ser hvor den havnet etter hver handling, altså at miljøet er fullt observerbart, selv om handlingene ikke er deterministiske. En betinget plan kalles også en strategi (strategy): den sier hva agenten skal gjøre i hver situasjon som kan oppstå, ikke bare i den som faktisk oppstår. Den kan bli stor, fordi hver forgreining multipliserer antall grener med antall utfall.

Betingede planer finnes ved å søke i et AND-OR-søketre (AND–OR search tree) med to slags noder. En OR-node er en tilstand der agenten velger handling, og det holder at én handling fører fram. En AND-node er en handling med flere mulige utfall, og da må hvert utfall ha en plan, fordi naturen velger. En løsning er et deltre der hvert blad er en måltilstand, hver OR-node har ett valgt barn og hver AND-node har alle barna med.

Søket går dybde først. En OR-node lykkes hvis ett barn lykkes, og en AND-node lykkes hvis alle barna gjør det. Dukker samme tilstand opp igjen på stien fra roten, gir grenen feil, slik at søket ikke går i ring. Det mister ingen løsninger: finnes det en plan uten løkker fra en gjentatt tilstand, finnes den også fra første gang tilstanden dukket opp. Resultatet av søket er selve planen, bygd opp nedenfra: hver OR-node legger til handlingen den valgte, og hver AND-node samler delplanene i en if–then–else.

Noen ganger kan en handling mislykkes og etterlate agenten der den var. Da finnes ingen plan uten løkke, men en syklisk plan (cyclic plan) kan prøve igjen: «så lenge dronen står i rute 2, fly øst». En syklisk plan er en løsning når hvert blad er et mål og målet kan nås fra hvert punkt i planen, så hver løkke kan forlates. Den bygger på at handlingen før eller siden lykkes.

Dronen under skal fra rute 1 til rute 3. Et vindkast kan ta den rett til målet, og motvind kan holde den igjen i rute 2.

Tenk deg nå at agenten ikke kan observere noe i det hele tatt. Det er et sensorløst problem (sensorless problem). Agenten vet ikke hvilken tilstand den er i, men den kan resonnere om mengden av tilstander den kan være i. Den mengden kalles en oppfatningstilstand (belief state), $b$.

Søket foregår da i rommet av oppfatningstilstander. En handling gir en ny oppfatningstilstand ved prediksjon (prediction), etter ƒprediksjonssteget:

Med $N$ fysiske tilstander finnes det opptil $2^N$ oppfatningstilstander (ƒantall oppfatningstilstander), men bare noen få av dem kan nås fra start. Målet er nådd når hver tilstand i $b$ er en måltilstand, fordi agenten ikke kan vite hvilken av dem den faktisk er i. Søket kan bruke de vanlige algoritmene fra kapittel 2 og 3, bare med oppfatningstilstander som noder. En plan som virker for $b$, virker for hver delmengde av $b$, og finnes ingen plan for en delmengde, finnes ingen for $b$. Søket kan derfor finne en plan for én tilstand og så sjekke at den virker for de andre. Det som gjør sensorløse planer mulige, er tvinging (coercion): en handling som skyver mot en vegg, samler mange mulige tilstander i én, uansett hvor agenten startet.

Roboten under står i en av de ti frie rutene uten å vite hvilken. Går den mot en vegg eller kanten, blir den stående.

Koden finner den korteste sensorløse planen med bredde-først-søk i rommet av oppfatningstilstander, for et drivhus med to bedrader og en vegg imellom som bare har én åpning.

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)], start
for 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)}")

De fleste agenter har noen sensorer. Et percept kan ikke fortelle nøyaktig hvor agenten er, men det stryker tilstandene der perceptet ville vært et annet. I rutenettene her er perceptet mengden retninger med vegg eller kant rett ved siden av agenten: {N, V} betyr vegg i nord og vest.

Hvert steg har tre deler. Først prediksjon med handlingen, som gir $b^{\prime }$. Så ser agenten hvilke percepter som er mulige i $b^{\prime }$. Til slutt kommer perceptet, og oppdatering (update) beholder bare tilstandene som passer, etter ƒoppdateringssteget:

Oppdateringen kan bare fjerne tilstander, aldri legge til nye. Rekkefølgen er viktig: perceptet beskriver stedet agenten står etter handlingen, så det må sammenlignes med rutene i $b^{\prime }$, ikke med rutene før handlingen. Like percepter i flere ruter er grunnen til at agenten trenger flere steg: symmetri i brettet gjør at to ruter kan se helt like ut, og først en handling som bryter symmetrien, skiller dem. Å holde $b$ oppdatert etter hver handling og hvert percept kalles tilstandsestimering (state estimation), og er det en robot gjør når den lokaliserer seg selv. Ved planlegging blir de mulige perceptene en AND-node: planen må virke for hvert percept som kan komme.

Roboten under har to vegger midt i brettet og vet ikke hvor den starter. Rad 0 er nederst.

I et online søk (online search) kjenner ikke agenten miljøet på forhånd. Den vet ikke hva en handling fører til før den har prøvd den, så den må veksle mellom å handle og å planlegge. Et vanlig offline-søk, som tenker gjennom hele planen før første trekk, går ikke an.

Det er farlig når handlinger ikke kan gjøres om. En blindvei (dead end) er en tilstand der målet ikke lenger kan nås, og ingen algoritme kan unngå blindveier i alle tilstandsrom: for hver algoritme finnes det et miljø som lurer den inn i en. Kvaliteten måles med konkurranseforhold (competitive ratio), altså ƒkonkurranseforholdet: faktisk kostnad delt på kostnaden agenten ville hatt om den kjente miljøet. Med blindveier kan forholdet bli uendelig. I miljøer der hver handling kan gjøres om, virker et online dybde-først-søk som går tilbake samme vei. At målet kan nås fra hver tilstand, er det LRTA* trenger.

LRTA* (learning real-time A*) lagrer et anslag $H(s)$ for hver tilstand den har besøkt, først lik $h(s)$. Etter hvert trekk oppdateres anslaget for tilstanden den forlot, med ƒLRTA*-oppdateringen:

En handling som ikke er prøvd ennå, anslås optimistisk med $h(s)$. Det drar agenten mot det ukjente, og over flere forsøk nærmer $H$ seg den sanne restkostnaden langs stien agenten bruker. Står agenten fast i en grop der $h$ er for lav, hever oppdateringene $H$ i gropa litt for hvert besøk, til en vei ut ser billigere ut. LRTA* er garantert å finne målet i et endelig miljø der målet kan nås fra hver tilstand, men den kan bruke mange trekk på det første forsøket.

Tabellen viser LRTA* i en korridor der anslaget først lokker agenten feil vei.