Foundations — Planning and task decomposition

Before we can talk about DAGs, search complexity, or ReAct loops, we must earn every piece of notation the parent note throws at you. Nothing below assumes you have seen these symbols before. We build each one from a picture.

---

1. What is an "agent", and what is a "goal"?

The picture below is the single mental model for this entire chapter: a start state on the left, a goal state on the right, and the agent trying to get from one to the other.

Look at the gap between the two dots. Everything in this topic — decomposition, planning, search — is a strategy for crossing that gap without getting lost.

We will use the letter $G$ for the goal throughout, exactly as the parent note does.

• $G$ ::: the goal — the state of the world we are trying to reach.

---

2. State — the snapshot of "how things are right now"

Why do we need a word for this? Because a plan is only valid relative to a state. "Grind the beans" is a sensible step only if the state says a grinder exists. The parent note's HTN algorithm literally reads the state to pick a method — that is why "state" must exist before "plan" can.

---

3. Action — the smallest thing an agent can do

Picture a fork in the road with $n$ branches. From each branch there are $n$ more forks, and so on. That fan-out is what makes planning hard — and it is exactly what decomposition tames.

• $n$ ::: the branching factor — how many actions are available at each step.

---

4. Depth $d$ — how many steps deep we must go

Now we can read the scary-looking symbol from the parent note. The number of distinct paths of length $d$, when each step has $n$ choices, is:

WHY this shape? Look at figure s02. Step 1 has $n$ branches. Each of those splits into $n$ at step 2, giving $n\times n=n^2$. After $d$ steps you have multiplied $n$ by itself $d$ times: $n^d$. That is the whole meaning of the exponent — repeated fanning-out.

• $d$ ::: the depth — number of steps from start to goal.
• $n^d$ ::: total number of length-$d$ paths through the search tree.

---

5. Big-O notation $O(\cdot )$ — "roughly how much work?"

WHY this tool and not just a plain number? Because we do not care whether it takes 1,000,000 or 1,050,000 operations — we care that it grows exponentially. Big-O throws away the noise and keeps the trend. That is the only comparison that matters when deciding whether a strategy scales.

• $O(n^d)$ ::: "work grows exponentially with depth" — the cost of naive, undecomposed search.

---

6. Subgoals and the number $k$ — splitting the mountain

So $\{G_1,\dots ,G_k\}$ reads: "the collection of $k$ subgoals, from the first to the $k$-th." Nothing more mysterious than numbered boxes.

Now the payoff formula from the parent note becomes readable. If each of the $k$ subgoals only needs depth $d/k$ (the total depth shared out equally), then:

WHY is this smaller? Because the exponent shrank from $d$ to $d/k$. A smaller exponent means far less fanning-out. With $n=10,d=6,k=3$: each subgoal has depth $6/3=2$, costing $10^2=100$, and three of them cost $3\times 100=300$ — versus a million. The figure makes the collapse visible.

• $k$ ::: the number of independent subgoals we split $G$ into.
• $G_i$ ::: subgoal number $i$ (a name-tag, not multiplication).
• $d/k$ ::: the depth each subgoal needs when the work is shared equally.

---

7. Graph, DAG, and dependencies

The figure shows the parent note's "summarize and compare two papers" plan drawn as a DAG. Notice which steps sit side-by-side (they can run at the same time) and which wait in line.

• $S_i$ ::: subtask number $i$ in the plan.
• $\parallel$ ::: "in parallel" — these steps can run at the same time.
• DAG ::: the arrow-diagram shape that a correct plan must have.

---

8. The three ways to build a plan

The parent note names three strategies. Here is the plain-words picture of each so the vocabulary is earned:

---

Prerequisite map

Follow the arrows: agents give us states and actions; actions give us branching and depth; those give the exponential cost; subgoals plus the DAG cut that cost — and all of it feeds the parent topic.

---

Where these plug into the rest of the vault

• The reasoning inside each Thought step comes from 5.3.02-Chain-of-thought-prompting.
• The tools an action can call are the subject of 6.2.01-Tool-augmented-LMs.
• Independent subgoals run by different agents connect to 6.2.03-Multi-agent-systems.
• Remembering results between steps needs 6.2.05-Memory-in-agents.
• When a step might fail or a fact is unsure, see 8.1.03-Reasoning-under-uncertainty.
• Full topic: the parent note.

---

Equipment checklist

Test yourself — you are ready for the parent note only if you can answer each without peeking:

• What are the three things an agent does in its loop? ::: Observe (look), think, act — then repeat.
• What is the difference between a state and a goal? ::: State = where things are now; goal = where we want them to be.
• What does the branching factor $n$ count? ::: The number of possible actions available at each step.
• What does $d$ mean, and what does $n^d$ count? ::: $d$ is plan length (depth); $n^d$ is the number of distinct length-$d$ paths.
• Why do we use Big-O instead of an exact count? ::: We care about how work grows (the trend), not the exact number, so we ignore constants.
• In $\{G_1,\dots ,G_k\}$, what is $k$ and what is the subscript on $G$? ::: $k$ is how many subgoals there are; the subscript is a name-tag (goal number $i$), not multiplication.
• Why is $k\cdot n^{d/k}$ smaller than $n^d$? ::: The exponent drops from $d$ to $d/k$, so each subproblem fans out far less; multiplying by $k$ is a tiny cost next to that shrink.
• What makes a graph a DAG, and why must a plan be one? ::: Directed (arrows point forward) and acyclic (no loops); a plan needs this so no step waits on itself in a circle.
• What does a topological sort produce? ::: A valid execution order where every dependency comes before the step that needs it.
• Which planning direction starts at the goal and works backward? ::: Backward chaining.