INF1771 - INTELIGÊNCIA ARTIFICIAL
TRABALHO 1 – BUSCA HEURÍSTICA
Descrição:
Durante o torneio da Guerra Galáctica, os Cavaleiros de Bronze descobrem que
“
Saori é a reencarnação de Atena e que o Grande Mestre tentou matá-la ainda bebê.
Decididos a apoiar Saori, os Cavaleiros de Bronze partem para o Santuário para
enfrentar o Grande Mestre.
Ao chegar ao Santuário, Saori e os Cavaleiros são recepcionados por Tremy, um
Cavaleiro de Prata, que ataca o grupo e atinge Saori com uma flecha mortal.
Para salvar Atena, os Cavaleiros devem percorrer um caminho composto pelas 12
Casas do Zodíaco, cada uma protegida por um Cavaleiro de Ouro, e chegar à casa do
Grande Mestre, o único capaz de remover a flecha do peito de Saori. Para complicar
ainda mais, os Cavaleiros tem um prazo máximo de 12 horas para realizar essa tarefa!
O seu objetivo é ajudar Seiya, Shiryu, Hyoga, Shun e Ikki a passar pelas 12 Casas do
Zodíaco, derrotando todos os Cavaleiros de Ouro e salvando Atena o mais rápido
possível!”.
Figura 1. Os Cavaleiros de Bronze.
Figura 2. As 12 Casas do Zodíaco.
O Trabalho 1 consiste em implementar um agente capaz de guiar autonomamente Seiya,
Shiryu, Hyoga, Shun e Ikki pelas 12 Casas do Zodíaco, planejando a melhor forma de
derrotar os 12 Cavaleiros de Ouro e salvar Atena. Para isso, você deve utilizar o
algoritmo de busca heurística A*.
O agente deve ser capaz de calcular automaticamente a melhor rota para percorrer as
1
2 Casas do Zodíaco e derrotar os 12 Cavaleiros de Ouro no menor tempo possível.
O mapa das 12 Casas do Zodíaco é mostrado na Figura 3.
Figura 3. Mapa das 12 Casas do Zodíaco.
No caminho das 12 Casas do Zodíaco existem 3 tipos de terrenos: montanhoso (região
cinza escuro), plano (região cinza) e rochoso (região cinza claro).
Para passar por cada tipo de terreno, os Cavaleiros gastam uma determinada quantidade
de tempo:
•
•
•
Montanhoso: +200 minutos
Plano: +1 minuto
Rochoso: +5 minutos
Os Cavaleiros de Bronze iniciam a sua jornada na entrada do santuário (região em
vermelho no mapa) e terminam ao chegar à casa do Grande Mestre (região verde no
mapa).
Ao chegar a uma Casa do Zodíaco, o agente deve decidir quais Cavaleiros vão lutar
contra o Cavaleiro de Ouro que protege a casa. Cada Cavaleiro de Ouro apresenta um
nível de dificuldade diferente. Este nível determina o tempo gasto pelos Cavaleiros de
Bronze para pode vencê-lo e avançar para a próxima Casa.
A Tabela 1 mostra os níveis de dificuldade das 12 Casas do Zodíaco.
Casa
Dificuldade
1
2
3
4
5
6
7
8
9
1
1
1
°
°
°
°
°
°
°
°
°
Casa de Áries
Casa de Touro
Casa de Gêmeos
Casa de Câncer
Casa de Leão
Casa de Virgem
Casa de Libra
Casa de Escorpião
Casa de Sagitário
50
55
60
70
75
80
85
90
95
0° Casa de Capricórnio
1° Casa de Aquário
2° Casa de Peixes
100
110
120
Tabela 1. Níveis de dificuldade das 12 Casas do Zodíaco.
O número de Cavaleiros de Bronze participando das batalhas contra os Cavaleiros de
Ouro influência o tempo gasto na batalha. Além disso, cada Cavaleiro possui um
determinado nível de poder cósmico que também influencia no tempo gasto nas
batalhas. Quanto mais Cavaleiros lutando, mais rápido o Cavaleiro de Ouro será
derrotado.
A Tabela 2 mostra o poder cósmico dos Cavaleiros de Bronze.
Cavaleiro
Seiya
Shiryu
Hyoga
Shun
Poder Cósmico
1.5
1.4
1.3
1.2
1.1
Ikki
Tabela 2. Poder cósmico dos Cavaleiros de Bronze.
O tempo gasto nas batalhas contra os Cavaleiros de Ouro é dado por:
ꢅꢆꢇꢆꢈꢉꢊꢋꢌꢋꢁ ꢋꢌ ꢍꢌꢎꢌ
ꢀꢁꢂꢃꢄ = ∑ ꢏꢄꢋꢁꢐ ꢍꢄꢎꢂꢆꢈꢄ ꢋꢄꢎ ꢍꢌꢑꢌꢊꢁꢆꢐꢄꢎ ꢏꢌꢐꢒꢆꢈꢆꢃꢌꢓꢋꢄ ꢋꢌ ꢔꢌꢒꢌꢊℎꢌ
Além do poder cósmico, cada Cavaleiro de Bronze também possui 5 pontos de energia.
Ao participar de uma batalha, o Cavaleiro perde -1 ponto de energia. Se o Cavaleiro
perder todos os pontos de energia, ele morre.
Informações Adicionais:
•
•
•
O mapa principal deve ser representado por uma matriz 42 x 42 (igual à
mostrada na Figura 3).
O agente sempre inicia a jornada na entrada do santuário (região em vermelho
no mapa).
O agente sempre termina a sua jornada ao chegar à casa do Grande Mestre
(
região verde no mapa).
•
•
O agente não pode andar na diagonal, somente na vertical e na horizontal.
O agente obrigatoriamente deve utilizar um algoritmo de busca para encontrar
o melhor caminho e planejar as batalhas.
•
•
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.
Os mapas devem ser configuráveis, 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 dificuldade das casas e o poder cósmico dos Cavaleiros de Bronze devem
ser configuráveis e facilmente editáveis.
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:
1
2
) O membro do grupo que não comparecer receberá nota zero;
) O membro do grupo que não souber explicar algo relacionado ao
trabalho perderá 5.0 pontos.
Dicas:
•
Neste trabalho existem dois problemas distintos:
1
2
) Encontrar o melhor caminho para passar pelas 12 Casa do Zodíaco e
chegar até a Casa do Grande Mestre;
) Encontrar a melhor ordem de equipes para lutar contra os Cavaleiros de
Bronze.
•
Os dois problemas podem ser resolvidos individualmente ou tratando ambos em
um único problema. Você deve definir a melhor maneira de estruturar a sua
solução.
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 trabalho que conseguir encontrar a solução ótima no menor tempo de
execução do algoritmo de busca, receberá 1.0 ponto extra na nota. Para poder
participar da competição, o trabalho deverá implementar um mecanismo para
calcular o tempo de execução do algoritmo e deverá ser executado em Windows
(
se bibliotecas auxiliares forem usadas, todos os arquivos necessários deverão
ser incluídos no projeto para que ele possa ser executado).
Data de Entrega:
7/04
2
Forma de Entrega:
O programa deve ser apresentado na aula do dia 27/04 (segunda) e enviando até o
mesmo dia para o email edirlei.slima@gmail.com.
Trabalhos entregues atrasados perderam 1.0 ponto para cada dia de atraso.