SCE-5774 Introdução à Inteligência Artificial
Primeiro projeto - 07/04/1999
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.
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.
% 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).
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.
?- sobre(X,b). X = c . yes
(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
?- 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
?- 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
?- acima(a,f). no
?- acima(g,e). yes
?- acima(X,b). X = c ; X = d ; no ?- todos_acima(b,L). L = [c,d] ; no
?- acima(g,X). X = f ; X = e ; no ?- todos_abaixo(g,L). L = [f,e] ; no
?- esta_pilha_esquerda(d,e). yes
?- esta_pilha_esquerda(g,a). no
?- esta_pilha_esquerda(a,i). no
?- 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
?- pilha_direita(c,Pilha). Pilha = [e,f,g] ; No
?- acima(X,f);esta_pilha_esquerda(X,f). X = g ; X = a ; X = b ; X = c ; X = d ; No
?- pilha(d,Pilha). Pilha = [c,b,a,d] ; no