Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten

Die Sprachen STRIPS und PDDL, Vorwärts- und Rückwärtsplanung, die Heuristiken hmax und hadd, die Sussman-Anomalie, hierarchische Planung und Neuplanen — vom Roboter Shakey bis zu KI-Agenten, die sich eine Aufgabenliste schreiben.

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

Serie KI-Grundlagen Teil 25 von 52

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Was du mitnimmst

Wie man eine Planungsaufgabe als Atome, Aktionen mit Vorbedingungen und Effekten und ein Ziel aufschreibt.
Wie ein Planer seine Heuristik selbst aus der relaxierten Aufgabe berechnet und wie viel Arbeit er damit spart.
Warum sich Teilziele nicht eines nach dem anderen erfüllen lassen und wie heutige KI-Agenten planen.

Vorher gut zu wissen: Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen, Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme

Der Roboter Shakey vom Stanford Research Institute fuhr Ende der Sechzigerjahre durch mehrere Räume, schob Kisten herum und schaltete Lichter aus. Er war der erste Roboter, der über sein Handeln nachdachte: Er bekam ein Ziel („bring die Kiste in den Nebenraum“) und überlegte sich selbst, welche Aktionen in welcher Reihenfolge dorthin führen. Die Sprache, in der er das tat, heißt STRIPS — und ihre Ideen findest du heute in der Logistik, in Computerspielen und in der Schleife des KI-Agenten, der für dich Code schreibt.

Er baut auf den Teilen Zustandsraumsuche und Logik und wissensbasierte Systeme auf.

1. Planung: eine Suche, die hineinschaut

Planung ist die Suche nach einer Folge von Aktionen, die zum Ziel führt — genau wie im Teil über die Suche. Der Unterschied liegt darin, wie die Aufgabe aufgeschrieben ist. Beim Labyrinth war der Zustand eine Blackbox, und der Algorithmus wusste über ihn nur, wohin die Aktionen von ihm aus führen. Ein Planer schaut hinein: Der Zustand ist eine Liste von Fakten über die Welt, und eine Aktion sagt, welche Fakten sie braucht und welche sie ändert. Deshalb kann der Planer selbst abschätzen, wie weit das Ziel entfernt ist — eine Heuristik musst du ihm nicht von Hand schreiben.

2. Die Sprache STRIPS

Definition — STRIPS-Planungsaufgabe

Gegeben ist eine endliche Menge von Atomen F (Aussagen über die Welt). Ein Zustand ist eine Teilmenge s ⊆ F — die Atome, die in ihm gelten; was nicht in s ist, gilt nicht.

Eine Aktion a ist ein Tripel (pre(a), add(a), del(a)) von Teilmengen von F: Vorbedingungen, hinzugefügte und entfernte Atome. Die Aktion ist in s anwendbar, wenn pre(a) ⊆ s, und der Folgezustand ist

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

T(s, a): der Zustand nach Ausführung der Aktion — die Übergangsfunktion, die im Teil über die Suche der Programmierer lieferte; hier leitet sie der Planer selbst aus der Beschreibung der Aktion ab
s: der Ausgangszustand: Alles, was die Aktion nicht erwähnt, wird unverändert in den neuen Zustand übernommen (die STRIPS-Annahme, die das Rahmenproblem löst — wir müssen nicht aufzählen, was sich nicht ändert)
del(a): Atome, die die Aktion ungültig macht; sie werden per Mengendifferenz ∖ abgezogen
add(a): Atome, die die Aktion herbeiführt; sie werden per Vereinigung erst nach dem Entfernen hinzugefügt, ein Atom, das in beiden Listen steht, gilt also am Ende

Eine Aufgabe ist ein Quadrupel (F, A, s₀, G), wobei G ⊆ F das Ziel ist. Ein Plan ist eine Folge von Aktionen a₁, …, a_k, von denen jede im Zustand nach den vorherigen anwendbar ist, und im letzten Zustand s_k gilt G ⊆ s_k.

Einfach gesagt

Ein Zustand ist eine Liste von Sätzen, die gerade gelten: „C liegt auf A“, „auf B liegt nichts“. Eine Aktion ist ein Rezept mit drei Spalten: was gelten muss, damit du sie ausführen kannst; was danach gilt; was nicht mehr gilt. Das Ziel muss nicht die ganze Welt beschreiben — es genügt zu sagen, worauf es dir ankommt, der Rest ist egal.

Beispiel — eine Aktion Schritt für Schritt

Block C liegt auf A, B steht daneben. Die Aktion auf Tisch(C, A) hat pre = {auf(C, A), frei(C)}, add = {tisch(C), frei(A)}, del = {auf(C, A)} (die vollständige Beschreibung der Aktionen steht im nächsten Abschnitt).

s = {auf(C, A), tisch(A), tisch(B), frei(B), frei(C)}

pre ⊆ s? auf(C, A) ∈ s, frei(C) ∈ s → die Aktion ist anwendbar

s ∖ del = {tisch(A), tisch(B), frei(B), frei(C)}

(s ∖ del) ∪ add = {tisch(A), tisch(B), tisch(C), frei(A), frei(B), frei(C)} — alle drei Blöcke auf dem Tisch

STRIPS entstand 1971 (Fikes und Nilsson) eigens für Shakey. Sein heutiger Nachfolger ist die Sprache PDDL, in der seit 1998 die Aufgaben für die internationalen Planungswettbewerbe gestellt werden. Eine Aktion wird darin als Schema mit Variablen geschrieben:

(:action auf-tisch
  :parameters (?a ?b)
  :precondition (and (auf ?a ?b) (frei ?a))
  :effect (and (tisch ?a) (frei ?b) (not (auf ?a ?b))))

3. Die Blockwelt

Die klassische Testaufgabe der Planung: Auf einem Tisch liegen Blöcke, manche aufeinander. Mit einer Aktion nimmst du einen Block, auf dem nichts liegt, und legst ihn auf den Tisch oder auf einen anderen freien Block. Es gibt drei Arten von Atomen: auf(A, B) — A liegt auf B, tisch(A) und frei(A).

Aktionen in der Blockwelt

auf Tisch(A, B): pre = {auf(A, B), frei(A)}, add = {tisch(A), frei(B)}, del = {auf(A, B)}
vom Tisch(A, C): pre = {tisch(A), frei(A), frei(C)}, add = {auf(A, C)}, del = {tisch(A), frei(C)}
umsetzen(A, B, C): pre = {auf(A, B), frei(A), frei(C)}, add = {auf(A, C), frei(B)}, del = {auf(A, B), frei(C)}

Einfach gesagt

Wenn du A von B auf den Tisch hebst, liegt A auf dem Tisch, B wird frei, und A liegt nicht mehr auf B. Alles andere bleibt, wie es war — und das ist wichtig: STRIPS nimmt an, dass eine Aktion nur das ändert, was sie selbst sagt.

Das Schema mit Variablen instanziiert der Planer zuerst (Grounding): Er setzt für die Variablen alle Kombinationen von Blöcken ein. Für n Blöcke gibt es n(n − 1) Aktionen „auf Tisch“, ebenso viele „vom Tisch“ und n(n − 1)(n − 2) Umsetzungen, insgesamt n²(n − 1). Für drei Blöcke sind das 9 · 2 = 18 Aktionen, für sechs 36 · 5 = 180. In jedem Zustand ist aber nur eine Handvoll davon anwendbar — Blöcke, auf denen nichts liegt, gibt es wenige.

Die Welt sieht aus wie ein Spielzeug, wächst aber schnell. Drei Blöcke lassen sich auf 13 Arten anordnen, vier auf 73, fünf auf 501 und sechs schon auf 4 051. Woher diese Zahlen kommen:

Anzahl der Zustände = ∑_k=1ⁿ n! · C(n − 1, k − 1) / k!

n!: wir stellen alle Blöcke in eine Reihe — jede Reihenfolge ist ein Kandidat; die Türme erhalten wir daraus durch Zerschneiden
C(n − 1, k − 1): wir zerschneiden die Reihe in k nichtleere Türme: Wir wählen k − 1 der n − 1 Lücken zwischen den Blöcken. Die Reihenfolge innerhalb eines Turms zählt (A auf B ist nicht B auf A), deshalb zerschneiden wir eine Reihenfolge, keine Menge
k!: die Reihenfolge der Türme auf dem Tisch spielt keine Rolle — zwei Türme nebeneinander sind derselbe Zustand, in welcher Reihenfolge wir sie auch aufschreiben. Jeden Zustand haben wir also k!-mal gezählt

Die Summanden sind die Lah-Zahlen L(n, k), und die Summe ist die Folge A000262 in der Online-Enzyklopädie der Zahlenfolgen OEIS.

n = 3: k = 1: 6 · 1 / 1 = 6, k = 2: 6 · 2 / 2 = 6, k = 3: 6 · 1 / 6 = 1 → 13

n = 4: 24 + 36 + 12 + 1 = 73

n = 6: 720 + 1 800 + 1 200 + 300 + 30 + 1 = 4 051

Der Planer hat sie anders gezählt — er ist alle erreichbaren Zustände durchgegangen — und kam auf dasselbe. Wir probieren zwei Aufgaben aus. In der größeren stehen auf dem Tisch zwei Türme A–B–C und D–E–F (von unten gelesen), und das Ziel ist ein einziger Turm F–E–D–C–B–A:

Kürzester Plan: aus zwei Türmen ein umgedrehter

4. Vorwärtsplanung

Definition — Vorwärtsplanung (Progression)

Suche im Zustandsraum ab dem Zustand s₀: Die Nachfolger eines Zustands s sind die Zustände T(s, a) für alle in s anwendbaren Aktionen a. Zieltest: G ⊆ s.

Einfach gesagt

Du probierst von der Ausgangssituation aus alle Züge, von allen Ergebnissen wieder alle Züge, bis du auf eine Situation stößt, in der das Ziel gilt. Nichts Neues — es ist BFS oder A* aus dem Teil über die Suche, nur über Zuständen, die als Mengen von Fakten geschrieben sind.

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:                      # alle Zielatome gelten
            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)

Bei der Turmaufgabe findet die Breitensuche den kürzesten Plan mit 6 Aktionen, expandiert dabei aber 2 132 Zustände — mehr als die Hälfte aller 4 051. Sie weiß nämlich nichts darüber, in welcher Richtung das Ziel liegt.

5. Heuristiken aus Relaxierung

Im Teil über die Suche haben wir uns die Heuristik für das Labyrinth selbst ausgedacht. Ein Planer kann sie aus der Beschreibung der Aktionen berechnen — indem er die Aufgabe vereinfacht, sie löst und die Kosten der vereinfachten Lösung als Schätzung verwendet.

Definition — Relaxierung ohne Löschen

Die relaxierte Aufgabe entsteht, wenn wir für alle Aktionen del(a) = ∅ setzen. Ein Atom, das einmal gilt, gilt dann für immer.

Die Kosten eines Atoms p ab dem Zustand s in der relaxierten Aufgabe schätzen wir rekursiv: c(p) = 0 für p ∈ s, sonst ist c(p) das Minimum über die Aktionen a mit p ∈ add(a) des Werts 1 + c(pre(a)), wobei die Kosten einer Atommenge

bei h_max das Maximum der Kosten ihrer Atome sind — die Heuristik ist zulässig,
bei h_add die Summe der Kosten ihrer Atome — ein genauerer Wegweiser, der aber überschätzen kann.

Die Heuristik des Zustands s sind die Kosten der Zielmenge G.

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

c(p): Schätzung, wie viele Aktionen nötig sind, damit das Atom p gilt (für Atome, die schon gelten, ist sie 0)
min über Aktionen mit p ∈ add(a): ein Atom können mehrere Aktionen herbeiführen; wir nehmen die billigste, weil der Planer seinen Weg selbst wählt
1: die Kosten der Aktion selbst, die p schließlich hinzufügt
c(pre(a)): die Kosten dafür, dass die Aktion überhaupt anwendbar ist — alle ihre Vorbedingungen zu erfüllen. Hier unterscheiden sich h_max und h_add: Das Maximum nimmt an, dass die Vorbedingungen „gleichzeitig“ erfüllt werden und sich ihre Vorbereitungen überlappen, die Summe, dass jede eigene Arbeit kostet

Das Löschen (del) fehlt in der Formel — das ist die Relaxierung. Die Rekursion ist wohldefiniert, weil wir die Kosten schichtweise von null aufwärts berechnen, solange sich etwas ändert.

Einfach gesagt

Stell dir eine Welt vor, in der nichts kaputtgehen kann: Wenn du einen Block einmal freigelegt hast, bleibt er frei, auch wenn du etwas darauflegst. In so einer Welt ist Planen leicht, und seine Kosten sind eine optimistische Schätzung der echten. h_max rechnet nur mit dem schwersten Teilziel (vorsichtig, überschätzt nie), h_add zählt alle zusammen (mutiger, kann übers Ziel hinausschießen, weil eine Aktion manchmal mehreren Zielen auf einmal hilft).

def ceny(stav, akce, agreguj):             # agreguj = max (hmax) oder sum (hadd)
    c = {p: 0 for p in stav}
    zmena = True
    while zmena:                             # wiederholen, solange sich Kosten verbessern
        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 wird ignoriert — Relaxierung
                    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)        # unerreichbares Ziel: h = ∞

Beispiel — h_max und h_add für die Sussman-Anomalie

Start: C liegt auf A, B steht daneben; Ziel G = {auf(A, B), auf(B, C)} (die Aufgabe besprechen wir weiter unten). Kosten der Atome nach Schichten:

Kosten 0 (gilt): tisch(A), tisch(B), auf(C, A), frei(B), frei(C)

Kosten 1: auf Tisch(C, A) → tisch(C), frei(A); vom Tisch(B, C) → auf(B, C); umsetzen(C, A, B) → auf(C, B)

Kosten 2: vom Tisch(A, B) braucht tisch(A), frei(A), frei(B) mit den Kosten 0, 1, 0

h_max: 1 + max(0, 1, 0) = 2, h_add: 1 + (0 + 1 + 0) = 2 → auf(A, B) kostet 2

h_max(s₀) = max(2, 1) = 2, h_add(s₀) = 2 + 1 = 3, tatsächlich nötig: h* = 3

h_max unterschätzt, weil es nur das teuerste Ziel zählt: auf(A, B) kostet zwei Aktionen, aber auf(B, C) braucht noch eine eigene dritte, und das Maximum verschluckt sie. Die Summe zählt sie mit und trifft hier genau. Bei der Turmaufgabe ist es deutlicher: Vom Start aus ist h* = 6, h_max = 3, die Zahl der unerfüllten Ziele 5 und h_add = 15 — die Summe zählt die gemeinsame Vorbereitung (das Freilegen von Blöcken) bei jedem Ziel erneut und überschätzt die echten Kosten um das Zweieinhalbfache.

Satz — h_max und die Zahl der unerfüllten Ziele sind zulässig

Zulässigkeit aus dem Teil über die Suche: h(s) ≤ h*(s), wobei h*(s) die Länge des kürzesten Plans ab s ist.

h_max. Nehmen wir einen kürzesten Plan a₁, …, a_k der echten Aufgabe. Er ist auch ein Plan für die relaxierte Aufgabe (ohne Löschen gelten in jedem Schritt mindestens dieselben Atome, die Vorbedingungen bleiben also erfüllt). Induktion über i: Jedes Atom, das nach i Aktionen gilt, hat c_max ≤ i — entweder galt es schon vorher, oder die Aktion a_i hat es hinzugefügt, deren Vorbedingungen nach i − 1 Aktionen galten und daher Kosten ≤ i − 1 haben, also 1 + max ≤ i. Alle Zielatome gelten nach k Aktionen, deshalb ist h_max(s) = max_{g ∈ G} c(g) ≤ k = h*(s).

Zahl der unerfüllten Ziele. Die Ziele der Blockwelt sind Atome auf(·, ·), und jede Aktion fügt höchstens ein solches Atom hinzu. Um m fehlende Ziele zu erfüllen, braucht man daher mindestens m Aktionen.

Für h_add scheitert der Beweis am letzten Schritt: Die Summe der Kosten kann größer als k sein, weil dieselben Aktionen des Plans bei mehreren Zielen gezählt werden.

Drei Heuristiken bei der Turmaufgabe, alle mit dem Algorithmus A*:

Suche	Expandierte Zustände	Planlänge
Breitensuche (ohne Heuristik)	2 132	6
A* mit `h`_max	136	6
A* mit der Zahl der unerfüllten Ziele	19	6
A* mit `h`_add	12	7

Die zulässige h_max findet das Optimum und spart über 90 % der Arbeit. Die Zahl der unerfüllten Ziele ist in unserer Welt ebenfalls zulässig (jede Aktion setzt nur einen Block ab, erfüllt also höchstens ein Ziel) und funktioniert hier sogar noch besser. h_add expandiert am wenigsten, zahlt aber dafür: Der Plan hat einen Schritt mehr als nötig. Keine Heuristik gewinnt immer — und echte Planer wie FF oder Fast Downward haben ganze Sätze von Heuristiken, die sie kombinieren.

Wie A* mit h_max arbeitet, sieht man am besten an einer kleinen Aufgabe — der Sussman-Anomalie, die wir zwei Abschnitte weiter besprechen. Jede Zeile ist ein expandierter Zustand (Türme von unten); A* nimmt immer den Zustand mit dem kleinsten f = g + h, wobei g die Zahl der Aktionen seit dem Start ist, und bei Gleichstand den früher entdeckten:

Schritt	Expandierter Zustand	Letzte Aktion	`g`	`h`_max	`f`
1	A–C, B	— (Start)	0	2	2
2	A, B, C	auf Tisch(C, A)	1	1	2
3	A, B–C	umsetzen(C, A, B)	1	2	3
4	A, C–B	vom Tisch(B, C)	2	1	3
5	C–B–A	vom Tisch(A, B)	3	0	3 — Ziel

Die Breitensuche expandiert bei derselben Aufgabe alle 13 Zustände, A* mit h_max nur 5. Im dritten Schritt biegt sie falsch ab — sie legt C auf B —, weil dieser Zustand f = 3 hat, genau wie der richtige Weg, und früher entdeckt wurde. Gleich der nächste Schritt korrigiert das. Der erste expandierte Zielzustand hat den kürzesten Plan — das garantiert A*, wenn die Heuristik zulässig ist (und h_max ist sogar konsistent, sodass A* nicht zu geschlossenen Zuständen zurückkehren muss).

6. Rückwärtsplanung

Definition — Rückwärtsplanung (Regression)

Sucht vom Ziel aus: Ein Suchzustand ist eine Menge von Atomen g, die noch gelten müssen (am Anfang g = G). Eine Aktion a ist für g relevant, wenn add(a) ∩ g ≠ ∅ und del(a) ∩ g = ∅. Die Regression des Ziels über a ist

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

g′: was vor der Aktion a gelten muss, damit danach g gilt — ein neues, früheres Teilziel
g: das bisherige Teilziel; Atome, die die Aktion nicht erwähnt, müssen schon vorher gelten, weil die Aktion sie nicht selbst herbeiführt (und sie dank der Relevanzbedingung auch nicht zerstört)
add(a): ziehen wir ab, weil diese Atome die Aktion selbst herstellt — vorher müssen sie nicht gelten
pre(a): fügen wir hinzu, weil die Aktion ohne ihre Vorbedingungen nicht ausführbar ist — sie werden zu neuen Teilzielen

Das ist das „Spiegelbild“ der Übergangsfunktion T(s, a): Dort wird del entfernt und add hinzugefügt, hier wird add entfernt und pre hinzugefügt.

Die Suche endet, wenn g′ ⊆ s₀; der Plan sind die gefundenen Aktionen in umgekehrter Reihenfolge.

Einfach gesagt

Du fragst: „Welche Aktion könnte mir geben, was ich will, ohne dabei etwas davon zu zerstören? Und was müsste vorher gelten?“ Dieselbe Überlegung wie beim Rückwärtsverketten im vorigen Teil. Der Vorteil: Du untersuchst nur Aktionen, die mit dem Ziel zu tun haben. Der Nachteil: Du arbeitest mit Mengen von Zielen statt mit vollständigen Zuständen, und die lassen sich schlechter abschätzen.

Beispiel — Regression des Ziels der Sussman-Anomalie

Ziel g = {auf(A, B), auf(B, C)}, Start s₀ = {auf(C, A), tisch(A), tisch(B), frei(B), frei(C)}. Wir nehmen die Aktionen von der letzten her:

vom Tisch(A, B): add = {auf(A, B)} trifft g, del = {tisch(A), frei(B)} nicht → relevant

g′ = {auf(B, C)} ∪ {tisch(A), frei(A), frei(B)}

vom Tisch(B, C): add = {auf(B, C)}, del = {tisch(B), frei(C)} → relevant

g″ = {tisch(A), frei(A), frei(B)} ∪ {tisch(B), frei(B), frei(C)} = {tisch(A), tisch(B), frei(A), frei(B), frei(C)}

auf Tisch(C, A): add = {tisch(C), frei(A)}, del = {auf(C, A)} → relevant

g‴ = {tisch(A), tisch(B), frei(B), frei(C)} ∪ {auf(C, A), frei(C)} = {auf(C, A), tisch(A), tisch(B), frei(B), frei(C)} ⊆ s₀ ✓

Der Plan rückwärts gelesen: auf Tisch(C, A), vom Tisch(B, C), vom Tisch(A, B). Hätten wir aber als letzte Aktion vom Tisch(B, C) probiert, bekämen wir das Teilziel {auf(A, B), tisch(B), frei(B), frei(C)} — A liegt auf B, und B ist zugleich frei. Einen solchen Zustand gibt es nicht, aber die Regression merkt das von selbst nicht; Rückwärtsplaner brauchen deshalb zusätzliche Regeln, die unmögliche Kombinationen aufdecken.

7. Die Sussman-Anomalie

Die einfachste Idee, wie man plant: das Ziel in Teile zerlegen und sie einen nach dem anderen erfüllen. Das funktioniert oft — und scheitert schon an drei Blöcken. Die Aufgabe trägt den Namen von Gerald Sussman, der sie in den Siebzigerjahren analysiert hat: C liegt auf A, B steht daneben, das Ziel ist A auf B und zugleich B auf C.

Ziel für Ziel: erst „A auf B“, dann „B auf C“

Der kürzeste Plan für „A auf B“ nimmt C herunter und legt A auf B. Dann aber liegt B unter A, und B auf C zu bringen heißt, A wieder herunterzunehmen. Am Ende gilt nur das zweite Ziel, und es hat 4 Schritte gekostet. Die umgekehrte Reihenfolge geht genauso aus: Wir legen B auf C, begraben damit aber A unter C und B — und es freizulegen, zerstört wieder das erste Ziel. Die Ziele stören einander, egal, mit welchem du anfängst.

Kürzester Plan: drei Schritte, Ziele verschränkt

Die Lösung muss die Schritte beider Ziele verschränken: erst A freilegen (ein Schritt für das erste Ziel), dann B auf C (zweites Ziel) und erst dann A auf B (erstes Ziel). Ein Planer, der im Raum ganzer Zustände sucht, findet das selbst — er ist hier alle 13 Zustände der Welt mit drei Blöcken durchgegangen. Ein Planer, der Teilpläne zusammensetzt, muss sie entflechten und neu verbinden können. Das ist das Thema einer ganzen Familie: der „Planung im Planraum“.

8. Hierarchische Planung

Definition — HTN

In einem hierarchischen Aufgabennetz (HTN) gibt es neben primitiven Aktionen auch zusammengesetzte Aufgaben. Jede zusammengesetzte Aufgabe hat eine oder mehrere Methoden — Folgen von Teilaufgaben, in die sie sich zerlegen lässt. Die Planung beginnt mit einer einzigen Aufgabe der obersten Ebene und zerlegt sie, bis nur noch primitive Aktionen übrig sind.

Einfach gesagt

Niemand plant einen Urlaub Schritt für Schritt mit den Füßen. Du zerlegst ihn in „hinkommen“, „unterkommen“ und „zurückkommen“; „hinkommen“ in „Fahrkarte kaufen“ und „zum Bahnhof fahren“ — und erst ganz unten stehen konkrete Handgriffe. Methoden sind bewährte Rezepte, wie man eine komplizierte Sache zerlegt, und dank ihnen probiert der Planer keinen Unsinn aus.

def rozloz(ukoly, stav):                   # ukoly: Liste der verbleibenden Aufgaben
    if not ukoly:
        return []                            # alles zerlegt
    u, zbytek = ukoly[0], ukoly[1:]
    if u.primitivni:                         # gewöhnliche STRIPS-Aktion
        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:                  # Rezepte nacheinander probieren
        if metoda.podminka <= stav:
            plan = rozloz(metoda.podukoly + zbytek, stav)
            if plan is not None:
                return plan
    return None                              # keine Methode ging auf — zurück

Gesucht wird hier im Raum der Zerlegungen, nicht der Zustände: Verzweigt wird nur danach, welche Methode man für eine zusammengesetzte Aufgabe wählt. Die Aufgaben werden in der Reihenfolge zerlegt, in der sie ausgeführt werden, sodass der Planer immer den aktuellen Zustand kennt — so geht zum Beispiel der Planer SHOP2 vor.

Hierarchische Planung wird dort eingesetzt, wo Fachleute bewährte Vorgehensweisen haben: in der Logistik, bei der Produktionssteuerung und häufig in Computerspielen. Das Actionspiel F.E.A.R. (2005) wurde berühmt für Soldaten, die ihre Taktik zur Laufzeit in einer STRIPS-artigen Sprache planten — und auf derselben Idee beruhen die Planer in einer ganzen Reihe weiterer Spiele.

9. Planung in einer unsicheren Welt

STRIPS nimmt an, dass die Welt genau so ist, wie wir glauben, und Aktionen genau wie beschrieben ausgehen. Ein echter Roboter lässt aber einen Block fallen, und ein echter Server antwortet nicht. Die häufigsten Antworten darauf sind drei:

Überwachen und Neuplanen. Prüfe nach jeder Aktion, ob die Welt so aussieht, wie der Plan es erwartet hat. Wenn nicht, plane neu von dem aus, was ist. Einfach und überraschend wirksam (die Schleife steht unten).
Bedingte Pläne haben Verzweigungen: „Wenn sich die Tür öffnet, geh weiter, sonst nimm den zweiten Eingang.“
Probabilistische Planung. Hat eine Aktion mehrere mögliche Ergebnisse mit gegebenen Wahrscheinlichkeiten, suchen wir keine Folge von Aktionen, sondern eine Strategie für jede Situation — Markow-Entscheidungsprozesse haben im Lehrplan einen eigenen Teil.

def proved_s_dohledem(cil, akce, svet):
    plan = planuj(svet.pozoruj(), cil, akce)
    while plan:
        a = plan.pop(0)
        cekany = proved(svet.pozoruj(), a)   # was laut Modell gelten sollte
        svet.udelej(a)
        skutecny = svet.pozoruj()
        if cil <= skutecny:
            return True
        if skutecny != cekany:               # die Welt hat sich anders verhalten
            plan = planuj(skutecny, cil, akce)   # neu planen von dem aus, was ist
    return cil <= svet.pozoruj()

Dabei genügt es, nur das zu überwachen, wovon der Rest des Plans abhängt: Ändert sich ein Atom, das weder Vorbedingung einer weiteren Aktion noch Teil des Ziels ist, gilt der Plan weiter. Diese Einsparung führte schon das System PLANEX ein, das Shakeys Pläne ausführte (Fikes, Hart und Nilsson, 1972).

10. Planung in KI-Agenten

Ein Sprachagent, der einen Fehler im Code behebt, plant ebenfalls: Er zerlegt die Aufgabe in eine Liste von Schritten, schaut sich nach jedem Schritt das Ergebnis an (Tests bestanden? Datei vorhanden?) und passt den Plan entsprechend an. Das ist Überwachen und Neuplanen, nur sind die Aktionen Befehle im Terminal, und Vorbedingungen und Effekte sind nirgends formal aufgeschrieben — das Modell schätzt sie aus dem Text.

Genau hier liegt die Schwachstelle. Forschung an Aufgaben aus der Blockwelt (etwa der Testsammlung PlanBench) hat gezeigt, dass Sprachmodelle bei klassischer Planung oft Fehler machen, besonders wenn man die Blöcke in sinnlose Wörter umbenennt, sodass das Modell nicht aus gelernten Beispielen schöpfen kann. Neuere Modelle mit längerem Nachdenken schneiden viel besser ab, eine Garantie für Korrektheit geben sie aber nicht. Bewährt hat sich deshalb eine Arbeitsteilung: Das Modell übersetzt die Aufgabe in PDDL oder schlägt einen Plan vor, und ein klassischer Planer oder Validator prüft ihn — jeder macht, was er kann.

11. Zusammenfassung

Planung ist die Suche nach einer Folge von Aktionen zum Ziel; STRIPS beschreibt einen Zustand als Menge von Atomen und eine Aktion durch Vorbedingungen, hinzugefügte und entfernte Atome.
Vorwärtsplanung ist Suche über Zustände; Rückwärtsplanung regrediert das Ziel über relevante Aktionen.
Der Planer berechnet seine Heuristik selbst aus der relaxierten Aufgabe ohne Löschen: h_max ist zulässig, h_add schneller, kann aber zu einem längeren Plan führen.
Die Sussman-Anomalie zeigt, dass sich Teilziele nicht immer eines nach dem anderen erfüllen lassen — die Schritte müssen verschränkt werden.
Hierarchische Planung zerlegt Aufgaben nach bewährten Methoden; in einer unsicheren Welt wird der Plan überwacht und neu geplant — genau das tun heutige KI-Agenten.

Willst du es selbst ausprobieren? Lass einen KI-Agenten die Blockwelt in PDDL aufschreiben und den frei verfügbaren Planer Fast Downward darauf loslassen — und probier dann aus, wie viele Blöcke das Modell allein ohne ihn schafft.

Siehst du das anders? Schreib an support@coden-app.com.

Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten

1. Planung: eine Suche, die hineinschaut

2. Die Sprache STRIPS

3. Die Blockwelt

4. Vorwärtsplanung

5. Heuristiken aus Relaxierung

6. Rückwärtsplanung

7. Die Sussman-Anomalie

8. Hierarchische Planung

9. Planung in einer unsicheren Welt

10. Planung in KI-Agenten

11. Zusammenfassung

Ein Agent auf deinem Rechner, vom Telefon aus gesteuert