4) { while ($ads2 == $ads1) { $ads2 = rand(1, $slides); } } $ads3 = rand(1, $slides); if ($slides > 4) { while (($ads3 == $ads2) || ($ads3 == $ads1)) { $ads3 = rand(1, $slides); } } ?>
INF1771 - INTELIGÊNCIA ARTIFICIAL  
TRABALHO 1 BUSCA HEURÍSTICA  
Descrição:  
O trabalho 1 consiste em implementar um sistema de navegação automática de um  
agente utilizando o algoritmo de busca heurística A*. O agente 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. Durante o percurso, o agente também deve  
coletar todas as recompensas existentes.  
O ambiente por onde o agente irá navegar é formado por diversos tipos de terrenos e  
em cada tipo de terreno o agente tem um grau de dificuldade diferente para andar. Por  
exemplo, o agente 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...).  
O trabalho pode ser feito individualmente ou em dupla.  
A Figura 1 ilustra o mapa do ambiente utilizado no programa base fornecido. O  
símbolo representa paredes (por onde o agente não pode passar de nenhuma  
maneira), os espaços em branco em diferentes cores representam os locais onde  
o agente pode andar (cada cor representa um tipo de terreno), o símbolo”  
representa o agente e as recompensas são representadas pelo símbolo “$”.  
O agente não pode andar na diagonal, somente na vertical e na horizontal.  
Após calcular a melhor rota, o programa deve mostrar a movimentação do  
agente 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_2012_1/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:  
(
1) A interface gráfica não é o objetivo desse trabalho, mas caso alguém implemente  
uma boa interface gráfica (2D ou 3D) para representar o ambiente e o robô  
receberá 2 pontos extras na nota.  
(
2) Para encontrar a melhor ordem para pegar as recompensas é necessário resolver  
o problema do caixeiro viajante (travelling salesman). Quem resolver esse  
problema usando um algoritmo genético receberá 2 pontos extras na nota.  
Data de Entrega:  
9/04  
0
Forma de Entrega:  
O programa deve ser apresentado na aula do dia 09/04 (segunda) e enviando até o  
mesmo dia para o email edirlei.slima@gmail.com.