HTN and Evolutionary Planning

In plain words

Think of your college time-table. Some plans must simply not break the rules, and a fluent AI answer is not good enough. An HTN planner breaks a big task into small ones and refuses any step whose precondition is false, so the plan is correct by construction. Evolutionary search is the other tool: when you can score a candidate with a small program, you mutate, score, keep the best, and repeat.

How it flows

A tiny example

state = {"has_account"}
for step in decompose("book_ticket"):
    pre, eff = OPERATORS[step]
    if not pre <= state:
        reject(step)      # LLM may suggest, schema decides
        break
    state |= eff
print(plan)

Notice that the suggestion is checked against the operator's precondition before it is ever allowed into the plan.

What you will learn

• What an HTN planner is, in plain words: tasks, methods, operators, state.
• How a symbolic planner can use an LLM for help without letting it break the rules.
• What evolutionary search is, and why it needs a score you can compute by machine.
• When to skip both of these and just use a normal agent loop.

The problem, simply

Think about your college time-table committee. They have to fit 60 subjects, 20 rooms and 40 teachers into one week. There are hard rules. One teacher cannot be in two rooms at 10 am. A lab needs two continuous hours. If the final time-table breaks even one of these rules, it is useless.

Now ask an AI chatbot to make that time-table. It will give you something that looks beautiful. And somewhere in the middle, Prof. Rao is teaching two classes at the same time. The output was fluent, not correct. That is problem one: some plans must be correct by construction, not by luck.

Problem two is different. Suppose the time-table is already valid, and now you want the best one. Least gaps for students, least walking between blocks. Here you do not need a proof. You need a way to score any time-table with a small program, then hunt for a higher score.

Two problems, two tools. Normal agent loops like ReAct (the think-act-observe loop from Module 1) handle neither one well.

The idea

Hierarchical Task Networks, in four words

HTN stands for Hierarchical Task Network. It is a planning method much older than LLMs. It has exactly four parts.

• State — a set of facts that are true right now. Like {"logged_in", "seat_available"}.
• Task — something you want done. A compound task is big and must be broken down. A primitive task can be done directly.
• Method — a recipe that breaks one compound task into smaller subtasks. Each method has a precondition: when is this recipe allowed.
• Operator — one primitive action. It has a precondition (what must be true before) and an effect (what becomes true after).

Planning means: start from the goal task, keep applying methods until everything is primitive, and check that every operator's precondition holds at that point. If it does not, that branch is thrown away.

So the planner cannot output a step whose precondition is false. Correctness is not a hope here, it is enforced by the machinery.

Worked example: Priya books a train ticket

Priya's agent gets the compound task book_ticket. The method library says: to book a ticket, do login, then search_train, then select_seat, then pay.

State at the start is {"has_account"}. The operator login needs has_account — true, so it runs and adds logged_in. search_train needs logged_in — true now, and it adds seat_available. So select_seat runs and adds seat_selected. Finally pay needs seat_selected and wallet_ok.

But wallet_ok is not in the state. A chatbot would happily write "Step 4: pay ₹1,250." The HTN planner refuses. That branch dies, and it looks for another method — maybe one that does add_money first.

ChatHTN: where the LLM comes in

The weakness of plain HTN is obvious. Somebody has to write every method by hand, and if a compound task has no matching method, the planner is stuck. ChatHTN is a 2025 research idea that fixes this with a hybrid loop.

The key point, and interviewers like this one: the LLM's answer never goes straight into the plan. It only enters as a candidate decomposition. The symbolic layer still checks every precondition and effect, and throws the suggestion away if it does not fit. The LLM grows the method library; it never edits the plan.

A follow-up idea adds a learner that remembers and generalises those decompositions, so you stop paying for the same call again and again. The reported cut in query frequency was up to seventy-five percent.

IMP

Note: If you drop the operator schema, the whole soundness claim collapses. The schema is the thing doing the rejecting. Without it, ChatHTN is just an LLM writing plans.

AlphaEvolve: search by scoring, not by proving

AlphaEvolve, also from 2025, is a different animal: evolutionary code search driven by a group of LLMs.

You start with a seed program and an evaluator — a small deterministic program that takes any candidate and returns a fitness score. The LLMs propose mutations. Each mutation is run through the evaluator. Keep the best few, mutate those again, repeat for many generations.

Reported wins include the first improvement over the Strassen method for 4x4 complex matrix multiplication in fifty-six years, down to 48 scalar multiplications. Also a scheduling heuristic that recovered about 0.7% of Google's compute, and a 32% speedup on a FlashAttention workload.

Here is the hard constraint. The fitness function must be machine-checkable, deterministic and fast. "Ask the LLM if this version is better" is not a fitness function — the score wobbles and the search never converges. If your goal is an essay, this will not help you.

Which one, when

• Scheduling with hard rules, compliance flows, policy-bound automation — HTN. Preconditions are how you encode policy.
• Compiler passes, matrix tricks, "make this code pass 20 tests and run faster" — evolutionary search. The test suite is your evaluator.
• Everything else, which is most agent work — a plain ReAct or plan-and-execute loop.

IMPRemember: HTN gives you a plan that is provably correct; evolutionary search gives you a plan that scores highest. Ask which one your problem actually needs before writing any code.

Build it

"""Toy HTN planner with an LLM fallback, plus a toy evolutionary search."""
import random

# --- HTN part -------------------------------------------------------
# operator name -> (preconditions needed, effects added)
OPERATORS = {
    "login":       ({"has_account"}, {"logged_in"}),
    "search":      ({"logged_in"}, {"seat_found"}),
    "add_money":   ({"logged_in"}, {"wallet_ok"}),
    "pay":         ({"seat_found", "wallet_ok"}, {"booked"}),
}
# compound task -> list of subtasks (our hand written method library)
METHODS = {"book_ticket": ["login", "search", "pay"]}

def fake_llm(task):
    """Stands in for a real model. Suggests a fix, still gets validated."""
    return ["login", "search", "add_money", "pay"] if task == "book_ticket" else []

def plan(task, state, ask_llm=False):
    """Return a list of primitive steps, or None if no sound plan exists."""
    candidates = [METHODS.get(task)] if task in METHODS else []
    if ask_llm:
        candidates.append(fake_llm(task))      # LLM only proposes
    for steps in candidates:
        if not steps:
            continue
        s, ok = set(state), True
        for step in steps:                     # symbolic layer validates
            pre, eff = OPERATORS[step]
            if not pre <= s:                   # precondition not met
                ok = False
                break
            s |= eff
        if ok:
            return steps
    return None

# --- Evolutionary part ----------------------------------------------
TARGET = 42
def fitness(n):
    """Deterministic, machine checkable. Higher is better."""
    return -abs(n - TARGET)

def evolve(seed=3, generations=12):
    best = seed
    for g in range(generations):
        kids = [best + random.choice([-7, -3, -1, 1, 3, 7]) for _ in range(6)]
        winner = max(kids + [best], key=fitness)
        if fitness(winner) > fitness(best):
            best = winner
            print(f"  gen {g:>2}: value={best:<4} score={fitness(best)}")
    return best

if __name__ == "__main__":
    random.seed(7)
    print("hand method only :", plan("book_ticket", {"has_account"}))
    print("with LLM fallback:", plan("book_ticket", {"has_account"}, True))
    print("Evolving towards", TARGET)
    print("best found:", evolve())

Look at the two HTN lines. With only the hand-written method you get None, because pay needs wallet_ok and nothing set it. With the fallback on, the LLM's suggestion is accepted — but only because it passed the same precondition check.

Then look at the evolution trace. The score only moves upward, because every candidate is scored by the same small deterministic function.

Where you will see this

• Airline and railway scheduling, where a plan that breaks a rule cannot ship at all.
• Bank and insurance workflow engines, where preconditions are literally the compliance policy.
• Coding agents like Claude Code, Cursor and GitHub Copilot running your test suite in a loop — the tests are the evaluator, and that loop is a simple evolutionary search.
• Compiler and database query optimisers, searching over machine-scored candidates for decades now.
• Swiggy or Flipkart style delivery-route and slot-assignment systems, where a valid route matters more than a pretty explanation.

Common mistakes

• Using HTN without operator preconditions and effects. Then nothing is rejecting bad steps, and you have lost the only reason to use HTN.
• Letting the LLM write into the plan directly. The moment an unvalidated suggestion becomes a plan step, your soundness guarantee is gone.
• Using an LLM as the fitness function. Its scores are not stable, so the search has no real signal and wanders instead of converging.
• Reaching for these tools too early. Most agent tasks are happy with a plain loop. Building a planner for a three-step task is wasted effort you will have to maintain.
• Forgetting to cache LLM decompositions. You end up making the same expensive call for the same task in the same state, again and again.

If they ask in an interview

Q: How can a planner use an LLM and still promise a correct plan?

A: The LLM is only allowed to propose, never to decide. Its suggested decomposition is checked against the operator schema, so any step whose precondition is not satisfied is thrown away. The symbolic layer owns correctness; the LLM only widens what the planner knows how to break down.

Q: When would you pick evolutionary search over a normal agent loop?

A: Only when I have a fast, deterministic, machine-checkable score — a test suite, a benchmark timing, a cost number. Then the search has real signal and improves across generations. If a human has to judge the output, it will not converge.

Q: What is the difference between a method and an operator in HTN?

A: A method is a recipe that breaks a compound task into subtasks, with a condition saying when it applies. An operator is a single primitive action with a precondition and an effect. Methods build the tree; operators are the leaves that actually run.

Try these

1. Add backtracking to the toy planner, and print which methods were tried and rejected on the way.
2. Add a cache: when the fake LLM decomposes a task, store it as a new method and check the library first next time. Count the calls you saved.
3. Replace the evolutionary target with a real evaluator — five test cases for a sorting function, scored by how many pass. Report generations to convergence.
4. Add an operator whose precondition nothing ever satisfies, then confirm the planner refuses every plan using it instead of silently including it.

Words, simply

Quick recap

• HTN plans are correct by construction because every precondition is checked; an LLM may suggest decompositions but never edits the plan.
• Evolutionary search works only when a fast deterministic program can score a candidate — never an LLM's opinion.
• Most agent tasks need neither. Start with a plain loop; add a planner only when correctness or optimality is really at stake.