Heuristic
Search Planning
O objetivo do projeto
é implementar 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.
Você deverá utilizar o algoritmo de busca heurística A* implementado no EP1. A
diferença agora é que a entrada do seu sistema de busca A* será como descrita
acima. Além disso, você deverá implementar TRÊS funções heurísticas diferentes
para serem usadas em seu A*:
·
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]: (D0) de custo aditivo e (D1) de custo MAX.
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 operadores STRIPS (ações com variáveis).
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 foi preciso gerar um conjunto de ações proposicionais para cada tamanho de problema. Para isso, foi usado um parser (implementado por Aldebaran Perseke, ex-aluno de mestrado do IME), que recebe como entrada:
que gera 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 (e que será a entrada do seu planejador).
Domínios de teste
simples
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 mas
somente usado para testar o seu programa!
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.
Nessa versão do
domínio do Mundo dos Blocos o agente robótico é capaz de executar 4 ações:
|
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 |
Exemplos de problemas
para o Mundo dos Blocos
Este é um domínio
de planejamento que está muito em moda. A programação de satélites espaciais
tem
sido tema de vários projetos financiados pelas grandes agências internacionais
de fomento à pesquisa.
Alguns desses projetos desenvolveram sistemas de planejamento que estão sendo
de fato utilizados em
estações espaciais.
Exemplos de problemas
para o domínio de 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.
IMPORTANTE:
No EP1 a maioria dos alunos não fizaram uma análise comparativa como foi
pedido mas somente adicionaram um conjunto de gráficos. No EP2 isso não será
aceito.
A nota deste
projeto valerá de 0 a 10.0 pontos que serão distribuídos da seguinte forma:
4.0 para a implementação
das funções heurísticas
6.0 para a
análise de desempenho e relatório final
Links de interesse e
bibliografia