Phase 14 - Lesson 11

Planejamento com HTN e Busca Evolutiva

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

O planejamento simbólico lida com os casos em que o plano é comprovadamente correto. A busca evolutiva de código lida com os casos em que a função de fitness é verificável por máquina. O ChatHTN (2025) e o AlphaEvolve (2025) mostram o que cada um desbloqueia quando combinado com um LLM.

Tipo: Build Linguagens: Python (stdlib) Pré-requisitos: Phase 14 · 02 (ReWOO and Plan-and-Execute) Tempo: ~75 minutos

Objetivos de Aprendizado

• Explicar Hierarchical Task Networks: tarefas, métodos, operadores, pré-condições, efeitos.
• Descrever o loop híbrido do ChatHTN — busca simbólica com decomposição de fallback do LLM.
• Explicar o loop evolutivo do AlphaEvolve e por que ele só funciona com um avaliador programático.
• Implementar um planejador HTN de brinquedo e uma busca evolutiva de brinquedo na stdlib.

O Problema

ReWOO (Lesson 02), Plan-and-Execute e ReAct cobrem a maior parte do planejamento de agentes. Dois casos que eles não cobrem bem:

1. Planos com correção comprovável. Agendamento, rotas de voo, fluxos de trabalho de conformidade — o plano deve ser seguro por construção. Um plano fluente de LLM que às vezes alucina um passo é inaceitável.
2. Otimizações com uma função de fitness verificável por máquina. Multiplicação de matrizes, heurísticas de agendamento, passagens de compilador — o objetivo não é "um plano correto", mas "o melhor plano".

O planejamento HTN e o AlphaEvolve resolvem esses dois problemas diferentes. Ambos usam LLMs como amplificadores, não substitutos.

O Conceito

Hierarchical Task Networks

Um HTN consiste em:

• Tarefas — compostas (a serem decompostas) e primitivas (diretamente executáveis).
• Métodos — maneiras de decompor uma tarefa composta em subtarefas, com pré-condições.
• Operadores — ações primitivas com pré-condições e efeitos.
• Estado — um conjunto de fatos.

Planejamento: dada uma tarefa objetivo e um estado inicial, encontrar uma decomposição em operadores primitivos cujas pré-condições sejam satisfeitas em sequência.

O HTN é mais antigo que os LLMs e ainda é a referência para planos comprovadamente corretos.

ChatHTN (Gopalakrishnan et al., 2025)

O ChatHTN (arXiv:2505.11814) intercala o HTN simbólico com consultas ao LLM:

1. Tenta decompor a tarefa composta atual com os métodos existentes.
2. Se nenhum método se aplicar, pergunta ao LLM: "como você decomporia task no estado s?"
3. Traduz a resposta do LLM em subtarefas candidatas.
4. Valida em relação ao esquema do operador; rejeita decomposições inválidas.
5. Executa recursivamente.

A alegação central do artigo: cada plano produzido é comprovadamente seguro porque as sugestões do LLM entram apenas como decomposições candidatas, nunca como edições diretas do plano. A camada simbólica é responsável pela correção; o LLM expande a biblioteca de métodos.

O aprendizado de método online (continuação do OpenReview gwYEDY9j2x, 2025) adiciona um aprendiz que generaliza decomposições produzidas por LLM por meio de regressão — reduzindo a frequência de consultas ao LLM em até 75%.

AlphaEvolve (Novikov et al., 2025)

O AlphaEvolve (arXiv:2506.13131, DeepMind, junho de 2025) é uma proposta diferente: busca evolutiva de código orquestrada por um ensemble de Gemini 2.0 Flash/Pro.

Loop:

1. Começa com um programa semente + um avaliador programático (que retorna uma pontuação de fitness).
2. Um ensemble de LLMs propõe mutações.
3. Executa as mutações através do avaliador.
4. Mantém as melhores; faz novas mutações.

Vitórias publicadas:

• Primeira melhoria em relação a Strassen para multiplicação de matrizes complexas 4x4 em 56 anos (48 multiplicações escalares).
• 0,7% de computação do Google recuperada por meio de uma heurística de agendamento do Borg.
• Aceleração de 32% no FlashAttention em uma carga de trabalho de fronteira.

A restrição rígida: a função de fitness deve ser verificável por máquina. A busca evolutiva sobre respostas em prosa não converge.

Quando usar qual

Onde este padrão falha

• HTN sem operadores. Sem esquemas de pré-condição/efeito, a alegação de correção entra em colapso. O "LLM sugere decomposição" do ChatHTN exige o esquema para rejeitar movimentos inválidos.
• AlphaEvolve sem um avaliador real. "Perguntar ao LLM se o código é melhor" não é uma função de fitness. O avaliador deve ser determinístico e rápido.
• Superengenharia. A maioria das tarefas de agentes não precisa de nenhum dos dois. Use ReAct ou ReWOO primeiro.

Construa

O arquivo code/main.py implementa dois exemplos de brinquedo:

• Um planejador HTN em stdlib com operadores, métodos, pré-condições, efeitos e um LLMFallback que entra em ação quando nenhum método corresponde a uma tarefa composta. O "LLM" é um decompositor programado em script para que o planejador funcione offline.
• Uma busca evolutiva em stdlib sobre programas aritméticos: desenvolver expressões cuja saída minimize |f(x) - target| em um conjunto de testes. O avaliador é determinístico.

Execute-o:

python3 code/main.py

O rastreamento mostra o planejador HTN decompondo uma tarefa composta (com um fallback de LLM no meio do plano) e o loop evolutivo convergindo em uma expressão alvo.

Use

• Planejadores HTN — pyhop, SHOP3 ou crie o seu próprio para aplicação de políticas específicas do domínio.
• ChatHTN — código de pesquisa; o padrão (simbólico + fallback de LLM) é portado de forma limpa para qualquer planejador HTN.
• AlphaEvolve — artigo da DeepMind; o padrão (ensemble + avaliador) é reproduzível. O OpenEvolve e forks de código aberto semelhantes estão surgindo.
• Frameworks de agentes — nenhum deles oferece suporte nativo a HTN ou AlphaEvolve ainda. Construa como um subagente ou um trabalhador em segundo plano.

Ship It

O arquivo outputs/skill-hybrid-planner.md gera um esqueleto de planejador híbrido (HTN ou evolutivo) com a função do LLM explicitamente delimitada.

Exercícios

1. Estenda o planejador HTN com backtracking: quando uma pós-condição do operador falhar em tempo de execução, desfaça as alterações (roll back) e tente o próximo método.
2. Adicione um cache de método LLM ao ChatHTN: quando o LLM decompor a tarefa T no padrão de estado P, armazene o resultado. Verifique primeiro a biblioteca de métodos na próxima chamada.
3. Substitua o avaliador de busca evolutiva por uma suíte de testes real. Desenvolva uma função de ordenação que passe em 20 casos de teste; relate as gerações até a convergência.
4. Leia as notas de design do avaliador do AlphaEvolve. Projete um avaliador para um domínio de seu interesse (otimização de consultas SQL, minimização de suíte de testes, YAML de implantação).
5. Combine: use HTN para decompor uma tarefa composta em subtarefas e, em seguida, use a busca evolutiva no operador primitivo de cada subtarefa. Onde isso brilha e onde gera superengenharia?

Termos-Chave

Leitura Adicional

• Gopalakrishnan et al., ChatHTN (arXiv:2505.11814) — planejador híbrido simbólico + LLM
• Novikov et al., AlphaEvolve (arXiv:2506.13131) — busca evolutiva de código com mutações de LLM
• Anthropic, Building Effective Agents — quando recorrer a um planejador em vez de um loop simples