[REDES DE TELECOMINUCACIONES] Resumen de redes sensoras

Mobile Robot Navigation using a Sensor Network

Autores: Maxim A. Batalin y Gaurav S. Sukhatme

Link al artículo: http://nesl.ee.ucla.edu/courses/ee206a/2004s/submissions/project/Trail_PacBot/References/367.pdf

1. Introducción

La navegación es un problema fundamental en la robótica móvil. La navegación local tiene un principal problema y es evitar obstáculos. La navegación global tiene otro problema, el robot no puede ver el estado de su objetivo debido a la gran escala del terreno.

Un número de soluciones han sido propuestas entre las cuales se encuentran: pre-especificación de mapa, construcción de mapa en vuelo, topología basada en señalamientos, etc. El problema con estas soluciones es que no son del todo exactas, pues los sensores envían ruido.

Un tipo de navegación basado en el filtrado de Kalman es preciso métricamente, sin embargo en situaciones de pérdida no se puede recuperar, pues es una solución unimodal.

Algunas soluciones desarrolladas en los últimos basadas en la localización de Markov prueban ser multimodales y exactas. para representar distribuciones probabilisticas de distintos tipos, pero requieren mayor poder de procesamiento, y por lo tanto son imprácticas.

Otro tipo de solución es el uso de técnicas basada en muestras. En lugar de guardar y procesar distribuciones en el momento, se toman con anterioridad y se procesan, las muestras se guardan. Mediante algoritmos de localización de Markov se procesa parcialmente para no dejar todo del lado de los datos almacenados previamente.

Estas soluciones tienen distintas ventajas y desventajas, e incluso en algunos casos pueden fallar. La solución propuesta en el artículo utiliza redes sensoras para monitorear el entorno.

Algunas propiedades de esta solución se sumarizan como sigue:

1. La red sensora está previamente implementada en el entorno.
2. En adición a implementar los nodos de la red, el algoritmo calcula las distribuciones de portabilidad de transición P(s'|s,a) de un nodo s a s', cuando el robot ejecuta una acción a.
3. Los nodos están sincronizados en tiempo (no es necesario gran precisión).
4. El robot no tiene un mapa precargado o acceso a GPS, IMU o brújula.
5. No es necesario que el entorno sea estático.
6. El robot no realiza mapéos o localizaciones.
7. El robot no es sofisticado, los cálculos primarios se realizan distribuidamente en al red, solo se requiere que sepa evitar obstáculos.

2. Navegación probabilística

Para que el robot sea capaz de navegar por el entorno de un punto A a un punto B, debe ser capaz de seleccionar una acción que maximice las oportunidades de llegar a su destino, para poder medir el progreso y reconocer que ha llegado al punto B. La solución propuesta depende de una red sensora que determina las probabilidades de transición y consiste en dos etapas:

2.1 Planeando

Cuando el objetivo de navegación es especificado, el nodo más cercano al objetivo inicia una comunicación con el resto de nodos para determinar probabilísticamente cuál es el camino más óptimo.

1) Marco teórico - Valor de iteración: Considerando la red sensora como un grafo, donde los nodos son vértices. Se asume un número finito conjuntos de vértices S en la red y un número finito conjuntos de acciones A que el robot puede tomar. Dado un subconjunto de secciones A(s) ⊆ A, para cada dos vértices s,s' ∈ S en el grafo de la red y la acción a ∈ A(s) las probabilidades de transmisión P(s'|s,a) son determinadas para todos los vértices. Se muestra un ejemplo de distribución para un vértice por acción:

Para calular la mejor acción dado un vértice se utiliza un algoritmo de valor de iteración para el conjunto de vértices S - sg donde sg es el objetivo. La idea general es calcular las utilidades para cada estado y después tomar las acciones que determinen un camino hacia el objetivo con la máxima utilidad esperada. La utilidad se calcula incrementalmente:

donde C(s,a) es el costo asociado con el movimiento hacia el siguiente vértice. Usualmente el costo es escogido para ser un número negativo que es menor a -1/k donde k es el número de vértices. Racionalmente el robot debe "pagar" para tomar una acción, pero el costo no debe ser muy grande, de otra manera el robot optará por quedarse en su sitio. Dadas las utilidades, se calcula una política de acción para cada estado s como sigue:

El robot mantiene un modelo de transición probabilística para el grafo y puede calcular la política de acción para cada nodo para cualquier punto de destino.

2) Computación distribuida y procesamiento en red: Una solución más atractiva es calcular la política de acción distribuidamente en la red. La idea es que cada nodo en la red actualice su utilidad y calcule la acción óptima. Cuando el objetivo de acción es determinado, el nodo más cercano al objetivo inicia el cálculo inyectando un paquete "inicio de cálculo" en la red. Cada nodo redirecciona el paquete a sus vecinos usando llenado. Los nodos que reciben el paquete inician la utilidades y el valor del costo si el nodo particular es especificado como objetivo o no.

Esta técnica permite al robot navegar a través el entorno entre dos nodos en la red.

2.2 Navegación

La red sensora discretiza el entorno, en la imagen anterior, en el camino desde el nodo 1 al objetivo 5, el robot podría navegar del nodo 1 al 2, del 2 al 3 y así. Por lo tanto la navegación es acertada. Un nodo cuya dirección sugerida es seguida por el robot es llamado nodo actual. Inicialmente el nodo actual es el más cercano al robot.

El problema con esta solución es que los valores de intensidad de señal no son constantes o proporcionales de un radio a otro, de una topología a otra. Los resultados experimentales muestran que esta solución no es segura. Para predecir de forma segura donde se encuentra el robot, se desarrolló un algoritmo llamado Adaptative Delta Percent, basado en el procesamiento de los valores de intensidad de señal.

Considerar que el nodo actuales t. El nodo sugiere al robot en que dirección moverse. Asumiendo que antes de llegar al siguiente nodo el robot recibirá n muestras de valores de intensidad de señal para cada k nodos en los cuales el robot puede cambiar de acción. Después por cada uno de los k nodos:

1. Se calcula un promedio del máximo inicial Aim - un promedio de las primeras i muestras donde i << n.
2. Se calcula unpromedio corrido AR que es un promedio de j muestras consecutivas donde j << i.
3. Si R = AR/Aim < M, donde M es el valor umbral, entonces se regresa del algoritmo. Se pone R a la lisa LR.
4. Si y elementos consecutivos de LR están en orden no decreciente, se regresa del algoritmo, si no se repite del 2 a 4.

En caso de varios nodos regresen del algoritmo, se toma un nodo con el radio más pequeño.

3. Experimentos y discusión

Se realizaron experimentos  con un robot Pioneer 2DX con un rango laser de 180º para detectar y evitar obstáculos. La red de 9 nodos fue implementada dentro de un ambiente de cubículos y corredores largos. El escenario experimental de control de alarmas. Una alarma ocurre cuando un nodo  detecta un evento.

Puesto que el robot no tiene ningún dispositivo para posicionase, la dirección en la que el robot inicia es manualmente configurada. El robot mantiene la noción de dirección virtual mientras cambia de direcciones.

Los experimentos fueron los siguentes:

En todos los casos el robot pudo navegar a su destino.

4. Conclusión

4.1 Conclusión de los autores

Los autores concluyen que es factible utilizar robots que naveguen sin el uso de GPS o cualquier otro instrumento para posicionamiento. Lo que tratan de hacer es una red sensora que comunique al robot los eventos que suceden y mediante fuerza de señal, posicionar al robot creando una noción de posicionamiento virtual.

4.2 Conclusión personal

Aunque los experimentos muestran que el robot es capaz de moverse en la dirección señalada y al lugar correcto, las pruebas son hechas en un ambiente cerrado y con obstaculos sencillos, pues el área es una oficina llena de cubículos. Pienso que en un ambiente libre y con una distribución de nodos irregular podría fallar debido a que las intensidades de señal serían variables ademas de que habría ruido de por medio.

Posiblemente la red tendría que estar distribuida con distancias entre nodos muy pequeñas para generar intensidades de señal más altas.

Referecncias:
[1] Maxim A. Batalin, Gaurav S. Sukhatme, "Mobile Robot Navigation using a Sensor Network" (presentado en IEEE International Conference on Robotics and Automation, páginas 636 a 642, Abril 26 a Mayo 1, 2004)