Plánovanie: STRIPS, svet kociek, heuristiky z relaxácie a plánovanie v AI agentoch

Jazyk STRIPS a PDDL, dopredné a spätné plánovanie, heuristiky hmax a hadd, Sussmanova anomália, hierarchické plánovanie a preplánovanie — od robota Shakeyho po AI agentov, ktorí si píšu zoznam úloh.

14 minút Matěj Žalmánek 2026-10-15

Séria Základy AI Diel 25 z 52

1. Mapa umelej inteligencie: čo je čo a ako to do seba zapadá
2. Stručná história umelej inteligencie: od Turinga po jazykové modely
3. Dáta, model, tréning, inferencia: základné pojmy na jednom príklade
4. Ako čítať matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relácie: stavebnica, z ktorej sa skladajú definície v AI
6. Funkcie a zobrazenia: prečo je každý model v AI funkcia
7. Logika a dôkazy: pravidlá, podľa ktorých sa v AI uvažuje
8. Grafy a stromy: štruktúra, na ktorej stojí hľadanie aj neurónové siete
9. Lineárna algebra pre strojové učenie: vektory, matice a prečo AI hlavne násobí
10. Derivácie, gradient a reťazové pravidlo: ako model zistí, ktorým smerom sa učiť
11. Gradientný zostup: ako sa model učí
12. Čo je pravdepodobnosť: od hodu kockou ku Kolmogorovovým axiómam
13. Podmienená pravdepodobnosť a Bayesova veta: ako zmeniť odhad, keď sa dozviete niečo nové
14. Náhodná premenná a distribučná funkcia: jedna funkcia, ktorá o rozdelení povie všetko
15. Funkcia hustoty a pravdepodobnostná funkcia: prečo má spojitá premenná v bode pravdepodobnosť nula
16. Stredná hodnota, rozptyl a kovariancia: kde rozdelenie leží, aké je široké a čo s čím súvisí
17. Prehľad pravdepodobnostných rozdelení: Bernoulliho, binomické, Poissonovo, rovnomerné, normálne a exponenciálne
18. Zákon veľkých čísel a centrálna limitná veta: prečo sa priemery správajú tak predvídateľne
19. Štatistika a odhady parametrov: maximálna vierohodnosť, MAP a intervaly spoľahlivosti
20. Teória informácie: entropia, krížová entropia a KL divergencia — odkiaľ sa berú stratové funkcie
21. Prehľadávanie stavového priestoru: BFS, DFS, UCS a A* s animáciami
22. Hry a protivník: minimax, alfa-beta orezávanie a Monte Carlo tree search
23. Splňovanie obmedzujúcich podmienok: backtracking, propagácia obmedzení a AC-3 na sudoku a mape krajov
24. Logika a znalostné systémy: dopredné a spätné reťazenie, rezolúcia a expertné systémy
25. Plánovanie: STRIPS, svet kociek, heuristiky z relaxácie a plánovanie v AI agentoch
26. Lokálne hľadanie a simulované žíhanie: obchodný cestujúci cez krajské mestá
27. Genetické algoritmy: populácia, kríženie, mutácia a výber na batohu na výlet
28. Evolučné stratégie a genetické programovanie: od pravidla jednej pätiny po Keplerov zákon
29. Optimalizácia mravčou kolóniou: ako feromónová stopa nájde krátku cestu
30. Optimalizácia rojom častíc: zotrvačnosť, vlastná skúsenosť a skúsenosť roja
31. Neuroevolúcia: evolúcia váh aj tvaru neurónových sietí a algoritmus NEAT
32. Fuzzy množiny a funkcie príslušnosti: ako zapísať „trochu teplo“
33. Fuzzy logika a pravdepodobnosť: prečo „trochu teplo“ neznamená „pravdepodobne teplo“
34. Fuzzy logika: t-normy, implikácie a pravidlá AK–TAK
35. Fuzzy riadenie: Mamdani a Sugeno od ventilátora po kyvadlo na vozíku
36. Fuzzy zhlukovanie: algoritmus fuzzy c-means a body medzi zhlukmi
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidlá, ktoré sa učia z dát
38. Markovove reťazce: prechodová matica, stacionárne rozdelenie a PageRank
39. Skryté Markovove modely: Viterbiho algoritmus a nepoctivé kasíno
40. Bayesovské siete: prečo je tráva mokrá a čo z toho vyplýva pre postrekovač
41. Kalmanov filter: ako z nepresných meraní odhadnúť, kde auto je a ako rýchlo ide
42. Druhy strojového učenia: s učiteľom, bez učiteľa, s čiastočným učiteľom a ďalšie
43. Prompty, kontext a RAG: ako modelu dať správne informácie
44. Variačné autoenkodéry (VAE): nové obrázky zo spojitého latentného priestoru
45. Generatívne adversariálne siete (GAN): falšovateľ proti detektívovi
46. Difúzne modely: ako sa z čistého šumu stane obrázok
47. Markovove rozhodovacie procesy: stavy, akcie, odmeny a Bellmanove rovnice
48. Q-learning a DQN: učenie hodnoty akcií od tabuľky po neurónovú sieť
49. Policy gradient a PPO: učenie priamo stratégie
50. Ako funguje AI agent: jazykový model v slučke s nástrojmi
51. Programovanie s AI agentmi: zadanie, testy a kontrola
52. Vyhodnocovanie a bezpečnosť AI systémov: ako merať a ako strážiť

Celá osnova série Hotovo: 52 z 83 tém

Robot Shakey zo Stanfordského výskumného inštitútu jazdil koncom šesťdesiatych rokov po niekoľkých miestnostiach, posúval škatule a zhasínal svetlá. Bol to prvý robot, ktorý o svojich činoch uvažoval: dostal cieľ („dostaň škatuľu do vedľajšej miestnosti“) a sám si vymyslel, ktoré akcie a v akom poradí k nemu vedú. Jazyk, v ktorom to robil, sa volá STRIPS — a jeho myšlienky dnes nájdete v logistike, v počítačových hrách aj v slučke AI agenta, ktorý vám píše kód.

Nadväzuje na diely Prehľadávanie stavového priestoru a Logika a znalostné systémy.

1. Plánovanie: hľadanie, ktoré vidí dovnútra

Plánovanie je hľadanie postupnosti akcií, ktorá vedie k cieľu — presne ako v diele o prehľadávaní. Rozdiel je v tom, ako je úloha zapísaná. Pri bludisku bol stav čierna skrinka a algoritmus o ňom vedel len to, kam z neho vedú akcie. Plánovač vidí dovnútra: stav je zoznam faktov o svete a akcia hovorí, ktoré fakty potrebuje a ktoré zmení. Vďaka tomu si plánovač vie sám odvodiť odhad, ako ďaleko je cieľ — žiadnu heuristiku mu nemusíte písať ručne.

2. Jazyk STRIPS

Definícia — plánovacia úloha STRIPS

Nech F je konečná množina atómov (výrokov o svete). Stav je ľubovoľná podmnožina s ⊆ F; atóm p ∈ F v stave s platí práve vtedy, keď p ∈ s (čo v s nie je, neplatí).

Akcia je trojica a = (pre(a), add(a), del(a)) podmnožín F: predpoklady, pridávané a odoberané atómy. Akcia a je v stave s použiteľná práve vtedy, keď pre(a) ⊆ s, a pre také s a a je výsledný stav

T(s, a) = (s ∖ del(a)) ∪ add(a)

T(s, a)

stav po vykonaní akcie — prechodová funkcia, ktorú v diele o prehľadávaní dodával programátor; tu ju plánovač odvodí z opisu akcie sám

s

východiskový stav: všetko, čo akcia nespomenie, sa do nového stavu prenesie bez zmeny (predpoklad STRIPS, ktorý rieši problém rámca — nemusíme vypisovať, čo sa nemení)

del(a)

atómy, ktoré akcia zneplatní; odčítajú sa množinovým rozdielom ∖

add(a)

atómy, ktoré akcia zavedie; pridávajú sa zjednotením až po odobratí, takže atóm, ktorý je v oboch zoznamoch, nakoniec platí

Plánovacia úloha je štvorica Π = (F, A, s₀, G), kde A je konečná množina akcií nad F, s₀ ⊆ F počiatočný stav a G ⊆ F cieľ. Stav s je cieľový práve vtedy, keď G ⊆ s.

Plán pre Π je postupnosť akcií a₁, …, a_k ∈ A (k ≥ 0) taká, že pre stavy s_i = T(s_i−1, a_i), i = 1, …, k, platí

1. pre(a_i) ⊆ s_i−1 pre každé i = 1, …, k (každá akcia je použiteľná v stave po predchádzajúcich);
2. G ⊆ s_k (posledný stav je cieľový).

Číslo k je dĺžka plánu; plán najmenšej dĺžky je optimálny. Slovami: plán je postupnosť akcií, ktorú možno z počiatočného stavu postupne vykonať a po ktorej platia všetky cieľové atómy.

Príklad — jedna akcia krok za krokom

Kocka C leží na A, B stojí vedľa. Akcia na stôl(C, A) má pre = {na(C, A), voľná(C)}, add = {stôl(C), voľná(A)}, del = {na(C, A)} (celý opis akcií je v ďalšom oddiele; farby podľa vzorca pre T(s, a) vyššie).

s = {na(C, A), stôl(A), stôl(B), voľná(B), voľná(C)}

pre ⊆ s?   na(C, A) ∈ s, voľná(C) ∈ s → akcia je použiteľná

s ∖ del = {stôl(A), stôl(B), voľná(B), voľná(C)}

T(s, a) = (s ∖ del) ∪ add = {stôl(A), stôl(B), stôl(C), voľná(A), voľná(B), voľná(C)} — všetky tri kocky na stole

STRIPS vznikol v roku 1971 (Fikes a Nilsson) práve pre Shakeyho. Jeho dnešný nástupca je jazyk PDDL, v ktorom sa od roku 1998 zadávajú úlohy pre medzinárodné súťaže plánovačov. Akcia sa v ňom píše ako schéma s premennými:

(:action na-stol
  :parameters (?a ?b)
  :precondition (and (na ?a ?b) (volna ?a))
  :effect (and (stol ?a) (volna ?b) (not (na ?a ?b))))

3. Svet kociek

Klasická skúšobná úloha plánovania: na stole ležia kocky, niektoré na sebe. Jednou akciou vezmete kocku, na ktorej nič neleží, a položíte ju na stôl alebo na inú voľnú kocku. Atómy sú troch druhov: na(A, B) — A leží na B, stôl(A) a voľná(A).

Akcie vo svete kociek

Nech K je konečná množina kociek. Atómy sú F = {na(x, y) : x, y ∈ K, x ≠ y} ∪ {stôl(x), voľná(x) : x ∈ K}. Pre každú voľbu navzájom rôznych kociek A, B, C ∈ K sú v úlohe akcie:

• na stôl(A, B): pre = {na(A, B), voľná(A)}, add = {stôl(A), voľná(B)}, del = {na(A, B)}
• zo stola(A, C): pre = {stôl(A), voľná(A), voľná(C)}, add = {na(A, C)}, del = {stôl(A), voľná(C)}
• presun(A, B, C): pre = {na(A, B), voľná(A), voľná(C)}, add = {na(A, C), voľná(B)}, del = {na(A, B), voľná(C)}

Schému s premennými plánovač najprv uzemní: dosadí za premenné všetky kombinácie kociek. Pre n kociek je n(n − 1) akcií „na stôl“, rovnako „zo stola“ a n(n − 1)(n − 2) presunov, spolu n²(n − 1). Pre tri kocky je to 9 · 2 = 18 akcií, pre šesť 36 · 5 = 180. V každom stave je však použiteľných len pár z nich — kociek, na ktorých nič neleží, je málo.

Svet vyzerá ako hračka, ale rastie rýchlo. Tri kocky sa dajú rozostaviť 13 spôsobmi, štyri 73, päť 501 a šesť už 4 051. Odkiaľ tie čísla sú:

počet stavov = ∑_k=1ⁿ n! · C(n − 1, k − 1)/k!

n!

zoradíme všetky kocky do jedného radu — každé poradie je kandidát; veže z neho dostaneme rozrezaním

C(n − 1, k − 1)

rad rozrežeme na k neprázdnych veží: vyberieme k − 1 z n − 1 medzier medzi kockami. Na poradí vnútri veže záleží (A na B nie je B na A), preto režeme poradie, nie množinu

k!

na poradí veží na stole nezáleží — dve veže vedľa seba sú ten istý stav, nech ich vypíšeme v akomkoľvek poradí. Každý stav sme teda započítali k!-krát

Plánovač ich spočítal inak — prešiel všetky dosiahnuteľné stavy — a vyšlo mu to isté. Skúsime dve úlohy. V tej väčšej stoja na stole dve veže A–B–C a D–E–F (písané odspodu) a cieľom je jediná veža F–E–D–C–B–A:

4. Dopredné plánovanie

Definícia — dopredné plánovanie (progresia)

Nech Π = (F, A, s₀, G) je plánovacia úloha STRIPS. Dopredné plánovanie rieši Π prehľadávaním (do šírky, A* … — pozri Prehľadávanie stavového priestoru) stavového priestoru, v ktorom

1. stavy sú množiny s ⊆ F a počiatočný stav je s₀;
2. nasledovníci stavu s sú Succ(s) = {T(s, a) : a ∈ A ∧ pre(a) ⊆ s}, každý prechod má cenu 1;
3. stav s je cieľový práve vtedy, keď G ⊆ s.

Nájdená cesta s₀ → … → s_k do cieľového stavu dáva plán: akcie, ktoré jednotlivé prechody spôsobili, v poradí od začiatku. Keďže stavov je najviac 2^|F|, prehľadávanie s kontrolou navštívených stavov vždy skončí.

from collections import deque

def proved(stav, akce):
    return (stav - akce.odeber) | akce.pridej

def planuj(start, cil, akce):
    okraj, rodic = deque([start]), {start: None}
    while okraj:
        stav = okraj.popleft()
        if cil <= stav:                      # všetky cieľové atómy platia
            return plan_z(rodic, stav)
        for a in akce:
            if a.predpoklady <= stav:
                dalsi = proved(stav, a)
                if dalsi not in rodic:
                    rodic[dalsi] = (stav, a)
                    okraj.append(dalsi)

Na úlohe s vežou nájde prehľadávanie do šírky najkratší plán so 6 akciami, ale rozbalí pritom 2 132 stavov — viac ako polovicu zo všetkých 4 051. Nevie totiž nič o tom, ktorým smerom cieľ leží.

5. Heuristiky z relaxácie

V diele o prehľadávaní sme si heuristiku pre bludisko vymysleli sami. Plánovač ju vie vypočítať z opisu akcií — tak, že si úlohu zjednoduší, vyrieši ju a cenu zjednodušeného riešenia použije ako odhad.

Definícia — relaxácia bez odoberania

Nech Π = (F, A, s₀, G) je plánovacia úloha STRIPS. Pre akciu a položme a⁺ = (pre(a), add(a), ∅). Relaxovaná úloha (bez odoberania) je

Π⁺ = (F, {a⁺ : a ∈ A}, s₀, G).

V Π⁺ je T(s, a⁺) = s ∪ add(a) ⊇ s, takže atóm, ktorý raz platí, platí navždy.

Nech s ⊆ F je stav a ⊕ ∈ {max, ∑} zvolená agregácia. Cenu množiny atómov P ⊆ F definujeme ako c(P) = max_{q ∈ P} c(q) pre ⊕ = max, resp. c(P) = ∑_{q ∈ P} c(q) pre ⊕ = ∑ (pre P = ∅ je oboje 0). Cena atómu c : F → ℕ ∪ {∞} zo stavu s je riešenie sústavy

1. c(p) = 0 pre p ∈ s;
2. c(p) = min_{a ∈ A : p ∈ add(a)} [1 + c(pre(a))] pre p ∉ s (minimum cez prázdnu množinu je ∞),

ktoré získame iteráciou: začneme s c(p) = 0 pre p ∈ s a c(p) = ∞ inak a hodnoty podľa pravej strany znižujeme, kým sa menia (kód nižšie). Heuristiky stavu s sú

h_max(s) = max_{g ∈ G} c(g)   (s agregáciou max),   h_add(s) = ∑_{g ∈ G} c(g)   (s agregáciou ∑).

Slovami: c(p) odhaduje počet akcií potrebných na dosiahnutie atómu p vo svete, kde sa nič neodoberá. h_max je prípustná (veta nižšie), h_add je presnejšie vodidlo, ale môže preceniť.

c(p) = min_{a : p ∈ add(a)} [ 1 + c(pre(a)) ]

c(p)

odhad, koľko akcií je potrebných, aby začal platiť atóm p (pre atómy, ktoré už platia, je 0)

minimum cez akcie s p ∈ add(a)

atóm môže zaviesť viac akcií; vyberieme tú najlacnejšiu, pretože plánovač si cestu volí sám

1

cena samotnej akcie, ktorá p nakoniec pridá

c(pre(a))

cena toho, aby akcia bola vôbec použiteľná — splniť všetky jej predpoklady. Tu sa h_max a h_add líšia: maximum predpokladá, že sa predpoklady splnia „naraz“ a ich prípravy sa prekrývajú, súčet, že každý stojí samostatnú prácu

def ceny(stav, akce, agreguj):             # agreguj = max (hmax) alebo sum (hadd)
    c = {p: 0 for p in stav}
    zmena = True
    while zmena:                             # opakuj, kým sa nejaká cena zlepší
        zmena = False
        for a in akce:
            if all(p in c for p in a.predpoklady):
                nova = 1 + agreguj(c[p] for p in a.predpoklady)
                for p in a.pridej:           # a.odeber sa ignoruje — relaxácia
                    if nova < c.get(p, float("inf")):
                        c[p], zmena = nova, True
    return c

def h(stav, cil, akce, agreguj):
    c = ceny(stav, akce, agreguj)
    return agreguj(c[g] for g in cil)        # nedosiahnuteľný cieľ: h = ∞

Príklad — h_max a h_add pre Sussmanovu anomáliu

Začiatok: C leží na A, B stojí vedľa; cieľ G = {na(A, B), na(B, C)} (úlohu rozoberieme nižšie). Ceny atómov po vrstvách:

cena 0 (platí): stôl(A), stôl(B), na(C, A), voľná(B), voľná(C)

cena 1: na stôl(C, A) → stôl(C), voľná(A);   zo stola(B, C) → na(B, C);   presun(C, A, B) → na(C, B)

cena 2: zo stola(A, B) potrebuje stôl(A), voľná(A), voľná(B) s cenami 0, 1, 0

   h_max: 1 + max(0, 1, 0) = 2,   h_add: 1 + (0 + 1 + 0) = 2 → na(A, B) má cenu 2 (farby podľa vzorca pre c(p) vyššie)

h_max(s₀) = max(2, 1) = 2,   h_add(s₀) = 2 + 1 = 3,   skutočne potrebné: h* = 3

h_max podcení, pretože započíta len najdrahší cieľ: na(A, B) stojí dve akcie, ale na(B, C) potrebuje ešte vlastnú tretiu, a maximum ju prehltne. Súčet ju započíta a tu trafí presne. Na úlohe s vežou je to výraznejšie: zo štartu je h* = 6, h_max = 3, počet nesplnených cieľov 5 a h_add = 15 — súčet započíta spoločnú prípravu (odkrytie kociek) pri každom cieli znova a skutočnú cenu precení dva a pol krát.

Veta — h_max a počet nesplnených cieľov sú prípustné

Nech Π = (F, A, s₀, G) je plánovacia úloha STRIPS a pre stav s ⊆ F je h*(s) dĺžka najkratšieho plánu zo s do cieľa G (∞, ak neexistuje). Heuristika h je prípustná (ako v diele o prehľadávaní) práve vtedy, keď h(s) ≤ h*(s) pre každý stav s.

Veta. (1) Pre každú úlohu STRIPS je h_max prípustná. (2) Nech Π je úloha vo svete kociek, ktorej cieľ obsahuje len atómy tvaru na(x, y). Potom heuristika h_#(s) = |G ∖ s| (počet nesplnených cieľov) je prípustná.

Dôkaz (1). Ak je h*(s) = ∞, nie je čo dokazovať. Inak vezmime najkratší plán a₁, …, a_k skutočnej úlohy. Je to plán aj pre relaxovanú úlohu (bez odoberania platia v každom kroku aspoň tie isté atómy, takže predpoklady zostanú splnené). Indukciou podľa i: každý atóm, ktorý platí po i akciách, má c_max ≤ i — buď platil už skôr, alebo ho pridala akcia a_i, ktorej predpoklady platili po i − 1 akciách a majú teda cenu ≤ i − 1, takže 1 + max ≤ i. Všetky cieľové atómy platia po k akciách, preto h_max(s) = max_{g ∈ G} c(g) ≤ k = h*(s).

Dôkaz (2). Ciele sú atómy na(·, ·) a každá akcia pridá najviac jeden taký atóm. Na splnenie m chýbajúcich cieľov je preto treba aspoň m akcií.

Pre h_add dôkaz zlyhá v poslednom kroku: súčet cien môže byť väčší ako k, pretože tie isté akcie plánu sa započítajú pri viacerých cieľoch.

Tri heuristiky na úlohe s vežou, všetky s algoritmom A*:

Prípustná h_max nájde optimum a ušetrí cez 90 % práce. Počet nesplnených cieľov je v našom svete tiež prípustný (každá akcia položí len jednu kocku, takže splní najviac jeden cieľ) a tu funguje ešte lepšie. h_add rozbalí najmenej, ale zaplatí za to: plán má o krok viac, než je nutné. Žiadna heuristika nevyhráva vždy — a skutočné plánovače ako FF alebo Fast Downward majú celé sady heuristík, ktoré kombinujú.

Ako A* s h_max pracuje, je najlepšie vidieť na malej úlohe — Sussmanovej anomálii, ktorú rozoberieme o dva oddiely ďalej. Každý riadok je jeden rozbalený stav (veže odspodu); A* berie vždy stav s najmenším f = g + h, kde g je počet akcií od začiatku, a pri zhode ten, ktorý objavil skôr:

Hľadanie do šírky na tej istej úlohe rozbalí všetkých 13 stavov, A* s h_max len 5. V treťom kroku odbočí zle — položí C na B — pretože stav má f = 3 rovnako ako správna cesta a bol objavený skôr. Hneď ďalší krok to napraví. Prvý rozbalený cieľový stav má najkratší plán — to A* zaručuje, keď je heuristika prípustná (a h_max je dokonca konzistentná, takže sa k uzavretým stavom nemusí vracať).

6. Spätné plánovanie

Definícia — spätné plánovanie (regresia)

Nech Π = (F, A, s₀, G) je plánovacia úloha STRIPS. Podcieľ je množina atómov g ⊆ F, ktoré ešte musia platiť. Akcia a ∈ A je pre podcieľ g relevantná práve vtedy, keď

add(a) ∩ g ≠ ∅   ∧   del(a) ∩ g = ∅,

t. j. akcia zavedie aspoň jeden atóm podcieľa a žiadny nezničí. Regresia podcieľa g cez relevantnú akciu a je podcieľ

g′ = (g ∖ add(a)) ∪ pre(a)

g′

čo musí platiť pred akciou a, aby po nej platilo g — nový, skorší podcieľ

g

doterajší podcieľ; atómy, ktoré akcia nespomenie, musia platiť už predtým, pretože ich akcia sama nezavedie (a vďaka podmienke relevancie ich ani nezničí)

add(a)

odčítame, pretože tieto atómy zariadi akcia sama — predtým platiť nemusia

pre(a)

pridávame, pretože bez predpokladov akciu nemožno vykonať — stávajú sa novými podcieľmi

Spätné plánovanie prehľadáva priestor podcieľov, v ktorom

1. počiatočný podcieľ je g₀ = G;
2. nasledovníci podcieľa g sú regresie g′ cez všetky akcie a ∈ A relevantné pre g;
3. podcieľ g je koncový práve vtedy, keď g ⊆ s₀.

Ak nájde cestu g₀ → g₁ → … → g_k ⊆ s₀ cez akcie b₁, …, b_k, je plánom postupnosť b_k, …, b₁ — nájdené akcie v obrátenom poradí.

Príklad — regresia cieľa Sussmanovej anomálie

Cieľ g = {na(A, B), na(B, C)}, začiatok s₀ = {na(C, A), stôl(A), stôl(B), voľná(B), voľná(C)}. Akcie berieme od poslednej (farby podľa vzorca pre regresiu vyššie):

zo stola(A, B): add = {na(A, B)} zasahuje do g, del = {stôl(A), voľná(B)} nie → relevantná

   g′ = {na(B, C)} ∪ {stôl(A), voľná(A), voľná(B)}

zo stola(B, C): add = {na(B, C)}, del = {stôl(B), voľná(C)} → relevantná

   g″ = {stôl(A), voľná(A), voľná(B)} ∪ {stôl(B), voľná(B), voľná(C)} = {stôl(A), stôl(B), voľná(A), voľná(B), voľná(C)}

na stôl(C, A): add = {stôl(C), voľná(A)}, del = {na(C, A)} → relevantná

   g‴ = {stôl(A), stôl(B), voľná(B), voľná(C)} ∪ {na(C, A), voľná(C)} = {na(C, A), stôl(A), stôl(B), voľná(B), voľná(C)} ⊆ s₀ ✓

Plán čítaný odzadu: na stôl(C, A), zo stola(B, C), zo stola(A, B). Keby sme však ako poslednú akciu skúsili zo stola(B, C), dostali by sme podcieľ {na(A, B), stôl(B), voľná(B), voľná(C)} — A leží na B a B je zároveň voľná. Taký stav neexistuje, ale regresia to sama nespozná; spätné plánovače preto potrebujú dodatočné pravidlá, ktoré nemožné kombinácie odhalia.

7. Sussmanova anomália

Najjednoduchší nápad, ako plánovať: rozdeliť cieľ na časti a splniť ich jednu po druhej. Funguje to často — a zlyhá to už na troch kockách. Úloha nesie meno Geralda Sussmana, ktorý ju v sedemdesiatych rokoch rozobral: C leží na A, B stojí vedľa, cieľom je A na B a zároveň B na C.

Najkratší plán pre „A na B“ zloží C a položí A na B. Lenže potom je B pod A a dostať B na C znamená A zase zložiť. Na konci platí len druhý cieľ a stálo to 4 kroky. Opačné poradie dopadne rovnako: položíme B na C, ale tým zasypeme A pod C a B — a uvoľniť ho zase zničí prvý cieľ. Ciele sa navzájom rušia, nech začnete ktorýmkoľvek.

Riešenie potrebuje kroky oboch cieľov preložiť: najprv uvoľniť A (krok pre prvý cieľ), potom B na C (druhý cieľ) a až potom A na B (prvý cieľ). Plánovač, ktorý hľadá v priestore celých stavov, to nájde sám — prešiel tu všetkých 13 stavov sveta troch kociek. Plánovač, ktorý skladá čiastkové plány, ich musí vedieť rozpletať a znova spájať. To je téma celej rodiny „plánovania v priestore plánov“.

8. Hierarchické plánovanie

Definícia — HTN

Uvádzame úplne usporiadanú variantu HTN, ktorú používa plánovač SHOP2 aj kód nižšie. Nech F je konečná množina atómov a A konečná množina akcií STRIPS nad F. Úlohy sú dvoch druhov: primitívne — to sú akcie a ∈ A — a zložené z konečnej množiny U (U ∩ A = ∅).

Metóda pre zloženú úlohu u ∈ U je dvojica m = (pre(m), (u₁, …, u_j)), kde pre(m) ⊆ F je podmienka a u₁, …, u_j ∈ A ∪ U (j ≥ 0) sú podúlohy. Úloha HTN je (F, A, U, M, s₀, w₀), kde M je konečná množina metód, s₀ ⊆ F počiatočný stav a w₀ počiatočná postupnosť úloh (zvyčajne jediná úloha najvyššej úrovne).

Dvojicu (stav s, postupnosť úloh w = (t, w′)) spracujeme takto:

1. ak je t primitívna a pre(t) ⊆ s, prejdeme na (T(s, t), w′) a t pripíšeme na koniec plánu;
2. ak je t zložená a m ∈ M jej metóda s pre(m) ⊆ s, prejdeme na (s, (u₁, …, u_j, w′)) — úlohu t nahradíme podúlohami metódy.

Riešenie je plán (postupnosť primitívnych akcií), ktorý vznikne konečne mnohými takými krokmi z (s₀, w₀) až do prázdnej postupnosti úloh. Slovami: plánovanie začína úlohou najvyššej úrovne a podľa metód ju rozkladá, kým nezostanú len primitívne akcie, ktoré sa dajú vykonať.

def rozloz(ukoly, stav):                   # ukoly: zoznam zostávajúcich úloh
    if not ukoly:
        return []                            # všetko rozložené
    u, zbytek = ukoly[0], ukoly[1:]
    if u.primitivni:                         # obyčajná akcia STRIPS
        if not u.predpoklady <= stav:
            return None
        plan = rozloz(zbytek, proved(stav, u))
        return None if plan is None else [u] + plan
    for metoda in u.metody:                  # skús recepty jeden po druhom
        if metoda.podminka <= stav:
            plan = rozloz(metoda.podukoly + zbytek, stav)
            if plan is not None:
                return plan
    return None                              # žiadna metóda nevyšla — návrat späť

Hľadá sa tu v priestore rozkladov, nie stavov: vetví sa len podľa toho, ktorú metódu pre zloženú úlohu zvoliť. Úlohy sa rozkladajú v poradí, v akom sa budú vykonávať, takže plánovač vždy pozná aktuálny stav — rovnako postupuje napríklad plánovač SHOP2.

Hierarchické plánovanie sa používa tam, kde majú odborníci osvedčené postupy: v logistike, pri riadení výroby a veľa v počítačových hrách. Akčná hra F.E.A.R. (2005) preslávila vojakov, ktorí si taktiku plánovali za behu jazykom v štýle STRIPS — a z toho istého nápadu vychádzajú plánovače v rade ďalších hier.

9. Plánovanie v neistom svete

STRIPS predpokladá, že svet je presne taký, ako si myslíme, a akcie dopadnú presne podľa opisu. Skutočný robot však kocku pustí a skutočný server neodpovie. Najčastejšie odpovede na to sú tri:

• Sledovanie a preplánovanie. Po každej akcii skontroluj, či svet vyzerá, ako plán čakal. Ak nie, naplánuj znova z toho, čo je. Jednoduché a prekvapivo účinné (slučka je nižšie).
• Podmienené plány majú vetvenie: „keď sa dvere otvoria, choď ďalej, inak použi druhý vchod“.
• Pravdepodobnostné plánovanie. Keď má akcia viac možných výsledkov s danými pravdepodobnosťami, nehľadáme postupnosť akcií, ale stratégiu pre každú situáciu — Markovove rozhodovacie procesy majú v osnove vlastný diel.

def proved_s_dohledem(cil, akce, svet):
    plan = planuj(svet.pozoruj(), cil, akce)
    while plan:
        a = plan.pop(0)
        cekany = proved(svet.pozoruj(), a)   # čo by malo platiť podľa modelu
        svet.udelej(a)
        skutecny = svet.pozoruj()
        if cil <= skutecny:
            return True
        if skutecny != cekany:               # svet sa zachoval inak
            plan = planuj(skutecny, cil, akce)   # preplánuj z toho, čo je
    return cil <= svet.pozoruj()

Stačí pritom strážiť len to, na čom zvyšok plánu závisí: keď sa zmení atóm, ktorý nie je predpokladom žiadnej ďalšej akcie ani súčasťou cieľa, plán platí ďalej. Túto úsporu zaviedol už systém PLANEX, ktorý vykonával plány Shakeyho (Fikes, Hart a Nilsson, 1972).

10. Plánovanie v AI agentoch

Jazykový agent, ktorý opravuje chybu v kóde, tiež plánuje: rozpíše si úlohu do zoznamu krokov, po každom kroku sa pozrie na výsledok (testy prešli? súbor existuje?) a podľa toho plán upraví. Je to sledovanie a preplánovanie, len akcie sú príkazy v termináli a predpoklady a účinky nie sú nikde formálne zapísané — model ich odhaduje z textu.

Práve tu je slabina. Výskum na úlohách zo sveta kociek (napríklad sada PlanBench) ukázal, že jazykové modely v klasickom plánovaní často chybujú, a zvlášť keď sa kocky premenujú na nezmyselné slová, takže model nemôže čerpať z naučených príkladov. Novšie modely s dlhším uvažovaním si vedú oveľa lepšie, ale záruku správnosti nedávajú. Osvedčuje sa preto deľba práce: model úlohu preloží do PDDL alebo navrhne plán a klasický plánovač či validátor ho skontroluje — každý robí to, čo vie.

11. Zhrnutie

• Plánovanie je hľadanie postupnosti akcií k cieľu; STRIPS opisuje stav ako množinu atómov a akciu predpokladmi, pridávanými a odoberanými atómami.
• Dopredné plánovanie je prehľadávanie stavov; spätné regreduje cieľ cez relevantné akcie.
• Plánovač si heuristiku vypočíta sám z relaxovanej úlohy bez odoberania: h_max je prípustná, h_add rýchlejšia, ale môže viesť k dlhšiemu plánu.
• Sussmanova anomália ukazuje, že čiastkové ciele nejde vždy plniť jeden po druhom — kroky sa musia preložiť.
• Hierarchické plánovanie rozkladá úlohy podľa osvedčených metód; v neistom svete sa plán sleduje a preplánováva — presne to robia dnešní AI agenti.

Chcete si to vyskúšať? Nechajte AI agenta zapísať svet kociek v PDDL a pustiť naň voľne dostupný plánovač Fast Downward — a potom skúste, koľko kociek zvládne model sám bez neho.

Máte na to iný názor? Napíšte na support@coden-app.com.