Occupancy Grid Mapping 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 el supuesto 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 uniformemente espaciado de variables aleatorias binarias , cada una de las cuales representa la presencia de un obstáculo en esa ubicación del entorno. Los algoritmos de la cuadrícula de ocupación calculan estimaciones posteriores aproximadas para estas variables aleatorias. [2]
Hay cuatro componentes principales del enfoque de mapeo de la cuadrícula de ocupación. Ellos son:
El objetivo de un algoritmo de mapeo de ocupación es estimar la probabilidad posterior sobre mapas dados los datos: , donde está el mapa, es el conjunto de mediciones desde el tiempo 1 hasta t, y es el conjunto de posturas del robot desde el tiempo 1 hasta t. Los controles y los datos de odometría no desempeñan ningún papel en el algoritmo de mapeo de la cuadrícula de ocupación ya que se supone que la ruta es conocida.
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 mapas 2D que describen una porción del mundo 3D.
Si denotamos la celda de la cuadrícula con el índice i (a menudo en mapas 2D, se usan dos índices para representar las dos dimensiones), entonces la notación representa la probabilidad de que la celda i esté ocupada. El problema computacional al estimar el posterior es la dimensionalidad del problema: si el mapa contiene 10.000 celdas de cuadrícula (un mapa relativamente pequeño), entonces el número de mapas posibles que pueden representarse mediante esta cuadrícula es . Por lo tanto, no es factible calcular una probabilidad posterior para todos esos mapas.
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. Este desglose es conveniente pero pierde parte de la estructura del problema, ya que no permite modelar dependencias entre celdas vecinas. En cambio, la parte posterior de un mapa se aproxima factorizándola en
Debido a esta factorización, se puede utilizar un filtro binario de Bayes para estimar la probabilidad de ocupación de cada celda de la cuadrícula. Es común utilizar una representación logarítmica de la probabilidad de que cada celda de la cuadrícula esté ocupada.
