Fabricio Breve - Página Pessoal
Português Português   English English
www.fabriciobreve.com
         
Informações Gerais
Publicações
Currículo Lattes
Trabalhos Acadêmicos
Softwares
Links
Links
Análise de Sinais e Sistemas (UFSCar)
Teoria da Computação (EEP)
PHP (SENAC)
Banco de Dados I (FSL)
Redes de Computadores (FSL)
Laboratório de Programação (FSL)
Laboratório de Redes de Computadores e Sistemas Operacionais (FSL)
Sistemas Orientados a Objetos (UNESP)
Análise de Sistemas (UNESP)
Tópicos: Computação Avançada (UNESP)
Organização de Computadores (UNESP)
Redes de Computadores (UNESP)
Sistemas Operacionais II (UNESP)
Computação Inspirada pela Natureza (UNESP)

Google Scholar ORCID iD icon
 

NOTICE: This page is no longer mantained. Please check the new home page.

Universidade Metodista de Piracicaba

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Trabalho de Inteligência Artificial

LABIRINTO

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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é 299 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

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.

 
eXTReMe Tracker

"Ainda não compreendeis que tudo o que entra pela boca desce para o ventre, e é lançado fora?" (Mt 15:17)

Webdesigner: Fabricio Breve 1997 - 2003
[email protected] - Privacidade