Begreper & referanser

1forfininger = 2  # @param 1..42nivaaer = 3  # @param 1..43k = 2  # steg i hver forfining4b = 6  # handlinger per tilstand i et primitivt søk5 6d = k ** nivaaer  # primitive handlinger i en ferdig plan7indre = (d - 1) // (k - 1)  # høynivåhandlinger som forfines (indre noder i treet)8tall = lambda x: f"{x:,}".replace(",", " ")9print(f"HLA-er som forfines: {indre}")10print(f"Primitive handlinger per implementasjon: {d}")11print(f"Antall implementasjoner: {tall(forfininger ** indre)}")12print(f"Planer i primitivt søk med b = {b}: {tall(b ** d)}")

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.

1from itertools import product2 3antall_rom = 3  # @param 2..54alt_av = 1  # @param 0..15 6rom = [f"R{i}" for i in range(1, antall_rom + 1)]7plan = (["AltAv"] if alt_av else []) + [f"Vipp({r})" for r in rom]8 9def utfor(lyser, a):  # lyser = mengden rom der lampa er på10    if a == "AltAv":11        return frozenset()12    r = a[5:-1]  # Vipp(r) bytter lampa i r: betinget effekt13    return lyser - {r} if r in lyser else lyser | {r}14 15def kjente(b):  # literaler som er sanne i alle fysiske tilstander i b16    paa = [f"Lys({r})" for r in rom if all(r in s for s in b)]17    av = [f"¬Lys({r})" for r in rom if all(r not in s for s in b)]18    return "{" + ", ".join(paa + av) + "}"19 20# Oppfatningstilstanden som mengde av fysiske tilstander: alle 2^n i starten21b = {frozenset(r for r, p in zip(rom, bits) if p) for bits in product([0, 1], repeat=antall_rom)}22print(f"Fysiske tilstander i starten: {len(b)}")23for a in plan:24    b = {utfor(s, a) for s in b}25    print(f"Etter {a}: {kjente(b)}, fysiske tilstander = {len(b)}")26print(f"Planen virker i alle starttilstander: {'ja' if b == {frozenset(rom)} else 'nei'}")

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.

1import random2 3p_feil = 0.30  # @param 0.00..0.60 0.054random.seed(4)5 6H = {"Fyll": ({"Ved(Kran)", "¬Full"}, {"Full"}, set())}  # navn -> (PRECOND, ADD, DEL)7for b in ["B1", "B2", "B3"]:8    H[f"TilBed({b})"] = ({"Ved(Kran)"}, {f"Ved({b})"}, {"Ved(Kran)"})9    H[f"TilKran({b})"] = ({f"Ved({b})"}, {"Ved(Kran)"}, {f"Ved({b})"})10    H[f"Vann({b})"] = ({f"Ved({b})", "Full"}, {f"Vannet({b})"}, {"Full"})11maal = {"Vannet(B1)", "Vannet(B2)", "Vannet(B3)"}12res = lambda s, a: frozenset((s - H[a][2]) | H[a][1])13ok = lambda s, a: all((l[1:] not in s) if l[0] == "¬" else (l in s) for l in H[a][0])14 15def planlegg(s):  # bredde-først progresjon: korteste plan fra s16    forelder, i = {s: []}, 0  # forelder er også køen: nøklene i innsettingsrekkefølge17    while not maal <= (s := list(forelder)[i]):18        forelder |= {res(s, a): forelder[s] + [a] for a in H if ok(s, a) and res(s, a) not in forelder}19        i += 120    return forelder[s]21 22def utfor(s, plan):  # kjør resten av planen; en handling som ikke er anvendbar, stopper alt23    for a in plan:24        s = res(s, a) if ok(s, a) else frozenset()25    return s26 27s, plan, utfort, replan = frozenset({"Ved(Kran)"}), [], 0, 028while not maal <= s and utfort < 60:29    if not maal <= utfor(s, plan):  # planovervåking: når resten av planen målet?30        plan, replan = planlegg(s), replan + (utfort > 0)31    a, plan, utfort = plan[0], plan[1:], utfort + 132    s = res(s, a) if a != "Fyll" or random.random() >= p_feil else s  # kranen kan svikte33print(f"Utførte handlinger: {utfort}")34print(f"Replanlegginger: {replan}")35print(f"Mål nådd: {'ja' if maal <= s else 'nei, stoppet etter 60 handlinger'}")

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.