Localización de Montecarlo

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, donde cada partícula representa un estado posible, es decir, una hipótesis de dónde se encuentra 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] Cada vez que el robot se mueve, desplaza las partículas para predecir su nuevo estado después del movimiento. Cada vez que el robot detecta algo, las partículas se vuelven a muestrear basándose en una estimación bayesiana recursiva , es decir, qué tan bien se correlacionan los datos reales detectados 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

Consideremos un robot con un mapa interno de su entorno. Cuando el robot se mueve, necesita saber dónde se encuentra dentro de este mapa. Determinar su ubicación y rotación (más generalmente, la pose ) mediante el uso de observaciones de sus sensores se conoce como localización del robot .

Debido a que es posible que el robot no siempre se comporte de una manera perfectamente predecible, genera muchas conjeturas aleatorias sobre dónde estará a continuación. Estas conjeturas 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 inconsistentes 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 donde realmente se encuentra 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 contenga 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 en un momento está representada por un conjunto de partículas . ^[4] Cada partícula contiene un estado y, por lo 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 sólo del estado anterior (y no de ninguno de los anteriores), es decir, depende sólo de . ^[4] Esto sólo 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}}$

Descripción general

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

En cada momento el algoritmo toma como entrada la creencia anterior , una orden de actuación y 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 : para : 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 para para a : ${\displaystyle m=1}$ ${\displaystyle M}$ sacar con probabilidad ${\displaystyle x_{t}^{[m]}}$ ${\displaystyle {\bar {X_{t}}}}$ ${\displaystyle \propto w_{t}^{[m]}}$  ${\displaystyle X_{t}=X_{t}+x_{t}^{[m]}}$ fin para devolver ${\displaystyle X_{t}}$

Ejemplo de robot 1D

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

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

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

Actualización de movimiento

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

Durante la actualización del movimiento, el robot predice su nueva ubicación en función del comando de actuación dado, aplicando el movimiento simulado a cada una de las partículas. ^[1] Por ejemplo, si un robot avanza, todas las partículas avanzan 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 lo 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 esperarse, ya que un robot se vuelve menos seguro de su posición si se mueve a ciegas sin detectar el entorno.

Actualización de sensores

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, percibiría 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 que concuerden con las lecturas del sensor (posiblemente más de una vez) y rara vez se seleccionan partículas que no concuerden con las lecturas del sensor. Como tal, las partículas convergen hacia una mejor estimación del estado del robot. Esto es de esperarse 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 fundamental para 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 sus variantes, el filtro de Kalman extendido y el filtro de Kalman sin perfume ), asumen que la creencia del robot está cerca de ser una distribución gaussiana y no funcionan bien en situaciones en las que La creencia es multimodal . ^[4] Por ejemplo, un robot en un pasillo largo con muchas puertas de apariencia similar puede llegar a la creencia de que hay un pico para cada puerta, pero el robot no puede 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 para 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 será la precisión, por lo que existe un compromiso entre velocidad y precisión y se desea encontrar un valor óptimo de . Una estrategia a seleccionar es generar continuamente partículas adicionales hasta que llegue el siguiente par de lecturas de comando y sensor . ^[4] De esta forma se obtiene el mayor número posible de partículas sin impedir el funcionamiento del resto del robot. Como tal, la implementación se adapta a los recursos computacionales disponibles: cuanto más rápido sea el procesador, más partículas se pueden generar y, por lo tanto, más preciso será 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 la memoria solo depende del número de partículas y no escala con el tamaño del mapa, ^[2] y puede integrar mediciones a una frecuencia mucho mayor. ^[2]

El algoritmo se puede mejorar utilizando el muestreo KLD, como se describe a continuación, que adapta la cantidad de partículas a usar en función de qué tan seguro está el robot de su posición.

Privación de partículas

Un inconveniente de la implementación ingenua de la localización Monte Carlo se produce en un escenario en el que un robot se sienta en un lugar y detecta repetidamente el entorno sin moverse. ^[4] Supongamos que todas las partículas convergen hacia un estado erróneo, o si una mano oculta toma el robot y lo mueve a una nueva ubicación después de que las partículas ya han 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 un número pequeño de partículas, por ejemplo, y cuando las partículas se distribuyen en un espacio de estados grande. ^[4] De hecho, cualquier algoritmo de filtro de partículas puede descartar accidentalmente todas las partículas cercanas al estado correcto durante el paso de remuestreo. ^[4] ${\displaystyle M\leq 50}$

Una forma de mitigar este problema es agregar partículas adicionales de forma aleatoria 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 ninguna área del 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 solucionan sus deficiencias o lo adaptan para que sea más eficaz en determinadas situaciones.

muestreo KLD

La localización de Monte Carlo se puede mejorar muestreando las partículas de manera adaptativa basándose en una estimación del error utilizando la divergencia Kullback-Leibler (KLD). Inicialmente, es necesario utilizar uno grande 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 un desperdicio computacional. ^[6] ${\displaystyle M}$

El muestreo KLD es una variante de la localización 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 posterior verdadero 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 al espacio de estados. Cada contenedor del histograma está inicialmente vacío. En cada iteración, se extrae una nueva partícula del conjunto de partículas anterior (ponderada) con una 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 sensores antes de colocar la partícula en su contenedor. El algoritmo realiza un seguimiento del número de contenedores no vacíos . Si se inserta una partícula en un contenedor previamente vacío, se recalcula 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 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 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 sobre 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 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 Montecarlo: 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. Robótica probabilística MIT Press, 2005. Cap. 8.3 ISBN  9780262201629 .
5. Sebastian Thrun, Dieter Fox, Wolfram Burgard, Frank Dellaert. "Robusta localización montecarlo para robots móviles". Inteligencia artificial 128.1 (2001): 99–141.
6. Dieter Fox. "KLD – Muestreo: filtros de partículas adaptativos". Departamento de Ingeniería y Ciencias de la Computación, Universidad de Washington. NIPS, 2001.