Inteligencia Artificial (II): GPS, conocimiento experto y algoritmos de búsqueda

Un GPS dice al conductor que se tire al agua

Como vimos en el artículo sobre programación lógica, la I.A. ha vuelto al candelero gracias al mensaje de Google: ha llegado la era de la Inteligencia Artificial.

La I.A. son programas que se comportan de manera que, de hacerlo un humano, diríamos que es inteligente.

Hoy vamos a aplicar la Inteligencia Artificial a los algoritmos de búsqueda y explicaremos como calcula las rutas un GPS.

El cálculo de rutas en GPS

Existen problemas cuya solución es única, como por ejemplo el cálculo de un balance de gastos. Y también hay problemas donde hay muchas soluciones y se pretende obtener una buena solución o, llevado al extremo, una solución óptima.

Por ejemplo, el problema del GPS: resolver el camino más corto entre dos direcciones. Este es una variante de un problema clásico de Informática que se llama el problema del viajante. En este problema tenemos:

  • Una serie de ciudades (pueden ser calles)
  • Una serie de conexiones que unen dos de esas ciudades (las carreteras)
  • Una serie de «pesos» o «costes». Puede ser la distancia, pero también el tiempo que se tarda en llegar.

salesman

Es un problema con un conjunto enorme de soluciones y se trata de encontrar una solución de compromiso que sea «lo suficientemente buena».

La forma más evidente de resolver este problema es recorriendo todos los caminos posibles desde el origen hasta el destino y quedarse con el más económico (menor peso o coste). Para ello habrá que hacer un montón de combinaciones entre las ciudades origen, destino y las intermedias.

El programa recorrerá un primer camino y calculará su peso. Luego otro. Irá recorriendo los caminos hasta obtener uno que tenga un coste admisible por el usuario. O hasta que los recorra todos, entonces cogerá el menor.

Otra alternativa es recorrer una etapa de cada camino posible. En lugar de recorrer un camino hasta el final, y luego otro, y otro, lo que hacen es mantener un conjunto de candidatos al mejor camino. Estos candidatos se ordenan de mejor opción a peor opción. Y se exploran en ese orden.

En algoritmos heurísticos, se clasifican las posibles soluciones apoyándonos en el conocimiento de un experto

Imaginemos que queremos ir de La Coruña a Irún. Y que sólo existen dos vías: por Gijón (282 Km) o Lugo (97 Km). Tendríamos el camino LC-G con un peso de 282 y el LC-L con un peso de 97.

  1. LC-Lugo (peso 97 Km)
  2. LC-Gijón (peso 282 Km)

Se toma el camino más prometedor (LC-L) y se expande hacia sus ciudades destino. Imagina LC-L-Ponferrada (con peso 135) y LC-L-Zamora (con peso 293).  Los nuevos caminos generados, que incluyen el último nodo, se agregan a la bolsa de alternativas, que se ordena con el más prometedor primero. Así conseguimos un grupo de candidatos a mejor solución. Si continuamos este algoritmo, al final obtendremos una solución.

Orden de la bolsa de candidatas en el paso 2.

  1. LC-L-Ponferrada (peso 135)
  2. LC-Gijón (peso 282)
  3. LC-L-Zamora (peso 293)

Añadiendo I.A.

En los algoritmos heurísticos a cada camino se le asigna además un peso extra. Basándonos en el conocimiento de un experto, añadimos un coste hipotético que corresponde a la parte de la solución todavía no resuelta.

En nuestro caso será una aproximación de la distancia que todavía queda por recorrer. El heurístico por ejemplo puede tener en cuenta la geoposición de la última ciudad del camino (Gijón o Lugo) y la de la ciudad destino (Irún) y tendrá un peso menor cuanto más cerca estén (en el espacio, sin contar con las carreteras).

En ese caso el peso del camino LC-G será de 282 + 300 (del heurístico) mientras que el del camino LC-L podría ser de 97  + 600. Como ves, al añadir conocimiento experto, los pesos de las alternativas cambian.

  1. LC-Gijón (peso’ = 582)
  2. LC-Ponferrada (peso’ = 697)

Exploraremos primero el camino por Gijón, que es más prometedor, a pesar de tener un coste mayor acumulado. Con este conocimiento experto, la bolsa de candidatas cambiará respecto a la versión original.

La utilización de distintas funciones heurísticas devolverá distintas soluciones. El heurístico puede tener en cuenta, por ejemplo, el número de ciudades intermedias entre la alternativa y el destino.

Otros problemas

Se pueden utilizar heurísticos en almacenaje de paquetería con tamaños irregulares, cálculo de volúmenes, clasificación de correos electrónicos como SPAM, etc.

¿Y a tí, se te ocurre algún problema que resolverías con Heurísticos?

Un comentario en “Inteligencia Artificial (II): GPS, conocimiento experto y algoritmos de búsqueda”

Comentarios cerrados.