O sistema deverá ser desenvolvido em duplas. O objetivo do projeto é implementar diferentes versões de um sistema de planejamento clássico que faz busca heurística no espaço de estados. O sistema deverá receber como entrada um conjunto de ações proposicionais, uma descrição do estado inicial e um conjunto de proposições que devem ser satisfeitas no estado meta. O planejador deverá devolver um plano de ações (totalmente ordenado) que, quando executadas, transformam o estado inicial num estado meta.

Cada dupla deverá implementar: 

• um algoritmo de busca do tipo A* (apresentado em sala de aula e detalhado no livro [AIMA, 2006]).
  
• uma heurística simples que calcula o número de proposições da meta que não são satisfeitas no estado atual.
• duas heurísticas baseadas no sistema HSP [Bonet and Geffner, 2001]: de custo aditivo e de custo MAX. 

O algoritmo de busca deverá:

Domínios de Teste:

O sistema de planejamento, com as diferentes heurísticas, deverá ser analisado 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 de ações).

Em geral, sistemas de planejamento que fazem busca no espaço de estados, como o que será implementado nesse projeto,  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, que também deverão ser instanciados com os objetos do problema.

Assim, para a realização desse projeto será preciso gerar um conjunto de ações proposicionais para cada tamanho de problema. Para isso, será preciso usar um parser (implementado por Aldebaran Perseke, ex-aluno de mestrado do IME), que recebe como entrada:

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

Para se ter uma idéia de como os planejadores implementados resolvem 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. heurística empregada

Domínio do Jantar Surpresa
 
Esse é um domínio bem simples e por isso servirá somente para a realização de 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: 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 deverá ser feita com base nos tempos de execução, número de estados visitados pela busca e tamanho dos planos encontrados para os problemas e domínios estudados. esses resultados deverão ser apresentados na forma de gráficos.

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 do A*
            3.0 para a implementação das funções heurísticas
            4.0 para a análise de desempenho e relatório final
           

• [Bonet and Geffner, 2001] Heuristic Search Planner Ver. 2.0. (Description of Planner entered into AIPS-00 Competition) Blai Bonet and Héctor Geffner. AI Magazine. Fall 2001. Pages 77-80.

• 2002 International Planning Competition  e  AIPS2002    -   Onde você encontra fácil um conjunto de domínios descritos em PDDL 
• 2004 International Planning Competition
• [AIMA, 2006] Artificial Intelligence: A Modern Approach (AIMA). Stuart Russel and Peter Norvig. Prentice Hall. Second Edition.