Chapter 7. Planning and Search
Make a plan for a goal · Search among possible paths
In Chapter 4, the agent loop chose one action at a time. In Chapter 6, a team divided a task among agents. Some tasks need several connected actions before the answer is ready. This chapter explains how an agent makes a plan for such a task, and how it searches when several paths are possible.
Part 1. Planning
1.1 Why plan
Consider this request: “Find a way for me to reach the conference before it starts.” The agent must find the venue and the start time. Then it must find journeys to the venue. Then it must compare the arrival times with the start time. If the agent chooses only one action at a time, it can forget a necessary step. A plan shows all the work before the work starts.
1.2 Task decomposition and dependencies
Task decomposition divides a goal into smaller tasks. Each task gives a result that another task or the final answer uses.
A dependency exists when a task needs the output of another task. A task with a dependency must wait for that output. Tasks without dependencies can run in any order, or at the same time.
To make a plan, do these steps:
- Write the final result that the goal needs.
- Find the information that this result needs.
- Write one task for each piece of information.
- Put each task after the tasks whose outputs it needs.
1.3 Example: a plan for the conference
| Task | Output for the next task |
|---|---|
| Find the conference information. | The venue, the date, and the start time |
| Find journeys to the venue on that date. | The departure times and arrival times |
| Compare the arrival times with the start time. | A journey that arrives before the start |
Each task has an output that the next task uses. The last output answers the request.
Part 2. Planning and execution
2.1 Two approaches
A plan must also be carried out. There are two approaches. They differ in when the model reads the tool results.
- Interleaved execution. The model chooses the next action after it reads the last observation. ReAct in Chapter 4 works in this way.
- Plan-and-execute. The model first writes the whole plan, usually as a list of tasks in a fixed format such as JSON, so that code can read it. Then an executor runs the tasks in order. It gives each result to the tasks that need it.
| Interleaved execution | Plan-and-execute | |
|---|---|---|
| When the model chooses actions | After each observation | Once, before the run |
| Model calls | One call for each action | Fewer calls |
| Use it when | A result decides which task comes next | The tasks are known, and only their input values are not known |
2.2 Replanning
A result can show that the plan cannot reach the goal. For example, a lookup does not give the information that a later task needs. Then the system changes the tasks that remain. This change is replanning. The system keeps the results that are still correct.
Plan-and-execute is therefore also a loop: plan → execute → examine the results → continue or replan.
Check 1 · Choose an approach
A search result decides which task comes next. Which approach fits, interleaved execution or plan-and-execute?
Read the answer
Interleaved execution. The model must read the result before it can choose the next task.
Part 3. ReWOO
ReWOO (Reasoning WithOut Observation) applies plan-and-execute to tool calls (Xu et al., 2023). The model plans all tool calls before it receives any tool result. For this reason, it does not read each observation to choose the next call. This gives fewer model calls and shorter inputs.
ReWOO has three parts:
- Planner. It writes all tool calls. A later call can use the result of an earlier call through a label, for example
#E1. - Worker. It runs the tool calls in order. It puts each result in the place of its label.
- Solver. It receives the plan and all results, and it writes the answer.
Planner → Worker → Solver
For the conference request, the planner writes “find the conference information” as #E1 and “find journeys to the venue in #E1” as #E2. The worker runs the two calls. The solver compares the arrival times with the start time.
Part 4. Search
4.1 States and paths
A plan can run and still fail. At each step, several choices are possible. An early choice can lead to a point from which the goal cannot be reached. Search explores several choices to find a path that reaches the goal.
Search uses three terms:
- A state is the current situation: the information and the partial work so far.
- An action changes one state into a new state.
- A goal test examines if a state satisfies the task.
The states and the actions between them make a search tree.
4.2 Backtracking
Task: use 4, 5, 6, and 10 once each to make 24, with +, −, ×, ÷. A state is the set of numbers that remain. An action combines two numbers into one number.
The left path leaves 2 and 50. No operation makes 24 from these two numbers.
After backtracking, the right path reaches the goal: (10 − 4) × 5 − 6 = 24. To backtrack, the system must keep the other choices, not only the current path.
4.3 Search order and pruning
A search procedure decides which state to expand next. To expand a state is to make its next states.
- Breadth-first search (BFS) expands all states at one depth before it goes deeper.
- Depth-first search (DFS) follows one branch to its end before it returns to other branches.
Pruning removes a branch that looks invalid or unlikely to succeed. This saves work. The search stops when it finds a solution, when no choice remains, or when it gets to a limit of time or calls.
Check 2 · Backtracking
In the example, a path leaves 2 and 50. What does backtracking do next?
Read the answer
It returns to an earlier state, for example 4, 5, 6, 10, and tries a different pair of numbers.
Part 5. Tree of Thoughts
A model usually writes one reasoning path. It keeps its first choices, also when they lead to a dead end. Tree of Thoughts (ToT) applies search to reasoning (Yao et al., 2023).
ToT repeats three steps:
- Generate. The model writes several possible next thoughts for each state.
- Evaluate. The model judges which partial solutions can still reach the goal.
- Select. The search procedure (BFS or DFS) keeps the best states and continues from them.
Generate → evaluate → select
In the make-24 task, the model proposes several next calculations. Then it judges which sets of numbers can still make 24. The model guides the search, and the search procedure keeps the alternatives for backtracking.
ReWOO and ToT help at different points:
| Method | What it organizes |
|---|---|
| ReWOO | Tool calls that the plan knows before the run |
| ToT | Reasoning paths when an early choice can fail |
Summary
- A plan is a set of tasks with dependencies. Each task gives an output that a later task uses.
- Interleaved execution reads each observation before the next action. Plan-and-execute plans first and then runs the tasks.
- Replanning changes the tasks that remain when a result shows that the plan cannot reach the goal.
- ReWOO plans all tool calls first: planner, worker, and solver.
- Search explores states and backtracks. Tree of Thoughts uses a model to generate and evaluate the states.
Lab
The lab builds a research team that uses plan-and-execute. A planner writes the task list. An executor gives each task to a role: researcher, writer, or editor. Each role receives the outputs of the earlier tasks.
- Run each role by hand. Pass the research notes to the writer, and the draft to the editor.
- Let a planner write the task list for a research question.
- Let the executor choose a role for each task and pass the earlier outputs automatically.
- Write your own plan for a question in your field, and run it.
- Trace one claim in the final report back to its source.
Materials and sources
- Yao et al., ReAct (2022): reasoning interleaved with actions.
- Xu et al., ReWOO (2023): planning separated from tool observations.
- Yao et al., Tree of Thoughts (2023): search over reasoning steps (implementation).
- Andrew Ng, Agentic AI: the lab adapts the research-agent project of Module 5.