RESEARCH DOSSIER
Planning and Search in Artificial Agents
Abstract. Planning and search in artificial agents concern the construction, evaluation, revision, and execution of action sequences aimed at goals under computational, informational, and environmental constraints. This research monograph traces the development from shortest-path and heuristic-search theory through symbolic and probabilistic planning, reinforcement-learning systems, Monte Carlo tree search, learned dynamics, and contemporary language-model agents. A critical narrative evidence review distinguishes mathematical guarantees in formal models from laboratory benchmarks and outcomes in open-ended settings. It analyzes goal representation, state abstraction, heuristic guidance, uncertainty, action costs, online feedback, verification, and replanning. The synthesis shows that performance depends jointly on the model of the environment, the search procedure, feedback access, objective specification, and the reliability of execution. Modern language agents broaden the interface to tools and text but retain substantial difficulties with feasibility, global constraints, long-horizon dependencies, and dynamic environments. Evidence concerning planning competence does not establish subjective intention or other psychological experience. The work outlines a comparative research framework for testing formal planners, learned planners, and language agents with transparent constraints and independent validation. This is a critical narrative scientific synthesis, not an experimental study, PRISMA systematic review, or meta-analysis.
Keywords: artificial agents; planning; heuristic search; state-space search; A*; STRIPS; classical planning; partially observable Markov decision process; model-based reinforcement learning; Monte Carlo tree search; MuZero; language agents; task decomposition; replanning; constraint satisfaction; agent evaluation; Artificial Era
The Scientific Object of Artificial Planning
Planning in an artificial agent is the computational construction or selection of actions whose anticipated consequences satisfy an objective under specified constraints. Search is the exploration of candidate states, actions, plans, policies, or reasoning continuations used to make such a selection. The two functions overlap, because planning typically requires search over possible futures, while search may serve retrieval or proof rather than action. Their scientific analysis begins with a precise account of what the agent receives, what it can do, how an environment changes, what counts as success, and how much computation may be spent before acting. The difference between producing a plausible sequence and producing a valid plan is central: a valid plan has executable steps that preserve or satisfy the required conditions under the assumed transition model Fikes & Nilsson (1971) Hart et al. (1968) Valmeekam et al. (2023).
An action sequence is one possible product of planning. Other products include a conditional policy, a partial-order set of dependencies, a contingent program, or a strategy for obtaining information before committing to an action. Under deterministic fully observed dynamics, a plan can sometimes be verified by repeated application of a transition function. Under stochastic or partially observed dynamics, appropriate evaluation requires a distribution over possible outcomes and observation histories. A language-model agent may also have to query tools, parse feedback, and repair an initial plan. These variations are scientifically consequential, because evidence of correct text prediction, optimal graph search, and resilient closed-loop behavior addresses different properties Kaelbling et al. (1998) Sutton (1991) Yao et al. (2023a).
The present monograph is a critical narrative synthesis of foundational algorithms, formal planning theory, learned-model experiments, and interactive-agent evaluations. Its questions concern how goals and costs are represented; how candidate futures are generated and pruned; how hidden information, risk, and execution feedback reshape solutions; and how reliably various agent architectures generalize beyond the tasks on which they were trained or prompted. It combines results from mathematics, computer science, robotics, machine learning, and comparative cognitive evaluation. Claims about the psychological organization of artificial systems are grounded in observable control and behavior, while questions of subjective experience require different evidence Schrittwieser et al. (2020) Liu et al. (2024) Kambhampati (2024).
From Problem Solving to Computational Search
The history of artificial planning grew from the analysis of problems as formally specified spaces of alternatives. In graph-theoretic form, nodes represent candidate states and edges represent permitted transitions; the planner seeks a path between a start state and a goal, possibly minimizing total cost. Dijkstra's 1959 work established a foundational shortest-path method for graphs with nonnegative edge costs, while Hart, Nilsson, and Raphael's 1968 A* analysis showed how a domain-sensitive heuristic can direct the exploration while retaining carefully qualified optimality guarantees. These results provided mathematical accounts of search effort and solution cost, supplying a lasting standard against which less explicit forms of apparent reasoning can be tested Dijkstra (1959) Hart et al. (1968).
Early symbolic planning made the structure of action explicit. Fikes and Nilsson's STRIPS architecture, reported in 1971, used descriptions of world models, goal conditions, and operators whose applicability and effects could be reasoned about. Planning became a problem of transforming a represented initial situation into one that satisfies a target formula. This shift joined goal-directed search to an explicit theory of change. Its importance is visible in later planning benchmarks: if the conditions for operating a device or moving an object are represented as preconditions, a superficially plausible sequence can be rejected as soon as a required condition is absent Fikes & Nilsson (1971) Blum & Furst (1997).
Subsequent research addressed the expansion of reachable states and the limitations of elementary search. Iterative-deepening methods reduced memory requirements in important tree-search settings, while planning graphs and domain-independent heuristics exploited structural information to guide exploration. These methods did not eliminate combinatorial difficulty; they redistributed it through abstractions, ordering constraints, evaluation functions, and selective expansions. Understanding that history clarifies a contemporary problem: increasing the length of an agent's visible reasoning trace is only useful insofar as the trace improves the actual representation, branching decisions, validity checking, or quality of discovered solutions Korf (1985) Blum & Furst (1997) Hoffmann & Nebel (2001).
The Formal Anatomy of a Planning Problem
A minimal deterministic planning model consists of states S, available actions A, a transition function T(s,a), an initial state s0, and a condition G that defines goal satisfaction. When path quality matters, a cost function c(s,a) assigns weights to transitions. A solution is a finite legal action sequence whose successive states are defined by T and whose terminal state satisfies G; an optimal solution minimizes accumulated cost under the chosen criterion. This formulation separates feasibility from preference. A cheap action that violates a precondition cannot be rescued by favorable cost accounting, and a valid low-cost path under one objective can be unacceptable when the objective changes Dijkstra (1959) Fikes & Nilsson (1971).
Real planning tasks require additional structures: deadlines, multiple resources, temporal overlap, safety constraints, stochastic outcomes, unobserved variables, preferences among terminal states, and budgets for computation itself. Such constraints may be global, meaning that no single step violates them although the complete plan does. A travel plan might individually contain feasible hotels and transport connections yet exceed a total budget or require incompatible departure times. This difference between local consistency and global feasibility is observable in recent language-agent benchmarks, which evaluate the complete itinerary rather than merely the plausibility of each sentence Xie et al. (2024) Zhang et al. (2026).
Scientific reports should identify the world model, the planning objective, the action vocabulary, the cost model, and the acceptance test. These constitute the task's operational definition, without which claims of reasoning ability are difficult to interpret. It is also necessary to distinguish offline planning, which generates a plan before execution, from online planning, which repeatedly recomputes decisions as new observations arrive. For a benchmark with a known deterministic simulator, independent plan validation can be exact. In a live environment, a robust assessment additionally requires behavior during disturbance, recovery from unavailable tools, and accounting of the actual effects caused by the agent Koenig et al. (2004) Sun et al. (2026).
Goal Representation, Decomposition, and Means–Ends Structure
Goal representation determines which futures are relevant to search. A goal may designate a single final state, a set of acceptable states, a reward function, a conjunction of requirements, or an ordered set of preferences. A planner pursuing several goals can encounter interactions in which satisfying one condition destroys another. Decomposition is the construction of subproblems whose dependencies permit useful progress toward the global objective. STRIPS historically approached goal differences by identifying operators that could achieve an unsatisfied requirement and then treating their preconditions as new subgoals. In that architecture, decomposition produces concrete testable dependencies rather than a rhetorically appealing list of activities Fikes & Nilsson (1971).
Not all decompositions preserve feasibility. Separately allocating a budget, a time slot, and a shared tool to independent subplans can create conflicts after locally valid sequences are combined. Partial-order approaches and planning graphs address some interactions by maintaining ordering and mutual-exclusion information before committing to a total sequence. Their lesson extends to modern agents coordinating searches, purchases, or API calls: a plan must record which actions consume shared resources and which facts remain true after an action. A task breakdown without these invariants can make failure more likely as the horizon grows Blum & Furst (1997) Helmert (2006).
An agent's goal can also change through clarification, environmental feedback, or a user's revised instruction. This creates a distinction between pursuing an obsolete objective efficiently and adapting to a new objective correctly. Suitable experiments modify a constraint after a plan has been partially executed and measure whether the agent recognizes which earlier steps remain reusable. The ability to revise a plan is related to memory, state tracking, and action selection, yet it is an independently measurable computational function. Dynamic-graph planning research makes the advantage of reusing previous search information explicit Koenig et al. (2004) Yao et al. (2023a).
Psychological Comparison and the Boundaries of Attribution
Planning has long been a central topic in human cognitive psychology, where researchers study how people represent goals, anticipate outcomes, manage working memory, and adjust behavior after errors. Artificial planning can be compared to these functional descriptions because both domains involve sequences of decisions under constraints. Such comparison requires choosing the level of analysis. Algorithmic search properties, behavioral success under experimental conditions, and cognitive explanations are not interchangeable. A graph-search algorithm may find an optimal route without resembling the strategy a person uses, while a language agent can reproduce humanlike explanations without exposing a reliable search procedure Hart et al. (1968) Kambhampati (2024).
Comparative psychology becomes informative when agents and people encounter matched informational and resource constraints. Researchers can compare sensitivity to horizon length, changing costs, irrelevant options, deceptive heuristics, delayed feedback, and uncertainty about action effects. Mechanistic conclusions then require interventions: for example, removing the planner, limiting lookahead, degrading the transition model, or substituting a search heuristic while holding the task fixed. Behavior alone reveals competence under the test distribution; transparent manipulation of system components can identify which computational capacities support it Schrittwieser et al. (2020) Liu et al. (2024).
Within the Artificial Era, artificial planning offers a concrete case of organized goal-directed performance in a nonbiological system. The phrase goal-directed describes a system's relation to a specified objective and to measured consequences. It does not by itself establish phenomenological desire, personal intention, or independent moral agency. The legitimate research program is therefore to specify functions, architectures, evidence, and limits before drawing broader philosophical conclusions. This separation preserves a strong empirical basis for Psychology of Artificial while supporting meaningful comparisons to human planning, distributed cognition, and human–artificial cooperation Kaelbling et al. (1998) Kambhampati (2024).
State-Space Search and the Geometry of Alternatives
State-space search turns an action problem into a graph of reachable configurations. Breadth-first methods enumerate successive levels, depth-first methods follow a branch until a stopping rule is reached, and uniform-cost methods prioritize accumulated transition cost. Their performance is governed by branching factor, solution depth, repeated states, and the distribution of costs. These properties can be measured independently of the semantic domain, which allows navigation problems, puzzles, and parts of automated planning to be compared. A search result is therefore meaningful only relative to the represented graph and the policy for detecting revisited configurations Dijkstra (1959) Korf (1985).
The distinction between a search tree and the underlying state graph matters because different action histories can lead to the same configuration. Failing to recognize duplicates can produce extensive redundant exploration, and a naive closed list can be unsafe when a lower-cost path to an earlier state is discovered under conditions that require reopening. Search algorithms make formal guarantees only when their assumptions concerning action costs, heuristics, and expansion policies hold. The mere use of an algorithm named A* does not establish that every implementation or problem formulation returns an optimal result Hart et al. (1968) Koenig et al. (2004).
Search effort has more than one cost. Memory may be consumed by a growing frontier; simulation may require expensive calls to a world model; evaluating an action may trigger a paid tool invocation; and a deadline may force a choice before the search is complete. Korf's iterative-deepening work demonstrated the importance of trading repeated expansions against reduced storage in suitable search settings. For an interactive agent, a practical evaluation should report peak memory, node expansions, external calls, elapsed time, and final solution quality rather than concentrating exclusively on the success indicator Korf (1985) Browne et al. (2012).
State abstractions alter the space before search starts. Two physical situations may be treated as equivalent when the omitted differences cannot change legal actions or future rewards relevant to a task. That simplification reduces computation, but an abstraction that discards a binding resource constraint may cause a purported solution to fail during execution. The appropriateness of an abstraction can be tested by comparing plans generated in the simplified model with validation in the complete environment. This is particularly important when an agent plans in natural language from incomplete descriptions of a structured world Helmert (2006) Xie et al. (2024).
Heuristics, Admissibility, and Optimality
A heuristic estimates the future cost of reaching a goal from a candidate state. A* evaluates a node through the accumulated cost g and the estimated remaining cost h, conventionally combining them as f=g+h. Under relevant assumptions, an admissible heuristic that never overestimates the true residual cost supports optimality of appropriately implemented A* search; consistency offers further practical properties for graph-search implementations. These are precise mathematical statements about a specified state model, not general endorsements of whichever choice looks most promising. Hart, Nilsson, and Raphael established the formal significance of combining actual path cost with informed estimates Hart et al. (1968).
More aggressive heuristics may rank productive states well while occasionally overestimating. Such heuristics can speed the discovery of a feasible plan at the cost of optimality guarantees. The design decision should follow the application's objective: an emergency response may prioritize an acceptable timely plan, while a certified shortest path may require a proof of minimum cost. This distinction underlies comparisons between optimal and satisficing planners. An experimental claim that one method is better must state whether the criterion is first valid solution, best cost within a budget, or proved optimality Hoffmann & Nebel (2001) Helmert (2006).
Heuristics are themselves representations of problem structure. Relaxing operator effects, estimating reachability, or learning a value function provides different ways of ranking alternative futures. Hoffmann and Nebel's FF system used relaxed-plan heuristics that ignore negative action effects during heuristic construction; this created computationally useful guidance even though the relaxed world differs from the original task. The discrepancy can mislead search when harmful interactions among goals are substantial. Strong planning research documents these failure conditions instead of treating a useful heuristic estimate as an exact distance Hoffmann & Nebel (2001).
Modern learned guidance can be investigated using the same experimental logic. If a language model proposes a high-level path while a symbolic search engine checks legality, the resulting performance is attributable to their joint architecture. Ablations should compare a neutral heuristic, a learned heuristic, and an independently validated final plan. Valmeekam and colleagues explicitly separated autonomous language-model plan generation from use of language outputs as heuristic advice, finding more promising contributions in the latter setting. Such decomposition is essential for identifying the role of generative models in planning systems Valmeekam et al. (2023).
Symbolic Operators, Preconditions, and Plan Validity
Classical symbolic planning represents actions in terms of applicability conditions and changes to facts. A STRIPS-style action is enabled when its preconditions hold; executing it adds and removes propositions according to its effects. This representation supports a direct validity test: beginning from the initial state, check every action's preconditions, update the state, and verify the final goal. The test can falsify an attractive plan whose steps depend on a missing key, an unavailable vehicle, or a resource already consumed. Because each state transition is explicit, a failure can be localized and explained Fikes & Nilsson (1971).
Action descriptions impose a closed modeling vocabulary. If the model omits battery depletion, permission checks, uncertain tool status, or a deadline, a plan can be perfectly valid in the formal domain and unusable in the world. The central issue is model adequacy, not simply solver correctness. Empirical assessment therefore requires two levels of verification: whether the solver respects the encoded domain, and whether that domain captures the operational facts of the target environment. Large language agents frequently face both problems because their action descriptions are inferred from prose and API interfaces Xie et al. (2024) Sun et al. (2026).
Planning graphs offer a compact method for propagating reachable propositions and recording mutually exclusive possibilities across levels. Blum and Furst demonstrated that useful restrictions can be derived before exploring fully instantiated action sequences. Such methods illustrate a general principle of computational reasoning: constraint propagation can eliminate impossible combinations without enumerating every combination. The same principle motivates preflight checks that compare a proposed schedule with resource calendars, dependency constraints, and mutually exclusive activities before execution begins Blum & Furst (1997).
Validity is also distinct from robustness. A sequence may be executable under one known initial state but fragile under a small perturbation or delayed observation. Testing a planner at neighboring states, injecting an unavailable action, and checking for successful recovery reveals properties absent from an exact-state validation. A useful system may therefore combine formal validation for the present model with ongoing monitoring for model divergence. This architecture connects the symbolic tradition to incremental search and closed-loop artificial control Koenig et al. (2004) Yao et al. (2023a).
Planning Graphs, Relaxations, and Domain-Independent Solvers
Domain-independent planning systems seek reusable principles that apply across many encoded task families. Graphplan revealed that layered planning graphs and mutual exclusions could constrain search effectively. FF subsequently exploited a relaxed planning problem to estimate goal distance, pairing heuristic guidance with techniques for escaping local stagnation. Fast Downward developed a systematic planning architecture grounded in translations and heuristic search. The historical sequence illustrates an accumulation of reusable algorithmic components: representation, preprocessing, search control, heuristic evaluation, and solution extraction Blum & Furst (1997) Hoffmann & Nebel (2001) Helmert (2006).
A solver can perform strongly on a collection of benchmarks for reasons that do not generalize to unconstrained applications. Standard domains often provide exact action models, a complete initial state, and a checker capable of rapidly validating plans. Open digital environments supply partial documentation, intermittent observations, asynchronous actions, and changing external data. Comparisons across these settings need to specify what knowledge has been provided by benchmark designers rather than inferred by an agent. Providing a perfect transition system can be a substantial form of assistance Fikes & Nilsson (1971) Gonzalez-Pumariega et al. (2025).
Planning quality has several dimensions. Completeness means finding a plan when one exists under stated assumptions; soundness requires reported plans to satisfy formal requirements; optimality concerns cost relative to the specified objective; efficiency concerns resources consumed to obtain an answer. One system may be highly efficient and incomplete under a strict time budget, while another may offer guarantees but scale poorly to larger problems. These differences cannot be collapsed into a single general-purpose intelligence score without obscuring practical tradeoffs and the scientific question being tested Hart et al. (1968) Helmert (2006).
Research on learned or linguistic agents benefits from retaining these distinctions. If an agent generates a plan and then uses a validator, its reported success should include both raw validity and validity after repair; otherwise the contribution of the verifier disappears. Search-guidance comparisons should report performance under equivalent call budgets and ensure that different systems receive equivalent environmental information. These methodological requirements allow novel model-based components to be evaluated within the cumulative tradition of planning science Valmeekam et al. (2023) Sun et al. (2026).
Incremental Search and Planning in Changing Worlds
A plan computed at one moment may become obsolete because a corridor is blocked, a service price changes, an API call fails, or another agent consumes a shared resource. Replanning addresses this divergence between expected and observed state. Incremental algorithms reuse portions of earlier search results when changes affect only part of the underlying graph. Koenig, Likhachev, and Furcy's Lifelong Planning A* formalized this strategy for sequences of related pathfinding problems with changing edges or vertices, providing analytical and experimental reasons to avoid solving every variant completely from scratch Koenig et al. (2004).
Replanning depends on detecting changes and identifying which commitments remain safe. A system that recomputes its entire task from the original text may lose valuable progress; one that merely continues an old plan may violate new conditions. Proper state management records completed actions, pending actions, current constraints, resources, and whether earlier assumptions were invalidated. Such record keeping constitutes a computational link between search, memory, and monitoring, with specific measurable effects on recovery time and redundant work Koenig et al. (2004) Yao et al. (2023a).
Dynamic environments also raise a distinction between a stationary target and a moving optimization problem. The agent may be required to maintain a sequence of feasible decisions as costs change, rather than ever complete one immutable plan. In this case, performance should be assessed over trajectories using cumulative cost, downtime, frequency of constraint violations, and response to perturbations. Recent agent benchmarks explicitly include broken or distracting tools, impossible tasks, and shifting requirements because a static endpoint metric hides these failure classes Sun et al. (2026) Zhang et al. (2026).
Computational reuse is advantageous only when the saved information remains valid under the changed conditions. A world model that confidently preserves an obsolete fact can make an incremental procedure worse than a fresh search. Research should therefore vary both the magnitude of change and the accuracy of change detection. These controls clarify how search algorithms, state estimates, and feedback systems contribute separately to flexible planning across repeated tasks Kaelbling et al. (1998) Koenig et al. (2004).
Planning Under Uncertainty and Partial Observability
An agent rarely knows all relevant properties of its environment. Uncertain transition outcomes and incomplete observations require a richer representation than a single known state and deterministic action rules. Markov decision processes describe decisions through states, actions, transition probabilities, and reward or cost. A partially observable Markov decision process adds observations and a belief state summarizing uncertainty about the environment. The appropriate planning object is then a policy contingent on information rather than a single guaranteed sequence. Kaelbling, Littman, and Cassandra established an influential framework for analyzing planning and acting in partially observable stochastic domains Kaelbling et al. (1998).
A belief-state planner must choose actions partly for their effect on information. Looking behind a door, querying an inventory service, or testing whether a tool is operational may have little immediate goal reward but can prevent an expensive mistake. The value of such actions depends on the probability of alternative situations and the downstream consequences of different decisions. A system that treats every missing fact as true effectively conceals uncertainty. A system that asks for every possible fact can become inefficient. Planning research therefore studies the value of observation relative to the cost and horizon of action Kaelbling et al. (1998) Kocsis & Szepesvári (2006).
Partial observability transforms evaluation. Success on a visible deterministic puzzle tests a different operation from success when the state must be inferred from noisy signals and actions may fail. A useful benchmark must specify what the agent was allowed to observe, whether observations were reliable, and how belief or memory was updated after new evidence. Outcome averages alone may conceal systematic risk if a planner succeeds frequently but makes occasional high-cost violations. The analysis of uncertainty should encompass outcome variance, worst-case failures, and the resources used to gather information Kaelbling et al. (1998) Sun et al. (2026).
Language agents introduce an additional form of uncertainty: textual descriptions can be ambiguous, incomplete, or contradicted by later tool responses. A plan generated before tool invocation may rest on hypothetical prices, schedules, or permissions. Interleaving retrieval and action with plan updates can reduce such errors, but retrieving data does not independently guarantee correct interpretation. TravelPlanner and later constrained-planning benchmarks make active information gathering part of the task rather than treating all required facts as available in the original question Xie et al. (2024) Zhang et al. (2026).
Model-Based Learning and the Dyna Tradition
Model-based learning permits an agent to estimate how the environment responds to actions and then use those estimates for hypothetical experience or lookahead. Sutton's Dyna architecture integrates direct reinforcement learning, model learning, simulated planning updates, and reactive interaction. This formulation clarifies that learning and planning are connected through an evolving model whose errors affect imagined outcomes. An agent can improve decisions from simulated transitions only to the extent that its model preserves task-relevant consequences. Computation spent on an inaccurate simulator can reinforce mistakes instead of correcting them Sutton (1991).
World models may describe observations in a literal state space or encode a compressed latent representation. A latent model is useful when it predicts rewards, action values, and the effects of choices without reconstructing every detail of the environment. The scientific burden then shifts toward determining which latent information is necessary for control. A model that predicts local rewards accurately may still fail at rare transitions or delayed constraints, while one trained to predict many visual details may spend capacity on information irrelevant to action Schrittwieser et al. (2020) Sutton (1991).
Planning and adaptation operate at distinguishable timescales. Search within a fixed model changes a current decision without necessarily changing model parameters. Model learning changes beliefs about environmental dynamics. Policy learning updates a persistent action-selection function. In-context linguistic adaptation changes the active information available to a language model while its parameters remain fixed. Studies of artificial planning should report which of these mechanisms is present before claiming that an agent learned from an episode or generalized a plan. Shinn and colleagues' Reflexion design, for example, uses stored linguistic feedback to change subsequent behavior without necessarily updating model weights Shinn et al. (2023).
Experimental comparisons can isolate these mechanisms with controlled ablations. A planner can be evaluated using the true environment simulator, a learned model, a shuffled learned model, and a model with a known systematic error. The resulting differences reveal how much the agent relies on dynamics fidelity, search depth, or replay from experience. Similar controls for language agents can remove their external memory buffer, forbid tool feedback, or reset context after each step. The resulting pattern can support a mechanistic explanation more informative than the final task-completion rate alone Sutton (1991) Schrittwieser et al. (2020) Shinn et al. (2023).
Monte Carlo Tree Search and Sampling-Based Lookahead
Monte Carlo tree search builds a selective tree using repeated simulations and uses empirical outcomes to guide the allocation of further simulation effort. Rather than expanding every option in order, it concentrates sampling on promising actions while retaining some exploration. Kocsis and Szepesvári's UCT method adapts bandit-based selection to lookahead trees and analyzes convergence under specified decision-process assumptions. The approach is valuable when exhaustive search is infeasible but a generative model permits repeated hypothetical transitions Kocsis & Szepesvári (2006).
The quality of Monte Carlo search is jointly determined by the simulator, the exploration rule, the action space, and the value estimates returned by sampled trajectories. Increasing the number of simulations can reduce sampling uncertainty, but it cannot repair systematic defects in the world model. Nor does a theoretical result about a particular finite or discounted process imply that arbitrary interactive environments share its assumptions. Browne and colleagues' survey documents variations of selection, expansion, simulation, and backup and their differences across application domains Browne et al. (2012).
Monte Carlo search also changes the interpretation of apparent strategic foresight. A strong move may emerge from selective rollouts combined with statistical value estimates rather than from an explicitly formulated verbal explanation. Analyzing such an agent requires access to expansion counts, sampled outcomes, policy distributions, and decision changes as computation increases. Without this information it can be difficult to distinguish a capable search procedure from a shortcut that has memorized frequent decisions in the evaluation domain Browne et al. (2012) Silver et al. (2016).
Planning experiments should therefore vary the computational budget systematically and report performance curves, not only a single fixed-budget score. An algorithm that is superior after thousands of simulations may be impractical under a severe latency limit. A learned policy that acts quickly may be preferable when the environment demands immediate responses, while deeper search may be justified for irreversible costly choices. These tradeoffs connect Monte Carlo planning to broader questions of rational resource allocation and action under time pressure Kocsis & Szepesvári (2006) Silver et al. (2018).
Deep Reinforcement Learning, AlphaGo, and AlphaZero
The integration of learned evaluation with explicit search became a prominent experimental demonstration in game-playing agents. Silver and colleagues' AlphaGo system combined policy networks, value networks, reinforcement learning, and tree search to select moves in Go, a domain with a highly challenging branching structure. The resulting performance is evidence for a particular architecture operating within a precisely specified game environment. Its interpretation requires recognizing that the system could evaluate actions against complete rules and a well-defined outcome criterion Silver et al. (2016).
AlphaZero subsequently used self-play reinforcement learning with a common algorithmic scheme across chess, shogi, and Go. Its achievements support the transfer of a general learning-and-search architecture across several formal games rather than the universal applicability of a single learned representation to every real-world planning task. The rules and terminal rewards remained explicit and simulations were available. These conditions are powerful experimental affordances, and their absence in poorly specified digital environments makes direct extrapolation unwarranted Silver et al. (2018).
Search can improve a learned policy during both decision making and training. The current policy proposes promising actions, the search process allocates additional consideration, and the resulting search distribution can provide a training target for the next policy update. This is an important mechanism of iterative improvement because planning helps generate stronger supervision than the original policy could have supplied alone. The mechanism can be examined by removing search at evaluation, changing its simulation budget, or comparing learning with and without search-derived targets Silver et al. (2016) Silver et al. (2018).
Game results also show why appropriate comparisons require equal access to rules, training computation, and interaction histories. A model evaluated with a tree search cannot simply be compared to another model given only a single forward pass and labeled more intelligent on that basis. Strong agent science reports system-level performance while analyzing the contributions of the environment model, network architecture, learning regime, and available computation. This multi-component perspective later became especially important for claims about language-model agents supported by external tools and validators Silver et al. (2018) Valmeekam et al. (2023).
MuZero and Planning with Learned Dynamics
MuZero addressed the challenge of planning when the agent is not supplied with the full transition rules required for search. Schrittwieser and colleagues combined tree-based lookahead with a learned model trained to predict reward, action-selection policy, and state value in a representation useful for planning. Their Nature report evaluated the system on Atari games as well as Go, chess, and shogi. The architecture is significant because it demonstrates that effective lookahead can proceed through a learned, task-oriented internal dynamics representation rather than a hand-coded full simulator Schrittwieser et al. (2020).
The experiment distinguishes several claims often conflated in popular accounts. It demonstrates high performance under the paper's specified training and testing protocols; it does not establish that any learned world model is causally faithful at every level of physical detail. A latent transition can be sufficient for selecting rewarding actions while failing to preserve aspects of the environment irrelevant to the trained objectives. Conversely, task relevance can shift, rendering previously omitted distinctions consequential. The model should therefore be analyzed in terms of policy, value, and reward prediction under controlled perturbations Schrittwieser et al. (2020).
An important design question is the depth of imagined computation. A deeper rollout can reveal delayed consequences, but learned-transition errors may accumulate as predictions move farther from observed states. Model fidelity and search depth must therefore be optimized jointly. A planning method may perform best at an intermediate depth when longer predictions become misleading, and it may improve through frequent returns to real feedback. This logic connects learned dynamics to receding-horizon strategies and explains why additional apparent deliberation is not automatically beneficial Sutton (1991) Schrittwieser et al. (2020).
MuZero and related work provide an empirical basis for studying planning in artificial systems without importing assumptions about human-like understanding. The measurable object is a computational procedure that estimates the consequences of candidate actions and uses those estimates to guide behavior. Extending its lessons to language agents requires careful attention to the change of interface: text and tool outputs may lack the regularity of game-state observations, while action semantics can be uncertain or mediated by external institutions. Those differences demand independent validity experiments Schrittwieser et al. (2020) Xie et al. (2024).
Language Models as Components of Planning Systems
Large language models can express goals, propose sequences of activities, interpret instructions, generate action descriptions, and summarize observed consequences. These capacities are relevant to planning because many practical environments expose their interfaces through natural language. Yet the generation of a syntactically coherent plan is separable from identifying valid transitions in a state model. A language model may produce an appealing itinerary without checking inventory, travel duration, budget interactions, or feasibility. Critical experiments therefore compare its outputs against independent simulators or formal validators instead of treating fluency as a proxy for executable planning competence Valmeekam et al. (2023) Kambhampati (2024).
Valmeekam and colleagues' NeurIPS study evaluated large language models both as autonomous plan generators and as sources of guidance for classical planning tools. In the examined benchmark configuration, autonomous plans often failed validity requirements; the paper reported approximately twelve percent average success for its strongest evaluated model across the tested domains. The same study identified more constructive uses of language-model output as heuristic advice, particularly when external solvers and verifiers preserved formal constraints. This is evidence about particular models, prompts, domains, and evaluation dates rather than a permanent score for language-model technology Valmeekam et al. (2023).
The functional decomposition of an agent matters at least as much as its underlying text generator. A system may contain a language model for semantic interpretation, a state estimator for observations, a symbolic planner for legal actions, a database for task memory, and a verifier for completion. Assigning the whole system's success to the language model hides which component prevents infeasible moves. Conversely, attributing failure solely to language generation may overlook incorrect tool definitions, stale environmental data, or unsuitable objective functions. Research design must specify interfaces and perform component ablations Yao et al. (2023a) Sun et al. (2026).
An additional concern is the difference between planning a familiar pattern and adapting to a changed domain. Changing object names, reordering descriptions, perturbing action effects, or altering a global constraint can reveal reliance on memorized examples. Robust generalization requires maintaining the structure of a problem even when its linguistic surface varies. This concern applies to both language models and formal planners using learned heuristics, but it is especially urgent where training data may overlap with public benchmark examples Valmeekam et al. (2023) Liu et al. (2024).
Deliberative Sampling, Tree of Thoughts, and Self-Evaluation
Language-model inference can be organized as exploration over candidate intermediate solutions rather than one uninterrupted text sequence. Yao and colleagues' Tree of Thoughts method introduced explicit branching, evaluation, and potential backtracking across coherent units of generated reasoning. Their experiments reported task-specific improvements over a chain-of-thought baseline, including a large difference on the Game of 24. The result illustrates the utility of allocating additional inference computation to a structured search process. It remains important to distinguish this inference-time procedure from classical state-space planning, in which action applicability and environmental transitions may be formally defined Yao et al. (2023b).
A language-based search tree may branch over hypotheses, drafts, tool requests, or candidate subgoals. Its evaluator can be another model, a formal checker, environmental feedback, or a combination. When evaluation is generated by the same fallible model as the candidates, errors may be correlated: a mistaken assumption can appear repeatedly across branches and be endorsed by the evaluator. Backtracking then offers apparent diversity while preserving the underlying defect. Controlled experiments should measure the effect of independent validation, scoring reliability, and the number of genuinely distinct candidate states reached Yao et al. (2023b) Kambhampati (2024).
The performance of deliberate prompting is also budget-sensitive. Multiple candidate evaluations increase token expenditure, latency, and opportunities for false confidence. A benchmark that allows one agent substantially more external calls than another tests an unequal resource allocation. To identify genuine search benefits, investigators should plot outcome quality against wall-clock time, model calls, and budget, while preserving identical input information. Improvement after more sampling is a useful finding, but the underlying mechanism can be assessed only by comparing search strategies under matched budgets Yao et al. (2023b) Browne et al. (2012).
Self-evaluation requires particular caution in empirical interpretation. A convincing linguistic criticism of a proposed plan can indicate sensitivity to task structure, yet the ability to generate that criticism does not prove the system can reliably detect all invalid plans or repair them. An independent validator provides a stronger test when the action space is formalizable. For open-world tasks, adjudication may require actual execution traces and external facts, and evaluator disagreement should be reported. This evidentiary discipline prevents verbal deliberation from substituting for observed task competence Kambhampati (2024) Sun et al. (2026).
Reasoning–Action Loops, Tools, and External Feedback
An interactive agent must connect planning to observation and execution. The ReAct framework described by Yao and colleagues interleaves model-generated reasoning steps with task-specific actions, allowing subsequent decisions to use external observations. This design addresses a practical weakness of wholly offline verbal planning: new information can invalidate an earlier assumption before the entire task is complete. The empirical contribution concerns a coupling between language generation and environmental action rather than the demonstration that every generated intermediate explanation is a transparent record of the system's internal mechanism Yao et al. (2023a).
Tool use introduces distinct planning decisions. The agent must select an appropriate tool, construct valid arguments, decide whether information is sufficient, interpret success or error states, and decide when to repeat or abandon an action. An incorrect tool call can be a planning failure, an interface misunderstanding, or an execution failure, depending on the system design. Studies of interactive agent performance should record these categories separately. AgentBench evaluated agents across eight environments and described difficulties with long-term reasoning, decision making, and instruction following that a final completion label alone cannot explain Liu et al. (2024).
External feedback can support adaptive correction without changing a model's parameters. Reflexion uses linguistic feedback and an episodic text buffer to influence decisions in subsequent episodes. This creates a reusable external history but also presents risks of reinforcing inaccurate self-descriptions or outdated error diagnoses. Experimental isolation requires comparison with equivalent memory capacity and feedback under controlled reset conditions. A failure repeated across episodes may arise from defective diagnosis, retrieval, policy selection, or an inaccessible environmental constraint Shinn et al. (2023).
Planning in tool-rich settings therefore depends on a verifiable action loop: propose, authorize, execute, observe, update, and reconsider. Authorization and side-effect checks are important when actions modify accounts, files, financial resources, or other external systems. Scientific evaluation should distinguish simulation from real execution and document the independence of the observation channel. Successful text about a completed action cannot substitute for an authoritative record that the action occurred. This principle generalizes from planning science to responsible human–artificial workflows Yao et al. (2023a) Sun et al. (2026).
Empirical Benchmarks for Feasibility and Long-Horizon Performance
Agent benchmarks vary substantially in the construct they measure. Some tasks present symbolic operators and permit exact plan validation; others test retrieval-augmented action in simulated digital environments; others evaluate constrained practical itineraries. TravelPlanner, published at ICML 2024, introduced 1,225 planning intents and a large underlying travel-data environment. The authors reported that the systems evaluated at that time struggled to satisfy global travel requirements; in their tested setup, GPT-4 reached a final success rate of 0.6 percent. This figure describes the benchmark's defined metric and experimental configuration, not a general success rate for all travel planning or for later model generations Xie et al. (2024).
AgentBench assessed language-model agents in eight environments and emphasized interactive decision making, while TravelPlanner subjected complete plans to combined feasibility constraints. These benchmarks complement rather than replace one another. An agent might succeed in navigating an interface yet fail a constrained scheduling task, or solve a synthetic puzzle without retrieving missing facts. Reporting construct definitions, tool availability, context length, number of attempts, and evaluation criteria makes cross-benchmark comparisons scientifically interpretable Liu et al. (2024) Xie et al. (2024).
Robotouille, presented at ICLR 2025, addressed asynchronous planning in a setting with overlapping activities and interruptions. Its authors reported a marked performance decrease for an evaluated ReAct configuration when moving from synchronous to asynchronous tasks. This contrast is informative because a plan that orders steps correctly can still fail when activities run concurrently, waiting has consequences, and shared resources become unavailable. It establishes a distinct research domain for temporal coordination rather than a universal ranking of model architectures Gonzalez-Pumariega et al. (2025).
More recent evaluations put longer horizons and verifiable global constraints at the center of the design. DeepPlanning, an ACL 2026 study, combines active information acquisition with constrained travel and shopping tasks and reports persistent difficulties for evaluated frontier agents. Agent Planning Benchmark, published in Findings of EMNLP 2026, introduces separate diagnostic conditions including extraneous tools, broken tools, and unsolvable cases. These designs improve interpretability by asking whether an agent recognized infeasibility, selected relevant actions, and preserved constraints, not merely whether a final answer resembled a reference plan Zhang et al. (2026) Sun et al. (2026).
What the Experimental Evidence Establishes
Current evidence supports several bounded conclusions. Under specified formal assumptions, search algorithms can provide soundness, completeness, optimality, or convergence guarantees. In complex games, learned evaluation combined with search can achieve exceptionally strong performance. In natural-language and tool-mediated environments, agent architectures can execute multi-step behavior, but published benchmark results document substantial weaknesses in maintaining constraints, adapting to disturbances, and identifying infeasible tasks. These findings describe different classes of evidence and should be integrated without assigning them one undifferentiated meaning Hart et al. (1968) Silver et al. (2018) Xie et al. (2024) Sun et al. (2026).
Comparisons across years are particularly difficult because model versions, prompting methods, tools, simulation environments, and costs change rapidly. A reported failure rate for a 2023 model cannot be presented as a measurement of an unrelated 2026 model. A benchmark may also be used repeatedly in development, increasing the risk that improvements reflect familiarity with specific cases rather than transferable planning capacity. Independent held-out environments, counterfactual changes to task rules, and complete reporting of tool traces are therefore necessary to support claims of generalization Valmeekam et al. (2023) Zhang et al. (2026).
Human-level planning is itself a heterogeneous target. People can use remembered templates, formal calculation, social collaboration, perceptual feedback, and external artifacts; they also make systematic errors. A fair human–artificial comparison should control the resources and information available, clarify whether assisted human performance is compared to assisted agents, and report distributional patterns rather than anecdotal tasks. A machine's achievement on exact graph search and a person's achievement in an ambiguous social planning situation are not interchangeable psychological measurements Kaelbling et al. (1998) Kambhampati (2024).
The scientific synthesis is architectural: planning performance emerges from the interaction of state representation, available actions, model accuracy, search allocation, evaluation criteria, and feedback. No single component guarantees success across the full variety of task environments. This implies that future studies should use multicomponent designs with transparent ablations and rigorous end-to-end outcome checks. It also suggests a constructive path for artificial systems: combine specialized verification and planning tools with flexible language interpretation, while preserving the distinctions between proposed actions and measured consequences Valmeekam et al. (2023) Schrittwieser et al. (2020) Sun et al. (2026).
Measuring Planning Competence
Planning competence is multidimensional and requires a measurement model. At minimum, studies should distinguish whether the proposed sequence is executable, whether the specified goal is satisfied, whether hard constraints are preserved, how much the solution costs, and how much computation or interaction was needed to generate it. Validity can be measured before execution by a formal action simulator when one is available; realized performance requires an independent observation of environmental outcomes. A benchmark that records only the apparent elegance of a plan is measuring linguistic form rather than the target function Fikes & Nilsson (1971) Valmeekam et al. (2023).
Evaluation should separate feasibility, optimization, flexibility, and calibration. Feasibility concerns whether any acceptable plan has been produced. Optimization concerns solution quality among acceptable plans. Flexibility concerns adaptation when states, constraints, or goals change. Calibration concerns whether confidence, requests for clarification, and abstention track actual probabilities of success. The latter becomes especially important when tasks are unsolvable. Agent Planning Benchmark explicitly includes impossible tasks and tool failures, supporting measurement beyond a single success rate Sun et al. (2026).
Horizon length should be manipulated carefully. Simply adding irrelevant steps may make instructions longer without substantially changing dependency complexity. Strong designs vary the number of coupled constraints, the depth of prerequisite chains, uncertainty about effects, the number of alternative actions, and the degree of environmental change. Analyzing how outcomes deteriorate across these dimensions can identify whether an agent struggles with memory, constraint propagation, search budgeting, or feedback interpretation. Long-horizon benchmark designs increasingly reflect these distinctions Gonzalez-Pumariega et al. (2025) Zhang et al. (2026).
Measurement reliability also depends on repeated trials, multiple problem instances, and clearly reported sampling settings. Stochastic decoders can generate different plans from the same input; tool results can vary by time; and a model may improve after repeated attempts. Investigators should record the number of trials per task, report uncertainty around performance estimates, and avoid treating correlated restarts as independent observations. Exact versions of model, tools, environment, scoring code, and reference data are essential to meaningful replication Liu et al. (2024) Xie et al. (2024).
Experimental Design, Causal Inference, and Failure Taxonomies
A planning study becomes explanatory when it varies mechanisms rather than merely collecting outcomes. Useful interventions include disabling search, reducing simulation depth, withholding state feedback, substituting inaccurate world models, removing task memory, perturbing heuristics, or replacing an external verifier. Each intervention tests a different causal claim. If success collapses when the verifier is removed, the combined system's strength may rely heavily on formal checking. If success remains high without extended reasoning, the task may be solved largely through a learned policy or familiar pattern. These interpretations require controlled comparisons and suitable statistical uncertainty Silver et al. (2018) Valmeekam et al. (2023).
Failure analysis should distinguish at least five observable stages: incorrect task interpretation; invalid or incomplete world representation; ineffective search or decomposition; incorrect action execution; and failed recognition or recovery after feedback. This taxonomy allows investigators to avoid assigning a tool outage to the reasoning component or misclassifying an infeasible request as a planning error. In dynamic tasks, an additional category is failure to detect that a formerly legal action has become unavailable. Recording the earliest point of divergence supplies diagnostic evidence rather than post hoc speculation about an agent's internal thought Yao et al. (2023a) Sun et al. (2026).
Counterfactual tests strengthen causal interpretation. An experiment can preserve the stated goal while changing prices, tool order, action preconditions, or the consequences of a high-ranked option. A genuine constraint-sensitive planner should update the relevant choices, with errors revealing which dependencies were omitted. In formal domains, an independent validator can calculate whether the repaired plan satisfies the altered conditions. In open-world tasks, experimental sandboxes must document their own limitations so that failures of the simulated environment are not credited to the agent Blum & Furst (1997) Zhang et al. (2026).
Performance analysis should also report negative results. If more search calls do not improve feasibility, the bottleneck may lie in model adequacy or the evaluation function. If the system identifies an impossible task but incurs excessive cost before doing so, the capability is real yet operationally limited. If an intervention benefits one task family and harms another, averaging the results can conceal a meaningful interaction. Publishing disaggregated outcomes, ablations, and representative execution traces is essential for cumulative research Kocsis & Szepesvári (2006) Kambhampati (2024).
Construct Validity, Transfer, and Reproducibility
Construct validity concerns whether a test actually measures planning rather than closely related abilities. A benchmark may reward retrieving a known solution, obeying a formatting convention, or guessing likely final answers. Such behavior can improve the test score without demonstrating an ability to forecast consequences of unfamiliar actions. More discriminating evaluation modifies transition rules, resource relationships, and goal structures while preserving a transparent ground truth. This allows the experiment to test abstraction and structural transfer instead of phrase familiarity Valmeekam et al. (2023) Xie et al. (2024).
Contamination is a particular concern when benchmark tasks, reference solutions, or evaluation scripts circulate in the data used to develop models. Randomly holding out individual examples can be insufficient if near-identical problem templates remain visible. Domain-level holdouts, newly generated action systems, confidential test sets, and independently timed evaluations offer stronger evidence. Researchers must distinguish contamination established by direct evidence from the general risk of exposure, and should not assume that every unexpectedly strong result is memorization Liu et al. (2024) Sun et al. (2026).
Reproducibility requires preserving the operational environment. A tool interface can change while a model's name stays constant, and a retrieval endpoint can return updated information. Therefore, reliable planning experiments should record environment snapshots where practical, model versions and decoding parameters, permissible tools, scoring rules, action logs, and any human intervention. Where private commercial systems prevent exact reruns, the study should explicitly state those limitations. Independent replication across several providers and newly designed tasks offers stronger generalization evidence than repeated trials on one familiar suite Xie et al. (2024) Gonzalez-Pumariega et al. (2025).
The evidentiary status of theory should remain explicit. Optimality proofs describe mathematical algorithms operating under stated assumptions; randomized evaluations estimate performance distributions under a benchmark protocol; case studies can suggest failure mechanisms without establishing their prevalence; and a conceptual account of artificial agency is a framework to be operationalized. Treating all these claims as equivalent would distort both the strengths and limitations of planning research. Careful attribution preserves the practical relevance of formal methods and the empirical specificity of modern agents Hart et al. (1968) Schrittwieser et al. (2020) Kambhampati (2024).
Human–Artificial Planning and the Wider Artificial Era
Human–artificial planning is an interaction in which a person's goals and contextual knowledge are combined with artificial search, constraint checking, retrieval, or action execution. The joint system can redistribute cognitive labor: people clarify priorities and judge ambiguous outcomes, while computational tools enumerate alternatives and check formal dependencies. This introduces questions about how goals are translated into machine-readable constraints, how uncertainty is communicated, and how errors are detected before irreversible actions occur. A successful partnership must be evaluated as a process with explicit responsibilities, observable handoffs, and measured outcomes Yao et al. (2023a) Xie et al. (2024).
Planning support is particularly valuable where the combinatorics of schedules, budgets, or dependencies exceed what can be inspected easily without external artifacts. Its use also creates risks if a generated plan is given authority beyond the evidence supporting it. An agent that presents a feasible-looking travel program can lead a person to commit resources before cost or availability is checked. Good interface design makes conditional assumptions, hard constraints, tool verification states, and pending approvals visible, allowing the human participant to act on evidence rather than on stylistic confidence Xie et al. (2024) Zhang et al. (2026).
Across Artificial Era research, the functional study of planning connects Psychology of Artificial with computational cognition, decision-making, memory, tool use, and distributed cognitive systems. These are scientific relationships rather than claims that artificial agents share all properties of the human psyche. The present dossier isolates planning and search from neighboring dossiers on representation, learning, artificial agency, and action selection while showing how those capacities jointly determine sequential behavior. A stable scholarly architecture allows one canonical object to support several disciplinary connections without multiplying the same text Sutton (1991) Schrittwieser et al. (2020).
A productive future program should examine human–artificial teams against matched baselines: unaided human performance, tool-only assistance, language-model-only assistance, and integrated planning with independent verification. Such designs can measure whether the collaboration changes total error, time, resource consumption, and the ability to recognize impossible requests. Studies should also test whether users appropriately adjust trust after an agent's failures and whether a system preserves user goals when constraints change. These are researchable consequences of the architecture rather than assumptions about the agent's internal identity Kambhampati (2024) Sun et al. (2026).
Conclusion
Planning and search in artificial agents constitute an established computational research domain with identifiable formal foundations, experimental methods, and increasingly demanding environmental tests. The historical progression from shortest-path procedures and A* through STRIPS, planning graphs, probabilistic decision processes, Monte Carlo tree search, and learned dynamics reveals a continuous scientific problem: how to select consequential actions from an expanding space of possible futures under limited information and resources. Different architectures solve different versions of that problem and deserve interpretation within their own assumptions Hart et al. (1968) Fikes & Nilsson (1971) Kaelbling et al. (1998) Schrittwieser et al. (2020).
The strongest synthesis is that reliable planning is a property of an integrated decision system. Goal representation determines what counts as success, transition models delimit the futures considered, search strategies allocate computation, cost functions rank feasible plans, and monitoring connects hypothetical action to the environment. A weakness in any component can defeat the whole process. Formal verification can establish validity within an encoded model; it cannot certify that the model is complete. More capable generative language can improve interpretation and candidate generation, but it does not make independent feasibility checks redundant Hoffmann & Nebel (2001) Valmeekam et al. (2023) Xie et al. (2024).
Contemporary empirical studies sharpen the research agenda. Long-horizon and asynchronous tasks, global budgets, changing tools, and unsolvable requests expose limitations that short static puzzles may hide. The appropriate response is a more discriminating experimental science: independent validators, held-out task structures, transparent call budgets, systematic perturbations, execution traces, and explicit causal ablations. Numerical benchmark outcomes must retain their historical model, task, and metric context. General claims about artificial reasoning require evidence of transferable control under such tests Gonzalez-Pumariega et al. (2025) Zhang et al. (2026) Sun et al. (2026).
The scientific contribution of this monograph is a structured synthesis of those established traditions and their evidentiary boundaries. Artificial planning provides measurable forms of anticipatory organization, decision selection, and environmental adaptation. The Artificial Era extends their significance to new nonbiological systems and cooperative human–artificial arrangements while leaving questions of subjective experience to distinct research programs. A mature Psychology of Artificial can investigate planning through reproducible functions, causal mechanisms, and longitudinal behavior, building its conclusions from verified actions and explicitly defined constraints Sutton (1991) Schrittwieser et al. (2020) Kambhampati (2024).
References
- Blum, A. L., & Furst, M. L. (1997). Fast planning through planning graph analysis. Artificial Intelligence, 90(1–2), 281–300. https://doi.org/10.1016/S0004-3702(96)00047-1
- Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., & Colton, S. (2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43. https://doi.org/10.1109/TCIAIG.2012.2186810
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271. https://doi.org/10.1007/BF01386390
- 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. https://doi.org/10.1016/0004-3702(71)90010-5
- Gonzalez-Pumariega, G., Yean, L., Sunkara, N., & Choudhury, S. (2025). Robotouille: An asynchronous planning benchmark for LLM agents. International Conference on Learning Representations. https://proceedings.iclr.cc/paper_files/paper/2025/hash/d033407a1a4b7a75cd5f9e4575ad9fb5-Abstract-Conference.html
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136
- Helmert, M. (2006). The Fast Downward planning system. Journal of Artificial Intelligence Research, 26, 191–246. https://doi.org/10.1613/jair.1705
- Hoffmann, J., & Nebel, B. (2001). The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14, 253–302. https://doi.org/10.1613/jair.855
- Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1–2), 99–134. https://doi.org/10.1016/S0004-3702(98)00023-X
- Kambhampati, S. (2024). Can large language models reason and plan? Annals of the New York Academy of Sciences, 1534(1), 15–18. https://doi.org/10.1111/nyas.15125
- Kocsis, L., & Szepesvári, C. (2006). Bandit based Monte-Carlo planning. In Proceedings of the 17th European Conference on Machine Learning (pp. 282–293). Springer. https://doi.org/10.1007/11871842_29
- Koenig, S., Likhachev, M., & Furcy, D. (2004). Lifelong planning A*. Artificial Intelligence, 155(1–2), 93–146. https://doi.org/10.1016/j.artint.2003.12.001
- Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97–109. https://doi.org/10.1016/0004-3702(85)90084-0
- Liu, X., Yu, H., Zhang, H., Xu, Y., Lei, X., Lai, H., Gu, Y., Ding, H., Men, K., Yang, K., Zhang, S., Deng, X., Zeng, A., Du, Z., Zhang, C., Shen, S., Zhang, T., Su, Y., Sun, H., ... Tang, J. (2024). AgentBench: Evaluating LLMs as agents. International Conference on Learning Representations. https://proceedings.iclr.cc/paper_files/paper/2024/hash/e9df36b21ff4ee211a8b71ee8b7e9f57-Abstract-Conference.html
- Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., Lillicrap, T., & Silver, D. (2020). Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, 588, 604–609. https://doi.org/10.1038/s41586-020-03051-4
- Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K., & Yao, S. (2023). Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36. https://papers.neurips.cc/paper_files/paper/2023/hash/1b44b878bb782e6954cd888628510e90-Abstract-Conference.html
- Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., & Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529, 484–489. https://doi.org/10.1038/nature16961
- Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., & Hassabis, D. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419), 1140–1144. https://doi.org/10.1126/science.aar6404
- Sun, H., Wang, W., Song, M., He, J., Zhang, W., Liu, Y., Yang, Y., & Cheng, Y. (2026). Agent Planning Benchmark: A diagnostic framework for planning capabilities in LLM agents. Findings of the Association for Computational Linguistics: EMNLP 2026. https://aclanthology.org/2026.findings-emnlp.1041/
- Sutton, R. S. (1991). Dyna, an integrated architecture for learning, planning, and reacting. ACM SIGART Bulletin, 2(4), 160–163. https://doi.org/10.1145/122344.122377
- Valmeekam, K., Marquez, M., Sreedharan, S., & Kambhampati, S. (2023). On the planning abilities of large language models—A critical investigation. Advances in Neural Information Processing Systems, 36. https://papers.neurips.cc/paper_files/paper/2023/hash/efb2072a358cefb75886a315a6fcf880-Abstract-Conference.html
- Xie, J., Zhang, K., Chen, J., Zhu, T., Lou, R., Tian, Y., Xiao, Y., & Su, Y. (2024). TravelPlanner: A benchmark for real-world planning with language agents. Proceedings of Machine Learning Research, 235, 54590–54613. https://proceedings.mlr.press/v235/xie24j.html
- Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., & Narasimhan, K. (2023). Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36. https://papers.nips.cc/paper/2023/hash/271db9922b8d1f4dd7aaef84ed5ac703-Abstract-Conference.html
- Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. R., & Cao, Y. (2023). ReAct: Synergizing reasoning and acting in language models. International Conference on Learning Representations. https://apice.unibo.it/bin/view/Publication/ReactIclr2023
- Zhang, Y., Jiang, S., Li, R., Tu, J., Su, Y., Deng, L., Guo, X., Lv, C., & Lin, J. (2026). DeepPlanning: Benchmarking long-horizon agentic planning with verifiable constraints. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (pp. 7377–7407). https://doi.org/10.18653/v1/2026.acl-long.335