- Atlas
- Computer Science
- Planning And Search
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
- Adversarial game-tree search 1956-Present
- Markov decision process 1957-Present
- State-space search 1957-Present
- Means-ends analysis 1959-1985
- Heuristic search 1968-Present
- Classical action representation and planning 1971-Present
- Hierarchical task network 1975-Present
- Belief–desire–intention software model 1990-2015
- Partially observable Markov decision process 1990-Present
- Temporal and scheduling planning 1990-Present
- Constraint satisfaction and SAT-based planning 1992-Present
- Heuristic planning from relaxed models 1995-Present
- Automated planning competition benchmarking 1998-Present
- Monte Carlo tree search 2006-Present
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
- Automated planning and scheduling (introduction, Overview, Reduction to other problems), Wikipedia
- Heuristic (computer science) (Search), Wikipedia
- Alpha–beta pruning (introduction, History), Wikipedia
- Means–ends analysis, Wikipedia
- Stanford Research Institute Problem Solver, Wikipedia
- Planning Domain Definition Language, Wikipedia
- Constraint satisfaction problem, Wikipedia
- Graphplan, Wikipedia
- Markov decision process, Wikipedia
- Dynamic programming, Wikipedia
- Partially observable Markov decision process, Wikipedia
- 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.
- 1956-Present
Adversarial game-tree search
What move should I make against an opponent who plays well?
- 1957-Present
Markov decision process
Which action maximizes expected reward when outcomes are uncertain?
- 1957-Present
State-space search
How do I find a path from start to goal through possible situations?
- 1959-1985
- 1968-Present
Heuristic search
How can a rule of thumb make search fast enough to be useful?
- 1971-Present
Classical action representation and planning
How should actions be described so a machine can chain them into a plan?
- 1975-Present
Hierarchical task network
How can a big task be broken into smaller tasks and steps?
- 1990-2015
Belief–desire–intention software model
How can an agent commit to plans while staying open to new information?
- 1990-Present
Partially observable Markov decision process
How should an agent act when it cannot see its true situation?
- 1990-Present
Temporal and scheduling planning
How do I schedule actions with durations and deadlines?
- 1992-Present
Constraint satisfaction and SAT-based planning
Can planning be reduced to solving a set of logical constraints?
- 1995-Present
Heuristic planning from relaxed models
Can a planner derive its own guidance from a simplified problem?
- 1998-Present
Automated planning competition benchmarking
How do we compare planners fairly on shared problems?
- 2006-Present
Monte Carlo tree search
Can random sampling guide search better than exhaustive evaluation?
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.
Partially observable Markov decision process grew out of Markov decision process
Partially observable MDPs extended the Markov decision process to hidden state by replacing the known state with a belief distribution. The value-function and expected-reward machinery of the MDP was carried over to belief-space planning.
Heuristic search grew out of State-space search
Heuristic search grew directly out of state-space search by adding an estimate of remaining distance to guide node expansion. The A* algorithm of Hart, Nilsson and Raphael formalized this as best-first search with an admissible evaluation function.
Carried by Peter Hart; Nils Nilsson; A* (1968).
Heuristic planning from relaxed models grew out of Heuristic search
Heuristic planning from relaxed models grew out of heuristic search by automatically deriving the heuristic from a relaxed planning problem rather than hand-tuning it. Planners such as FF combined A*-style search with delete-relaxation estimates.
Carried by Jörg Hoffmann; Bernhard Nebel.
State-space search grew out of Adversarial game-tree search
Game-tree search applied the state-space formulation to two-player games, treating positions as nodes and moves as edges and searching the resulting tree with minimax. The same graph-search machinery was adapted to an adversarial setting.
Carried by John McCarthy; Claude Shannon.
Monte Carlo tree search grew out of Adversarial game-tree search
Monte Carlo tree search replaced exhaustive minimax evaluation in game trees with sampled playouts and a growing selective tree. It kept the adversarial game-tree setting while abandoning full-width search.
Monte Carlo tree search influenced by Markov decision process
Monte Carlo tree search estimates action values by sampling and uses the reward-and-transition structure of decision processes to guide tree growth. Its rollout-based value estimates draw on the same sequential-decision formulation.
Means-ends analysis influenced by State-space search
Means-ends analysis in the General Problem Solver operated over a state space of situations and operators, using differences between states to select operators. Newell and Simon built on the state-space picture while adding goal-directed operator selection.
Carried by Allen Newell; Herbert Simon; General Problem Solver (1959).
Classical action representation and planning influenced by State-space search
Classical planners searched a state space whose nodes were sets of logical facts and whose edges were STRIPS operators. The state-space formulation supplied the search framework within which action representations were defined.
Carried by Richard Fikes; Nils Nilsson.
Classical action representation and planning influenced by Means-ends analysis
STRIPS inherited from means-ends analysis the idea of operators with preconditions and effects that a planner chains toward a goal, and its planning was framed as reducing differences between states. Fikes and Nilsson replaced the general difference table with explicit add and delete lists.
Carried by Richard Fikes; Nils Nilsson; STRIPS (1971).
Hierarchical task network grew out of Classical action representation and planning
Hierarchical task network planning extended classical action representation by decomposing tasks into subtasks, with primitive actions described in STRIPS-like terms. It added hierarchical structure on top of the precondition-effect action model.
Carried by Earl Sacerdoti.
Temporal and scheduling planning grew out of Classical action representation and planning
Temporal planning extended the classical action model by adding start times, end times and duration constraints to preconditions and effects. The STRIPS-style representation was kept but enriched with a temporal layer.
Constraint satisfaction and SAT-based planning influenced by Classical action representation and planning
SAT-based planning encoded classical planning problems, with their STRIPS-style actions and states, as propositional satisfiability instances. Kautz and Selman translated the action representation into Boolean clauses over a bounded plan length.
Carried by Henry Kautz; Bart Selman.
Heuristic planning from relaxed models influenced by Classical action representation and planning
The relaxed-model heuristics were computed over STRIPS-style action descriptions by ignoring delete lists. Classical action representation supplied the problem structure from which the heuristic was extracted.
Carried by Jörg Hoffmann; Bernhard Nebel.
Automated planning competition benchmarking influenced by Classical action representation and planning
The International Planning Competition standardized its benchmark problems in PDDL, the planning domain definition language descended from STRIPS. Competition benchmarking was built on the classical action representation.
Carried by International Planning Competition (1998).
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.
Adversarial game-tree search influenced Self-play in Game Playing Ai
Self-play in checkers and chess was run by playing the same adversarial game-tree search against itself, so the search procedure is the mechanism that generates the training games. Samuel's 1959 checkers program used self-play on top of minimax search.
Carried by Arthur Samuel.
Adversarial game-tree search influenced Knowledge-Based Chess AI in Game Playing Ai
Knowledge-based chess programs kept adversarial game-tree search as their skeleton and added hand-crafted evaluation knowledge on top of it. The alpha-beta search of the 1960s remained the engine into which chess heuristics were inserted.
Adversarial game-tree search led to Brute-Force Search and Special-Purpose Hardware in Game Playing Ai
Brute-force chess hardware was a direct scaling-up of adversarial game-tree search: the same alpha-beta minimax algorithm, pushed to greater depth by special-purpose chips. The later approach is the earlier search method carried to its hardware limit.
Adversarial game-tree search led to Monte Carlo Tree Search in Game Playing Ai
Monte Carlo tree search grew out of adversarial game-tree search by replacing exhaustive minimax backup with statistical sampling of playouts. The tree structure, selection and backup machinery were inherited from the earlier minimax search tradition.
Adversarial game-tree search influenced by Minimax theorem in Game Theory
The minimax theorem for two-person zero-sum games is the mathematical basis for backing up values in an adversarial game tree. Chess-program designers in the late 1940s and 1950s took the minimax rule directly from game theory.
Carried by John von Neumann; Theory of Games and Economic Behavior (1944).
Adversarial game-tree search influenced by Zero-Sum Games and Minimax Theorem in Game Theory
Von Neumann and Morgenstern's minimax theorem for zero-sum games supplied the evaluation rule that game-playing programs applied to alternating-move game trees. Shannon and Turing cited game theory when proposing chess programs in 1950.
Carried by John von Neumann; Oskar Morgenstern; Theory of Games and Economic Behavior (1944).
Markov decision process influenced Planning Under Uncertainty in Robot Motion Planning
Planning under uncertainty is built directly on the Markov decision process formalism, extending it to partially observable settings via POMDPs. The MDP supplied the state, action, transition and reward structure that the planners use.
Markov decision process influenced by Markov chain in Stochastic Processes
The Markov chain, formalised by Markov from 1906, is the stochastic substrate of the MDP. Bellman's 1957 formulation added decisions and rewards to the Markov transition structure.
Carried by Andrey Markov; Richard Bellman.
Markov decision process influenced by Markov chain in Stochastic Modeling
The Markov chain's memoryless transition structure is the core of the MDP; Bellman added actions, rewards and control to Markov's stochastic process. Without the Markov property the MDP formalism would not exist.
Carried by Andrey Markov; Richard Bellman.
Classical action representation and planning provoked Reactive planning in Robot Motion Planning
Reactive planning arose as a direct attack on classical symbolic planning, arguing that explicit world models and search over action representations were the wrong basis for robot control. Brooks's subsumption architecture was framed as a rejection of the STRIPS-style planning tradition.
Carried by Rodney Brooks.
Belief–desire–intention software model influenced by Planning Theory of Intention in Philosophy Of Action
Bratman's planning theory of intention supplied the core commitment that intentions are conduct-controlling, partial plans that constrain and guide later reasoning. The BDI software model's makers took this directly as the specification for agent deliberation and means-end reasoning.
Carried by Michael Bratman; Intention, Plans, and Practical Reason (1987).
Partially observable Markov decision process grew out of Markov decision process in Stochastic Modeling
The POMDP is a direct generalisation of the Markov decision process to the case where the agent cannot observe the state directly but only receives noisy observations. It keeps the MDP's reward and transition formalism and adds a belief-state layer on top.

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 SearchRelated fields
Fields its ideas are linked to
- Game Playing Ai 7 links
- Life And Death 4 links
- Robot Motion Planning 4 links
- Operations Research 3 links
- Production Planning And Control 3 links
- Stochastic Modeling 2 links
- Applied Mathematics 2 links
- Philosophy Of Action 2 links
- Stochastic Processes 2 links
- Knowledge Representation Reasoning 1 link
- Probabilistic Ai 1 link
- Algorithms 1 link
More in Artificial Intelligence
- Ai Ethics And Fairness
- Ai Safety
- Artificial Intelligence
- Computer Vision
- Deep Learning
- Evolutionary Computation
- Knowledge Representation Reasoning
- Machine Learning
- Multiagent Systems
- Natural Language Processing
- Probabilistic Ai
- Reinforcement Learning
- Speech Recognition And Synthesis
See where Planning And Search sits on the Map of Human Knowledge