Intro Robotica 1
Introducción a la Robótica Móvil
Eduardo Morales, L. Enrique Sucar Inteligencia Artificial
Intro Robotica 2
Contendio • ¿Qué es un robot? • Tipos de Robots • Partes de un robot • Arquitecturas • Percepción • Mapas del ambiente • Localización • Planeación de trayectorias • Mapeo y Localización Simultánea (SLAM) • Interacción Humano Robot
Intro Robotica 4
Un robot es ...
• “manipulador programable y multifuncional diseñado para mover materiales, partes, herramientas o dispositivos específicos mediante movimientos programados para realizar diferentes tareas” [Instituto de Robótica de América]
Intro Robotica 5
Un robot es ...
• “agente activo artificial cuyo ambiente es el mundo físico” [Russell y Norvig]
• “conexión inteligente de percepción a acción” [Jones y Flynn]
• “una máquina programable capaz de percibir y actuar en el mundo con cierta autonomía” [Sucar]
Intro Robotica 6
Tipos de Robots • Robots manipuladores (brazos) • Robots móviles • Robots “híbridos” (móviles con
manipulación) • Vehículos autónomos • Robots áereos (UAVs) • Robots submarinos • Robots humanoides • Robots hexápodos • ….
Intro Robotica 7
Partes de un Robot
Actuadores
Sensores
Comunicación
“Inteligencia”
Control
Potencia
Intro Robotica 8
Actuadores
• Dispositivos que permiten al robot modificar el medio ambiente
• Dos tipos principales: – Locomoción: cambiar la posición del robot
respecto al medio ambiente – Manipulación: mover otros objetos en el
medio ambiente
Intro Robotica 9
Sensores • Dispositivos que permiten
al robot percibir el medio ambiente y su estado interno
• Principales tipos: – “Propriception” – posición y
movimiento: • Codificadores en uniones
de manipuladores • Odometría en robots
móviles – Fuerza (bumpers) – Táctiles – Ultrasonido (sonares)
Intro Robotica 10
Sensores
– Cámaras – Fotorreceptores – Apuntadores láser – Telémetros láser – Sensores de energía – Brújulas – Kinect
Intro Robotica 11
Potencia
• Sistema de potencia que proporcionan la energía eléctrica para la operación de las diferentes partes: electrónica, motores, sensores, etc.
• Los robots manipuladores se pueden alimentar de las líneas eléctricas (fijos), mientras que los robots móviles normalmente se alimentan de baterías
Intro Robotica 12
Control
• Provee la interfaz entre el sistema de procesamiento del robot y sus sensores y actuadores
• Normalmente se realiza mediante una combinación de hardware y software
• Provee una serie de comandos (subrutinas) para los programas de alto nivel del robot (“inteligencia”)
Intro Robotica 13
“Inteligencia”
• Programas que permiten que el robot realice sus tareas
• Dependiendo del tipo de robot y de la complejidad y variedad de las tareas a realizar, se tienen diferentes tipos de programas
Intro Robotica 14
“Inteligencia” • Algunas tareas de un robot móvil:
– Integrar/interprertar la información de sus sensores – Navegación (evitar obstáculos, ir a cierto lugar - meta) – Planeación (decidir la serie de pasos para cumplir una o
más metas) – Construir modelos del ambiente (mapas) – Localizarse en el mundo (en el mapa) – Reconocer lugares y/o objetos – Manipular objetos – Comunicarse con otros agentes: computadoras, otros
robots, personas
Intro Robotica 15
Comunicación
• En diversas aplicaciones es necesario que el robot se comunique con otros agentes
• Tipos de comunicación: – Telecontrol: programación y control a distancia – Cooperación: comunicación con robots u otras
máquinas para realizar tareas conjuntas – Interacción humano-robot: comunicación con
personas para recibir comandos o dar información
Intro Robotica 16
Problemas fundamentales
• Obtener información del mundo: Percepción
• Saber donde estoy: Localización • Construir un modelo del ambiente: Mapeo
(SLAM) y Exploración • Decidir como alcanzar el objetivo:
Planeación • Seguir un plan para alcanzar el objetivo:
Navegación, Control
Intro Robotica 17
Arquitecturas de Software • “organización de la generación de acciones
a partir de las percepciones del robot” • “arreglo de módulos de software para un
robot móvil.” • Principales tipos:
– Arquitecturas deliberativas – Arquitecturas reactivas – Arquitecturas híbridas
Intro Robotica 19
Arquitecturas básicas
• Arquitectura deliberativa • Arquitectura reactiva
actuadores sensores
Intro Robotica 20
Arquitectura deliberativa
• Basada en el paradigma de sensa-planea-actua (SPA): – Se tiene un modelo completo (mapa) del
ambiente – Se construye un plan de acción para realizar
la tarea basado en el modelo – Se ejecuta el plan
Intro Robotica 22
Ejemplo: enfoque deliberativo
• Construir mapa del ambiente, incluyendo obstáculos y meta
• Generar un plan para ir de la posición inicial a la meta evitando los obstáculos
• Ejecutar el plan
Intro Robotica 23
Ejemplo: plan en un mapa de rejilla
• Plan: buscar una serie de acciones básicas que lleven al robot de la posición inicial a la meta
Intro Robotica 24
Arquitectura deliberativa
• Ventajas: – El tener un modelo del ambiente permite optimizar
las acciones para obtener el “mejor” plan • Limitaciones:
– Necesidad de un modelo preciso del ambiente – Altos requerimientos de cómputo y memoria – Dificultad de operar en un mundo dinámico o
desconocido – Reacción “lenta” a situaciones imprevistas
Intro Robotica 25
Arquitectura Reactiva
• En el enfoque reactivo hay una conexión directa de percepción a acción sin necesidad de un modelo del mundo
• Normalmente se considera una serie de niveles de comportamiento que realizan diferentes comportamientos en forma “paralela” (subsumption architecture)
Intro Robotica 26
Arquitectura basada en Comportamiento
Planear
Explorar
Deambular
Evitar objetos
sensores actuadores
Intro Robotica 27
Manejo de Conflictos • Al existir varios módulos en paralelo
pueden existir conflictos, que se resuelven dando prioridades a los diferentes comportamientos
• El comportamiento de mayor prioridad “suprime” los otros comportamientos
Deambular
Evitar objetos motores
Intro Robotica 29
Arquitectura Reactiva • Ventajas:
– Bajo requerimiento de cómputo, respuesta rápida
– Facilidad de desarrollo modular – No requiere un modelo del mundo
• Limitaciones: – Difícil de extender a tareas complejas – Limitaciones sensoriales pueden ocasionar
problemas al no contar con un modelo – No garantiza la mejor solución (óptimo)
Intro Robotica 30
Arquitecturas Híbridas
• Combinación de arquitecturas deliberativas y reactivas que intentan aprovechar ventajas de ambas
• Ejemplos: – Arquitecturas jerárquicas (3 capas) – Arquitecturas de pizarrón (blackboard) – Arquitecturas probabilísticas
Intro Robotica 31
Arquitectura de 3 capas • Tres componentes básicos:
– Capa de habilidades: Mecanismo de control reactivo (controlador)
– Capa de secuenciación: Mecanismo de ejecución de plan (secuenciador)
– Capa de planeación: Mecanismo deliberativo (deliberador)
• El secuenciador selecciona los mecanismos básicos de la capa de habilidades en base al plan de la capa de planeación
Intro Robotica 32
Arquitectura de 3 capas: ejemplo
Planeador
Secuenciador
sensores actuadores avanzar
sin chocar
girar ir a luz
Intro Robotica 33
Arquitectura de Pizarrón
• Conjunto de módulos o procesos que interactúan mediante un espacio de información común llamado pizarrón (blackboard)
• Cada módulo implemente una función específica y en conjunto todos realizan la tarea
• Todos los módulos pueden ver la información en el pizarrón y actúan en forma oportunística, de acuerdo al que más pueda aportar en ese momento (coordinador)
Intro Robotica 34
Arquitectura de Pizarrón
Obtener info.
sensores Ir a la meta
Evitar obstáculo control
planeación
PIZARRÓN
Intro Robotica 35
Arquitectura probabilística • Consideran la incertidumbre inherente en el
mundo real, tanto en la información de los sensores como en la ejecución de los actuadores
• Representan en forma explícita dicha incertidumbre mediante distribuciones de probabilidad: – Integración probabilística de sensores – Mapas probabilísticos – Acciones basadas en teoría de decisiones
(maximizar utilidad)
Intro Robotica 36
Arquitectura probabilística
sensores actuadores Fusión sensorial
Locali- zación
Nave- gación
Coordinación
Control (sensores/actuadores)
Robótica Probabilista, L. E. Sucar 37
Percepción del Ambiente • Los sensores permiten al robot percibir
su medio ambiente y su estado interno • Dos tipos básicos:
– Sensores de estado interno – Sensores de estado externo
• Desde otro punto de vista se pueden clasificar en: – Activos: emiten energía o modifican el
ambiente – Pasivos: reciben energía pasivamente
Robótica Probabilista, L. E. Sucar 38
Modelo del Sensor
• El modelo de un sensor provee una relación matemática entre la propiedad de interés (e) y la lectura del sensor (r)
r = f (e) • El modelo debe incluir la relación del
dispositivo físico y el ruido debido al sensor mismo (interno) y al medio ambiente (externo)
Robótica Probabilista, L. E. Sucar 40
Modelo del Sensor
P(Olaser|Z)
Z
Considerando la incertidumbre – modelo probabilístico
Robótica Probabilista, L. E. Sucar 41
Fusión sensorial • Una forma de reducir la incertidumbre es
combinando varios sensores, ya sea del mismo tipo o de diferente tipo: Fusión sensorial
• La forma más sencilla de combinar varios sensores es simplemente tomar el promedio de las mediciones
• Existen técnicas más sofisticadas de fusión como técnicas bayesianas y el filtro de Kalman
Robótica Probabilista, L. E. Sucar 42
Fusión sensorial
• Existen al menos 3 diferentes formas de fusión sensorial en robótica móvil:
1. Diferentes sensores 2. Diferentes posiciones 3. Diferentes tiempos
Robótica Probabilista, L. E. Sucar 43
Filtro de Kalman
• Las variables de estado (X) y observaciones (Z) tienen una distribución Gaussiana
• Las funciones de transición y observación son lineales: xt+1 = A xt + G wt zt = C xt + vt
• Donde A, C, G son constantes, y wt, vt son los términos que representan el ruido (media cero, varianza q, r) [En general, x y z son vectores y Q, R matrices de covarianza]
Robótica Probabilista, L. E. Sucar 44
Filtro de Kalman – Inferencia
• El problema básico es calcular la probabilidad posterior del estado, xt, dada la secuencia de observaciones, z1, …, zt
P( xt | z1, …, zt ) • Dado que las variables son Gaussians, sólo
necesitamos estimar la media y varianza de xt m(xt | z1, …, zt ) v(xt | z1, …, zt )
Robótica Probabilista, L. E. Sucar 45
Filtro de Kalman – Inferencia • Algoritmo recursivo:
– Actualización temporal-predicción P( xt+1 | xt) – Actualización de la observación P(xt+1 | xt, zt+1)
Xt Xt+1
Zt Z
T T+1
Xt Xt+1
Z Zt+1
T T+1
P(xt+1 | xt) P(xt+1 | xt , zt+1)
Robótica Probabilista, L. E. Sucar 46
Ejemplo – localización en 1-D
Distr. inicial.
Obs.
nueva distr.
Robótica Probabilista, L. E. Sucar 47
Mapas • Modelo del ambiente – generalemnte
se representa el espacio libre y el espacio ocupado (obstáculos) mediante una representación geométrica: un mapa
• Tipos de mapas: – Mapas métricos – Mapas topológicos – Mapas semánticos
Robótica Probabilista, L. E. Sucar 48
Mapas Métricos
• Se representa el espacio libre y/o obstáculos mediante medidas espaciales (geométricas).
• Dos formas básicas: – descomposición o rejillas – geométrico
Robótica Probabilista, L. E. Sucar 49
Descomposición espacial
• Se representa el espacio libre / obstáculos mediante una discretización en un con junto de celdas básicas, por medio de una rejilla de ocupación espacial (occupancy grids)
• Tipos de rejillas: – Binarias (bitmap) o probabilísticas – Uniformes o jerárquicas
Robótica Probabilista, L. E. Sucar 53
Mapa de Rejilla Probabilístico
• Cada celda tiene asociada una probabilidad de estar ocupada
Robótica Probabilista, L. E. Sucar 54
Mapas Topológicos
• Se considera el ambiente como una serie de lugares y conexiones entre dichos lugares.
• Esto se puede considerar como un grafo: – Nodos: lugares – Arcos: conexiones
• Se le puede incorporar información métrica al grafo – longitud y orientación de los arcos
Robótica Probabilista, L. E. Sucar 55
Ejemplo: mapa topológico
• Grafo de conectividad entre “cuartos”
Robótica Probabilista, L. E. Sucar 56
Ejemplo: mapa topológico
• Grafo de conectividad entre “cuartos”
Robótica Probabilista, L. E. Sucar 57
Mapas semánticos
• Se tiene asociado a un mapa métrico o topológico, una cierta semántica para los diferentes espacios/objetos en el mapa
• Esto permite una comunicación más natural con el robot en forma análoga a la comunicación entre personas (ve al a la oficina de Enrique …)
Robótica Probabilista, L. E. Sucar 59
Localización
• Hay dos tipos principales de localización: 1. Local (seguimiento) – dada una posición
conocida del robot, mantener su localización en el mapa
2. Global – encontrar la posición sin conocimiento previo (o con conocimiento erróneo – “kidnapped robot”)
Robótica Probabilista, L. E. Sucar 60
Seguimiento de la posición
• Odometría (“dead reckoning”) – se estima la posición integrando los movimientos (traslación y rotación) desde una posición conocida
• Esto introduce un error que es acumulativo, normalmente mayor para rotaciones
• Puede utilizarse en combinación con información de sensores externos
Robótica Probabilista, L. E. Sucar 61
Localización global
• Consiste en determinar la posición del robot sin tener una referencia de su posición anterior
• Dada las lecturas de los sensores, normalmente hay varias posibles localizaciones para el robot, por lo que tiene que en ocasiones tiene que desplazarse para encontrar su posición “real”
Robótica Probabilista, L. E. Sucar 62
Localización basada en Marcas
• Una alternativa para la localización es usar marcas y triangulación
• Se pueden usar más de 2 marcas y hacer un esquema de “votación” para hacer el sistema más robusto
• Existen diferentes tipos de “marcas naturales”, como esquinas, paredes, puertas, …
Robótica Probabilista, L. E. Sucar 65
Localización global
No se puede mostrar la imagen. Puede que su equipo no tenga suficiente memoria para abrir la imagen o que ésta esté dañada. Reinicie el equipo y, a continuación, abra el archivo de nuevo. Si sigue apareciendo la x roja, puede que tenga que borrar la imagen e insertarla de nuevo.
No se puede mostrar la imagen. Puede que su equipo no tenga suficiente memoria para abrir la imagen o que ésta esté dañada. Reinicie el equipo y, a continuación, abra el archivo de nuevo. Si sigue apareciendo la x roja, puede que tenga que borrar la imagen e insertarla de nuevo.
No se puede mostrar la imagen. Puede que su equipo no tenga suficiente memoria para abrir la imagen o que ésta esté dañada. Reinicie el equipo y, a continuación, abra el archivo de nuevo. Si sigue apareciendo la x roja, puede que tenga que borrar la imagen e insertarla de nuevo.
Robótica Probabilista, L. E. Sucar 66
Localización de Markov
• Bajo el enfoque probabilístico, el problema de localización global se puede resolver mediante el Filtro de Bayes (localización de Markov)
• El robot va alternando sensado/movimiento hasta poder determinar su ubicación
• Se puede implementar de diferentes formas: – Filtro de Kalman – Filtros de partículas – Filtro discreto
Intro Robotica 69
Ejemplo de localización de Markov (Fox 98)
• Filtro de partículas: P(ST | A1:T, O0:T)
S
S
Robótica Probabilista, L. E. Sucar 70
Cinemática
• La cinemática se refiere a los efectos de las acciones de control en la configuración del robot
• La configuración es la posición y orientación de un cuerpo, en este caso un robot en el espacio
Robótica Probabilista, L. E. Sucar 71
Espacio de configuraciones
• Grados de libertad: – Se refiere a los posibles movimientos de un
robot (X,Y,Z y rotaciones) – Para manipuladores, cada articulación provee
un grado de libertad (se requieren 6 para ubicar un objeto rígido en cualquier posición y orientación)
• Robots móviles: – Movimiento en el plano X-Y y rotación
Robótica Probabilista, L. E. Sucar 72
Configuración de un robot • La configuración de un robot se refiere a
la posición de sus todas articulaciones que definen su estado en el espacio
Θ1
Θ2
Robótica Probabilista, L. E. Sucar 73
Espacio de configuraciones • Espacio “n”-dimensional donde se ubica
cada grado de libertad del robot – el robot (orgáno terminal) se puede ver como un punto en este espacio
Θ1
Θ2
Robótica Probabilista, L. E. Sucar 74
Espacio de configuraciones
• Ejemplos: – Robot Scout: X, Y, Θ1 – Robot Nomad: X, Y, Θ1, Θ2
Para un robot móvil, la configuración del robot está dada por su posición X-Y y su orientación
Robótica Probabilista, L. E. Sucar 76
Ejemplo: espacio de configuraciones, de obstáculos y
espacio libre
Θ1
Θ2
Robótica Probabilista, L. E. Sucar 77
Planeación de Trayectorias
• Determinar una trayectoria en el espacio de configuraciones, entre una configuración inicial (inicio) y una configuración final (meta), de forma que el robot no colisione con los obstáculos y cumpla con las restricciones cinemáticas del robot
Robótica Probabilista, L. E. Sucar 78
Plan • Un plan es un conjunto de acciones
(operadores) que permiten a un agente (robot) ir de un estado inicial a un estado final o meta
• Los elementos básicos para hacer un plan son: – Estados (p. ej. Posición del robot),
incluyendo el estado incial y el estado meta
– Operadores: acciones que llevan de un estado a otro, Si Sj
Robótica Probabilista, L. E. Sucar 79
Ejemplo de Plan
• Considerando el mapa de rejilla: • Estados:
– posición X,Y en el mapa – Estado inicial: 0,0 – Estado meta (luz): Xm, Ym
• Acciones: – Movimiento a alguna de las celdas vecinas – X+1, Y+1, X-1, Y-1
Robótica Probabilista, L. E. Sucar 80
Ejemplo de Plan • Plan: buscar una serie de acciones básicas
que lleven al robot de la posición inicial a la meta
Robótica Probabilista, L. E. Sucar 81
Ejemplo: plan en el mapa topológico
• Plan = búsqueda de una trayectoria en el grafo, del nodo inicial al meta
Robótica Probabilista, L. E. Sucar 82
Programación dinámica
• Procedimiento iterativo (recursivo) para evaluar el costo de la trayectoria mínima de cualquier punto a la meta
• Se considera un ambiente discreto y un costo de moverse de un sitio (celda) a otro
• El algoritmo básico se conoce como “iteración de valor”
Robótica Probabilista, L. E. Sucar 84
Ejemplo – programación dinámica
0
1 1.4
1
1.4 1
2.4
2.4
2
2 3
3.4
3
3.4
3.4 3.8 4.8
4.4 4.8
4.4
4.4
5.8
4
6.8
5.8
5.4 6.4
6.8
6.8
7.8 8.2
7.8
7.8
8.2 9.2
8.8
8.8
9.2
10.2
9.8
Robótica Probabilista, L. E. Sucar 85
Ejemplo – programación dinámica
0
1 1.4
1
1.4 1
2.4
2.4
2
2 3
3.4
3
3.4
3.4 3.8 4.8
4.4 4.8
4.4
4.4
5.8
4
6.8
5.8
5.4 6.4
6.8
6.8
7.8 8.2
7.8
7.8
8.2 9.2
8.8
8.8
9.2
10.2
9.8
Robótica Probabilista, L. E. Sucar 86
Ejemplo de programación dinámica
Se considera un conjunto de celdas (road-map) libres de obstáculos obtenidas previamente
V(x,y) (pixel oscuros denotan valores altos) G I
Robótica Probabilista, L. E. Sucar 87
SLAM • El problema de construcción de mapas por el
mismo robot es uno de los problemas fundamentales en robótica móvil
• Este involucra el resolver concurrentemente (simultáneamente) dos problemas: – Construir un mapa (espacio libre/ocupado) del
ambiente – Localizarse en el mapa que se va construyendo
• Por lo que se conoce como “mapeo y localización simultáneos” – SLAM
Robótica Probabilista, L. E. Sucar 91
Mapas en el INAOE
Pasillo oficinas 2do piso Laboratorio de robótica
Reconocimiento de Personas
Localization and tracking
SIFT feature extraction
Face recognition
Video streaming
Results
Ademanes
• Útiles para la comunicación humano-robot • Comunicar información geométrica
– Ve para allá – Toma ese objeto – Qué es eso?
• Complemento a la voz – Para! – Ven!
RoboCup@Home • Torneo orientado a robots de servicio en casa
que es parte de la iniciativa de RoboCup • Alguna Tareas:
– Presentation – Who is Who – Follow me – Lost & Found – Shopping mall – Restaurante – Fire detection – Open challenge (mesero, rehabilitación, bailarín)