7.8. Trabajo de prácticas: Resolución de un laberinto

7.8.1. Objetivo

En este trabajo se desarrollará un sistema que resolverá laberintos. Debe crearse una estrategía básica e implementar la máquina de estados correspondiente. El laberinto se presentará en una pantalla VGA.

El trabajo se realizará individualmente.

7.8.2. Introducción

Considere una hormiga robot cuyas patas están controladas por servomotores y que dispone de dos antenas unidas a la parte frontal del robot (sensor_L y sensor_R) actúan como sensores para indicar posibles contactos con las diferentes secciones de las paredes de un laberinto. Los servomotores conectados a las ruedas del robot, le permiten tres movimientos:

  1. Hacia delante, salida front = 1 (avanza).

  2. Rotación de 90o a la derecha, salida gd = 1 (no avanza, solo gira).

  3. Rotación de 90o a la izquierda, salida gi = 1 (no avanza, solo gira).

Si las salidas son todas “0”, indica que el robot no se mueve. En un instante determinado solo una de las salidas puede ser “1”.

7.8.2.1. Laberintos

Un laberinto típico es el que se muestra en la Figura 7.34. Como se oberva en la posición que se encuentra la hormiga el sensor_L está detectando un “0” y el sensor_R está detectando un “1”. En el laberinto se consideran cuatro direcciones, refeidas a la posicion que se muestra en la Figura 7.34:

  1. norte: hacia abajo.

  2. sur: hacia arriba.

  3. oeste: hacias la derecha.

  4. este: hacia la izquierda.

Cada posición del laberinto está indicado por dos coordenadas x e y. La x es horizontal (de 0 hasta 18, 19 columnas) y la y es vertical (de 0 hasta 15, 16 filas).

../../_images/laberinto_tipico.png

Figura 7.34 Representación de un laberinto típico.

Posteriormente se usarán hasta 4 laberintos, que se almacenarán en una memoria ROM con doble puerto de lectura (ver Listado 7.27).

7.8.2.2. Modo de funcionamiento

Como se observa en la Figura 7.34 la hormiga ocupa una cuadricula. Inicialmente está en la cuadrícula [1,1] y con sus antenas sensor_L y sensor_R detecta las cuadrículas que están delante a la derecha (R) y delante a la izquierda (L). Si una de sus antenas detecta una pared, la señal de entrada pasará a “1” y permanecerá a “0” si no lo hace. Por ejemplo, en la posición inicial de la figura sensor_R = “1” y sensor_L =”0”. La salida del laberinto será reconocida por la hormiga por una nueva entrada al autómata (denominada fin) que siempre permanecerá a “0”, excepto cuando se llegué a la salida del laberinto que se pondrá a “1”, con lo cual la hormiga robot se detendrá.

7.8.3. Trabajo previo

Establecer una estrategia para que la hormiga llegue a la salida del laberinto. Por ejemplo, suponer que la hormiga robot avanza (front = 1) tratando de mantenerse cerca de la pared a su derecha (sensor_R = “1” y sensor_L = “0”), y que podrá girar a la izquierda (gi = 1) o a la derecha (gd = 1), según se encuentre con una pared enfrente (sensor_R = “1” y sensor_L = “1”) o con un pasillo (sensor_R = “0”). Todos los pasillos son lo suficientemente anchos para que en ellos solo R sea igual “1” y sensor_L = “0”. La hormiga nunca deberá encontrarse en una cuadricula marcada con un “1”, que representan las paredes del laberinto.

Crear un estado inicial en el que todas las salidas estén a nivel lógico “0” y una vez que se ponga la hormiga robot en la posición indicada en la figura (sensor_R = “1”, detectando la pared de la derecha) deberá ponerse en movimiento, siempre y cuando la señal fin sea igual a “0”. En cualquier estado, si la señal fin se pone a “1”, significa que el laberinto se ha resuelto, y se debe volver al estado inicial.

En definitiva, la hormiga robot tendrá la siguiente interfaz (ver entidad descrita en VHDL en Listado 7.28:

– entradas:

  • señales de las antenas izquierda y derecha, sensor_L y sensor_R, configuradas en 1 siempre que haya contacto con una sección de pared;

  • Señal fin que se pondrá a “1” cuando la hormiga complete el laberinto correctamente.

– salidas: señales de control que se utilizan para iniciar un movimiento hacia:

  • avanza (front).

  • rotación de 90^o a la derecha (gd).

  • rotación de 90^o a la izquierda (gi).

Realizar el VPL (Virtual programming Laboratory) que está en el Campus Virtual de la asignatura. Información de mensajes de VPL:

  1. Posición.

    1. La posición se marcará por los índices de posición i, j.

    2. El i aumenta según la dirección del eje x (horizontal, aumenta hacia la derecha) y la j según la dirección del eje y (vertical, aumenta hacia abajo).

    3. La i está comprendida entre 0 y 18 y la j entre 0 y 15.

  2. Sentidos:

    1. Norte: hacia abajo (j crecientes).

    2. Sur: hacia arriba (j decrecientes).

    3. Oeste: hacia la derecha (i crecientes).

    4. Este: hacia la izquierda (i decrecientes).

  3. Mensajes del VPL:

    1. Test:

      1. Testing 1/5 : hormiga-robot ha salido con éxito.

      2. Testing 2/5 : hormiga-robot ha realizado el primer giro.

      3. Testing 3/5 : hormiga-robot ha realizado el segundo giro.

      4. Testing 4/5 : hormiga-robot ha realizado el tercer giro.

      5. Testing 5/5 : hormiga-robot ha terminado con éxito.

    2. Reports:

      1. Error: hormiga sobre paredes o fuera de límites.

      2. Primer giro realizado correctamente.

      3. Segundo giro realizado correctamente.

      4. Hormiga-robot cerca de la salida.

      5. Succesfull trayectory. Problem solved.

      6. End of test with no solution.

    3. En la ventana de compilación se da la siguiente información

      1. Número de iteración, índice i-índice j.

      2. Sensores LR = L-R.

      3. Sentido: norte (índice j creciente), sur (índice j decreciente), oeste (índice i creciente), este (índice i decreciente) y acción (hormiga avanza, parada, giro a izquierda y giro a derecha).

7.8.4. Trabajo en el laboratorio

Para realizar el trabajo en el laboratorio se necesitan los siguientes ficheros VHDL que se proporcionan en el Campus Virtual.

  1. Control de la pantalla VGA.

    1. Controlador de VGA: vga_controller.vhd.

    2. Contador (nru_counter) que divide la señal de 50 MHz hasta conseguir los 25.175 MHz requeridos por la pantalla: counter.vhd.

    3. Función utis.vhd que calcula el tamaño de los registros en función de la resolución de la pantalla.

    4. PLL para obtener la frecuancia exacta de la pantalla (pll.vhd).

  2. Formas de la hormiga.

    1. La hormiga se presentará en la pantalla simplemente como un cuadrado que tiene una flecha indicando el sentido de su marcha.

  3. Para utilizar los displays de 7 segmentos se necesitarán:

    1. Convertir un número binario en BDC: bynary_to_BCD.vhd y binary_to_bcd_digit.vhd.

    2. Representar un BCD en un display 7 segmentos: BCD_7segment.vhd.

7.8.4.1. Diagrama general

El diagrama general del sistema será tal como representa la Figura 7.35. De este diagrama la descripción VHDL de los diferentes bloques se encuentra en el Campus Virtual de la Asignatura.

../../_images/Diagrama_general.png

Figura 7.35 Diagrama general del diseño.

7.8.4.2. Representación de información en la DE10-Lite

Una vez programada la tarjeta DE10-Lite con nuestro diseño de la hormiga robot, la interfaz se muestra en la Figura 7.36. Los switches se utilizan para introducir la posición inicial de la hormiga y para seleccionar el laberinto. Mientras que la entrada start, que da inicio a la resolución del laberinto estará conectada a uno de los botones de la tarjeta. El otro botón hará las veces de reset del sistema.

../../_images/hormigarobot_pinout.png

Figura 7.36 Pin out del trabajo de la hormiga robot.

Nota

En esta primera parte del trabajo la hormiga siempre debe partir de la posición [1, 1], lo cual debe establecerse con los switches (interruptores) pos_x_inicial y pos_y_inicial.

7.8.5. Mejoras del sistema diseñado

7.8.5.1. Control del punto de partida

En este apartado se mejorará la máquina de estados para que la hormiga pueda partir desde cualquier posición (siempre en dirección norte) y resolverá el laberinto. Debe ternerse en cuenta que la posición inicial no debe estar nunca sobre el muro del laberinto.

7.8.5.2. Modificación del dibujo de la hormiga

Modificar el contenido de la memoria rom_hormiga.vhd para representar la hormiga de forma más realista. la hormiga es ocupa un cuadrado de 32 píxeles en x y 30 píxeles en y. Habría que hacer 4 versiones según la dirección que toma la hormiga.

7.8.5.3. Movimiento continuo de la hormiga

Cuando la hormiga avanza (front = “1”) la hormiga de una posición a otra dando saltos. En este apartado se modificará el controlador de VGA para que la hormiga se desplace de manera continua. Para ello se debe modificar el fichero vga_controller.vhd. Hay que tener en cuenta que en cada desplazamiento de la hormiga la pantalla se refresca unas 30 veces (seún lo indicado por el contador U1 en el Listado %s. Dado que la pantalla tiene una resolución de 640x480 píxeles y el laberinto es una cuadícula de 19x16 posiciones, la hormiga es ocupa un cuadrado de 32 píxeles en x y 30 píxeles en y. Por tanto el avance de una posición se puede realizar desplazando la hormiga píxel a píxel en cada una de las 30 pantallas en las que se representa el avance de la hormiga.

7.8.6. Entregables

7.8.6.1. Trabajo previo

Por hacer

ET7.1. Memoria de trabajo incluyendo el grafo de estados de la solución propuesta.

ET7.2. Resolución laboratorio virtual (VPL) en el Campus Virtual.

7.8.6.2. Trabajo práctico

Por hacer

ET7.3. Implementación en el laboratorio de la primera versión de la hormiga (parte desde la posición [1,1].

ET7.4. Memoria de trabajo incluyendo el grafo de estados de la solución propuesta en el cual la hormiga pueda partir de cualquier posición.

ET7.5. Implementación en el laboratorio de la versión definitiva de la hormiga en la tarjeta DE10-Lite.

7.8.7. Listados VHDL

Lista 7.27 Código VHDL de una memoria ROM con los laberintos (dual_port_rom.vhd)
-- Ver en el campus Virtual de la Asignatura
Lista 7.28 ENTITY del hormiga_robot.vhd.
 entity hormiga_robot is
     port(
       rstn   : in std_logic;
       clock  :in std_logic;
       l_in   :in std_logic;
       r_in   :in std_logic;
       fin_in :in std_logic;
       f_out  :out std_logic;
       gi_out :out std_logic;
       gd_out :out std_logic);
 end entity;
Lista 7.29 Contador divisor del reloj de la hormiga (contador_reloj.vhd)
-- Ver en el campus Virtual de la Asignatura
Lista 7.30 Interfaz de la hormiga con los elementos de la DE10-Lite (TrabajoPR7.vhd).
-- Ver en el campus Virtual de la Asignatura