HTN & evolutionary planning

At 3:03 a.m., your deployment agent receives a simple request: “Ship version 2.4.1.”

The tests are green. The rollback artifact exists. Production has three instances. One is already serving a little more traffic than usual.

A free-form LLM planner might produce a sensible-looking sequence:

1. Deploy version 2.4.1.
2. Check health.
3. Monitor errors.
4. Roll back if needed.

The problem is step one. Deploy where? All three instances? One canary first? What counts as healthy? Who is allowed to approve an emergency release? If the model forgets to check the rollback artifact, you discover the omission after the bad release, which is an expensive time to learn anything.

You want the agent to be flexible about language but boring about operations.

Hierarchical Task Network planning, usually shortened to HTN planning, provides that shape. It represents a high-level task such as “release a version,” chooses a known method for accomplishing it, and recursively breaks that method into smaller tasks until only directly executable actions remain.

Evolutionary planning solves a different problem. It searches among candidate plans when you do not know the right decomposition in advance. Instead of asking, “Which recipe applies?” it asks, “Which of these many possible plans scores best?”

The techniques are related, but not interchangeable: HTN planning spends human effort up front to make execution predictable, while evolutionary planning spends computation during search to discover a good sequence.

The HTN mental model

An HTN has three core concepts.

A primitive task is an action the system can execute directly, such as deploy_canary, wait_5_minutes, or check_error_rate. It usually maps to a tool call, command, API operation, or function.

A compound task is a goal that still needs planning, such as release_version. It is not executable by itself. Telling a deployment API “release the version” is like telling a kitchen appliance “make dinner”: clear to a human, useless to a machine.

A method is a named recipe for completing a compound task. It specifies the subtasks and the conditions under which the recipe applies. A compound task can have several methods:

• safe_release, used when tests are green and a rollback artifact exists.
• emergency_release, used only for a critical incident with incident-commander authorisation.
• rollback_release, used when the new version fails a health check.

The planner starts with release_version, finds an applicable method, replaces the compound task with its subtasks, and repeats. This recursive decomposition continues until every leaf is primitive.

A primitive sequence is not automatically a valid plan. Each primitive has preconditions, facts that must be true before it runs, and effects, facts that become true or false afterward.

For example, deploy_canary_1 requires a ready artifact and an available first instance. Its effects include that instance one runs version 2.4.1 and traffic is routed through it. check_error_rate requires canary traffic, records the measured rate, and sets canary_check_passed to true only when the rate is at most 1.0 percent. deploy_remaining_2 requires canary_check_passed=true.

The method determines the shape of the work. Preconditions and effects determine whether each step is legal and whether later steps still make sense. Methods can also express ordering constraints or parallel work; the example uses a simple sequence to expose the mechanism.

Worked example: release one canary before the other two

Start with this state:

• The requested release artifact is version 2.4.1.
• Tests are green and a rollback artifact is ready.
• The first instance is available; production has three instances.
• The current error rate is 0.4 percent.
• Policy allows the remaining instances to deploy only if the canary error rate is at most 1.0 percent.

The initial task is the compound task release_version. Because the safe-release preconditions hold, the planner expands it into:

state = {"tests_green": True, "rollback_ready": True}

methods = {
    "release_version": [{
        "name": "safe_release",
        "when": lambda s: s["tests_green"] and s["rollback_ready"],
        "steps": [
            "deploy_canary_1",
            "wait_5_minutes",
            "check_error_rate",
            "deploy_remaining_2",
            "monitor_10_minutes",
        ],
    }]
}

primitive_plan = []

def decompose(task, depth=0):
    print("  " * depth + task)
    candidates = methods.get(task)

    if candidates is None:                 # primitive: emit it
        primitive_plan.append(task)
        return

    for method in candidates:              # compound: choose an applicable method
        if method["when"](state):
            print("  " * (depth + 1) + f"[{method['name']}]")
            for subtask in method["steps"]:
                decompose(subtask, depth + 1)
            return

    raise RuntimeError(f"No applicable method for {task}")

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

1. Deploy version 2.4.1 to one canary instance and route traffic to it.
2. Wait five minutes.
3. Check the canary error rate.
4. Deploy to the remaining two instances only if the check sets canary_check_passed=true.
5. Monitor for ten minutes.

The minimum planned observation time is fifteen minutes: five minutes before promotion and ten minutes afterward. That is the arithmetic implied by the policy, not a performance benchmark.

If the check reports 0.8 percent, it records the measurement and sets canary_check_passed=true; promotion is allowed because 0.8 is at most 1.0. If it reports 1.4 percent, the fact is false, so the promotion precondition fails. The executor must not deploy the remaining instances. It should follow the recovery policy:

1. Stop promotion.
2. Route traffic away from the canary.
3. Restore the previous version.
4. Record the failed release.

The LLM did not need to remember this policy in natural language. The method and executable checks encode it. Both the successful path and the failure branch have explicit state transitions.

The executor must still re-check critical facts immediately before side effects. The world can change while a plan waits in a queue: the artifact can be revoked, the canary can become unhealthy, or authorisation can expire. A plan is a prediction about the world, not a reservation on it.

What HTN buys you

HTN gives you bounded action choice. A free-form model can invent an action because it sounds plausible; an HTN executor can choose only from registered methods and primitives. Plans are therefore easier to inspect before execution.

It also gives you reuse. The same safe_release method can serve a chat request, scheduled release, or incident workflow. Fix the policy once instead of hoping every prompt describes it correctly.

Finally, it enables local verification. You can check that safe_release requires a rollback artifact, that deploy_remaining_2 requires a passed canary, and that a primitive receives a valid version identifier.

The cost is the method library. Someone must define “safe release,” encode its conditions, test alternatives, and maintain them as systems change. If the library says production has three instances but production has five, formal structure does not make it correct.

HTN is also a poor fit for tasks whose structure is genuinely unknown, such as finding a novel research hypothesis. A library can constrain the search so heavily that the agent becomes reliable at yesterday’s problem but helpless with today’s.

The production pattern: let the LLM propose, not overrule

An LLM-HTN hybrid works when users express goals loosely but operations have hard rules.

The LLM can turn “ship the hotfix” into a typed task such as release(version="2.4.1"), choose a candidate method, explain its choice, or suggest a new method for review. A deterministic planner must then verify that the method exists, arguments have the right types, and preconditions hold.

A practical pipeline is:

1. Parse the request into a task and typed arguments.
2. Resolve phrases such as “latest version” to an immutable artifact identifier.
3. Load a fresh state snapshot.
4. Select an applicable method and recursively decompose it.
5. Validate preconditions, authorisation, ordering, and resource limits.
6. Request approval at the defined risk boundary.
7. Execute one primitive at a time, re-checking state after side effects.
8. Continue, recover, or replan, while recording the task tree and tool results.

Approval belongs before the dangerous primitive, not after the plan completes. A low-risk service might approve safe_release; a payment service might require approval immediately before fleet promotion.

Planning does not replace ordinary engineering safeguards. A charge primitive needs an idempotency key; an infrastructure primitive needs locking or conflict handling. Generated methods belong in a sandbox and require validation before promotion.

Choosing HTN over the alternatives

The deciding questions are whether the domain structure is known and how costly a wrong action would be.

Use HTN for deployments, loan approvals, fulfilment, or incident procedures when the organisation already has a correct process. Do not use it to make a two-step script sound intelligent; a normal function or workflow is clearer.

When methods are missing: evolutionary planning

Suppose a release simulator can model canary sizes, observation windows, traffic shifts, rollback delays, and error bursts. You want a rollout that finishes quickly without exceeding a risk threshold, but nobody knows the best sequence. That is a search problem.

Evolutionary planning maintains a population of candidate plans. Each candidate is a sequence or structured policy. The system evaluates candidates with a fitness function, selects strong candidates, mutates them, sometimes recombines two candidates, and repeats for several generations.

For example, 12 plans across 25 generations require 300 evaluations. At four seconds per simulation, a serial run takes 1,200 seconds, or 20 minutes. Parallel workers reduce elapsed time but not the compute cost.

A candidate might deploy one canary, wait five minutes, shift 10 percent of traffic, wait again, check errors, and shift the rest. Another might use two canaries and a shorter observation window. The score could reward low rollout time, penalise resources, and reject simulated error rates above 1.0 percent.

The evaluator matters more than the mutation operator. A plan that promotes the fleet before a successful canary check should be invalid, not merely given a slightly worse score. Otherwise an unsafe plan can win by compensating for danger with speed.

For example:

• Candidate A takes 15 minutes and keeps errors at 0.8 percent; it is valid.
• Candidate B takes 9 minutes but reaches 1.4 percent; it must be rejected under a 1.0 percent limit.
• Candidate C takes 18 minutes and stays at 0.3 percent; it may beat A if fewer errors are worth three extra minutes.

Evolutionary search does not need a complete HTN hierarchy, but it still needs an action vocabulary, constraints, and a simulator or test harness. It is not guaranteed to find the global best plan: populations can converge early, recombination can create invalid orderings, and noisy evaluators can reward lucky runs. Keep candidate validation separate from subjective quality scoring.

This makes evolutionary planning a better fit for scheduling, simulator-backed control, program synthesis, and configuration optimisation than for real refunds or deletions. Search is appropriate when candidate evaluation is cheap and safely repeatable.

Tree of Thoughts explores explicit alternatives through tree search. Evolutionary planning explores a population and uses selection across generations. Both search, but their bookkeeping and failure modes differ.

Failure modes you will see first

No applicable method. The request is understood, but no method matches the current state. The cause may be legitimate, such as a missing rollback artifact, or mundane, such as a stale state field. Log failed conditions and expose a recovery path; do not ignore the condition to improve completion rates.

A tool call fails after planning. Conflicts, permission denials, or missing resources mean the state model was incomplete or stale. Re-read critical state before the side effect, make primitives idempotent where possible, and define recovery methods.

The model bypasses the hierarchy. If the trace contains a direct deploy_all, the executor probably accepts arbitrary model-generated calls. Give it a closed vocabulary of primitives and reject calls not produced by validated decomposition.

Decomposition never finishes. Self-expanding methods or cycles can exhaust time or depth. Add cycle detection, a maximum depth, and tests that every supported task reaches primitives.

The agent is reliable but useless. An incomplete hierarchy may reject every unfamiliar request or satisfy the words while missing the intent. Let the LLM propose clarification or a candidate method for review; do not quietly loosen executor rules.

Record the task tree, selected method, precondition results, primitive inputs, tool outcomes, and state changes. Agent observability and evaluating agents cover the surrounding practice.

In one breath

HTN planning is recipe-based planning. A compound task such as release_version expands through an applicable method such as safe_release until only primitive tasks remain.

The hierarchy limits what the agent may do. Preconditions and effects determine whether each action is valid, while runtime checks account for a changing world.

HTN fits known, consequential workflows, but its price is a maintained method library. An LLM can translate intent, choose known methods, or propose new ones; it should not bypass the registry, authorisation checks, or executor.

Evolutionary planning addresses the opposite gap: when candidate plans can be evaluated but no complete hierarchy is known. It evolves plans through mutation, recombination, and selection, with the evaluator and its hard constraints determining whether the result is safe or merely fast.

Quick check

Next

HTN gives one agent a controlled decomposition hierarchy. ReWOO reduces wasted observations in plan-and-execute workflows, while Tree of Thoughts searches explicit alternatives. For reusable procedures that agents accumulate over time, see skill libraries.