Autómatas finitos: su aplicación para describir la trayectoria

de un vehículo evasor de obstáculos

Aretaga Sanchez Jhonel, Epinola Benites Johann, Jorge
Universidad Nacional Truijllo, Av. ----noseee. 1000, Av. Juan Pablo II, Trujillo 13011. Peru-La
Libertad, Tel. (55) 57296000.
[email protected]

Resumen. 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.

Palabras clave – Autómatas finitos, Vehículo evasor, modelado descriptivo, diagrama

de transiciones

Introducción autómatas finitos es una herramienta

La teoría de autómatas finitos consiste muy útil en lo que a esta ciencia concierne.
en Un ejemplo es un circuito de interrupción,
modelos matemáticos de sistemas, con como la unidad de control de una
entradas y salidas discretas. El sistema computadora, el que está compuesto por un
puede estar en cualquiera de un número número finito de compuertas, cada una de
finito de configuraciones o “estados”. El las cuales pueden utilizar dos condiciones
estado del sistema resume la información posibles, por lo general denotadas por 0 y
concerniente a entradas anteriores y que es 1 hablando de valores lógicos de voltaje.
necesaria para determinar el En este contexto el presente trabajo está
comportamiento del sistema para entradas enfocado a utilizar la técnica de autómatas
posteriores. En la ciencia de la finitos para modelar las trayectorias
computación encontramos muchos posibles de un Vehículo
ejemplos de sistemas de estados finitos, y
la teoría de
Evasor de Obstáculos (VEO), que son las están designados como finales o de
diferentes salidas (estados) que se aceptación.
presentan ante diferentes entradas al Un tipo especial de autómatas son los
sistema, las que provienen de los sensores Autómatas Finitos no Determinísticos que
con los que ha sido equipado el vehículo. de acuerdo a (Brookshear,1989) analizan
cadenas construidas a partir de un alfabeto
(Hopcroft,1997) establece que un
Autómata Finito consiste en un conjunto finito y solo puede tener un numero finito
finito de estados y un conjunto de de estados, algunos de los cuales son de
transiciones de estado a estado, que se dan aceptación y uno es el estado inicial. En
sobre símbolos de entrada tomados de un este tipo de autómatas, la transición que se
alfabeto ∑. Para cada símbolo de entrada ejecuta en una etapa dada puede ser
existe exactamente una transición a partir incierta, es decir en la transición de un
de cada estado (posiblemente de regreso al
estado a otro pueden existir más de un arco
mismo estado). Un estado, por lo general
denotado como q0, es el estado inicial en rotulado e inclusive arcos que conlleven al
el que el autómata tiene su origen, mismo estado, considere la figura 1
mientras que otros estados para
clarificar el
concepto.

Inicio

1 0 q2 q0 q3
q1 q4 0 1

0
1
Figura. 1. Diagrama de transiciones para un autómata finito no
determinístico.
De manera formal se representa a un Autómata en δ si y solo si el autómata puede pasar del estado
Finito no determinístico mediante una quíntupla (Q, p al q al leer el símbolo x de la cadena de entrada.
∑, δ, q0, F), en donde Q es un conjunto finito de Así, un autómata finito no determinístico (Q, ∑, δ,
estados, ∑ es un alfabeto de entrada finito, q0 es q0, F), acepta la cadena no vacía x1, x2,..., xn є
el estado inicial y además es elemento de Q, F es ∑ si y solo si existe una secuencia de estados s0,
el conjunto de estados finales, pero en este caso s1, … sn tal que s0 = q0, sn є F y para cada entero
δ representa las posibles transiciones de la j de 1 a n, (sj-1, xj, sj) está en δ.
maquina. Es decir, el trío (p, x, q) está
Construcción del vehículo evasor de
obstáculos
El Vehículo Evasor de
Uno de los primeros trabajos que
Obstáculos (VEO de aquí en adelante)
comenzaron a formalizar la dinámica de
obtiene información del medio por el cual
robots móviles es (Crowley,1989) en el
transita a través de unos fotodiodos y unas
que se utilizan dispositivos ultrasónicos en
fotorresistencias que actúan como
el vehículo para su posicionamiento y
sensores, estos sensores arrojan como
orientación. En (Maes,1990) se muestra un
resultado niveles de voltaje que varían en
estudio del comportamiento de robots
proporción directa con la proximidad al
autónomos y se divide en construcción de
obstáculo, los niveles de voltaje después
mapas, exploración, transitar y evasión de
de pasar por un comparador de niveles se
obstáculos. En (Seng,1997) se plantea
convierten en niveles digitales, los cuales
como una de las mayores problemáticas de
determinan una dirección especifica al
la navegación robótica la localización y se
actuar como entradas en el bus de
proponen los pasos claves para el diseño,
direcciones de una memoria RAM, la cual
calibración y modelado de autómatas. Hay
se ha cargado con un programa, que
otros autores que refuerzan la evasión de
contiene instrucciones precisas para lograr
objetos o desarrollo de trayectorias
la evasión de obstáculos, estas
mediante técnicas de navegación como
instrucciones que provienen del bus de
son: navegación inercial, compases
datos de la memoria RAM, controlan
magnéticos y
directamente
triangulación.(Borenstein,1997).
2 dispositivos transistorizados conocidos
(Betke,1997) considera que el autómata como puentes H, los cuales interactúan
puede reconocer marcas especificas en el directamente con los motores de
medio por el cual se desplaza usando dirección del vehículo, indicándoles la
reconocimiento de patrones visuales. La acción de giro y por tanto ejecutando los
localización robótica así como la evasión diferentes movimientos para los cuales se
de obstáculos del autómata, ha llegado a diseño VEO. Es necesario por tal motivo
ser uno de los problemas fundamentales en presentar el programa que se cargo en la
los robots móviles, y por ello, en memoria RAM según (Catálogo,2010), lo
(Fox,1999) se presenta una versión de la cual representa el punto de partida para
localización Markov, en donde la idea definir el alfabeto que se emplea para la
principal es mantener una densidad de descripción de la dinámica de VEO a través
probabilidad sobre el espacio de todas las de autómatas finitos.
localizaciones posibles de un robot en su
En la figura 2 se puede observar la
entorno.
apariencia física del vehículo evasor de
obstáculos.
 Año 16, Número 60, Abril – Junio 2011

Sensor 4 (Bit Sensor

1) Bit menos 2 (Bit
significativo 3)

Sensor Sensor 1 (Bit

3 (Bit 4) Bit más
2) significativo

Figura 2. Vehículo Evasor de Obstáculos (VEO).

La forma en que se encuentran distribuidos bit en estado 1. La presencia de un

los cuatro sensores en el vehículo se puede obstáculo en el sensor 1 arrojaría como
apreciar en la figura 2, donde cada uno de resultado la secuencia de bits 1000 por
los sensores establece un bit en el bus de ejemplo (ver figura 2).
direcciones de la memoria RAM,
En cada una de las direcciones de la
teniendo por consecuencia 24 direcciones memoria RAM determinadas por los
definidas en la memoria. El sensor 4 sensores, existe una instrucción cargada
establece el primer bit de izquierda a que establece la dirección de giro del
derecha en el bus de direcciones, es decir motor, después de haber interactuado con
el bit menos significativo, el sensor 3 el puente H transistorizado, el cual requiere
establece el segundo bit, el sensor 2 el de 2 bits de control (teniendo por tanto 4
tercer bit, y el sensor 1 el cuarto bit, es decir posibles entradas) para realizar 3
el más significativo. Cabe mencionar que acciones básicas que son: giro del motor
bajo ninguna presencia de obstáculo los hacia un sentido, giro hacia el lado
sensores arrojan de manera permanente un contrario y permanencia estática del
bit en estado 0 hacia el bus de direcciones motor. Estas acciones se ejemplifican con
de la memoria, pero con la presencia de un
mayor claridad en la tabla 1.
obstáculo, estos arrojan un
 Tabla 1. Operación del puente H y direcciones de giro de los motores.
Entrada al Puente Estado del Motor
H

(Bits de
00
Control) Permanencia estática

01 Giro hacia delante

10 Giro hacia atrás

11 Estado prohibido

El VEO cuenta con 2 motores de dirección, estableció el siguiente lineamiento de

cada uno de los cuales está controlado operación: el motor derecho será
por un puente H de manera independiente. controlado por el puente H numero 1, y el
En la figura 3 se aprecia la distribución motor izquierdo será controlado por el
de los puente H
motores en el vehículo, de donde numero 2.
se

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.
 Tabla 2. Programa cargado en la memoria RAM de VEO.
Entradas Alfabet Entradas Acció Entradas Alfabeto Entradas Acción
o al puente n al puente evasor
(Sensores evasor (Sensores ∑
H H a
) ∑ )
a
0000 a 0101 A 1000 i 1000 E

0001 b 0001 C 1001 j 0110 G

0010 c 0111 D 1010 k 0110 G

0011 d 0101 A 1011 l 0110 G

0100 e 0010 F 1100 m 1010 B

0101 f 0110 G 1101 n 0110 G

0110 g 0110 G 1110 ñ 0110 G

0111 h 0110 G 1111 o 0110 G

Las acciones evasoras mencionadas en la tabla 2, se describen en la tabla 3.

Tabla 3. Descripción de acciones evasoras del VEO.

Acción
Significado Descripción de la acción Estado
Evasora
A Avanzar hacia adelante Ambos motores giran hacia delante qo
B Avanzar hacia atrás Ambos motores giran hacia atrás q1
Giro a la izquierda y Motor derecho gira hacia adelante y motor
C q2
hacia delante izquierdo no gira
Giro a la derecha y Motor izquierdo gira hacia adelante y motor
D q3
hacia delante derecho no gira
Giro a la izquierda y Motor izquierdo gira hacia atrás y motor derecho
E q4
hacia atrás no gira
Giro a la derecha y Motor derecho gira hacia atrás y motor izquierdo
F q5
hacia atrás no gira
Giro rápido El motor izquierdo gira hacia adelante y el motor
G q6
derecho gira hacia atrás
En la acción evasora A, la entrada para el están diseñadas para evadir obstáculos
autómata finito estará definida por y donde que se presenten en la parte trasera del
y puede tomar cualquiera de las dos vehículo, es decir cuando se presentan
posibles entradas que originan el estado obstáculos en los sensores 3 y 4. Las
A en el vehículo y que son: a y d. Mientras estrategias evasivas E y F están diseñadas
que en la acción evasora G, la entrada para evitar obstáculos que se presenten en
para el autómata finito estará definida por la parte delantera del vehículo, es decir
z donde z puede tomar cualquiera de las 9 cuando se presentan obstáculos en los
posibles entradas que provienen de los sensores 1 y 2. En la figura
sensores y que originan el estado G en el 4(a) se resumen los movimientos
vehículo, que anteriormente descritos.
son: f, g, h, j, k, l, n, ñ, o. Las estrategias C
yD

a) Estrategias evasivas b) Conjunto de trayectorias

válidas

Figura 4. Acciones evasoras del vehículo VEO.

Antes de presentar el diagrama de transiciones las entradas al sistema (VEO) que harían
que caracteriza la dinámica de VEO, es posible una trayectoria valida serían: b, c, b,
necesario establecer el conjunto de trayectorias c. Nótese que la permanencia en un estado
posibles, lo cual lo hacemos con ayuda de una no está definida como una trayectoria valida,
pequeña retícula, que representa un plano por tanto dicho de otra forma una cadena
bidimensional, la cual tiene un conjunto de definida por y,y,y ó b,b,b ó c,c,c ó d,d,d, etc.
obstáculos a evadir, estos últimos están no es permitida por el autómata, pues en el
representados por cuadros negros en la figura diagrama de transición presentado en una
4(b); de donde se observa que el conjunto de sección posterior ni siquiera permite una
acciones evasivas serían en forma ordenada: transición de estados.
C, D, C, D, y que
Un análisis detallado a los estados pues VEO tiene bien definidos 7 posibles
posibles del vehículo y las trayectorias estados, lo cual complica un poco su
validas, y considerando lo establecido en la entendimiento. Se puede notar por
descripción de las acciones evasoras, inspección directa por parte del lector a
nos permite denotar de manera formal el través de un análisis al diagrama
autómata finito no determinístico de transición y a la función de transición
correspondiente como sigue: presentados en este trabajo en las figuras
7 y 8 respectivamente, que el siguiente
M = (Q, ∑, δ, q0, F)
estado del vehículo, con siete estados
Donde Q = {q0, q1, q2, q3, q4, q5,
q6,}. finitos y siete entradas conocidas, se puede
∑ = {b, c, e, i, m, y, z}. estimar de una forma muy sencilla y
F = {Ø}. concisa, lo cual representó uno de los retos
primordiales de este trabajo.
Donde se define a F como un elemento Conclusiones
nulo, ya que como se aprecia en la tabla 3 En el presente trabajo se pudo observar
el vehículo no tiene definido estados que el uso de autómatas finitos no
finales. De una observación directa al determinísticos, es una herramienta muy
autómata anteriormente planteado se poderosa para elaborar los modelados
distingue que el modelado descriptivo del descriptivos de sistemas físicos de manera
vehículo se pudo realizar utilizando siete digital, que permiten ser comprendidos
estados, después de haber redefinido el mediante el uso de funciones de
alfabeto del autómata, este se compone de transiciones así como diagramas de
cinco entradas y finalmente el estado transición. Para el caso del VEO, los 16
inicial se encuentra definido por un solo estados posibles de trayectorias, pudieron
estado que es q0. reducirse a 7, mismos que son mostrados
Resultados en las figuras 6 y 7.

El modelado de la trayectoria del vehículo Se establece además que el uso de

VEO presentado en este articulo por autómatas finitos no se encuentra
medio de autómatas finitos no restringido solo a los sistemas digitales, y
determinísticos resultó ser una valiosa puede ser aplicado a diversos sistemas
herramienta para describir de manera físicos en diferentes ámbitos de
formal su dinámica, lo cual no investigación.
representaba una tarea tan sencilla,
 i
i c
b m
e b q2
c c
q3

c i
c
y b y b m

y m z b
e c q4 q0 q1
i y

z
i e y e y mz b

z z q6
q5 e
e
i
z m

m
Figura 5. Diagrama de transiciones para el autómata finito no determinístico que
describe la dinámica de VEO.

Entrad
Estado b c e as
i m y z
s q { q2 } { q3 } { q5 } { q4 } { q1 }
0 Ø { q6 }
{ q2 } { q3 } { q5 } { q4 } Ø
q { qo } { q6 }
1 Ø { q3 } { q5 } { q4 } { q1 }
q { qo } { q6 }
2 { q2 } Ø { q5 } { q4 } { q1 }
{ qo } { q6 }
q
Figura 6. Función q2 } { qδ3para
de {Transición } el{ qautómata
5} finito
Ø no determinístico
{ q1 } de la
3 {figura
qo } 7 { q6 }
q { q2 } { q3 } Ø { q4 } { q1 }
4 { q o } { q 6 }
{ q2 } { q3 } { q5 } { q4 } { q1 }
q { qo } Ø
5
q
6
 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).
http://www.datasheet4u.com/
i o n s
t a t s