Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI

Język STRIPS i PDDL, planowanie w przód i wstecz, heurystyki hmax i hadd, anomalia Sussmana, planowanie hierarchiczne i ponowne planowanie — od robota Shakeya po agentów AI, którzy piszą sobie listę zadań.

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

Seria Podstawy AI Część 25 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

Robot Shakey ze Stanford Research Institute jeździł pod koniec lat sześćdziesiątych po kilku pomieszczeniach, przesuwał pudła i gasił światła. Był pierwszym robotem, który rozumował o własnych działaniach: dostawał cel („przenieś pudło do sąsiedniego pokoju”) i sam wymyślał, które akcje i w jakiej kolejności do niego prowadzą. Język, w którym to robił, nazywa się STRIPS — a jego idee znajdziesz dziś w logistyce, w grach komputerowych i w pętli agenta AI, który pisze dla ciebie kod.

Nawiązuje do części Przeszukiwanie przestrzeni stanów i Logika i systemy z bazą wiedzy.

1. Planowanie: przeszukiwanie, które widzi do środka

Planowanie to szukanie ciągu akcji prowadzącego do celu — dokładnie jak w części o przeszukiwaniu. Różnica tkwi w tym, jak zadanie jest zapisane. W labiryncie stan był czarną skrzynką, a algorytm wiedział o nim tylko tyle, dokąd prowadzą z niego akcje. Planer widzi do środka: stan to lista faktów o świecie, a akcja mówi, których faktów potrzebuje i które zmienia. Dzięki temu planer potrafi sam wyprowadzić oszacowanie, jak daleko jest cel — nie musisz pisać mu żadnej heurystyki ręcznie.

2. Język STRIPS

Definicja — zadanie planowania STRIPS

Dany jest skończony zbiór atomów F (zdań o świecie). Stan to podzbiór s ⊆ F — atomy, które w nim zachodzą; czego nie ma w s, to nie zachodzi.

Akcja a to trójka (pre(a), add(a), del(a)) podzbiorów F: warunki wstępne, atomy dodawane i usuwane. Akcja jest wykonalna w s, gdy pre(a) ⊆ s, a stan wynikowy to

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

T(s, a)

stan po wykonaniu akcji — funkcja przejścia, którą w części o przeszukiwaniu dostarczał programista; tutaj planer wyprowadza ją sam z opisu akcji

s

stan wyjściowy: wszystko, czego akcja nie wspomina, przechodzi do nowego stanu bez zmian (założenie STRIPS, które rozwiązuje problem ramy — nie trzeba wypisywać, co się nie zmienia)

del(a)

atomy, które akcja unieważnia; odejmuje się je różnicą zbiorów ∖

add(a)

atomy, które akcja wprowadza; dodaje się je sumą dopiero po usunięciu, więc atom, który jest na obu listach, ostatecznie zachodzi

Zadanie to czwórka (F, A, s₀, G), gdzie G ⊆ F jest celem. Plan to ciąg akcji a₁, …, a_k, z których każda jest wykonalna w stanie po poprzednich, a w ostatnim stanie s_k zachodzi G ⊆ s_k.

Przykład — jedna akcja krok po kroku

Klocek C leży na A, B stoi obok. Akcja na stół(C, A) ma pre = {na(C, A), wolny(C)}, add = {stół(C), wolny(A)}, del = {na(C, A)} (pełny opis akcji jest w następnym rozdziale).

s = {na(C, A), stół(A), stół(B), wolny(B), wolny(C)}

pre ⊆ s?   na(C, A) ∈ s, wolny(C) ∈ s → akcja jest wykonalna

s ∖ del = {stół(A), stół(B), wolny(B), wolny(C)}

(s ∖ del) ∪ add = {stół(A), stół(B), stół(C), wolny(A), wolny(B), wolny(C)} — wszystkie trzy klocki na stole

STRIPS powstał w 1971 roku (Fikes i Nilsson) właśnie dla Shakeya. Jego dzisiejszym następcą jest język PDDL, w którym od 1998 roku zadaje się problemy na międzynarodowe zawody planerów. Akcję zapisuje się w nim jako schemat ze zmiennymi:

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

3. Świat klocków

Klasyczne zadanie testowe planowania: na stole leżą klocki, niektóre jeden na drugim. Jedną akcją bierzesz klocek, na którym nic nie leży, i kładziesz go na stół albo na inny wolny klocek. Atomy są trzech rodzajów: na(A, B) — A leży na B, stół(A) i wolny(A).

Akcje w świecie klocków

• na stół(A, B): pre = {na(A, B), wolny(A)}, add = {stół(A), wolny(B)}, del = {na(A, B)}
• ze stołu(A, C): pre = {stół(A), wolny(A), wolny(C)}, add = {na(A, C)}, del = {stół(A), wolny(C)}
• przenieś(A, B, C): pre = {na(A, B), wolny(A), wolny(C)}, add = {na(A, C), wolny(B)}, del = {na(A, B), wolny(C)}

Schemat ze zmiennymi planer najpierw ukonkretnia (grounding): podstawia za zmienne wszystkie kombinacje klocków. Dla n klocków jest n(n − 1) akcji „na stół”, tyle samo „ze stołu” i n(n − 1)(n − 2) przeniesień, razem n²(n − 1). Dla trzech klocków to 9 · 2 = 18 akcji, dla sześciu 36 · 5 = 180. W każdym stanie wykonalnych jest jednak tylko kilka z nich — klocków, na których nic nie leży, jest niewiele.

Świat wygląda jak zabawka, ale szybko rośnie. Trzy klocki można ustawić na 13 sposobów, cztery na 73, pięć na 501, a sześć już na 4 051. Skąd te liczby:

liczba stanów = ∑_k=1ⁿ n! · C(n − 1, k − 1) / k!

n!

ustawiamy wszystkie klocki w jeden rząd — każda kolejność jest kandydatem; wieże dostaniemy z niej przez rozcięcie

C(n − 1, k − 1)

rząd rozcinamy na k niepustych wież: wybieramy k − 1 z n − 1 przerw między klockami. Kolejność wewnątrz wieży ma znaczenie (A na B to nie B na A), dlatego tniemy kolejność, a nie zbiór

k!

kolejność wież na stole nie ma znaczenia — dwie wieże obok siebie to ten sam stan, w jakiejkolwiek kolejności je wypiszemy. Każdy stan policzyliśmy więc k! razy

Planer policzył je inaczej — przeszedł wszystkie osiągalne stany — i wyszło mu to samo. Spróbujemy dwóch zadań. W większym stoją na stole dwie wieże A–B–C i D–E–F (zapisane od dołu), a celem jest jedna wieża F–E–D–C–B–A:

4. Planowanie w przód

Definicja — planowanie w przód (progresja)

Przeszukiwanie przestrzeni stanów ze stanu s₀: następnikami stanu s są stany T(s, a) dla wszystkich akcji a wykonalnych w s. Test celu: G ⊆ s.

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:                      # wszystkie atomy celu zachodzą
            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)

W zadaniu z wieżą przeszukiwanie wszerz znajduje najkrótszy plan z 6 akcjami, ale rozwija przy tym 2 132 stany — ponad połowę ze wszystkich 4 051. Nie wie bowiem nic o tym, w którym kierunku leży cel.

5. Heurystyki z relaksacji

W części o przeszukiwaniu heurystykę dla labiryntu wymyśliliśmy sami. Planer potrafi ją policzyć z opisu akcji — tak, że upraszcza sobie zadanie, rozwiązuje je i koszt uproszczonego rozwiązania używa jako oszacowania.

Definicja — relaksacja bez usuwania

Zadanie zrelaksowane powstaje, gdy wszystkim akcjom ustawimy del(a) = ∅. Atom, który raz zajdzie, zachodzi wtedy już zawsze.

Koszt atomu p ze stanu s w zadaniu zrelaksowanym szacujemy rekurencyjnie: c(p) = 0 dla p ∈ s, w przeciwnym razie c(p) = minimum po akcjach a z p ∈ add(a) z wartości 1 + c(pre(a)), gdzie koszt zbioru atomów to

• dla h_max maksimum kosztów jego atomów — heurystyka jest dopuszczalna,
• dla h_add suma kosztów jego atomów — dokładniejsza wskazówka, ale może przeszacować.

Heurystyka stanu s to koszt zbioru celów G.

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

c(p)

oszacowanie, ile akcji potrzeba, żeby zaczął zachodzić atom p (dla atomów, które już zachodzą, wynosi 0)

min po akcjach z p ∈ add(a)

atom może wprowadzić kilka akcji; wybieramy najtańszą, bo planer sam wybiera drogę

1

koszt samej akcji, która ostatecznie doda p

c(pre(a))

koszt tego, by akcja w ogóle była wykonalna — spełnienia wszystkich jej warunków wstępnych. Tu h_max i h_add się różnią: maksimum zakłada, że warunki spełnią się „jednocześnie”, a ich przygotowania się pokrywają, suma — że każdy wymaga osobnej pracy

def ceny(stav, akce, agreguj):             # agreguj = max (hmax) albo sum (hadd)
    c = {p: 0 for p in stav}
    zmena = True
    while zmena:                             # powtarzaj, dopóki jakiś koszt się poprawia
        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 jest ignorowane — relaksacja
                    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)        # cel nieosiągalny: h = ∞

Przykład — h_max i h_add dla anomalii Sussmana

Początek: C leży na A, B stoi obok; cel G = {na(A, B), na(B, C)} (zadanie omówimy niżej). Koszty atomów warstwami:

koszt 0 (zachodzą): stół(A), stół(B), na(C, A), wolny(B), wolny(C)

koszt 1: na stół(C, A) → stół(C), wolny(A);   ze stołu(B, C) → na(B, C);   przenieś(C, A, B) → na(C, B)

koszt 2: ze stołu(A, B) potrzebuje stół(A), wolny(A), wolny(B) z kosztami 0, 1, 0

   h_max: 1 + max(0, 1, 0) = 2,   h_add: 1 + (0 + 1 + 0) = 2 → na(A, B) ma koszt 2

h_max(s₀) = max(2, 1) = 2,   h_add(s₀) = 2 + 1 = 3,   faktycznie potrzeba: h* = 3

h_max nie doszacowuje, bo liczy tylko najdroższy cel: na(A, B) kosztuje dwie akcje, ale na(B, C) potrzebuje jeszcze własnej, trzeciej, a maksimum ją połyka. Suma ją uwzględnia i tutaj trafia dokładnie. W zadaniu z wieżą widać to wyraźniej: od startu h* = 6, h_max = 3, liczba niespełnionych celów 5, a h_add = 15 — suma liczy wspólne przygotowanie (odsłanianie klocków) przy każdym celu od nowa i przeszacowuje prawdziwy koszt dwa i pół raza.

Twierdzenie — h_max i liczba niespełnionych celów są dopuszczalne

Dopuszczalność z części o przeszukiwaniu: h(s) ≤ h*(s), gdzie h*(s) to długość najkrótszego planu z s.

h_max. Weźmy najkrótszy plan a₁, …, a_k prawdziwego zadania. Jest to plan także dla zadania zrelaksowanego (bez usuwania w każdym kroku zachodzą co najmniej te same atomy, więc warunki wstępne pozostają spełnione). Indukcja po i: każdy atom, który zachodzi po i akcjach, ma c_max ≤ i — albo zachodził już wcześniej, albo dodała go akcja a_i, której warunki wstępne zachodziły po i − 1 akcjach i mają więc koszt ≤ i − 1, zatem 1 + max ≤ i. Wszystkie atomy celu zachodzą po k akcjach, dlatego h_max(s) = max_{g ∈ G} c(g) ≤ k = h*(s).

Liczba niespełnionych celów. Cele świata klocków to atomy na(·, ·), a każda akcja dodaje co najwyżej jeden taki atom. Do spełnienia m brakujących celów potrzeba więc co najmniej m akcji.

Dla h_add dowód zawodzi w ostatnim kroku: suma kosztów może być większa niż k, bo te same akcje planu liczą się przy kilku celach.

Trzy heurystyki w zadaniu z wieżą, wszystkie z algorytmem A*:

Dopuszczalna h_max znajduje optimum i oszczędza ponad 90 % pracy. Liczba niespełnionych celów jest w naszym świecie również dopuszczalna (każda akcja kładzie tylko jeden klocek, więc spełnia co najwyżej jeden cel) i tutaj działa jeszcze lepiej. h_add rozwija najmniej, ale płaci za to: plan ma o krok więcej, niż trzeba. Żadna heurystyka nie wygrywa zawsze — a prawdziwe planery, takie jak FF czy Fast Downward, mają całe zestawy heurystyk, które łączą.

Jak A* z h_max pracuje, najlepiej widać na małym zadaniu — anomalii Sussmana, którą omówimy dwa rozdziały dalej. Każdy wiersz to jeden rozwinięty stan (wieże od dołu); A* bierze zawsze stan z najmniejszym f = g + h, gdzie g to liczba akcji od początku, a przy remisie ten, który odkrył wcześniej:

Przeszukiwanie wszerz w tym samym zadaniu rozwija wszystkie 13 stanów, A* z h_max tylko 5. W trzecim kroku skręca źle — kładzie C na B — bo ten stan ma f = 3, tak samo jak właściwa droga, i został odkryty wcześniej. Już następny krok to naprawia. Pierwszy rozwinięty stan docelowy ma najkrótszy plan — to A* gwarantuje, gdy heurystyka jest dopuszczalna (a h_max jest nawet spójna, więc nie musi wracać do stanów zamkniętych).

6. Planowanie wstecz

Definicja — planowanie wstecz (regresja)

Szuka od celu: stanem przeszukiwania jest zbiór atomów g, które jeszcze muszą zachodzić (na początku g = G). Akcja a jest istotna dla g, gdy add(a) ∩ g ≠ ∅ i del(a) ∩ g = ∅. Regresja celu przez a to

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

g′

co musi zachodzić przed akcją a, żeby po niej zachodziło g — nowy, wcześniejszy cel cząstkowy

g

dotychczasowy cel cząstkowy; atomy, których akcja nie wspomina, muszą zachodzić już wcześniej, bo akcja sama ich nie wprowadzi (a dzięki warunkowi istotności też ich nie zniszczy)

add(a)

odejmujemy, bo te atomy zapewni sama akcja — wcześniej zachodzić nie muszą

pre(a)

dodajemy, bo bez warunków wstępnych akcji nie da się wykonać — stają się nowymi celami cząstkowymi

Przeszukiwanie kończy się, gdy g′ ⊆ s₀; planem są znalezione akcje w odwrotnej kolejności.

Przykład — regresja celu anomalii Sussmana

Cel g = {na(A, B), na(B, C)}, początek s₀ = {na(C, A), stół(A), stół(B), wolny(B), wolny(C)}. Akcje bierzemy od ostatniej:

ze stołu(A, B): add = {na(A, B)} dotyka g, del = {stół(A), wolny(B)} nie → istotna

   g′ = {na(B, C)} ∪ {stół(A), wolny(A), wolny(B)}

ze stołu(B, C): add = {na(B, C)}, del = {stół(B), wolny(C)} → istotna

   g″ = {stół(A), wolny(A), wolny(B)} ∪ {stół(B), wolny(B), wolny(C)} = {stół(A), stół(B), wolny(A), wolny(B), wolny(C)}

na stół(C, A): add = {stół(C), wolny(A)}, del = {na(C, A)} → istotna

   g‴ = {stół(A), stół(B), wolny(B), wolny(C)} ∪ {na(C, A), wolny(C)} = {na(C, A), stół(A), stół(B), wolny(B), wolny(C)} ⊆ s₀ ✓

Plan czytany od tyłu: na stół(C, A), ze stołu(B, C), ze stołu(A, B). Gdybyśmy jednak jako ostatnią akcję spróbowali ze stołu(B, C), dostalibyśmy cel cząstkowy {na(A, B), stół(B), wolny(B), wolny(C)} — A leży na B, a B jest jednocześnie wolny. Taki stan nie istnieje, ale regresja sama tego nie rozpozna; planery wsteczne potrzebują więc dodatkowych reguł, które wykryją niemożliwe kombinacje.

7. Anomalia Sussmana

Najprostszy pomysł na planowanie: podzielić cel na części i spełniać je jedną po drugiej. Często to działa — i zawodzi już przy trzech klockach. Zadanie nosi imię Geralda Sussmana, który omówił je w latach siedemdziesiątych: C leży na A, B stoi obok, celem jest A na B i jednocześnie B na C.

Najkrótszy plan dla „A na B” zdejmuje C i kładzie A na B. Tyle że wtedy B jest pod A, a przeniesienie B na C oznacza ponowne zdjęcie A. Na końcu zachodzi tylko drugi cel i kosztowało to 4 kroki. Odwrotna kolejność kończy się tak samo: kładziemy B na C, ale tym samym zasypujemy A pod C i B — a odsłonięcie go znów niszczy pierwszy cel. Cele wzajemnie się psują, od którego byś nie zaczął.

Rozwiązanie wymaga przeplecenia kroków obu celów: najpierw zwolnić A (krok dla pierwszego celu), potem B na C (drugi cel), a dopiero potem A na B (pierwszy cel). Planer, który przeszukuje przestrzeń pełnych stanów, znajdzie to sam — przeszedł tu wszystkie 13 stanów świata trzech klocków. Planer, który składa plany cząstkowe, musi umieć je rozplatać i łączyć na nowo. To temat całej rodziny „planowania w przestrzeni planów”.

8. Planowanie hierarchiczne

Definicja — HTN

W hierarchicznej sieci zadań (HTN) oprócz akcji prymitywnych są też zadania złożone. Każde zadanie złożone ma jedną lub więcej metod — ciągów podzadań, na które da się je rozłożyć. Planowanie zaczyna się od jednego zadania najwyższego poziomu i rozkłada je, dopóki nie zostaną same akcje prymitywne.

def rozloz(ukoly, stav):                   # ukoly: lista pozostałych zadań
    if not ukoly:
        return []                            # wszystko rozłożone
    u, zbytek = ukoly[0], ukoly[1:]
    if u.primitivni:                         # zwykła akcja 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:                  # próbuj przepisów jeden po drugim
        if metoda.podminka <= stav:
            plan = rozloz(metoda.podukoly + zbytek, stav)
            if plan is not None:
                return plan
    return None                              # żadna metoda nie wyszła — nawrót

Przeszukuje się tu przestrzeń rozkładów, nie stanów: rozgałęzienie zależy tylko od tego, którą metodę wybrać dla zadania złożonego. Zadania rozkłada się w kolejności, w jakiej będą wykonywane, więc planer zawsze zna bieżący stan — tak samo postępuje na przykład planer SHOP2.

Planowanie hierarchiczne stosuje się tam, gdzie eksperci mają sprawdzone procedury: w logistyce, przy sterowaniu produkcją i często w grach komputerowych. Gra akcji F.E.A.R. (2005) zasłynęła żołnierzami, którzy planowali taktykę w locie językiem w stylu STRIPS — i z tego samego pomysłu wychodzą planery w wielu innych grach.

9. Planowanie w niepewnym świecie

STRIPS zakłada, że świat jest dokładnie taki, jak myślimy, a akcje kończą się dokładnie zgodnie z opisem. Prawdziwy robot upuszcza jednak klocek, a prawdziwy serwer nie odpowiada. Najczęstsze odpowiedzi na to są trzy:

• Monitorowanie i ponowne planowanie. Po każdej akcji sprawdź, czy świat wygląda tak, jak plan zakładał. Jeśli nie, zaplanuj od nowa z tego, co jest. Proste i zaskakująco skuteczne (pętla jest niżej).
• Plany warunkowe mają rozgałęzienia: „jeśli drzwi się otworzą, idź dalej, w przeciwnym razie użyj drugiego wejścia”.
• Planowanie probabilistyczne. Gdy akcja ma kilka możliwych wyników o danych prawdopodobieństwach, nie szukamy ciągu akcji, lecz strategii dla każdej sytuacji — procesy decyzyjne Markowa mają w programie własną część.

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 powinno zachodzić według modelu
        svet.udelej(a)
        skutecny = svet.pozoruj()
        if cil <= skutecny:
            return True
        if skutecny != cekany:               # świat zachował się inaczej
            plan = planuj(skutecny, cil, akce)   # zaplanuj od nowa z tego, co jest
    return cil <= svet.pozoruj()

Wystarczy przy tym pilnować tylko tego, od czego zależy reszta planu: gdy zmieni się atom, który nie jest warunkiem wstępnym żadnej dalszej akcji ani częścią celu, plan nadal obowiązuje. Tę oszczędność wprowadził już system PLANEX, który wykonywał plany Shakeya (Fikes, Hart i Nilsson, 1972).

10. Planowanie w agentach AI

Agent językowy, który naprawia błąd w kodzie, też planuje: rozpisuje sobie zadanie na listę kroków, po każdym kroku patrzy na wynik (testy przeszły? plik istnieje?) i zależnie od tego poprawia plan. To monitorowanie i ponowne planowanie, tylko akcje są poleceniami w terminalu, a warunki wstępne i efekty nie są nigdzie formalnie zapisane — model szacuje je z tekstu.

Właśnie tu leży słabość. Badania na zadaniach ze świata klocków (na przykład zestaw PlanBench) pokazały, że modele językowe w klasycznym planowaniu często się mylą, zwłaszcza gdy klocki przemianuje się na bezsensowne słowa, tak że model nie może czerpać z wyuczonych przykładów. Nowsze modele z dłuższym rozumowaniem radzą sobie dużo lepiej, ale gwarancji poprawności nie dają. Sprawdza się więc podział pracy: model tłumaczy zadanie na PDDL albo proponuje plan, a klasyczny planer lub walidator go sprawdza — każdy robi to, co umie.

11. Podsumowanie

• Planowanie to szukanie ciągu akcji prowadzącego do celu; STRIPS opisuje stan jako zbiór atomów, a akcję warunkami wstępnymi, atomami dodawanymi i usuwanymi.
• Planowanie w przód to przeszukiwanie stanów; planowanie wstecz wykonuje regresję celu przez istotne akcje.
• Planer sam liczy heurystykę z zadania zrelaksowanego bez usuwania: h_max jest dopuszczalna, h_add szybsza, ale może prowadzić do dłuższego planu.
• Anomalia Sussmana pokazuje, że celów cząstkowych nie zawsze da się spełniać jeden po drugim — kroki trzeba przeplatać.
• Planowanie hierarchiczne rozkłada zadania według sprawdzonych metod; w niepewnym świecie plan się monitoruje i planuje na nowo — dokładnie to robią dzisiejsi agenci AI.

Chcesz spróbować sam? Poproś agenta AI, żeby zapisał świat klocków w PDDL i uruchomił na nim darmowy planer Fast Downward — a potem sprawdź, ile klocków model ogarnie sam, bez niego.

Masz inne zdanie? Napisz na support@coden-app.com.