Localización de Monte Carlo

La localización de Monte Carlo (MCL) , también conocida como localización de filtro de partículas , ^[1] es un algoritmo para que los robots localicen utilizando un filtro de partículas . ^{[2] [3] [4] [5]} Dado un mapa del entorno, el algoritmo estima la posición y orientación de un robot a medida que se mueve y detecta el entorno. ^[4] El algoritmo utiliza un filtro de partículas para representar la distribución de estados probables, y cada partícula representa un estado posible, es decir, una hipótesis de dónde está el robot. ^[4]El algoritmo generalmente comienza con una distribución aleatoria uniforme de partículas en el espacio de configuración , lo que significa que el robot no tiene información sobre dónde está y asume que es igualmente probable que esté en cualquier punto del espacio. ^[4] Siempre que el robot se mueve, cambia las partículas para predecir su nuevo estado después del movimiento. Siempre que el robot detecta algo, las partículas se vuelven a muestrear en función de la estimación bayesiana recursiva , es decir, qué tan bien los datos detectados reales se correlacionan con el estado predicho. En última instancia, las partículas deberían converger hacia la posición real del robot. ^[4]

Descripción básica

Considere un robot con un mapa interno de su entorno. Cuando el robot se mueve, necesita saber dónde está dentro de este mapa. La determinación de su ubicación y rotación (más generalmente, la pose ) mediante el uso de las observaciones de su sensor se conoce como localización de robot .

Debido a que es posible que el robot no siempre se comporte de una manera perfectamente predecible, genera muchas suposiciones aleatorias de dónde estará a continuación. Estas suposiciones se conocen como partículas. Cada partícula contiene una descripción completa de un posible estado futuro. Cuando el robot observa el entorno, descarta partículas incompatibles con esta observación y genera más partículas cercanas a las que parecen consistentes. Al final, es de esperar que la mayoría de las partículas converjan hacia donde realmente está el robot.

Representación estatal

El estado del robot depende de la aplicación y el diseño. Por ejemplo, el estado de un robot 2D típico puede consistir en una tupla de posición y orientación . Para un brazo robótico con 10 articulaciones, puede ser una tupla que contiene el ángulo en cada articulación: .${\displaystyle (x,y,\theta )}$${\displaystyle x,y}$${\displaystyle \theta }$${\displaystyle (\theta _{1},\theta _{2},...,\theta _{10})}$

La creencia , que es la estimación del robot de su estado actual, es una función de densidad de probabilidad distribuida en el espacio de estados. ^{[1] [4]} En el algoritmo MCL, la creencia a la vez está representada por un conjunto de partículas . ^[4] Cada partícula contiene un estado y, por tanto, puede considerarse una hipótesis del estado del robot. Las regiones en el espacio de estados con muchas partículas corresponden a una mayor probabilidad de que el robot esté allí, y es poco probable que las regiones con pocas partículas estén donde está el robot.${\displaystyle t}$${\displaystyle M}$ ${\displaystyle X_{t}=\lbrace x_{t}^{[1]},x_{t}^{[2]},\ldots ,x_{t}^{[M]}\rbrace }$

El algoritmo asume la propiedad de Markov de que la distribución de probabilidad del estado actual depende solo del estado anterior (y no de los anteriores), es decir, depende solo de . ^[4] Esto solo funciona si el entorno es estático y no cambia con el tiempo . ^[4] Normalmente, al iniciarse, el robot no tiene información sobre su pose actual, por lo que las partículas se distribuyen uniformemente en el espacio de configuración . ^[4]${\displaystyle X_{t}}$${\displaystyle X_{t-1}}$

Resumen

Dado un mapa del entorno, el objetivo del algoritmo es que el robot determine su pose dentro del entorno.

En todo momento, el algoritmo toma como entrada la creencia anterior , un comando de actuación y los datos recibidos de los sensores ; y el algoritmo genera la nueva creencia . ^[4]${\displaystyle t}$${\displaystyle X_{t-1}=\lbrace x_{t-1}^{[1]},x_{t-1}^{[2]},\ldots ,x_{t-1}^{[M]}\rbrace }$${\displaystyle u_{t}}$${\displaystyle z_{t}}$${\displaystyle X_{t}}$

 Algoritmo MCL : de a : MOTION_UPDATE sensor_update${\displaystyle (X_{t-1},u_{t},z_{t})}$${\displaystyle {\bar {X_{t}}}=X_{t}=\emptyset }$${\displaystyle m=1}$${\displaystyle M}$${\displaystyle x_{t}^{[m]}=}$ ${\displaystyle (u_{t},x_{t-1}^{[m]})}$ ${\displaystyle w_{t}^{[m]}=}$ ${\displaystyle (z_{t},x_{t}^{[m]})}$ ${\displaystyle {\bar {X_{t}}}={\bar {X_{t}}}+\langle x_{t}^{[m]},w_{t}^{[m]}\rangle }$ fin de para para :${\displaystyle m=1}$${\displaystyle M}$ dibujar de con probabilidad${\displaystyle x_{t}^{[m]}}$${\displaystyle {\bar {X_{t}}}}$${\displaystyle \propto w_{t}^{[m]}}$ ${\displaystyle X_{t}=X_{t}+x_{t}^{[m]}}$ fin de regreso ${\displaystyle X_{t}}$

Ejemplo de robot 1D

Un robot viaja a lo largo de un pasillo unidimensional, armado con un sensor que solo puede decir si hay una puerta (izquierda) o no hay puerta (derecha).

Considere un robot en un pasillo circular unidimensional con tres puertas idénticas, usando un sensor que devuelve verdadero o falso dependiendo de si hay una puerta.

${\displaystyle t=0}$
El algoritmo se inicializa con una distribución uniforme de partículas. El robot se considera igualmente probable que se encuentre en cualquier punto del espacio a lo largo del pasillo, aunque esté físicamente en la primera puerta.	Actualización del sensor : el robot detecta una puerta . Asigna un peso a cada una de las partículas. Las partículas que probablemente den la lectura de este sensor reciben un peso mayor.	Remuestreo : el robot genera un conjunto de nuevas partículas, la mayoría de ellas generadas alrededor de las partículas anteriores con más peso. Ahora cree que está en una de las tres puertas.

${\displaystyle t=1}$
Actualización de movimiento : el robot se mueve un poco hacia la derecha. Todas las partículas también se mueven a la derecha y se aplica algo de ruido. El robot está físicamente entre la segunda y la tercera puerta.	Actualización del sensor : el robot no detecta puerta . Asigna un peso a cada una de las partículas. Las partículas que probablemente den la lectura de este sensor reciben un peso mayor.	Remuestreo : el robot genera un conjunto de nuevas partículas, la mayoría de ellas generadas alrededor de las partículas anteriores con más peso. Ahora cree que está en una de dos ubicaciones.

${\displaystyle t=2}$
Actualización de movimiento : el robot se mueve un poco hacia la izquierda. Todas las partículas también se mueven hacia la izquierda y se aplica algo de ruido. El robot está físicamente en la segunda puerta.	Actualización del sensor : el robot detecta una puerta . Asigna un peso a cada una de las partículas. Las partículas que probablemente den la lectura de este sensor reciben un peso mayor.	Remuestreo : el robot genera un conjunto de nuevas partículas, la mayoría de ellas generadas alrededor de las partículas anteriores con más peso. El robot se ha localizado con éxito.

Al final de las tres iteraciones, la mayoría de las partículas convergen en la posición real del robot según se desee.

Actualización de movimiento

Creencia después de mover varios pasos para un robot 2D utilizando un modelo de movimiento típico sin detección .

Durante la actualización de movimiento, el robot predice su nueva ubicación basándose en el comando de actuación dado, aplicando el movimiento simulado a cada una de las partículas. ^[1] Por ejemplo, si un robot se mueve hacia adelante, todas las partículas se mueven hacia adelante en sus propias direcciones sin importar hacia dónde apunten. Si un robot gira 90 grados en el sentido de las agujas del reloj, todas las partículas giran 90 grados en el sentido de las agujas del reloj, independientemente de dónde se encuentren. Sin embargo, en el mundo real, ningún actuador es perfecto: pueden sobrepasar o no alcanzar la cantidad de movimiento deseada. Cuando un robot intenta conducir en línea recta, inevitablemente se curva hacia un lado o hacia el otro debido a pequeñas diferencias en el radio de las ruedas. ^[1]Por tanto, el modelo de movimiento debe compensar el ruido. Como consecuencia, inevitablemente, las partículas divergen durante la actualización del movimiento. Esto es de esperar ya que un robot se vuelve menos seguro de su posición si se mueve a ciegas sin sentir el entorno.

Actualización del sensor

Cuando el robot detecta su entorno, actualiza sus partículas para reflejar con mayor precisión dónde se encuentra. Para cada partícula, el robot calcula la probabilidad de que, si hubiera estado en el estado de la partícula, percibiera lo que sus sensores realmente han detectado. Asigna un peso a cada partícula proporcional a dicha probabilidad. Luego, extrae aleatoriamente nuevas partículas de la creencia anterior, con probabilidad proporcional a . Es más probable que se elijan partículas consistentes con las lecturas del sensor (posiblemente más de una vez) y las partículas inconsistentes con las lecturas del sensor rara vez se seleccionan. Como tal, las partículas convergen hacia una mejor estimación del estado del robot. Esto se espera ya que un robot se vuelve cada vez más seguro de su posición a medida que detecta su entorno.${\displaystyle w_{t}^{[i]}}$${\displaystyle M}$${\displaystyle w_{t}^{[i]}}$

Propiedades

No parametricidad

El filtro de partículas central de MCL puede aproximarse a múltiples tipos diferentes de distribuciones de probabilidad , ya que es una representación no paramétrica . ^[4] Algunos otros algoritmos de localización bayesianos, como el filtro de Kalman (y variantes, el filtro de Kalman extendido y el filtro de Kalman sin aroma ), asumen que la creencia de que el robot está cerca de ser una distribución gaussiana y no funciona bien en situaciones en las que la creencia es multimodal . ^[4]Por ejemplo, un robot en un pasillo largo con muchas puertas de aspecto similar puede llegar a la creencia de que tiene un pico para cada puerta, pero el robot es incapaz de distinguir en qué puerta se encuentra. En tales situaciones, el filtro de partículas puede ofrecer un mejor rendimiento que los filtros paramétricos. ^[4]

Otro enfoque no paramétrico de la localización de Markov es la localización basada en cuadrículas, que utiliza un histograma para representar la distribución de creencias. En comparación con el enfoque basado en cuadrículas, la localización de Monte Carlo es más precisa porque el estado representado en las muestras no está discretizado. ^[2]

Requisitos computacionales

La complejidad temporal del filtro de partículas es lineal con respecto al número de partículas. Naturalmente, cuantas más partículas, mejor es la precisión, por lo que existe un compromiso entre la velocidad y la precisión y se desea encontrar un valor óptimo de . Una estrategia para seleccionar es generar continuamente partículas adicionales hasta que llegue el siguiente par de comandos y lecturas del sensor . ^{[4] De} esta forma se obtiene el mayor número posible de partículas sin obstaculizar la función del resto del robot. Como tal, la implementación se adapta a los recursos computacionales disponibles: cuanto más rápido es el procesador, más partículas se pueden generar y, por lo tanto, más preciso es el algoritmo. ^[4]${\displaystyle M}$${\displaystyle M}$${\displaystyle u_{t}}$${\displaystyle z_{t}}$

En comparación con la localización de Markov basada en cuadrículas, la localización de Monte Carlo ha reducido el uso de memoria ya que el uso de memoria solo depende del número de partículas y no se escala con el tamaño del mapa, ^[2] y puede integrar mediciones a una frecuencia mucho mayor. ^[2]

El algoritmo se puede mejorar mediante el muestreo KLD , como se describe a continuación, que adapta el número de partículas a utilizar en función de la seguridad del robot en su posición.

Privación de partículas

Un inconveniente de la implementación ingenua de la localización de Monte Carlo ocurre en un escenario en el que un robot se sienta en un lugar y detecta repetidamente el entorno sin moverse. ^[4] Suponga que todas las partículas convergen hacia un estado erróneo, o si una mano oculta levanta el robot y lo mueve a una nueva ubicación después de que las partículas ya hayan convergido. Como las partículas alejadas del estado convergente rara vez se seleccionan para la siguiente iteración, se vuelven más escasas en cada iteración hasta que desaparecen por completo. En este punto, el algoritmo no puede recuperarse. ^[4] Es más probable que este problema ocurra para una pequeña cantidad de partículas, por ejemplo , y cuando las partículas se extienden sobre un gran espacio de estado. ^[4] De hecho, cualquier${\displaystyle M\leq 50}$El algoritmo del filtro de partículas puede descartar accidentalmente todas las partículas cerca del estado correcto durante el paso de remuestreo. ^[4]

Una forma de mitigar este problema es agregar partículas adicionales al azar en cada iteración. ^[4] Esto equivale a suponer que, en cualquier momento, el robot tiene una pequeña probabilidad de ser secuestrado en una posición aleatoria en el mapa, provocando así una fracción de estados aleatorios en el modelo de movimiento. ^[4] Al garantizar que ningún área en el mapa esté totalmente privada de partículas, el algoritmo ahora es robusto contra la privación de partículas.

Variantes

El algoritmo de localización original de Monte Carlo es bastante simple. Se han propuesto varias variantes del algoritmo, que abordan sus deficiencias o lo adaptan para ser más efectivo en determinadas situaciones.

Muestreo de KLD

La localización de Monte Carlo puede mejorarse muestreando las partículas de una manera adaptativa basada en una estimación de error utilizando la divergencia de Kullback-Leibler (KLD). Inicialmente, es necesario utilizar un gran debido a la necesidad de cubrir todo el mapa con una distribución uniformemente aleatoria de partículas. Sin embargo, cuando las partículas han convergido alrededor de la misma ubicación, mantener un tamaño de muestra tan grande es computacionalmente un desperdicio. ^[6]${\displaystyle M}$

El muestreo de KLD es una variante de la localización de Monte Carlo donde en cada iteración, se calcula un tamaño de muestra . El tamaño de la muestra se calcula de manera que, con probabilidad , el error entre el verdadero posterior y la aproximación basada en la muestra sea menor que . Las variables y son parámetros fijos. ^[4]${\displaystyle M_{x}}$${\displaystyle M_{x}}$${\displaystyle 1-\delta }$${\displaystyle \epsilon }$${\displaystyle \delta }$${\displaystyle \epsilon }$

La idea principal es crear una cuadrícula (un histograma) superpuesta en el espacio de estado. Cada contenedor del histograma está inicialmente vacío. En cada iteración, se extrae una nueva partícula del conjunto de partículas anterior (ponderado) con probabilidad proporcional a su peso. En lugar del remuestreo realizado en el MCL clásico, el algoritmo de muestreo KLD extrae partículas del conjunto de partículas ponderado anterior y aplica las actualizaciones de movimiento y sensor antes de colocar la partícula en su contenedor. El algoritmo mantiene un registro del número de contenedores no vacíos, . Si se inserta una partícula en un contenedor previamente vacío, se vuelve a calcular el valor de , que aumenta principalmente de forma lineal en . Esto se repite hasta que el tamaño de la muestra sea ​​el mismo que . ^[4]${\displaystyle k}$${\displaystyle M_{x}}$${\displaystyle k}$${\displaystyle M}$${\displaystyle M_{x}}$

Es fácil ver que el muestreo de KLD elimina las partículas redundantes del conjunto de partículas, aumentando solo cuando se ha llenado una nueva ubicación (contenedor). En la práctica, el muestreo de KLD supera consistentemente y converge más rápido que el MCL clásico. ^[4]${\displaystyle M_{x}}$

Referencias

1. Ioannis M. Rekleitis. " Un tutorial de filtro de partículas para la localización de robots móviles ". Centro de Máquinas Inteligentes, Universidad McGill, Tech. Rep. TR-CIM-04-02 (2004).
2. Frank Dellaert , Dieter Fox, Wolfram Burgard , Sebastian Thrun . " Localización de Monte Carlo para robots móviles. Archivado el 17 de septiembre de 2007 en la Wayback Machine ." Proc. de la Conferencia Internacional IEEE sobre Robótica y Automatización Vol. 2. IEEE, 1999.
3. Dieter Fox, Wolfram Burgard, Frank Dellaert y Sebastian Thrun, " Localización de Monte Carlo: estimación de posición eficiente para robots móviles ". Proc. de la Decimosexta Conferencia Nacional sobre Inteligencia Artificial John Wiley & Sons Ltd, 1999.
4. Sebastian Thrun, Wolfram Burgard, Dieter Fox. Probabilistic Robotics MIT Press, 2005. Cap. 8.3 ISBN  9780262201629 .
5. Sebastian Thrun, Dieter Fox, Wolfram Burgard, Frank Dellaert. " Robusta localización de monte carlo para robots móviles ". Inteligencia artificial 128.1 (2001): 99-141.
6. Dieter Fox. " KLD-Sampling: Adaptive Particle Filters ". Departamento de Ingeniería y Ciencias de la Computación, Universidad de Washington. NIPS, 2001.