Grafos de Planejamento e Heurísticas

Grafos de planejamento e heurísticas independentes de domínio são as técnicas que tornaram o planejamento clássico rápido, analisando de forma compacta a alcançabilidade e estimando automaticamente a distância de um estado ao objetivo.

Definition

Um grafo de planejamento é uma estrutura em camadas que intercala níveis de proposições e ações com restrições mutex para aproximar a alcançabilidade; heurísticas de planejamento são funções, frequentemente calculadas a partir de tais estruturas ou de problemas com exclusão relaxada, que estimam o custo de alcançar o objetivo a partir de um estado.

Scope

Este tópico abrange a estrutura de dados do grafo de planejamento introduzida pelo Graphplan, incluindo níveis de proposições e ações e as relações de exclusão mútua (mutex) que capturam quais fatos e ações não podem ocorrer simultaneamente, e a família de heurísticas independentes de domínio derivadas de problemas relaxados (notavelmente ignorando efeitos de exclusão) que impulsionam os planejadores de busca heurística modernos. Ele aborda como as informações de alcançabilidade são calculadas e usadas para guiar a busca. O modelo de planejamento clássico subjacente é abordado no tópico relacionado.

Core questions

• Como um grafo de planejamento representa proposições e ações alcançáveis nível por nível?
• O que são relações mutex e como elas capturam a incompatibilidade entre fatos e ações?
• Como a relaxamento de exclusão é usada para derivar heurísticas de planejamento admissíveis ou informativas?
• Como essas heurísticas transformam o planejamento em uma busca heurística eficiente?

Key concepts

• grafo de planejamento
• níveis de proposição e ação
• exclusão mútua (mutex)
• Graphplan
• relaxamento de exclusão
• heurísticas h-max e h-add
• heurística FF e planos relaxados
• busca heurística para frente

Key theories

Grafo de planejamento e Graphplan

O Graphplan constrói um grafo de planejamento que codifica compactamente quais proposições e ações são alcançáveis em cada nível e quais pares são mutuamente exclusivos, então extrai um plano buscando para trás através desta estrutura, acelerando dramaticamente o planejamento.

Heurísticas de relaxamento de exclusão

Ignorar os efeitos de exclusão das ações produz um problema de planejamento relaxado que é muito mais fácil de resolver; o custo de resolver essa relaxamento fornece heurísticas informativas, frequentemente admissíveis (como h-max e h-add e a heurística FF) que guiam a busca para frente.

Planejamento por busca heurística

Os planejadores clássicos de última geração combinam heurísticas derivadas automaticamente com busca gulosa ou de melhor primeiro e aprimoramentos como operadores preferenciais, alcançando um forte desempenho de propósito geral em diversos domínios.

Clinical relevance

Grafos de planejamento e heurísticas de relaxamento de exclusão são a tecnologia central de planejadores vencedores de competições usados em robótica, logística e controle autônomo, onde permitem que planejadores independentes de domínio resolvam grandes problemas rapidamente sem orientação de busca artesanal.

History

O Graphplan de Blum e Furst (1995, versão de revista 1997) introduziu o grafo de planejamento e revolucionou a velocidade do planejamento. O final dos anos 1990 e os anos 2000 viram o surgimento das heurísticas de relaxamento de exclusão, com o planejador FF (Hoffmann e Nebel, 2001) e, posteriormente, o Fast Downward (Helmert, 2006) estabelecendo a busca heurística para frente como a abordagem dominante.

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

O que é um mutex em um grafo de planejamento?

Uma relação mutex (exclusão mútua) marca duas proposições ou duas ações que não podem ambas ser válidas ou aplicadas no mesmo nível, por exemplo, porque uma ação exclui uma pré-condição da outra. Mutexes tornam o grafo de planejamento uma aproximação mais precisa da verdadeira alcançabilidade.

Por que ignorar os efeitos de exclusão fornece uma heurística útil?

Sem os efeitos de exclusão, alcançar um objetivo nunca desfaz outro, então o problema relaxado é muito mais fácil de resolver e nunca mais difícil que o original. O custo do plano relaxado é, portanto, um limite inferior ou uma estimativa informada do custo real, tornando-o uma heurística eficaz para guiar a busca.