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 123 CPU-seconds to plan a five-step walk between two rooms — and it's the direct ancestor of F.E.A.R.'s GOAP system, 34 years later. Reading both papers side by side turns up four specific things Jeff Orkin's team changed to make planning fast enough for a real-time game, and one error in Orkin's own account that explains why almost nobody checks.

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., implemented in LISP on a PDP-10, 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, presented at the 2nd IJCAI at Imperial College London on September 1–3, 1971, and published in Artificial Intelligence 2(3-4), 189–208. It's sitting on Nilsson's own Stanford page as a scanned PDF, and almost nobody citing GOAP tutorials seems to have actually opened it.

Worth knowing before you do: the OCR layer on that scan is rough. It renders the operator goto1 as gotol, and it flattens the paper's three-column operator tables into single columns. Half the secondhand errors about STRIPS are downstream of that scan.

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 push operator as the paper gives it in Section 3.5, reproduced exactly:

push(k, m, n)
Precondition: AT(k, m) ∧ ATR(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 "object is at n" and "robot is at n." The paper actually prints this operator twice, in §3.2 and again in §3.5, with the two conjuncts of the precondition in opposite order — a reminder that you're reading a 1971 conference paper, not a spec.

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 the means-ends strategy from GPS, which the paper cites via Ernst and Newell: 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 add-list clauses could resolve away clauses in that difference become candidates, their preconditions become new subgoals, and the process recurses. The paper's own diagram represents this as a tree of (world model, goal list) node pairs, and it's explicit that the result combines forward and backward search: when an operator is found relevant, nothing yet says where in the finished plan it will land.

The architectural decision that made any of this tractable is easy to miss. Green's earlier theorem-proving problem solver did everything through formal proof and choked on the frame problem. STRIPS separates the two jobs completely — the theorem prover only answers questions inside a single world model, while a separate means-ends layer searches between models. Fikes and Nilsson are direct about the payoff: Green's solver couldn't handle their three-box problem at all, and managed only a simpler two-operator version of it.

They were also already worrying about memory. Copying a world model of several hundred formulas at every node was infeasible, so STRIPS keeps all clauses for all models in one store, tags each with a visibility flag, and defines any given world model as two small lists — DELETIONS and ADDITIONS — of differences from the initial model. The theorem prover is then pointed at whichever clauses are currently marked visible. A fixed-size delta against a shared base, rather than a copy per node: the same instinct that shows up in F.E.A.R.'s flat world-state array three decades later.

Game AI isn't intelligent. It's state machines, search, and scoring arranged to feel like judgment, with real, runnable code from FSMs to local LLM dialogue.
SudoSecurity · Amrutanshu

The Three Tasks It Planned

Section 4 of the paper isn't a toy example — it's real performance data from three planning runs against the same world model: a corridor connecting four rooms, described by about thirty axioms, with operators including goto1, goto2, pushto, turnonlight, climbonbox, climboffbox, and gothrudoor.

The three tasks were turning on a lightswitch mounted out of reach, pushing three boxes together, and walking to a specific coordinate in another room.

Those numbers are worth sitting with. The lightswitch task burned 83 seconds inside the resolution theorem prover, out of 113 seconds total, to produce a six-operator plan. The paper says plainly that in all three cases most of the time went to theorem proving in QA3.5, not to the search strategy. That's the actual cost of doing planning the way STRIPS did it — full first-order resolution on every precondition check — and it's exactly the bottleneck GOAP was built to eliminate three decades later.

One detail the article-length retellings always drop: these were planning runs, not robot runs. Footnote 6 says the lightswitch problem is a robot version of the Monkey and Bananas problem — the paper names it, it isn't an unlabeled coincidence — and adds that STRIPS solves it "even though the current SRI robot is incapable of climbing boxes and turning on lightswitches." The planner was ahead of the hardware.

The paper also volunteers that its own search heuristics have a large depth-first component, and that this is why STRIPS returns an "interesting but nonoptimal" solution to the lightswitch task. Read the generated plan and you can see it: the robot goes to BOX1, climbs on it, climbs back off, pushes it to the lightswitch, climbs on again, and only then flips the switch. Two of those six operators cancel each other out.

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

Orkin's paper has a section titled "Differences Between F.E.A.R. and STRIPS Planning," and it lists four specific modifications. The usual summary is that all four were for speed. Only two of them were.

Dropping the theorem prover for a flat array comparison is the speed change, and it's most of why GOAP runs per-tick in a shipping game while STRIPS needed two minutes per plan on a PDP-10. Procedural preconditions are a speed change too, in the other direction: pathfinding is too expensive to keep in world state continuously, so GOAP defers it to a function call made only when a candidate action is being considered.

The cost model isn't about speed at all. Adding A* cost weighting makes the search more expensive, not less. Orkin's reason is plan preference: in his worked example, Alma can satisfy hunger by ordering pizza (cost 2.0) or baking a pie (cost 8.0), and without a cost metric both plans are equally valid, so the planner has no basis to prefer the cheap one. The fourth change, procedural effects, is about honesty rather than performance — moving to a destination or eliminating a threat takes time, and applying the effect at plan time would assert something false for as long as the action is still running.

That fourth row is also the one that connects planning back to the FSM discussion Orkin opens with. F.E.A.R.'s state machine has three states — Goto, Animate, and UseSmartObject — and Orkin immediately concedes that the third is a data-driven variant of the second, so it's really two states. 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. ActivateAction() is the seam: it sets the state and its parameters, and the FSM takes it from there.

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();
};

Worth noting what motivated all of this, because it wasn't research ambition. Orkin writes that F.E.A.R. had exactly one AI programmer and a great many AI characters, and the thought was that if some of the workload could be delegated to the characters themselves, the team would be in good shape. Declarative planning was a staffing decision before it was a technical one.

The Error in Orkin's Own Paper

Here's the part that makes the whole "nobody reads the original" complaint concrete rather than smug.

Orkin's STRIPS primer opens: "STRIPS was developed at Stanford University in 1970, and the name is simply an acronym for the STanford Research Institute Problem Solver."

Both facts in that sentence are wrong, and the sentence contradicts itself as it goes. SRI was Stanford Research Institute, in Menlo Park — a separate organization from Stanford University, which is what the acronym he correctly expands actually says. And the paper is 1971, presented at IJCAI that September and published in that year's volume of Artificial Intelligence.

The reference list explains how. Orkin's STRIPS section cites [Nilsson 1998, and Russell & Norvig 2002] — Nilsson's Artificial Intelligence: A New Synthesis and the second edition of AI: A Modern Approach. Both are excellent textbooks. Neither is the 1971 paper, which appears nowhere in his bibliography.

None of which undermines Orkin's contribution; the four differences he documents are accurate, and the GOAP implementation is his. But the provenance of STRIPS reached the entire game AI community through a secondhand summary, with the institution and the year slightly wrong, and the tutorials downstream inherited both. That's the cost of a citation chain nobody walks back to its source.

Run the Actual Thing

You don't have to take either paper's word for it. A working STRIPS/PDDL implementation exists as an npm package, built by Kory Becker:

$ npm install strips

It's old — v0.0.10, last published to npm around nine years ago — but it installs and runs, and its examples use real PDDL-flavored domain and problem files. Here's the complete examples/blocksworld1/domain.txt, seven lines, reproduced exactly as it sits in the repo:

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

And the matching problem.txt, six lines:

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

Read those carefully, because they are not textbook PDDL and that is itself instructive. The domain file's parentheses don't balance the way a strict PDDL parser would want — the :precondition clause never closes before :effect begins, and the :effect form closes (on ?b ?t2) and then trails (not (on ?b ?t1)) outside it. There's no (:predicates ...) declaration and no (:objects ...) line. The package's PEG.js grammar is permissive enough to accept all of it. If you've only ever seen PDDL in course slides, the real-world version is messier, and tightening these files up before showing them to you would have hidden the actual lesson.

What does map cleanly is the shape. :precondition and :effect correspond directly to Fikes and Nilsson's precondition and add/delete lists, 55 years later, written in PDDL syntax instead of predicate calculus. The (not (on ?b ?t1)) inside the effect is the delete list, folded into the same form rather than kept separate.

Run the package's harder blocks-world problem — unstacking two blocks from one table and restacking them on another, one block or stack per table — and it doesn't print one answer. Its README shows the full depth-first sweep, six solutions from six steps down to three:

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

That's worth comparing against 1971 directly. STRIPS also had no optimality guarantee and also returned a nonoptimal plan for one of its three tasks — but STRIPS stopped at the first plan it proved, where this package enumerates the space and lets you see the three-step answer sitting underneath the six-step one. Same family of search, two different stopping rules.

Andon Labs' AI agent Luna runs a real San Francisco store with real employees, and it just recommended terminating one of them. The headline undersells what actually happened, and what it doesn't prove.
SudoSecurity

More Repos Worth Cloning

Three real repositories, 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, a Towers of Hanoi domain, and a StarCraft domain where the planner works out how to build a barracks. Note that Blocks World is a different canonical domain from the one STRIPS itself was tested against; Fikes and Nilsson's tasks were robot navigation and box-pushing between rooms, not block stacking. Unmaintained but functional.

aibasel/pyperplan (Python, GPLv3) — a lightweight STRIPS/PDDL planner written in the planning practical course at Albert-Ludwigs-Universität Freiburg in winter 2010/11, under Malte Helmert and Robert Mattmüller, and now hosted under the Basel AI group's org. The README says it "deliberately prefers clean code over fast code" and asks anyone using it for paper experiments to state that it doesn't offer state-of-the-art performance. That makes it the one to read start to finish. Documented usage:

$ uv tool install pyperplan
$ 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. For a heuristic search instead of the default, pyperplan -H hff -s gbfs DOMAIN PROBLEM runs greedy best-first with FF.

The detail that closes the loop: pyperplan's README states it supports "STRIPS without action costs." Fifty-five years on, the reference teaching implementation of STRIPS still has the exact gap Orkin had to fill to ship F.E.A.R.

cpowell/cppGOAP (C++11, 105 stars) — a from-scratch GOAP planner whose README says it "is inspired by Jeff Orkin's writings," links his GOAP page directly, and treats "each worldstate as a 'node' on a possible path" searched with A*, exactly as the GDC paper describes. It ships a shooter-AI example with verbose output a real game would suppress. Closer to an engine planner than either STRIPS repo above, because it's built around the cost-per-action model GOAP added rather than a bare 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 on a PDP-10 — make clear this was never going to run at interactive speed without the changes GOAP made. Fikes and Nilsson say they don't attach much importance to the timings, since most of the code ran interpreted, but the order of magnitude is the point.
• No optimality guarantee. This is the nuance the secondhand summaries flatten into "no cost model." The evaluation function picking which node to expand next does weigh the cost of operators applied so far, among other factors. What's missing is any guarantee the returned plan is the cheapest — STRIPS accepts the first plan it proves, and the paper admits its depth-first lean produced a nonoptimal lightswitch solution. Preferring one valid plan over another on cost, the way Orkin's pizza-versus-pie example needs, requires the per-action cost metric GOAP added.
• No concurrency. Plans are strictly sequential operator applications; nothing in the 1971 formalism represents two actions happening in parallel. That's precisely why Orkin points squad-AI developers toward Hierarchical Task Network planning instead, and why F.E.A.R.'s own squad behaviors were never run through the planner at all — Orkin says the formal STRIPS-like system drove individual characters only, and squad coordination was "something more ad-hoc."
• No learning from past solutions. Section 5 of the paper describes wanting STRIPS to define new generalized operators for itself from previous solutions, and cites Hart and Nilsson's work on generalized plans as a promising approach. The paper is explicit that this was future work, not something the 1971 implementation did.
• No partial observability. The world model is assumed fully known and static during planning; nothing changes it mid-search. The execution-monitoring problem — what the robot does when the world turns out different — was handled by separate systems, in the companion papers by Munson and by Fikes that the 1971 paper cites.
  For a different angle on how modern AI systems are handed 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.

Why the Lineage Still Matters

STRIPS wasn't built for games at all. It was built to make a physical robot navigate a real corridor, and on its slowest task it spent 105 seconds of theorem proving, inside 123 seconds total, to produce a five-step plan.

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 planner's two-minutes-per-plan search into something that runs every tick for dozens of NPCs at once.

The lineage is real and documented in both authors' own words. It's also slightly garbled in the one document the games industry actually read, which had the institution and the year wrong because it was working from textbooks rather than the paper. Fifty-five years of citations, and the fix was a free PDF and twenty minutes.

Code and configuration in this article come from three places, and they are not equivalent. The push operator is reproduced from §3.5 of the 1971 Fikes & Nilsson STRIPS paper (ai.stanford.edu), and the Action class from Jeff Orkin's 2006 GDC paper (alumni.media.mit.edu). The two PDDL files and the solver output are reproduced byte-for-byte from the primaryobjects/strips repository, unbalanced parentheses included. The npm, pyperplan, and cppGOAP commands are each repository's own documented usage; we did not run them against these specific benchmarks, so treat the outputs as documented rather than independently reproduced.