Artículo Original/Original Article

Evolución de chip ADN emulado con algoritmo genético en FPGA para control de navegación de un robot móvil

DNA chip evolution emulated with genetic algorithm in FPGA for controlling mobile robot navigation

Borrero Guerrero, H.1; Delgado Rivera, A.2

1 Profesor, Facultad de Ciencias Básicas e Ingeniería, Universidad de los Llanos, Villavicencio

Grupo de Estudio en Control y Automatización de la Universidad de los Llanos (gecaull)[email protected]

2 Profesor Titular, Facultad de Ingeniería, Universidad Nacional de Colombia, Bogotá. Grupo de investigación en Control Inteligente de Sistemas (CIS) Universidad Nacional de Colombia. [email protected]

Recibido: Marzo 8 de 2008. Aceptado: Mayo 8 de 2008.

RESUMEN

Los chips ADN constituyen una herramienta importante en biología y medicina porque ofrecen paralelismo así como memoria asociativa, características que optimizan la identificación del genoma y el diagnóstico de enfermedades, entre otros. La apropiación del concepto de chip ADN y el uso de los dispositivos electrónicos reconfigurables, genera el chip ADN emulado electrónicamente, capaz de procesar información en paralelo y acceder contenidos en memoria por asociación.

La utilización de algoritmos genéticos extiende las capacidades propuestas en el chip ADN emulado, sumándole un nivel de aprendizaje. La funcionalidad de un chip ADN emulado entrenado por medio de un algoritmo genético, se demuestra revisando la capacidad de aprendizaje de un robot móvil de tracción diferencial para navegar en un espacio cambiante evitando colisiones.

Palabras clave: chip ADN, emulación electrónica, algoritmo genético, sistema clasificador.

SUMMARY

DNA chips represent an important tool in biology and medicine as they offer parallelism as well as associative memory, such characteristics optimizing genome identification and diagnosing diseases. Appropriating DNA chip concept and using reconfigurable electronic devices produces an electronically-emulated DNA chip able to process information in parallel and access memory content by association.

Using genetic algorithms extends emulated DNA chip’s proposed capacity, thereby adding on a level of learning. A genetic algorithmtrained emulated DNA chip’s functionality can be demonstrated by reviewing a differential traction mobile robot’s learning ability in terms of navigating in a changing space and avoiding collisions.

Key words: DNA chip, electronic emulation, genetic algorithm, classifier system.

INTRODUCCION

Un chip de ADN (del inglés DNA microarray) consiste de una superficie sólida de materiales como vidrio, plástico e incluso chips de silicio a la cual se unen una serie de fragmentos de ADN. Son utilizados para diagnosticar la expresión de genes, monitorizándose los niveles de miles de ellos de forma simultánea [Kohane,2003 & Fogel,2003]. La tecnología del chip de ADN es una técnica muy usada en biología molecular, permite observar de forma casi instantánea la expresión genética del genoma de un organismo. De tal forma que suelen ser utilizados para identificar genes que producen ciertas enfermedades mediante la comparación de los niveles de expresión entre células sanas y células que están desarrollando ciertos tipos de enfermedades [Kohane,2003 & Fogel, 2003].

La apropiación del concepto “chip ADN”, el aprovechamiento de sus principales características: paralelismo y memoria asociativa además de la integración con los sistemas electrónicos reconfigurables genera su emulación en hardware, constituyendo una alternativa eficiente en tareas que requieren interactuar con un elevado número de variables así como el menor tiempo de procesamiento posible.

La utilización de un algoritmo genético (AG) extiende las capacidades propuestas en el chip ADN emulado hacia un nivel de entrenamiento. La funcionalidad de un chip ADN emulado entrenado por medio de un AG, se demuestra revisando la capacidad de aprendizaje de un robot móvil de tracción diferencial para navegar en un espacio determinado evitando colisiones.

Este trabajo no explora en detalle los fundamentos biológicos de los chips ADN, el lector interesado puede consultar la bibliografía especializada (Alberts 1998, Campbell 2003, Lewin 2004).

El artículo se desarrolla como sigue, en la sección 1 se realiza una presentación sobre los aspectos básicos del ADN, así como las generalidades en torno a los chips ADN, para luego tratar lo pertinente en cuanto a su emulación electrónica y algunos fundamentos para su aplicación. También se tratan algunos aspectos importantes y básicos sobre algoritmos genéticos y los sistemas clasificadores. En la sección 2 se realiza una descripción global de la implementación mecánica y electrónica de un robot móvil de tracción diferencia. En la sección 3 se expone lo pertinente a la utilización de un lenguaje de descripción de hardware con VHDL (VHSIC Hardware Description Language) en el diseño y construcción del sistema. En la sección 4 se realiza una exposición sobre la utilización de un algoritmo genético y un sistema clasificador en el entrenamiento de un del chip ADN emulado electrónicamente utilizándose en el cumplimiento de la tarea de un robot móvil que aprende a navegar evitando colisiones.

CONCEPTOS GENERALES

Figura 1. El ADN. (a) Representación de los nucleótidos; (b) Cadena sencilla de ADN; (c) Doble hélice de ADN

El ADN está constituido por moléculas denominadas nucleótidos, cada nucleótido está compuesto de un fosfato, un azúcar de cinco carbonos (desoxirribosa) y una base nitrogenada (Alberts1998, Campbell2003, Lewin2004). Los nucleótidos derivan su nombre de la base que poseen las cuales se clasifican en dos pirimidinas {Citosina(C), Timina(T)} y dos purinas {Adenina(A), Guanina(G)}. En la figura1(a) se representan los cuatro nucleótidos constituyentes del ADN cada fosfato (cruz) se enlaza con la desoxirribosa (óvalo) y el grupo fosfato-azúcar se enlaza a una base nitrogenada.

Una cadena de ADN está conformada por una secuencia de nucleótidos como se representa en la figura 1(b). Existe un principio natural denominado complemento Watson–Crick en el cual dos nucleótidos son complementarios si sus bases son complementarias, la Adenina complementa la Timina y la Citosina complementa la Guanina, el complemento corresponde a la unión por enlaces de hidrógeno. Cuando dos cadenas de ADN son complementarias en el sentido Watson–Crick, como se ilustra en la figura 1 (c), ocurre el proceso denominado hibridación en el cual se produce una doble hélice de ADN (Alberts 1998, Campbell 2003, Lewin 2004).

1.1. El Chip ADN

Figura 2.Imagen representativa de un chip ADN y su funcionamiento

Un chip ADN, consiste en un gran número de cadenas de ADN fijadas ordenadamente sobre un substrato sólido formando un arreglo matricial. De acuerdo con la figura 2, dentro de un punto del chip se encuentran implantadas miles de cadenas de nucleótidos de la misma secuencia; en cada punto hay secuencias diferentes las cuales se denominan cadenas de prueba (Delgado2002). Los chips ADN explotan la propiedad de hibridación de las cadenas de ADN (Delgado2002), las secuencias de prueba han de ser comparadas con las muestras extraídas de algún organismo vivo y son incubadas sobre la superficie del chip, de tal manera que cuando se presente complementariedad en el sentido Watson-Crick con alguna de las cadenas de prueba del chip ocurre la hibridación formando una doble hélice de ADN en cada uno de los puntos que corresponde.

La identificación de los puntos en los cuales hubo hibridación depende de las técnicas utilizadas, existen adelantos tecnológicos por medio de los cuales es posible detectar este efecto de acuerdo con la generación de un potencial o corriente eléctrica. Otra de las técnicas consiste en marcar con sustancias fluorescentes las cadenas de muestra de tal manera que cuando hay hibridación las muestras pigmentadas forman hélices de ADN con sus complementarios en el chip. Al aplicar luz al chip para su análisis se resaltan por su color las moléculas de ADN formadas. En la detección de las hélices de ADN formadas en el chip, la electrónica y la informática juegan un papel fundamental pues permiten automatizar el análisis de la información proporcionada por los chips ADN.

1.2. El Chip ADN Emulado electrónicamente

Figura 3. Representación lógica de un Chip ADN emulado electrónicamente

En el chip ADN emulado electrónicamente la información de entrada se codifica como cadenas binarias de n bits correspondientes a las lecturas de un sistema externo como censores digitales o un conversor A/D (Borrero2005), entre otros, esta información se carga en un registro denominado muestra como se aprecia en la figura 3.

Para emular un chip de ADN, se debe contar con una estructura electrónica que contenga las posibles cadenas binarias que puedan generar hibridación exitosa con los datos de entrada (muestra), estas cadenas tienen n bits de longitud (Delgado2002) y emulan las cadenas de prueba, dichas cadenas de prueba se cargan en registros del chip ADN emulado.

En la figura 3 se muestra cómo la información de entrada es comparada paralelamente con varias cadenas binarias de “prueba”. Si la información en el registro muestra es complementaria con alguna de las palabras prueba, al ejecutar la función XOR entre las dos cadenas, una hibridación exitosa produce una cadena de n unos, de manera que al realizar la operación AND entre los bits a la salida de la función XOR se activará una bandera (Borrero & Delgado 2002).

Figura 4. Chip ADN aplicado a un sistema basado en reglas

El chip ADN emulado puede almacenar y evaluar reglas explotando el paralelismo propuesto en los circuitos electrónicos reconfigurables. De acuerdo con la representación de la figura 4, para que se active una bandera basta con que haya hibridación entre una palabra de entrada (muestra 1 o muestra 2) y una cadena de prueba. Para que se active una bandera de regla se requiere que haya hibridación para las dos cadenas de entrada. La condición en la cual muestra 1 genera hibridación exitosa con prueba (1,n-1) activa la correspondiente bandera (1,n-1), además paralelamente muestra 2 genera hibridación exitosa con prueba (2,n-1) activando la bandera (2,n-1), como se cumplen los dos antecedentes se activa la bandera de regla (r-1). La activación de banderas previa hibridación de cadenas de ADN emuladas es útil en el desarrollo de sistemas de control basados en reglas, nótese como la parte sombreada del sistema conduce a la activación de una bandera de regla indicando el cumplimiento de condiciones esperadas.

Figura 5. Las banderas de reglas son las entradas a un bloque programado con las palabras a direccionar hacia las salidas

Las banderas de regla son utilizables como entradas a sub-sistemas en los cuales se encuentran configuradas las salidas a ejecutar. De acuerdo con la figura 5 los estados de las banderas de la base de reglas ingresan al bloque de acciones, allí se diseccionan los registros donde se encuentran cargadas las palabras de control (reglas de acción) a las salidas (Delgado2002) que han de estar conectadas directa o indirectamente a los actuadores correspondientes.

1.3. Algoritmo genético

Figura 6. Diagrama de flujo de un AG.

 

Herramienta matemática que se utiliza para la búsqueda de soluciones óptimas, apropiando el concepto de la teoría de la evolución de los seres vivos (García & Sarmiento 2005). Chalela & Arias2004). El diagrama de flujo de un algoritmo genético con recompensa externa se muestra en la figura 6.

De manera aleatoria se crea una población inicial de m individuos que componen la primera generación (primeras palabras prueba en el chip ADN emulado).

1. Cada uno de los individuos de la población es evaluado en el ambiente y de acuerdo con su desempeño se le asigna una recompensa o calificación.

2. Se cuestiona al sistema en adaptación sobre si se ha encontrado la solución.

3. Si se encontró la solución al problema, se culmina con la etapa de adaptación o aprendizaje.

4. Si no se ha encontrado una solución se procede a seleccionar algunos individuos de la generación actual para aplicar en ellos los operadores de cruce y mutación para crear una nueva generación de individuos.

5. Regresar al paso 2.

1.4. Sistema Clasificador

Los sistemas clasificadores son sistemas basados en reglas, diseñados para interactuar con su entorno, aprender mediante la asignación de pesos a cada regla, y la creación de nuevas reglas a partir de las anteriores. Las reglas tienen la forma de una sentencia lógica (condición-acción), identificando una condición con una acción a realizar en caso de que la condición se cumpla (Holland 1998, Chalela & Arias 2004).

II. ROBOT MÓVIL

Figura 7. Sobre las plataformas de acrílico soportan los elementos que componen el robot móvil

Se construyó un minirobot móvil de tracción diferencial para el cual se tienen en cuenta consideraciones mecánicas y electrónicas, constituye una plataforma de prueba y desarrollo del modelo de aprendizaje planteado. Los algoritmos para el control de navegación se implementan en un FPGA, lo que permite un mayor aprovechamiento de las capacidades ofrecidas por el chip ADN emulado (paralelismo y memoria asociativa).

2.1. Estructura mecánica.

Los soportes de la estructura mecánica del minirobot constan de dos plataformas de material acrílico las cuales se representan en la figura 7, sobre dichas plataformas se instalan los componentes del robot móvil. En la plataforma superior se fijó una tarjeta de desarrollo comercializada por la firma DIGILENTINC que cuenta con un FPGA (XC3S200) de la familia Spartan 3 de la firma XILINX.

En la plataforma inferior se instalaron dos servomotores Hobbico HS-60, las llantas y algunos dispositivos electrónicos para el control del robot como los circuitos encargados del manejo de los censores de obstáculos y una batería recargable de 6 VDC-700mA, lo que se representa en la figura 8.

Figura 8. Representación Vista lateral robot

n la parte delantera de la plataforma inferior se debe fijar una rueda que en el marco de la robótica móvil se le denomina rueda caster o simplemente rueda libre, la cual sirve para soportar la estructura del robot, facilitar su movimiento (Ollero 2001).

Figura. 9. Representación del sistema rueda libre

De conformidad con la representación de la figura 9, el sistema de la rueda gira libremente en un paralelo al plano x, mientras que la rueda gira libremente en un paralelo al plano y.

Figura 10. Vista frontal y lateral del minirobot

En la figura 10 se muestra una vista frontal general del robot, así como una vista lateral del mismo, en dichas imágenes se puede apreciar los elementos que soportan las plataformas.

2.2. Detectores de Proximidad.

Para determinar la presencia de obstáculos frente al robot se construyó un bloque de cuatro detectores de proximidad cuyo funcionamiento se basa en emitir a través de un diodo una ráfaga de señales infrarrojas, las cuales al rebotar con un objeto cercano se reciben en el fototransistor, detectando así un obstáculo al frente de la pareja emisor–receptor, permitiendo utilizar dicho comportamiento en el control de navegación del minirobot. En las figuras 7, 8 y 10 se puede apreciar la disposición física de los detectores de obstáculos en el robot móvil.

III. DESCRIPCIONES DE HARDWARE

Figura 11. Diagrama de bloques del sistema HW/ SW. Cada bloque representa un módulo VHDL implementado en FPGA

La temática abordada exige una implementación en hardware que permita explotar explote el paralelismo y memoria asociativa, lo cual está disponible con la utilización de circuitos lógicos combinatorios que son susceptibles de ser implementados en FPGA. Se utilizó una tarjeta de desarrollo FPGA de la familia Spartan III de la firma XILINX, sobre la cual se implementaron descripciones de hardware en lenguaje VHDL desarrolladas en el entorno XILINX ISE 8.1.

Fundamentalmente el minirobot físicamente consiste de la estructura que se expone en la sección 2, con la implementación en hardware del circuito de control (chip ADN emulado). El diagrama de bloques que se muestra en la figura 11 representa los módulos desarrollados en el lenguaje de descripción de hardware VHDL e implementados en FPGA. La función de cada módulo se indica a continuación:

Módulo IR: Debido a que las señales generadas por los censores de proximidad son inestables en cierto rango de distancia (aproximadamente entre 7 10cm. con respecto a un obstáculo), se implementa una descripción en la cual se tratan las señales mencionadas, de manera que las salidas del módulo solo generen información cuando las señales desde los detectores sean estables (seguridad ate la presencia de obstáculos).

Módulo Pseudo: En dicho módulo se implementó una descripción para generar números pseudo-aleatorios, requeridos en la creación de la primera generación de individuos (palabras de prueba) en el chip ADN, así como en la determinación del punto de cruce y mutación durante el funcionamiento del AG.

Módulo unidad de control: Se implementa una descripción utilizando una máquina de estados algorítmica (Brown & Brazenic 2005), por medio de la cual se diseña e implementa un algoritmo genético y un sistema clasificador para entrenar el chip ADN (auto-aprendizaje). El diagrama de flujo mostrado en la figura 12 y en la sección 4 se explica en mayor detalle.

Módulo Chip ADN: En este módulo se implementa una descripción para emular electrónicamente un chip ADN. Debido a que en el chip ADN se busca aprovechar las cualidades de paralelismo y memo- ria asociativa. Se debe prestar atención en implementar una descripción recurrente, para lograr que el proceso de comparación de todos los bits a la muestra con respecto a las palabras de prueba se ejecute en el nivel lógico combinatorio.

Retomando lo expuesto para la figura 3, que orienta sobre el concepto del chip ADN emulado electrónicamente, así como lo representado en las figuras 7 a 10, se puede apreciar con claridad que en virtud al número de detectores de proximidad en el frente del robot, las palabras prueba y la muestra en el chip ADN implementado son de cuatro bits. Para el caso del uso del robot móvil, la palabra de entrada al el chip ADN (la muestra) esta compuesta por la concatenación de los bits generados por la proximidad de algún obstáculo frente a cada uno de los detectores.

En referencia al chip ADN emulado, no representa sentido práctico incorporar un número de registros de prueba que permita cargar todas las palabras que generen hibridación exitosa con todas las posibles combinaciones de entrada que se puedan presentar en el registro de muestra.

Si la muestra es de cuatro bits, al implementar 24=16registros de prueba no habría necesidad de implementar algún algoritmo de búsqueda ya que es posible incorporar todas las posibles combinaciones que generen hibridación exitosa con la muestra, es decir que el sistema está predispuesto a reaccionar ante cualquier palabra de entrada que es una expresión clara de la configuración de obstáculos al frente del robot.

Figura 12. Chip ADN emulado de cuatro bits utilizado en el proyecto

En la figura 12 se representa la implementación chip ADN utilizada para las pruebas realizadas, como se aprecia solo se incorporan 4 registros de prueba a cambio de 24=16. Lo cual anuncia que el proceso de evolución implementado tiene por función cargar en los registros prueba(0) a prueba(3) con palabras destinadas a lograr la evasión de cuatro configuraciones diferentes de obstáculos frente al robot.

Módulo PWM: La activación de las banderas en el chip ADN emulado determina las reglas (comportamientos) que debe asumir el minirobot (tracción diferencial), según el estado de las entradas (las salidas en chip ADN) se define el estado de las salidas PWM que corresponden a señales moduladas por anchura de pulso necesarias para determinar el sentido de giro de cada servomotor (tracción diferencial).

Un Servo es un dispositivo pequeño que cuenta con un eje de rendimiento controlado que puede ser llevado a posiciones angulares específicas al enviar una señal codificada. A menos que una señal codificada exista en la línea de entrada, el servo mantendrá la posición angular del engranaje. Cuando la señal codificada cambia, la posición angular de los piñones cambia. En la práctica, se usan servos para posicionar superficies de control como el movimiento de palancas, pequeños ascensores y timones. Ellos también se usan en radio control, títeres, y por supuesto, en robots. Los Servos son sumamente útiles en robótica. Los motores son pequeños, cuentan con circuitos de control internos, y son sumamente poderosos para su tamaño. Un servo normal o estándar como el HS-60 de Hobbico que tiene 42onzas por pulgada o mejor 3kg por cm. de torque y potencia proporcional para cargas mecánicas. Por consiguiente un servo no consume mucha potencia (Iovine 2000).

El servo tiene algunos circuitos de control y un potenciómetro el cual se conecta al eje central del servo motor. Este potenciómetro permite al circuito de control, supervisar el ángulo actual del servo motor. Si el eje está en el ángulo correcto, entonces el motor mantiene la posición, si el circuito chequea que el ángulo no es el correcto el motor girará en la dirección adecuada hasta llegar al ángulo correspondiente y sostenerse en dicha posición. El eje del servo es capaz de llegar alrededor de los 180grados. Normalmente, en algunos llega a los 210grados, pero varía según el fabricante. Un servo normal se usa para controlar un movimiento angular de entre 0 y 180grados. Un servo normal no es mecánicamente capaz de retornar a su lugar, si hay un mayor peso que el sugerido por las especificaciones del fabricante.

Para la utilización del servomotor en el robot, se requiere que el giro de su eje sea de 360grados, por lo cual este debe modificarse, para lo cual ha de ser desarmada su estructura, reemplazando el potenciómetro por dos resistencias de 2.2K como fijando el potenciómetro a la mitad de su valor resistivo. También se debe remover un tope que originalmente obstaculiza el avance en el giro del engranaje. Una vez se ha modificado el servo para que cuente con la posibilidad de girar su eje 360º (sin topes) se procedió a implementar en el FPGA una descripción correspondiente a emitir señales PWM (bloque PWM en la figura 11) que permitieran un control adecuado en el manejo de los servomotores para el robot, cuando se requiere que el robot evite un obstáculo girando su estructura se procede a generar desde la FPGA las señales PWM que hagan que un servo gire en un sentido contrario al del otro servo, logrando así obedecer al diseño de tracción diferencial propuesto.

IV. Evolución de un chip ADN con AG

El proyecto desarrollado evalúa el éxito en la navegación del minirobot expuesto en la sección II, implementando en hardware (FPGA) las descripciones correspondientes al chip ADN y su correspondiente entrenamiento. Para la ejecución de pruebas el robot tiene por función aprender evadir los obstáculos ubicados en su frente. Tomando nuevamente como referencia el diagrama de bloques mostrado en la figura11 se puede apreciar que la palabra de entrada (muestra) resulta del tratamiento en el bloque IR de las señales provenientes desde los detectores de proximidad, dicha palabra es cargada a la entrada de la unidad de control y del módulo chip ADN.

En la unidad de control se construyen las palabras a cargar en los registros de prueba en el chip ADN emulado, las cuales para la primera generación son generadas pseudo-aleatoriamente y cargadas en el chip ADN, dichas palabras son incorporadas en los registros prueba(0) a prueba(3) que se representan en la figura 13. Es pertinente aclarar que la unidad de control debe funcionar para lograr que las palabras cargadas en los registros de prueba sean diferentes entre sí, para asegurar un entrenamiento para cuatro configuraciones de obstáculos diferentes

Figura 13. Chip ADN ante una configuración de entrada específica y en relación con la descripción del bloque de acciones

La figura 14 corresponde al diagrama de flujo que representa el funcionamiento del un algoritmo genético y un sistema clasificador, que en hardware se implementaron en una máquina de estados basada en la versatilidad que ofrece la máquina de estados algorítmica (Brown & Vranezic 2005). El diagrama de flujo resume un extenso diagrama de estados algorítmicos implementado en la unidad de control del sistema.

Figura 14. Diagrama de flujo general sobre el entrenamiento del chip ADN emulado electrónicamente

El algoritmo genético implementado debe contar con una función de bondad (García & Sarmiento2005, Chalela & Arias 2004) que para el caso de la aplicación corresponde a la detección de la hibridación entre la muestra y alguna de las cuatro palabras de prueba, para ello se utiliza la función “or exclusiva” (XOR) y la función AND a la salida de cada XOR, lo cual genera la activación de alguno de los bits del vector BANDERA(0) a BANDERA(3) tal como se puede apreciar en la figura 13. La activación de un bit del vector BANDERAS le indica a la unidad de control la ocurrencia de una hibridación exitosa.

En caso de no ocurrir hibridación alguna, la unidad de control procede a ejecutar las operaciones genéticas de cruce y mutación sobre las palabras de prueba del chip ADN para procrear una nueva generación a recargar en los registros de prueba del chip ADN como lo representa el diagrama de flujo indicado en la figura 14.

En el diagrama que se muestra en la Figura 13 se muestra la conexión del bloque de acciones a la entrada con el chip ADN a través del vector banderas(3:0) mencionado previamente y a la salida con los módulos PWM_D y PWM_I, que de acuerdo con los valores 1/0 desde el bloque de acciones generan un tren de pulsos específico que controla el sentido de giro de los motores de tracción diferencial en el minirobot. Se debe tener en cuenta que si bien las palabras que se cargan en los registros del chip ADN son producto del entrenamiento, en el bloque de acciones se describe en detalle el sentido de giro que deben adoptar los ejes de los motores del robot y por lo tanto generar las acciones de navegación adelante, girar a la derecha y girar a la izquierda. Las indicaciones descritas en el bloque de acciones no cambien en el aprendizaje, dicha descripción se conserva durante el aprendizaje, lo cual ocasiona que en muchas generaciones de pobladores se presentan hibridaciones exitosas pero acciones de navegación inadecuadas.

De acuerdo con la representación de la figura 15 el generador de números pseudo-aleatorios ha cargado en los registros de prueba del chip ADN las palabras que se aprecia, el registro para la muestra se encuentra cargado con la palabra “0011”que el caso de la experimentación corresponde a obstáculos frente a los detectores central derecho y extremo derecho.

Figura 15. Representación de un configuración de obstáculo frente al robot, muestra = “0011”.

Tomando nuevamente como referencia la figura 13, de acuerdo con las condiciones de entrada mostradas en la figura 15 (muestra=“0011”) se genera una hibridación exitosa entre la muestra y el registro prueba(2), lo que genera la activación de la bandera bandera(2), lo que de acuerdo con lo previsto en el bloque de acciones genera que el robot se dirija hacia adelante. Lo cual indica que una hibridación exitosa no necesariamente genera una buena acción de navegación.

Es claro que la primera generación de pobladores de los registros de prueba descienden directamente del generador de números pseudo-aleatorios y que las generaciones posteriores descienden de la primera producto de la intervención de los operadores genéticos.

En el evento de una hibridación exitosa se debe aprovechar la utilidad que representa un sistema clasificador (Holland 1998, Chalela & Arias 2004) que en la experimentación realizada se utiliza para generar recompensa a registros del chip ADN ante la detección de acciones de control exitosas. Nótese como una hibridación exitosa no necesariamente implicará una acción de control exitosa.

Figura 16. Chip ADN ante una configuración de entrada similar a la de la figura 13 pero con la evolución lograda en algunas generaciones futuras

En la unidad de control se procede a evaluar que la acción de navegación ejecutada por el robot sea adecuada, para esto se temporiza un segundo, si una vez transcurrido ese tiempo la palabra de entrada (muestra) es diferente a su valor al iniciar la temporización (premuestra), la acción de control realizada provocó la evasión del obstáculo y al registro de prueba cuyo contenido provocó hibridación exitosa y acción de control exitosa se asigna recompensa al registro e prueba que la generó buen comportamieto, es decir clasifica (Holland1998, Chalela & Arias2004), produciendo que dicha palabra en dicho registro permanezca fija durante el resto del proceso de aprendizaje, de modo que solo se puede actualizar los registros sin recompensa. La evolución del chip ADN continuará para el resto de los registros de prueba aún no recompensados.

Tomando ahora como referencia las figuras y 13 y 16, que corresponden con muestra=“0011”, para efectos de clasificación, con el robot en movimiento (de acuerdo con las figuras nótese que el robot va hacia adelante) se temporiza un segundo como se mencionó anteriormente, en virtud a que la FPGA utilizada funciona con un reloj de 50MHz, por medio de la máquina de estados se cuenta con una nueva generación producto del trabajo realizado por el algoritmo genético cada 160nS, rapidez lograda gracias a la explotación de las capacidades de procesamiento paralelo los dispositivos lógicos programables en este caso una FPGA, de manera que se crean unas nuevas condiciones como las que se representan en la figura 16 donde ahora hay una hibridación exitosa para la misma muestra=“0011” con el registro prueba(1) lo cual se refleja en con la activación del bit bandera(1), que como se aprecia en el bloque de acciones genera que el robot gire a la izquierda, de forma tal que al transcurrir una nueva temporización de un segundo, experimentalmente se comprobó que la palabra de entrada (muestra) cambia y por lo tanto se asigna una recompensa al registro prueba(1) que no puede ser actualizado durante el restante proceso de aprendizaje, es decir que el robot ya ha sido entrenado para una de las cuatro posibles configuraciones de obstáculos.

El algoritmo finaliza el entrenamiento cuando se detecta que todos los registros del chip ADN has sido cargados con palabras que generan éxito, de manera que todos los mismos han sido recompensados, así mismo si todos los registros tienen recompensa se ha culminado la etapa de aprendizaje.

Cuando la etapa de aprendizaje ha terminado se puede verificar las palabras de entrada (muestra y/o configuración de los obstáculos) para los cuales el minirobot ejecuta la evasión correspondiente y las palabras de entrada para las cuales el minirobot no ejecuta acciones de control exitosas como estrellarse.

Esto resalta como el minirobot se auto-entrenó para una cantidad de palabras de entrada correspondiente al número de registros de prueba del chip ADN. Si el minirobot detecta una configuración de obstáculos en su frente, es decir una muestra distinta a las entrenadas el minirobot, se estrellará con el obstáculo.

CONCLUSIONES

Un chip ADN emulado electrónicamente representa una alternativa en aplicaciones en las que se requiere evaluar un elevado número de variables y/o se necesita el menor tiempo de procesamiento posible aprovechando la capacidad de procesamiento paralelo (paralelismo) y memoria asociativa.

La robótica móvil permite una buena exploración sobre diversas técnicas de control, de tal forma que se considera fundamental la disposición de un buen robot móvil que contribuya como plataforma en el diseño y desarrollo en el área de control

La disponibilidad de arquitecturas electrónicas reconfigurables genera un mayor beneficio para aplicación de las técnicas inteligentes de control que se puedan ver optimizadas ante la disposición de procesamiento paralelo.

Durante la etapa de entrenamiento del chip ADN, una hibridación exitosa no necesariamente implicará una acción de navegación adecuada, una palabra en un registro de prueba puede generar una acción de control inadecuada de modo que es imprescindible e uso de un sistema clasificador que recompense los registros de prueba que contengan palabras que generan hibridación y acciones de control exitosa. En esencia se requiere ubicar las palabras con hibridación exitosa en un registro de prueba que provoque una acción de navegación exitosa para el caso del robot y acciones de control y/o diagnóstico en otras aplicaciones.

El proceso de evolución de un chip ADN emulado por medio de un algoritmo genético se realiza de manera secuencial, utilizado una máquina de estados algorítmicos. El chip ADN fue implementado como un circuito lógico combinacional lográndose así que su paralelismo y asociatividad se conserven durante proceso de aprendizaje y ejecución de lo aprendido.

Una vez se ha cumplido con el proceso de entrenamiento (evolución) el chip ADN emulado procesa en paralelo, de manera asocia la información a la entrada (sensores de proximidad–palabra muestra) del ambiente sobre el cual se entrenó el minirobot y ejecuta las correspondientes acciones de navegación.

La utilización de un AG para fijar las mejores palabras de prueba en un chip ADN emulado frente a una situación específica, representa alternativa sencilla en el aprendizaje sobre el dominio de un sistema en diversos ambientes. Representa la ventaja de tomar la decisión sobre el número de registros de prueba a utilizar para reducir el número de reglas que se describen en al bloque de acciones, sin sacrificar el éxito en la ejecución de tareas, lo cual implica la disminución en la necesidad de recursos, como en este caso registros de prueba.

La utilización de la emulación electrónica del chip ADN y su respectivo entrenamiento mediante un algoritmo genético puede ser llevada a un nivel de aplicación de mayor complejidad, para ello se sugiere utilizar herramientas software de codiseño en lenguajes de programación de as alto nivel que el lenguaje VHDL (Prieto & Ramos 2007, Farfán & Herreño 2007).

AGRADECIMIENTOS

Los autores agradecen el soporte ofrecido por parte de la Facultad de Ingeniería y el grupo de investigación en Control Inteligente de Sistemas (CIS) de la Universidad Nacional de Colombia, el apoyo por parte del Instituto de Investigaciones de la Orinoquía Colombiana (IIOC) y la Universidad de los Llanos, el aporte de la beca–pasantía por parte del Instituto Colombiano para el Desarrollo de la Ciencia y la Tecnología (COLCIENCIAS) en el marco del programa “Jóvenes Investigadores e Innovadores”, la disposición de los estudiantes que integran el Grupo de Estudio en Control y Automatización de la Universidad de los Llanos (GECAULL) y de manera especial se agradece al Ing. Miguel Melgarejo por sus enseñanzas en lo correspondiente a la descripción de hardware con VHDL.

REFERENCIAS

Alberts B, Bray D, Johnson A, Lewis J, Raff M, Rob- erts K, Walter, P .“Essential cell biology.” Garland Pub-lishing, 1998.

Borrero H. “Chip ADN, Emulación electrónica y aplicaciones,” II Congreso colombiano de bioingeniería e ingeniería biomédica, Bogotá–Colombia, Octubre 10 - 12, 2005.

Brown S, Vranezic Z. “Fundamentals of digital logic with VHDL design,”Mc Graw Hill, New York, 2005.

Campbell A.M. y Heyer L.J. “Discovering genomics, proteomics, and bioinformatics, Pearson Education”, 2003.

Chalela S, Arias R. “Evolución de un sistema clasificador utilizando algoritmos genéticos,” Facultad de ingeniería. Universidad Nacional de Colombia, Bogotá–Colombia, 2004.

Delgado A. “DNA chips as lookup tables for rule based systems,” IEE Computing and Control Engineering Journal, Vol. 13, No. 3, pp. 113 - 119, 2002.

Farfan A, Herreño J y Delgado A. “Gene digital y chip ADN electrónico: aplicaciones en robótica móvil,” 3rd Colombian Work shop on Robotics and Automation (CWRA), Universidad Tecnológica de Bolívar, Cartagena, Agosto 21-22, 2007.

Fogel G.B. and Corne D W. Sánchez-Gutiérrez A, Martín-Hernández I, García-Izquierdo SM. Bioquímica 2003; 28 (2): 3-8.

García L, Sarmiento T, y Delgado A. “Diseño e implementación de un robot móvil con aprendizaje autónomo en FPGA,” IEEE Colombian Workshop on Robotics and Automation (CWRA), Pontificia Universidad Javeriana, Bogotá, Agosto 11, 2005.

Holland, J.H. Emergence, Perseus Books, 1998.

Iovine J. “PIC Robotics,” McGraw Hill, 2000.

Kohane I.S, Kho A.T, Butte A.J. Microarrays for an Integrative Genomics, The MIT Press, Cambridge, 2003.

Lewin B. Genes VII, Oxford University Press, 2000.

Ollero B. “Robótica, manipuladores y robots móviles,” Alfaomega- Marcomobo, España, 2001.

Prieto J, Ramos O y Delgado A. “Diseño de un gene digital en FPGA y MATLAB con aplicaciones en robótica móvil,” XIII Taller Iberchip IWS-2007, Lima–Perú, Marzo 14-16, 2007.