AUTOMATAS FINITOS EN LA ROBOTICA

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,
dengue_mgs4@hotmail.com, jsvaldezmtz@yahoo.com.mx
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
pguevara@ipn.mx
 
 
Resumen. En el presente trabajo, se muestra unarepresentació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 einterpretada 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. 
 Palabras clave – Autómatas finitos, Vehículo evasor, modelado descriptivo, diagrama de transiciones  
 
Introducción
 
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 anterioresy 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 unnú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 sepresentan 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 ∑. Para cada símbolo de entrada existe exactamente una transición a partir decada 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 finitoy 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.
 ...