INF1771 - INTELIGÊNCIA ARTIFICIAL
TRABALHO 1 – BUSCA HEURÍSTICA
Descrição:
O trabalho consiste em implementar um sistema de navegação automática de um robô
utilizando o algoritmo de busca heurística A*. O robô 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.
O ambiente por onde o robô vai navegar é formado por diversos tipos de terrenos e em
cada tipo de terreno o robô tem um grau de dificuldade diferente para andar. Por
exemplo, o robô 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...).
A Figura 1 ilustra o mapa do ambiente utilizado no programa base fornecido. A
letra “X” representa paredes (por onde o robô não pode passar de nenhuma
maneira), o espaço em branco “ ” representa os locais onde o robô pode andar, e
o símbolo “@” representa o robô.
•
•
O robô pode andar somente na vertical e na horizontal.
Após calcular a melhor rota, o programa deve mostrar a movimentação do robô
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_2011_2/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:
A interface gráfica não é o objetivo desse trabalho, mas caso alguém implemente uma
ótima interface gráfica para representar o ambiente e o robô receberá 2 pontos extras na
nota. Podendo tirar até 12 no trabalho.
Data de Entrega:
0
5/09
Forma de Entrega:
O programa deve ser apresentado na aula do dia 05/09 (segunda) e enviando até o
mesmo dia para o email edirlei.slima@gmail.com.