1 Introducción a la Robótica mecanismos avanzados Coordinación de Ciencias Computacionales, INAOE Dra Angélica Muñoz Dr Eduardo Morales [email protected] [email protected]

2 Localización La localización es la habilidad de un robot móvil para situarse en un ambiente Saber “donde está” le sirve para decidir que hacer y contruir mapas Generalmente se hace con ayuda de mapas y/o marcas, utilizando sus sensores (sonar, cámara, laser, odómetro, brújula, GPS, etc.) 2

3 Localización Dos tipos de localización: Localización continua: el robot se sitúa a lo largo de un trayecto Localización puntual: El robot se localiza únicamente cuando pasa frenta a marcas y las identifica. No son excluyentes y se han propuesto esquemas híbridos 3

4 Problemas Ruido en sensores: cámaras, sonares, laser, …. Tomar múltiples lecturas y hacer fusión temporal/multi-sensorial Aliasing: estados indistinguibles (mismas lecturas pero diferentes lugares). Localización basada en varias lecturas en el tiempo. Ruido en los efectores: errores odométricos (poca resolución, no alineación de llantas, diámetro desigual, variaciones de contacto). Uso de sensores adicionales (giróscopos) 4

5 Errores odométricos Los errores de orientación son mayores que los de distancia. 5

6 Seguimiento usando odómetro Con más rotaciones Con menos rotaciones 6

7 Seguimiento (localización) y errores odométricos Con Corrección Sin Corrección 7

8 Localización El problema de localización consiste en encontrar la configuración del robot en el espacio posible de configuraciones, o la probabilidad de cada posición: P (q) Se basa en la combinación de datos de los sensores y un mapa: P (q | s, M) 8

9 Localización Hay dos tipos principales de localización: Local: dada una posición conocida del robot, mantener su localización en el mapa Global: encontrar la posición sin conocimiento previo (o con conocimiento erróneo –“kidnapped robot”) 9

10 Localización Un paso importante en ambos tipos de localización es estimar la semejanza (match) entre los datos de los sensores y el mapa. Tres tipos: datos – datos datos – modelo modelo – modelo 10

11 Localización También podemos dividir los enfoques de localización en:  Ambientes estáticos o dinámicos  Pasivo o activo  Un robot o múltiples robots  Una hipótesis o múltiples hipótesis 11

12 Representación de creencias Mapa contínuo una hipótesis Mapa contínuo muchas hipótesis Mapa discreto de rejillas con todas las posiciones Mapa discreto de grafos con todos los nodos 12

13 Localización basada en Marcas Una forma común de localización es usar marcas (landmarks) en el ambiente Bajo una definición genérica de marca, casi todos los algoritmos de localización se pueden ver como basados en marcas Tipos de marcas: (i) artificiales y (ii) naturales 13

14 Ejemplos de marcas naturales

15 Triangulación Para ello primero se necesitan identificar las marcas y después hacer triangulación Dada la distancia (y/o orientación) de dos o más marcas, es posible determinar la posición (x,y) y orientación del robot 15

16 Incertidumbre Normalmente existe incertidumbre en la identificación y localización de las marcas, por lo que usar 2 o 3 marcas no siempre es suficiente Alternativas: Rangos en la posición de las marcas y más marcas Correlación Filtro de Bayes 16

17 Ejemplo de localización local usando varias marcas y triangulación 17

18 Correlación En vez de basarse en unas cuantas marcas, se pueden utilizar los sensores de rango (láser, sonar) y hacer una comparación “densa” entre los datos sensados y el mapa 18

19 Ejemplo 19

20 Localización Global Consiste en determinar la posición del robot sin tener una referencia de su posición anterior Dadas las lecturas de los sensores, normalmente hay varias posibles localizaciones, por lo que se tiene que desplazar para encontrar su posición real 20

21 Criterios de movimiento Movimiento útil Movimiento inútil

22 Localización Global Localización global Se pueden usar de nuevo varias marcas 22

23 Ejemplo

24 Localización de Markov Bajo este enfoque probabilista, el robot alterna sensado – movimiento Se puede implementar usando: Filtro de Kalman Filtros de partículas Filtro discreto 24

25 Modelo Gráfico 25

26 Localización de Markov 26

27 Ejemplo (Fox 98) Sensado Predicción Sensado 27

28 Localización de Markov Calcular una distribución de probabilidad Bel(q) para la ubicación del robot sobre todas las ubicaciones posibles q ( ) 28

29 Paso de sensado 29

30 Paso de movimiento 30

31 Algoritmo 31

32 Inicialización Si se sabe la posición inicial, Bel(X 0 ) es una delta o una gaussiana Si no se sabe es una distribución uniforme 32

33 Ejemplo (local) Estado inicial Predicción (u=der) Sensado (z=3) 33

34 Ejemplo (global) Estado inicial Predicción (u=izq) Sensado (z=4) 34

35 Ejemplo continuo (Kalman) 35

36 Problemas de complejidad Para 100 m 2 con celdas de 10 cm 2 y resolución de 1 o, q tiene 3,600,000 posibilidades Los pasos de sensado y movimiento son costosos Estrategia común: desechar Bel(q) ≈ 0 Otra posibilidad, restringir movilidad del robot (e.g., 8 orientaciones) 36