Localización de Monte Carlo

La localización de Monte Carlo ( MCL ), también conocida como localización por filtro de partículas , ^[1] es un algoritmo para que los robots se 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 se encuentra el robot. ^[4] El algoritmo generalmente comienza con una distribución aleatoria uniforme de partículas sobre el espacio de configuración , lo que significa que el robot no tiene información sobre dónde se encuentra 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 se correlacionan los datos detectados reales con el estado predicho. En última instancia, las partículas deberían converger hacia la posición real del robot. ^[4]

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. La determinación de su ubicación y rotación (en términos más generales, la pose ) mediante las observaciones de sus sensores se conoce como localización del robot .

Como el robot no siempre se comporta de una manera perfectamente predecible, genera muchas suposiciones aleatorias sobre 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 que no coinciden 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 se encuentra realmente el robot.

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 para la posición y la 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)}$${\estilo de visualización x,y}$${\estilo de visualización \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 sobre el espacio de estados. ^{[1] [4]} En el algoritmo MCL, la creencia en un momento dado 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. ${\estilo de visualización t}$${\estilo de visualización 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 ninguno anterior), 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 postura actual, por lo que las partículas se distribuyen uniformemente en el espacio de configuración . ^[4]$Estilo de visualización X_{t}}$$Estilo de visualización X_{t-1}}$

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 , un comando de actuación y datos recibidos de los sensores ; y el algoritmo genera como salida la nueva creencia . ^[4]${\estilo de visualización t}$${\displaystyle X_{t-1}=\lbrace x_{t-1}^{[1]},x_{t-1}^{[2]},\ldots ,x_{t-1}^{[M]}\rbrace }$${\displaystyle u_{t}}$$estilo de visualización z_{t}}$$Estilo de visualización X_{t}}$

   Algoritmo MCL :
        
       para : actualización_de_movimiento
            actualización_de_sensor${\displaystyle (X_{t-1},u_{t},z_{t})}$${\displaystyle {\bar {X_{t}}}=X_{t}=\conjunto vacío}$${\estilo de visualización m=1}$${\estilo de visualización 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 :​${\estilo de visualización m=1}$${\estilo de visualización M}$
           sacar con probabilidad$Estilo de visualización x_{t}^{[m]}}$${\displaystyle {\bar {X_{t}}}}$${\displaystyle \propto w_{t}^{[m]}}$
           ${\displaystyle X_{t}=X_{t}+x_{t}^{[m]}}$
       fin para
       devolver$Estilo de visualización X_{t}}$

Considere un robot en un corredor circular unidimensional con tres puertas idénticas, utilizando 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.

Durante la actualización de 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 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 lo tanto, el modelo de movimiento debe compensar el ruido. Inevitablemente, las partículas divergen como consecuencia de ello durante la actualización de movimiento. Esto es esperable ya que un robot se vuelve menos seguro de su posición si se mueve a ciegas sin detectar el entorno.

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 han detectado realmente. Asigna un peso a cada partícula proporcional a dicha probabilidad. Luego, extrae aleatoriamente nuevas partículas de la creencia anterior, con una probabilidad proporcional a . Las partículas consistentes con las lecturas del sensor tienen más probabilidades de ser elegidas (posiblemente más de una vez) y las partículas inconsistentes con las lecturas del sensor rara vez se eligen. Como tal, las partículas convergen hacia una mejor estimación del estado del robot. Esto es esperable 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]}}$${\estilo de visualización M}$${\displaystyle w_{t}^{[i]}}$

El filtro de partículas central 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 variantes, el filtro de Kalman extendido y el filtro de Kalman sin aroma ), asumen que la creencia del robot está cerca de ser una distribución gaussiana y no funcionan bien para situaciones donde la creencia es multimodal . ^[4] Por ejemplo, un robot en un pasillo largo con muchas puertas de apariencia similar puede llegar a una creencia que tiene 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 brindar 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ícula, que utiliza un histograma para representar la distribución de creencias. En comparación con el enfoque basado en cuadrícula, la localización de Monte Carlo es más precisa porque el estado representado en las muestras no está discretizado. ^[2]

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 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 partículas adicionales de forma continua 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 impedir la función del resto del robot. Como tal, la implementación es adaptable 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 es el algoritmo. ^[4]${\estilo de visualización M}$${\estilo de visualización M}$${\displaystyle u_{t}}$$estilo de visualización z_{t}}$

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

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

Un inconveniente de la implementación ingenua de la localización de Monte Carlo ocurre en un escenario donde 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 al 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 convergido 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] Este problema es más probable que ocurra para un pequeño número de partículas, por ejemplo, y cuando las partículas se distribuyen en un gran espacio de estados. ^[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]${\estilo de visualización M\leq 50}$

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

El algoritmo original de localización 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.

La localización de Monte Carlo se puede mejorar muestreando las partículas de manera adaptativa en función de una estimación de error utilizando la divergencia de Kullback-Leibler (KLD). Inicialmente, es necesario utilizar un tamaño de muestra 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]${\estilo de visualización M}$

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

La idea principal es crear una cuadrícula (un histograma) superpuesta al espacio de estados. Cada contenedor en el histograma está inicialmente vacío. En cada iteración, se extrae una nueva partícula del conjunto de partículas (ponderado) anterior 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 sensor 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 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 igual a . ^[4]${\estilo de visualización k}$$Estilo de visualización M_{x}}$${\estilo de visualización k}$${\estilo de visualización M}$$Estilo de visualización M_{x}}$

Es fácil ver que el muestreo KLD elimina las partículas redundantes del conjunto de partículas, ya que solo aumenta cuando se llena una nueva ubicación (bin). En la práctica, el muestreo KLD supera sistemáticamente y converge más rápido que el MCL clásico. ^[4]$Estilo de visualización M_{x}}$