Plánování: STRIPS, svět kostek, heuristiky z relaxace a plánování v AI agentech

Jazyk STRIPS a PDDL, dopředné a zpětné plánování, heuristiky hmax a hadd, Sussmanova anomálie, hierarchické plánování a přeplánování — od robota Shakeyho po AI agenty, kteří si píšou seznam úkolů.

14 minut Matěj Žalmánek 2026-10-15

Série Základy AI Díl 25 z 83

1. Mapa umělé inteligence: co je co a jak to do sebe zapadá
2. Stručná historie umělé inteligence: od Turinga po jazykové modely
3. Data, model, trénink, inference: základní pojmy na jednom příkladu
4. Jak číst matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relace: stavebnice, ze které se skládají definice v AI
6. Funkce a zobrazení: proč je každý model v AI funkce
7. Logika a důkazy: pravidla, podle kterých se v AI uvažuje
8. Grafy a stromy: struktura, na které stojí hledání i neuronové sítě
9. Lineární algebra pro strojové učení: vektory, matice a proč AI hlavně násobí
10. Derivace, gradient a řetízkové pravidlo: jak model zjistí, kterým směrem se učit
11. Gradientní sestup: jak se model učí
12. Co je pravděpodobnost: od hodu kostkou ke Kolmogorovovým axiomům
13. Podmíněná pravděpodobnost a Bayesova věta: jak změnit odhad, když se dozvíte něco nového
14. Náhodná veličina a distribuční funkce: jedna funkce, která o rozdělení řekne všechno
15. Funkce hustoty a pravděpodobnostní funkce: proč má spojitá veličina v bodě pravděpodobnost nula
16. Střední hodnota, rozptyl a kovariance: kde rozdělení leží, jak je široké a co s čím souvisí
17. Přehled pravděpodobnostních rozdělení: Bernoulli, binomické, Poisson, rovnoměrné, normální a exponenciální
18. Zákon velkých čísel a centrální limitní věta: proč se průměry chovají tak předvídatelně
19. Statistika a odhady parametrů: maximální věrohodnost, MAP a intervaly spolehlivosti
20. Teorie informace: entropie, křížová entropie a KL divergence — odkud se berou ztrátové funkce
21. Prohledávání stavového prostoru: BFS, DFS, UCS a A* s animacemi
22. Hry a protivník: minimax, alfa-beta ořezávání a Monte Carlo tree search
23. Splňování omezujících podmínek: backtracking, propagace omezení a AC-3 na sudoku a mapě krajů
24. Logika a znalostní systémy: dopředné a zpětné řetězení, rezoluce a expertní systémy
25. Plánování: STRIPS, svět kostek, heuristiky z relaxace a plánování v AI agentech
26. Lokální hledání a simulované žíhání: obchodní cestující přes krajská města
27. Genetické algoritmy: populace, křížení, mutace a výběr na batohu na výlet
28. Evoluční strategie a genetické programování: od pravidla jedné pětiny po Keplerův zákon
29. Optimalizace mravenčí kolonií: jak feromonová stopa najde krátkou cestu
30. Optimalizace hejnem částic: setrvačnost, vlastní zkušenost a zkušenost hejna
31. Neuroevoluce: evoluce vah i tvaru neuronových sítí a algoritmus NEAT
32. Fuzzy množiny a funkce příslušnosti: jak zapsat „trochu teplo“
33. Fuzzy logika a pravděpodobnost: proč „trochu teplo“ neznamená „pravděpodobně teplo“
34. Fuzzy logika: t-normy, implikace a pravidla KDYŽ–PAK
35. Fuzzy řízení: Mamdani a Sugeno od ventilátoru po kyvadlo na vozíku
36. Fuzzy shlukování: algoritmus fuzzy c-means a body mezi shluky
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidla, která se učí z dat
38. Markovovy řetězce: přechodová matice, stacionární rozdělení a PageRank
39. Skryté Markovovy modely: Viterbiho algoritmus a nepoctivé kasino
40. Bayesovské sítě: proč je tráva mokrá a co z toho plyne pro postřikovač
41. Kalmanův filtr: jak z nepřesných měření odhadnout, kde auto je a jak rychle jede
42. Druhy strojového učení: s učitelem, bez učitele, s částečným učitelem a další
43. Přeučení a regularizace: proč model, který zná data nazpaměť, selže
44. Vyhodnocení modelu: křížová validace, F1 a křivka ROC
45. Shlukování a snížení dimenze: k-means, PCA a t-SNE
46. Klasifikace a regrese: dvě úlohy učení s učitelem
47. Lineární regrese: nejmenší čtverce geometricky i maticově
48. Polynomiální a nelineární regrese: jak přímku ohnout
49. Logistická regrese: sigmoida, šance a křížová entropie
50. Vícetřídní klasifikace a softmax: od dvou tříd k mnoha
51. Naivní Bayesův klasifikátor: spamový filtr, který funguje lépe, než by měl
52. Ztrátové funkce: co přesně model minimalizuje
53. Rozhodovací stromy a k nejbližších sousedů: modely bez vzorců
54. Ansámbly: náhodný les a gradient boosting
55. SVM a jádrový trik: nejširší hranice a jak ji ohnout
56. Signál a vzorkování: proč platí Nyquistův teorém
57. Fourierova transformace: rozklad signálu na frekvence
58. Filtry a konvoluce: vyhlazení, hrany a odstranění šumu
59. Zvuk a řeč: spektrogram, melová škála a MFCC
60. Obraz jako signál: pixely, barvy, konvoluce a hrany
61. Perceptron a umělý neuron: nejjednodušší neuronová síť a co neumí
62. Neuronová síť od nuly: zpětné šíření chyby krok za krokem
63. Aktivace, inicializace a normalizace: drobnosti, na kterých hluboká síť stojí
64. Konvoluční sítě: jak síť poznává obrázky
65. Rekurentní sítě: paměť pro posloupnosti a mizející gradient
66. LSTM a GRU: brány, které rozhodují, co si síť zapamatuje
67. Autoenkodéry: síť, která se učí data stlačit a zase rozbalit
68. Embeddingy a word2vec: jak se slovo stane vektorem
69. Mechanismus pozornosti: jak se model naučí, kam se dívat
70. Transformery a velké jazykové modely: architektura krok za krokem
71. Tokenizace: jak se text rozseká na kousky pro model
72. Předtrénování a škálování: proč větší model a víc dat funguje
73. Doladění a RLHF: jak se z doplňovače textu stane asistent
74. Prompty, kontext a RAG: jak modelu dát správné informace
75. Variační autoenkodéry (VAE): nové obrázky ze spojitého latentního prostoru
76. Generativní adversariální sítě (GAN): padělatel proti detektivovi
77. Difúzní modely: jak se z čistého šumu stane obrázek
78. Markovovy rozhodovací procesy: stavy, akce, odměny a Bellmanovy rovnice
79. Q-learning a DQN: učení hodnoty akcí od tabulky po neuronovou síť
80. Policy gradient a PPO: učení přímo strategie
81. Jak funguje AI agent: jazykový model ve smyčce s nástroji
82. Programování s AI agenty: zadání, testy a kontrola
83. Vyhodnocení a bezpečnost AI systémů: jak měřit a jak hlídat

Celá osnova série 83 z 83 témat hotovo

Robot Shakey ze Stanfordského výzkumného institutu jezdil koncem šedesátých let po několika místnostech, posouval krabice a zhasínal světla. Byl to první robot, který o svých činech uvažoval: dostal cíl („dostaň krabici do vedlejší místnosti“) a sám si vymyslel, které akce a v jakém pořadí k němu vedou. Jazyk, ve kterém to dělal, se jmenuje STRIPS — a jeho myšlenky dnes najdete v logistice, v počítačových hrách i ve smyčce AI agenta, který vám píše kód.

Navazuje na díly Prohledávání stavového prostoru a Logika a znalostní systémy.

1. Plánování: hledání, které vidí dovnitř

Plánování je hledání posloupnosti akcí, která vede k cíli — přesně jako v dílu o prohledávání. Rozdíl je v tom, jak je úloha zapsaná. U bludiště byl stav černá skříňka a algoritmus o něm věděl jen to, kam z něj vedou akce. Plánovač vidí dovnitř: stav je seznam faktů o světě a akce říká, které fakty potřebuje a které změní. Díky tomu si plánovač umí sám odvodit odhad, jak daleko je cíl — žádnou heuristiku mu nemusíte psát ručně.

2. Jazyk STRIPS

Definice — plánovací úloha STRIPS

Nechť F je konečná množina atomů (výroků o světě). Stav je libovolná podmnožina s ⊆ F; atom p ∈ F ve stavu s platí, právě když p ∈ s (co v s není, neplatí).

Akce je trojice a = (pre(a), add(a), del(a)) podmnožin F: předpoklady, přidávané a odebírané atomy. Akce a je ve stavu s použitelná, právě když pre(a) ⊆ s, a pro takové s a a je výsledný stav

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

T(s, a)

stav po provedení akce — přechodová funkce, kterou v dílu o prohledávání dodával programátor; tady ji plánovač odvodí z popisu akce sám

s

výchozí stav: všechno, co akce nezmíní, se do nového stavu přenese beze změny (předpoklad STRIPS, který řeší problém rámce — nemusíme vypisovat, co se nemění)

del(a)

atomy, které akce zneplatní; odečítají se množinovým rozdílem ∖

add(a)

atomy, které akce zavede; přidávají se sjednocením až po odebrání, takže atom, který je v obou seznamech, nakonec platí

Plánovací úloha je čtveřice Π = (F, A, s₀, G), kde A je konečná množina akcí nad F, s₀ ⊆ F počáteční stav a G ⊆ F cíl. Stav s je cílový, právě když G ⊆ s.

Plán pro Π je posloupnost akcí a₁, …, a_k ∈ A (k ≥ 0) taková, že pro stavy s_i = T(s_i−1, a_i), i = 1, …, k, platí

1. pre(a_i) ⊆ s_i−1 pro každé i = 1, …, k (každá akce je použitelná ve stavu po předchozích);
2. G ⊆ s_k (poslední stav je cílový).

Číslo k je délka plánu; plán nejmenší délky je optimální. Slovy: plán je posloupnost akcí, kterou lze z počátečního stavu postupně provést a po které platí všechny cílové atomy.

Příklad — jedna akce krok za krokem

Kostka C leží na A, B stojí vedle. Akce na stůl(C, A) má pre = {na(C, A), volná(C)}, add = {stůl(C), volná(A)}, del = {na(C, A)} (celý popis akcí je v dalším oddílu; barvy podle vzorce pro T(s, a) výše).

s = {na(C, A), stůl(A), stůl(B), volná(B), volná(C)}

pre ⊆ s?   na(C, A) ∈ s, volná(C) ∈ s → akce je použitelná

s ∖ del = {stůl(A), stůl(B), volná(B), volná(C)}

T(s, a) = (s ∖ del) ∪ add = {stůl(A), stůl(B), stůl(C), volná(A), volná(B), volná(C)} — všechny tři kostky na stole

STRIPS vznikl v roce 1971 (Fikes a Nilsson) právě pro Shakeyho. Jeho dnešní nástupce je jazyk PDDL, ve kterém se od roku 1998 zadávají úlohy pro mezinárodní soutěže plánovačů. Akce se v něm píše jako schéma s proměnnými:

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

3. Svět kostek

Klasická zkušební úloha plánování: na stole leží kostky, některé na sobě. Jednou akcí vezmete kostku, na které nic neleží, a položíte ji na stůl nebo na jinou volnou kostku. Atomy jsou tři druhy: na(A, B) — A leží na B, stůl(A) a volná(A).

Akce ve světě kostek

Nechť K je konečná množina kostek. Atomy jsou F = {na(x, y) : x, y ∈ K, x ≠ y} ∪ {stůl(x), volná(x) : x ∈ K}. Pro každou volbu navzájem různých kostek A, B, C ∈ K jsou v úloze akce:

• na stůl(A, B): pre = {na(A, B), volná(A)}, add = {stůl(A), volná(B)}, del = {na(A, B)}
• ze stolu(A, C): pre = {stůl(A), volná(A), volná(C)}, add = {na(A, C)}, del = {stůl(A), volná(C)}
• přesun(A, B, C): pre = {na(A, B), volná(A), volná(C)}, add = {na(A, C), volná(B)}, del = {na(A, B), volná(C)}

Schéma s proměnnými plánovač nejdřív uzemní: dosadí za proměnné všechny kombinace kostek. Pro n kostek je n(n − 1) akcí „na stůl“, stejně „ze stolu“ a n(n − 1)(n − 2) přesunů, celkem n²(n − 1). Pro tři kostky je to 9 · 2 = 18 akcí, pro šest 36 · 5 = 180. V každém stavu je ale použitelných jen pár z nich — kostek, na kterých nic neleží, je málo.

Svět vypadá jako hračka, ale roste rychle. Tři kostky se dají rozestavit 13 způsoby, čtyři 73, pět 501 a šest už 4 051. Odkud ta čísla jsou:

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

n!

seřadíme všechny kostky do jedné řady — každé pořadí je kandidát; věže z něj dostaneme rozříznutím

C(n − 1, k − 1)

řadu rozřízneme na k neprázdných věží: vybereme k − 1 z n − 1 mezer mezi kostkami. Pořadí uvnitř věže záleží (A na B není B na A), proto řežeme pořadí, ne množinu

k!

na pořadí věží na stole nezáleží — dvě věže vedle sebe jsou týž stav, ať je vypíšeme v jakémkoli pořadí. Každý stav jsme tedy započítali k!-krát

Plánovač je spočítal jinak — prošel všechny dosažitelné stavy — a vyšlo mu totéž. Zkusíme dvě úlohy. V té větší stojí na stole dvě věže A–B–C a D–E–F (psáno odspodu) a cílem je jediná věž F–E–D–C–B–A:

4. Dopředné plánování

Definice — dopředné plánování (progrese)

Nechť Π = (F, A, s₀, G) je plánovací úloha STRIPS. Dopředné plánování řeší Π prohledáváním (do šířky, A* … — viz Prohledávání stavového prostoru) stavového prostoru, ve kterém

1. stavy jsou množiny s ⊆ F a počáteční stav je s₀;
2. následníci stavu s jsou Succ(s) = {T(s, a) : a ∈ A ∧ pre(a) ⊆ s}, každý přechod má cenu 1;
3. stav s je cílový, právě když G ⊆ s.

Nalezená cesta s₀ → … → s_k do cílového stavu dává plán: akce, které jednotlivé přechody způsobily, v pořadí od začátku. Protože stavů je nejvýš 2^|F|, prohledávání s kontrolou navštívených stavů 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šechny cílové atomy platí
            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 úloze s věží najde prohledávání do šířky nejkratší plán o 6 akcích, ale rozbalí přitom 2 132 stavů — víc než polovinu ze všech 4 051. Neví totiž nic o tom, kterým směrem cíl leží.

5. Heuristiky z relaxace

V dílu o prohledávání jsme si heuristiku pro bludiště vymysleli sami. Plánovač ji umí spočítat z popisu akcí — tak, že si úlohu zjednoduší, vyřeší ji a cenu zjednodušeného řešení použije jako odhad.

Definice — relaxace bez odebírání

Nechť Π = (F, A, s₀, G) je plánovací úloha STRIPS. Pro akci a položme a⁺ = (pre(a), add(a), ∅). Relaxovaná úloha (bez odebírání) je

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

V Π⁺ je T(s, a⁺) = s ∪ add(a) ⊇ s, takže atom, který jednou platí, platí navždy.

Nechť s ⊆ F je stav a ⊕ ∈ {max, ∑} zvolená agregace. Cenu množiny atomů P ⊆ F definujeme jako c(P) = max_{q ∈ P} c(q) pro ⊕ = max, resp. c(P) = ∑_{q ∈ P} c(q) pro ⊕ = ∑ (pro P = ∅ je obojí 0). Cena atomu c : F → ℕ ∪ {∞} ze stavu s je řešení soustavy

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

které získáme iterací: začneme s c(p) = 0 pro p ∈ s a c(p) = ∞ jinak a hodnoty podle pravé strany snižujeme, dokud se mění (kód níže). Heuristiky stavu s jsou

h_max(s) = max_{g ∈ G} c(g)   (s agregací max),   h_add(s) = ∑_{g ∈ G} c(g)   (s agregací ∑).

Slovy: c(p) odhaduje počet akcí potřebných k dosažení atomu p ve světě, kde se nic neodebírá. h_max je přípustná (věta níže), h_add je přesnější vodítko, ale může přecenit.

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

c(p)

odhad, kolik akcí je potřeba, aby začal platit atom p (pro atomy, které už platí, je 0)

min přes akce s p ∈ add(a)

atom může zavést víc akcí; vybereme tu nejlevnější, protože plánovač si cestu volí sám

1

cena akce samotné, která p nakonec přidá

c(pre(a))

cena toho, aby akce byla vůbec použitelná — splnit všechny její předpoklady. Tady se h_max a h_add liší: maximum předpokládá, že se předpoklady splní „zároveň“ a jejich přípravy se překrývají, součet, že každý stojí samostatnou práci

def ceny(stav, akce, agreguj):             # agreguj = max (hmax), nebo sum (hadd)
    c = {p: 0 for p in stav}
    zmena = True
    while zmena:                             # opakuj, dokud se nějaká 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 se ignoruje — relaxace
                    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)        # nedosažitelný cíl: h = ∞

Příklad — h_max a h_add pro Sussmanovu anomálii

Začátek: C leží na A, B stojí vedle; cíl G = {na(A, B), na(B, C)} (úlohu rozebereme níže). Ceny atomů po vrstvách:

cena 0 (platí): stůl(A), stůl(B), na(C, A), volná(B), volná(C)

cena 1: na stůl(C, A) → stůl(C), volná(A);   ze stolu(B, C) → na(B, C);   přesun(C, A, B) → na(C, B)

cena 2: ze stolu(A, B) potřebuje stůl(A), volná(A), volná(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 (barvy podle vzorce pro c(p) výše)

h_max(s₀) = max(2, 1) = 2,   h_add(s₀) = 2 + 1 = 3,   skutečně potřeba: h* = 3

h_max podcení, protože započítá jen nejdražší cíl: na(A, B) stojí dvě akce, ale na(B, C) potřebuje ještě vlastní třetí, a maximum ji spolkne. Součet ji započítá a tady trefí přesně. Na úloze s věží je to výraznější: ze startu je h* = 6, h_max = 3, počet nesplněných cílů 5 a h_add = 15 — součet započítá společnou přípravu (odkrytí kostek) u každého cíle znovu a skutečnou cenu přecení dva a půlkrát.

Věta — h_max a počet nesplněných cílů jsou přípustné

Nechť Π = (F, A, s₀, G) je plánovací úloha STRIPS a pro stav s ⊆ F je h*(s) délka nejkratšího plánu z s do cíle G (∞, neexistuje-li). Heuristika h je přípustná (jako v dílu o prohledávání), právě když h(s) ≤ h*(s) pro každý stav s.

Věta. (1) Pro každou úlohu STRIPS je h_max přípustná. (2) Nechť Π je úloha ve světě kostek, jejíž cíl obsahuje jen atomy tvaru na(x, y). Pak heuristika h_#(s) = |G ∖ s| (počet nesplněných cílů) je přípustná.

Důkaz (1). Je-li h*(s) = ∞, není co dokazovat. Jinak vezměme nejkratší plán a₁, …, a_k skutečné úlohy. Je to plán i pro relaxovanou úlohu (bez odebírání platí v každém kroku aspoň tytéž atomy, takže předpoklady zůstanou splněny). Indukcí podle i: každý atom, který platí po i akcích, má c_max ≤ i — buď platil už dřív, nebo ho přidala akce a_i, jejíž předpoklady platily po i − 1 akcích a mají tedy cenu ≤ i − 1, takže 1 + max ≤ i. Všechny cílové atomy platí po k akcích, proto h_max(s) = max_{g ∈ G} c(g) ≤ k = h*(s).

Důkaz (2). Cíle jsou atomy na(·, ·) a každá akce přidá nejvýš jeden takový atom. Na splnění m chybějících cílů je proto třeba aspoň m akcí.

Pro h_add důkaz selže v posledním kroku: součet cen může být větší než k, protože tytéž akce plánu se započítají u více cílů.

Tři heuristiky na úloze s věží, všechny s algoritmem A*:

Přípustná h_max najde optimum a ušetří přes 90 % práce. Počet nesplněných cílů je v našem světě také přípustný (každá akce položí jen jednu kostku, takže splní nejvýš jeden cíl) a tady funguje ještě lépe. h_add rozbalí nejméně, ale zaplatí za to: plán má o krok víc, než je nutné. Žádná heuristika nevyhrává vždycky — a skutečné plánovače jako FF nebo Fast Downward mají celé sady heuristik, které kombinují.

Jak A* s h_max pracuje, je nejlépe vidět na malé úloze — Sussmanově anomálii, kterou rozebereme o dva oddíly dál. Každý řádek je jeden rozbalený stav (věže odspodu); A* bere vždy stav s nejmenším f = g + h, kde g je počet akcí od začátku, a při shodě ten, který objevil dřív:

Hledání do šířky na téže úloze rozbalí všech 13 stavů, A* s h_max jen 5. Ve třetím kroku odbočí špatně — položí C na B — protože stav má f = 3 stejně jako správná cesta a byl objeven dřív. Hned další krok to napraví. První rozbalený cílový stav má nejkratší plán — to A* zaručuje, když je heuristika přípustná (a h_max je dokonce konzistentní, takže se k uzavřeným stavům nemusí vracet).

6. Zpětné plánování

Definice — zpětné plánování (regrese)

Nechť Π = (F, A, s₀, G) je plánovací úloha STRIPS. Podcíl je množina atomů g ⊆ F, které ještě musí platit. Akce a ∈ A je pro podcíl g relevantní, právě když

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

tj. akce zavede aspoň jeden atom podcíle a žádný nezničí. Regrese podcíle g přes relevantní akci a je podcíl

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

g′

co musí platit před akcí a, aby po ní platilo g — nový, dřívější podcíl

g

dosavadní podcíl; atomy, které akce nezmíní, musí platit už předtím, protože je akce sama nezavede (a díky podmínce relevance je ani nezničí)

add(a)

odečítáme, protože tyhle atomy zařídí akce sama — předtím platit nemusí

pre(a)

přidáváme, protože bez předpokladů akci nelze provést — stávají se novými podcíli

Zpětné plánování prohledává prostor podcílů, ve kterém

1. počáteční podcíl je g₀ = G;
2. následníci podcíle g jsou regrese g′ přes všechny akce a ∈ A relevantní pro g;
3. podcíl g je koncový, právě když g ⊆ s₀.

Najde-li cestu g₀ → g₁ → … → g_k ⊆ s₀ přes akce b₁, …, b_k, je plánem posloupnost b_k, …, b₁ — nalezené akce v obráceném pořadí.

Příklad — regrese cíle Sussmanovy anomálie

Cíl g = {na(A, B), na(B, C)}, začátek s₀ = {na(C, A), stůl(A), stůl(B), volná(B), volná(C)}. Akce bereme od poslední (barvy podle vzorce pro regresi výše):

ze stolu(A, B): add = {na(A, B)} zasahuje do g, del = {stůl(A), volná(B)} ne → relevantní

   g′ = {na(B, C)} ∪ {stůl(A), volná(A), volná(B)}

ze stolu(B, C): add = {na(B, C)}, del = {stůl(B), volná(C)} → relevantní

   g″ = {stůl(A), volná(A), volná(B)} ∪ {stůl(B), volná(B), volná(C)} = {stůl(A), stůl(B), volná(A), volná(B), volná(C)}

na stůl(C, A): add = {stůl(C), volná(A)}, del = {na(C, A)} → relevantní

   g‴ = {stůl(A), stůl(B), volná(B), volná(C)} ∪ {na(C, A), volná(C)} = {na(C, A), stůl(A), stůl(B), volná(B), volná(C)} ⊆ s₀ ✓

Plán čtený pozpátku: na stůl(C, A), ze stolu(B, C), ze stolu(A, B). Kdybychom ale jako poslední akci zkusili ze stolu(B, C), dostali bychom podcíl {na(A, B), stůl(B), volná(B), volná(C)} — A leží na B a B je zároveň volná. Takový stav neexistuje, ale regrese to sama nepozná; zpětné plánovače proto potřebují dodatečná pravidla, která nemožné kombinace odhalí.

7. Sussmanova anomálie

Nejjednodušší nápad, jak plánovat: rozdělit cíl na části a splnit je jednu po druhé. Funguje to často — a selže to už na třech kostkách. Úloha nese jméno Geralda Sussmana, který ji v sedmdesátých letech rozebral: C leží na A, B stojí vedle, cílem je A na B a zároveň B na C.

Nejkratší plán pro „A na B“ sundá C a položí A na B. Jenže pak je B pod A a dostat B na C znamená A zase sundat. Na konci platí jen druhý cíl a stálo to 4 kroky. Opačné pořadí dopadne stejně: položíme B na C, ale tím zasypeme A pod C a B — a uvolnit ho zase zničí první cíl. Cíle se navzájem ruší, ať začnete kterýmkoli.

Řešení potřebuje kroky obou cílů proložit: nejdřív uvolnit A (krok pro první cíl), pak B na C (druhý cíl), a teprve pak A na B (první cíl). Plánovač, který hledá v prostoru celých stavů, to najde sám — prošel tu všech 13 stavů světa tří kostek. Plánovač, který skládá dílčí plány, musí umět je rozplétat a znovu spojovat. To je téma celé rodiny „plánování v prostoru plánů“.

8. Hierarchické plánování

Definice — HTN

Uvádíme úplně uspořádanou variantu HTN, kterou používá plánovač SHOP2 i kód níže. Nechť F je konečná množina atomů a A konečná množina akcí STRIPS nad F. Úkoly jsou dvou druhů: primitivní — to jsou akce a ∈ A — a složené z konečné množiny U (U ∩ A = ∅).

Metoda pro složený úkol u ∈ U je dvojice m = (pre(m), (u₁, …, u_j)), kde pre(m) ⊆ F je podmínka a u₁, …, u_j ∈ A ∪ U (j ≥ 0) jsou podúkoly. Úloha HTN je (F, A, U, M, s₀, w₀), kde M je konečná množina metod, s₀ ⊆ F počáteční stav a w₀ počáteční posloupnost úkolů (obvykle jediný úkol nejvyšší úrovně).

Dvojici (stav s, posloupnost úkolů w = (t, w′)) zpracujeme takto:

1. je-li t primitivní a pre(t) ⊆ s, přejdeme na (T(s, t), w′) a t připíšeme na konec plánu;
2. je-li t složený a m ∈ M jeho metoda s pre(m) ⊆ s, přejdeme na (s, (u₁, …, u_j, w′)) — úkol t nahradíme podúkoly metody.

Řešení je plán (posloupnost primitivních akcí), který vznikne konečně mnoha takovými kroky z (s₀, w₀) až do prázdné posloupnosti úkolů. Slovy: plánování začíná úkolem nejvyšší úrovně a podle metod ho rozkládá, dokud nezbydou jen primitivní akce, které jdou provést.

def rozloz(ukoly, stav):                   # ukoly: seznam zbývajících úkolů
    if not ukoly:
        return []                            # vše rozloženo
    u, zbytek = ukoly[0], ukoly[1:]
    if u.primitivni:                         # obyčejná akce 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:                  # zkus recepty jeden po druhém
        if metoda.podminka <= stav:
            plan = rozloz(metoda.podukoly + zbytek, stav)
            if plan is not None:
                return plan
    return None                              # žádná metoda nevyšla — návrat zpět

Hledá se tu v prostoru rozkladů, ne stavů: větví se jen podle toho, kterou metodu pro složený úkol zvolit. Úkoly se rozkládají v pořadí, v jakém se budou provádět, takže plánovač vždy zná aktuální stav — stejně postupuje například plánovač SHOP2.

Hierarchické plánování se používá tam, kde mají odborníci osvědčené postupy: v logistice, při řízení výroby a hodně v počítačových hrách. Akční hra F.E.A.R. (2005) proslula vojáky, kteří si taktiku plánovali za běhu jazykem ve stylu STRIPS — a z téhož nápadu vycházejí plánovače v řadě dalších her.

9. Plánování v nejistém světě

STRIPS předpokládá, že svět je přesně takový, jak si myslíme, a akce dopadnou přesně podle popisu. Skutečný robot ale kostku upustí a skutečný server neodpoví. Nejčastější odpovědi na to jsou tři:

• Sledování a přeplánování. Po každé akci zkontroluj, jestli svět vypadá, jak plán čekal. Když ne, naplánuj znovu z toho, co je. Jednoduché a překvapivě účinné (smyčka je níže).
• Podmíněné plány mají větvení: „když se dveře otevřou, jdi dál, jinak použij druhý vchod“.
• Pravděpodobnostní plánování. Když má akce víc možných výsledků s danými pravděpodobnostmi, nehledáme posloupnost akcí, ale strategii pro každou situaci — Markovovy rozhodovací procesy mají v osnově vlastní díl.

def proved_s_dohledem(cil, akce, svet):
    plan = planuj(svet.pozoruj(), cil, akce)
    while plan:
        a = plan.pop(0)
        cekany = proved(svet.pozoruj(), a)   # co by mělo platit podle modelu
        svet.udelej(a)
        skutecny = svet.pozoruj()
        if cil <= skutecny:
            return True
        if skutecny != cekany:               # svět se zachoval jinak
            plan = planuj(skutecny, cil, akce)   # přeplánuj z toho, co je
    return cil <= svet.pozoruj()

Stačí přitom hlídat jen to, na čem zbytek plánu závisí: když se změní atom, který není předpokladem žádné další akce ani součástí cíle, plán platí dál. Tuhle úsporu zavedl už systém PLANEX, který prováděl plány Shakeyho (Fikes, Hart a Nilsson, 1972).

10. Plánování v AI agentech

Jazykový agent, který opravuje chybu v kódu, také plánuje: rozepíše si úkol do seznamu kroků, po každém kroku se podívá na výsledek (testy prošly? soubor existuje?) a podle toho plán upraví. Je to sledování a přeplánování, jen akce jsou příkazy v terminálu a předpoklady a účinky nejsou nikde formálně zapsané — model je odhaduje z textu.

Právě tady je slabina. Výzkum na úlohách ze světa kostek (například sada PlanBench) ukázal, že jazykové modely v klasickém plánování často chybují, a zvlášť když se kostky přejmenují na nesmyslná slova, takže model nemůže čerpat z naučených příkladů. Novější modely s delším uvažováním si vedou mnohem lépe, ale záruku správnosti nedávají. Osvědčuje se proto dělba práce: model úlohu přeloží do PDDL nebo navrhne plán a klasický plánovač či validátor ho zkontroluje — každý dělá to, co umí.

11. Shrnutí

• Plánování je hledání posloupnosti akcí k cíli; STRIPS popisuje stav jako množinu atomů a akci předpoklady, přidávanými a odebíranými atomy.
• Dopředné plánování je prohledávání stavů; zpětné regreduje cíl přes relevantní akce.
• Plánovač si heuristiku spočítá sám z relaxované úlohy bez odebírání: h_max je přípustná, h_add rychlejší, ale může vést k delšímu plánu.
• Sussmanova anomálie ukazuje, že dílčí cíle nejde vždy plnit jeden po druhém — kroky se musí proložit.
• Hierarchické plánování rozkládá úkoly podle osvědčených metod; v nejistém světě se plán sleduje a přeplánovává — přesně to dělají dnešní AI agenti.

Chcete si to osahat? Nechte AI agenta zapsat svět kostek v PDDL a pustit na něj volně dostupný plánovač Fast Downward — a pak zkuste, kolik kostek zvládne model sám bez něj.

Máte na to jiný názor? Napište na support@coden-app.com.