4.1: Representaciones de mapas

Para planificar un camino, de alguna manera necesitamos representar el entorno en la computadora. Diferenciamos entre dos enfoques complementarios: aproximaciones discretas y continuas. En una aproximación discreta, un mapa se subdivide en trozos de igual (por ejemplo, un mapa de cuadrícula o hexagonal) o diferentes tamaños (por ejemplo, habitaciones en un edificio). Estos últimos mapas también se conocen como mapas topológicos. Los mapas discretos se prestan bien a una representación gráfica. Aquí, cada trozo del mapa corresponde a un vértice (también conocido como “nodo”), que están conectados por bordes, si un robot puede navegar de un vértice a otro. Por ejemplo, una hoja de ruta es un mapa topológico, con intersecciones como vértices y carreteras como aristas, etiquetadas con su longitud (Figura 4.2.1). Computacionalmente, un gráfico podría almacenarse como una lista/matriz de adyacencia o incidencia. Una aproximación continua requiere la definición de límites internos (obstáculos) y externos, típicamente en forma de polígono, mientras que los caminos pueden codificarse como secuencias de puntos definidos por números reales. A pesar de las ventajas de memoria de una representación continua, los mapas discretos son la representación dominante en robótica.

Para mapear obstáculos, el mapa más común es el mapa de cuadrícula de ocupación. En un mapa de cuadrícula, el entorno se discretiza en cuadrados de resolución arbitraria, por ejemplo, 1cm x 1cm, en los que se marcan obstáculos. En una cuadrícula de ocupación probabilística, las celdas de la cuadrícula también se pueden marcar con la probabilidad de que contengan un obstáculo. Esto es particularmente importante cuando la posición del robot que detecta un obstáculo es incierta. Las desventajas de los mapas de cuadrícula son sus grandes requisitos de memoria, así como el tiempo computacional para atravesar estructuras de datos con un gran número de vértices. Una solución a esto es almacenar el mapa de cuadrícula como árbol k-d. Un árbol k-d rompe recursivamente el entorno en k pedazos. Para k = 4, un área se rompe en cuatro pedazos. Cada una de estas piezas se rompe nuevamente en cuatro piezas y así sucesivamente, hasta que se alcanza la resolución deseada. Estas piezas se pueden almacenar fácilmente en una gráfica con cada vértice teniendo cuatro hijos, que son las cuatro piezas en las que se rompe el vértice, o es una hoja del árbol. Lo que hace atractiva esta estructura de datos es que no todos los vértices necesitan desglosarse a la menor resolución posible. En cambio, solo las áreas, que contienen obstáculos, deben desglosarse aún más. Un mapa de cuadrícula que contiene obstáculos y el árbol k-d correspondiente, aquí un árbol cuádruple, se muestran en la Figura 4.1.1. No hay una bala de plata, y cada aplicación puede requerir una solución diferente que podría ser una combinación de diferentes tipos de mapas.

Figura\(\PageIndex{1}\): Un mapa de cuadrícula y su árbol cuadriculado correspondiente (árbol k-d).

También existen todas las combinaciones posibles de representación discreta y continua. Por ejemplo, las hojas de ruta para sistemas GPS se almacenan como mapas topológicos que almacenan las coordenadas GPS de cada vértice, pero también pueden contener superposiciones de fotografía aérea y callejera o incluso nubes de puntos 3D almacenadas en un árbol 8-d, también conocido como Octree. Estos diferentes mapas se utilizan luego en diferentes etapas de la etapa de planificación del camino.