Implementação do Planejador
Construir um sistema de planejamento que receba como entrada um conjunto de ações proposicionais, uma descrição do estado inicial e estado meta (ou estado objetivo) e devolva um plano de ações que, quando executadas, transformam o estado inicial no estado meta.Serão dadas duas especificações de domínios de planejamento: Mundo dos Blocos e Satélite. Esses domínios são descritos na linguagem PDDL e são do tipo STRIPS com variáveis (schemas). Para a geração das ações proposicionais os alunos poderão usar um programa dado.
O algoritmo de planejamento que deverá ser implementado é o HSP dado em sala de aula. Cada grupo de dois alunos deverá implementar uma das seguintes estratégias de busca:
Todos os grupos deverão implementar os dois tipos de função heurística do HSP discutidas em sala de aula: h_aditiva e h_max. O maior desafio deste projeto será implementar a função heurística. Todas as terças estarei na sala de aula para tirar dúvidas. Artigos que ajudarão vocês a desenvolverem o projeto podem ser encontrados na página do autor.
- Hill-climbing Reforçado e
- WA*
As duplas deverão entregar um relatório (detalhado abaixo) descrevendo o planejador, a implementação da função heurística, as curvas de desempenho (tempo e número de estados examinados pelo algoritmo de busca) e de comprimento de planos soluções. Além disso, o relatório deverá conter:
- uma análise dos resultados encontrados com a execução do planejador nos domínios dados
- uma descrição de um domínio novo de planejamento (veja critério de avaliação)
- uma proposta de como o planejador contruído poderia ser modificado para resolver problemas do domínio dos Satélites com variáveis numéricas.
| 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 |
Em geral, sistemas de planejamento que fazem busca local, como o HSP, raciocinam sobre uma descrição de ações proposicionais, ou seja, ações sem variáveis. Por exemplo, considere o domínio do mundo dos blocos com braço de robô descrito acima. 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 2 blocos, A e B, a ação empilha(x,y) deve ser traduzida para um conjunto de ações proposicionais, 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, 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. Daí o nome de ações do tipo Strips Proposicional.O Parser PDDL para Strips Proposicional
Este programa foi escrito em Perl pelo meu aluno de mestrado Aldebaran Perseke.Instruções de utilização do parser PDDL/Strips-proposicional
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.
As duplas deverão dividir as tarefas de forma equilibrada e os dois alunos deverão saber explicar todo o projeto, inclusive as partes implementadas pelo seu parceiro. Um dos critérios de avaliação que será aplicado é a entrevista individual com os membros do grupo.A nota deste projeto valerá de 0 a 10.0 pontos que serão distribuídos da seguinte forma:
5.0 para a implementação
4.0 para os testes de desempenho e relatório
1.0 para um novo domínio modelado como um problema de planejamento, ou seja, um conjunto de ações
Neste sítio você encontra
os domínios de teste da última competição internacional
de planejamento, entre eles o domínio dos Satélites.
Nesta página você poderá encontrar outros domínios
para sua escolha de mais um domínio para o projeto.