Inteligência Artificial

dividir para planejar melhor

Planejamento hierárquico decompõe problemas complexos em níveis de abstração progressivamente mais detalhados. Em vez de planejar diretamente com ações primitivas, ele usa ações de alto nível. Por exemplo, uma ação “viajar para Paris” se decompõe em “comprar passagem”, “ir ao aeroporto”, “embarcar”. Essa decomposição continua até atingir ações executáveis diretamente pelo agente. A abordagem reduz drasticamente o espaço de busca comparada ao planejamento clássico. Além disso, permite reutilização de conhecimento: uma vez definida, uma ação pode ser usada em múltiplos contextos. O planejamento hierárquico imita como humanos organizam tarefas complexas.

métodos de decomposição de tarefas

HTN (Hierarchical Task Network) é o formalismo mais conhecido para planejamento hierárquico. Ele utiliza métodos que especificam como decompor tarefas compostas em subtarefas. Cada método tem um nome de tarefa, pré-condições e uma rede de subtarefas ordenadas. Por exemplo, método “viajar-de-carro” pode decompor “ir a cidade” em “pegar chaves”, “entrar carro”, “dirigir”. As pré-condições do método determinam quando essa decomposição é aplicável. Diferente do planejamento clássico, HTN não busca sequência de ações primitivas. Ele busca uma decomposição que respeite as ordenações e restrições entre subtarefas.

exemplo prático: preparar refeição

Considere uma tarefa “preparar jantar” em um sistema de planejamento hierárquico. O método para “preparar jantar” decompõe em “preparar entrada”, “preparar prato principal”, “servir”. Cada uma dessas subtarefas se decompõe ainda mais em ações mais específicas. “Preparar entrada” pode ser “fazer salada”, que se decompõe em “lavar alface”, “cortar tomate”, “misturar”. As pré-condições verificam disponibilidade de ingredientes e utensílios antes de cada decomposição. O planejador resolve conflitos como usar o mesmo forno para dois pratos diferentes. O plano final é uma sequência de ações primitivas executáveis.

vantagens e desafios

O planejamento hierárquico oferece vantagens significativas em termos de eficiência e modularidade. A decomposição em níveis reduz exponencialmente o espaço de busca necessário. Conhecimento especializado pode ser encapsulado em métodos reutilizáveis para diferentes problemas. Além disso, planos hierárquicos são mais compreensíveis para humanos que os planos tradicionais. Contudo, a construção da base de métodos exige engenharia de conhecimento substancial. A interação entre diferentes métodos pode gerar conflitos complexos de resolver. Para iniciantes, o planejamento hierárquico mostra como abstração pode domar a complexidade. Ele revela uma abordagem que combina eficiência computacional com organização intuitiva do conhecimento.

aplicações e legado

Planejamento hierárquico é amplamente utilizado em sistemas reais que exigem coordenação complexa. Assistentes pessoais como Siri e Alexa utilizam planejamento hierárquico para entender comandos compostos. Sistemas de automação industrial planejam tarefas de manufatura com múltiplas etapas. Jogos eletrônicos empregam planejamento hierárquico para controlar personagens não-jogadores. O formalismo SHOP (Simple Hierarchical Ordered Planner) é um implementação eficiente e amplamente utilizada. Para iniciantes, estudar planejamento hierárquico é entender como sistemas lidam com tarefas complexas. Ele demonstra que organização hierárquica do conhecimento é fundamental para planejamento escalável.

planejamento com estruturas de grafos

Graphplan é um algoritmo de planejamento que utiliza estruturas de grafos para encontrar soluções. Desenvolvido por Avrim Blum e Merrick Furst nos anos 1990, ele revolucionou a área. Diferente de abordagens anteriores, Graphplan constrói um grafo de planejamento que expande camadas alternadas. O grafo alterna entre camadas de proposições (estados) e camadas de ações. A construção prossegue até que o objetivo apareça na camada de proposições. Em seguida, o algoritmo extrai um plano válido a partir do grafo construído. Essa abordagem provou ser mais eficiente que planejadores baseados em busca tradicional.

construção do grafo de planejamento

O grafo de planejamento começa com a camada de proposições representando o estado inicial. A cada camada de ações, adicionamos todas as ações cujas pré-condições estão na camada anterior. Também incluímos ações “no-op” que mantêm proposições inalteradas. A camada seguinte de proposições contém todos os efeitos das ações da camada anterior. Por exemplo, se na camada 0 temos “mão_vazia” e “bloco_livre”, adicionamos ação “pegar”. Essa ação adiciona “segurando(bloco)” na próxima camada de proposições. O processo repete até que o objetivo apareça em alguma camada.

detecção de mutex e poda

Graphplan utiliza relações de exclusão mútua (mutex) para podar combinações inviáveis. Duas proposições são mutex se não podem ser verdadeiras simultaneamente em um plano. Duas ações são mutex se interferem entre si ou têm pré-condições mutex. Por exemplo, “segurando(A)” e “segurando(B)” são mutex porque a mão só segura um bloco. Ações “pegar(A)” e “pegar(B)” são mutex porque competem pelo recurso “mão_vazia”. Essas relações se propagam entre camadas, reduzindo drasticamente o espaço de busca. A detecção de mutex permite podar combinações impossíveis precocemente.

extração de planos

Após construir o grafo até o objetivo, Graphplan extrai um plano de forma regressiva. O algoritmo começa na camada onde o objetivo aparece e busca um conjunto de ações que o suportam. Para cada ação selecionada, suas pré-condições se tornam subobjetivos na camada anterior. O processo recursivo continua até alcançar a camada inicial do grafo. Se em algum ponto não encontrar suporte válido, o algoritmo retrocede e tenta alternativas. Esse processo de extração garante que o plano encontrado é consistente e executável. O algoritmo retorna o plano de comprimento mínimo correspondente ao grafo construído.

vantagens e impacto do graphplan

Graphplan trouxe avanços significativos em eficiência para planejamento clássico. Sua estrutura de grafo permite detectar inconsistências e podar combinações inviáveis precocemente. A abordagem provou ser mais rápida que planejadores baseados em busca tradicional. Graphplan inspirou o desenvolvimento de planejadores modernos como IPP e STAN. Suas ideias influenciaram também a área de verificação de modelos e sistemas de transição. Para iniciantes, Graphplan oferece uma visão alternativa ao planejamento baseado em busca. Ele demonstra como estruturas de dados podem transformar a complexidade de problemas. O algoritmo permanece um marco na história do planejamento automatizado.