Extendí mi ejercicio de A* para que además busque la solución utilizando Avara y las compare gráficamente.
Avara es otro algoritmo de búsqueda, pero a diferencia de A* no es ni óptimo ni completo. Ambos utilizan una heurística para estimar el costo de un estado n al estado objetivo y por esto se dice que son métodos informados.

La diferencia radica en cómo seleccionan nodos para su expansión: mientras que A* siempre elije el nodo que minimice la función camino recorrido + estimación al objetivo, Avara simplemente elije el nodo con menor estimación al objetivo (no tiene en cuenta el camino previo). Read the rest of this entry »

El ejemplo consiste en un plano de 800×600 puntos con el punto (0,0) en la esquina superior izquierda. En el plano hay puntos y figuras (formadas por puntos). Uno de los puntos es el origen y otro el destino. El problema a resolver es encontrar el camino más corto desde el origen al destino moviéndose de punto a punto y sin pasar sobre una figura.

La heurística utilizada es la distancia en línea recta desde la posición actual a la posición del objetivo. Read the rest of this entry »

Inteligencia Artificial -un enfoque moderno-, el libro del que estoy estudiando tiene muchos de los algorítmos que explica en pseudo código implementados en Python.

Uno de los autores cuenta que originalmente estaban escritos en Lisp, pero muchos estudiantes tenían problemas con este lenguaje. En especial, saltar del pseudo código del libro a una implementación que corra en sus computadoras. El primer intento fue usar Java, pero no tuvieron éxito:

However, one attempt at getting Java code up and running was largely unsuccesful. Then I discovered Python and Jython, and thought this might be a better way to go than Java.

cita

En este capítulo ampliaremos estos temas para conseguir algoritmos que pueden responder a preguntas expresadas en lógica de primer orden. Esto es muy significativo, porque si se trabaja duro, más o menos cualquier cosa se puede representar en lógica de primer orden.

Inferencia lógica de primer orden – Cap. 9 de Inteligencia Artificial, un enfoque moderno 2° ed – Stuart Russell & Peter Norvig

Mientras cursamos este cuatrimestre Intelegencia Artificial en la facu uno de los ejemplos que aparecía era el del Wumpus, un monstruo que vive en una cueva muy parecida a una grilla. El Wumpus ocupa una casilla de la grilla (dónde inicialmente está dormido) y en las otras puede haber pozos, viento de un pozo cercano, olor a Wumpus o un lingote de oro. Y por supuesto nosotros (el cazador).

Este escenario constituye un juego en el cual el cazador (que solo puede percibir lo que hay en las celdas adyacentes a las que ocupa) debe realizar movimientos (Arriba, Abajo, Derecha, Izquierda) o acciones como lanzar una flecha o tomar el lingote para cumplir su objetivo: salir de la cueva con el oro y sin ser comido por el Wumpus.

Read the rest of this entry »