Construir um sistema de planejamento clássico que receba como entrada um conjunto de ações (STRIPS) proposicionais, uma descrição do estado inicial e um conjunto de proposições que devem ser satisfeitas pelo estado meta. Seu planejador deverá devolver um plano de ações que, quando executadas, transformam o estado inicial num estado meta.

Nessa primeira fase você deverá implementar duas estratégias de busca diferentes:

• planejamento progressivo usando um algoritmo de busca do tipo IDS (Iterative Deepening Search);
• planejamento progressivo usando um algoritmo de busca do tipo A*. Usar a heurística simples que calcula o número de proposições que devem ser satisfeitas no estado meta e que não são satisfeitas no estado atual.

Características desejadas do seu sistema:

Domínios de Teste:

Vocês deverão testar os planejadores em dois domínios de teste: Mundo dos Blocos e Domínio dos Satélites. Esses domínios foram originalmente descritos, juntamente com um conjunto de problemas, na linguagem PDDL para a Competição Internacional de Planejamento e são do tipo STRIPS com variáveis (schemas).

Em geral, sistemas de planejamento que fazem busca no espaço de estados, como os que vocês irão implementar, raciocinam diretamente sobre uma descrição de ações proposicionais, ou seja, sem variáveis. Por exemplo, considere o domínio do mundo dos blocos com braço de robô descrito abaixo. Nesta versão do Mundo dos Blocos a ação empilha(x,y) move um bloco x que está na mão do robô para cima de um outro bloco y.  Para resolvermos um problema nesse domínio que envolva apenas dois blocos, A e B, a ação empilha(x,y) deve ser traduzida para um conjunto de ações proposicionais (ou ações instanciadas), neste caso, empilha(A,B) e empilha(B,A).  Note que empilha(x,y) é um nome de ação. O que chamamos de fluente ou literal de um domínio (por exemplo, sobre(x,y)) são os elementos das listas de pré-condições e efeitos da ação. Após a tradução, chamamos os fluentes de proposições.

Para esse projeto foi gerado um conjunto de ações proposicionais para cada problema. Para isso foi usado um parser (implementado pelo meu ex-aluno de mestrado Aldebaran Perseke) que recebe como entrada:

gerando um arquivo com as ações instanciadas, o estado inicial e a meta. Veja a descrição da linguagem adotada como formato de saída do parser.

Na medida que vocês resolverem os problemas propostos, publiquem no Forum da disciplina as seguintes informações:

        1. o nome do problema resolvido
        2. o tempo de CPU gasto
        3. o número de nós expandidos
        4. estratégia empregada

Domínio do Jantar Surpresa
 
Esse é um domínio bem simples e por isso servirá para vocês realizarem testes simples durante o desenvolvimento do sistema.  Os resultados desse domínio não deverão entrar para a análise de desempenho.
As ações estão descritas em PDDL e podem ser traduzidas na mão para o formato de saída adotado pelo
parser.
Problema para o Domínio do Jantar Surpresa
Este é um exemplo de problema para o domínio do Jantar Surpresa descrito na linguagem PDDL. Note que na lista de metas existe uma proposição negada ( not ( lixo ) ). Será que um planejador com uma heurística que considera o custo da solução do problema relaxado consegue resolver esse problema? Caso isso cause dificuldades para testar o seu planejador, especifique metas apenas com proposições positivas, ou seja, proposições não negadas.

Domínio do Mundo dos Blocos  

pick-up ( ?x - block )	o agente pega um bloco de cima da mesa e o segura
put-down ( ?x - block )	o agente coloca o bloco que está segurando em cima da mesa
stack ( ?x - block ?y - block )	o agente coloca o bloco que está segurando em cima de outro bloco
unstack ( ?x - block ?y - block )	o agente pega um bloco de cima de outro bloco e o segura

---





Domínio dos Satélites

A análise de desempenho deve ser feita a partir das curvas no tempo, número de estados visitados na busca e tamanho dos planos encontrados para os problemas e domínios estudados.

A nota deste projeto valerá de 0 a 10.0 pontos que serão distribuídos da seguinte forma:

            3.0 para a implementação da Primeira Fase
            3.0 para a implementação da Segunda Fase
            4.0 para a análise de desempenho e relatório final
           

 
• 2002 International Planning Competition  e  AIPS2002    -   Onde você encontra fácil um conjunto de domínios descritos em PDDL 
• 2004 International Planning Competition