A Arte de Ensinar Máquinas a Resolver Problemas
Coleção Escola de Lógica Matemática
JOÃO CARLOS MOREIRA
Doutor em Matemática
Universidade Federal de Uberlândia
Copyright©2013-2025 Coleção Escola de Lógica Matemática. Todos os direitos reservados.
Imagine um robô em Marte que precisa coletar amostras de solo, fotografar formações rochosas e retornar à base antes que uma tempestade de areia chegue. Como ele decide a ordem das tarefas? Como calcula o melhor caminho? Como adapta seus planos quando encontra obstáculos inesperados? Bem-vindo ao fascinante universo do planejamento automático, onde ensinamos máquinas a pensar estrategicamente, resolver problemas complexos e tomar decisões inteligentes de forma autônoma. Esta é a história de como transformamos problemas do mundo real em quebra-cabeças matemáticos que computadores podem resolver.
Planejar é uma atividade fundamentalmente humana. Desde organizar nossa rotina matinal até traçar metas de vida, constantemente criamos sequências de ações para alcançar objetivos. O planejamento automático transporta essa habilidade para o mundo computacional, permitindo que sistemas artificiais raciocinem sobre o futuro, antecipem consequências e escolham caminhos ótimos para atingir metas complexas.
A jornada do planejamento automático começou na década de 1950, quando pioneiros da inteligência artificial sonhavam com máquinas capazes de resolver problemas como humanos. O General Problem Solver de Newell e Simon foi uma das primeiras tentativas de criar um sistema universal de resolução de problemas. Desde então, o campo evoluiu dramaticamente, passando por marcos como o STRIPS nos anos 1970, o planejamento hierárquico nos anos 1980, até os modernos sistemas que controlam missões espaciais e dirigem carros autônomos.
Todo sistema de planejamento automático possui três elementos essenciais: estados (representações do mundo), ações (formas de modificar o mundo) e objetivos (situações desejadas). Como um maestro regendo uma orquestra, o planejador coordena esses elementos para compor uma sinfonia de decisões que levam do estado inicial ao objetivo desejado.
Planejar automaticamente não é tarefa simples. O espaço de possibilidades cresce exponencialmente com o número de ações e objetos. Um problema aparentemente simples, como organizar blocos em uma mesa, pode ter bilhões de estados possíveis. Adicione restrições temporais, recursos limitados e incerteza, e o desafio se torna monumental. É como jogar xadrez em múltiplos tabuleiros simultaneamente, onde as regras podem mudar durante o jogo.
O planejamento automático não é apenas teoria acadêmica; ele move o mundo moderno. Satélites usam planejadores para agendar observações da Terra. Fábricas inteligentes otimizam linhas de produção em tempo real. Assistentes virtuais organizam nossas agendas. Games criam narrativas dinâmicas que se adaptam às escolhas dos jogadores. Em hospitais, sistemas planejam tratamentos personalizados considerando milhares de variáveis médicas.
O planejamento automático é profundamente matemático. Utilizamos teoria dos grafos para representar espaços de estados, álgebra booleana para expressar condições, teoria da complexidade para analisar algoritmos, e probabilidade para lidar com incerteza. Cada problema de planejamento pode ser visto como uma busca em um grafo gigantesco, onde nós são estados e arestas são ações.
O planejamento automático é um dos pilares da inteligência artificial simbólica. Diferente do aprendizado de máquina que extrai padrões de dados, o planejamento raciocina explicitamente sobre causas e efeitos, construindo cadeias lógicas de ações. É a diferença entre reconhecer um gato em uma foto (aprendizado) e descobrir como resgatar um gato preso em uma árvore (planejamento).
Este livro é sua porta de entrada para o universo do planejamento automático. Exploraremos desde conceitos fundamentais até técnicas avançadas, sempre com exemplos práticos e intuições claras. Aprenderemos a pensar como um planejador automático, decompondo problemas complexos em componentes manejáveis, identificando padrões e aplicando algoritmos poderosos.
O planejamento automático é onde a matemática encontra a criatividade, onde algoritmos encontram problemas reais, onde máquinas aprendem a pensar estrategicamente. É um campo vibrante, em constante evolução, com desafios fascinantes e aplicações que mudam o mundo. Prepare-se para uma jornada intelectual emocionante, onde cada conceito aprendido abre portas para novas possibilidades. Vamos começar nossa exploração mergulhando no conceito fundamental de estados - as peças básicas do quebra-cabeça do planejamento!
Feche os olhos e imagine sua cozinha neste exato momento. Onde está cada objeto? Quais portas estão abertas? O fogão está ligado? Essa imagem mental que você criou é semelhante a um estado em planejamento automático - uma fotografia completa de como o mundo está em um determinado instante. Mas como ensinamos um computador a "ver" e representar o mundo? Como capturamos a essência de situações complexas em estruturas que máquinas possam processar? Neste capítulo, descobriremos a arte e a ciência de representar mundos em bits e bytes.
Um estado é uma descrição completa e instantânea do mundo relevante para nosso problema. Como uma partida de xadrez congelada no tempo, o estado captura todas as informações necessárias para determinar quais ações são possíveis e qual será o resultado de cada ação. A escolha de o que incluir no estado é crucial: informação demais torna o problema intratável; informação de menos torna impossível planejar corretamente.
A forma mais simples de representar estados usa proposições booleanas - afirmações que podem ser verdadeiras ou falsas. "O robô está na sala A", "A porta está aberta", "A caixa foi entregue" são exemplos de proposições. Um estado é então um conjunto de proposições verdadeiras. Esta representação é intuitiva e poderosa o suficiente para muitos problemas práticos.
Para domínios mais ricos, usamos variáveis que podem assumir múltiplos valores. Em vez de múltiplas proposições como "robô_na_sala", "robô_na_cozinha", "robô_no_quarto", temos uma única variável posição_robô com valores possíveis {sala, cozinha, quarto}. Esta abordagem é mais compacta e naturalmente garante exclusão mútua - o robô não pode estar em dois lugares ao mesmo tempo.
Muitos problemas envolvem múltiplos objetos com propriedades similares. Um armazém pode ter dezenas de caixas, cada uma com posição, peso e conteúdo. Representações orientadas a objetos capturam esta estrutura naturalmente, tratando cada entidade como uma instância com atributos. Isso facilita a generalização - o mesmo planejador pode funcionar com 3 ou 300 caixas.
O conjunto de todos os estados possíveis forma o espaço de estados - um universo de configurações que nosso sistema pode assumir. Para n proposições booleanas, existem 2ⁿ estados possíveis. Com apenas 20 proposições, já temos mais de um milhão de estados! Esta explosão exponencial é um dos grandes desafios do planejamento, exigindo representações e algoritmos inteligentes.
Na vida real, raramente conhecemos o estado completo do mundo. Um robô explorador pode não saber o que há atrás de uma porta fechada. Um sistema médico pode desconhecer certas condições do paciente. Representamos esta incerteza através de crenças - distribuições de probabilidade sobre estados possíveis, ou conjuntos de estados compatíveis com nossas observações.
Problemas complexos requerem múltiplos níveis de abstração. Planejar uma viagem internacional envolve desde decisões de alto nível (quais cidades visitar) até detalhes minuciosos (qual assento escolher no avião). Estados hierárquicos permitem raciocinar em diferentes granularidades, focando nos detalhes relevantes para cada decisão.
Alguns domínios requerem representação explícita do tempo. Um estado temporal inclui não apenas o que é verdade, mas quando. Compromissos têm horários, recursos têm prazos de validade, ações têm durações. Esta dimensão temporal adiciona riqueza e complexidade à representação, permitindo modelar problemas mais realistas.
Nem toda combinação de valores forma um estado válido. Um objeto não pode estar em dois lugares simultaneamente. Um recipiente não pode conter mais que sua capacidade. Restrições de integridade garantem que nossos estados façam sentido, evitando situações impossíveis que confundiriam o planejador.
A representação de estados é a fundação sobre a qual construímos todo o edifício do planejamento automático. Como escolhemos representar o mundo determina quais problemas podemos resolver, quão eficientemente podemos resolvê-los, e quão naturais serão as soluções. É uma arte que equilibra expressividade com tratabilidade, detalhe com abstração, generalidade com eficiência.
Estados são mais que dados - são a linguagem através da qual máquinas compreendem e raciocinam sobre o mundo. Dominar esta linguagem é essencial para criar sistemas inteligentes que navegam a complexidade do mundo real. Com esta base sólida, estamos prontos para o próximo passo: entender como ações transformam estados, criando a dinâmica que torna o planejamento possível e poderoso!
Se estados são fotografias do mundo, ações são os verbos que transformam uma foto em outra. Abrir uma porta, mover uma peça, enviar uma mensagem - cada ação é uma ponte entre o que é e o que será. Mas como capturamos a essência de uma ação em termos que um computador possa entender? Como modelamos não apenas o que uma ação faz, mas quando pode ser feita e quais são suas consequências? Neste capítulo, exploraremos o coração pulsante do planejamento: as ações que dão vida aos planos.
Uma ação em planejamento automático não é apenas um nome; é uma estrutura rica que especifica precisamente quando pode ser executada e o que acontece quando é. Como uma receita detalhada, cada ação tem ingredientes necessários (pré-condições) e resultado garantido (efeitos). Esta precisão permite que sistemas automatizados raciocinem sobre sequências de ações sem ambiguidade.
O STRIPS (Stanford Research Institute Problem Solver) revolucionou a representação de ações nos anos 1970 e continua influente hoje. No STRIPS, uma ação tem pré-condições (o que deve ser verdade), lista de adição (o que se torna verdadeiro) e lista de remoção (o que deixa de ser verdadeiro). Simples mas poderoso, este modelo captura a essência de mudança de estado.
Em vez de definir uma ação separada para cada objeto, usamos parâmetros para criar esquemas de ação. "Mover(X, de_Y, para_Z)" representa infinitas ações específicas - mover caixa de A para B, mover robô de C para D. Esta parametrização torna a representação compacta e o raciocínio mais eficiente.
O mundo real é cheio de nuances. Abrir uma porta só deixa entrar luz se for dia. Regar plantas só as mantém vivas se não estiver congelando. Efeitos condicionais capturam estas sutilezas, permitindo que ações tenham consequências diferentes dependendo do contexto. Esta flexibilidade é crucial para modelar domínios realistas.
Muitas ações levam tempo. Cozinhar um bolo demora 30 minutos, voar de São Paulo a Nova York leva 10 horas. Ações durativas têm condições no início, condições mantidas durante a execução, e efeitos no fim. Modelar duração permite otimização temporal e execução paralela de ações compatíveis.
Nem sempre sabemos exatamente o que uma ação produzirá. Lançar um dado, fazer um investimento, tratar uma doença - muitas ações têm resultados probabilísticos. Ações estocásticas modelam esta incerteza, associando probabilidades a diferentes efeitos possíveis. Planejar com incerteza requer técnicas especiais que exploraremos em capítulos futuros.
Ações frequentemente consomem recursos - combustível, dinheiro, tempo, energia. Modelar recursos explicitamente permite planejamento mais realista. Um drone de entrega deve considerar autonomia de bateria, um robô de construção deve gerenciar materiais disponíveis. Recursos criam restrições adicionais mas tornam planos mais robustos.
Ações não existem no vácuo - elas interagem de formas complexas. Duas ações podem ser mutuamente exclusivas (dois robôs não podem ocupar o mesmo espaço), sinérgicas (carregar duas caixas no mesmo caminhão economiza combustível), ou ter efeitos cumulativos. Entender estas interações é crucial para planejamento eficiente.
Problemas complexos beneficiam-se de hierarquias de ações. "Preparar jantar" decompõe-se em "comprar ingredientes", "cozinhar" e "servir", cada uma decompondo-se em ações mais específicas. Ações abstratas permitem planejar em múltiplos níveis, refinando detalhes conforme necessário.
Antes de executar no mundo real, podemos simular ações para prever consequências. Um simulador aplica ações a estados, gerando trajetórias possíveis. Isso permite testar planos, identificar problemas e otimizar sequências sem riscos ou custos reais.
Ações são os motores da mudança no mundo do planejamento. São elas que transformam possibilidade em realidade, intenção em execução. Compreender profundamente como modelar e raciocinar sobre ações é essencial para criar sistemas que não apenas pensam, mas agem de forma inteligente e eficaz. Com estados para representar o mundo e ações para transformá-lo, falta apenas uma peça: os objetivos que direcionam todo o processo de planejamento!
Todo plano começa com um sonho, uma visão de como queremos que o mundo seja. Na vida, chamamos isso de objetivos ou metas. No planejamento automático, objetivos são descrições formais de estados desejados - o destino para onde nossos planos devem nos levar. Mas como expressamos desejos complexos em linguagem que máquinas entendam? Como equilibramos múltiplos objetivos conflitantes? Como lidamos com metas que evoluem com o tempo? Este capítulo explora a arte de definir o que queremos alcançar.
Um objetivo é mais que um estado específico - é uma caracterização de estados aceitáveis. Quando pedimos pizza, não especificamos a posição exata de cada molécula; descrevemos propriedades desejadas: pizza quente, saborosa, entregue em casa. Esta flexibilidade permite que planejadores encontrem qualquer solução satisfatória, não apenas uma predeterminada.
A maioria dos problemas reais envolve múltiplos sub-objetivos que devem ser satisfeitos simultaneamente. Preparar um jantar romântico requer comida pronta, mesa arrumada, música ambiente e velas acesas - todos verdadeiros ao mesmo tempo. Objetivos conjuntivos criam desafios interessantes de coordenação e ordenação.
Às vezes, qualquer uma de várias alternativas é aceitável. Para chegar ao trabalho, posso ir de carro, ônibus, bicicleta ou caminhando - qualquer uma atinge o objetivo. Objetivos disjuntivos oferecem flexibilidade, permitindo que o planejador escolha a opção mais conveniente ou eficiente dado o contexto.
Muitos objetivos têm componentes temporais. Entregar antes do prazo, manter temperatura estável por uma hora, garantir backup diário. Objetivos temporais podem especificar quando algo deve acontecer, por quanto tempo deve durar, ou sequências temporais complexas. Eles adicionam uma dimensão rica mas desafiadora ao planejamento.
Nem todos os objetivos têm igual importância. Queremos chegar no horário E confortavelmente E economicamente, mas se necessário, sacrificamos conforto por pontualidade. Modelar preferências permite planejadores fazerem trade-offs inteligentes, produzindo planos que melhor equilibram múltiplos critérios.
Além de satisfazer condições, frequentemente queremos otimizar métricas. Minimizar custo, tempo ou risco. Maximizar lucro, satisfação ou cobertura. Objetivos de otimização transformam planejamento de problema de satisfação em problema de otimização, onde buscamos não apenas uma solução, mas a melhor solução.
Em ambientes dinâmicos, objetivos podem mudar durante a execução. Um robô de resgate pode receber novas informações sobre vítimas. Um sistema de navegação adapta a rota com mudanças no trânsito. Objetivos evolutivos requerem replanejamento dinâmico e flexibilidade para adaptar-se a novas prioridades.
A fronteira entre objetivos e restrições pode ser sutil. "Não colidir" é uma restrição de segurança ou objetivo de prevenção? Na prática, restrições são condições que devem sempre valer, enquanto objetivos são estados a alcançar. Restrições podam o espaço de planos válidos; objetivos direcionam a busca dentro desse espaço.
Objetivos complexos frequentemente decompõem-se em sub-objetivos mais simples. "Construir casa" divide-se em "preparar terreno", "fazer fundação", "erguer estrutura", etc. Esta decomposição hierárquica facilita o planejamento, permitindo focar em partes gerenciáveis e combinar sub-planos.
Como sabemos quando um objetivo foi alcançado? Para objetivos simples, verificação é direta - checar se condições são satisfeitas no estado atual. Para objetivos complexos envolvendo tempo, probabilidade ou otimização, verificação pode requerer análise sofisticada de trajetórias, cálculo de métricas agregadas, ou avaliação estatística.
Objetivos são a bússola do planejamento automático, apontando a direção e definindo o sucesso. Sem objetivos claros, até o melhor planejador vaga sem rumo. Com objetivos bem definidos, transformamos computadores em solucionadores de problemas focados e eficazes. Aprendemos que objetivos podem ser simples ou complexos, rígidos ou flexíveis, estáticos ou dinâmicos. Esta riqueza permite modelar a diversidade de problemas do mundo real. Agora, com estados, ações e objetivos em mãos, estamos prontos para explorar os algoritmos que encontram caminhos do presente ao futuro desejado!
Imagine-se em um labirinto gigantesco, onde cada corredor leva a dezenas de outros corredores, e apenas um caminho leva à saída. Como você encontraria o caminho? Exploraria sistematicamente? Seguiria sua intuição? Marcaria caminhos já visitados? Os algoritmos de busca são estratégias matemáticas para navegar por espaços de possibilidades, encontrando caminhos do estado inicial ao objetivo. São o motor que transforma problemas de planejamento em soluções concretas. Neste capítulo, exploraremos desde buscas cegas até estratégias sofisticadas que parecem ter intuição quase humana.
Todo problema de planejamento define implicitamente um grafo gigantesco: nós são estados, arestas são ações. O desafio é encontrar um caminho do nó inicial ao nó objetivo sem construir o grafo inteiro - que pode ter bilhões ou infinitos nós. Algoritmos de busca exploram este espaço estrategicamente, expandindo apenas nós promissores.
A busca em largura explora o espaço como ondas em um lago - uniformemente em todas as direções. Examina todos os estados a distância 1, depois distância 2, e assim por diante. Garante encontrar o caminho mais curto (em número de ações), mas consome muita memória, armazenando todos os estados visitados. É como procurar as chaves perdidas verificando sistematicamente cada centímetro da casa.
A busca em profundidade mergulha fundo em uma direção antes de retroceder e tentar outra. Como explorar uma caverna seguindo sempre o caminho mais à esquerda até encontrar um beco sem saída. Usa pouca memória mas pode perder-se em ramos infinitos ou encontrar soluções muito longas. É eficiente quando soluções estão profundas e uniformemente distribuídas.
Quando ações têm custos diferentes, queremos o caminho mais barato, não necessariamente o mais curto. A busca de custo uniforme expande nós em ordem de custo acumulado, como água fluindo sempre pelo caminho de menor resistência. Garante solução ótima em termos de custo, essencial para problemas onde recursos são críticos.
A* é a estrela dos algoritmos de busca, combinando o melhor de dois mundos: considera tanto o custo já gasto (g) quanto uma estimativa do custo restante (h). É como navegar com GPS que considera não apenas a distância percorrida, mas também a distância em linha reta até o destino. Com uma boa heurística, A* é otimamente eficiente - nenhum algoritmo que garante solução ótima expande menos nós.
A busca gulosa ignora o passado e foca apenas no futuro estimado, sempre escolhendo o que parece mais próximo do objetivo. É como escalar uma montanha sempre subindo a inclinação mais íngreme. Rápida mas pode ficar presa em máximos locais. Útil quando velocidade importa mais que otimalidade.
Por que buscar apenas do início? A busca bidirecional explora simultaneamente do início para o fim e do fim para o início, encontrando-se no meio. Como dois times de resgate cavando um túnel de ambos os lados da montanha. Pode reduzir drasticamente o espaço explorado - duas buscas de profundidade d/2 em vez de uma de profundidade d.
Este algoritmo engenhoso combina benefícios de DFS (pouca memória) com BFS (solução ótima). Executa DFS com limite de profundidade crescente: primeiro profundidade 1, depois 2, depois 3... Parece ineficiente repetir trabalho, mas o custo é dominado pela última iteração. É como procurar algo começando pela gaveta mais próxima e expandindo o raio gradualmente.
Nem sempre precisamos do caminho, apenas do destino. Busca local mantém apenas o estado atual e move para vizinhos melhores, como escalar no nevoeiro sempre subindo. Hill climbing, simulated annealing, busca tabu - variantes que tentam escapar de ótimos locais. Úteis para otimização e problemas onde o caminho não importa.
Alguns problemas têm estrutura AND-OR: para resolver A, preciso resolver B E C, ou resolver D OU E. Grafos AND-OR capturam esta estrutura, permitindo decomposição de problemas. A busca deve encontrar não um caminho, mas uma árvore de solução cobrindo todas as contingências. Fundamental para planejamento com incerteza.
Algoritmos de busca são a ponte entre problemas e soluções, transformando espaços abstratos de possibilidades em caminhos concretos de ação. Cada algoritmo tem suas forças e fraquezas, brilhando em diferentes contextos. A arte está em escolher o algoritmo certo para cada problema, equilibrando completude, otimalidade, eficiência temporal e espacial. Mas mesmo o melhor algoritmo de busca pode naufragar em espaços muito grandes. É aí que entram as heurísticas - intuições matemáticas que guiam a busca na direção certa!
Se algoritmos de busca são exploradores navegando territórios desconhecidos, heurísticas são suas bússolas - não garantem o caminho perfeito, mas apontam a direção promissora. Uma boa heurística transforma uma busca cega em exploração guiada, reduzindo o tempo de horas para segundos. Como desenvolvemos estas intuições matemáticas? Como garantimos que ajudam mais do que atrapalham? Neste capítulo, mergulharemos na arte e ciência de criar heurísticas eficazes, o segredo por trás da eficiência dos planejadores modernos.
Uma heurística é uma função que estima o custo ou distância do estado atual até o objetivo. Como estimar o tempo de viagem olhando a distância em linha reta no mapa - não é exato, mas fornece orientação útil. A magia está em criar estimativas computacionalmente baratas que correlacionem bem com o custo real, acelerando dramaticamente a busca sem sacrificar qualidade.
Uma heurística admissível nunca superestima o custo real - é otimista por natureza. Esta propriedade é crucial: garante que A* encontre solução ótima. É como estimar o tempo de viagem ignorando semáforos - sempre subestima, mas mantém a busca honesta. Criar heurísticas admissíveis informativas é uma arte que equilibra otimismo com realismo.
Uma técnica poderosa para criar heurísticas é relaxar o problema original - remover restrições tornando-o mais fácil de resolver. O custo ótimo do problema relaxado é uma heurística admissível para o problema original. Como estimar o tempo de viagem assumindo que podemos voar em linha reta - claramente otimista, mas útil.
Pattern databases armazenam soluções ótimas para subproblemas, usando-as como heurísticas. Como memorizar finais de jogos de xadrez - quando reconhecemos um padrão, sabemos exatamente quantos movimentos faltam. Requer pré-computação e memória, mas fornece estimativas muito precisas. Técnica poderosa para domínios com estrutura decomponível.
Máquinas podem aprender suas próprias heurísticas! Treinando em milhares de problemas resolvidos, redes neurais aprendem a estimar custos. Reinforcement learning descobre features importantes. É como desenvolver intuição através da experiência - depois de resolver muitos problemas similares, desenvolvemos "feeling" para soluções.
Às vezes, sacrificamos garantia de otimalidade por velocidade. Heurísticas não-admissíveis podem superestimar, guiando agressivamente ao objetivo. Como usar atalhos arriscados - geralmente funcionam, ocasionalmente levam a caminhos piores. Úteis quando precisamos de soluções rápidas e "bom o suficiente" é aceitável.
Por que escolher uma quando podemos usar várias? Podemos tomar o máximo de várias heurísticas admissíveis (mantém admissibilidade), fazer média ponderada (pode perder admissibilidade mas suaviza erros), ou selecionar dinamicamente baseado no contexto. Como consultar múltiplos especialistas e sintetizar suas opiniões.
Conhecimento do domínio permite heurísticas poderosas. Em roteamento, considerar tráfego típico por horário. Em jogos, avaliar posições por padrões conhecidos. Em robótica, considerar consumo energético por terreno. Heurísticas específicas superam genéricas, mas requerem expertise e não generalizam.
Como sabemos se uma heurística é boa? Medimos fator de ramificação efetivo - quantos nós expandimos comparado com busca cega. Analisamos erro médio e máximo comparado com custo real. Testamos em benchmark de problemas. Uma boa heurística reduz exponencialmente o espaço explorado mantendo qualidade da solução.
O campo evolui rapidamente. Deep learning cria heurísticas que superam humanos. Quantum computing promete explorar espaços exponenciais. Meta-raciocínio escolhe heurísticas automaticamente. O futuro combina intuição humana, aprendizado de máquina e poder computacional para criar heurísticas cada vez mais poderosas.
Heurísticas são a ponte entre força bruta e inteligência, transformando buscas intratáveis em explorações eficientes. São a intuição matemática que guia através de espaços impossíveis de explorar completamente. Dominar heurísticas é dominar a arte de aproximar o perfeito com o possível, de trocar garantias teóricas por desempenho prático. Com este conhecimento, estamos prontos para aplicar tudo que aprendemos no reino do planejamento clássico - onde teoria encontra prática!
O planejamento clássico é o coração da disciplina - um mundo idealizado onde temos informação completa, ações determinísticas e objetivos claros. Como jogar xadrez com todas as peças visíveis e regras imutáveis. Embora simplificado comparado ao mundo real, o planejamento clássico fornece fundamentos teóricos profundos e algoritmos práticos que resolvem problemas importantes. É o laboratório onde testamos ideias antes de enfrentar a complexidade total da realidade. Neste capítulo, exploraremos os pilares do planejamento clássico e suas técnicas revolucionárias.
O planejamento clássico faz assumções simplificadoras que tornam o problema tratável. Ambiente totalmente observável - conhecemos o estado completo. Ações determinísticas - sabemos exatamente seus efeitos. Ambiente estático - muda apenas por nossas ações. Objetivos de alcance - queremos atingir certos estados. Estas assumções permitem garantias teóricas fortes e algoritmos eficientes.
STRIPS estabeleceu a linguagem padrão para planejamento clássico. Ações têm pré-condições e efeitos. Estados são conjuntos de proposições. Planos são sequências de ações. Simples mas expressivo, STRIPS captura a essência de muitos problemas práticos. Sua influência persiste em planejadores modernos, que estendem mas preservam suas ideias centrais.
A abordagem mais direta: buscar no grafo de estados. Cada nó é um estado completo, cada aresta uma ação aplicável. Algoritmos de busca exploram este espaço procurando caminho ao objetivo. Forward search parte do inicial aplicando ações. Backward search parte do objetivo regredindo pré-condições. Ambas têm méritos dependendo da estrutura do problema.
Graphplan mudou o jogo nos anos 90. Em vez de buscar estado por estado, constrói um grafo em camadas alternando proposições e ações. Detecta mutex (exclusões mútuas) - proposições/ações incompatíveis. Expande até objetivo aparecer sem mutex, então extrai plano. Extremamente eficiente para muitos domínios, inspirou gerações de planejadores.
Insight brilhante: planejamento pode ser codificado como problema de satisfatibilidade booleana (SAT). Variáveis representam proposições em cada tempo e ações executadas. Cláusulas codificam pré-condições, efeitos, mutex. SAT solver encontra atribuição satisfazível = plano válido. Permite usar décadas de pesquisa em SAT solvers ultra-otimizados.
Grafos de planejamento relaxados fornecem excelentes heurísticas. Ignorando mutex, calculamos rapidamente quantas camadas até objetivo. Ou extraímos plano relaxado e usamos seu comprimento/custo. Estas heurísticas são informativas e rápidas de computar, acelerando dramaticamente busca heurística. Base de muitos planejadores estado-da-arte.
Nem sempre precisamos do plano perfeito. Planejamento ótimo garante menor custo mas pode ser muito lento. Planejamento satisficing busca qualquer plano válido rapidamente. Como escolher entre o restaurante perfeito (ótimo) ou qualquer restaurante decente (satisficing). A escolha depende do domínio e restrições de tempo.
Problemas grandes demandam divide-and-conquer. Decompomos em subproblemas independentes ou fracamente acoplados. Resolvemos abstração de alto nível, depois refinamos. Como planejar viagem decidindo primeiro países, depois cidades, depois atividades. Hierarquia e modularidade tornam problemas grandes tratáveis.
Planejamento clássico é PSPACE-completo em geral - muito difícil! Mas restrições tornam tratável. Proposições sem delete: polinomial. Ações unitárias: NP-completo. Comprimento limitado: NP. Entender complexidade ajuda escolher representações e algoritmos apropriados. Teoria guia prática.
International Planning Competition (IPC) impulsiona o campo. Domínios benchmark testam diferentes aspectos - logística, puzzles, controle. Planejadores competem em tracks (ótimo, satisficing, temporal). Competição incentiva inovação e fornece comparação objetiva. Muitas técnicas revolucionárias surgiram para vencer IPC.
Planejamento clássico é onde elegância matemática encontra utilidade prática. Suas assumções simplificadoras permitem teoria profunda e algoritmos poderosos que resolvem problemas reais importantes. É o campo de provas onde testamos ideias antes de enfrentar a complexidade total do mundo. Dominar planejamento clássico fornece intuições e ferramentas essenciais para todos os tipos de planejamento. Com esta base sólida, estamos prontos para adicionar a dimensão do tempo - onde ações têm duração e o relógio não para!
O mundo real não espera. Enquanto o robô carrega sua bateria, o tempo passa, prazos se aproximam, oportunidades surgem e desaparecem. O planejamento temporal abraça esta realidade, modelando explicitamente duração de ações, restrições temporais e execução concorrente. É como reger uma orquestra onde cada músico tem seu tempo, mas todos devem harmonizar-se. Neste capítulo, exploraremos como o tempo transforma o planejamento, adicionando riqueza e complexidade que espelham melhor nosso mundo dinâmico.
Adicionar tempo muda tudo. Ações não são mais instantâneas - cozinhar leva 30 minutos, voar leva horas. Recursos têm disponibilidade temporal - a sala está livre das 14h às 16h. Objetivos têm prazos - entregar antes do meio-dia. O tempo transforma planejamento de sequenciamento puro em problema de agendamento rico, onde quando importa tanto quanto o quê.
Ações durativas têm estrutura temporal rica. Condições no início devem valer para iniciar. Condições invariantes devem manter-se durante execução. Efeitos podem ocorrer no início, durante ou no fim. Como assar um bolo: pré-aquecer forno (início), manter temperatura (durante), bolo pronto (fim). Esta granularidade permite modelagem precisa de processos complexos.
O poder real do planejamento temporal é permitir ações simultâneas. Enquanto o robô A carrega caixas, o robô B pode preparar o caminhão. Mas concorrência traz desafios: conflitos de recursos, sincronização, coordenação. É como cozinhar uma refeição completa - múltiplos pratos preparados em paralelo, mas servidos juntos.
Allen's interval algebra fornece linguagem rica para relações temporais. A antes de B, A durante B, A sobrepõe B - treze relações básicas capturam todas as possibilidades entre intervalos. Podemos expressar restrições sofisticadas: "manutenção deve começar 2 horas após produção terminar mas antes da meia-noite".
Abordagem alternativa: modelar evolução de variáveis sobre o tempo. Cada variável tem timeline - sequência de valores com durações. Planejar é encontrar timelines consistentes que satisfazem objetivos. Natural para domínios contínuos como controle de satélites, onde variáveis (orientação, energia) evoluem continuamente.
Tempo real é contínuo, não discreto. Ações podem começar em qualquer instante, ter durações reais. Isto cria espaço de busca infinito! Técnicas especiais necessárias: discretização adaptativa, constraint programming, linear programming. Essencial para robótica e controle onde timing preciso importa.
Recursos variam no tempo. Energia solar disponível apenas durante o dia. Banda de rede congestionada em horários de pico. Trabalhadores com turnos específicos. Modelar perfis temporais de recursos permite planejamento mais realista, evitando violações e aproveitando oportunidades.
STNs representam restrições temporais como grafo. Nós são timepoints, arestas são constraints de distância. Podemos verificar consistência e calcular janelas temporais eficientemente. STPs (Simple Temporal Problems) estendem com disjunções. Ferramentas poderosas para raciocínio temporal eficiente.
Não basta encontrar plano válido temporalmente - queremos otimizar. Minimizar makespan (tempo total). Maximizar utilização de recursos. Minimizar atrasos. Balancear carga temporal. Problemas multi-objetivo onde tempo compete com outros critérios. Técnicas de otimização combinatória e metaheurísticas são essenciais.
Planos temporais devem ser executados em mundo real onde relógios divergem, ações atrasam, durações variam. Executivo temporal monitora progresso, detecta desvios, dispara ações no momento certo. Como um maestro adaptando-se quando músicos aceleram ou desaceleram, mantendo harmonia geral.
Planejamento temporal traz o realismo do tempo para o mundo do planejamento. Transforma problemas de sequências em sinfonias temporais onde timing, duração e sincronização criam harmonia ou caos. É desafiador - adiciona dimensões de complexidade - mas essencial para problemas reais onde o relógio não para. Dominar planejamento temporal é aprender a dançar com o tempo, criando planos que não apenas alcançam objetivos, mas o fazem no momento certo. Agora, preparemo-nos para o próximo nível de realismo: o mundo incerto onde nem tudo sai como planejado!
A vida raramente segue o roteiro. O trânsito pode estar pior que o esperado, a chuva pode cancelar o piquenique, o investimento pode não render como previsto. O planejamento sob incerteza abraça esta realidade imprevisível, criando planos robustos que funcionam apesar das surpresas. É como navegar em névoa - não vemos tudo claramente, mas ainda precisamos chegar ao destino. Neste capítulo, exploraremos como planejar quando o futuro é probabilístico, a informação é parcial e o sucesso não é garantido.
Incerteza permeia o mundo real de múltiplas formas. Ações podem ter efeitos não-determinísticos - o tratamento pode ou não curar. Observações são ruidosas - sensores têm erro. O ambiente evolui independentemente - outros agentes agem, eventos ocorrem. Objetivos podem mudar - novas prioridades surgem. Cada fonte requer técnicas específicas para gerenciar.
MDPs são o framework fundamental para decisões sequenciais sob incerteza. Estados, ações, probabilidades de transição e recompensas definem o modelo. O objetivo é encontrar política ótima - mapeamento de estados para ações que maximiza recompensa esperada. Como um GPS que recalcula a rota baseado no trânsito atual, sempre escolhendo a melhor ação dado o estado presente.
POMDPs estendem MDPs para mundos parcialmente observáveis. O agente mantém crença - distribuição de probabilidade sobre estados possíveis. Decisões baseiam-se em crenças, não estados. Como dirigir na neblina - não vemos tudo, mas atualizamos constantemente nossa estimativa de onde estamos e o que está à frente.
Em vez de sequência linear, planos contingentes são árvores com ramificações condicionais. "Se o teste der positivo, fazer tratamento A, senão fazer B". Cada contingência preparada antecipadamente. Como um manual de troubleshooting - diferentes caminhos para diferentes situações. Robusto mas pode crescer exponencialmente.
Quando modelamos probabilidades explicitamente, podemos otimizar valor esperado, minimizar risco, ou balancear ambos. Técnicas incluem value iteration, policy iteration, e aproximações. Como investir - não sabemos retornos exatos, mas escolhemos portfolio que maximiza retorno esperado dado nosso apetite por risco.
MCTS simula múltiplos futuros possíveis, construindo árvore de busca incrementalmente. Balanceia exploração (tentar novas ações) com exploitation (focar em promissoras). Revolucionou jogos como Go. Como testar estratégias jogando milhares de partidas mentais rápidas, aprendendo quais funcionam melhor.
Quando a realidade diverge do esperado, replanejar pode ser necessário. Mas replanejar constantemente é caro. Estratégias incluem: replanejar só quando necessário, manter envelope de planos, ajustar localmente. Como recalcular rota GPS - só quando saímos muito do caminho ou condições mudam significativamente.
Às vezes preferimos planos robustos que funcionam em muitos cenários, mesmo se não ótimos em nenhum. Adicionar margens de segurança, evitar ações arriscadas, preferir reversibilidade. Como escolher rota com múltiplas alternativas em vez da mais rápida mas sem opções se algo der errado.
Incerteza diminui com experiência. Reinforcement learning permite aprender políticas ótimas através de tentativa e erro. Bayesian optimization balanceia exploração de novas ações com exploitation de conhecidas boas. Como criança aprendendo a andar - cada queda ensina, gradualmente dominando o equilíbrio.
Com múltiplos agentes, incerteza inclui intenções e ações dos outros. Comunicação pode reduzir incerteza mas tem custo. Protocolos de coordenação garantem comportamento coerente mesmo com informação limitada. Como time de futebol - cada jogador tem visão parcial mas coordena através de sinais e padrões treinados.
Planejamento sob incerteza é onde a elegância matemática encontra a confusão do mundo real. É desafiador - requer probabilidade, otimização, teoria da decisão - mas essencial para sistemas que operam fora de ambientes controlados. Dominar estas técnicas permite criar sistemas robustos que prosperam apesar da incerteza, adaptando-se graciosamente quando surpresas inevitavelmente surgem. Com todo este arsenal teórico e prático, estamos prontos para o grand finale: ver como planejamento automático está transformando o mundo real!
O planejamento automático saiu dos laboratórios e conquistou o mundo. Está no smartphone que otimiza suas rotas, no robô que monta seu carro, no satélite que fotografa a Terra, no assistente que agenda suas reuniões. Cada aplicação traz desafios únicos, exigindo adaptações criativas das técnicas que estudamos. Neste capítulo final, exploraremos como o planejamento automático está revolucionando indústrias, salvando vidas e expandindo as fronteiras do possível. Prepare-se para descobrir que o futuro já chegou!
O espaço é o playground supremo do planejamento automático. Comunicação com atraso de minutos ou horas torna controle remoto impraticável. Rovers em Marte devem planejar autonomamente como navegar terreno desconhecido, coletar amostras, gerenciar energia solar. Satélites agendam observações maximizando valor científico dentro de constraints orbitais. O planejamento automático literalmente expande nossos horizontes.
Carros autônomos são planejadores sobre rodas. Planejamento de rota de alto nível escolhe caminhos. Planejamento de movimento gera trajetórias suaves e seguras. Planejamento de comportamento decide quando ultrapassar, ceder passagem, estacionar. Tudo em tempo real, com incerteza sobre outros motoristas, pedestres, condições. Cada viagem é uma sinfonia de decisões coordenadas.
Amazon, FedEx, Walmart - gigantes da logística dependem de planejamento automático. Rotear milhões de pacotes, agendar milhares de caminhões, gerenciar centenas de armazéns. Cada decisão afeta outras em cascata. Planejadores otimizam custo, tempo, confiabilidade simultaneamente. Durante a pandemia, replanejamento ágil manteve suprimentos fluindo apesar de disrupções massivas.
Fábricas modernas são sinfonias de automação. Planejadores coordenam robôs, máquinas, humanos. Sequenciam operações minimizando tempo e desperdício. Adaptam-se a quebras, variações de demanda, personalização em massa. Indústria 4.0 usa planejamento para transformar produção rígida em manufatura ágil e responsiva.
Planejamento salva vidas. Radioterapia usa planejamento para maximizar dose em tumores minimizando dano a tecido saudável. Robôs cirúrgicos planejam incisões e movimentos precisos. Hospitais otimizam agendamento de salas, equipamentos, equipes. Durante COVID-19, planejadores alocaram recursos escassos - ventiladores, leitos, vacinas - onde mais necessários.
Games modernos usam planejamento para criar experiências dinâmicas. NPCs planejam estratégias, navegam mundos, coordenam ataques. Narrativas adaptam-se às escolhas do jogador. Dificuldade ajusta-se automaticamente. AlphaGo mostrou que planejamento pode superar humanos até em jogos considerados intuitivos. Planejamento transforma entretenimento passivo em experiências interativas personalizadas.
Cidades inteligentes são organismos complexos que requerem coordenação massiva. Semáforos adaptam-se ao tráfego em tempo real. Transporte público otimiza rotas baseado em demanda. Energia é distribuída eficientemente. Serviços de emergência são despachados otimamente. Planejamento automático é o cérebro que transforma infraestrutura em inteligência urbana.
Fazendas modernas usam planejamento para alimentar o mundo eficientemente. Drones planejam rotas para monitorar plantações. Tratores autônomos otimizam plantio e colheita. Irrigação é agendada baseada em previsões meteorológicas e umidade do solo. Planejamento maximiza produção minimizando água, pesticidas, combustível. Agricultura sustentável depende de decisões inteligentes.
Mercados financeiros são arenas de planejamento de alta velocidade. Algoritmos planejam portfolios balanceando risco e retorno. Trading de alta frequência executa milhares de transações por segundo. Robo-advisors criam planos de investimento personalizados. Blockchain smart contracts executam planos financeiros automaticamente. Cada decisão é um plano miniatura em ambiente altamente incerto.
Siri, Alexa, Google Assistant são planejadores pessoais. Interpretam comandos, decompõem em subtarefas, coordenam serviços. "Reserve um voo e hotel para Paris" dispara planejamento complexo considerando preferências, orçamento, disponibilidade. Assistentes evoluem de respondedores reativos para planejadores proativos que antecipam necessidades.
O planejamento automático está em toda parte, melhorando vidas, salvando recursos, expandindo possibilidades. Cada aplicação é uma validação das técnicas que estudamos, uma demonstração de que teoria matemática pode transformar o mundo real. Mas isto é apenas o começo. À medida que computadores ficam mais poderosos, dados mais abundantes, e algoritmos mais sofisticados, o planejamento automático continuará revolucionando como vivemos, trabalhamos e exploramos. O futuro será planejado automaticamente - e você agora entende como!
Este volume sobre Planejamento Automático foi construído sobre décadas de pesquisa em inteligência artificial, otimização e ciência da computação. As referências abrangem desde trabalhos pioneiros dos anos 1950 até desenvolvimentos contemporâneos em aprendizado por reforço e sistemas autônomos. Esta bibliografia oferece recursos para aprofundamento em cada aspecto do planejamento automático, desde fundamentos teóricos até aplicações práticas revolucionárias.
AERONAUTICS AND SPACE ENGINEERING BOARD. Autonomy Research for Civil Aviation: Toward a New Era of Flight. Washington: National Academies Press, 2014.
ALLEN, James F. Maintaining Knowledge about Temporal Intervals. Communications of the ACM, v. 26, n. 11, p. 832-843, 1983.
BELLMAN, Richard. Dynamic Programming. Princeton: Princeton University Press, 1957.
BERTSEKAS, Dimitri P. Dynamic Programming and Optimal Control. 4th ed. Belmont: Athena Scientific, 2017. 2 v.
BLUM, Avrim L.; FURST, Merrick L. Fast Planning Through Planning Graph Analysis. Artificial Intelligence, v. 90, n. 1-2, p. 281-300, 1997.
BONET, Blai; GEFFNER, Héctor. Planning as Heuristic Search. Artificial Intelligence, v. 129, n. 1-2, p. 5-33, 2001.
BOUTILIER, Craig; DEAN, Thomas; HANKS, Steve. Decision-Theoretic Planning: Structural Assumptions and Computational Leverage. Journal of AI Research, v. 11, p. 1-94, 1999.
BRASIL. Base Nacional Comum Curricular: Educação é a Base. Brasília: MEC/CONSED/UNDIME, 2018.
BRESINA, John; DEARDEN, Richard; MEULEAU, Nicolas et al. Planning Under Continuous Time and Resource Uncertainty. In: Uncertainty in AI, 2002.
BROWNE, Cameron et al. A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games, v. 4, n. 1, p. 1-43, 2012.
BYLANDER, Tom. The Computational Complexity of Propositional STRIPS Planning. Artificial Intelligence, v. 69, n. 1-2, p. 165-204, 1994.
CHAPMAN, David. Planning for Conjunctive Goals. Artificial Intelligence, v. 32, n. 3, p. 333-377, 1987.
CIMATTI, Alessandro et al. Strong Planning in Non-Deterministic Domains via Model Checking. In: AIPS-98, 1998.
DEAN, Thomas; KANAZAWA, Keiji. A Model for Reasoning about Persistence and Causation. Computational Intelligence, v. 5, n. 2, p. 142-150, 1989.
DO, Minh Binh; KAMBHAMPATI, Subbarao. Sapa: A Domain-Independent Heuristic Metric Temporal Planner. In: ECP-01, 2001.
EDELKAMP, Stefan; HOFFMANN, Jörg. PDDL2.2: The Language for the Classical Part of IPC-4. In: IPC-4, 2004.
FIKES, Richard E.; NILSSON, Nils J. STRIPS: A New Approach to the Application of Theorem Proving. Artificial Intelligence, v. 2, n. 3-4, p. 189-208, 1971.
FOX, Maria; LONG, Derek. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. JAIR, v. 20, p. 61-124, 2003.
GEFFNER, Héctor; BONET, Blai. A Concise Introduction to Models and Methods for Automated Planning. Morgan & Claypool, 2013.
GHALLAB, Malik; NAU, Dana; TRAVERSO, Paolo. Automated Planning: Theory and Practice. San Francisco: Morgan Kaufmann, 2004.
GHALLAB, Malik; HOWE, Adele; KNOBLOCK, Craig et al. PDDL - The Planning Domain Definition Language. Yale Center for Computational Vision and Control, 1998.
HART, Peter E.; NILSSON, Nils J.; RAPHAEL, Bertram. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Trans. SSC, v. 4, n. 2, p. 100-107, 1968.
HELMERT, Malte. The Fast Downward Planning System. Journal of AI Research, v. 26, p. 191-246, 2006.
HOFFMANN, Jörg. The Metric-FF Planning System: Translating "Ignoring Delete Lists" to Numeric State Variables. JAIR, v. 20, p. 291-341, 2003.
HOFFMANN, Jörg; NEBEL, Bernhard. The FF Planning System: Fast Plan Generation Through Heuristic Search. JAIR, v. 14, p. 253-302, 2001.
HOWARD, Ronald A. Dynamic Programming and Markov Processes. Cambridge: MIT Press, 1960.
KAELBLING, Leslie Pack; LITTMAN, Michael L.; CASSANDRA, Anthony R. Planning and Acting in Partially Observable Stochastic Domains. AI, v. 101, p. 99-134, 1998.
KAUTZ, Henry; SELMAN, Bart. Planning as Satisfiability. In: ECAI-92, p. 359-363, 1992.
KNOBLOCK, Craig A. Automatically Generating Abstractions for Planning. Artificial Intelligence, v. 68, n. 2, p. 243-302, 1994.
KOCSIS, Levente; SZEPESVÁRI, Csaba. Bandit Based Monte-Carlo Planning. In: ECML-06, p. 282-293, 2006.
KORF, Richard E. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. AI, v. 27, n. 1, p. 97-109, 1985.
LAVALLE, Steven M. Planning Algorithms. Cambridge: Cambridge University Press, 2006.
MCALLESTER, David; ROSENBLITT, David. Systematic Nonlinear Planning. In: AAAI-91, p. 634-639, 1991.
MCDERMOTT, Drew et al. PDDL - The Planning Domain Definition Language. Technical Report CVC TR-98-003, Yale, 1998.
MUSCETTOLA, Nicola et al. Remote Agent: To Boldly Go Where No AI System Has Gone Before. AI, v. 103, n. 1-2, p. 5-47, 1998.
NAU, Dana et al. SHOP2: An HTN Planning System. Journal of AI Research, v. 20, p. 379-404, 2003.
NEWELL, Allen; SIMON, Herbert A. GPS, A Program that Simulates Human Thought. In: Computers and Thought, p. 279-293, 1963.
NILSSON, Nils J. Principles of Artificial Intelligence. Palo Alto: Tioga Publishing, 1980.
PEDNAULT, Edwin P. D. ADL: Exploring the Middle Ground Between STRIPS and the Situation Calculus. In: KR-89, p. 324-332, 1989.
PENBERTHY, J. Scott; WELD, Daniel S. UCPOP: A Sound, Complete, Partial Order Planner for ADL. In: KR-92, p. 103-114, 1992.
PEARL, Judea. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Reading: Addison-Wesley, 1984.
PUTERMAN, Martin L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. New York: Wiley, 1994.
RINTANEN, Jussi. Planning as Satisfiability: Heuristics. Artificial Intelligence, v. 193, p. 45-86, 2012.
RUSSELL, Stuart; NORVIG, Peter. Artificial Intelligence: A Modern Approach. 4th ed. Upper Saddle River: Pearson, 2020.
SACERDOTI, Earl D. Planning in a Hierarchy of Abstraction Spaces. Artificial Intelligence, v. 5, n. 2, p. 115-135, 1974.
SILVER, David et al. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, v. 529, p. 484-489, 2016.
SMITH, David E.; WELD, Daniel S. Temporal Planning with Mutual Exclusion Reasoning. In: IJCAI-99, p. 326-337, 1999.
SUTTON, Richard S.; BARTO, Andrew G. Reinforcement Learning: An Introduction. 2nd ed. Cambridge: MIT Press, 2018.
TATE, Austin. Generating Project Networks. In: IJCAI-77, p. 888-893, 1977.
THRUN, Sebastian; BURGARD, Wolfram; FOX, Dieter. Probabilistic Robotics. Cambridge: MIT Press, 2005.
VERE, Steven. Planning in Time: Windows and Durations for Activities and Goals. IEEE PAMI, v. 5, n. 3, p. 246-267, 1983.
WELD, Daniel S. An Introduction to Least Commitment Planning. AI Magazine, v. 15, n. 4, p. 27-61, 1994.
WILKINS, David E. Practical Planning: Extending the Classical AI Planning Paradigm. San Francisco: Morgan Kaufmann, 1988.
YOUNES, Håkan L. S.; LITTMAN, Michael L. PPDDL1.0: An Extension to PDDL for Expressing Planning Domains with Probabilistic Effects. Technical Report CMU-CS-04-162, 2004.