Planning And Search

Planning and search is the branch of artificial intelligence concerned with getting a machine to find a course of action: to work out which sequence of moves, steps, or operations will take it from where it is to where it wants to be.

14 frameworks, from 1956 to today · Artificial Intelligence · Computer Science

still a working view ended · each leads to its entry below

Overview

Planning and search is the branch of artificial intelligence concerned with getting a machine to find a course of action: to work out which sequence of moves, steps, or operations will take it from where it is to where it wants to be1. The search half is the machinery of looking through possibilities efficiently; the planning half is the question of how to represent what an action does and how to assemble actions into a workable plan. What is at stake is deliberation itself—the difference between a system that reacts and a system that thinks ahead. This is one of the oldest and most durable parts of AI, and its ideas about heuristics, state spaces, and decision-making under uncertainty run quietly through the modern field.

Search as the First Model of Thinking: State Spaces and Heuristics

In the 1950s and 1960s, researchers treated problem-solving as moving through a state space: a graph in which each node is a complete description of a situation and each edge is a legal move. Solving a puzzle, proving a theorem, and playing a game all became the same task—find a path from a start node to a goal node. The brute-force methods, breadth-first and depth-first search, were correct but exploded in cost as problems grew.

The decisive idea was the heuristic: a rule of thumb that estimates how far a node is from the goal and guides the search toward promising directions2. In 1968 Peter Hart, Nils Nilsson, and Bertram Raphael at SRI International published the A\ algorithm, which combines the cost already paid with a heuristic estimate of the remaining cost. When the estimate never overstates the true distance—an admissible heuristic—A\ is guaranteed to find an optimal path while expanding far fewer nodes than blind search. Their paper demonstrated it on a route-planning problem, and the algorithm became one of the most cited in AI. The heuristic-search tradition that grew from this work, including game-playing search, established the pattern of trading guaranteed completeness for practical speed.

Playing Games: Adversarial Search Against an Opponent

Games gave search a natural adversary. In adversarial game-tree search, one player's gain is the other's loss, so the machine must assume the opponent plays well3. The minimax principle—choose the move that maximizes your outcome assuming the opponent minimizes it—dates to John von Neumann's game theory of the 1920s and was adapted to trees of moves. The alpha–beta pruning technique, developed and named in the late 1950s and early 1960s (John McCarthy is credited with the idea around 1956), skips branches that cannot possibly affect the result, letting the same search see much deeper3.

These methods showed their power when IBM's Deep Blue defeated world chess champion Garry Kasparov in a 1997 six-game match. Deep Blue paired massive parallel hardware with carefully tuned evaluation functions, searching hundreds of millions of positions—a triumph of the classical approach. Its later descendant in the game of Go, however, would not come from deeper minimax, a story taken up below.

Means–Ends Analysis and the GPS

While A\ searched a given space, a different tradition asked how to construct* the space and the steps. Means–ends analysis compares the current state with the goal, identifies the difference, and selects an operator known to reduce that difference—recursing on the subgoals this creates4. It was embodied in the General Problem Solver (GPS), built by Allen Newell and Herbert Simon with Cliff Shaw at Carnegie Mellon, reported in 1959. GPS was a deliberate attempt at a domain-general problem-solver, and its program separation of a "means–ends analysis" from domain-specific knowledge was influential. Its limits were equally instructive: it worked on puzzles and simple logic but struggled when subgoals interfered with one another.

STRIPS and the Representational Turn

The bottleneck became representation. In 1971 Richard Fikes and Nils Nilsson introduced STRIPS (Stanford Research Institute Problem Solver), a formalism for describing actions in a way a planner could reason over5. Each action was specified by three lists: preconditions (facts that must hold to apply it), an add list (facts it makes true), and a delete list (facts it makes false). Plans could be built and then verified by simulating these changes on a set of logical facts.

STRIPS and its relatives, such as the planning domain definition language (PDDL) standardized in 1998 for a planning competition, gave the field a clean, sharable way to state problems6. The classical planning problem—find a sequence of actions from an initial state to a goal, given deterministic actions—became the field's reference point1. But STRIPS-style plans said nothing about when things happen.

Temporal and Scheduling Planning

Real tasks have deadlines, durations, and resource conflicts. Temporal and scheduling planning extended action descriptions with start and end times and duration constraints, and merged with the older operations-research tradition of scheduling. A visible milestone was NASA's Remote Agent experiment in 1999, when an autonomous planning system controlled the Deep Space 1 spacecraft, generating and executing its own activity plans. The system combined a temporal planner with a scheduler and executed plans on a probe millions of kilometres away—evidence that these methods could run where mistakes are irreversible.

Constraint Satisfaction and SAT-Based Planning

A parallel strand reframed combinatorial problems as constraint satisfaction: assign values to variables so that stated constraints all hold (the map-colouring problem is the textbook case)7. By the 1990s, SAT-based planning recast a planning problem as a propositional satisfiability question—encode the action sequence as Boolean variables, add clauses that forbid illegal transitions, and hand it to a fast SAT solver18. The approach, associated with work such as Henry Kautz and Bart Selman's around 1992, showed that a general-purpose satisfiability engine could solve planning problems competitively, and it blurred the line between planning and a broader family of search-and-constraint techniques.

Planning as a Competition and a Discipline

A turning point for the field as a community was the creation of the International Planning Competition (IPC), first held in 1998 alongside the AIPS conference. Competitions standardized problem sets (in PDDL), compared planners on shared benchmarks, and pushed progress on speed and coverage6. Automated planning competition benchmarking became the field's shared measuring stick—sometimes criticized for encouraging narrow optimization, but undeniably effective at turning planning into an empirical science with comparable results.

Belief–Desire–Intention and Deliberative Agents

At the agent level, the question shifted from one plan to sustained behaviour. The belief–desire–intention (BDI) model, developed by Michael Bratman as a philosophical account of human practical reasoning in the 1980s and adopted into AI by Anand Rao and Michael Georgeff in the 1990s, described an agent by its beliefs (what it takes to be true), desires (what it wants), and intentions (what it has committed to do). BDI systems supported commitment and reconsideration, giving practical agents a principled way to persist with plans without ignoring new information.

Planning Under Uncertainty: MDPs and POMDPs

Classical planning assumed actions always succeed1. The real world does not cooperate. The Markov decision process (MDP), studied in operations research before entering AI, models actions with probabilistic outcomes and assumes the agent can see its current state19. The key—stated most clearly in the work of Richard Bellman in the 1950s—is that optimal behaviour can be computed by solving for a value function over states and choosing the action that maximizes expected reward10. The partially observable MDP (POMDP) extends this to situations where the agent cannot directly see its state but must act on beliefs—probability distributions over possible states111. Exact POMDP solving is computationally brutal, and a series of approximation algorithms since the 1990s made the framework practical for problems like robot navigation and dialogue. This probabilistic, reward-driven view of sequential decision-making is the direct ancestor of modern reinforcement learning9.

Heuristic and Deterministic Planning Come Together

From the 1990s onward, heuristic search met symbolic planning head-on. Planners such as FF, which won the 2000 IPC, derived a heuristic automatically from a relaxed version of the problem—pretending delete lists were empty to get an optimistic estimate—and searched with it. This "planning as heuristic search" view, associated with work by Jörg Hoffmann and Bernhard Nebel, showed that you did not need hand-tuned heuristics: the action model itself could supply them. It reconciled the classical representational tradition with the search tradition that had grown up separately.

Hierarchical task network (HTN) planning offered another reconciliation12. Instead of searching for a sequence of primitive actions, an HTN planner decomposes a high-level task into subtasks using methods, recursively, until primitive operators remain12. This captures expertise as recipes and procedures, and proved valuable where domain knowledge of how to do things outweighs search—NASA's Remote Agent used a form of HTN reasoning. HTN remains the practical backbone in several deployment contexts, from game AI to industrial automation.

The Present: Learning, Sampling, and the Old Questions

Today the field is a patchwork of living traditions. Classical planners with strong heuristics remain the baseline. Probabilistic methods from MDPs and POMDPs, now supercharged by reinforcement learning, dominate robotics and control. Monte Carlo tree search—which samples game trees instead of enumerating them, guided by learned evaluations—supplied the breakthrough that defeated a top human Go player in 2016 (AlphaGo), fusing adversarial search with learning in a way classical minimax could not. HTN and constraint-based methods continue in domains where procedure matters more than raw optimization.

The open questions are old ones in new dress: how to scale planning to huge, uncertain, partially observable worlds; how to combine learned heuristics and policies with the verifiable structure of symbolic planning; and how autonomous agents should plan with commitments when information keeps arriving. What began as graph search and a list of add-and-delete facts is now a framework for how any deliberative machine—from a spacecraft to a game engine to a foundation-model-based agent—decides what to do next.

References

  1. Automated planning and scheduling (introduction, Overview, Reduction to other problems), Wikipedia
  2. Heuristic (computer science) (Search), Wikipedia
  3. Alpha–beta pruning (introduction, History), Wikipedia
  4. Means–ends analysis, Wikipedia
  5. Stanford Research Institute Problem Solver, Wikipedia
  6. Planning Domain Definition Language, Wikipedia
  7. Constraint satisfaction problem, Wikipedia
  8. Graphplan, Wikipedia
  9. Markov decision process, Wikipedia
  10. Dynamic programming, Wikipedia
  11. Partially observable Markov decision process, Wikipedia
  12. Hierarchical task network, Wikipedia

The frameworks of Planning And Search

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1957-Present

    Markov decision process

    Which action maximizes expected reward when outcomes are uncertain?

    Fly to its tower in Nousfarer

  2. 1959-1985
  3. 1971-Present

    Classical action representation and planning

    How should actions be described so a machine can chain them into a plan?

    Fly to its tower in Nousfarer

  4. 1975-Present

    Hierarchical task network

    How can a big task be broken into smaller tasks and steps?

    Fly to its tower in Nousfarer

  5. 1990-2015

    Belief–desire–intention software model

    How can an agent commit to plans while staying open to new information?

    Fly to its tower in Nousfarer

  6. 1990-Present

    Partially observable Markov decision process

    How should an agent act when it cannot see its true situation?

    Fly to its tower in Nousfarer

  7. 1990-Present

    Temporal and scheduling planning

    How do I schedule actions with durations and deadlines?

    Fly to its tower in Nousfarer

  8. 1992-Present

    Constraint satisfaction and SAT-based planning

    Can planning be reduced to solving a set of logical constraints?

    Fly to its tower in Nousfarer

  9. 1995-Present

    Heuristic planning from relaxed models

    Can a planner derive its own guidance from a simplified problem?

    Fly to its tower in Nousfarer

  10. 1998-Present

    Automated planning competition benchmarking

    How do we compare planners fairly on shared problems?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Adversarial game-tree searchMarkov decision processState-space searchMeans-ends analysisHeuristic searchClassical action representation and p…Hierarchical task networkBelief–desire–intention software modelPartially observable Markov decision …Temporal and scheduling planningConstraint satisfaction and SAT-based…Heuristic planning from relaxed modelsAutomated planning competition benchm…Monte Carlo tree search

Beyond the field

Where Planning And Search's ideas came from in other fields, and what they led to there: the strongest 12 of 42 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Planning And Search is a planet in Nousfarer

Its city has a tower for each of these 14 frameworks. Land, walk in, and climb one concept at a time.

Land on Planning And Search

Related fields

Fields its ideas are linked to

More in Artificial Intelligence

See where Planning And Search sits on the Map of Human Knowledge