Enunciado
Desafio de navegação autônoma
Durante as aulas de computação, vimos a importância do uso de algoritmos de grafos para a solução de problemas de busca. Para esta atividade, você precisará aplicar esse conhecimento em um desafio de navegação de labirinto.
O desafio se divide em duas partes:
A parte 1 consiste em navegação com mapa — tendo acesso ao mapa, você deverá desenvolver um algoritmo para encontrar a rota otimizada até o alvo.
A parte 2 envolve o mapeamento do labirinto. O algoritmo desenvolvido deve navegar pelo mapa, mapeando-o no processo. A seguir, deve-se comprovar que o mapa criado é suficiente para reproduzir a rota da parte 1.
O simulador
Para esta atividade, você deve utilizar um pacote ROS. Neste pacote, você vai encontrar um simulador de labirinto feito em pygame em que você poderá interagir com um "robô".
O labirinto em si trata-se de um grid — ou seja, uma matriz de células de tamanho igual — dividido nos seguintes elementos:
- AZUL representa o robô que deve ser movimentado;
- VERMELHO o alvo a ser encontrado pelo robô;
- BRANCO representa espaços vazios por onde o robô pode passar;
- PRETO representa espaços ocupados, por onde o robô não pode passar;
Interagindo com o simulador
As instruções para instalar e interagir com o simulador estão no repositório anexado.
Regras de entrega
A entrega desta atividade deve ser feita em um repositório do github. Nele, é obrigatório:
- Um README com a explicação do projeto e como utilizá-lo.
- Um vídeo com uma demonstração dos algoritmos e uma explicação de como eles funcionam.
- O código dos dois algoritmos. O código não pode ser feito em uma linguagem com garbage collector. Sugere-se o uso de C++. A interação com o labirinto deve obrigatoriamente ser feita utilizando os serviços e tópico ROS.
Caso qualquer das regras acima não seja cumprida, a atividade será considerada como não entregue.
Forma de avaliação
Arguição
Esta atividade será avaliada por uma demonstração seguida de arguição.
O roteiro de avaliação será:
- Demonstrar o funcionamento dos dois algoritmos com um labirinto aleatório gerado na hora; e
- Uma série de perguntas técnicas de implementação feitas com base na entrega do repositório.
Está apresentação será feita com horário agendado e terá duração de 10 minutos.
Composição da nota
A implementação da parte 1 vale até 5 pontos.
A implementação da parte 2 vale até 5 pontos.
A nota da arguição irá variar 0 a 1 e será um fator multiplicador na nota de implementação. E.g.: se você implementou as duas partes corretamente, parte de uma nota 10 de implementação. Caso sua arguição receba nota 0.6, a sua nota final será 6.
Para a arguição, o que será julgado é:
- Domínio das ferramentas; 1.1. ENTENDER os conceitos de alocação dinâmica e ponteiros inteligentes; 1.2. AVALIAR quando se deve utilizar cada tipo de ponteiro; 1.3. ENTENDER as ferramentas básicas de ROS;
- Domínio dos algoritmos utilizados; 2.1. ENTENDER e ANALISAR a forma de representação escolhida para o grafo do labirinto; 2.2. ENTENDER e ANALISAR os algoritmos de travessia básicos e o que os difere; 2.3. ENTENDER e ANALISAR os algoritmos de busca disponíveis e explicar adequadamente a sua escolha; 2.4. AVALIAR o algoritmo de mapeamento encontrado/criado com relação às suas principais limitações (caso haja alguma);