Labirinto

Universidade Metodista de Piracicaba

Trabalho de Inteligência Artificial

Adriano Gheller Bruschi

Fabricio Aparecido Breve

Luis Gustavo Giordano

Descrição do Universo

Um robô deve caminhar por um labirinto até encontrar a saída.

Ambiente: o labirinto fica localizado em uma sala que está dividida em 100 quadros (10x10). Cada espaço pode estar livre (o robô pode passar), ou bloqueado (o robô não pode passar).

Exemplo:

Agente: o agente é o robô, ele deve caminhar pelo labirinto até encontrar a saída ou até constatar que o labirinto não tem saída, nesse caso ele deve voltar para a entrada.

Conhecimento: o robô sabe apenas que o labirinto tem 10x10 e que o Espaço 10,10 é a saída. Os caminhos são aleatórios, portanto ele não sabe qual o caminho que leva até a saída, e também não sabe se existe um caminho que leva até a saída, pois pode não existir uma maneira de chegar até lá ou o bloco da saída pode estar fechado.

Objetivo: Chegar na saída caso exista um caminho. Ou voltar para a entrada caso chegue a conclusão de que não existe uma saída ou não existe uma maneira de chegar na saída.

Estado Inicial:

O robô sempre começa no espaço 1,1 (superior esquerdo)

Obs: os espaços bloqueados e livres dependem do labirinto selecionado pelo usuário. Existem alguns labirintos predefinidos e o usuário também pode criar o seu próprio labirinto. O espaço inicial (1,1) deve sempre estar livre.

Estado Final:

Existem 2 tipos de estados finais possíveis:

No labirinto com saída, o robô estará na posição de saída (10,10).
Em um labirinto sem saída, o robô volta ao início do labirinto, na posição (1,1).

Os espaços bloqueados e livres também dependerão do labirinto selecionado pelo usuário.

Labirinto com saída

Labirinto sem saída

Ações:

Andar para cima
Andar para baixo
Andar para a esquerda
Andar para a direita

O custo de cada ação é 1

Percepções:

O robô “enxerga” apenas os quadros imediatamente acima, abaixo, a direita e a esquerda do local onde ele está. Assim ele pode perceber se estes quadros estão bloqueados ou livres.

Método de Busca Utilizado:

Foi escolhido o método de busca heurística “Hill Climbing”, a seleção do caminho à ser seguido é baseada em uma lista de prioridades. Neste caso, a primeira prioridade é andar à direita, a segunda prioridade é andar para baixo, a terceira andar à esquerda, e a quarta e última é andar para cima. As prioridades se devem ao fato de o Agente saber que a saída (se existir) estará no canto inferior direito. Ele também nunca deve escolher um caminho pelo qual já tenha passado anteriormente independentemente da prioridade, se ele o fizesse ficaria andando em círculos.

Exemplo de Estados intermediários (Exemplo de execução do algoritmo)

Não é possível representar todos os estados intermediários possíveis, pois são muitos, com uma matriz 10x10 é possível criar até 2⁹⁹ labirintos diferentes, ou seja 633.825.300.114.114.700.748.351.602.688 labirintos diferentes. E para cada labirinto o robô pode dar de 0 a 196 passos.

Representamos aqui alguns estados intermediários do labirinto já utilizado como exemplo anteriormente:

O robô começa a caminhar pelo labirinto a procura da saída	Neste ponto o robô encontra uma bifurcação e deve escolher o caminho a seguir.	O robô escolhe entrar pelo caminho a direita baseado na sua lista de prioridades.
	O robô percebe que escolheu um caminho sem saída.	Agora o robô deve voltar até a última bifurcação e tomar um outro caminho
	O robô já sabe que pelo caminho de cima ele já passou (foi de onde ele veio)	Portanto ele decide ir para baixo agora.

E o robô continua caminhando desta forma, escolhendo um caminho em cada bifurcação de acordo com sua prioridade. E no caso de chegar em um beco sem saída, ele volta e escolhe outro caminho, até que ele consiga chegar ao final do labirinto.

Se o robô andar por todos os caminhos possíveis e não encontrar a saída, ele conclui que o labirinto não tem saída, e retorna para o início.

Algoritmo

Variáveis:

Matriz 10x10 para armazenar onde o robô já passou. (0 = não passou, 1 = passou)0
Estrutura Bloco

Inteiro Linha, Coluna
Ponteiros: cima, baixo, esquerda, direita

Método de Busca:

função caminha(ponteiro bloco atual) {

marca espaço na matriz como já caminhado;

se (linha = 9 e coluna = 9) então achou saída;

senão {

se (bloco a direita não bloqueado e ainda não caminhou por ele) {

caminha(bloco da direita);

}

se (bloco abaixo não bloqueado e ainda não caminhou por ele)

caminha(bloco abaixo);

}

se (bloco a esquerda não bloqueado e ainda não caminhou por ele) {

caminha(bloco da esquerda);

}

se (bloco acima não bloqueado e ainda não caminhou por ele) {

caminha(bloco acima);

}

É montada dinamicamente uma estrutura, com variáveis dinâmicas sendo alocadas para cada novo bloco visitado. Cada variável armazena a linha e coluna de cada bloco, e contém ponteiro para as variáveis dos blocos imediatamente acima, abaixo, a direita e a esquerda.

Algoritmo Completo comentado:

/* LAB vr 1.0

Adriano Gheller Bruschi

Fabricio Aparecido Breve

Luis Gustavo Giordano

Inteligencia Artificial I

5§ semestre - CCOMP

Observa‡äes:

a) todo coment rio com a marca‡Æo (I) representa

vari veis e/ou fun‡äes que nÆo fazem parte do

projeto em si, e sÆo usadas apenas para montar a

interface do programa.

b) As fun‡äes usadas apenas para montar a interface

nao estÆo comentadas detalhadamente

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

#include <string.h>

#include <stdlib.h>

#include <graphics.h>

#include <dos.h>

// matriz que guarda o labirinto

short int mat[10][10];

// matriz do robo para guardar caminho percorrido

short int matint[10][10];

// arq -> arquivo do labirinto

// arqrobo -> desenho do robo (I)

FILE *arq,*arqrobo;

// estrutura bloco, armazena cada bloco no

// qual o robo passa. Tem ponteiros para os

// blocos acima, abaixo, a esquerda e a direita

struct bloco {

short int lin,col;

bloco *c,*b,*e,*d;

}*inicio;

// ultima bloco no qual o robo esteve (I)

short int lastlin,lastcol;

// variavel para nome de arquivo do usuario (I)

char nome_arq[15];

// variavel que guarda o desenho do robo (I)

int robo[2025];

// passos 1 guarda o custo total do caminho percorrido

// passos 2 guarda o custo caso o rob“ tivesse sempre

// tomado o caminho correto e nÆo tivesse de fazer

// nenhum backtrack.

short int passos,passos2;

// inicializacao do modo gr fico (I)

void modografico() {

int gd,gm;

gd=DETECT;

initgraph(&gd,&gm,"");

if(graphresult()!=grOk) exit(1);

}

// le o arquivo que guarda o desenho do robo

// para a memoria (I)

short int robotomem() {

if((arqrobo=fopen("robo.txt","r"))==NULL) {

cout << "Erro abrindo arquivo robo.txt\n";

return(0);

}

short int tmp;

for (int x=0;x<2025;x++) {

do {

tmp=fgetc(arq);

}

while(tmp==10);

robo[x]=tmp-48;

}

fclose(arqrobo);

return(1);

}

// fun‡Æo que armazena a paleta de cores

// do desenho do robo (I)

short int corrobo(short int x) {

switch(x) {

case 0: return(0);

case 1: return(7);

case 2: return(10);

case 3: return(4);

case 4: return(14);

case 5: return(1);

};

return(0);

};

// fun‡Æo que desenha o robo na tela (I)

void desenharobo(short int col, short int lin) {

for (int x=0;x<2025;x++) {

putpixel(47*col+86+x%45,47*lin+6+x/45,corrobo(robo[x]));

}

// fun‡Æo que desenha os blocos do labirinto na tela (I)

void desenhabloco(short int col, short int lin, short int tipo) {

if (tipo==0) setfillstyle(1,1);

if (tipo==1) setfillstyle(9,10);

bar(47*col+86,47*lin+6,47*col+131,47*lin+51);

}

// fun‡Æo que desenha o labirinto na tela (I)

void desenhalab() {

for(int x=0;x<11;x++) {

line(47*x+85,5,47*x+85,474); //linhas verticais

line(85,47*x+5,555,47*x+5); //linhas horizontais

}

for(x=0;x<10;x++) {

for(int y=0;y<10;y++) {

desenhabloco(y,x,mat[x][y]);

}

outtextxy(8,10,"ENTRADA ->");

outtextxy(560,450,"<- SAÖDA");

}

// fun‡Æo que le o arquivo do mapa para a mem¢ria (I)

short int preenchemat() {

if((arq=fopen(nome_arq,"r"))==NULL) {

printf("Erro abrindo arquivo de mapa\n\n");

return(0);

}

else {

char str[12];

int y;

for(int x=0;x<10;x++) {

fgets(str,12,arq);

for(y=0;y<10;y++) {

mat[x][y]=str[y]-48;

}

fclose(arq);

}

return(1);

}

// funcao que atualiza posi‡Æo do robo na tela

// e contadores de custo (I)

void mostra(short int lin,short int col) {

char passos_c[4],passos2_c[4];

if (lastlin!=lin || lastcol!=col) {

desenhabloco(lastcol,lastlin,0);

desenharobo(col,lin);

passos++; // aumenta 1 ponto no contador de custo

strcpy(passos_c,itoa(passos,passos_c,10));

strcpy(passos2_c,itoa(passos2,passos2_c,10));

setfillstyle(0,1);

bar(580,250,639,330);

outtextxy(580,250,passos_c);

outtextxy(580,300,passos2_c);

delay(400);

lastlin=lin;

lastcol=col;

}

// Funcao de Caminhamento

short int caminha(bloco *sbloco) {

// aumenta um na variavel de custo para melhor caminho

passos2++;

// marca bloco atual como j visitado

matint[sbloco->lin][sbloco->col]=1;

mostra(sbloco->lin,sbloco->col);

// verifica se bloco atual ‚ a sa¡da

if(sbloco->lin==9 && sbloco->col==9) {

return(1);

}

// se nao achou saida, decide pra qual caminho deve seguir

// primeira tentativa ‚ seguir a direita, prioridade 1

if (sbloco->col!=9) {

if (mat[sbloco->lin][sbloco->col+1]==1) matint[sbloco->lin][sbloco->col+1]=1;

else if(!matint[sbloco->lin][sbloco->col+1]) {

sbloco->d= (struct bloco *) malloc(sizeof(bloco));

sbloco->d->d=NULL;

sbloco->d->b=NULL;

sbloco->d->c=NULL;

sbloco->d->e=sbloco;

sbloco->d->lin=sbloco->lin;

sbloco->d->col=sbloco->col+1;

if(caminha(sbloco->d)) return(1); // chamada recursiva

}

mostra(sbloco->lin,sbloco->col);

// segunda tentativa ‚ seguir para baixo, prioridade 2

if (sbloco->lin!=9) {

if (mat[sbloco->lin+1][sbloco->col]==1) matint[sbloco->lin+1][sbloco->col]=1;

else if(!matint[sbloco->lin+1][sbloco->col]) {

sbloco->b= (struct bloco *) malloc(sizeof(bloco));

sbloco->b->b=NULL;

sbloco->b->d=NULL;

sbloco->b->e=NULL;

sbloco->b->c=sbloco;

sbloco->b->lin=sbloco->lin+1;

sbloco->b->col=sbloco->col;

if(caminha(sbloco->b)) return(1);

}

mostra(sbloco->lin,sbloco->col);

// terceira tentativa ‚ seguir para esquerda, prioridade 3

if (sbloco->col!=0) {

if (mat[sbloco->lin][sbloco->col-1]==1) matint[sbloco->lin][sbloco->col-1]=1;

else if(!matint[sbloco->lin][sbloco->col-1]) {

sbloco->e= (struct bloco *) malloc(sizeof(bloco));

sbloco->e->c=NULL;

sbloco->e->b=NULL;

sbloco->e->e=NULL;

sbloco->e->d=sbloco;

sbloco->e->lin=sbloco->lin;

sbloco->e->col=sbloco->col-1;

if(caminha(sbloco->e)) return(1);

}

mostra(sbloco->lin,sbloco->col);

// quarta tentativa ‚ seguir para cima, prioridade 4

if (sbloco->lin!=0) {

if (mat[sbloco->lin-1][sbloco->col]==1) matint[sbloco->lin-1][sbloco->col]=1;

else if(!matint[sbloco->lin-1][sbloco->col]) {

sbloco->c= (struct bloco *) malloc(sizeof(bloco));

sbloco->c->c=NULL;

sbloco->c->d=NULL;

sbloco->c->e=NULL;

sbloco->c->b=sbloco;

sbloco->c->lin=sbloco->lin-1;

sbloco->c->col=sbloco->col;

if(caminha(sbloco->c)) return(1);

}

passos2--;

mostra(sbloco->lin,sbloco->col);

return(0);

// se nao conseguiu seguir para nenhuma dire‡Æo,

// ser preciso voltar (backtrack), diminui 1

// na variavel que guarda o custo do melhor caminho

}

// funcao que le o nome de arquivo de usuario (I)

void peganomearq() {

do {

printf("Digite o nome do arquivo de mapa: ");

gets(nome_arq);

if(strlen(nome_arq)>13)

printf("Erro: Nome de arquivo invalido\n\n");

}

while(strlen(nome_arq)>13);

}

void main() {

short int op;

do {

for(int x=0;x<10;x++)

for (int y=0;y<10;y++)

matint[x][y]=0;

printf("Qual labirinto vocˆ deseja?\n");

printf("1. Mapa 1\n");

printf("2. Mapa 2\n");

printf("3. Mapa 3 (sem sa¡da)\n");

printf("4. Mapa de usu rio\n");

printf("0. Sair\n");

do {

printf("Digite sua op‡Æo: ");

scanf("%i",&op);

getchar();

}

while(op<0 && op>4);

switch(op) {

case 0:break;

case 1:strcpy(nome_arq,"lab1.txt");break;

case 2:strcpy(nome_arq,"lab2.txt");break;

case 3:strcpy(nome_arq,"lab3.txt");break;

case 4:peganomearq();

}

if (op!=0) {

if (preenchemat()) {

if (robotomem()) {

if(mat[0][0]==1) printf("Erro: Bloco inicial nÆo pode estar bloqueado\n\n");

else {

passos=passos2=-1;

lastlin=lastcol=-2;

modografico();

desenhalab();

getch();

inicio=(struct bloco *) malloc(sizeof(bloco));

inicio->d=inicio->e=inicio->b=inicio->c=NULL;

inicio->lin=0; inicio->col=0;

caminha(inicio);

getch();

closegraph();

}

while(op!=0);

}

Instruções do programa:

Instalação:

Os seguintes arquivos devem estar em um mesmo diretório:

LAB.EXE
EGAVGA.BGI
ROBO.TXT
LAB1.TXT
LAB2.TXT
LAB3.TXT
LAB4.TXT

Mostrando o caminhamento em um labirinto:

Basta escolher a opção desejada:

1 – Labirinto com saída simples
2 – Labirinto com saída complexo
3 – Labirinto sem saída
4 – Labirinto criado pelo usuário
0 – Para sair do programa

Após selecionar o labirinto desejado o modo gráfico é acionado com o mapa e o robô, pressione ENTER para iniciar a simulação.

Após o término da simulação pressione ENTER para voltar ao menu

Caso selecione a opção 4, digite o nome do arquivo do mapa. Ele será carregado e a simulação será iniciada.

Obs: Acompanha o programa um labirinto de usuário com o nome lab4.txt, é um labirinto interessante pois mostra como o robô não entra em caminhos já percorridos evitando ficar andando em círculos infinitamente.

Criando labirintos de usuário:

O labirinto de usuário deve estar no formato texto (.txt) e conter 10 linhas com 10 números cada (sem espaços). O número 1 representa um espaço bloqueado e o número 0 representa um espaço livre.

Exemplo:

0100000001

0111101101

0000101001

0111100100

0111110110

0011000100

1000011101

1110100100

0010100010

Estes arquivos podem ser criados em qualquer editor de texto que não utilize formatação (Edit do MS-DOS, Windows Notepad, etc) e devem estar sempre no mesmo diretório do programa.