Práctica

El Escape Inteligente

Implementación del Algoritmo A* en Laberintos

El escape inteligente

En el campo de la Inteligencia Artificial y el desarrollo de videojuegos, la navegación eficiente de un punto a otro es un desafío fundamental. Los algoritmos de búsqueda ciega suelen ser ineficientes al explorar rutas innecesarias. Aquí es donde intervienen las heurísticas: estimaciones matemáticas que guían al algoritmo hacia la meta. 

Esta práctica se centra en el algoritmo A*, el cual combina el costo real de llegar a un nodo con el costo estimado (heurística) para llegar al objetivo, logrando una búsqueda óptima y rápida.

Objetivo General

El estudiante logrará comprender y programar un algoritmo de búsqueda informada (A*) en un entorno de cuadrícula discreto, integrando una función heurística para optimizar la búsqueda del camino más corto entre un punto de inicio y una meta.

Materiales o Recursos Necesarios:

  • Computadora con un entorno de desarrollo de Python (se recomienda Google Colab, Jupyter Notebook o VS Code).
  • Intérprete de Python 3.8 o superior.
  • Conocimientos básicos de estructuras de datos (listas, diccionarios, colas de prioridad).

Generación de Insumos Prácticos

 El estudiante utilizará el siguiente código base, el cual contiene la estructura del laberinto (donde 0 es un camino libre y 1 es un obstáculo) y la clase Nodo. El objetivo del estudiante será completar la función heurística y la lógica principal del algoritmo.

Instrucciones Paso a Paso

  1. Analizar el entorno de trabajo: El estudiante debe examinar la matriz laberinto, identificando las coordenadas de inicio (0, 0) y la meta (9, 9). Se debe comprender ¿cómo los unos (1) representan barreras intransitables?
  2. Implementar la función heurística: El estudiante debe programar la función calcular_heuristica utilizando la fórmula de la “Distancia Manhattan”: ∣x1−x2∣+∣y1−y2∣∣x1​−x2​∣+∣y1​−y2​∣. Esta función orientará la búsqueda.
  3. Inicializar las estructuras de control: Dentro de la función busqueda_a_estrella, se debe instanciar el nodo inicial y crear una lista abierta (preferiblemente una cola de prioridad usando heapq) y un conjunto o lista cerrada para los nodos ya visitados.
  4. Desarrollar el ciclo de expansión: El estudiante debe programar un bucle while que extraiga el nodo con el menor valor de f de la lista abierta. Si es la meta, se reconstruirá el camino hacia atrás utilizando el atributo padre de los nodos.
  5. Generar los vecinos: Por cada nodo extraído, se deben generar sus posiciones adyacentes (arriba, abajo, izquierda,derecha). Se debe verificar que no sean paredes y calcular sus valores g, h y f antes de añadirlos a la lista abierta si aportan un camino más barato.
  6. Ejecutar y validar: El código debe ejecutarse para imprimir la lista de coordenadas (tuplas) que conforman el camino más corto encontrado.

Recomendaciones

  1. Leer detenidamente la estructura de la clase Nodo antes de empezar a programar la lógica, entendiendo para qué sirve el atributo padre.
  2. Recordar que las matrices en Python se indexan como matriz[y][x], no matriz[x][y]. Las posiciones son pares (fila, columna).
  3. Imprimir el valor del nodo actual en cada iteración del bucle while (de manera temporal) para depurar y visualizar cómo se expande la búsqueda en tiempo real.
  4. Asegurarse de no añadir nodos a la lista abierta si ya se encuentran en la lista cerrada con un costo f menor, para evitar cálculos redundantes.

Posible Problema y Solución Rápida

  • Problema: El programa entra en un ciclo infinito y eventualmente arroja un error de falta de memoria o límite de recursión, evaluando repetidamente los mismos cuadros vacíos.
  • Solución Rápida: El problema se debe a que no se está utilizando correctamente una lista cerrada (closed_list).El estudiante debe asegurar que la posición (x, y) del nodo actual se agregue al conjunto de visitados tan pronto como sea extraído de la lista abierta, e incluir una condición if vecino_posicion in visitados: continueantes de procesar cualquier vecino.

Leave a Reply

Your email address will not be published. Required fields are marked *