INF1771 - INTELIGÊNCIA ARTIFICIAL
TRABALHO 1 – BUSCA HEURÍSTICA
Descrição:
Para se tornar um Mestre Pokémon é necessário aventurar-se por terras
“
desconhecidas, capturar novos pokémons, treina-los e derrotar os Lideres de Ginásios
em batalhas pokémon para demonstrar as suas habilidades de treinador.
Ao vencer o líder do ginásio de uma cidade, o treinador pokémon recebe uma Insígnia.
Após derrotar todos os líderes de ginásio de um continente, conquistando suas
respectivas insígnias, o treinador pode participar da Liga Pokémon deste continente.
A sua aventura como treinador pokémon inicia-se no Continente de Kanto. Para entrar
para a Liga Pokémon de Kanto você deve derrotar os 8 lideres dos ginásios do
continente e ganhar as 8 Insígnias de Kanto.
Para poder acessar os ginásios e derrotar os lideres você deve capturar pokémons
durante a sua jornada. Lembre-se de utilizar a sua Pokédex para localizar e identificar
os pokémons.”
Figura 1. Insígnias de Kanto.
Figura 2. Pokédex.
O Trabalho 1 consiste em implementar um agente capaz de locomover-se pelo
continente, capturar os pokémons necessários para acessar os ginásios e ganhar as 8
insígnias 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 reunir as 8
Insígnias de Kanto.
O mapa do continente é mostrado na Figura 3.
Figura 3. Mapa do continente de Kanto.
O continente é formado por 5 tipos de terrenos: grama (região verde), água (região
azul), montanha (região marrom), caverna (região cinza) e vulcão (região laranja).
Os custos para passar por cada tipo de terreno são os seguintes:
•
•
•
•
•
Grama – Custo: +10
Água – Custo: +100
Caverna – Custo: +120
Montanha – Custo: +120
Vulcão – Custo: +150
Ao capturar determinados tipos de pokémons se torna mais fácil passar em alguns tipos
de terrenos:
•
•
•
•
Água usando um pokémon de água – Custo: +10
Caverna usando um pokémon elétrico – Custo: +12
Montanha usando um pokémon que voa – Custo: +12
Vulcão usando um pokémon de fogo – Custo: +15
A melhor rota para ganhar as 8 insígnias é a rota de menor custo levando em
consideração o terreno.
A localização dos ginásios e as suas respectivas insígnias estão definidas na Figura 3.
Existem 5 tipos de pokémons espalhados pelo continente (Grama, Fogo, Elétrico, Água
e Ar). A posição inicial dos pokémons é desconhecida. O agente deve utilizar o radar
da pokédex para localiza-los. O radar possui um alcance máximo de 4 regiões
adjacentes em todas as direções. A Figura 4 ilustra o alcance máximo do radar
considerando que o agente está localizado na posição marcada em vermelho.
Figura 4. Alcance máximo do radar de pokémons.
Informações Adicionais:
•
O planeta deve ser representado por uma matriz 42 x 42 (igual à mostrada na
Figura 3).
•
O agente sempre inicia a jornada no laboratório do Professor Carvalho (ponto
onde está o personagem no mapa).
•
•
O agente não pode andar na diagonal, somente na vertical e na horizontal.
Inicialmente as posições dos pokémons 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 os pokémons usando o radar da
pokédex.
•
•
A pokédex é capaz de identificar o tipo de pokémon quando ele entra no
alcance do radar.
Caso mais de um pokémon apareça no radar da pokédex, você deve calcular
o melhor caminho e a melhor ordem para capturar os pokémons visíveis que
desejar.
•
O total de cada tipo de pokémon é o seguinte:
o 20 pokémons de grama;
o 10 pokémons de água;
o 8 pokémons de ar;
o 6 pokémons de fogo;
o 4 pokémons elétricos;
•
•
•
•
•
Os pokémons sempre estão em locais de grama. Ao sortear a posição inicial
dos pokémons, o programa deve garantir que eles sempre estejam em regiões de
grama.
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.
A única forma de garantir o caminho de menor custo possível é resolvendo
várias vezes o problema do Caixeiro Viajante (Travelling Salesman) para
selecionar a melhor ordem para visitar os ginásios e capturar os pokémons.
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:
•
Neste trabalho existem 2 problemas distintos:
o (1) Capturar os pokémons;
o (2) Encontrar o melhor caminho para chegar aos ginásios e ganhar as
insígnias;
•
Para resolver o primeiro problema é aconselhável dividir o processo de busca em
duas etapas:
o (1) Exploração do mapa: O agente deve explorar o mapa até que o
radar da pokédex localize um pokémon.
o (2) Capturar o pokémon: Uma vez que um pokémon for localizado, o
agente deve executar o algoritmo de busca A* para encontrar a rota de
menor custo para chegar até o pokémon 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 da
pokédex. Durante a execução do programa você deve executar o algoritmo de
busca A* para encontrar o melhor caminho para navegar por esses pontos até
encontrar os pokémons necessários.
Note também que alguns ginásios podem ser acessados facilmente sem a ajuda
de um pokémon e outros podem ser acessados antes de capturar todos os tipos
de pokémons. Planeje bem a sua estratégia de exploração do mapa para ir
ganhando as insígnias ao mesmo tempo em que você captura os pokémons
necessários para acessar os outros ginásios.
Programa Base (Projeto do Visual Studio 2010):
http://edirlei.3dgb.com.br/aulas/ia_2013_2/Trabalho1ProgramaBase_2013_2.zip
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;
4) O trabalho foi apresentado corretamente em sala de aula;
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 8 insígnias com o menor custo, dado
uma determinada configuração de posições de pokémons, receberá 2 pontos
extras na nota. Para participar dessa competição é necessário que o programa
inclua uma forma simples de definir manualmente a posição dos pokémons. Em
caso de empate, ambos os trabalhos receberão a nota extra.
(
3) O trabalho que implementar corretamente a resolução do problema do Caixeiro
Viajante (Travelling Salesman) usando algoritmos genéticos receberá 1 ponto
extra na nota.
Data de Entrega:
0/09
3
Forma de Entrega:
O programa deve ser apresentado na aula do dia 30/09 (segunda) e enviando até o
mesmo dia para o email edirlei.slima@gmail.com.
Trabalhos entregues atrasados perderam 0.5 pontos para cada dia de atraso.