"comprehendere scire est"

Welcome divider

Consejo Nacional para el Entendimiento Público de la Ciencia.

Autómatas finitos: su aplicación para describir la trayectoria de un vehículo evasor de obstáculos


Gustavo Delgado Reyes1, Jorge Salvador Valdez Martínez2, Pedro Guevara López3 1,2 Escuela Superior de Ingeniería Mecánica y Eléctrica, Unidad Culhuacán, Av. Santa Ana No. 1000, Col. San Francisco Culhuacán, México DF, México, Tel. (55) 57296000, ext. 73250, Contacto , Contacto 3 Centro de Investigación Ciencia Aplicada y Tecnología Avanzada, Unidad Legaria- IPN, Av. Legaria, No. 694, Col. Irrigación, México, DF, C.P. 11500 Contacto

En el presente trabajo, se muestra una representación alternativa de las trayectorias de un Vehículo Evasor de Obstáculos (VEO) usando la teoría de autómatas finitos de tipo no determinísticos. El vehículo en estudio posee dos motores de corriente continua y puede evadir obstáculos al obtener información del medio que lo rodea mediante el uso de fotodiodos y fotorresistencias. La salida de estos componentes electrónicos es procesada e interpretada digitalmente para elaborar una serie de trayectorias posibles del vehículo (girar a la izquierda, girar a la derecha, avanzar, retroceder, etc.). Con el análisis de estas trayectorias (o estados posibles) y empleando la teoría de autómatas finitos, el modelado descriptivo del VEO puede ser simplificado e incluso representado gráficamente mediante el uso de un diagrama de transiciones.


La teoría de autómatas finitos consiste en modelos matemáticos de sistemas, con entradas y salidas discretas. El sistema puede estar en cualquiera de un número finito de configuraciones o “estados”. El estado del sistema resume la información concerniente a entradas anteriores y que es necesaria para determinar el comportamiento del sistema para entradas posteriores. En la ciencia de la computación encontramos muchos ejemplos de sistemas de estados finitos, y la teoría de autómatas finitos es una herramienta muy útil en lo que a esta ciencia concierne. Un ejemplo es un circuito de interrupción, como la unidad de control de una computadora, el que está compuesto por un número finito de compuertas, cada una de las cuales pueden utilizar dos condiciones posibles, por lo general denotadas por 0 y 1 hablando de valores lógicos de voltaje. En este contexto el presente trabajo está enfocado a utilizar la técnica de autómatas finitos para modelar las trayectorias posibles de un Vehículo Evasor de Obstáculos (VEO), que son las diferentes salidas (estados) que se presentan ante diferentes entradas al sistema, las que provienen de los sensores con los que ha sido equipado el vehículo. (Hopcroft,1997) establece que un Autómata Finito consiste en un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre símbolos de entrada tomados de un alfabeto S. Para cada símbolo de entrada existe exactamente una transición a partir de cada estado (posiblemente de regreso al mismo estado). Un estado, por lo general denotado como q0, es el estado inicial en el que el autómata tiene su origen, mientras que otros estados están designados como finales o de aceptación. Un tipo especial de autómatas son los Autómatas Finitos no Determinísticos que de acuerdo a (Brookshear,1989) analizan cadenas construidas a partir de un alfabeto finito y solo puede tener un numero finito de estados, algunos de los cuales son de aceptación y uno es el estado inicial. En este tipo de autómatas, la transición que se ejecuta en una etapa dada puede ser incierta, es decir en la transición de un estado a otro pueden existir más de un arco rotulado e inclusive arcos que conlleven al mismo estado, considere la figura 1 para clarificar el concepto. Figura. 1. Diagrama de transiciones para un autómata finito no determinístico. De manera formal se representa a un Autómata Finito no determinístico mediante una quíntupla (Q, S, d, q0, F), en donde Q es un conjunto finito de estados, S es un alfabeto de entrada finito, q0 es el estado inicial y además es elemento de Q, F es el conjunto de estados finales, pero en este caso d representa las posibles transiciones de la maquina. Es decir, el trío (p, x, q) está en d si y solo si el autómata puede pasar del estado p al q al leer el símbolo x de la cadena de entrada. Así, un autómata finito no determinístico (Q, S, d, q0, F), acepta la cadena no vacía x1, x2,..., xn ? S si y solo si existe una secuencia de estados s0, s1, … sn tal que s0 = q0, sn ? F y para cada entero j de 1 a n, (sj-1, xj, sj) está en d.&nbsp; Construcción del vehículo evasor de obstáculos Uno de los primeros trabajos que comenzaron a formalizar la dinámica de robots móviles es (Crowley,1989) en el que se utilizan dispositivos ultrasónicos en el vehículo para su posicionamiento y orientación. En (Maes,1990) se muestra un estudio del comportamiento de robots autónomos y se divide en construcción de mapas, exploración, transitar y evasión de obstáculos. En (Seng,1997) se plantea como una de las mayores problemáticas de la navegación robótica la localización y se proponen los pasos claves para el diseño, calibración y modelado de autómatas. Hay otros autores que refuerzan la evasión de objetos o desarrollo de trayectorias mediante técnicas de navegación como son: navegación inercial, compases magnéticos y triangulación.(Borenstein,1997). (Betke,1997) considera que el autómata puede reconocer marcas especificas en el medio por el cual se desplaza usando reconocimiento de patrones visuales. La localización robótica así como la evasión de obstáculos del autómata, ha llegado a ser uno de los problemas fundamentales en los robots móviles, y por ello, en (Fox,1999) se presenta una versión de la localización Markov, en donde la idea principal es mantener una densidad de probabilidad sobre el espacio de todas las localizaciones posibles de un robot en su entorno. El Vehículo Evasor de Obstáculos (VEO de aquí en adelante) obtiene información del medio por el cual transita a través de unos fotodiodos y unas fotorresistencias que actúan como sensores, estos sensores arrojan como resultado niveles de voltaje que varían en proporción directa con la proximidad al obstáculo, los niveles de voltaje después de pasar por un comparador de niveles se convierten en niveles digitales, los cuales determinan una dirección especifica al actuar como entradas en el bus de direcciones de una memoria RAM, la cual se ha cargado con un programa, que contiene instrucciones precisas para lograr la evasión de obstáculos, estas instrucciones que provienen del bus de datos de la memoria RAM, controlan directamente 2 dispositivos transistorizados conocidos como puentes H, los cuales interactúan directamente con los motores de dirección del vehículo, indicándoles la acción de giro y por tanto ejecutando los diferentes movimientos para los cuales se diseño VEO. Es necesario por tal motivo presentar el programa que se cargo en la memoria RAM según (Catálogo,2010), lo cual representa el punto de partida para definir el alfabeto que se emplea para la descripción de la dinámica de VEO a través de autómatas finitos. En la figura 2 se puede observar la apariencia física del vehículo evasor de obstáculos.&nbsp; La forma en que se encuentran distribuidos los cuatro sensores en el vehículo se puede apreciar en la figura 2, donde cada uno de los sensores establece un bit en el bus de direcciones de la memoria RAM, teniendo por consecuencia 24 direcciones definidas en la memoria. El sensor 4 establece el primer bit de izquierda a derecha en el bus de direcciones, es decir el bit menos significativo, el sensor 3 establece el segundo bit, el sensor 2 el tercer bit, y el sensor 1 el cuarto bit, es decir el más significativo. Cabe mencionar que bajo ninguna presencia de obstáculo los sensores arrojan de manera permanente un bit en estado 0 hacia el bus de direcciones de la memoria, pero con la presencia de un obstáculo, estos arrojan un bit en estado 1. La presencia de un obstáculo en el sensor 1 arrojaría como resultado la secuencia de bits 1000 por ejemplo (ver figura 2). En cada una de las direcciones de la memoria RAM determinadas por los sensores, existe una instrucción cargada que establece la dirección de giro del motor, después de haber interactuado con el puente H transistorizado, el cual requiere de 2 bits de control (teniendo por tanto 4 posibles entradas) para realizar 3 acciones básicas que son: giro del motor hacia un sentido, giro hacia el lado contrario y permanencia estática del motor. Estas acciones se ejemplifican con mayor claridad en la tabla 1.&nbsp; El VEO cuenta con 2 motores de dirección, cada uno de los cuales está controlado por un puente H de manera independiente. En la figura 3 se aprecia la distribución de los motores en el vehículo, de donde se estableció el siguiente lineamiento de operación: el motor derecho será controlado por el puente H numero 1, y el motor izquierdo será controlado por el puente H numero 2. Motor Izquierdo Motor Derecho Figura 3. Distribución de motores de VEO (Vista trasera del vehículo). Teniendo por consecuencia la distribución de bits provenientes del bus de datos de la memoria RAM, según lo muestra la tabla 2.&nbsp; Las acciones evasoras mencionadas en la tabla 2, se describen en la tabla 3.&nbsp; En la acción evasora A, la entrada para el autómata finito estará definida por y donde y puede tomar cualquiera de las dos posibles entradas que originan el estado A en el vehículo y que son: a y d. Mientras que en la acción evasora G, la entrada para el autómata finito estará definida por z donde z puede tomar cualquiera de las 9 posibles entradas que provienen de los sensores y que originan el estado G en el vehículo, que son: f, g, h, j, k, l, n, ñ, o. Las estrategias C y D están diseñadas para evadir obstáculos que se presenten en la parte trasera del vehículo, es decir cuando se presentan obstáculos en los sensores 3 y 4. Las estrategias evasivas E y F están diseñadas para evitar obstáculos que se presenten en la parte delantera del vehículo, es decir cuando se presentan obstáculos en los sensores 1 y 2. En la figura 4(a) se resumen los movimientos anteriormente descritos. a) Estrategias evasivas b) Conjunto de trayectorias válidas Figura 4. Acciones evasoras del vehículo VEO. Antes de presentar el diagrama de transiciones que caracteriza la dinámica de VEO, es necesario establecer el conjunto de trayectorias posibles, lo cual lo hacemos con ayuda de una pequeña retícula, que representa un plano bidimensional, la cual tiene un conjunto de obstáculos a evadir, estos últimos están representados por cuadros negros en la figura 4(b); de donde se observa que el conjunto de acciones evasivas serían en forma ordenada: C, D, C, D, y que las entradas al sistema (VEO) que harían posible una trayectoria valida serían: b, c, b, c. Nótese que la permanencia en un estado no está definida como una trayectoria valida, por tanto dicho de otra forma una cadena definida por y,y,y ó b,b,b ó c,c,c ó d,d,d, etc. no es permitida por el autómata, pues en el diagrama de transición presentado en una sección posterior ni siquiera permite una transición de estados.&nbsp; Un análisis detallado a los estados posibles del vehículo y las trayectorias validas, y considerando lo establecido en la descripción de las acciones evasoras, nos permite denotar de manera formal el autómata finito no determinístico correspondiente como sigue: M = (Q, S, d, q0, F) Donde Q = {q0, q1, q2, q3, q4, q5, q6,}. S = {b, c, e, i, m, y, z}. F = {Ø}. Donde se define a F como un elemento nulo, ya que como se aprecia en la tabla 3 el vehículo no tiene definido estados finales. De una observación directa al autómata anteriormente planteado se distingue que el modelado descriptivo del vehículo se pudo realizar utilizando siete estados, después de haber redefinido el alfabeto del autómata, este se compone de cinco entradas y finalmente el estado inicial se encuentra definido por un solo estado que es q0. Resultados El modelado de la trayectoria del vehículo VEO presentado en este articulo por medio de autómatas finitos no determinísticos resultó ser una valiosa herramienta para describir de manera formal su dinámica, lo cual no representaba una tarea tan sencilla, pues VEO tiene bien definidos 7 posibles estados, lo cual complica un poco su entendimiento. Se puede notar por inspección directa por parte del lector a través de un análisis al diagrama de transición y a la función de transición presentados en este trabajo en las figuras 7 y 8 respectivamente, que el siguiente estado del vehículo, con siete estados finitos y siete entradas conocidas, se puede estimar de una forma muy sencilla y concisa, lo cual representó uno de los retos primordiales de este trabajo. Conclusiones En el presente trabajo se pudo observar que el uso de autómatas finitos no determinísticos, es una herramienta muy poderosa para elaborar los modelados descriptivos de sistemas físicos de manera digital, que permiten ser comprendidos mediante el uso de funciones de transiciones así como diagramas de transición. Para el caso del VEO, los 16 estados posibles de trayectorias, pudieron reducirse a 7, mismos que son mostrados en las figuras 6 y 7. Se establece además que el uso de autómatas finitos no se encuentra restringido solo a los sistemas digitales, y puede ser aplicado a diversos sistemas físicos en diferentes ámbitos de investigación.&nbsp; Figura 5. Diagrama de transiciones para el autómata finito no determinístico que describe la dinámica de VEO&nbsp; REFERENCIAS ? (Hopcroft,1997) Hopcroft J. E. y Ullman J. D.; Introducción a la Teoría de Autómatas, Lenguajes y Computación, Compañía Editorial Continental, S.A. de C.V., México (1997). ? (Brookshear,1989) Brookshear J. G.; Teoría de la Computación, Addison Wesley Iberoamericana, Mexico (1989). ? (Crowley,1989) Crowley J.; “World Modeling and Position Estimation for a Mobile Robot Using Ultrasonic Ranging”. IEEE Conference on Robotics and Automation, ICRA 89, Vol. 3, 1574-1579 (1989). ? (Maes,1990) Maes P. y Brooks R. A.;?Learning to coordinate behaviors”. Massachusetts Institute of Technology,1-7 (1990). ? (Seng,1997) Seng K. y Kleeman L.; ?Accurate Odometry and Error Modelling for a Mobile Robot”. IEEE International Conference on Robotics and Automation, 2783-2788 (1997). ? (Borenstein,1997) Borenstein J., Everett H. R., Feng L. y Wehe D.; ?Mobile Robot Positioning Sensors and Techniques”. Journal of Robotic Systems, Special Issue on Mobile Robots. Vol. 14 [4], 231 – 249 (1997). ? (Betke,1997) Betke M. y Gurvits L.; ?Mobile Robot Localization Using Landmarks”. IEEE Transactions on Robotics and Automation, Vol. 13 [2], 135-142, (1997) ? (Fox,1999) Fox D., Burgard W. y Thrun S.;?Markov Localization for Mobile Robots in Dynamics Environments”. Journal of Artificial Intelligence Research Vol. 11 391-427 (1999) ? (Catálogo,2010) Catalogo electrónico de circuitos integrados DataSheet (2010). <A href="http://www.datasheet4u.com/">http://www.datasheet4u.com/</A> Acerca de los autores C. M. en C. Gustavo Delgado Reyes Ingeniero en Comunicaciones y Electrónica egresado de la Escuela Superior de Ingeniería Mecánica y Eléctrica del IPN y estudiante de la Maestría en Ingeniería en Microelectrónica de la misma escuela. Actualmente es becario de CONACyT y forma parte del Programa Institucional de Formación de Investigadores. Sus áreas de interés son Sistemas en Tiempo Real, Sistemas Embebidos y Teoría de Control. C. Dr. en C. Jorge Salvador Valdez Martínez Ingeniero en Comunicaciones y Electrónica egresado de la Escuela Superior de Ingeniería Mecánica y Eléctrica del IPN, Maestro en Tecnología Avanzada por el Centro de Investigación en Ciencia Aplicada y Tecnología Avanzada del IPN y candidato Doctor en Ciencias en Comunicaciones y Electrónica por la Escuela Superior de Ingeniería Mecánica y Eléctrica Unidad Culhuacan. Sus áreas de interés son Sistemas en Tiempo Real y sistemas de control. Dr. Pedro Guevara López Doctor y Maestro en Ciencias de la Computación e Ingeniero Electricista, todos del Instituto Politécnico Nacional, Doctor en Filosofía de la Educación Iberoamericana por el Consejo Iberoamericano en Honor a la Calidad Educativa. Es Profesor Investigador de la Escuela Superior de Ingeniería Mecánica y Eléctrica y Profesor Invitado del Centro de Investigación en Ciencia Aplicada y Tecnología Avanzada pertenecientes al Instituto Politécnico Nacional. Sus áreas de investigación son: Sistemas en Tiempo Real, Modelado de Sistemas Dinámicos e Investigación Educativa.

Portada Aleph-Zero

Aleph-Zero No. 60


Revista de Educación y Divulgación de la Ciencia, Tecnología e Innovación

Una Breve Historia de la Medida .

Divulgadores. Federico Menéndez-Conde Lara Universidad Autónoma del Estado de Hidalgo, Centro de Investigación en Matemáticas, Pachuca, Hidalgo, México Contacto .

Supra/Razón de los números “granizo” .

Divulgadores. Mario Peral Manzo Universidad Pedagógica Nacional, Unidad 152, Atizapán, Estado de México, México Contacto .

La salud está en la dieta .

Divulgadores. Héctor R. Martínez, Gabriela Garza, Rodrigo E. Martínez, Ma. Guadalupe Treviño y Gerardo Rivera Universidad de Monterrey, Av. Morones Prieto 4500, Pte. San Pedro Garza García, Nuevo León, México, Tel. +52 (81) 8215-1000, ext. 1541 Contacto .

El embarazo y el cuidado dental .

Divulgadores. Héctor Martínez Menchaca1, Ma. Guadalupe Treviño Alanís2 y Gerardo Rivera Silva3 1 Director del Programa Médico Cirujano Dentista, UDEM 2 Integrante del Laboratorio de Ingeniería Tisular y Medicina Regenerativa, UDEM 3 Responsable del Laboratorio de Ingeniería Tisular y Medicina Regenerativa, UDEM Universidad de Monterrey, Av. Morones Prieto 4500, Pte. San Pedro Garza García, Nuevo León, México, Tel. +52 (81) 8215-1000, ext. 1541 Contacto .

¿Qué se derrite más rápido, un cubo o una esfera de hielo? .

Divulgadores. Diego Hernando Angulo Florez Licenciado en Química, cra 24C N 53-39 Sur, Bogotá, Colombia Tel. 7140546-3112508512 Contacto .

La imagen del cielo desde la antigüedad hasta los comienzos del siglo XX .

Divulgadores. Joan Josep Solaz-Portolés Departament de Didáctica de les Ciències Experimentals i Socials. Universitat de València, España Contacto .

El género Capsicum spp. (“chile”) .

Divulgadores. José Waizel-Bucay1, Roxana Camacho Morfín2 1 Dr.en C. Biológicas, Profesor-Investigador, Escuela Nacional de Medicina y Homeopatía, Instituto Politécnico Nacional (IPN), Calle Guillermo Massieu #239, 07320, México, DF. Becario COFAA-IPN Contacto 2 M. en C. Profesora-Investigadora, Centro Interdisciplinario de Ciencias de la Salud, Unidad Santo Tomás, IPN, México, DF. Becario EDD-IPN.

¿Cuánto cuesta la ciencia? (Abril – Junio 2011) .

Editorial. Miguel Angel Méndez Rojas Universidad de las Américas Puebla, Departamento de Ciencias Químico-Biológicas, San Andrés Cholula, 72820, Puebla, México.

Empoderando el aprendizaje matemático con Power Point: Una experiencia en un curso de nivelación universitario .

Educadores. Germán Rangel* y Cirilo Orozco Universidad de Carabobo. Unidad de Investigación en Educación Matemática, UIEMAT, Carabobo, Venezuela Contacto , Contacto .

Autómatas finitos: su aplicación para describir la trayectoria de un vehículo evasor de obstáculos .

Tecnólogos. Gustavo Delgado Reyes1, Jorge Salvador Valdez Martínez2, Pedro Guevara López3 1,2 Escuela Superior de Ingeniería Mecánica y Eléctrica, Unidad Culhuacán, Av. Santa Ana No. 1000, Col. San Francisco Culhuacán, México DF, México, Tel. (55) 57296000, ext. 73250, Contacto , Contacto 3 Centro de Investigación Ciencia Aplicada y Tecnología Avanzada, Unidad Legaria- IPN, Av. Legaria, No. 694, Col. Irrigación, México, DF, C.P. 11500 Contacto .