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
“boa” interface 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.