Programação por conjuntos

Páginas: 8 (1923 palavras) Publicado: 2 de novembro de 2011
Inteligência Artificial
2010/2011
Relatório Trabalho Prático 3 – Turno P4
Utilização da programação por conjuntos de resposta SMODELS na resolução de problemas combinatórios.

[Página deixada em branco intencionalmente]

Introdução

Neste trabalho pretende-se utilizar o paradigma de programação por conjuntos de resposta (answer-set programming), recorrendo ao programa SMODELS, queimplementa a semântica dos modelos estáveis para programas em lógica, que no nosso caso de estudo, passa por modelar um problema combinatório. Em conjunto com o smodels vamos utilizar o programa lparse que adiciona variáveis à linguagem que se está a escrever, gerando assim um programa em lógica, livre de variáveis para que o smodels o possa processar. O lparse para além da semântica de modelo estável,implementa também a semântica da negação clássica e a de modelos estáveis parciais entre outros, fazendo depois a tradução para programas de lógica normal.
Na semântica dos modelos estáveis, os modelos são validados pelo programa ou seja só podemos ter coisas verdadeiras para as quais tenho um antecedente com uma regra verdadeira. Os modelos podem ser vistos como cenários possíveis, podendocada programa ter nenhum, um ou vários modelos estáveis.
Para determinar um modelos estável, é utilizada a transformação de Gelfond-Lifschitz, em que um modelo é estável se e só se: I = least (P/I), sendo I uma interpretação (conjunto de átomos), e least(P/I) um programa positivo, que por definição tem apenas um único modelo mínimo.

A programação por conjuntos de resposta aparece então com aexpressividade da programação em lógica com a semântica dos modelos estáveis. Os conjuntos de resposta ou modelos estáveis correspondem a uma solução. Este paradigma de semântica de modelo estável garante a completude, ou seja, a descoberta de uma solução é garantida.



Desenvolvimento

O problema a modelar, tem por base a análise das observações recolhidas por um Rover em Marte em cincopontos de observação pré determinados, agregando a informação em cinco observações por cada ponto a fim de concluir se existe água ou não. As observações podem ter o valor positivo (+), zero (0) ou negativo (-).
Por problemas de comunicação os dados chegaram incompletos à Terra, ficando 3 observações, por registar, podendo estas então assumir os valores {+, 0, -} identificados na tabela. Osresultados vão ser analisados na Terra por cinco peritos, Anacleto, Belarmina, Carlota, Daniel e Ester.

  | Obs. 1 | Obs. 2 | Obs. 3 | Obs. 4 | Obs. 5 |
Ponto 1 | + | + | + | + | + |
Ponto 2 | + | + | {+, 0, -} | 0 | {+, 0, -} |
Ponto 3 | 0 | 0 | {+, 0, -} | 0 | + |
Ponto 4 | + | + | + | - | + |
Ponto 5 | 0 | + | - | 0 | - |
Tabela [ 1 ] – Tabela das Observações Recebidas na Terrafeitas pelo Rover. As observações incompletas estão identificadas por {+, 0, -}
Os resultados de cada ponto de observação, foram discutidos pelos peritos, onde cada um destes proferiu uma ou mais opiniões.
O objectivo do trabalho é recorrer ao sistema smodels e verificar que as 9 frases proferidas são incompatíveis existindo uma que é falsa.


Resultados e Observações

Seguindo asindicações do enunciado, começámos por definir os factos e construir o gerador de modelos estáveis.
1{obsPonto(P,Obs,Res):resultado(Res)}1 :- ponto(P), obs(Obs).

Este gerou 27 modelos estáveis, mostrando que a intuição de que o espaço de respostas é de 33 (3 observações em falta para 3 resultados possíveis) é verdadeira.

Em seguida definimos o predicado interessante com base nas condições dadaspelo enunciado, definindo o que torna um ponto de observação interessante.
Por observação directa na tabela observamos que o ponto 5 não vai ser interessante e é o que observamos no output do interessante, que é mostrado no Anexo A.

interessante(P):- ponto(P), cond1(P), cond2(P).
interessante(P):- ponto(P), cond3(P), cond4(P).

A seguir foi definido o predicado tem_agua, que indica se um...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • conjuntos
  • Conjuntos !
  • conjuntos
  • Conjunto
  • Conjunto
  • Conjuntos
  • Conjuntos
  • Conjuntos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!