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:  
Durante o uma complicada batalha no 21º torneio de artes marciais, Kuririn acabou  
sendo morto pelo seu adversário. Agora a única esperança que Goku tem de algum dia  
voltar a ver o seu grande amigo é reunindo as 7 Esferas do Dragão e revivendo  
Kuririn.  
As esferas do dragão são artefatos mágicos que podem realizar qualquer desejo de  
quem as reunir. Quando as 7 esferas são reunidas é possível invocar o deus dragão  
Shenlong e fazer qualquer pedido. As esferas estão espalhadas pelo planeta terra, a  
única maneira de localiza-las é através de um dispositivo chamado Radar do Dragão.  
O radar do dragão é capaz de localizar a posição de cada esfera. Mas infelizmente o  
radar possui um alcance máximo, dessa forma, somente é possível localizar as esferas  
que estejam próximas.  
Usando o radar, você deve reunir as esferas do dragão o mais rápido possível!”  
Figura 1. Esferas do dragão.  
Figura 2. Radar do dragão.  
O Trabalho 1 consiste em implementar um agente capaz de locomover-se pelo planeta e  
reunir as 7 esferas do dragão de forma inteligente. Para isso, você deve utilizar o  
algoritmo de busca heurística A*.  
O agente deve ser capaz de calcular automaticamente a melhor rota para encontrar as  
7
esferas do dragão e, por ultimo, voltar para a Ilha do Mestre Kame (ponto vermelho  
no mapa).  
O mapa do planeta é mostrado na Figura 3.  
Figura 3. Mapa da Planeta.  
O planeta é formado por 3 tipos de terrenos: água (região azul), grama (região verde) e  
montanha (região marrom).  
Os custos para passar por cada tipo de terreno são os seguintes:  
Água Custo: +10  
Grama Custo: +1  
Montanha Custo: +60  
A melhor rota para reunir as esferas do dragão é a rota de menor custo levando em  
consideração o terreno.  
O radar do dragão possui um alcance máximo de 3 regiões adjacentes em todas as  
direções. A Figura 4 ilustra o alcance máximo do radar do dragão considerando que o  
agente está localizado na posição marcada em vermelho.  
Figura 4. Alcance máximo do radar do dragão.  
Informações Adicionais:  
O planeta deve ser representado por uma matriz 42 x 42 (igual à mostrada na  
Figura 3).  
O agente sempre inicia e termina a jornada na Ilha do Mestre Kame (ponto  
vermelho no mapa)  
O agente não pode andar na diagonal, somente na vertical e na horizontal.  
Inicialmente as posições das esferas do dragão são desconhecidas. O programa  
deve sortear as posições durante a inicialização, mas o agente não pode ter  
acesso a essa informação diretamente. Ele deve localizar as esferas usando o  
radar do dragão.  
Deve existir uma maneira de visualizar os movimentos do agente, mesmo que a  
interface seja bem simples. Podendo até mesmo ser uma matriz desenhada e  
atualizada no console.  
O mapa do planeta deve ser configurável, ou seja, deve ser possível modificar  
o tipo de terreno em cada local. O mapa pode ser lido de um arquivo de texto ou  
deve ser facilmente editável no código.  
O programa deve exibir o custo do caminho percorrido pelo agente enquanto  
ele se movimenta pelo mapa e também o custo final ao terminar a execução.  
O programa pode ser implementado em qualquer linguagem.  
O trabalho pode ser feito individualmente ou em grupos de no máximo 3  
pessoas.  
O programa deve ser apresentado durante a aula por todos os membros do  
grupo. Se algum dos membros do grupo não comparecer ou não souber explicar  
nada sobre a implementação receberá nota zero.  
Dicas:  
Divida o processo de busca em duas etapas:  
o (1) Exploração do mapa: O agente deve explorar o mapa até que o  
radar do dragão localize uma das esferas do dragão.  
o (2) Coleta da esfera do dragão: Uma vez que a esfera for localizada, o  
agente deve executar o algoritmo de busca A* para encontrar a rota de  
menor custo para chegar até a esfera partindo da sua posição atual.  
A maneira mais simples de realizar a exploração do mapa é definindo um  
conjunto de pontos, dos quais seja possível rastrear todo o mapa com o radar do  
dragão. Durante a execução do programa você deve executar o algoritmo de  
busca para encontrar o melhor caminho para navegar por esses pontos.  
Caso mais de uma esfera do dragão apareça no radar, você deve calcular o  
melhor caminho e a melhor ordem para pegar todas as esferas visíveis.  
Programa Base (Projeto do Visual Studio 2010):  
https://edirlei.com/aulas/ia_2013_1/Trabalho1ProgramaBase_2013_1.rar  
Forma de Avaliação:  
Será avaliado se:  
(
(
(
1) O trabalho atendeu a todos os requisitos especificados anteriormente;  
2) Os algoritmos foram implementados e aplicados de forma correta;  
3) O código foi devidamente organizado;  
Bônus:  
(
1) A interface gráfica não é o objetivo desse trabalho, mas quem implementar uma  
boainterface gráfica (2D ou 3D) para representar o ambiente e o agente  
receberá até 2 pontos extras na nota.  
(
2) O programa que conseguir coletar todas as 7 esferas do dragão com o menor  
custo, dado uma determinada configuração de posições das esferas, receberá 1  
ponto extra na nota. Para participar dessa competição é necessário que o  
programa inclua uma forma simples de definir manualmente a posição das  
esferas do dragão. Em caso de empate, ambos os trabalhos receberão a nota  
extra.  
Data de Entrega:  
2/04  
2
Forma de Entrega:  
O programa deve ser apresentado na aula do dia 22/04 (segunda) e enviando até o  
mesmo dia para o email edirlei.slima@gmail.com.