SCE-5774 Introdução à Inteligência Artificial

Primeiro projeto - 07/04/1999

Projeto

Mundo dos Blocos 2 – A seguinte figura representa três pilhas de blocos sobre uma mesa:

 

 

 

 

 

Represente em Prolog os fatos que descrevem as relações entre os blocos. Use dois predicados: um para indicar que um bloco está sobre outro bloco e outro para indicar que um bloco está imediatamente à esquerda de outro bloco. Para os blocos que estão sobre a mesa, defina somente fatos do segundo tipo.

Faça as seguintes perguntas:

a) Qual bloco está sobre o bloco B?
b) Quais são os blocos tal que A está embaixo?
c) Quais blocos estão sobre outros blocos?
d) Quais blocos estão sobre blocos que estão imediatamente à esquerda de outro bloco?

Defina o predicado acima(X,Y) e pilha_esquerda(X,Y). Gere perguntas pertinentes.

 

Resolução

O mundo dos blocos:

O mundo dos blocos é um micro-mundo que consiste de uma superfície plana, ou uma mesa, um conjunto de blocos colocados sobre essa superfície e que podem ser empilhados uns sobre os outros e uma braço de robô que pode manipular os blocos. Esse braço pode realizar as ações:

Além disso, algumas restrições são feitas:

Além de blocos outros objetos podem ser utilizados, tais como caixas, pirâmides e esferas.

O mundo dos blocos é um domínio muito utilizado no estudo de planejamento.

 

O Programa desenvolvido:

 

% programa que da algumas relacoes entre blocos no mundo dos blocos
% autora: Katti Faceli
% data: 07/04/1999

% sobre(X,Y) - bloco X esta sobre bloco Y.

sobre(b,a).
sobre(c,b).
sobre(d,c).
sobre(f,e).
sobre(g,f).
sobre(i,h).

% imed_esquerda(X,Y) - bloco X esta a esquerda de Y.
imed_esquerda(a,e).
imed_esquerda(b,e).
imed_esquerda(c,e).
imed_esquerda(d,e).
imed_esquerda(a,f).
imed_esquerda(b,f).
imed_esquerda(c,f).
imed_esquerda(d,f).
imed_esquerda(a,g).
imed_esquerda(b,g).
imed_esquerda(c,g).
imed_esquerda(d,g).
imed_esquerda(e,h).
imed_esquerda(f,h).
imed_esquerda(g,h).
imed_esquerda(e,i).
imed_esquerda(f,i).
imed_esquerda(g,i).

% acima(X,Y) - bloco X esta acima do bloco Y na mesma pilha.
acima(X,Y) :- sobre(X,Y).
acima(X,Y) :- sobre(X,Z),
                    acima(Z,Y).

% pilha_esquerda(X,Y) - bloco X esta a esquerda do bloco Y (o mesmo que usar so imed_esquerda).
pilha_esquerda(X,Y) :- imed_esquerda(X,Y).

% todos_acima(Bloco, Acima) - obtem uma lista com todos os blocos que estao
% acima do bloco Bloco.
todos_acima(Bloco, Acima) :- findall(X,acima(X,Bloco),Acima).

% todos_abaixo(Bloco, Abaixo) - obtem uma lista com todos os blocos que estao
% abaixo do bloco Bloco.
todos_abaixo(Bloco, Abaixo) :- findall(X,acima(Bloco,X),Abaixo).

% predicado auxiliar para concatenar duas listas.
conc([],L,L).
conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3).

% pilha(Bloco,Pilha) - Obtem uma lista com todos os blocos que pertencem a
% mesma pilha do bloco Bloco.
pilha(Bloco,Pilha) :- findall(X,acima(Bloco,X),Abaixo),
                             findall(X,acima(X,Bloco),Acima),
                             conc(Abaixo,[Bloco|Acima],Pilha).

% pilha_esquerda(Bloco,Pilha) - Obtem uma lista com todos os blocos que
% pertencem a pilha a esquerda do bloco Bloco.
pilha_esquerda(Bloco,Pilha) :- findall(X,imed_esquerda(X,Bloco),Pilha).

% pilha_direita(Bloco,Pilha) - Obtem uma lista com todos os blocos que
% pertencem a pilha a direita do bloco Bloco.
pilha_direita(Bloco,Pilha) :- findall(X,imed_esquerda(Bloco,X),Pilha).
 

Características utilizadas na resolução:

Além dos fatos e regras do Prolog, foram utilizados o predicado predefinido findall para obter todos resultados obtidos por um predicado e a manipulação de listas para manusear esses resultados que são armazenados na forma de lista.

 

Perguntas:

Qual bloco está sobre o bloco B? 

?- sobre(X,b).
X = c .
yes

 

Quais são os blocos tal que A está embaixo?

(Obs: neste caso foi necessário obter o elemento que está sobre A (X), o elemento que está sobre este X (Y) e sobre Y (Z); se houvesse mais elementos na pilha outras variáveis seriam necessárias. O predicado acima(X,Y) resolve o problema de forma mais simples e eficiente) 

?- sobre(X,a), sobre(Y,X), sobre(Z,Y).
X = b
Y = c
Z = d .
Yes

Utilizando o predicado acima(X,Y) pode-se obter todos os blocos que estão acima de outro, através de backtracking: 

?- acima(X,a).
X = b ;
X = c ;
X = d ;
no

Pode-se também obter uma lista com todos os blocos que estão acima de outro utilizando o predicado todos_acima(Bloco,Acima) ou fazendo a pergunta diretamente com findall.

 
?- todos_acima(a,Lista).
Lista = [b,c,d] .
yes

 

?- findall(X,acima(X,a),Acima).
X = H480
Acima = [b,c,d] .
yes

 

Quais blocos estão sobre outros blocos? 

?- sobre(X,_).
X = b ;
X = c ;
X = d ;
X = f ;
X = g ;
X = i ;
no

ou, mostrando qual o bloco que está abaixo (Y): 

?- sobre(X,Y).
X = b
Y = a ;
X = c
Y = b ;
X = d
Y = c ;
X = f
Y = e ;
X = g
Y = f ;
X = i
Y = h ;
no

Ou utilizando o findall:

 
?- findall(X,sobre(X,Y),Acima).
X = H522
Y = H524
Acima = [b,c,d,f,g,i] .
Yes

?- findall([X,Y],sobre(X,Y),Acima).
X = H567
Y = H568
Acima = [[b,a],[c,b],[d,c],[f,e],[g,f],[i,h]] .
yes

Quais blocos estão sobre blocos que estão imediatamente à esquerda de outro bloco? 

?- sobre(X,Y),imed_esquerda(Y,Z).
X = b
Y = a
Z = e ;
X = b
Y = a
Z = f ;
X = b
Y = a
Z = g ;
X = c
Y = b
Z = e ;
X = c
Y = b
Z = f ;
X = c
Y = b
Z = g ;
X = d
Y = c
Z = e ;
X = d
Y = c
Z = f ;
X = d
Y = c
Z = g ;
X = f
Y = e
Z = h ;
X = f
Y = e
Z = i ;
X = g
Y = f
Z = h ;
X = g
Y = f
Z = i ;
no

Utilizando findall:

 
?- findall([X,Y,Z],(sobre(X,Y),imed_esquerda(Y,Z)),Lista).
X = H627
Y = H628
Z = H629
Lista = [[b,a,e],[b,a,f],[b,a,g],[c,b,e],[c,b,f],[c,b,g],[d,c,e],[d,c,f],[d,c,g],[f,e,h],[f,e,i],[g,f,h],[g,f,i]] .
yes

 

Outras perguntas:

 A está acima de F? 

?- acima(a,f). 
no

 

G está acima de E? 

?- acima(g,e).
yes

 

Quais blocos estão acima de B? 

?- acima(X,b).
X = c ;
X = d ;
no

?- todos_acima(b,L).
L = [c,d] ;
no

Quais blocos estão abaixo de G? 

?- acima(g,X).
X = f ;
X = e ;
no

?- todos_abaixo(g,L).
L = [f,e] ;
no 

 

D está na pilha à esquerda de E? 

?- esta_pilha_esquerda(d,e).
yes

 

G está na pilha à esquerda de A? 

?- esta_pilha_esquerda(g,a).
no

 

A está na pilha à esquerda de I? 

?- esta_pilha_esquerda(a,i).
no

 

Quais blocos estão na pilha à esquerda de I? 

?- esta_pilha_esquerda(X,i).
X = e ;
X = f ;
X = g ;
No

Ou, obtendo uma lista com estes blocos através do findall diretamente: 

?- findall(X,pilha_esquerda(X,i),Pilha).
X = H156
Pilha = [e,f,g] ;
No

Ou, utilizando pilha_esquerda(Bloco,Pilha), que dá uma lista com todos os blocos da pilha a esquerda de Bloco:

 
?- pilha_esquerda(i,Pilha).
Pilha = [e,f,g] .
yes

 

Quais blocos estão na pilha à direita de C? 

?- pilha_direita(c,Pilha).
Pilha = [e,f,g] ;
No

 

Quais blocos estão acima do bloco F ou em uma pilha imediatamente a sua esquerda?

?- acima(X,f);esta_pilha_esquerda(X,f).
X = g ;
X = a ;
X = b ;
X = c ;
X = d ;
No

Quais são os blocos que estão na pilha de D?

?- pilha(d,Pilha).
Pilha = [c,b,a,d] ;
no