cs373 »

CS373 Unidad 1 - El Problema de la Localización

Contents

Introducción

En esta unidad aprenderemos a programar un localizador. Un programa localizador obtiene información del entorno a través de sensores y ubica al robot en el espacio. La localización se centra en la pregunta ¿Dónde está el robot ahora?

Aunque es una pregunta simple, la respuesta no es fácil, ya que el método o algoritmo mas conveniente a utilizar en cada caso depende de las características del robot y del entorno. Técnicas de localización que funcionan bien para un robot en un medio ambiente pueden no funcionar correctamente bajo otras circunstancias. Por ejemplo, métodos de localización que funcionan muy bien al aire libre, pueden ser inútiles en interiores.

Durante la ultima década, científicos han desarrollado métodos utilizando sensores, radares y software para programar vehículos con la capacidad de percibir su propia ubicación, la de otros vehículos y navegar por un camino trazado.

Todas las técnicas de localización por lo general proporcionan dos informaciones básicas:

  • ¿Cuál es la ubicación del robot en su entorno?
  • ¿Cuál es la orientación actual del robot en ese mismo espacio?

El Problema de la Localización

Localización es la habilidad de una maquina de ubicarse por si misma en el espacio.

Considere un robot totalmente perdido, sin tener idea donde se encuentra en relación a su entorno, ¿cómo puede ubicarse el robot dentro del espacio?

En lugar de instalar un dispositivo de GPS en nuestro robot, vamos a escribir un programa para implementar la localización.

Nuestro programa localizador reducirá el margen de error considerablemente, comparado con el de un dispositivo GPS, cuyo margen de error puede llegar a ser de hasta diez metros. Para que nuestro robot sea capaz de navegar por si mismo a través del espacio con éxito y precisión, estamos buscando un margen de error entre dos a diez centímetros.

Imagine un robot que se encuentra en un mundo unidimensional, en algún lugar a lo largo de una linea recta, sin tener idea en que punto de ese mundo se encuentra. Como ejemplo de un mundo de este tipo podemos imaginar un corredor largo y angosto donde solo es posible moverse hacia adelante y hacia atrás; siendo imposible moverse lateralmente.

Dado que nuestro robot esta totalmente desorientado, considera igualmente probable que su ubicación actual sea cualquier punto de ese mundo unidimensional. Podemos describir matemáticamente esta situación diciendo que la función de probabilidad de la ubicación del robot es uniforme (la misma) a lo largo del espacio de muestra (en este caso, el mundo unidimensional el robot).

Si graficaramos esta función de probabilidad, colocando la probabilidad en el eje vertical y la ubicación en el eje horizontal, dibujaríamos una linea recta, horizontal y nivelada. Esa linea describe una función de probabilidad uniforme, y representa el estado de máxima confusión.

cs373-01-01-Spanish.png

Ahora supongamos que introducimos tres puntos de referencia, tres puertas iguales a lo largo del corredor. Asumamos también que el robot tiene un mapa de su mundo y es capaz de diferenciar si está frente a una puerta o no.

Si el robot detecta que está al lado de una puerta, ¿cómo afecta esta medición a nuestra creencia, o a la probabilidad de que el robot se encuentre cerca de una puerta?

cs373-01-02-Spanish.png

La medición de estar frente a una puerta transforma la función de probabilidad definida. Imaginemos que el robot verifica el mapa de su mundo unidimensional, de un extremo al otro, verificando en cada posible ubicación si está frente a una puerta o no. La nueva función de probabilidad resultante tiene tres picos alineados con la ubicación de cada puerta. Para estas tres ubicaciones se incrementa la probabilidad de estar en esa posición (indicado con los picos en el gráfico) mientras que la probabilidad de las otras ubicaciones decrece.

La nueva función de probabilidad es llamada apreciación posterior ya que dicha función es definida luego que el robot realizo la medición en cada posible ubicación.

La función posterior es la representación de la creencia del robot sobre su propia ubicación tras realizar las mediciones. Es importante destacar que el robot aun no sabe donde está. Tras detectar que está frente a una puerta, hay tres posibles ubicaciones con puertas donde es probable que se encuentre. También es posible que por error de los sensores el robot detecte accidentalmente una puerta donde realmente no la hay, es por eso que existe una probabilidad residual que el robot se encuentre en cualquier otra ubicación.

La posibilidad de hacer una medición errónea esta siempre presente en rebotica, y en el transcurso de este curso veremos diferentes maneras de tratar este problema.

Movimiento del Robot

Si el robot se mueve, aun sin realizar una nueva medición, puede estimar su nueva posición, tomando como base la suposición de su ubicación anterior y el conocimiento de hacia donde y cuanto se movió.

En el ejemplo anterior, el robot había detectado estar frente a una puerta y supuso estar en alguna de las tres posiciones donde hay una puerta. Tras desplazarse un metro, puede suponer que se encuentra a un metro de cualquiera de esas tres posiciones.

Entonces si el robot se mueve a la derecha una cierta distancia, podemos desplazar la función de probabilidad a la derecha de acuerdo al movimiento.

cs373-01-03-Spanish.png

Observe que todos los picos de la función de probabilidad se han desplazado hacia la derecha, como podríamos esperar tras el desplazamiento del robot. Sin embargo es posible que le llame la atención que los picos no solo se hayan desplazado sino que también se han aplanado. Esta disminución de la certeza sobre la ubicación del robot es debida a la incertidumbre sobre el movimiento. En el mundo real, nunca podemos tener la certeza de que el movimiento del robot sea exacto, y esto disminuye la probabilidad de estar en una posición determinada, y por lo tanto los picos de la curva son menos pronunciados.

El desplazamiento y aplanamiento de los picos es el resultado de haber realizado una convolución entre la función de probabilidad posterior y la función de probabilidad asociada al movimiento del robot.

La convolución es una operación matemática que toma dos funciones y mide su superposición. Para ser mas específicos, representa la magnitud de su superposición a medida que una función se desliza sobre la otra. Las animaciones que se muestran aquí pueden servir para clarificar este concepto.

En la teoría de la probabilidad, la función de probabilidad de la suma de dos variables aleatorias independientes es la convolución de cada una de sus funciones de probabilidad. En nuestro caso las dos variables independientes son la creencia del robot sobre su propia ubicación y la incertidumbre del movimiento.

Por ejemplo, si dos funciones no se superponen, el valor de su convolución es igual a cero. Por el contrario si ambas funciones se superponen completamente, el valor de su convolución es igual a uno. Entre estos dos extremos, la convolución toma valores entre cero y uno.

Ahora, supongamos que tras desplazarse el robot realiza una segunda medición, y nuevamente detecta estar frente a una puerta, obteniendo exactamente el mismo resultado que en su medición anterior.

cs373-01-04-Spanish.png

¡Ahora la cosa mas increíble sucede! Gracias a la segunda medición nuestro robot logra tener una mas precisa idea de donde se encuentra.

Al igual que tras la primera medición, la detección de una puerta aumenta la probabilidad de que nuestro robot se encuentre en una de las tres posibles posiciones donde hay una puerta.

A pesar de que la segunda medición es exactamente igual a la primera, la función de probabilidad posterior a la segunda medición no es igual a la que habíamos obtenido después de la primera medición. ¿Por qué?

Porque a diferencia de nuestra primera medición, cuando partimos de un estado de máxima incertidumbre, antes de la segunda medición el robot ya tenia una idea sobre su posible ubicación. Esta información previa, junto con el resultado de la segunda medición, nos da como resultado una nueva función de probabilidad, como la que muestra el siguiente gráfico.

cs373-01-05-Spanish.png

En este gráfico vemos un par de protuberancias de poca importancia, pero solo un pico agudo. Este pico corresponde a la segunda puerta. Hemos intentado explicarlo matemáticamente, pero vamos a pensar intuitivamente sobre lo que pasó. Primero el robot vio la primera puerta. Esto le permitió suponer que estaba cerca de alguna puerta, pero no sabia cual. Luego se movió y vio una segunda puerta. !El robot ha visto dos puertas seguidas! Así que, por supuesto, nuestra función de probabilidad debe tener un pico principal, cerca del único lugar donde seria de esperar ver dos puertas seguidas.

Una vez más, es importante destacar que el robot aun no tiene certeza de su posición, pero después de dos mediciones está más seguro de su posible ubicación de lo que estaba tras la primera medición. ¿Qué cree que pasaría a medida que el robot realiza mas y mas mediciones?

cs373-01-06-Spanish.png

¡Felicidades! ¡Hemos repasado juntos los conceptos básicos de probabilidad y localización! El tipo de localización que acaba de estudiar se conoce como Método de Montecarlo.

Ejercicios de programación

Pregunta 1 (Pregunta sobre Probabilidad Uniforme)

Imaginemos un mundo formado por cinco celdas diferentes o lugares posibles. Supongamos ademas que existe la misma probabilidad de que nuestro robot se encuentre en cualquiera de esas cinco celdas.

Si nuestro robot puede estar en cualquiera de esas cinco celdas de la tabla, etiquetadas como X_i , siendo valores de i de 1 a 5, sabiendo que la suma de las probabilidades siempre suma 1, ¿cuál es la probabilidad de encontrar al robot en una celda determinada X_i ?

Respuesta 1

Y la respuesta es 0.2, la cual surge de dividir la probabilidad total, 1, por las 5 celdas.

P(X_i) = 0.2

Pregunta 2 (Pregunta sobre Probabilidad Uniforme)

Modifique la siguiente lista vacía:

p = []

de forma tal que p se convierta en una distribución uniforme sobre cinco celdas, expresado como un vector de cinco probabilidades. Por ejemplo, la probabilidad de que el robot se encuentre en la celda dos, se podría escribir como:

p[2] = 0.2

y dado que cada una de las celdas tiene la misma probabilidad de que el robot se encuentre en ella, también puede expresar la probabilidad de que el robot se encuentre en la celda cinco escribiendo:

p[5] = 0.2

Para un repaso de Python, le recomendamos visitar la siguiente página.

Respuesta 2

Una solución simple es especificar cada elemento de la lista p con la probabilidad 0.2, correspondiente a la función de probabilidad uniforme de encontrar al robot en una celda determinada.

p =  [0.2, 0.2, 0.2, 0.2, 0.2]

print p

obteniendo como resultado

[0.2, 0.2, 0.2, 0.2, 0.2]

Como hemos explicado, la función de probabilidad uniforme representa la situación de máxima incertidumbre, donde tenemos la misma probabilidad de encontrar el robot en cualquier celda.

Pregunta 3 (Probabilidad Uniforme Generalizada)

Complete el siguiente código para crear un vector de probabilidades, donde p es de la longitud arbitraria definida por n:

p=[]
n=5

print p

En este ejemplo definimos n igual a 5 para que el resultado coincida con el de la solución anterior, pero si hiciéramos n igual a 10 deberíamos obtener un vector de diez elementos iguales a 0.1.

Respuesta 3

Usando un bucle for y agregando elementos a la lista con appended una posible solución es la siguiente:

#define las variables globales p y n.
p = [ ]
n = 5

#Usa un bucle 'for' para recorrer todas las celdas en un mundo de longitud 'n'.
for i in range (n):

    #Agrega a la lista 'n' elementos cada uno con el valor '1.' dividido 'n' usando números con coma flotante.
    p.append(1./n)

print p

obteniendo el mismo resultado que en el ejercicio anterior

[0.2, 0.2, 0.2, 0.2, 0.2]

Si olvida utilizar operaciones de coma flotante, python interpretara que la división es entre números enteros. Debido a que el entero 1 dividido por el entero 5 da por resultado 0 con un resto de 1, si nos olvidáramos de colocar el punto decimal después del 1. obtendríamos el resultado incorrecto de [0, 0, 0, 0, 0].

Ahora somos capaces de inicializar el vector p con una función de probabilidad uniforme para cualquier numero de celdas, especificado por n.

Pregunta 4 (Probabilidad después de la medición)

Ahora que podemos establecer la creencia inicial del robot sobre su ubicación en el mundo, queremos actualizar esta creencias luego de obtener una medición de los sensores del robot.

Imaginemos que el robot se encuentra en un mundo con cinco celdas, x1 a x5 y supongamos que 2 de esas celdas son rojas y 3 son verdes. Al igual que antes partiremos de un estado de incertidumbre, con una probabilidad uniforme de 0.2 en cada celda.

Si el robot realiza una medición y ve el color rojo. ¿Cómo afectará esta medición a la probabilidad de encontrar al robot en cada una de las cinco celdas?

cs373-01-07-Spanish.png

Obviamente la probabilidad de encontrar al robot en las celdas x2 y x3 aumentará, y la probabilidad de encontrarlo en las celdas x1, x4 y x5 disminuirá.

Para actualizar la probabilidad de cada celda utilizaremos una simple regla basada en la multiplicación. Multiplicaremos la probabilidad de cada celda roja por 0.6 y la probabilidad de cada celda verde por 0.2.

celdas rojas * 0.6
celdas verdes * 0.2

Para el ejemplo hemos elegido estos valores arbitrariamente, pero como 0.6 es tres veces mas grande que 0.2, el resultado debe incrementar la probabilidad de estar en una celda roja por un factor de tres respecto a la probabilidad de estar en una celda verde.

Tenga en cuenta que es posible que la lectura de los sensores sea errónea, por lo tanto no podemos multiplicar la probabilidad de las celdas verdes por cero.

¿Cuál es la probabilidad de que el robot se encuentre en una celda roja y cuál es la probabilidad de que se encuentre en una celda verde? Por favor, complete los espacios en blanco en el siguiente gráfico:

cs373-01-08-Spanish.png


Respuesta 4 (Probabilidad después de la medición)

Encuentre la probabilidad para cada celda multiplicando la creencia previa (0.2 para todas las celdas) por el nuevo factor, cuyo valor depende del color de la celda.

Para las celdas rojas, 0.2*0.6 = .12 
Para las celdas verdes, 0.2*0.2 = 0.04

cs373-01-09-Spanish.png

¿Son éstas nuestras probabilidades?

Pregunta 5 (Calcular la suma)

¡No! Éstas no son nuestras probabilidades porque no suman uno. Desde que sabemos que estamos en alguna celda, la probabilidades individuales deben sumar uno. Lo que tenemos ahora es lo que se conoce como distribución no normalizada de probabilidad.

Entonces, ¿cómo normalizamos nuestra distribución?

Primero, calcule la suma de las probabilidades individuales. A continuación, obtenemos la distribución de probabilidad apropiada. Una distribución de probabilidad es una función que representa la probabilidad de cualquier variable, i, tomando un valor específico.

Calcule la suma de los valores para ver si tenemos una distribución de probabilidad apropiada — la suma debe dar uno.

cs373-01-10.png

Respuesta 5 (Calcular la suma)

cs373-01-11.png

Como la suma de las celdas no es igual a 1, nuestra distribución actualizada no es una distribución de probabilidad apropiada.

Pregunta 6 (Normalice la distribución)

Para obtener una distribución de probabilidad, divida cada número en cada celda por la suma de los valores, 0.36.

Respuesta 6 (Normalice la distribución)

cs373-01-12.png

  • Celdas verdes = 1/9
  • Celdas rojas = 1/3

Esto es una distribución de probabilidad escrita como: P(X_i|Z)

y leída como: La distribución posterior del lugar X_i dada la medida Z, siendo Z la medida de los sensores del robot. Esto es un ejemplo de probabilidad condicional. Si necesita más ayuda sobre este tema , este video puede ser de ayuda.

Pregunta 7 (pHit y pMiss)

Empezando con nuestro estado de máxima confusión

p = [0.2, 0.2, 0.2, 0.2, 0.2]

Queremos escribir un programa que multiplique cada entrada por el factor apropiado: pHit o pMiss.

Podemos empezar sin preocuparnos de que esta distribución sume uno (es decir, que esté normalizada). Como vimos en las últimas preguntas, podemos normalizarla fácilmente después.

Escriba una pieza de código que muestre p después de multiplicar pHit y pMiss en los lugares correspondientes.

  • pHit = 0.6 → factor para la medición correcta
  • pMiss = 0.2 → factor para la medición errónea

Respuesta 7 (pHit y pMiss)

Una forma de hacer esto es recorriendo los cinco casos, 0-4 y multiplicar manualmente según el caso pMiss o pHit:

p = [0.2, 0.2, 0.2, 0.2, 0.2)
pHit = 0.6
pMiss = 0.2
p[0] = p[0]*pMiss
p[1] = p[1]*pHit
p[2] = p[2]*pHit
p[3] = p[3]*pMiss
p[4] = p[4]*pMiss
print p

0.04000000000000004, 0.12, 0.12, 0.040000000000000008, 0.040000000000000008

Nota: Esta no es la solución más elegante.

Pregunta 8 (Suma de probabilidades)

Sabemos que ésta no es una distribución válida porque no suma 1. Antes de normalizar esta distribución necesitamos calcular la suma de las probabilidades individuales.

Modifique el programa para obtener la suma de todas las probabilidades individuales.

Respuesta 8 (Suma de probabilidades)

Utilice la función suma de Python:

p = [0.2, 0.2, 0.2, 0.2, 0.2)
pHit = 0.6
pMiss = 0.2
p[0] = p[0]*pMiss
p[1] = p[1]*pHit
p[2] = p[2]*pHit
p[3] = p[3]*pMiss
p[4] = p[4]*pMiss
print sum(p)

0.36

Pregunta 9 (Función de detección)

Permítame hacer el código más elegante introduciendo una variable, world, para especificar el color de cada una de las celdas — roja o verde.

p = [0.2, 0.2, 0.2, 0.2, 0.2] 
#introducimos la variable '''world'''
world = ['green', 'red', 'red', 'green', 'green']
pHit = 0.6
pMiss = 0.2

Además, indicamos que el robot ha detectado que se encuentra en una celda roja, por lo que definimos la medición Z para que sea de color roja:

p = [0.2, 0.2, 0.2, 0.2, 0.2]
world = ['green', 'red', 'red', 'green', 'green']

#defina la medida ''Z'' para que sea roja
Z = 'red'
pHit = 0.6
pMiss = 0.2

Defina una función para actualizar la medición llamada sense, que toma como entrada la distribución inicial p y la medida Z.

Prepare la función para proporcionar como salida la distribución no normalizada q, en la que q represente el producto no normalizado de la probabilidad de entrada (0.2) por pHit o pMiss respecto a si el color de la celda correspondiente del mundo (world) es roja (hit) o verde (miss).

p = [0.2, 0.2, 0.2, 0.2, 0.2]'''
world = ['green', 'red', 'red', 'green', 'green']
Z = 'red'
pHit = 0.6
pMiss = 0.2
def sense(p, Z):
    #Defina una función '''sense'''

    return q
print sense(p, Z)

Cuando devuelva q, debe esperar obtener el mismo vector que obtuvo en la respuesta de la pregunta 6, pero ahora lo calcularemos usando una función. Esta función debería funcionar para cualquier posible Z (roja o verde) y cualquier p[] válido.

Respuesta 9(Función de detección)

Paso 1: Una forma de hacer esto es la siguiente:

p = [0.2, 0.2, 0.2, 0.2, 0.2)
world = ['green', 'red', 'red', 'green', 'green']
Z = 'red'
pHit = 0.6
pMiss = 0.2

def sense(p, Z):
    q = [ ]
    for i in range(len(p)):
        hit = (Z == world[i])
        q.append(p[i] * (hit * pHit + (1-hit) * pMiss))
    return q

print sense(p, Z)

Este código establece el acierto (hit) a 1 cuando la medición es la misma que la entrada actual en el mundo (world) y 0 en cualquier otro caso. La siguiente linea añade a la lista q[ ] una entrada que es igual a p[i]*pHit cuando hit = 1 y p[i]*pMiss cuando hit = 0.

Esto nos proporciona nuestra distribución no normalizada. Un "bandera binaria" hace referencia a la siguiente pieza de código: (hit * pHit + (1-hit) * pMiss). El nombre viene del hecho de que cuando el operando (hit) es 1, el otro operando (1-hit) es cero, y viceversa.

Pregunta 10 (Función de detección normalizada)

Modifique el código para que normalice la salida para la función sense, y el total sume uno.

Respuesta 10 (Función de detección normalizada)

p = [0.2, 0.2, 0.2, 0.2, 0.2)
world = ['green', 'red', 'red', 'green', 'green']
Z = 'red'
pHit = 0.6
pMiss = 0.2
def sense(p, Z):
    q = [ ]
    for i in range(len(p)):
        hit = (Z == world[i])
        q.append(P[i] * (hit * pHit + (1-hit) * pMiss))
        # Primero, calculamos la suma del vector q, utilizando la función sum
        s = sum(q)
        for i in range (len(p)):
        # normalizamos recorriendo todos los elementos en q y dividiéndolos por el total s
            q[i]=q[i]/s
    return q

print sense(p, Z)

[0.1, 0.3, 0.3, 0.1, 0.1]

Pregunta 11 (Probando la función de detección)

Cambie a green el valor de la variable de medida de la detección Z, y ejecute de nuevo el código para ver si obtenemos el resultado correcto.

Respuesta 11 (Probando la función de detección)

p = [0.2, 0.2, 0.2, 0.2, 0.2)
world = ['green', 'red', 'red', 'green', 'green'] 
# Cambiamos a 'green' la variable de medición Z y lanzamos de nuevo la ejecución del código para obtener el resultado correcto
Z = 'green'
pHit = 0.6
pMiss = 0.2
def sense(p, Z):
    q = [ ]
    for i in range(len(p)):
        hit = (Z == world[i])
        q.append(p[i] * (hit * pHit + (1-hit) * pMiss))
        s = sum(q)
    for i in range (len(p)):
        q[i] = q[i]/s
    return q
print sense(p, Z)

[0.27,  0.09, 0.09, 0.27, 0.27]

Este resultado parece bueno. Ahora todas las celdas verdes tienen mayor probabilidad que las celdas rojas. La "división por 44" mencionada en el video viene del paso de la normalización donde dividimos por la suma. En este caso era 0.44.

Pregunta 12(Múltiples mediciones)

Modifique el código de forma que haya múltiples mediciones reemplazando Z por un vector de mediciones.

Asuma que el robot detecta rojo (red) y después verde (green).

¿Puede modificar el código para que actualice la probabilidad dos veces, y le proporcione la distribución posterior después de que ambas mediciones sean incorporadas para que cualquier secuencia de mediciones, independientemente de su longitud, pueda ser procesada?

Respuesta 12 (Múltiple mediciones)

p = [0.2, 0.2, 0.2, 0.2, 0.2)
world = ['green', 'red', 'red', 'green', 'green'] 
#Reemplazamos Z con un vector de mediciones y asumimos que el robot detecta rojo (red) y después verde (green)
measurements = ['red', 'green']
pHit = 0.6
pMiss = 0.2
def sense(p, Z):
    q = [ ]
    for i in range(len(p)):
        hit = (Z == world[i])
        q.append(p[i] * (hit * pHit + (1-hit) * pMiss))
        s = sum(q)
    for i in range (len(p)):
        q[i] = q[i]/s
    # Por cada medición utilice la siguiente iteración
for k in range(len(measurements)): 
    #Almacene el elemento k, aplique la creencia actual, p, y actualice esa creencia en su misma variable
    p = sense(P, measurements [k])
    print p 
    #ejecute esto dos veces y obtendrá la distribución uniforme:

Este código define la función de detección y a continuación llama a esa función una vez por cada medición y actualiza la distribución.

[0.2, 0.2, 0.2, 0.2, 0.2]

Movimiento exacto (Movimiento exacto)

Suponga que hay una distribución sobre las celdas como ésta: \frac{1}{9}, \frac{1}{3}, \frac{1}{3}, \frac{1}{9}, \frac{1}{9}

cs373-01-13.png

Sabemos que el robot se mueve a la derecha, y asumiremos que el mundo es cíclico. Es decir, cuando el robot alcanza la celda situada en el extremo derecho, retornará a la primera celda o la situada en el extremo izquierdo.

Pregunta 1 (Movimiento exacto)

Asumiendo que el robot se mueve exactamente una posición a la derecha, ¿cuál es la distribución de probabilidad posterior después del movimiento?

Respuesta 1 (Movimiento exacto)

Todo se desplaza a la derecha una celda.

cs373-01-14.png

Pregunta 2 (Función move)

Defina una función move con una distribución de entrada p y un desplazamiento u, donde u es el número de celdas que se mueve a la derecha o a la izquierda.

Programe una función que devuelva una nueva distribución q, donde si u=0, q es lo mismo q p.

  • Si u = 1, todos los valores son desplazados cíclicamente 1 posición a la derecha
  • Si U = 3, todos los valores se desplazan 3 posiciones a la derecha
  • Si U = -1, todos los valores se desplazan 1 posición a la izquierda

Cambiando la probabilidad de la celda dos de cero a uno nos permitirá ver el efecto del movimiento

p = [0, 1, 0, 0, 0)

world = ['green', 'red', 'red', 'green', 'green']
measurements = ['red', 'green']
pHit = 0.6
pMiss = 0.2
def sense(p, Z):
    q = []
    for i in range(len(p)):
        hit = (Z == world[i])
        q.append(p[i] * (hit * pHit + (1-hit) * pMiss))
    s = sum(q)
    for i in range (len(p)):
        q[i] = q[i]/s
    return q

print sense(p, Z)

def move(p, U):

return q

for k in range(len(measurements)):
    p = sense(p, measurements [k])
    print move (p, 1)

Respuesta 2 (Función move)

def move(p, U):
    q= [ ] #Start with empty list
    for i in range(len(p)):
        # Recorre todos los elementos en ''''''''p''''' 
        # Construye ''q'' elemento por elemento accediendo a la correspondiente ''p'' desplazado en ''U''
        q.append(p[(i-U) % len (p)])
    return q

for k in range(len(measurements)):
p = sense(p, measurements [k])
print move (p, 1)

El componente (i-U) de la función anterior puede ser confuso al principio.

Si se está moviendo a la derecha, puede tener la tentación de utilizar el signo más. ¡No lo haga! En lugar de pensar en p desplazando una celda en q, piense en esta función como q creándose desde cada celda de p.

Por ejemplo, si estamos desplazando p una posición a la derecha, cada celda en q tiene que almacenar su valor desde la celda en p que está a una posición a la izquierda.

Movimiento Inexacto del Robot: La Localización es dura

Pregunta 1 (Movimiento Inexacto)

Asuma que el robot ejecuta su acción correctamente con una probabilidad alta (0.8); con una probabilidad baja (0.1) de que se pase o se quede corto.

Observe que este modelo es más cercano al movimiento real del robot.

cs373-01-15.png

Dada una distribución previa, ¿puede obtener la distribución después del movimiento?

Utilice esta fórmula:

  • u = 2 \\ P(X_{i+2}|X_i) = 0.8 \\ P(X_{i+1}|X_i) = 0.1 \\ P(X_{i+3}|X_i) = 0.1

cs373-01-16.png

Respuesta 1 (Movimiento inexacto)

cs373-01-17.png

Como era de esperar, la distribución de probabilidad se ha desplazado y se ha extendido. El movimiento provoca una pérdida de información.

Pregunta 2 (Movimiento inexacto)

Esta vez, teniendo las celdas dos y cuatro el valor 0.5, obtenga la distribución posterior.

cs373-01-18.png

Respuesta 2 (Movimiento inexacto)

cs373-01-19.png

Respondemos a esta cuestión de la misma forma que en la anterior, pero esta vez tenemos que tener en cuenta que la celda 5 puede ser alcanzada de dos maneras: por la celda 4 quedándose corto o por la celda 2 pasándose.

Pregunta 3 (Movimiento inexacto)

Dada una distribución uniforme, complete la distribución después del movimiento utilizando la formula.

cs373-01-20.png

Respuesta 3 (Movimiento inexacto)

Podemos responder a esta pregunta de dos formas:

  1. As shown: explicitly calculate the possible ways of arriving at each cell. This takes quite a bit of calculation, but will give us the correct answer.
  2. Realize that if we start with a uniform prior distribution (state of maximum confusion), and we then move, we MUST end up with the uniform distribution. Since this problem starts with a state of maximum confusion and then moves (which, remember, never increases our knowledge of the system), we must remain in the maximally confused state.

image

Question 4 (Inexact Move Function)

Modify the move procedure to accommodate the added probabilities.

p = [0, 1, 0, 0, 0)
world = ['green', 'red', 'red', 'green', 'green']
measurements = ['red', 'green']
pHit = 0.6
pMiss = 0.2
#Add exact probability
pExact = 0.8
#Add overshoot probability
pOvershoot = 0.1
pUndershoot = 0.1

def move(p, U):
    q= []
    for i in range(len(p)):
        q.append(p[(i-U) % len (p)])
    return q

Answer 4 (Inexact Move Function)

def move(p, U):
    #Introduce auxiliary variable s
    q= []
    for i in range(len(p)):
        s = pExact * p[(i-U) % len(p)]
        s = s + pOvershoot * p[(i-U-1) % len(p)]
        s = s + pUndershoot * p[(i-U+1) % len(p)]
        q.append(s)
    return q

[0.0, 0.1, 0.8, 0.1, 0.0]

This function accommodates the possibility of undershooting or overshooting our intended move destination by going through each cell in p and appropriately distributing it's probability over three cells in q (the cell it was intended to go to, a distance U away, and the overshoot and undershoot cells)

Question 5 (Limit Distribution Quiz)

What happens if the robot never senses but executes the motion to the right forever, what will be the limit or stationary distribution in the end?

A distribution is stationary when it doesn't change over time. In the case of the moving robot, this corresponds to the probability distribution before a move being the same as the distribution after the move.

image

Answer 5 (Limit Distribution Quiz)

The fact that the result is a uniform distribution should not be surprising.

Remember Inexact Motion 3, where we saw that when we act on the uniform distribution with the function move, we get back the uniform distribution. Moving doesn't affect the uniform distribution, and this is exactly the definition of a stationary state!

We can also solve for the probability of each cell by realizing that each cell is the possible destination for three other cells. This is the method used in the lecture and shown below. Of course, regardless of our method, we get the same answer: the uniform distribution.

image

Question 6 (Move Twice)

Write code that makes the robot move twice, starting with the initial distribution:

p = [0, 1, 0, 0, 0]

Answer 6 (Move Twice)

p = move(p, 1)
p = move(p, 1)

print p

[0.01, 0.01, 0.16, 0.66, 0.16]

The result is a vector where 0.66 is the largest value and not 0.8 anymore. This is expected: two moves has flattened and broadened our distribution.

Question 7 (Move 1000)

Write a piece of code that moves 1,000 steps and give you the final distribution.

Answer 7 (Move 1000)

#Write a loop for 1,000 steps
for k in range(1000):
    p = move(p, 1)
    print p
    #Final distribution is 0.2 in each case as expected

After 1000 moves, we have lost essentially all information about the robot's location. We need to be continuously sensing if we want to know the robot's location.

Robot Sense and Movement

Localization, specifically the Monte Carlo Localization method that we are using here, is nothing but the repetition of sensing and moving. There is an initial belief that is tossed into the loop. If you sense first it comes to the left side. Localization cycles through move and sense. Every time it moves it loses information and every time it senses it gains information. Entropy- a measure of information that the distribution has

S = \sum_i p_i \log{p_i}

Entropy and information entropy are both fascinating topics. Feel free to read more about them!

image

Question 1 (Sense and Move)

Given the motions one and one, which means the robot moves right and right again:

motions = [1, 1]

Compute the posterior distribution if the robot first senses red, then moves right by one, then senses green, then moves right again. Start with a uniform prior distribution:

p = [0.2, 0.2, 0.2, 0.2, 0.2]

Answer 1 (Sense and Move)

for k in range(len(measurements)):
    p = sense(p, measurements[k])
    p = move(p, motions[k])
    print p

Robot is likely started in grid cell three, which is the right-most of the two red cells.

Question 2 (Sense and Move)

Can you modify the previous question so that the robot senses red twice. What do you think will be the most likely cell the robot will reside in?

How will this probability compare to that of the previous question?

Answer 2 (Sense and Move)

The most likely cell is cell four (not three! Don't forget we move after each sense).

This program is the essence of Google's self-driving car's Monte Carlo Localization approach.

image

Localization Summary (Localization Summary)

Localization involves a robot continuously updating its belief about its location over all possible locations. Stated mathematically, we could say the robot is constantly updating it's probability distribution over the sample space. For a real self-driving car, this means that all locations on the road are assigned a probability. If the AI is doing it's job properly, this probability distribution should have two qualities:

  1. It should have one sharp peak. This indicates that the car has a very specific belief about its current location.
  2. The peak should be correct! If this weren't true, the car would believe--very strongly--that it was in the wrong location. This would be bad for Stanley.

Our Monte Carlo localization procedure can be written as a series of steps:

  1. Start with a belief set about our current location.
  2. Multiply this distribution by the results of our sense measurement.

  3. Normalize the resulting distribution.

  4. Move by performing a convolution. This sounds more complicated than it really is: this step really involved multiplication and addition to obtain the new probabilities at each location.

Keep in mind that step 2 always increased our knowledge and step 4 always decreased our knowledge about our location.

Extra Information: You may be curious about how we can use individual cells to represent a road. After all, a road isn't neatly divided into cells for us to jump between: mathematically, we would say the road is not discrete it is continuous. Initially, this seems like a problem. Fortunately, whenever we have a situation where we don't need exact precision--and remember that we only need 2-10 cm of precision for our car--we can chop a continuous distribution into pieces and we can make those pieces as small as we need.

In the next unit we will discuss Kalman Filters, which use continuous probability distributions to describe beliefs.

Question 1 (Formal Definition of Probability)

Remember that a probability of zero means an event is impossible, while a probability of one means it is certain. Therefore, we know all probabilities must satisfy: 0 \leq P(x) \leq 1

image

Answer 1 (Formal Definition of Probability)

The answer is 0.8.

Question 2 (Formal Definition of Probability)

If the probability for x~1~ is: P(x~1~) = 0

What is the probability of x~2~ - P(x~2~) = ?

Answer 2 (Formal Definition of Probability)

  • P(x~2~) = 1

In both of these problems we used the fact that the sum of all probabilities must add to one. Probability distributions must be normalized.

Question 3 (Formal Definition of Probability)

Given:

image

Fill in the value of the fifth grid cell

Answer 3 (Formal Definition of Probability)

image

Bayes' Rule

Bayes' Rule is a tool for updating a probability distribution after making a measurement.

  • x = grid cell
  • Z = measurement

The equation for Bayes' Rule looks like this:

P(x|Z) = \frac{P(Z|x)P(x)}{P(Z)}

The left hand side of this equation should be read as "The probability of x after observing Z." In probability, we often want to update our probability distribution after making a measurement "Z". Sometimes, this isn't easy to do directly.

Bayes' Rule tells us that this probability (left hand side of the equation) is equal to another probability (right side of the equation), which is often easier to calculate. In those situations, we use Bayes' Rule to rephrase the problem in a way that is solvable.

To use Bayes' Rule, we first calculate the non-normalized probability distribution, which is given by: P(Z|x)P(x) and then divide that by the total probability of making measurement "Z" we call this probability our normalizer: P(Z)

This may seem a little confusing at first. If you are still a little unsure about Bayes Rule, continue on to the next example to see how we put it into practice.

image

Cancer Test Question

Suppose there exists a certain kind of cancer that is very rare:

  • P(C)=0.001 --> Probability of having cancer
  • P(¬C)=0.999 --> Probability of not having cancer

Suppose we have a test that is pretty good at identifying cancer in patients with the disease (it does so with 0.8 probability), but occasionally (with probability 0.1) misdiagnoses cancer in a healthy patient:

  • P(POS|C) = 0.8 --> Probability of a positive test if patient has cancer
  • P(POS|¬C) = 0.1--> Probability of a positive test in a cancer free patient "false positive"

Using this information, can you compute the probability of cancer, given that you receive a positive test:

  • P(C|POS) = ?

Answer: (Cancer Test)

image

0.79 out of 100 that despite the positive test results you have cancer. You can apply the same mechanics as before. The result of Bayes Rule, non-normalized is the product of the prior probability, P(C), multiplied by the probability of a positive test, P(POS|C):

  • P(C|POS)=

Plug in the probabilities:

  • p(C|POS) = 0.001 * 0.8 = 0.0008

Non-normalized probability for the opposite event, given a positive test:

. P(¬C|POS) = 0.999 * 0.1 = 0.0999

Normalized (the sum of the the probability of having cancer after a positive test and not having cancer after a positive test):

  • P(C|POS) + P(¬C|POS) = 0.1007

Dividing the non-normalized probability, 0.0008, by the normalized probability, 0.1007, gives us the answer: 0.0079

image

Theorem of Total Probability

Use a time index to indicate after and before motion:

image

Compute this by looking at all the grid cells the robot could have come from one time step earlier (t-1), and index those cells with the letter j which in our example ranges from 1 to 5. For each of those cells, look at the prior probability P(x_j^{t-1}) , and multiply it with the probability of moving from cell x~j~ to cell x~i~ , P(x~i~|x~j~). This gives us the probability that we will be in cell x~i~ at time t:

  • P(x~i~^t^)= \sum_j P(x_j^{t-1}) P(x_i|x_j)

This looks similar to the usual way of stating the theorem of total probability

  • P(A)= \sum P(A|B)P(B)

A represents a place, i at time, t. All the B's as possible prior locations. This is often called the Theorem of Total Probability.

image

Question 1 (Coin Flip Quiz)

Coin Toss: The probability of tossing a fair coin, heads (H) or tails (T) is: P(T) = P(H) = 0.5

If the coin comes up tails, you accept, but if it comes up heads, you flip it again and then accept the result. What is the probability that the final result is heads:

image

Answer (Coin Flip Quiz)

image

The probability of throwing heads in step two, P(H^2^), depends upon having thrown heads in step one, P(H^1^), which we can write as a condition, P(H^2^|H^1^)P(H^1^). Add the probability of throwing heads in step two with the condition, p(H^2^|T^1^)P(T^1^), of throwing tails in step one, multiplied by the probability of throwing tails in step one, P(T^1^). Written as:

  • P(H^2^) =P(H^2^|H^1^)P(H^1^)+P(H^2^|T^1^)P(T^1^)

The last term of this equation, P(H^2^|T^1^)P(T^1^) is the product of the probability of heads given a tail on the first throw with the probability of tails on the first throw. Since we are told that we stop flipping when we get a tails on the first throw, P(H^2^|T^1^)=0 and we can ignore this term. Our equation becomes: P(H^2^) = P(H^2^|H^1^)P(H^1^)

which is:

\frac{1}{4} = \frac{1}{2} * \frac{1}{2}

Note that the superscripts next to H and T in this problem indicate whether we are talking about the first or second toss. They are not exponents.

image

Note: We can also approach this problem as a probability tree, where the probability of moving down any branch is 1/2. We can see that the only way to arrive at heads is to proceed down the heads path twice.

Question 2 (Two Coin Quiz)

Say you have multiple coins, one is fair and the other is loaded. The probability of flipping heads for each coin is shown below.

  • fair coin --> P(H) = 0.5
  • loaded coin --> P(H) = 0.1

There is a 50% chance of flipping either the fair or the loaded coin. If you throw heads, what is the probability that the coin you flipped is fair?

image

Answer 2 (Two Coin Quiz)

The question, what is the probability of throwing a fair coin given that you observe H, can be written as:

  • P(F|H) = ?

Use Bayes' Rule because you are making observations. The non-normalized probability, which we will represent with a lower case p with a bar over it, of getting the fair coin is:

  • p(F|H) = P(H|F) P(F)
  • p(F|H) = 0.5 * 0.5

The non-normalized probability of NOT getting the fair coin, but getting the loaded coin is:

  • p(¬F|H) = P(H|¬F) P(¬F)
  • p(¬F|H) = 0.1 * 0.5

When you find the sum of these, the result is:

  • 0.25 + 0.05 = 0.3

Now, we divide our non-normalized probability by this sum to obtain our answer. \frac{0.25}{0.3} = 0.833

Conclusion (Conclusion)

This is what you've learned in this class:

  • Localization
  • Markov Localization
  • Probabilities
  • Bayes Rule
  • Total Probability

You are now able to make a robot localize, and you have an intuitive understanding of probabilistic methods called Filters. Next class we will learn about:

  • Kalman Filters

CategoryNotes