Download 15 Implementación de una Memoria Asociativa en

IMPLEMENTACIÓN DE UNA MEMORIA ASOCIATIVA EN FPGA PARA EL
CONTROL DE UN ROBOT MÓVIL
J. C. Vanegas*, O. D. Molina*, A. Delgado+
Departamento de Ingenierías Eléctrica y Electrónica
Universidad Nacional de Colombia, sede Bogotá
*
Estudiantes Ing. Electrónica, + Profesor Asociado
(jcvanegasa, odmolinag, adelgado)@ieee.org
RESUMEN
programada, el resultado final obtenido y algunas
conclusiones.
En aplicaciones que requieren la comparación de un gran
número de variables respecto a ciertos patrones, resulta de
gran ayuda la utilización de sistemas con procesamiento
paralelo. En este artículo se ha utilizado una arquitectura
en paralelo, chip de ADN y memoria asociativa, aplicada a
un sistema digital implementada en una FPGA para la
validación de un conjunto de instrucciones que controlan
un robot móvil con capacidad de evitar obstáculos.
1.
2.
CHIP DE ADN Y MEMORIAS
ASOCIATIVAS
El concepto de chip de ADN proviene de la apropiación
del estudio que en biología se hace a las cadenas de ADN,
las cuales se encuentran al interior de las células en los
seres vivos y se componen por la unión de dos cadenas
sencillas que se complementan entre sí y forman una
estructura helicoidal. Cada cadena sencilla se forma a
partir de la concatenación de pequeñas estructuras
denominadas nucleótidos, formadas a su vez por tres
componentes, azúcar, fosfato y base. Los nucleótidos
reciben nombres particulares de acuerdo a la base que los
compone. Existen dos tipos de bases, purinas y pirinidinas.
Las primeras se conocen como adenina (a) y timina (t),
mientras que las segundas se denominan guanina (g) y
citosina (c). De acuerdo a un criterio conocido como
principio de Watson y Crick, existen dos formas
complementarias en las cuales se presentan estas bases y
que dan lugar a la helicoidal de ADN, a saber: adeninatimina y guanina-citosina, ver figura 1. Cuando dos
cadenas sencillas complementarias de ADN se encuentran,
forman de manera natural una hélice. Este proceso se
denomina hibridación y es el principio que se explota en
los chips de ADN.
Un chip de ADN es una lámina de vidrio donde se
adhieren cadenas sencillas de ADN con distintas
secuencias o cadenas de prueba, ver figura 2. Aparte, y
sobre otras cadenas sencillas llamadas cadenas objetivo se
realizan marcas fluorescentes. El procedimiento es hacer
pasar cada cadena objetivo por el chip y luego de algunos
minutos lavarlo. Con esto quedan visibles puntos
fluorescentes donde ocurrió la hibridación y de esta forma
se conocen las secuencias presentes en las cadenas
objetivo. La hibridación es un proceso paralelo y se
pueden examinar miles de cadenas en un sólo ensayo.
INTRODUCCIÓN
La tendencia por aplicar conceptos propios de la biología a
la solución de problemas en ingeniería utilizando
herramientas de software y hardware ha permitido la
creación y desarrollo de técnicas novedosas [1]. Una de
estas técnicas es la hibridación propia de la cadena de
ADN y la identificación de bloques comparados de igual
estructura entre una muestra patrón y un conjunto de
muestras analizables. La emulación de este concepto
biológico en un sistema digital permite implementar lo que
se conoce como memorias asociativas que intenta
aproximarse al comportamiento cerebral en términos de la
identificación de un agente externo. La apropiación de la
técnica de análisis y la característica de funcionamiento en
paralelo propia de las cadenas de ADN, sumado a la
identificación por contenido de las memorias asociativas
ha permitido el diseño e implementación de una
arquitectura digital enfocada al control de un robot móvil.
El presente documento se divide en tres secciones. La
primera propone un acercamiento sencillo y discreto al
funcionamiento de las cadenas de ADN y su emulación
digital como chip de ADN para explorar someramente la
arquitectura de las memorias asociativas y su lectura por
contenido. En la segunda sección se presenta el diseño
mecánico y eléctrico de la arquitectura y control
propuestos para un robot móvil de baja escala. La tercera
sección ilustra las simulaciones hechas a la síntesis
1
Cuando la entrada y el patrón son complementarios la
palabra de salida no es otra cosa que una sucesión de unos
lógicos. Evaluando cada uno de los bits que forman la
palabra de salida en una función lógica AND se obtiene
finalmente una bandera lógica que determina la existencia
o no de complemento, esto es, hibridación entre la palabra
de entrada y la palabra de referencia [2].
Además de esta técnica de diseño, existen las
llamadas memorias asociativas, aplicación digital basada
en el concepto cognoscitivo de asociación propio del
cerebro humano. En una memoria digital convencional, el
contenido es almacenado y posteriormente recuperado a
través de una posición o dirección de entrada. A diferencia
de este procedimiento, las memorias asociativas utilizan
contenidos; esto es, dada una palabra de entrada, la salida
de la memoria será un contenido asociado a ésta
independiente de la posición que ocupe [3]. Claramente,
disponer a la salida de un contenido relacionado con la
entrada supone la comparación de rasgos de identidad
entre la entrada y todas las posiciones de la memoria
mediante la aplicación, por ejemplo, de la técnica paralela
de comparación del chip de ADN. La apropiación de este
modelo por asociación permite restringir el rango de
posiciones de la memoria, a diferencia de las memorias
convencionales donde el direccionamiento se realiza de
acuerdo al número de posiciones posibles que se pueden
codificar en el rango de la entrada.
Fig 1. Cadena doble de ADN formada por dos cadenas sencillas
complementarias.
3.
Fig. 2. Chip de ADN, note la marca realizada a la cadena
objetivo
ROBOT MÓVIL CONTROLADO POR
FPGA
De acuerdo con los conceptos de chip de ADN y memoria
asociativa, se propone una arquitectura en paralelo para el
control de un robot móvil autónomo capaz de evitar
obstáculos a partir de la validación de un conjunto de
instrucciones.
En términos generales la máquina consta de un par de
servomotores y dos sensores de proximidad. Las lecturas
análogas provenientes de los sensores son acondicionadas
y convertidas a lógica digital para ser procesadas por el
control dispuesto en una FPGA, capaz a su vez de
proporcionar las señales de operación PWM para cada uno
de los servomotores. El diseño e implementación del
control de movimiento a través de una memoria asociativa
permite evaluar cada una de las mediciones registradas por
los sensores, haciendo posible que la máquina opere de
forma autónoma evitando choques.
Fig 3. Esquema básico del chip de ADN.
Realizando una emulación del comportamiento de las
cadenas de ADN se ha logrado utilizar la técnica de chip
de ADN en aplicaciones electrónicas. En términos de un
sistema digital, la comparación entre una palabra binaria
de entrada y una palabra binaria de referencia o patrón se
puede realizar a través de la función lógica XOR, como
muestra la figura 3.
3. 1. Diseño Mecánico
El chasis del robot lo constituyen un juego de cuatro
piezas definidas como fondo, soportes de motor y techo,
junto con algunos soportes adicionales como se observa en
las figuras 4 - 6. Los actuadores son dos servomotores
estándar operados utilizando señales tipo PWM, unidos
2
3.2. Diseño Eléctrico
Fig. 4. Vista frontal superior.
Fig. 7. Esquema eléctrico del robot móvil
La figura 7 simplifica el esquema eléctrico diseñado para
la operación del robot móvil. Las señales análogas de dos
sensores de proximidad son acondicionadas y convertidas
a señales digitales de 8 bits cada una, obteniéndose un
total de 16 bits con la información de entrada para la
FPGA. En el caso particular, cada sensor posee su propio
módulo de acondicionamiento y conversión A/D con
niveles de voltaje inferiores a 5V DC. En la FPGA se han
programado los bloques correspondientes a la memoria
asociativa y al control PWM de cada uno de los
servomotores; de acuerdo a las entradas y a la validación
de las asociaciones programadas se obtiene un ancho de
pulso que acciona los motores hacia delante o hacia atrás,
según sea el caso.
La FPGA escogida es XC2S50 perteneciente a la
familia Spartan 2 de Xilinx, que requiere la utilización de
una tarjeta de desarrollo como la mostrada en la figura 8,
diseñada y elaborada en nuestro Departamento de IEE.
Esta tarjeta provee alimentación de 3.3V DC para la
FPGA, oscilador de 4MHz, programación vía puerto
paralelo a través del protocolo de programación JTAG,
acceso a microcontrolador y matriz de diodos emisores,
junto con otras funciones adicionales.
Fig. 5. Vista lateral. No se incluye la rueda libre.
Fig. 6. Vista posterior superior, note las celdas para los
servomotores.
directamente a las ruedas. Se ha preferido utilizar una
plataforma de baja escala y bajo costo con las dimensiones
apropiadas para acoger los sensores, tarjetas de control,
servomotores y batería, además una arquitectura
diferencial donde la tercera rueda o rueda libre ha sido
fabricada con el único fin de proporcionar soporte y
pivote, fuera de toda tracción, junto con una forma semi ovalada que permite mejor visual a los sensores.
Fig. 8. Tarjeta empleada. La FPGA es XC250 Spartan 2
3
Tabla 1: Relación de los estados a la entrada con los
movimientos del robot.
BANDERAS
COMPORTAMIENTO
Sensor 1 Sensor 2
ML
ML
Adelante
ML
L
Giro Suave a la Derecha
ML
P
Giro a la Derecha
ML
MP
Atrás a la Izquierda
L
ML
Giro Suave a la Izquierda
L
L
Giro a la Izquierda
L
P
Rotar a la Derecha
L
MP
Atrás a la Izquierda
P
ML
Giro a la Izquierda
P
L
Rotar a la Izquierda
P
P
Rotar
P
MP
Atrás a la Izquierda
MP
ML
Atrás a la Derecha
MP
L
Atrás a la Derecha
MP
P
Atrás a la Derecha
MP
MP
Atrás
Fig. 9: Estructura de bloques del control cargado en la FPGA
La programación de la FPGA consta de un bloque
fundamental constituido por las entradas digitales de los
sensores (8 bits cada una), una señal de reset asincrónico,
la señal de reloj proveniente del oscilador incluido en la
tarjeta y las dos salidas PWM para los servomotores, ver
figura 9.
Dos bloques funcionales internos describen la
arquitectura de la máquina, el primero de ellos
corresponde a una emulación del comportamiento del chip
de ADN no para complementariedad sino para definir
intervalos de pertenencia de las entradas provenientes de
los sensores. Cada entrada de 8 bits se evalúa respecto a
cuatro intervalos que dividen las 256 combinaciones
posibles en rangos de proximidad, denominados muy
lejano (ML), lejano (L), próximo (P) y muy próximo (MP).
A su vez, cada intervalo tiene asignada una bandera, de
manera que la evaluación de la pertenencia del valor de
entrada a uno de los cuatro intervalos de proximidad o
estados determina la activación de dos banderas, una por
cada sensor, con lo que una palabra de 8 bits (resultado)
formada por la concatenación de todas las banderas del
esquema deberá tener dos bits en alto y los demás en bajo.
El segundo bloque corresponde a una memoria
asociativa que relaciona la palabra producto de la
activación de las banderas con el ancho del pulso PWM
que opera los motores; es decir, se asocia el estado de la
entrada de los sensores con el movimiento de los motores
a partir de las características asociativas almacenadas en la
palabra resultado. La Tabla 1 muestra los 16 posibles
estados de la entrada asociados con 10 movimientos
asignados al robot. Por ejemplo, cuando las entradas son
ambas evaluadas dentro del intervalo correspondiente a
Muy Próximo (MP) el control genera las señales PWM
adecuadas para que el robot avance hacia atrás.
4.
SIMULACIONES Y RESULTADOS
La figura 10 muestra el aspecto del robot móvil terminado.
Se puede verificar el diseño mecánico previo y la
presencia de dos sensores en la parte frontal, dos
servomotores en la parte posterior directamente acoplados
a las ruedas, todo controlado por una tarjeta de
acondicionamiento de sensores y la FPGA. La
alimentación corre por cuenta de una batería de 6V a 1A
ubicada entre los dos servomotores.
Simulaciones realizadas a la síntesis de los
algoritmos desarrollados arrojaron los resultados
mostrados en las figuras 11 - 13. El PWM del motor
derecho del robot es la señal PWM1 mientras que el motor
izquierdo tiene su correspondiente PWM en la señal
PWM2.
La figura 11 muestra la simulación de la memoria
asociativa implementada. Las entradas son los valores
decimales de la señal digital proveniente de los sensores.
Se puede verificar cómo los anchos de pulso a la salida de
los motores cambian respecto a la combinación de entrada.
La figura 12 muestra el resultado de la simulación hecha
para el estado adelante, es decir, ambos sensores dentro
del intervalo muy lejos. Se observa que el ancho de pulso
NO es igual para los dos motores, como podría suponerse.
4
del otro en la disposición típica para un vehículo, el
avance hacia adelante de éste se obtenga cuando un motor
gira en un sentido y el otro en el opuesto. Es por esta razón
que en la figura 12 se observa el pulso del motor 1 de más
duración que el del motor 2. Se verifica entonces que el
motor 1 gira hacia la derecha en tanto que el motor 2 gira
hacia la izquierda logrando que el vehículo se mueva hacia
adelante.
La figura 13 muestra el resultado obtenido para el
estado de entrada giro suave a la derecha donde el motor
izquierdo gira un poco más rápido que el derecho aunque
ambos lo hagan hacia adelante. Se observa el cambio del
ancho de pulso cuando la entrada de los sensores cambia,
en este caso al estado giro a la izquierda. El cambio en el
ancho de pulso del PWM2 obliga que el motor izquierdo
cambie su sentido de giro de una posición de avance a
reversa (desde el punto de vista del robot). Aumento en el
ancho de pulso de PWM1 sugiere un aumento de la
velocidad en el motor derecho del robot. Esta condición,
en efecto, corresponde a un giro diferencial hacia la
izquierda.
Fig. 10: Aspecto Final del Robot Móvil.
Los servomotores utilizan una señal interna de
referencia contra la cual comparan el valor de la señal de
entrada PWM. Si el PWM de entrada tiene un ancho de
pulso más largo o más corto que esa referencia el motor
girará para uno u otro lado. Sin embargo, la geometría de
los motores usados obliga que, al colocarlos uno al lado
Fig. 11. Simulación de la memoria asociativa implementada.
Se observan los cambios en los ancho de pulso PWM de acuerdo a las señales de los sensores.
Fig. 12. Simulación del estado “Adelante” (3,1).
Los anchos de pulso son diferentes debido a la construcción del robot.
Fig. 13. Simulación del estado “Giro Suave a la Derecha” (3,16).
Se observa el cambio de los pulsos con la llegada del estado “Giro a la Izquierda” (16,18).
5
5.
CONCLUSIONES
gracias a la lógica combinacional que compone tanto la
memoria asociativa como la evaluación por intervalos del
chip de ADN.
Una característica intrínseca al funcionamiento de los
servomotores utilizados es su alto grado de precisión en el
giro, razón por la cual son altamente utilizados en
aplicaciones de control; esta misma facultad hace que el
movimiento rotacional esté restringido a 180º. Una
adaptación al interior del mecanismo de control propio de
los servomotores permitió liberar la rotación para poder
utilizarlos en el desplazamiento del vehículo construido.
Pruebas realizadas a la plataforma aseguran el
funcionamiento de la lógica implementada, en parte
garantizado por la respuesta análoga de los sensores ante
obstáculos. Esta salida presenta un comportamiento
decreciente respecto a la distancia entre el sensor y un
objeto; para distancias cortas (Muy Próximo) la salida es
máxima mientras que para distancias largas (Muy Lejos) la
salida es aproximadamente cero, lográndose que todos y
cada uno de los intervalos de proximidad definidos para la
validación de movimientos sean en algún momento
evaluados. En la mayoría de las pruebas se registró con
éxito la evaluación de los 10 comportamientos
establecidos, siendo necesario realizar algunas iteraciones
para determinar los intervalos de proximidad más
adecuados de forma que todos los comportamientos fuesen
ejecutados. Así mismo, parte del éxito logrado
corresponde a la velocidad de procesamiento garantizada
por la implementación en paralelo propia del chip de ADN
y la memoria asociativa; una aplicación secuencial
obligaría la revisión de todos los intervalos serialmente,
corriéndose el riesgo de no poder ejecutar una maniobra de
evasión consecuente con la presencia fortuita de un
obstáculo en las cercanías del vehículo. Esta misma
característica permite aumentar el número de intervalos de
proximidad y el grado de complejidad de los movimientos
del robot junto con la memoria asociativa que los ejecuta
sin perder la eficiencia del tiempo de respuesta; en parte
6.
AGRADECIMIENTOS
Gran parte del éxito alcanzado es producto del trabajo
interdisciplinario adelantado entre los Departamentos de
Ingeniería Eléctrica y Electrónica e Ingeniería Mecánica y
Mecatrónica de la Universidad Nacional de Colombia sede
Bogotá.
Agradecemos al profesor Máximo Roa del
Departamento de Ing. Mecánica y Mecatrónica, y al
estudiante de Ingeniería Mecánica Anderson Benito, por
su gran colaboración en el diseño mecánico y construcción
de la plataforma.
7.
REFERENCIAS
[1] 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.
[2] Delgado, A.: “Robot Controller Using Electronic
DNA Chip”. Memorias II Congreso Internacional de
Ingenierías Eléctrica y Electrónica. Bogotá, Colombia.
Marzo de 2003.
[3] Spitzer, M.: The mind within the net. The MIT Press,
Cambridge, Massachusetts, 1999.
[4]
6
Camargo, C.; Delgado A.; Sepúlveda, J.
“Implementación de Chip de ADN en FPGA”.
Memorias X Iberchip Workshop. Cartagena,
Colombia. Marzo 2.004.