SCE 5774 - Introdução à Inteligência Artificial
Segundo Projeto
Rato no Tabuleiro
&
TRY ME
Humberto Costa de Sousa
Rato no Tabuleiro
Um rato em uma posição de um tabuleiro de xadrez (Xr, Yr) quer pegar um pedaço de queijo em uma outra posição do tabuleiro (Xq,Yq). O rato lembra por onde caminha e não passa duas vezes pela mesma posição. Estando em uma posição ele pode se movimentar no máximo a qualquer das 8 posições vizinhas (não pode sair do tabuleiro). Determinar o caminho para pegar o queijo.
Acima temos ilustrado uma situação inicial do problema. O queijo se encontra na posição 2/6 do tabuleiro e o rato na posição 7/2. O rato pode se mover nas seguintes direções:
Estas direções serão representadas pelos 8 pontos cardinais n, s, l, o, no, ne, so, se. O mapeamento destes movimentos pode ser representado em prolog por:
n(X1/Y1,X1/Y2):- Y1 < 8, Y2 is Y1 + 1. |
s(X1/Y1,X1/Y2):- Y1 > 1, Y2 is Y1 - 1. |
l(X1/Y1,X2/Y1):- X1 < 8, X2 is X1 + 1. |
o(X1/Y1,X2/Y1):- X1 > 1, X2 is X1 - 1. |
ne(X1/Y1,X2/Y2):- X1 < 8, Y1 < 8, X2 is X1 + 1, Y2 is Y1 + 1. |
no(X1/Y1,X2/Y2):- X1 > 1, Y1 < 8, X2 is X1 - 1, Y2 is Y1 + 1. |
se(X1/Y1,X2/Y2):- X1 < 8, Y1 > 1, X2 is X1 + 1, Y2 is Y1 - 1. |
so(X1/Y1,X2/Y2):- X1 > 1, Y1 > 1, X2 is X1 - 1, Y2 is Y1 - 1. |
A solução deste problema foi alcançada utilizando o algoritmo de busca A* que combina uma função heurística admissível h(n) com uma função de custo g(n), de maneira que sua função de avaliação é f(n) = h(n) + g(n).
A função de custo adotada para este problema foi a profundidade do nó na árvore de busca e a função heurística o número de passos necessários para alcançar as coordenadas do queijo. A função heurística pode ser expressada como:
h(n) = max( |Xn - Xq| , |Yn - Yq| )
onde, Xn/Yn representam as coordenadas do nó n no tabuleiro e Xq/Yq representam as coordenadas do queijo no tabuleiro.
Para não repetir um caminho já percorrido, as coordenadas percorridas são armazenadas em uma lista auxiliar durante a busca, assim quando os nós filhos de um nó são expandidos, os que possuem coordenadas já visitadas, não são inseridos na lista de nós a serem visitados.
A listagem mouse.pl contém o código com a solução deste problema.
Principais metas e saída do programa:
resolve(Estado, Percurso, Solucao):-
f_func(Estado,0,F), % Calcula a f(n)=g(n)+h(n)
busca([Estado#0#F#[]], Percurso, S), % Busca solucao lembrando os
% pontos percorridos
inverte(S, [], Solucao). % Inverte a lista temporaria
% para apresentar a solucao
go:-
nl, write('Rato no Tabuleiro'),
nl, write('Entre com a posicao do queijo(X/Y): '),
read(EstadoQ),
setgoal(EstadoQ),
nl, write('Entre com a posicao do rato(X/Y): '),
read(EstadoM),
resolve(EstadoM, [], S),!,
nl, write('Solucao: '),
write(S),nl,
retract(goal(EstadoQ)).
| ?- go.
Rato no Tabuleiro
Entre com a posicao do queijo(X/Y): |: 2/6.
Entre com a posicao do rato(X/Y): |: 7/2.
Solucao: [o,no,no,no,no]
yes
TRY ME
Um sliding block puzzle, onde dada a configuração inicial :
deve-se obter:
Os movimentos são restritos a deslizar os blocos para o espaço em branco, ou trocar o espaço em branco com um dos seus blocos vizinhos. Estes movimentos foram representados em prolog como:
esquerda( 0/R/Y/M/E/T , R/0/Y/M/E/T ). esquerda( R/0/Y/M/E/T , R/Y/0/M/E/T ). esquerda( T/R/Y/0/M/E , T/R/Y/M/0/E ). esquerda( T/R/Y/M/0/E , T/R/Y/M/E/0 ).
|
direita( T/R/0/M/E/Y , T/0/R/M/E/Y ). direita( T/0/R/M/E/Y , 0/T/R/M/E/Y ). direita( T/R/Y/M/E/0 , T/R/Y/M/0/E ). direita( T/R/Y/M/0/E , T/R/Y/0/M/E ).
|
frente( T/R/0/M/E/Y , T/R/Y/M/E/0 ). frente( T/0/R/M/E/Y , T/E/R/M/0/Y ). frente( 0/R/Y/M/E/T , M/R/Y/0/E/T ). |
tras( T/R/Y/M/E/0 , T/R/0/M/E/Y ). tras( T/R/Y/M/0/E , T/0/Y/M/R/E ). tras( T/R/Y/0/M/E , 0/R/Y/T/M/E ). |
A solução deste problema foi alcançada utilizando o algoritmo de busca A* que combina uma função heurística admissível h(n) com uma função de custo g(n), de maneira que sua função de avaliação é f(n) = h(n) + g(n).
A função de custo adotada para este problema foi a profundidade do nó na árvore de busca. A função heurística é a combinação de dois estimadores freqüentemente utilizados em problemas de sliding blocks: a função de distância Manhattan, que calcula uma distância próxima até a solução, e a uma função fora-de-ciclo que penaliza o custo quando o estado está muito diferente do objetivo.
A solução deste problema está implementado em tryme.pl.
Vale lembrar que a execução deste algoritmo consome alguns minutos.
Principais metas e saída do programa:
resolve(Estado, Solucao):-
f_func(Estado,0,F), % Calcula a f(n)=g(n)+h(n)
busca([Estado#0#F#[]], S), % Busca solucao
inverte(S, [], Solucao). % Inverte a lista temporaria
% para apresentar a solucao
go:-
nl, write('Estado inicial:'),
nl, write('T R Y'),
nl, write('M E '),
nl, write('Solucao:'),
resolve(1/2/3/4/5/0, S),
nl, write(S),nl.
| ?- go.
Estado inicial:
T R Y
M E
Solucao:
[tras,direita,frente,direita,tras,esquerda,esquerda,frente,direita,tras,direita,frente,esquerda,esquerda,tras,direita,frente,direita,tras,esquerda,esquerda]
yes