Paralelismo y Robótica: El matrimonio Perfecto

por R. Theron, F. J. Blanco, B. Curto, V. Moreno y F. J. García
Traducido por Hector Perez-Gonzalez

Introducción

A pesar de los grandes avances en computación, estamos lejos aún del mundo soñado por Asimov en 1942, donde esboza un mundo dominado por robots. Sin embargo, la robótica es un área de estudio científico de rápido desarrollo, y muy sofisticados robots están siendo desarrollados. Incluso LEGO anuncia “MindStorms Robotics Invention System le permite diseñar y programar robots reales que hacen lo que usted quiere que hagan"

Actualmente, el campo de la Robótica se enfoca en la creación de Robots autónomos. Los Robots autónomos son programados para lograr un objetivo específico, el cual requiere el procesamiento de cierto conjunto de tareas con diversos niveles de habilidad y conocimiento [8]. Usando una especificación de alto nivel, el objetivo es formular una secuencia de movimientos inteligentes. La ejecución de esos procedimientos requiere de técnicas de procesamiento paralelo para manejar la pesada carga computacional. [2]. A pesar de los significativos avances en la velocidad de procesamiento, los procesadores secuenciales están lejos de proveer la suficiente capacidad computacional requerida por los sistemas de planeación robótica Las modernas tecnologías VLSI proveen una oportunidad única para salvar esta brecha a través del uso de computación paralela [3].

Muchos robots deben ser capaces de desempeñar planeación de rutas [8], que involucra la búsqueda del camino óptimo a partir de una ubicación inicial a una deseada, evitando colisiones. Algunos algoritmos de planeación de movimientos paralelos han sido propuestos para solucionar esto. [6].

Este artículo aborda el tema de cómo el paralelismo beneficia a la Robótica. Primeramente, presentamos el problema del entendimiento de un ambiente de obstáculos. A continuación presentamos un procedimiento de evaluación para determinar configuraciones y posiciones factibles con un análisis de oportunidades para aprovechar los beneficios del procesamiento paralelo. Después, se presenta un caso de estudio para explicar la implementación paralela que desarrollamos. Finalmente se presentan los resultados y conclusiones principales.

Conocimiento del Ambiente

Con el objetivo de construir una secuencia de movimientos que eviten las colisiones, el ambiente o espacio de trabajo debe ser entendido. Después de recibir una descripción del ambiente de trabajo, el robot debe evaluar como desplazarse entre los puntos origen y destino, tomando en cuenta las restricciones mecánicas y los obstáculos. Existen algunas técnicas para interpretar el espacio de trabajo. El enfoque planeación global, requiere el conocimiento total del ambiente. Una manera de “conocer” el ambiente completo usa el espacio de configuración (Espacio-C), que representa simplemente el espacio de trabajo del robot, donde la posición y orientación del robot es definida por un punto individual [9]. Este artículo se concentra en la búsqueda del Espacios-C libres formados por las configuraciones del robot que no producen colisiones con los obstáculos. Mas tarde esto será usado para la planeación de sus movimientos. La evaluación del Espacio-C es computacionalmente intensivo. Se han incorporado técnicas avanzadas de procesamiento [6] para lograr la toma de decisiones en tiempo real.

Curto y Moreno [4] proponen un formalismo matemático para el cálculo de obstáculos-C (la representación de un obstáculo en el Espacio-C) a través de la evaluación de una convolución de dos funciones, una describe el robot A, y la otra describe los obstáculos B. El Teorema de Convolución establece que las transformadas de Fourier pueden ser usadas para efectuar la convolución. Una expresión general, válida para cualquier tipo de estructura robótica es mostrada en Figura 1 (siendo CB la función que describe los Obstáculos-C).

Integración del producto punto de dos transformadas de Fourier (producto de convolución).
Figura 1. Expresion general para la evaluación del Espacio-C

En la siguiente sección, esta expresión general es analizada en búsqueda de oportunidades para introducir paralelismo

Hacia una Evaluación mas Rápida

Con el Objetivo de solucionar la ecuación mostrada en la Figura 1, necesitamos evaluar la integral de un producto de transformadas de Fourier para numerosas configuraciones y valores de variables de espacio. La solución requiere de la evaluación de Nm-r operaciones, donde N es la resolución elegida para describir el espacio de trabajo discreto, m la dimensión del Espacio-C y r la dimensión de la transformada de Fourier. Cuando no existe la convolución, la integración efectuada para las coordenadas espaciales provee nuevas oportunidades para la paralelización en general. En general se pueden encontrar tres niveles de paralelismo: Nm-r N m Espacio-C r Para clarificar, consideremos un robot móvil 2D. Este robot tiene tres variables de configuración, (x,y), que describen la posición, que convoluciona con las coordenadas del espacio de trabajo y theta, que define el ángulo de rotación (orientación) y no convoluciona. Entonces, dos niveles de paralelismo serían posibles, el nivel de la transformada de Fourier, y el nivel de la variable de configuración (por la acumulación de productos de convoluciones sobre los valores de theta). (x,y) theta theta

Los tres niveles previamente citados son válidos para cualquier estructura robótica, y soluciones diferentes pueden sacar provecho de uno, dos o de los tres niveles de paralelismo en un momento dado ,  produciendo mas rápidos algoritmos de evaluación del Espacio-C. A continuación se describe el diseño de diferentes enfoques que toman ventaja de uno, dos o tres niveles de paralelismo. Un tradicional enfoque Maestro-esclavo es propuesto para cada solución

En la Figure 2, el nivel FFT es explotado. El maestro pide a los esclavos desempeñar la computación de las transformadas de Fourier y ellos proceden en paralelo usando el conocido algoritmo FFT

Cada Transformada Rápida de Fourier es llevada a cabo por los procesos esclavos
Figura 2. Solución a nivel FFT

LaFigura 3 muestra el nivel de variables de configuración donde, una vez más hay un maestro y n procesos esclavos, el maestro pide a los esclavos evaluar una parte del Espacio-C, esto es, el producto de convolución para un valor de la variable de configuración para cada esclavo. Entonces los resultados parciales son recopilados y el Espacio-C es construido.

Producto de Convolución para cada valor de la variable de configuración es es obtenida por un proceso esclavo
Figure 3. Solución a nivel Variables de Configuración

En otra solución propuesta, el maestro colecta los productos de convolución de cada variable espacial obtenidos por los esclavos.

Hasta el momento, solo un nivel de paralelismo ha sido explotado, pero puede obtenerse una solución donde dos, o incluso tres niveles son tomados en cuenta. Estas soluciones paralelas son diseñadas para trabajar en ambientes con suficientes procesadores para que en ellos se ejecute un número significativo de procesos. Entonces podemos tener soluciones FFT-Configuración, FFT-Espacial, Configuración-Espacial y FFT- Configuración-Espacial. Un modelo mas complejo es ilustrado en la Figura 4 donde una solución de tres niveles es explotada. Los procesos sub-maestros organizan las comunicaciones de resultados parciales, que son entonces comunicados al maestro. Este método puede ser visto como una solución de nivel individual anidado.

Productos de convolución acumulados maestros llevados a cabo por Sub maestros que dan los productos de convolución a sub-sub-maestros que dan FFTs a esclavos.
Figura 4. Solución de tres niveles

Debe notarse que estas soluciones no consideran nada acerca de la validación de modelos, estas cuestiones pueden ser asociadas con la existencia de cuellos de botella, disponibilidad de memoria y problemas de sincronización por nombrar algunos. El lector solamente necesita imaginar lo difícil que sería alcanzar un rendimiento óptimo en el caso del modelo presentado en Figura 4, donde la sincronización de múltiples procesos de diferentes tipos (maestro, sub-maestros, sub-sub-maestros, escalvos) es necesaria, y lo fácil que sería para alguno de ellos el entrar a un largo tiempo de espera disminuiría el desempeño general. Los detalles de estas cuestiones se dejan a un artículo más profundo.

Un caso de Estudio : Implementando el Algoritmo Paralelo

Hemos implementado el algoritmo paralelo para evaluar el espacio de configuración de robot móvil, que se mueve en un espacio 3D parcialmente ocupado por obstáculos. Esta sección se concentra en el análisis para evaluar el éxito de nuestra implementación paralela.

El robot tiene un movimiento plano de tal manera que su posición es definida por tres variables de configuración (xr, yr, thetar) , como se describe en [4], la expresión para evaluar el Espacio-C es mostrada en Figura 5.

Integración de un producto de convolución para un robot móvil 3D.
Figura 5. Expresión para la evaluación del Espacio-C de un robot móvil 3D

Surgen entonces tres posibilidades para aprovechar el paralelismo inherente. Primero, el algoritmo consiste de una serie de operaciones básicas efectuadas iterativamente, una por cada una de las posibles orientaciones del robot thetar, (a nivel de variables de configuración). Segundo, cada orientación necesita acumular los productos de convolución para cada plano z (nivel de variable espacial). Estos cálculos son independientes, por consiguiente, pueden realizarse en paralelo. Estos resultados intermedios son integrados para formar el resultado final. Claramente, esta es una instancia del modelo de paralelismo de datos[1].

A continuación se describen las operaciones que llevan a cabo los dos tipos de procesos

Maestro

Después de algunos pasos de inicialización, el maestro comunica a cada uno de los esclavos, las tareas que deben ser desarrolladas, una vez que el maestro recibe el resultado (la parte del Espacio-C considerado) del esclavo, aquel asigna una nueva tarea. Finalmente, el maestro indica a los esclavos que no se requieren ya mas cálculos. Durante este proceso, el maestro construye una matriz tridimensional que representa al Espacio-C. Espacio-C Espacio-C

Esclavos

El proceso esclavo como ya mencionó, es responsable del cálculo de la porción del Espacio-C correspondiente a una orientación del robot. El esclavo debe saber cual orientación debe considerar (determinado por el maestro con el número de tarea) para el calculo de la porción del Espacio-C. De este modo, el esclavo construye el bitmap (mapa de bits) del robot para esa orientación y un plano z, finalmente obtiene su FFT. Mas tarde, obtiene el producto punto-a-punto de esa FFT con el espacio de trabajo transformado que el maestro ha provisto. Este procedimiento se repite el número de veces determinado por el punto más alto del robot móvil, y los resultados son agregados (la acumulación del nivel de variables espaciales, que en este caso, como ya se mencionó, no esta siendo explotado). A continuación, éste aplica la transformación inversa del resultado acumulado para obtener la porción del Espacio-C. Este rusultado intermedio es el que cada esclavo, en su turno le envía al maestro, para luego esperar otra tarea o una señal de fin de ejecución. Espacio-C Espacio-C z Espacio-C

Resultados

Se han usado dos diferentes plataformas para validar la implementación: una computadora Silicon Graphics Origin 200 con cuatro procesadores MIPS R10000 y 768 Mbytes de memoria, y cuatro workstations (PII 266Mhz con 64Mbytes de memoria) conectadas a través de una red FastEthernet. Hemos usado MPI para desarrollar ambas implementaciones. Los resultados son similares, sin embargo en el caso de las workstations conectadas en red se presentaron más dificultades debido a problemas de comunicación. Los siguientes resultados se refieren únicamente a los experimentos desarrollados en el sistema multiprocesador con memoria compartida (origen 200)

Con el objeto de trabajar con el algoritmo FFT empleado para la necesaria evaluación de las transformadas de Fourier 2D, se han utilizado tres discretizaciones del espacio de trabajo 3D: 64 x 64 x 64, 128 x 128 x 128 y 256 x 256 x 256 (Todas ellas son potencias de dos como lo requiere FFT). Elegimos usar la implementación FFTW del algoritmo FFT desarrollado en el MIT (Instituto Tecnológico de Massachussets MIT - por sus siglas en inglés) que presenta un buen desempeño y permite la generación de código paralelo.

En la Figura 6a, se muestra un robot haciendo frente a tres obstáculos, es claro que el robot tiene un reducido conjunto de opciones para circunnavegar. El Espacio-C correspondiente se muestra en Figura 6b, donde dos pequeños conjuntos de configuraciones libres de colisión aparecen dentro de un gran Obstáculo-C.

Basado en la experiencia presentada en [10], se obtienen los mejores resultados cuando un procesador dobla a ambos maestro y esclavo. La Figura 6.c ilustra la presencia del maestro desocupado (rojo) la mayor parte del tiempo mientras que los cuatro esclavos se encuentran trabajando (verde) la mayoría del tiempo. Los siguientes resultados se han obtenido de esta configuración específica


Figura 6. Resultados para un espacio de trabajo dado

En las tablas Tabla 1, Tabla 2, y Tabla 3, se muestra los tiempos de cálculo obtenidos con la ejecución del algoritmo paralelo de granularidad fina y para el algoritmo secuencial considerando diferentes resoluciones y alturas del robot. Se observa una tendencia del incremento de velocidad como una función de la resolución. Muy probablemente, la tendencia proviene de los períodos de tiempo ocupados en comunicación cuando el tiempo dedicado a cálculos es pequeño, como en caso de la resolución 64x64 de los bitmaps. La Tabla 3 muestra una mas pequeña mejoría en el desempeño debido a limitaciones de memoria

Sequencial Paralelo Altura del Robot Incremento de velocidad
0.99  0.73  5  1.36 
3.34  1.23  20  2.72 
7.30  2.40  45  3.04 
10.51  3.21  64  3.27
Tabla 1. Tiempos de ejecución (segundos) para resolución 64 x 64
Tabla 1. Tiempos de ejecución (segundos) para resolución 64 x 64

Sequencial Paralelo Altura del Robot Speedup
14.30  5.22  10  2.74 
52.81  15.21  40  3.47 
85.05  23.45  64  3.63 
164.06  44.34  128  3.70
Tabla 2. Tiempos de ejecución (segundos) para resolución 128 x 128
Tabla 2. Tiempos de ejecución (segundos) para resolución 128 x 128

Sequencial Paralelo Altura del Robot Incremento de velocidad
252.45  76.67  15  3.29 
376.54  107.51  30  3.50
792.70  226.77  64  3.50
Tabla 3. Tiempos de ejecución (segundos) para resolución 256 x 256
Tabla 3. Tiempos de ejecución (segundos) para resolución 256 x 256

Como la Figura 6c y los Incrementos de velocidad reflejan, el desempeño de las aplicaciones es óptimo: los procesos esclavos están trabajando la mayor parte del tiempo (verde) y el proceso maestro esta esperando (rojo) los resultados parciales de la tareas asignadas y recibiendo resultados (Amarillo).

Conclusiones

Se han presentado el diseño e implementación de los algoritmos para evaluar el Espacio-C del robot en paralelo. Los algoritmos se basan en la evaluación de las ecuaciones expresadas bajo un formalismo matemático general. Un robot móvil tridimensional es considerado como una aplicación práctica. Las limitaciones del ambiente de prueba impulsan el desarrollo e implementación de una solución óptima al nivel de variables de configuración. Se han desarrollado diferentes experimentos en donde los Incrementos de velocidas han sido muy aceptables. El caso de estudio presentado provee resultados razonables que podrían extrapolarse a estructuras robóticas más complejas. Podemos esperar que estructuras más complejas puedan ser diseñadas bajo los lineamientos del algoritmo paralelo estudiado en este artículo. Espacio-C

Referencias

1
Andrews, G. R. Concurrent Programming, The Benjamin/Cummings Publishing Company, Inc., 1991.
2
Barbosa, Valmir C., An Introduction to Distributed Algorithms, The MIT Press., 1991.
3
Bilardi, G., Hornick, S. and Sarrafradeh, M., "Optimal VLSI Architectures for Multidemensional DFT", ACM Comp. Architecture News, Vol. 19, No. 1, pp. 45-52, 1991.
4
Curto, B. and Moreno, V., "A Mathematical Formalism for the Fast Evaluation of the Configuration Space", In: Proc. of the IEEE Sym. on Comp. Int. In Rob., 1997.
5
Foster, I., Designing and Building Parallel Programs. Concepts and Tools for Parallel Software Engineering, Addison-Wesley P. C., 1994. http://www-unix.mcs.anl.gov/dbpp/
6
Henrich D., "Fast Motion Planning by Parallel Processing. A review", Journal of Intelligent and Robotic System, Vol 20, No 1, pp. 45-69, 1997.
7
Kavraki, L., "Computation of Configuration Space Obstacles Using the Fast Fourier Transform", IEEE Transactions on Robotics and Automation, Vol. 11, No 3, pp. 408-413, 1995.
8
Latombe, J. C., Robot motion planning, Kluwer Academic Publishers. Boston. MA, 1991.
9
Lozano-Pérez, T., "Spatial planning: a configuration space approach", IEEE Transactions on Computers, Vol. 32, pp. 108-120, 1983.
10
Theron, R., Blanco, F. J., Curto B., Moreno V., " Evaluation of the Configuration of Robots Upon a Distributed Computing System", Proceedings of the IEEE-IFAC European Control Conference, 2001.

Apéndice A - Acrónimos y definiciones

Configuration Space (C-space) - Espacio de Configuración (Espacio-C) - Cualquier tipo de Robot, para realizar un movimiento, requiere una serie de acciones de sus componentes móviles. El movimiento de la estructura completa del robot se efectúa por medio del movimiento de de cada una de sus partes móviles. Por consiguiente, cuando se ejecuta un movimiento, el aspecto fundamental descansa en la variación del grado de libertad (DOF , por sus siglas en ingles Degree of Freedom) de cada parte móvil. El estudio de cómo el movimiento de los elementos móviles afecta el movimiento del robot se encuentra bajo el dominio de la cinemática, que provee la posición de todos los puntos del robot para cada configuración. Es posible, en lugar de trabajar con todos esos puntos, trabajar con el (Espacio-C) que describe sin ambigüedad cada configuración dado un punto de cada DOF. Configuration Space (C-space) Espacio-CEspacio-C

Convolution Theorem - Teorema de Convolución - Existen dos maneras de expresar el teorema de convolución Teorema: 1) La transformada de Fourier de una convolución es el producto de transformadas de Fourier. 2) La transformada de Fourier de un producto es la convolución de transformadas de Fourier. Las convoluciones pueden ser difíciles de calcular directamente, pero frecuentemente su cálculo se facilita usando Transformadas de Fourier y multiplicaciones.

DFT (Discrete Fourier Transform) - DFT (Transformada de Fourier Discreta) - Es el algoritmo numérico para calcular la Transformada de Fourier. La computación numérica de la Transformada de Fourier de f(t) requiere valores discretos de f(t). En suma, la computadora solo puede calcular la Transformada F(s) para valores discretos de s.

FFT (Fast Fourier Transform) - Transformada Rápida de Fourier - La Transformada Rápida de Fourier es un algoritmo DFT desarrollado por Tukey y Cooley in 1965 que reduce el número de computaciones de N2 a N log N. Existen básicamente dos tipos de Algoritmos FFT Tukey-Cooley en uso: pérdida-en-tiempo y pérdida-en-frecuencia. El algoritmo se simplifica si se selecciona N como una potencia de 2, pero esto no es un requerimiento.

FFTW (Fastest Fourier Transform in the West) - Transformada Rápida de Fourier en el Occidente - FFTW es una biblioteca de subrutinas en lenguaje C para calcular la Transformada de Fourier Discreta para una o mas dimensiones, de datos reales y complejos y para un tamaño arbitrario de la entrada. FFTW es típicamente más rápido que otras implementaciones FFT disponibles públicamente e incluso compite con bibliotecas comerciales. El paquete FFTW fue desarrollado por Matteo Frigo y Steven G. Johnson. http://www.fftw.org

Fourier Transform - Transformada de Fourier - En esencia, descompone o separa una función en ondas senosoidales de diferente frecuencia cuya suma resulta en la función original

Load balance - Balance de Carga - El desempeño de cualquier algoritmo de implementación paralela depende críticamente del balance de carga (incluyendo lo relacionado con carga de trabajo y factores relacionados con diseño) entre los diferentes procesadores paralelos. La idea es mantener ocupados a los procesadores la mayor parte del tiempo. El balance de carga describe la medida en que las tareas (unidades básicas de trabajo asignadas a un procesador) están bien distribuidas entre los diferentes procesadores. Sorpresivamente no existe en la literatura, un consenso acerca de la definición de carga de trabajo

Master-slave paradigm - Paradigma Maestro-Esclavo Una tarea de maestro central recibe la responsabilidad de la asignación del problema. Repetidamente, cada esclavo solicita del maestro una tarea y la ejecuta. Los esclavos pueden también enviar nuevas tareas al manejador para reasignarse a otros esclavos. La eficiencia de esta estrategia depende del número de esclavos y los costos relativos en la obtención y ejecución de problemas.

MPI - The Message Passing Interface Standard. La interfaz estándar de paso de mensajes. Un acopio multilateral de usuarios, vendedores e investigadores de computación paralela han realizado la especificación de una interfaz de comunicación completa entre procesos basada en mensajes. El estándar MPI denota una auténtica portabilidad para programas paralelos, define la infraestructura necesaria para productos de software de terceros y provocará una mayor proliferación de aplicaciones paralelas. Para un desarrollador de aplicaciones paralelas, la semántica específica de la interfaz de comunicación y su esperada popularidad no será mas un factor para la elección de un ambiente o un producto especial. Los usuarios y compradores pueden enfocarse en otros factores como la eficiencia de la implementación y las herramientas de desarrollo.

Speedup - Incremento de velocidad Incremento de velocidad es el cociente o relación entre la mejor aplicación secuencial para resolver un problema y el tiempo tomado por un algoritmo paralelo para resolver el mismo problema en n procesadores

VLSI (Very Large Scale Integration) - Integración a Muy Grande Escala El proceso de colocar miles ( o cientos de miles) de componentes electrónicos un chip individual. Casi todos los modernos chips emplean arquitecturas VLSI o ULSI (Integración a Ultra alta Escala ULSI por sus siglas en ingles - Ultra Large Scale Integration) La linea entre VLSI y ULSI es vaga.

Reconocimientos

Este estudio fué parcialmente apoyado por la Junta de Castilla y León a través del proyecto de investigación SA02-00F . A los autores les gustaría agradecer a todos aquellos que hicieron comentarios y sugerencias acerca de este artículo

Biografía

Roberto Theron Es candidato a Doctor en Ciencias de la Computación en la Universidad de Salamanca, España. Sus intereses de investigación incluyen Programación paralela y Robótica. En 1999, el inició su trabajo como profesor del departamento de Computadoras y Automatización de la Universidad de Salamanca.

Francisco Javier Blanco Es candidato a Doctor en Ciencias de la Computación en la Universidad de Salamanca, España. Sus intereses de investigación incluyen la Robótica, particularmente en el área de planeación de rutas. En 1999, el inició su trabajo como profesor del departamento de Computadoras y Automatización de la Universidad de Salamanca.

Dr. Belen Curto, Profesor de la Universidad de Salamanca con interés de investigación principal en Robótica.

Dr. Vidal Moreno, Profesor de la Universidad de Salamanca con interés de investigación principal en Robótica.

Dr. Francisco José Garcia, Profesor de la Universidad de Salamanca con interés de investigación principal en Ingeniería de Software

Last Modified:
Location: www.acm.org/crossroads/espanol/xrds8-3/prm3.html