Planeamento
STRIPS
Exemplo
A Anomalia de Sussman
Dependendo da ordem pela qual o STRIPS trata os objectivos, os seguintes planos poderão ser gerados:
[ desempilhar(c,a), poisar(c), levantar(a), empilhar(a,b), desempilhar(a,b), poisar(a), levantar(b), empilhar(b,c), levantar(a), empilhar(a,b) ]
[ levantar(b), empilhar(b,c), desempilhar(b,c), poisar(b), desempilhar(c,a), poisar(c), levantar(a), empilhar(a,b), desempilhar(a,b), poisar(a), levantar(b), empilhar(b,c), levantar(a), empilhar(a,b) ]
Nenhum deles é óptimo
Na verdade, o algoritmo STRIPS não consegue gerar um plano óptimo para este problema.
Planeamento no espaço de soluções
Em todas as aproximações ao planeamento anteriormente apresentadas, cada nó da pesquisa corresponde a um estado do mundo -> planeamento no espaço de estados.
Uma técnica alternativa consiste em partir de um plano vazio e adicionar sucessivamente operações e restrições de sequenciamento -> planeamento no espaço de soluções.
Neste caso, cada nó da pesquisa corresponde a uma solução parcial para o problema.
Operações de transformação da solução:
Adicionar um operador.
Re-ordenar operadores.
Instanciar um operador.
Planeamento Hierárquico
ABSTRIPS
O planeamento é realizado numa hierarquia de níveis de abstração.
Um valor de “criticalidade” é atribuido a cada uma das condições que podem aparecer na descrição do estado do mundo.
Algoritmo
CM <- valor inicial para o nível de criticalidade mínima.
Gerar um um plano que satisfaça todas as condições com nível de criticalidade >= CM.
CM <- CM-1
Usando o plano anterior como guia, gerar um plano que satisfaça todas as condições com criticalidade >= CM.
Se todas as condições estão satisfeitas, retornar a solução.
Voltar ao passo 3.
Exemplo
Planeamento Inicial para CM=2
Planeamento para CM=1
As precondições de criticalidade 1 da primeira acção, lev(a), não estão reunidas, pelo que é preciso determinar um plano para as atingir.
Operadores com fórmulas não atómicas e condicionais
Literal – uma formula atómica (literal positivo) ou negação de uma fórmula atómica (literal negativo).
Fórmula de aplicabilidade do operador pode ser:
Fórmula atómica.
Negação de uma fórmula.
Conjunção de fórmulas.
Disjunção de fórmulas.
Fórmula quantificada existencialmente.
Fórmula quantificada universalmente.
Fórmula de efeitos do operador pode ser:
Literal Conjunção de literais
Efeitos condicionais: when <fórmula de aplicabilidade> <fórmula de efeitos>.
Fórmula de efeitos quantificada universalmente.
Conjunção de fórmulas de efeitos.
Ver “PDDL - Planning Domain Definition Language”.
PDDL - Exemplo
Last updated