INF1771 - INTELIGÊNCIA ARTIFICIAL
TRABALHO 1 – BUSCA HEURÍSTICA
Descrição:
O trabalho 1 consiste em implementar um sistema de navegação automática de um
agente utilizando o algoritmo de busca heurística A*. O agente deve ser capaz de
calcular automaticamente a melhor rota para chegar a qualquer ponto de um ambiente
representado através de uma matriz n x n. Durante o percurso, o agente também deve
coletar todas as recompensas existentes.
O ambiente por onde o agente irá navegar é formado por diversos tipos de terrenos e
em cada tipo de terreno o agente tem um grau de dificuldade diferente para andar. Por
exemplo, o agente consegue passar facilmente por um terreno solido e plano, porem terá
dificuldade para andar em um terreno rochoso ou um pântano.
Os tipos de terrenos que compõem o ambiente são:
•
•
•
•
Solido e plano – Custo: +1
Rochoso – Custo: +10
Arenosos– Custo: +4
Pântano – Custo: +20
A melhor rota para chegar a um determinado ponto do ambiente é a rota que tem o
menor custo.
Informações Adicionais:
•
O programa fornecido possui a base para o desenvolvimento do trabalho, mas
quem preferir pode criar uma nova implementação em qualquer linguagem (C,
C++, C#, Java...).
•
•
O trabalho pode ser feito individualmente ou em dupla.
A Figura 1 ilustra o mapa do ambiente utilizado no programa base fornecido. O
símbolo “▓” representa paredes (por onde o agente não pode passar de nenhuma
maneira), os espaços em branco em diferentes cores representam os locais onde
o agente pode andar (cada cor representa um tipo de terreno), o símbolo “☺”
representa o agente e as recompensas são representadas pelo símbolo “$”.
•
O agente não pode andar na diagonal, somente na vertical e na horizontal.
•
Após calcular a melhor rota, o programa deve mostrar a movimentação do
agente seguindo a rota calcula. O programa fornecido implementa uma
ilustração bem simples de como a movimentação pode ser realizada.
•
•
O algoritmo deve ser capaz de perceber quando não existe nenhum caminho para
chegar ao destino. Exemplo: uma sala que não possui nenhuma entrada.
A melhor maneira de começar o trabalho é pensando a função heurística que
será utilizada pelo algoritmo A*.
Figura 1: Exemplo de mapa do ambiente.
Programa Base (Projeto do Visual Studio 2010):
https://edirlei.com/aulas/ia_2012_1/Trabalho1ProgramaBase.zip
Forma de Avaliação:
Será avaliado se o trabalho atendeu a todos os requisitos especificados anteriormente. O
trabalho que atender a todos os requisitos receberá nota 10.
Bônus:
(
1) A interface gráfica não é o objetivo desse trabalho, mas caso alguém implemente
uma boa interface gráfica (2D ou 3D) para representar o ambiente e o robô
receberá 2 pontos extras na nota.
(
2) Para encontrar a melhor ordem para pegar as recompensas é necessário resolver
o problema do caixeiro viajante (travelling salesman). Quem resolver esse
problema usando um algoritmo genético receberá 2 pontos extras na nota.
Data de Entrega:
9/04
0
Forma de Entrega:
O programa deve ser apresentado na aula do dia 09/04 (segunda) e enviando até o
mesmo dia para o email edirlei.slima@gmail.com.