Begriff
STRIPS
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Wie plant ein Roboter? ("Ich bin im Flur und will ins Zimmer"). Vor STRIPS war das Logik-Chaos (Frame Problem). STRIPS (1971 für den Roboter "Shakey") machte es einfach. Jede Aktion hat 3 Listen:
- Precondition: Was muss wahr sein? ("Tür offen").
- Add List: Was wird wahr? ("Bin im Zimmer").
- Delete List: Was wird falsch? ("Bin im Flur"). Das Frame-Problem wurde ignoriert ("Alles, was nicht in der Delete List steht, bleibt gleich"). Das war pragmatisch und funktionierte super.
Merksatz: Eine formale Sprache und ein Planungsalgorithmus für künstliche Intelligenz, der Aktionen durch Vorbedingungen sowie hinzugefügte und gelöschte Fakten beschreibt, um das Frame-Problem pragmatisch zu umgehen (STRIPS Assumption).
Heute nutzt man PDDL (eine Erweiterung von STRIPS).
Planer: "Ziel: Box in Raum B."
Start: "Box in Raum A. Roboter in Raum A."
STRIPS sucht: "Welche Aktion bringt 'Box in Raum B'? -> carry(Box, A, B).
Precondition: at(Robot, A) und at(Box, A).
Precondition erfüllt? Ja.
Plan fertig: pickUp(Box), moveTo(B), drop(Box).
1. Means-Ends Analysis
Die Strategie von STRIPS.
Vergleiche IST und SOLL.
Differenz: "Roboter ist hier, soll da sein."
Finde Operator, der Diff reduziert (move).
Wende Operator an (simuliert).
Neuer Zustand. Wiederhole.
2. Sussman Anomaly
Ein berühmter Bug in STRIPS. Ziel: "A auf B" UND "B auf C". STRIPS löst erst Ziel 1 ("A auf B"). Super. Dann merkt es: "Mist, für B auf C muss B frei sein. Aber A liegt drauf!" Es muss alles wieder kaputt machen. Lineare Planung scheitert hier. Man braucht "Interleaved Planning" (Partial Order Planning).
1. State-Space Search & Graphplan
STRIPS verwandelt ein Planungsproblem in ein Graph-Problem. Jeder Zustand ist ein Knoten, jede Aktion eine Kante. In der Forschung wurde dies durch den Graphplan-Algorithmus (1995) revolutioniert. Anstatt blind zu suchen, baut Graphplan einen "Planning Graph" in Schichten auf (Zustände -> Aktionen -> Folge-Zustände). Er prüft gleichzeitig alle möglichen Aktionen pro Schicht und nutzt "Incompatibility Links" (Mutexes), um auszuschließen, dass zwei Dinge gleichzeitig passieren (z.B. "Tür aufschließen" und "Schlüssel wegwerfen").
2. PDDL: Die Evolutionsstufe
In der Industrie nutzt niemand mehr das originale STRIPS von 1971. Man nutzt PDDL (Planning Domain Definition Language). PDDL fügt alles hinzu, was STRIPS fehlte:
- Typen:
Robot,Box,Location. - Numerische Fluents: "Batteriestand sinkt um 5%".
- Zeit: "Aktion dauert 10 Sekunden". PDDL ist heute das Standard-Format für die jährlichen "International Planning Competitions" (IPC), in denen KI-Systeme zeigen, wie schnell sie Millionen von Aktionen koordinieren können.
3. Regression Planning vs. Progression
- Progression: Suche vom Start zum Ziel. (Normales Denken).
- Regression: Suche vom Ziel zum Start. STRIPS nutzt oft Regression. Warum? Weil es meist nur ein Ziel gibt ("Kaffee ist gekocht"), aber Millionen Wege vom Start abzweigen. Wenn man vom Ziel aus fragt: "Was brauchte ich davor?" (Kaffee-Maschine an), grenzt das den Suchbereich massiv ein. In modernen Planern nutzt man Heuristiken (wie Fast-Forward - FF), um die Distanz zum Ziel mathematisch zu schätzen, ähnlich wie A* im Straßennetz.
Quick-Check
Warum Shakey?
Der erste mobile Roboter, der über seine Handlungen "nachdenken" konnte. Er zitterte (shaked) beim Rechnen.Ist STRIPS modern?
Das Prinzip ja (State-Space Search). Der originale Solver nein (zu dumm für komplexe Probleme). Heute nutzt man Heuristiken (A*), um schneller zu suchen.Grenzen?
Keine Zeit ("Dauert 5 Minuten"), keine Wahrscheinlichkeiten ("Klappt zu 90%"). STRIPS ist eine Welt aus harten Fakten.