¿En qué narices piensa mi GPS?

Por Colaborador Invitado, el 7 diciembre, 2017. Categoría(s): Divulgación • Tecnología

Seguramente esto es lo que te preguntas cada vez que tu GPS tiene una ocurrencia totalmente absurda de las muchas que nos han ocurrido en los más de 10 años que llevan estos dispositivos facilitándonos la vida haciendo que no nos perdamos (mucho). Ahora bien ¿cómo funcionan estos dispositivos?

El GPS no es más que un dispositivo móvil (en la mayor parte de los casos el propio teléfono móvil) con una antena especial que capta una señal de radio que proviene de un grupo (constelación) de satélites que orbitan la tierra. Esta señal indica al dispositivo la ubicación relativa del satélite con respecto a nosotros, a esta información se la conoce como efeméride. Si juntamos la información de varios satélites, podemos determinar nuestra ubicación con un rango de error de unos pocos metros mediante lo que se conoce como triangulación.

satelites

Una vez nuestro dispositivo sabe dónde está ¿Cómo sabe cuál es el camino más corto para ir al destino que le hemos indicado? Ahí llegamos a su parte inteligente.

En el caso de los GPS que no están conectados a internet los mapas están precargados en su disco duro, estos mapas tienen las carreteras trazadas. Estos sistemas cogen nuestra posición y la del destino en el mapa, así como todas las carreteras que los unen formando un grafo, que es un conjunto de aristas (los caminos) y nodos (las ciudades, intersecciones…) creando un esquema como el de la imagen:

grafo

Imaginemos que el nodo negro es el punto en el que nos encontramos y el nodo rojo nuestro destino, las aristas nos indican los posibles caminos que existen para llegar. Ahora bien ¿Cuál es el mejor?

Para evaluar un camino, el software del GPS se puede configurar con varias opciones como el camino más corto o el camino más rápido. Imaginemos que le configuramos el camino más rápido, en este caso se puntúa cada camino con el tiempo estimado en recorrerlo y nuestro objetivo es lograr el camino con el valor mínimo. Para ello se usan algoritmos de “Búsqueda Informada”, se llaman así porque usan el conocimiento específico del problema, en este caso el tiempo en recorrer los caminos. Hay una gran variedad de algoritmos de este tipo, pero su funcionamiento se puede resumir en los siguientes pasos:

  1. Se escoge un nodo para expandir sus caminos con una función de evaluación (por ejemplo: el tiempo de ese nodo hasta el objetivo).
  2. Si el nodo escogido no es el objetivo se expanden los caminos que parten de ese nodo y se calculan sus funciones de evaluación para volver al paso 1.

Uno de los algoritmos mas eficientes para recorrido de grafos es el algoritmo A*, este algoritmo usa para evaluar sus nodos una combinación entre el coste (tiempo o distancia) hasta llegar al nodo y el coste estimado desde ese nodo al objetivo. Esta función de coste estimado o función heurística no es trivial y escoger una función equivocada puede hacer que el sistema nos devuelva una solución que no es la mejor. Para comprender mejor cómo funciona veamos su pseudocódigo:

// Conjunto de nodos ya evaluados

ConjuntoCerrado := {}

 

// Conjunto de nodos descubiertos sin evaluar

// Al inicio será el nodo origen

ConjuntoAbierto := {origen}

 

// Para cada nodo que sea alcanzado de modo más eficiente

// si un nodo puede ser alcanzado por muchos otros nodos

// su paso previo debe ser el de menor valor de todos

PasoPrevio := mapa vacío

 

// Para cada nodo, tomamos el coste hasta llegar a él desde el origen

Valorg := lista de valores por defecto (pondremos un valor muy elevado)

 

// iniciamos el coste del origen al origen a 0

valorg[origen] := 0

 

// Para cada nodo, coste total de llegar del origen al destino pasando por

// ese nodo. Este valor es parcialmente conocido, parcialmente heurístico.

Valorf := lista de valores por defecto (pondremos un valor muy elevado)

 

// Para el primer nodo ese valor es totalmente heurístico

valorf[inicio] := coste_estimado(inicio, objetivo)

 

mientras el ConjuntoAbierto tenga nodos:

actual := nodo del ConjuntoAbierto con el menor Valorf[]

Si actual = Objetivo

Mostrar_camino(actual) //Mostramos el camino en el mapa

Si no

                    //Borramos el nodo actual del conjunto abierto y lo añadimos al cerrado        

ConjuntoAbierto.Borrar(actual)

ConjuntoCerrado.Añadir(actual)

 

Para cada nodo vecino al actual //(accesible por un camino)

Si el vecino está en ConjuntoCerrado

continuar   // Ignora el vecino ya evaluado.

 

Si el vecino no está en Conjunto abierto //Nuevo nodo descubierto

ConjuntoAbierto.Añadir(vecino) //Lo añadimos al conjunto abierto

 

// Calculamos distancia del inicio al vecino

                                        //Esta función puede variar en función a nuestro objetivo.

Valorg_tentativo := Valorg[actual] + distancia_entre(actual, vecino)

Si Valorg_tentativo >= Valorg[Vecino]

continuar                       // No es el mejor camino, le ignoramos

Si no     // Este camino es el mejor hasta ahora, lo guardamos

PasoPrevio[vecino] := actual

Valorg[vecino] := Valorg_tentativo

Valorf[vecino] := Valorg[vecino] + coste_estimado(vecino, objetivo)

 

Fin

Una pega que tiene es su consumo de memoria, que en casos de mapas complejos puede ser muy elevado. Para evitar ese consumo de recursos se puede usar una variante llamada “búsqueda heurística con memoria acotada”. Esta variante expande los mejores nodos hasta que la memoria se llena, en ese momento se elimina de memoria el peor nodo y se expande el nodo con la mejor puntuación.

Otro tipo de algoritmos que se usan para buscar el camino más corto hasta un destino son los Algoritmos genéticos, estos algoritmos combinan los estados actuales (padres) para obtener los estados sucesores de un modo que recuerda a la selección natural. Los algoritmos genéticos crean una población inicial generando rutas al azar desde el punto origen al destino, de esa población escogen las mejores, las cruzan y aplican modificaciones con una probabilidad P a las que se llaman mutaciones, generando una nueva población de rutas con las que repetirán el proceso hasta obtener la ruta óptima o hasta haber llegado a un límite de iteraciones. En la siguiente imagen se muestra un esquema de su funcionamiento:

Algoritmo_genetico

Una vez encontrado el camino más corto con el algoritmo que lleve implementado el dispositivo, éste lo mostrará y, si nos desviamos del camino, recalculará la ruta para guiarnos.

Una cosa que vemos es que hoy en día nuestros teléfonos móviles conectados calculan las rutas mucho más rápido que nuestros viejos dispositivos GPS y, además, nos informan de la situación del tráfico y nos cambian la ruta si hay atasco. Esto se debe a que en los GPS de antes el cálculo de la ruta se hacía de forma local con la señal GPS y los mapas como única información mientras que, en el caso de los móviles, la ruta la calcula un servidor al que nos conectamos a través de la red de datos que además de nuestra ubicación y el mapa, tiene los datos de la velocidad a la que se mueven todos los dispositivos que tienen su aplicación instalada y puede determinar la situación del tráfico. La potencia de estos servidores y la enorme cantidad de información que recogen de los dispositivos conectados no sólo hacen que tengamos la ruta óptima rápidamente, sino que además hacen que estas aplicaciones no tengan errores por tener los mapas sin actualizar y nos ahorran tener los mapas almacenados en la memoria del dispositivo, todo a cambio de que nuestro móvil les envíe datos de nuestra ubicación y la velocidad a la que nos movemos. Esto parece un trato bastante razonable ¿Verdad? Otra mejora que se está introduciendo en los sistemas de rutas es el uso de Redes Neuronales Artificiales para encontrar el mejor camino a nuestro destino. Estos sistemas no sólo se adaptan a cualquier situación, sino que además, en función al tiempo que hemos tardado, si al llegar al destino le damos una opinión buena o mala de la ruta, si le hemos ignorado… son capaces de inferir si han dado un mal resultado y modificarse para mejorar.

Como veis los sistemas GPS son un ejemplo de sistema que usa Inteligencia Artificial en nuestra vida cotidiana y que ha evolucionado para ofrecernos la ruta óptima hacia nuestro destino de un modo rápido y eficiente pese a que a veces discutamos con él.

Este artículo nos lo envía Sara Robisco Cavite @SaraRC83, ingeniera en informática por la Universidad de Alcalá de Henares (Madrid) especializada en Inteligencia Artificial. Entusiasta de la ciencia y del arte, vive siempre aprendiendo.



Por Colaborador Invitado, publicado el 7 diciembre, 2017
Categoría(s): Divulgación • Tecnología