Breadth-first
Expands the shallowest state first. It finds a shortest-depth solution when actions have equal cost, but can explore a wide frontier.
priority(n) = depth(n)
0states expanded
1frontier size
0path cost
searchingplanner status
A plan is useful only when its search assumptions match the world.
Greedy best-first
Chooses the state estimated closest to the goal. A strong heuristic is fast; a misleading one can chase an expensive dead end.
priority(n) = h(n)
A*
Balances cost already paid with estimated remaining cost. With an admissible consistent heuristic, graph-search A* is optimal.
priority(n) = g(n) + h(n)
Tool calls make edges uncertain.
A web request, browser action, payment attempt, or human approval can fail. Robust planners represent retries, fallbacks, and irreversible costs rather than assuming every edge succeeds.
Heuristics encode product judgment.
“Closer to done” may combine missing evidence, risk, latency, and monetary cost. An aggressive heuristic reduces search but can hide alternatives; zero heuristic reduces A* to uniform-cost search.
Replanning begins after observation.
Agents do not execute a complete imagined plan blindly. They act, observe the actual state, update beliefs, and search again when preconditions or outcomes differ.
Planner questions
Why can greedy search return an expensive plan?
It ignores accumulated cost. A state that appears close to the goal can require costly actions or lead into a dead end.
Does A* solve every agent workflow?
No. Large, partially observable, stochastic, or continuous environments require abstractions, sampling, dynamic programming, or learned policies.
Where should approvals appear?
Model them as state transitions with explicit preconditions, latency, and denial outcomes so the planner cannot silently assume consent.
Primary sources
Hart, Nilsson, and Raphael (1968) formalized A*. Russell and Norvig provide standard search and planning foundations. Yao et al. (2022) introduced ReAct reasoning-and-action trajectories. Shinn et al. (2023) studies feedback-driven agent reflection.