Visión artificial y Robótica Modelos de movimiento y mapas

Depto. de Ciencia de la Computación e Inteligencia Artificial

Contenidos ●

Sistemas de coordenadas

●

Localización de objetos en el espacio

●

Modelos de movimiento

●

Modelos geométricos para representación de mapas de entorno

Álgebra necesaria ●

Necesitamos herramientas geométricas para manejar las posiciones de los robots y de los objetos en el espacio: ●

●

●

Posición del robot dentro de un entorno Posición de un objeto dentro del mismo entorno Posición relativa del objeto con respecto al robot

Etiquetado de los ejes de coordenadas ●

●

● ●

Podemos espacios de dos o tres dimensiones El origen de un sistema de coordenadas se puede colocar en cualquier posición Regla de la mano derecha Utilizaremos más de un sistema de coordenadas

Coordenadas cartesianas ●

Un punto en el espacio se define mediante las coordenadas de su posición con respecto al origen del sistema ZZ

p

YY

XX

Localización de objetos ●

Objeto definido por cada uno de sus vértices Alternativa: Definir un nuevo sistema de coordenadas en el objeto. Las coordenadas de los vértices del objeto se definen con respecto al nuevo sistema.

Grados de libertad ●

●

●

Grado de libertad: cada uno de los movimientos (desplazamiento y/o rotación) que se pueden realizar Un cuerpo 3D tiene 6 grados de libertad (dof: degree of freedom): 3 rotaciones y 3 posiciones Un cuerpo 2D tiene 3 dof: 1 rotación y 2 posiciones

Matrices de transformación ●

Nos relacionan un sistema de coordenadas con otro (seis grados de libertad) ri=términos de  rotación ti=términos de  traslación

●

Definen un conjunto de transformaciones (rotaciones y traslaciones)

Coordenadas homogéneas ●

●

Una matriz de rotación 3x3 no nos da ninguna posibilidad para la traslación y el escalado Introducimos una cuarta coordenada donde w tiene un valor arbitrario y representa un factor de escala

●

Así podemos trabajar con matrices de transformación y puntos en el espacio

Matrices de transformación Matriz de translación:

Matrices de rotación:

Matrices de transformación II ●

●

Cuando queremos realizar varias trasformaciones sucesivas multiplicamos las matrices de transformación correspondientes Las matrices se aplican siempre de derecha a izquierda. El resultado es distinto si no aplicamos el sentido correcto

Transformación de coordenadas Disponemos de las coordenadas de un punto con respecto a un sistema. Para encontrar las coordenadas de ese punto con respecto a otro sistema de coordenadas, multiplicamos las coordenadas del punto por la matriz que relaciona ambos sistemas

Sistemas de coordenadas 2D ●

●

●

Vamos a tener dos sistemas principales: el global y el local Las coordenadas del robot cambian cuando se desplaza Debemos ser capaces de calcular las coordenadas de los objetos en nuestro entorno

Coordenadas en 2D ●

●

●

Tenemos un mundo en dos dimensiones (x, y) y una orientación (θ) (tres grados de libertad) Las tres coordenadas (x, y, θ) definen tanto una posición como un sistema de coordenadas Matriz de rotación:

Relación de los sistemas de coordenadas

Transformación de coordenadas ●

Sistema de coordenadas del robot:

●

Coordenadas del punto p1 con respecto a R

●

Coordenadas del punto con respecto a G

Ejemplo Tenemos el punto El sistema del robot

Transformación de coordenadas inversa Coordenadas del punto con respecto a R conocidas las de G:

Configuración y movimiento del robot ●

●

●

Para cualquier tipo de configuración, si una rueda tiene un radio r, podemos calcular el desplazamiento de dicha rueda usando 2πr Odometría es la técnica que calcula la distancia desplazada midiendo el giro de las ruedas Diremos que un robot es holonómico si es capaz de girar sobre sí mismo

Centro de curvatura instantáneo ●

●

●

●

Una rueda no puede desplazarse en la dirección de su eje de giro Las ruedas deben estar configuradas de tal manera que exista un punto (Centro de Curvatura Instantáneo CCI) sobre el que se realizará el giro del robot Dependiendo de la configuración del CCI tendremos distintos modelos de conducción. No todas las disposiciones de las ruedas permiten un movimiento correcto Cuando disponemos de varias ruedas, el giro del robot se consigue modificando alguna de las propiedades del giro de las ruedas (velocidad, orientación, etc.)

Ejemplo de CCI

Modelos de conducción ●

Vamos a detallar dos modelos de configuración de ruedas para robots móviles – Conducción

diferencial – Conducción síncrona ●

Existen más modelos – Conducción

dirigida: triciclo, biciclo – Modelo de Ackerman (vehículos) ●

Algunos modelos incorporan una rueda de castor que no afecta al cálculo

Conducción diferencial

Cinemática de la conducción diferencial ●

●

●

●

L es la distancia entre los centros de las dos ruedas R es la distancia desde el punto medio entre las ruedas y el CCI vr y vl son las velocidades de la rueda derecha e izquierda, respectivamente En cada instante, R, vr y vl pueden ser distintas

Cinemática de la conducción diferencial (II) Suma y resta de estas dos ecuaciones

Casos especiales: – vr

= vl R es infinito, el robot se desplaza en línea recta

– vr

= -vl R es cero, el robot gira sin desplazarse

Cinemática de la conducción diferencial (III) ●

Actualización de las coordenadas

Características de la conducción diferencial Es holonómica ● No es posible que el robot se desplace (sin girar) de manera perpendicular a los ejes de las ruedas ● Se suele utilizar una rueda castor para estabilidad ● Pequeñas variaciones en las velocidades de las ruedas (e incluso en el suelo) hacen que se produzcan errores en las trayectorias ●

Conducción síncrona

Cinemática de la conducción síncrona El CCI está siempre en el infinito, lo que simplifica el control: cambiando la orientación de las ruedas cambiamos la dirección

Características de la conducción síncrona ●

●

●

●

●

Todas las ruedas giran a la vez Se suele utilizar dos motores, uno para el giro de las ruedas que producen el movimiento hacia delante y otro que hace que el robot gire También es holonómica No es necesario que el robot gire para cambiar de dirección, sólo giran las ruedas También le afecta problemas en el suelo, pero en menor medida que el diferencial

Modelos de representación para mapas ●

El robot debe disponer de una representación interna del mundo por el que se mueve – Para

establecer qué partes del entorno no están ocupadas (espacio libre) – Para reconocer regiones, localizaciones u objetos en dicho entorno ●

Esta representación no debe ser exhaustiva, pero debe contener la suficiente información para que el robot no colisione

Mapas del entorno Contiene la posición de los obstáculos y otros objetos en el entorno ● Información de regiones no seguras o difíciles de atravesar ● Puede contener información de experiencias previas ● Puede ser utilizado para planificar tareas futuras ●

Representación de mapas ●

●

●

Descomposición espacial –

Realiza una discretización del entorno

–

No representa objetos sino el entorno en sí mismo

Representación geométrica –

Usan líneas, polígonos, puntos, etc.

–

Ahorran espacio en memoria

Representación topológica –

Más semejante a la de los humanos

–

No utiliza datos métricos, sino conectividad entre regiones: seguir el pasillo hasta encontrar la puerta y entonces girar a la derecha

Descomposición espacial ● ●

●

●

Suele hacer uso de una malla de ocupación Cada elemento (celda) de esta malla es una discretización del entorno que representa el grado de ocupación (ocupado, libre, parcialmente ocupado) por un obstáculo del espacio correspondiente en el entorno El número de celdas a utilizar vendrá dado por el tamaño del entorno y por la discretización permitida (dependerá del tamaño del robot, entre otros factores) Tres posibilidades: uniforme, quadtrees y exacta

Descomposición uniforme ●

●

El entorno se divide en un número regular de celdas, todas representando el mismo tamaño El valor de cada celda se puede calcular comprobando la cantidad de obstáculo que se encuentra en ella, tomando valores entre 0 (no obstáculo) y 1 (todo obstáculo)

Rejilla de descomposición uniforme

Descomposición mediante quadtrees ●

●

●

●

En la representación anterior muchas celdas que son adyacentes tienen el mismo valor Podemos intentar subdividir el espacio de forma recursiva en trozos cada vez más pequeños, realizando la subdivisión si una celda no se encuentra uniformemente rellenada Dicha subdivisión se realiza partiendo una celda en cuatro celdas iguales Los quadtrees ahorran espacio si existe gran cantidad de espacio libre o los obstáculos son de gran tamaño

Rejilla obtenida mediante quadtrees

Descomposición exacta ●

●

●

Los quadtrees particionan las celdas en cuatro partes iguales Existe otra forma de realizar la descomposición que no tiene la restricción de los quadtrees, sino que permite dividir el espacio libre (sin obstáculos) en polígonos regulares No existe una forma única de obtener esta división

Rejilla obtenida mediante descomposición exacta

Representación geométrica ●

●

●

●

Hacen uso de primitivas geométricas, puntos, líneas, polígonos, etc. almacenando sus coordenadas No necesitan tanta memoria para representar el mismo mapa Al trabajar con coordenadas permiten aplicar transformaciones sobre ellas (rotaciones, traslaciones, cálculo de intersecciones, etc.) Sin embargo, existen ciertas características de los objetos que no pueden ser representadas exactamente con este modelo, sino mediante una simplificación (sillas, papeleras, columnas, etc.)

Ejemplo de representación geométrica

Representación topológica ●

●

Al contrario que las dos anteriores representaciones, no utiliza datos métricos: los datos métricos pueden ser fuente de error debido a los sensores Es una representación más cercana a la humana: sigue el pasillo hasta que encuentres un cruce, gira a la derecha y es la tercera puerta a la izquierda

Representación en forma de grafo Este tipo de representación realiza una abstracción del entorno en forma de grafo ● Los vértices del grafo son lugares distintivos del entorno: puertas, cruces de pasillo, columnas, etc. ● Las aristas del grafo indican conectividad entre los vértices: la puerta 2 se encuentra a la derecha del cruce ●

Ejemplo de representación topológica Escalera 1

Puerta principal

Cruce pasillos

Despacho 1 Despacho 2 Despacho 3 Despacho 4