Buscando caminos

Proseguimos con el minicurso de Navegación autónoma. ¿Cómo vuelve un robot de la panadería?

Ahora que nuestro robot sabe localizarse en un entorno, sólo hace falta que sepa cómo debe moverse desde su posición a su destino. Curiosamente un robot no se diferencia mucho de un ser humano en la forma de afrontar este problema.

Básicamente, cuando un ser humano está en su casa y tiene que ir a comprar el pan, ¿qué es lo que hace? Primero, recurre al mapa mental que ya tiene en su cabeza, en la cual puede ver dónde está la panadería más cercana. Acto seguido, planifica el camino más corto para llegar a ese punto del mapa. Evalúa de forma totalmente natural las distancias que debería recorrer si va por esta calle o por aquella otra. El resultado de esta reflexión es el camino que debe seguir para llegar a la panadería.

Este proceso que acabamos de describir se conoce en robótica móvil como planificación de rutas. Para llevarlo a cabo con éxito se necesita un mapa del entorno, la posición actual del robot (dada por la localización) y la posición de destino. Por lo tanto, necesitamos desarrollar un algoritmo o proceso que dadas estas entradas sea capaz de encontrar el camino más corto.

Os adelantamos ya mismo que existen miles de planificadores de rutas hoy en día. Pero en general, podríamos clasificar todos ellos en dos grandes grupos: los planificadores deterministas y los planificadores probabilísticos. Aunque podríamos escribir mucho sobre las virtudes y vergüenzas de cada grupo, baste por ahora decir que en robótica móvil suelen utilizarse más los planificadores deterministas. Los planificadores probabilísticos trabajan mejor cuando los sistemas robóticos son más complejos, como en el caso de un brazo robótico. En esta entrada no argumentaremos el por qué. Es suficiente con que os quedéis con la idea de que para navegar, los planificadores deterministas suelen dar un gran resultado.

Los planificadores deterministas están basados en los algoritmos de búsqueda que se usan en el campo de la inteligencia artificial clásica. Entre esos algoritmos, seguramente el más famoso es el llamado A*. La verdad es que el nombre no dice gran cosa, pero es lo que hay. Sobre este algoritmo se han hecho mil modificaciones para considerar otros mil problemas que aparecen en el ámbito de la planificación de rutas en aplicaciones reales. Pero nosotros vamos a ver cómo funciona el algoritmo A* a secas.

Vayamos a un mundo simple en el que podamos demostrar el funcionamiento del algoritmo. El nuestro será un mundo bi-dimensional, discreto y en blanco y negro. Las casillas negras tienen un obstáculo, por lo que no podemos navegar por ellas. En este mundillo, nuestro robot sólo puede realizar cuatro movimientos: arriba, abajo, izquierda y derecha (Figura 1).

Figura 1

La letra S nos señala dónde está el robot y la F dónde está el destino. Por lo tanto, nuestro algoritmo debe buscar el camino más corto para ir desde S hasta F.

El algoritmo A* parte desde la casilla (1, 1). Lo primero que hace es ejecutar la operación de expandir la casilla (1, 1). En este contexto, expandir significa simplemente considerar las casillas alcanzables desde el (1, 1) ejecutando todos los movimientos posibles. Durante la expansión, no se deben considerar aquellas casillas que contienen un obstáculo. Por lo tanto, en este caso sólo nos quedamos con la casilla (2, 1).

En este punto debemos introducir un nuevo concepto: el coste de realizar un movimiento. Para mantener todo simple, consideraremos que el coste de realizar cualquier movimiento (arriba, abajo, izquierda, derecha) es 1. El tema es que el algoritmo A* define el valor g para cualquier casilla. El valor g no es más que la suma de los costes de movimiento que nos han llevado a esa casilla. Por lo tanto, el valor g de la casilla (2, 1) es 1.

Si repetimos el procedimiento explicado, llegaremos hasta la casilla (4, 1), cuyo valor g es 3. En esta casilla, por primera vez en nuestro ejemplo, la expansión nos lleva a considerar dos casillas: la (4, 2) y la (5, 1). Ambas casillas tienen el mismo valor g, que en este caso es 4. La pregunta es obvia: ¿cómo seguimos a partir de aquí? Hasta ahora la expansión solo nos daba una casilla, por lo que seguíamos expandiéndola sin ningún problema. Ahora nos surge la duda: ¿debo elegir alguna de las casillas expandidas para seguir adelante o sigo expandiendo las dos?

En un algoritmo de búsqueda bruta, seguiríamos expandiendo las dos casillas. De esa expansión surgirían más casillas que volveríamos a expandir hasta dar con la casilla F. Como el objetivo de expandir las casillas es llegar hasta la casilla F, la búsqueda bruta nos serviría. Pero, salta a la vista que es una técnica poco eficiente. A simple vista vemos que en nuestro caso no tiene sentido considerar la expansión de la casilla (5, 1). Deberíamos elegir la casilla (4, 2) y así llegaríamos hasta F con menos expansiones.

Así es. La intuición es correcta, por lo que de alguna forma deberíamos introducirla en nuestro algoritmo de búsqueda. Eso es lo que hace el A* mediante un heurístico. Aunque la palabra en sí suene a algo muy profundo, un heurístico no es más que una función que nos ayuda a guiar la búsqueda. En este caso, la intuición nos ha hecho elegir la casilla (4, 2) por la simple razón de que está más cerca del destino. ¿Podemos poner eso en una función? ¡Pues claro!

Digamos que nuestro heurístico asigna la distancia en casillas entre una casilla dada y el destino. Así, y . En este caso, estamos usando la llamada distancia Manhattan, que no es más que la distancia en casillas no diagonales entre dos casillas. Utilizar la distancia euclídea también hubiese sido posible, por ejemplo.

Lo que hace el algoritmo A* es introducir un nuevo valor f que se define como . El valor g nos indica cuanto nos ha costado llegar a una casilla dada, mientras que h nos sugiere a qué distancia nos encontramos del destino en un mundo sin obstáculos. Pues bien, una vez tengamos dos casillas, elegimos a aquella que tenga la f más pequeña. En este caso, es la casilla (4, 2). En la Figura 2 ilustramos el proceso de expansión al completo, utilizando el proceso descrito. Las casillas elegidas en cada paso están coloreadas. Además, para todas las casillas consideradas en la expansión, hemos escrito los valores g, h y f.

Cuando la expansión incluya la casilla F, se termina. Ahora, hay que determinar el camino. En este ejemplo cada paso de expansión ha dado lugar a una única casilla. Esto es debido a que hemos seleccionado un ejemplo muy sencillo con movimientos limitados. Sin embargo, lo normal es que en cada paso se tenga más de una casilla que hay que seguir expandiendo. Por lo tanto, cuando llegamos al final, el camino resultante no es tan claro como en nuestro ejemplo. Lo que hay que hacer es ir desde F hasta S, seleccionando la casilla con el menor número g. Así, volviendo sobre nuestros pasos, es cuando definimos la lista de casillas que tenemos que pasar para ir desde S hasta F. Sencillo, ¿verdad?

Figura 2

Este algoritmo tan simple que acabamos de describir es uno de los más utilizados en robótica móvil. Nuestro ejemplo preferido, el famoso coche autónomo de Google, también utiliza este algoritmo. Un par de notas antes de terminar. En nuestro ejemplo hemos considerado que el coste de hacer cualquier movimiento es el mismo. Esto no tiene por qué ser así. Por ejemplo, en un coche preferiríamos penalizar los movimientos en marcha atrás. Eso lo conseguiríamos asignando un coste muy elevado a esos movimientos de tal forma que el algoritmo los seleccionaría sólo cuando no hay otro remedio. Por otro lado, la definición del heurístico también es flexible. Cada problemática puede requerir un heurístico diferente. Lo importante es captar la idea de que el heurístico debe guiar la búsqueda, minimizando las expansiones y evitando caminos sin retorno.

Ahora que entendemos cómo planificar una ruta, nos tenemos que enfrentar al reto de mover nuestro robot para que ande el camino planificado, evitando los obstáculos que puedan salir. Ese será el tema de la siguiente entrada.

Nos seguimos leyendo…