INF1771 - INTELIGÊNCIA ARTIFICIAL  
TRABALHO 1 BUSCA HEURÍSTICA  
Descrição:  
O trabalho consiste em implementar um sistema de navegação automática de um robô  
utilizando o algoritmo de busca heurística A*. O robô deve ser capaz de calcular  
automaticamente a melhor rota para chegar a qualquer ponto de um ambiente  
representado através de uma matriz n x n.  
O ambiente por onde o robô vai navegar é formado por diversos tipos de terrenos e em  
cada tipo de terreno o robô tem um grau de dificuldade diferente para andar. Por  
exemplo, o robô consegue passar facilmente por um terreno solido e plano, porem terá  
dificuldade para andar em um terreno rochoso ou um pântano.  
Os tipos de terrenos que compõem o ambiente são:  
Solido e plano Custo: 1  
Rochoso Custo: 10  
ArenososCusto: 4  
Pântano Custo: 20  
A melhor rota para chegar a um determinado ponto do ambiente é a rota que tem o  
menor custo.  
Informações Adicionais:  
O programa fornecido possui a base para o desenvolvimento do trabalho, mas  
quem preferir pode criar uma nova implementação em qualquer linguagem (C,  
C++, C#, Java...).  
A Figura 1 ilustra o mapa do ambiente utilizado no programa base fornecido. A  
letra “X” representa paredes (por onde o robô não pode passar de nenhuma  
maneira), o espaço em branco “ representa os locais onde o robô pode andar, e  
o símbolo “@” representa o robô.  
O robô pode andar somente na vertical e na horizontal.  
Após calcular a melhor rota, o programa deve mostrar a movimentação do robô  
seguindo a rota calcula. O programa fornecido implementa uma ilustração bem  
simples de como a movimentação pode ser realizada.  
O algoritmo deve ser capaz de perceber quando não existe nenhum caminho para  
chegar ao destino. Exemplo: uma sala que não possui nenhuma entrada.  
A melhor maneira de começar o trabalho é pensando a função heurística que  
será utilizada pelo algoritmo A*.  
Figura 1: Exemplo de mapa do ambiente.  
Programa Base (Projeto do Visual Studio 2010):  
https://edirlei.com/aulas/ia_2011_2/Trabalho1ProgramaBase.zip  
Forma de Avaliação:  
Será avaliado se o trabalho atendeu a todos os requisitos especificados anteriormente. O  
trabalho que atender a todos os requisitos receberá nota 10.  
Bônus:  
A interface gráfica não é o objetivo desse trabalho, mas caso alguém implemente uma  
ótima interface gráfica para representar o ambiente e o robô receberá 2 pontos extras na  
nota. Podendo tirar até 12 no trabalho.  
Data de Entrega:  
0
5/09  
Forma de Entrega:  
O programa deve ser apresentado na aula do dia 05/09 (segunda) e enviando até o  
mesmo dia para o email edirlei.slima@gmail.com.