COMPRENDAMOS

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. 

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.  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.  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.  Las acciones evasoras mencionadas en la tabla 2, se describen en la tabla 3. 

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. 

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.  Figura 5. Diagrama de transiciones para el autómata finito no determinístico que describe la dinámica de VEO.