El mapeo de cuadrículas de ocupación se refiere a una familia de algoritmos informáticos en robótica probabilística para robots móviles que abordan el problema de generar mapas a partir de datos de medición de sensores ruidosos e inciertos, con la suposición de que se conoce la postura del robot. Las cuadrículas de ocupación fueron propuestas por primera vez por H. Moravec y A. Elfes en 1985. [1]
La idea básica de la cuadrícula de ocupación es representar un mapa del entorno como un campo de variables aleatorias binarias uniformemente espaciadas , cada una de las cuales representa la presencia de un obstáculo en esa ubicación del entorno. Los algoritmos de cuadrícula de ocupación calculan estimaciones posteriores aproximadas para estas variables aleatorias. [2]
El método de mapeo de cuadrículas de ocupación consta de cuatro componentes principales:
El objetivo de un algoritmo de mapeo de ocupación es estimar la probabilidad posterior sobre mapas dados los datos: , donde es el mapa, es el conjunto de mediciones desde el tiempo 1 hasta t, y es el conjunto de poses del robot desde el tiempo 1 hasta t. Los datos de control y odometría no juegan ningún papel en el algoritmo de mapeo de la cuadrícula de ocupación ya que se supone que se conoce la ruta.
Los algoritmos de cuadrícula de ocupación representan el mapa como una cuadrícula de grano fino sobre el espacio continuo de ubicaciones en el entorno. El tipo más común de mapas de cuadrícula de ocupación son los mapas 2D que describen una porción del mundo 3D.
Si denotamos la celda de la cuadrícula con índice i (a menudo, en mapas 2D, se utilizan dos índices para representar las dos dimensiones), entonces la notación representa la probabilidad de que la celda i esté ocupada. El problema computacional con la estimación de la probabilidad posterior es la dimensionalidad del problema: si el mapa contiene 10 000 celdas de la cuadrícula (un mapa relativamente pequeño), entonces la cantidad de mapas posibles que se pueden representar mediante esta cuadrícula es . Por lo tanto, calcular una probabilidad posterior para todos esos mapas es inviable.
El enfoque estándar, entonces, es dividir el problema en problemas más pequeños de estimación.
para todas las celdas de la cuadrícula . Cada uno de estos problemas de estimación es entonces un problema binario. Esta descomposición es conveniente pero pierde algo de la estructura del problema, ya que no permite modelar dependencias entre celdas vecinas. En cambio, la posterior de un mapa se aproxima factorizándola en
Gracias a esta factorización, se puede utilizar un filtro bayesiano binario para estimar la probabilidad de ocupación de cada celda de la cuadrícula. Es habitual utilizar una representación de probabilidad logarítmica de la probabilidad de que cada celda de la cuadrícula esté ocupada.
