Instituto Polit�cnico Nacional
Instituto Politécnico Nacional
"La Técnica al Servicio de la Patria"

 

Boletín No. 51
1o. de noviembre de 2015




IMPLEMENTACIÓN DE ALGORITMOS GENÉTICOS EN SISTEMAS EMBEBIDOS

 

F. A. Chávez-Estrada1, C. A. Merlo-Zapata1, Ing. Jorge López Ortega1,
Dr. Juan Carlos Herrera Lozada1
1 Instituto Politécnico Nacional, CIDETEC. Área de Computo Inteligente.
Unidad Profesional Adolfo López Mateos. C.P. 07700, México, D. F., MÉXICO.

 

Resumen

En las últimas décadas, los investigadores han desarrollado un interés particular en los algoritmos evolutivos (AE) aplicados  en solucionar diversos problemas en la robótica y en las ciencias en general, donde se destaca la optimización numérica aplicada a la robótica. Las continuas investigaciones en aplicar algoritmos evolutivos en los sistemas de control son útiles para incrementar la confiabilidad y desempeño de: los sistemas de manufactura, procesos y robots de todo tipo, que consiste en aplicar un algoritmo genético en la optimización de una función la cual permite el desplazamiento (la trayectoria)  de un sistema mecánico. Este estudio describe la implementación de un algoritmo genético (AG) en un sistema embebido (SE) el cual controla servomecanismos por medio de la técnica de modulación por ancho de pulso (por sus siglas en ingles PWM) y se acciona el sistema mecánico que permitirá simular la optimización de la marcha de un robot, el movimiento de un actuador o controlar un proceso.
Palabras clave: Algoritmos genéticos y evolutivos, Marcha de robots, Aprendizaje, optimización, sistema embebido, función fitness.

I. Introducción.

Aplicar un algoritmo genético (AG) en un sistema de control de un robot, tiene por objetivo mejorar la marcha del sistema, además de que el sistema aprende y esto le permita mejorar su desempeño [1], (sea una función fitness nos genera las soluciones) generando soluciones y seleccionando las mejores soluciones; la implementación se lleva a cabo  a un sistema de control para observar y comprobar experimentalmente la mejora de su desempeño, tomando en cuenta las respectivas restricciones [2], ver figura 1. Este antecedente es descrito como la clave de los AE [3]. Por tanto, es un método alternativo en comparación de las técnicas de control clásico. El presente trabajo, se organiza de la siguiente manera: En la sección II desarrollo de un AG de propósito general. En la sección III la selección del sistema embebido dentro de las diferentes arquitecturas, el desarrollo y aplicaciones del sistema. En La sección IV consideraciones importantes. En la sección V pruebas y resultados de la implementación del sistema y finalmente conclusiones.

Figura 1. Diagrama de flujo implementación de AG.

 

II. Algoritmos genéticos

Estos algoritmos se basan en la teoría de la evolución de Darwin, en donde de forma natural se selecciona a los individuos de mejores características genéticas [3][4]. Este concepto se aplica en el desarrollo del AG, se describen los pasos:   
a) Se genera y evalúa la  población aleatoria resultado de una función.     
b) Selecciona y permite la reproducción de las mejores soluciones (cromosomas).              
c) Se genera una nueva población, hijos con mejores características como resultado de la optimización de la función, cruce, mutación, elitismo, siempre seleccionando las mejores soluciones o individuos. Estos pasos se repiten y con estas bases se diseña el AG, el cual es el resultado de una función optimizada [5].
2. Selección del sistema embebido. Es un sistema digital de arquitectura definida diseñado para aplicaciones específicas con alta confiabilidad (igual a una computadora) y de menor costo.
La computadora convencional es la herramienta utilizada para procesar los AG en algunos trabajos [6] dada la capacidad de procesamiento, sin embargo, para el caso de los sistemas embebidos se requiere de una análisis de la capacidad de procesamiento, de memoria e interface. Lo cual garantice que el desempeño del SE es capaz de emular en un sistema electrónico digital las señales eléctricas de control necesarias para interactuar físicamente con el sistema de control del robot.
La selección del sistema embebido (SE) se ha realizado bajo el esquema de que permite mejorar el rendimiento del sistema. Para esto,  en el ámbito comercial existen diversos productos como se debe seleccionar un procesamiento paralelo (varios núcleos en el sistema), velocidad, puertos de entrada y puertos de salida, lo cual permita conjuntar el hardware y software correctamente. Para el sistema embebido se debe considerar que incluya en su arquitectura las interfaces que necesita (CAD, PWM, DAC, TX-RX) con la finalidad de facilitar la implementación, además de tener en cuenta el lenguaje de programación, resulta conveniente que se elija un lenguaje que el usuario maneje, de modo que le facilite la integración [7].
3. Implementación del AG en el sistema embebido (ver figura2). Es la etapa en donde se conjunta el software y el hardware, primero se verifica que el software ejecute lo programado, es decir el AG se ejecute mostrando su desempeño y se vea reflejado en el sistema [8]. Esta etapa es una depuración continua para el software y hardware.

Figura 2. Implementación del algoritmo genético AG.

4. Aplicación del sistema (ver figura3). Una vez depurada la etapa anterior se libera el sistema para su experimentación. Posteriormente se implementa en un sistema de control general [4 y9].
Para este caso, como primera etapa se integra a un simulador que permitirá simular los movimientos de una articulación o extremidad de un robot con patas.

 

Figura 3. Aplicación del AG.

 

III. Desarrollo y aplicaciones

Los AG son usados en optimizar los movimientos de robots y actuadores, en la regulación, seguimiento de trayectoria, desplazamiento o marcha y evasión de obstáculos [10]. Los investigadores recurren a estos algoritmos por su confiabilidad y ser sistemas particulares de aprendizaje, que aseguran el desempeño y optimización de los sistemas a controlar.
Método general implementación de SE parallax+
A continuación se describe la implementación del sistema.

1. Se codifica y depura el AG en el lenguaje seleccionado.
2. Se selecciona el SE. Para su estudio, aprender su funcionamiento y conocer sus aplicaciones. Para este caso de la marca Parallax.
3. Se desarrolla el AG en lenguaje C y se implementa en el SE.

Se configura el computador con la Aplicación Simple IDE de la marca Parallax, dichas aplicaciones se pueden descargar de la página del fabricante [6]. La configuración para compilar en C, se muestra en la pantalla. Toda la información requerida para manejar el sistema embebido hardware y software, se encontrará en la opción de Ayuda del SimpleIDE User Guide (PDF)(ver figura4).

Figura 4. Aplicación Simple IDE.

4. Se implementa AG en el sistema embebido para formar el sistema mínimo.
5. Se implementa el sistema mínimo en el sistema de control.

El AG se ejecuta en el sistema embebido, se generan las super poblaciones que a través de una función evaluada, genera los valores optimizados, estos valores representan el ciclo de trabajo del PWM y generarán el desplazamiento en los servomecanismos.

 

IV. Consideraciones importantes

  1. Se deben caracterizar los servomecanismos, determinar los regímenes de alimentación (voltaje y corriente), frecuencia de operación y ciclo de trabajo del PWM. Determinados dichos parámetros se diseñan las interfaces necesarias y se conectan los puertos de salida a los servomecanismos y solo se ajusta vía programa la activación de señales del PWM.
  2. Por medio de una fuente externa de dos amperes regulados, se alimentan los servomecanismos, proporcionándoles el voltaje y corriente que requieren a plena carga (todos los sistemas y energizados al mismo tiempo). Es importante asegurar que la fuente este bien acondicionada y cumpla con el suministro de corriente de los servomecanismos.
  3. La señal de control de salida del sistema embebido, se conectan  a las entradas de control de los servomecanismos. Estas señales de control deben cumplir la frecuencia de operación y el ciclo de trabajo de los servos; este último parámetro se debe interpretar correctamente, el ciclo de trabajo del PWM es el tiempo de encendido y determina el desplazamiento del actuador o servomecanismo.
  4. Si el algoritmo corre una sola vez, el sistema ejecuta un ciclo y se verá reflejado en un movimiento del servomecanismo. Si el algoritmo corre en un  lazo, el sistema empieza a trabajar en un ciclo generando optimizaciones continuas que se verán reflejadas en un movimiento continuo del servomecanismo y en consecuencia del sistema.

V. Pruebas y Resultados

Los algoritmos genéticos son una alternativa para la solución de un problema (maximización, minimización de una función o proceso), el tiempo de procesamiento es la desventaja. Para implementar el AG en el sistema embebido, se programa en lenguaje C o C++. La primera restricción fue el tamaño de la memoria del SE, se optimizó el programa reduciendo el tamaño de la población generada de 2048 a 128 (o hasta 64), esto permite  correr el programa en el SE, se obtiene la optimización de la función y la generación de las señales de PWM.
La función optimizada es una caracterización del sistema y proporciona o contiene la información para los actuadores o servos. En esta aplicación la función optimizada es un string de bytes, es decodificada y almacenada en variables independientes, cada byte proporciona la información para cada Modulador de ancho por pulso (PWM), el valor del byte o variable determina el ciclo de trabajo de la señal PWM. El SE, genera las señales de control para los servomecanismos.
En una primera etapa, la habilitación de los servomecanismos se realiza de forma serie, y operan uno después de otro, esto es un fallo en el rendimiento del sistema (mayor tiempo de procesamiento). El requerimiento es activar algunos servos de forma paralela y     simultánea, necesarios para que el sistema opere correctamente. En el algoritmo rediseñado se obtuvieron tiempos de ejecución menores,  en comparación con las implementaciones secuenciales, se habilitan los núcleos del SE para ejecutar las señales PWM de manera paralela. Se busca que el tiempo de proceso del SE debe ser menor contra el tiempo de proceso en una computadora, sin embargo el consumo, tamaño y costo se reduce considerablemente. Un ejemplo, si la implementación del sistema corresponde a las articulaciones de un robot con patas, estas se muevan coordinadas y simultáneas. Para cumplir con lo anterior se habilita los núcleos del SE y de esta manera cumplimos con el requerimiento de generar de forma paralela las señales de PWM para los servomecanismos.

VI. Conclusiones

La aplicación de los AG, son de gran utilidad en Ingeniería como sistemas de experimentación en laboratorios de Control Automático, Mecánica, Robótica, Mecatrónica, Biónica, entre otros. El principio de operación de estos sistemas es similar al de cualquier otro con la ventaja que el sistema, calcula y evalúa los datos generados donde se pretende optimizar y mejorar una posición o tarea en particular. Este sistema puede ser una gran herramienta para facilitar el aprendizaje de conceptos relacionados con el control automático aplicando AG, estudiar técnicas de AG, algoritmos evolutivos y algoritmos bio inspirados para el control no lineal, control robusto, análisis de fricción, optimización,  que permita un mejor desempeño en dichos sistemas.
El presente trabajo también proporciona una guía de implementación de un AE en un SE aplicado en un sistema de control y abre el camino de investigación en esta área.  
Se ha encontrado una correcta implementación del AE en el SE, considerando una población pequeña y la arquitectura del SE para mejorar el rendimiento del sistema.
En este proyecto se comprobó que usar una arquitectura paralela para la ejecución del AG, se disminuye el tiempo de proceso.

Adecuar el programa software al hardware, en los AG, manejar bancos de registros que se pueden dejar corriendo de manera simultánea con la finalidad de mejorar el desempeño del sistema (disminuir tiempo de procesamiento). En el trabajo futuro se debe implementar el AG y diseñar sistemas con procesamientos paralelos aprovechando el hardware, para aumentar el rendimiento del sistema.

Referencias

  1. Gary Parker, William T. Tarimo, Michael Cantor; “Quadruped Gait Learning Using Cyclic Genetic Algorithms”; Department of Computer Science Connecticut College: New London, CT, USA; 6-2011.

  2. Chaohong Cai, Hong Jiang, “Performance Comparisons of Evolutionary Algorithms for Walking Gait Optimization “, Computer and Information College Hohai University Nanjing, 210000, China Robotics Laboratory, Hohai Universitry Wentian College.

  3. Lourdes Araujo “Algoritmos Evolutivos un Enfoque Práctico”, Editorial Alfaomega, Abril 2009.

  4. Francisco Barroso José Gómez Miguel Rodríguez Antonio Peregrín; “Optimización Evolutiva de la Locomoción de un Robot Bípedo”; Universidad de Huelva.

  5. Arranz de la Peña, Jorge, Parra Truyol, Antonio, “Algoritmos Genéticos” Universidad Carlos III.

  6. Tomoyuki Hosoyaand Kenichiro Nonaka; “Experiment of Integrated Steeringand DrivingForce Controller with Embedded CPU for Front Wheel Steering Vehicles”; Mechanical Systems Engineering, Tokyo City University, Tokyo, Japan.

  7. Fariboz Ahmadi, Reza Tati, Soraia Ahmadi, Veria Hossaini; “New hadware engine for genetic algorithms (Nuevo motor de hadware para los algoritmos genéticos)”. Islamic Azad University; Ghorveh, Iran; 2011 Fifth International Conference on Genetic and Evolutionary Computing.

  8. Disponible en: http://learn.parallax.com/propeller-c-simple-devices      
    Consultado en Septiembre de 2015.

  9. Pablo Gumiel Moreno, Yago Sáez Achaerandio, David Quintana Montero; “Implementación de técnicas de computación evolutivas a la programación automática de un robot”; Universidad Carlos III de Madrid; 18 de junio de 2009.

  10. Masaki Takahashi, Member, Takafumi Suzuki, Francesco Cinquegrani, Rosario Sorbello, Member, and Enrico Pagello, Member; “A Mobile Robot for Transport Applications in Hospital Domain with Safe Human Detection Algorithm”;  International Conference on Robotics and Biomimetics; 2009, Guilin, China.