## Definition **STRIPS** (Stanford Research Institute Problem Solver) is the foundational language for [[Classical Planning]]. Introduced by Fikes & Nilsson (1971) for the Shakey robot project. Its action representation — preconditions and effects as sets of literals — remains the conceptual core of every modern planning language including [[PDDL]]. ## Representation A STRIPS problem is $\langle P, O, I, G \rangle$: - $P$ — set of propositional symbols (the language of facts). - $O$ — set of operators (action schemas). - $I \subseteq P$ — initial state. - $G \subseteq P$ — goal. ### Operator Schema ``` Action a: Pre(a) — preconditions (propositions that must hold) Add(a) — propositions added to the state after the action Del(a) — propositions removed from the state after the action ``` State after applying $a$ to $s$: $s' = (s \setminus \text{Del}(a)) \cup \text{Add}(a)$. Applicable only if $\text{Pre}(a) \subseteq s$. ## Blocksworld Example ``` Action: Move(b, x, y) Preconditions: On(b, x), Clear(b), Clear(y), b ≠ y Add: On(b, y), Clear(x) Del: On(b, x), Clear(y) ``` ## The STRIPS Assumption (Closed-World) What is *not* listed in the add/delete lists *doesn't change*. Combined with the closed-world assumption (facts not in the state are false), this gives the *frame problem* a clean solution within the STRIPS framework. ## Limitations - No conditional effects (effect depends on context). - No quantifiers. - No disjunctive goals. - No numeric / continuous quantities. Extensions: **ADL** (Pednault, 1989) added conditional effects, quantifiers, and equality. Later subsumed by [[PDDL]]. ## Historical Significance Shakey the robot (1966-1972) was the first robot to reason about its own actions. STRIPS was the planner inside. The action representation is still in use 50+ years later — a rare longevity in computer science. ## Related - [[Classical Planning]] - [[PDDL]] - [[Heuristic Planning]] - [[GRAPHPLAN]]