INF1771 - INTELIGÊNCIA ARTIFICIAL
TRABALHO 1 – BUSCA HEURÍSTICA
Descrição:
Um vírus que transforma pessoas em zumbis está se espalhando pelo mundo. Por
“
sorte, a sua cidade ainda está segura e ninguém foi infectado. Mas isso pode mudar a
qualquer momento, por isso é necessário se preparar para o pior. A melhor maneira de
se preparar para esse apocalipse zumbi é estocando água, alimentos, armas e
munição em casa. Na sua cidade existem lojas especializadas na venda destes itens,
você deve ir até elas para comprar os itens do seu kit de sobrevivência zumbi. O tempo
está passando e é necessário estocar estes itens o mais rápido possível, por isso você
não pode perder tempo dando voltas pela cidade, você deve planejar todos os seus
passos antes mesmo de sair de casa. Tome cuidado para não perder tempo no transito.
Boa sorte!”
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
1
2
3
4
5
6
7
8
9
☺
A
F
1
0
1
2
3
4
5
6
7
8
9
0
1
1
1
1
1
1
1
1
1
2
W
G
Figura 1. Mapa da Cidade.
O Trabalho 1 consiste em implementar um agente capaz de locomover-se por essa
cidade e comprar os itens buscados 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 comprar
água, alimentos, armas, munição e, por ultimo, voltar para casa (posição [3,3] no
mapa).
Infelizmente você não é o único que está tentando comprar suprimentos para sobreviver
ao apocalipse zumbi. Todos os moradores da cidade estão fazendo o mesmo. Com isso,
o transito da cidade está caótico. Por sorte, o boletim de transito continua sendo
atualizado, o que permite ao agente planejar uma rota que evite perder muito tempo no
transito.
Existem 5 níveis de congestionamento:
•
•
•
•
•
Nível 1 – Tempo Gasto: +3 min
Nível 2 – Tempo Gasto: +8 min
Nível 3 – Tempo Gasto: +14 min
Nível 4 – Tempo Gasto: +20 min
Nível 5 – Tempo Gasto: +30 min
A melhor rota é aquela na qual o agente leva menos tempo para comprar os itens do kit
de sobrevivência zumbi.
Informações Adicionais:
•
A cidade deve ser representada por uma matriz 20 x 20 (igual à mostrada na
Figura 1).
•
•
•
O agente sempre inicia e termina a jornada na casa dele (posição [3, 3]).
O agente não pode andar na diagonal, somente na vertical e na horizontal.
A cidade deve possuir a estrutura de ruas ilustrada na Figura 1. As lojas são
representadas pelas seguintes letras:
o W – Loja de Água
o F – Loja de Alimentos
o G – Loja de Armas
o A – Loja de Munição
•
O mapa da cidade deve ser configurável, ou seja, deve ser possível modificar
as ruas e a posição das lojas. O mapa pode ser lido de um arquivo de texto ou
deve ser facilmente editável no código.
•
•
Todas as ruas do mapa possuem um nível de congestionamento. Essa
informação também deve ser configurável no mapa.
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 algoritmo deve ser capaz de perceber quando não existe nenhum caminho
para chegar ao destino. Exemplo: estar preso em uma rua sem saída.
O programa também deve exibir o tempo gasto pelo agente enquanto ele se
movimenta pela cidade.
•
•
O trabalho pode ser feito individualmente ou em dupla.
O programa pode ser implementado em qualquer linguagem.
Programa Base (Projeto do Visual Studio 2010):
https://edirlei.com/aulas/ia_2012_2/Trabalho1ProgramaBase_2012_2.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á 2 pontos extras na nota.
(
2) Para encontrar a melhor ordem para pegar os itens do kit de sobrevivência zumbi
é necessário resolver o problema do caixeiro viajante (travelling salesman).
Quem resolver esse problema usando um algoritmo genético receberá 1 ponto
extra na nota.
Data de Entrega:
9/09
1
Forma de Entrega:
O programa deve ser apresentado na aula do dia 19/09 (quarta) e enviando até o mesmo
dia para o email edirlei.slima@gmail.com.