Parte IV · Cap. 16 — Planejamento e Busca
Simbólica · Planejamento/decisão · Busca em espaço de estados. Encontra uma sequência de ações que leva de um estado inicial a um objetivo. Card:
../02-tipos-de-ia/01-simbolica.kmd.
🎨 Figura
F-IV.16.0— Do estado inicial ao objetivo. Brief: grafo de estados com um caminho destacado por A*; nós expandidos vs podados; meta sinalizada.
1. Definição e história curta
Resolve problemas como busca num espaço de estados/ações. Base de robótica, logística e jogos desde os anos 1970 (STRIPS, Shakey — ver Parte III, era 2).
2. Fundamentos
- Teoria de grafos — espaços de estados como grafos.
- Combinatória / complexidade — explosão do espaço de busca.
- Otimização / heurística — funções de avaliação admissíveis.
- Lógica — representação de ações (pré-condições/efeitos).
3. Algoritmos e arquiteturas
- Busca não-informada — BFS, DFS, custo uniforme.
- Busca heurística — A\*, IDA*, greedy best-first.
- Planejamento clássico — STRIPS, PDDL (ações com pré-condição/efeito).
- Sob incerteza — MDP/POMDP (ponte com RL, cap. 26).
4. Insumos
- Hardware: CPU; busca pode ser intensiva.
- Dados: modelo do domínio (estados, ações, custos) — não dados de treino.
- Estruturas de dados: fila de prioridade (A*), grafo de estados, closed set.
- Sistemas: planejadores PDDL, bibliotecas de busca.
5. Ciclo de vida especializado
| Etapa | Especialização |
|---|---|
| 0 Problema | Definir estados, ações, objetivo, custos |
| 1 Dados | Modelar o domínio (PDDL); heurísticas |
| 2 EDA | Tamanho do espaço, fator de ramificação |
| 3 Modelagem | Escolher algoritmo e heurística admissível |
| 4 "Treino" | Não há — há modelagem do domínio (ou aprender heurística) |
| 5 Avaliação | Optimalidade, nós expandidos, tempo |
| 5.5 Homologação | Casos extremos, garantia de solução |
| 6 Produção | Planejar online/replanejar sob mudanças |
| 7 Monitoramento | Falhas de plano, tempo de resposta |
| 8 Manutenção | Atualizar modelo do domínio |
| 9 Governança | Segurança das ações planejadas |
6. Capacidades, modos e modalidades
Estratégico/intelectual: rotas, logística, escalonamento, robótica, jogos; soluções ótimas e garantidas quando o domínio é modelável.
7. Limites, riscos e ética
Explosão combinatória; depende de modelo exato do domínio; pouca adaptação a incerteza/ruído (daí a ponte com RL e aprendizado de heurística).
8. Estado da arte e exemplos
A* em mapas/jogos, planejadores PDDL, task and motion planning em robótica; neural-guided search (rede aprende heurística) liga este capítulo ao neuro-simbólico (cap. 32) e ao AlphaZero (cap. 27).