Loading field map
Planning and search is the subfield of artificial intelligence concerned with how an autonomous system can decide, in advance, what to do. Its central subject is the problem of acting intelligently in a world the system can only partially observe and predict. The field studies both the abstract mathematics of such problems and the practical algorithms that solve them, and it has produced some of the most durable ideas in AI, from the search algorithms that power navigation systems to the planning formalisms that underpin robotics and automated scheduling.
At its core, planning is the task of finding a course of action that achieves a goal. The system begins in some initial state, can perform a set of actions, and each action transforms the state in a predictable (or at least modelable) way. The planner must select a sequence of actions—a plan—that leads from the initial state to a state satisfying the goal. Search is the general computational method for exploring the space of possible action sequences to find such a plan.
The difficulty of this problem varies enormously with its structure. In the simplest case, the world is fully observable, deterministic, and static: the planner knows everything about the current state, each action has exactly one outcome, and nothing changes except through the planner's own actions. This is the classical planning setting, and even here the problem is computationally hard in general. The state space grows exponentially with the number of variables, and finding a plan can require exploring a vast tree of possibilities.
Realistic problems add further complications. Actions may have probabilistic outcomes, the world may be only partially observable, other agents may act unpredictably, and goals may be complex conditions over time rather than simple end states. Each of these extensions changes the nature of the problem and demands different techniques. The field's history is largely the story of how researchers developed increasingly expressive models and increasingly efficient algorithms to handle them.
The earliest work in AI planning, in the 1950s and 1960s, treated planning as a form of problem solving. The influential General Problem Solver (GPS) developed by Allen Newell and Herbert Simon attempted to solve problems by comparing the current state to the goal and selecting actions that reduce the difference. This means–ends analysis was a precursor to modern planning, though it lacked a general way to represent actions and states.
The field took its modern shape with the development of the Stanford Research Institute Problem Solver (STRIPS) in the late 1960s and early 1970s. STRIPS introduced a formal language for describing planning problems that remains the basis of the field's standard notation. A state is a set of logical facts (e.g., "robot-at-roomA"), an action is described by its preconditions (facts that must hold before it can be executed) and its effects (facts it adds or deletes). A planning problem is then a triple: an initial state, a set of actions, and a goal condition. This representation is simple but powerful, and it made planning amenable to rigorous algorithmic study.
The most straightforward way to solve a STRIPS planning problem is state-space search. The planner starts at the initial state and considers all applicable actions, generating successor states, then continues until it reaches a state satisfying the goal. The classic algorithms for this are the uninformed searches—breadth-first search, depth-first search, iterative deepening—and, more importantly, informed searches that use a heuristic function to estimate the distance to the goal. The A* algorithm, developed in the late 1960s, remains the canonical informed search method: it expands states in order of the sum of the cost already incurred and a heuristic estimate of remaining cost, and it is guaranteed to find an optimal plan if the heuristic never overestimates the true remaining cost.
The central challenge in state-space search is the heuristic. A poor heuristic leads to exploring enormous numbers of states; a good one can make the difference between solving a problem in milliseconds and never solving it at all. Much of the research in classical planning has therefore focused on how to derive heuristics automatically from the problem description. One influential family of methods relaxes the problem—for example, by ignoring the delete effects of actions (treating facts as never becoming false once they become true)—and uses the length of the optimal plan in this relaxed problem as a heuristic for the original one. Another family abstracts the state space by grouping states into equivalence classes and uses the distances between abstract states as guidance. These techniques, developed from the 1990s onward, made it possible to solve planning problems with thousands of actions and variables, a scale that would have seemed impossible in the early decades of the field.
An alternative to searching through states is to search through partial plans. In plan-space planning, the planner starts with an incomplete plan—a set of actions with some ordering constraints and causal links—and refines it by adding actions or constraints until it becomes a complete, executable plan. The most influential early system of this kind was the Nonlinear Planning Using Constraint Posting (NONLIN) system and, later, the Universal Nonlinear Planner (UNPOP) and its successors. The key insight is that a plan can be represented as a partial order of actions, and the planner can reason about the plan's structure directly rather than about the states it passes through.
Plan-space planning was theoretically elegant and influenced the development of partial-order planning as a distinct research tradition. However, it proved difficult to scale to large problems, and by the 1990s it had largely been superseded by other approaches. Its legacy persists in the idea that planning can be viewed as a constraint satisfaction problem, and in the formal analysis of plan structures.
A more consequential development came from a different direction. In the early 1990s, researchers realized that a bounded planning problem—"is there a plan of length at most k?"—can be translated into a propositional satisfiability (SAT) problem. The translation encodes the initial state, the actions available at each time step, and the goal condition as logical formulas, and a SAT solver is then used to determine whether the formulas are satisfiable. If they are, the satisfying assignment encodes a valid plan. This approach, known as SAT-based planning, was initially met with skepticism because SAT solving itself was considered intractable in the worst case. But the dramatic progress in SAT solver technology during the 1990s—driven by the development of conflict-driven clause learning and efficient data structures—made SAT-based planning surprisingly effective. It remains one of the strongest approaches for classical planning, particularly for problems where the plan length is known or can be bounded.
The relationship between state-space search and SAT-based planning is instructive. They are not rival theories of planning but rather different computational strategies for the same underlying problem. State-space search works forward from the initial state; SAT-based planning works by constructing a candidate plan skeleton and checking it globally. Each has strengths and weaknesses, and modern planners often combine ideas from both.
Classical planning assumes that actions are atomic and instantaneous. Real-world planning often requires reasoning about actions at multiple levels of abstraction, and about actions that take time and use resources. Two extensions of the classical framework address these needs.
Hierarchical task network (HTN) planning, developed in the 1970s and 1980s, is based on the idea that a planner should work with tasks rather than primitive actions. A task is an abstract activity (e.g., "prepare a meal") that can be decomposed into subtasks (e.g., "gather ingredients," "cook," "serve") according to a set of methods. The planner starts with a high-level task and repeatedly decomposes it until it reaches primitive actions that can be executed directly. HTN planning is not a special case of classical planning; it is a different problem because the planner is given not just a goal but a library of decomposition methods that encode domain knowledge. This makes HTN planning more expressive and often more efficient for domains where such knowledge is available, but it also means the planner's competence depends heavily on the quality of the method library. HTN planning has been widely used in practice, particularly in military logistics, manufacturing, and game AI.
Temporal planning extends the classical model by associating actions with durations and allowing them to overlap. The planner must produce a schedule—a set of actions with start and end times—that achieves the goal while respecting resource constraints and temporal dependencies. This is closely related to scheduling problems studied in operations research, and temporal planners often integrate techniques from both fields. The standard approach is to represent the problem as a set of constraints over time points and to search for a consistent assignment. Temporal planning is important in applications such as space mission planning, where actions have long durations and must be coordinated with each other.
Classical planning assumes deterministic action outcomes. When actions can fail or have multiple possible effects, the planner must reason about uncertainty. The standard formal model for this setting is the Markov decision process (MDP), which describes a system in terms of states, actions, transition probabilities, and rewards. The planning problem becomes: find a policy—a mapping from states to actions—that maximizes the expected cumulative reward.
MDPs were developed in the 1950s in the field of operations research, and they entered AI planning in the 1980s and 1990s as researchers sought to extend planning to stochastic domains. The classical algorithms for solving MDPs are dynamic programming methods: value iteration, which repeatedly updates an estimate of the value of each state, and policy iteration, which alternates between evaluating a policy and improving it. These algorithms are guaranteed to converge to an optimal policy, but they require enumerating the state space, which is often infeasible for large problems.
The challenge of scaling MDP methods led to the development of factored MDPs, which exploit the structure of the state space by representing the transition and reward functions compactly, and to approximate methods that compute good but not guaranteed-optimal policies. A particularly influential idea is the use of heuristic search in the space of states, treating the MDP as a kind of stochastic search problem. The LAO algorithm and its successors combine the ideas of A with dynamic programming to find optimal policies without exploring the entire state space.
A related but distinct model is the partially observable Markov decision process (POMDP), in which the system cannot directly observe the state but receives observations that provide partial information. Planning in a POMDP requires reasoning about beliefs—probability distributions over states—and the optimal policy is a function from beliefs to actions. POMDPs are extremely expressive but computationally very hard; exact solution is possible only for small problems, and most practical work uses approximate methods. POMDP planning has become an active research area in robotics, where a robot must act based on noisy sensor data.
The field of planning and search has a distinctive intellectual culture. It is strongly empirical: researchers evaluate algorithms on benchmark problem sets, and the International Planning Competition, held regularly since 1998, has been a major driver of progress. The competition defines standard problem domains, runs planners under controlled conditions, and publishes results, creating a shared experimental culture that is rare in AI subfields.
At the same time, planning has a strong theoretical component. Researchers study the computational complexity of planning problems, establishing which variants are tractable and which are not. For example, classical planning with STRIPS actions is PSPACE-complete in general, but restricted classes of problems are easier. This theoretical work provides a map of the field's difficulty landscape and guides the design of algorithms.
The relationship between planning and other areas of AI is complex. Planning is sometimes contrasted with reinforcement learning, which learns policies from experience rather than from a model. In practice, the two are complementary: model-based planning can be used to accelerate learning, and learned models can be used for planning. Planning also overlaps with constraint satisfaction, since many planning problems can be formulated as constraint problems, and with automated reasoning, since the logical formalisms of planning are closely related to those of theorem proving.
The practical impact of planning and search is substantial. Search algorithms are embedded in navigation systems, web search, and game-playing programs. Planning technology is used in logistics, manufacturing, autonomous vehicles, and space exploration—NASA has used AI planners to schedule spacecraft operations. The field's formalisms have also influenced other areas of computer science, including program synthesis and database query optimization.
The current landscape of the field is characterized by a pragmatic eclecticism. Classical planning remains an active area, with ongoing work on improving heuristics and scaling to larger problems. Probabilistic planning has become increasingly important as robots and autonomous systems must operate in uncertain environments. Hierarchical and temporal planning are used in applications where domain knowledge and time constraints matter. And the boundaries between planning and learning have become increasingly porous, with modern systems often combining learned models, learned heuristics, and classical planning algorithms. The field's enduring contribution is not any single algorithm but a set of formal tools for thinking about action and change, and a body of algorithmic techniques that make intelligent action possible in a wide range of domains.