HTN & evolutionary planning

Letting an LLM plan freely — ReAct, plan-and-execute — is flexible, but flexibility cuts both ways. A free-form planner can hallucinate a step, skip a precondition, or produce a plan you can’t verify before running it. For domains you understand well, you often want the opposite: structure. Classical AI planning offers it, and the most agent-relevant flavor is Hierarchical Task Network (HTN) planning — decompose a goal into subtasks using a library of known recipes, all the way down to directly-executable actions.

Compound tasks, primitives, and methods

HTN has three pieces:

• Primitive tasks — actions the agent can execute directly (call a tool, run a command).
• Compound tasks — higher-level goals that must be decomposed (e.g. “make dinner”).
• Methods — the recipes: a method says to accomplish this compound task (when its preconditions hold), do these subtasks in order. There can be several methods for one task, chosen by precondition.

Planning is then recursive decomposition: replace each compound task with the subtasks from an applicable method, and repeat, until nothing is left but an ordered list of primitives — the executable plan.

# Methods decompose compound tasks; anything without a method is a primitive.
methods = {
    "make_dinner":         ["prepare_ingredients", "cook", "serve"],
    "prepare_ingredients": ["wash", "chop"],
    "cook":                ["heat_pan", "fry"],
}

primitive_plan = []
def decompose(task, depth=0):
    print("  " * depth + task)
    if task in methods:                       # compound: expand via its method
        for sub in methods[task]:
            decompose(sub, depth + 1)
    else:                                      # primitive: emit it
        primitive_plan.append(task)

decompose("make_dinner")
print("primitive plan:", primitive_plan)

make_dinner
  prepare_ingredients
    wash
    chop
  cook
    heat_pan
    fry
  serve
primitive plan: ['wash', 'chop', 'heat_pan', 'fry', 'serve']

The high-level goal make_dinner expands through its methods into a flat, ordered list of primitives the agent can actually run. The structure is the point: each level is a known, named recipe.

Why structure helps — and what it costs

Because every step comes from a vetted method with preconditions, HTN plans are predictable and verifiable — the planner can’t invent an arbitrary action, and you can check a plan before running it. Methods are reusable across goals. The price is the method library: someone has to encode the domain knowledge, and HTN is rigid for genuinely novel tasks it has no method for.

When you can’t write the methods: evolutionary planning

Some problems are too open-ended to have a method library at all. There, evolutionary planning searches the plan space directly: keep a population of candidate plans, mutate and recombine them, score each with a fitness function (an environment reward or an LLM judge), select the fittest, and repeat over generations. It’s a population-based alternative to tree search — no need to know the structure up front, just a way to evaluate a plan. This is the engine behind LLM-driven program-and-plan discovery (AlphaEvolve-style systems) and connects directly to self-improving agents.

In one breath

• Free-form LLM planning is flexible but unpredictable; HTN planning adds classical structure for domains you understand.
• HTN has primitive tasks (executable), compound tasks (goals), and methods (recipes that decompose a compound task into subtasks under preconditions).
• Planning is recursive decomposition down to an ordered list of primitives (make_dinner → wash, chop, heat_pan, fry, serve) — predictable, verifiable, reusable.
• The cost is the method library (encoded domain knowledge) and rigidity on novel tasks; LLM-HTN hybrids keep the structure but let the LLM propose decompositions.
• When methods can’t be written, evolutionary planning searches the plan space — population + mutate/recombine + fitness + select — the basis of open-ended plan discovery.

Quick check

Next

HTN brings structure to a single agent’s planning; ReWOO brings efficiency to plan-execute, and Tree of Thoughts brings search. For how an agent accumulates reusable procedures over time, see skill libraries.