STRIPS: The 1971 Paper That's Still the Ancestor of Every Game AI Planner

The 1971 Fikes & Nilsson paper that introduced STRIPS planning ran on a PDP-10 and took up to 123 CPU-seconds to solve a three-box task — and it's the direct ancestor of F.E.A.R.'s GOAP system, 34 years later. Reading the actual paper turns up four specific things Jeff Orkin's team had to change to make planning fast enough for a real-time game.

Contents

• What STRIPS Actually Is
• Inside the 1971 Paper
• The Robot That Ran It
• What Orkin Changed for F.E.A.R.
• Run the Actual Thing
• More Repos Worth Cloning
• What STRIPS Explicitly Doesn't Do
• Conclusion

What STRIPS Actually Is

Every "GOAP" tutorial on YouTube traces the technique back to F.E.A.R. and stops there, as if Jeff Orkin invented planning-based AI from scratch in a Monolith office in 2004. He didn't, and he says so directly in his own GDC paper: "The planning system that we implemented for F.E.A.R. most closely resembles the STRIPS planning system from academia." That system is 34 years older than F.E.A.R., built on a PDP-10 in LISP, and designed to plan the movements of an actual physical robot at Stanford Research Institute — not a videogame character at all.

The paper is STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving, written by Richard Fikes and Nils Nilsson and presented at IJCAI in September 1971. It's sitting in plain text on Nilsson's own Stanford page, and almost nobody citing GOAP tutorials seems to have actually opened it.

Inside the 1971 Paper

STRIPS solves problems by searching a space of "world models" — sets of first-order predicate calculus formulas — for one where a goal formula is provable. Fikes and Nilsson define an operator as two things: a precondition (what has to be provable before the operator applies) and two effect lists, a delete list and an add list, describing what stops being true and what becomes true. Here's the actual push operator from the paper, reproduced exactly:

push(k, m, n)
Precondition: ATR(m) ∧ AT(k, m)
Delete list:  ATR(m)
              AT(k, m)
Add list:     AT(k, n)
              ATR(n)

ATR(m) means the robot is at location m; AT(k, m) means object k is at location m. Pushing object k from m to n deletes both "robot is at m" and "object is at m," and adds both "robot is at n" and "object is at n." That two-list structure — delete first, then add — exists specifically because, as the paper explains, plain predicate logic has no way to overwrite a value; without an explicit delete step, a world model would end up asserting the robot is at both its old and new locations simultaneously.

The search itself borrows from Newell and Simon's General Problem Solver: STRIPS attempts to prove the goal from the current model, and when the proof fails, the leftover unprovable fragment is treated as a "difference." Operators whose effects could resolve that difference become candidate subgoals, and the process recurses — a mix of forward and backward search that the paper's own diagram represents as a tree of (world model, goal list) node pairs.

The Robot That Ran It

Section 4 of the paper isn't a toy example — it's real performance data from three actual tasks run on the SRI robot: turning on a lightswitch (which required pushing a box underneath it first, an unlabeled version of the Monkey-and-Bananas problem), pushing three boxes together, and navigating to a location in another room. All three used the same room layout — a corridor connecting four rooms — with real operators like gotol, pushto, climbonbox, and gothrudoor.

Those numbers are worth sitting with: more than a minute of CPU time to plan six operator applications, and the paper itself notes most of that time went to the resolution theorem prover, not the search. That's the actual cost of doing planning the way STRIPS did it — full first-order theorem proving on every precondition check. It's also exactly the bottleneck GOAP was built to eliminate three decades later.

What Orkin Changed for F.E.A.R.

Orkin's paper is explicit that GOAP is STRIPS with four specific, deliberate modifications, made because "STRIPS-style" theorem proving was never going to run inside a 2005 game's frame budget:

That last row is the one that actually connects planning back to the FSM discussion Orkin opens the paper with: F.E.A.R.'s state machine has exactly three states (Goto, Animate, UseSmartObject), and the planner's job is only to pick which sequence of those states to run and in what order — not to decide what "shooting" or "taking cover" looks like frame to frame. The C++ shape of a GOAP action, straight from the paper, is genuinely this small:

class Action
{
    // Symbolic preconditions and effects,
    // represented as arrays of variables.
    WORLD_STATE m_Preconditions;
    WORLD_STATE m_Effects;

    // Procedural preconditions and effects.
    bool CheckProceduralPreconditions();
    void ActivateAction();
};

Cutting the theorem prover for a flat array comparison is most of why GOAP can run per-tick in a shipping game while STRIPS needed two minutes per plan on a research robot.

Run the Actual Thing

You don't have to take either paper's word for it — a working, modern STRIPS/PDDL implementation exists as an npm package, built by Kory Becker and still installable today:

$ npm install strips

Its blocks-world examples use real PDDL-flavored domain and problem files. Here's the actual domain.txt for its simplest example, a world with one action:

(define (domain blocksworld)
  (:requirements :strips)
  (:predicates
    (block ?b)
    (table ?t)
    (on ?b ?t))
  (:action move
    :parameters (?b ?t1 ?t2)
    :precondition (and
      (block ?b)
      (table ?t1)
      (table ?t2)
      (on ?b ?t1))
    :effect (and
      (on ?b ?t2)
      (not (on ?b ?t1)))))

And the matching problem.txt:

(define (problem move-blocks-from-a-to-b)
  (:domain blocksworld)
  (:objects a b x y)
  (:init
    (block a)
    (block b)
    (table x)
    (table y)
    (on a x)
    (on b x))
  (:goal (and (on a y) (on b y))))

Note the shape: :precondition and :effect map directly onto Fikes and Nilsson's precondition/delete-list/add-list structure, 54 years later, just written in PDDL syntax instead of predicate calculus. Running the package's harder blocks-world problem — unstacking two blocks from one table and restacking them on another, with only one block or stack allowed per table — produces this real solver output:

Solution found in 4 steps!
1. unstack a b t1 t3
2. move b t1 t2
3. move a t3 t1
4. stack a t1 b t2

That's the same "search a space of world models for one where the goal holds" process from 1971, just fast enough now to run instantly instead of taking two minutes.

More Repos Worth Cloning

Three real, currently-maintained repos, for anyone who wants to go past reading about STRIPS and actually run one:

• primaryobjects/strips (Node.js, MIT) — the one used above. 327 stars, real Blocks World and Sussman Anomaly examples, and a working solver for the same Blocks World problem class STRIPS itself was tested against.
• aibasel/pyperplan (Python, GPLv3) — a lightweight, academically-maintained STRIPS/PDDL planner out of the University of Freiburg's AI planning course. Explicitly optimized for readable code over raw speed, which makes it the better one to actually read start to finish. Install and run against any PDDL domain/problem pair with:

  $ pip install pyperplan --break-system-packages
  $ pyperplan benchmarks/tpp/domain.pddl benchmarks/tpp/task01.pddl

Solutions are written to a .soln file next to the problem file, in the same LISP-like action-list notation STRIPS itself produced in 1971.

• cpowell/cppGOAP (C++11) — a from-scratch GOAP planner whose README explicitly credits Orkin's writings as the inspiration, and which uses A* over world-states exactly the way the GDC paper describes. Closer to what a real game engine's planner looks like than either of the STRIPS repos above, since it's built around the cost-per-action model GOAP added rather than a bare theorem-provable goal.

What STRIPS Explicitly Doesn't Do

It's worth being precise about the limits of the actual 1971 system, since "GOAP is STRIPS" gets repeated without much scrutiny of what STRIPS couldn't do:

• No real-time guarantee. The paper's own benchmark numbers — 66 to 123 CPU-seconds per plan — make clear this was never going to run at interactive speed without the changes GOAP made.
• No cost-based optimization. STRIPS accepts the first valid plan it proves, not the cheapest one. Preferring one plan over another (Orkin's Alma-orders-pizza-or-bakes-a-pie example) requires the cost model GOAP added.
• No concurrency. Plans are strictly sequential operator applications; nothing in the 1971 formalism represents two actions happening in parallel, which is part of why Orkin points modern squad-AI developers toward Hierarchical Task Network planning instead.
• No learning from failure inside the shipped system. Section 5 of the paper describes wanting STRIPS to learn new generalized operators from past solutions — but the paper is explicit this was future work, not something the 1971 implementation actually did.
• No partial observability. The world model is assumed fully known and static during planning; nothing changes it mid-search.

For a different angle on how modern AI systems are given goals and let loose to plan their own path to them, see SudoSecurity's piece on Cloudflare's open-source agent sandbox architecture — same underlying question of how much autonomy to hand an agent, five decades and a very different tech stack later.

Conclusion

STRIPS wasn't built for games at all — it was built to make a physical robot navigate a real corridor, and it took two minutes of theorem-proving to plan six moves. What made it into F.E.A.R. in 2005 wasn't the theorem prover, it was the shape of the problem: preconditions, effects, and a search over the space of possible action sequences. Orkin's four changes — cost-weighted A*, a flat world-state array instead of add/delete lists, procedural preconditions, and procedural effects — are what turned a research robot's two-minutes-per-plan search into something that runs every tick for dozens of NPCs at once. The lineage is real, documented in both authors' own words, and almost never actually read past the GOAP tutorials that cite it secondhand.

All code and configuration excerpts above are reproduced from the original 1971 Fikes & Nilsson STRIPS paper (ai.stanford.edu), Jeff Orkin's 2006 GDC paper "Three States and a Plan" (alumni.media.mit.edu), and the primaryobjects/strips and aibasel/pyperplan GitHub repositories — not reconstructed from description. The pyperplan and cppGOAP install/run commands reflect each repo's own documented usage, not independently verified output.

Sources: Fikes, R.E. & Nilsson, N.J. (1971), "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving," Artificial Intelligence 2(3-4), 189-208. Orkin, J. (2006), "Three States and a Plan: The A.I. of F.E.A.R.," GDC 2006. Becker, K., primaryobjects/strips, MIT License. aibasel/pyperplan, GPLv3. cpowell/cppGOAP.