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 no es más que la suma de los costes de movimiento que nos han llevado a esa casilla. Por lo tanto, el valor 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í, h(4, 2) = 3 y h(5, 1) = 5. 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 que se define como f(x, y) = g(x, y) + h(x, y). 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…

10 Respuestas a “Buscando caminos

  1. Pingback: Cognición, inteligencia y el apocalipsis | Cuentos Cuánticos

  2. Pingback: De lo global a lo local y vuelta a empezar | Cuentos Cuánticos

  3. Pingback: El slalom de los robots | Cuentos Cuánticos

  4. Ok. Entendido. Gracias!

  5. Una cosa que no entiendo, si hemos definido f = h + g, por qué para decidir el camino más corto sólo se utiliza g y no f?

    • La función f se define para que el proceso de expansión sea más eficiente. Si no hubiésemos definido la f, una búsqueda bruta también nos habría llevado a encontrar la casilla de destino. Sin embargo, una vez hemos llegado hasta la casilla de destino, es la función g la que representa de verdad el coste de los posibles caminos que hemos descubierto cómo resultado de la expansión.

      Imáginate el caso en el que un obstáculo está cerca del destino. La función h no tiene eso en cuenta y puede “puntuar” bien algunas casillas cercanas al destino que en realidad no están cerca por la presencia de obstáculos. Por lo que f no es una medida realmente buena para decidir el camino más corto. Sin embargo g contiene la información de todos los movimientos requeridos para llegar hasta el destino. La función g realmente cambia ante los obstáculos.

      Espero que esta explicación te ayude, aunque lo mejor sería ponerte un ejemplo.

  6. ¿Quién asigna las distancias al heurístico, el programador o los sensores del robot?. ¿Por qué h(4,1)= 5 y no es =4?

    • El heurístico lo define y “calcula” el programador. Si te fijas, en el texto hacemos referencia a que en este caso el heurístico es la distancia sin obstáculos entre dos casillas. Es decir, para su cálculo no conocemos el mapa. Si pudiésemos saber la distancia con obstáculos, ya habríamos resuelto el problema de buscar el camino. El heurístico es una ayuda. Si lo definimos mal, nos puede fastidiar la búsqueda más que ayudar.
      En la segunda pregunta tienes razón. ¡Es una errata! h(4, 1) es 4, ya que nos tenemos que desplazar cuatro casillas. Lo edito ya mismo. ¡Muchas gracias!

      • Ahora entiendo que las f(i,j) tal que las i, j pertenecen al recorrido que el robot debe andar: valen todas 7.
        PERO, gazkune, no te lo pongas tan facilito. Imaginemos que las casillas (4, 4) y (5,4) [en tu figura 1] fuesen obstáculos, y que el robot se encontrase en la casilla (4,3). Entonces el robot podría ir abajo, o arriba con igual probabilidad f =9. Pero si baja a (5, 3) entonces tendría que volver a (4,3) y luego podría ir de nuevo a (5, 3) y así en un bucle indefinido. ¿El algoritmo puede evitar este tipo de bucles?.

        • Tu ejemplo es muy bueno. El algoritmo “marca” las casillas que ya han sido expandidas. En un paso nuevo, las casillas que anteriormente han sido expandidas no se vuelven a expandir. En el caso que comentas, el algoritmo se expandiría hacia abajo y hacia arriba. Pero en el caso de las casillas de abajo detectaría que ya sólo quedan casillas exploradas, por lo que seguiría sólo con las casillas de arriba. Por lo tanto no hay bucle y se encontraría el camino al objetivo. La clave en tu ejemplo es que cuando hay dos casillas de igual f, se expanden las dos. Además, luego, se verifica que no se vuelvan a explorar casillas ya exploradas.
          Dándole otra vuelta a tu ejemplo, también cabe la posibilidad de que el heurístico te lleve a un “callejón sin salida” (obstáculo en forma de U, dónde el objetivo está “debajo” de la U por fuera). Incluso en esos casos el algoritmo es capaz de saber que ha llegado a un punto muerto y continuar a expandir casillas que habían sido descartadas por su valor f. Cómo ves, todo está pensado 😉

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s