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

1. CM <- valor inicial para o nível de criticalidade mínima.

2. Gerar um um plano que satisfaça todas as condições com nível de criticalidade >= CM.

3. CM <- CM-1

4. Usando o plano anterior como guia, gerar um plano que satisfaça todas as condições com criticalidade >= CM.

5. Se todas as condições estão satisfeitas, retornar a solução.

6. 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