Cerebro robótico para navegación de búsqueda de objetos (página 2)

La importancia de este estudio se puede definir por la necesidad de crear sistemas autónomos que funcionen sin la intervención humana y que puedan ser aplicados en muchas áreas de la ciencia y la industria. El estudio de estos sistemas llevará al descubrimiento de nuevas tecnologías para mejorar procesos, alcanzar objetivos que todavía no se han alcanzado y además para terminar de entender el comportamiento de estos complejos sistemas en diferentes escenarios.

Este proyecto representa un estudio que puede ser aplicado en muchas áreas de la industria donde se necesiten sistemas que realicen actividades autónomas de algún tipo, como por ejemplo: Sistemas de emergencia, sistemas para la solución de problemas en tiempo real, robots de limpieza de oficinas, robots autónomos que realicen tareas varias, etc. También se pueden aplicar a diferentes áreas de la ciencia, por ejemplo: robots exploradores, robots que puedan realizar actividades de reparación en diferentes tipos de equipos incluyendo otros robots, etc.

El alcance del proyecto es generar un sistema difuso utilizando el método de conductas, evolucionarlo con un algoritmo genético y obtener los mejores resultados para luego simularlos y ver cómo se comporta el individuo obtenido en el ambiente designado.

1.2. OBJETIVO GENERAL

Contribuir al desarrollo inicial del cerebro robótico que permitirá la navegación de manera autónoma para el proyecto del "Scavenger Hunt" de UNITEC San Pedro Sula.

1.3. OBJETIVOS ESPECIFICOS

Investigar los diferentes métodos utilizados para crear sistemas autónomos y aplicar uno de ellos en el desarrollo del cerebro robótico.

Crear una aplicación que permita evolucionar y simular los cerebros robóticos, lo cual permitirá probarlos antes de implementarlos en el robot real.

CAPÍTULO 2

Marco teórico

• Robots Autónomos

La autonomía de los robots se puede definir como la realización de tareas por parte de éstos sin la supervisión humana. Dentro de la autonomía se consideran muchos aspectos que incluyen: Navegación, planificación de tareas, realización de tareas de reparación a si mismo o a otros robots, etc. Por la complejidad de las tareas y los problemas con los que se encuentran los robots, es importante generar sistemas que manejen de forma eficiente la información que se recibe desde el entorno por medio de los dispositivos de entrada (i.e. Sensores Infrarrojos, Radares, etc.) y como se van a exteriorizar estos datos por medio de los dispositivos de salida (i.e. Motores, otros Sensores, etc.) de tal forma que el robot pueda hacer su tarea con el mínimo error posible.

En Tsourveloudis et al (2005), se describe a los robots autónomos como: ".vehículos capaces de realizar tareas en ambientes no estructurados, desconocidos y que pueden ser peligrosos.". También se describen como ".entes capaces de operar y funcionar de manera semiautónoma o autónoma que no necesitan intervención humana.". Sin embargo, falta mucho para que los robots que no son controlados por humanos se conviertan en entidades completamente autónomas en ambientes variados.

Para Surmann et al (1995), ".un robot autónomo se enfrenta a la incertidumbre del entorno en el que se encuentra y por lo tanto a información incompleta o aproximada.", por esta razón es que los sistemas autónomos deben ser autoreconfigurables, lo que quiere decir que pueden cambiar a medida que el entorno vaya cambiando.

"Las limitantes de los robots actuales están dadas por las limitantes del hardware que se utiliza para construirlos.", por lo tanto hay varios niveles de autonomía que se pueden definir según Tsourveloudis et al (2005). También se pueden relacionar varias características operacionales relacionadas con estos robots: Percepción, Inteligencia y Acción. Por percepción se entiende como ".el uso del conocimiento adquirido a cerca del entorno y de si mismo para realizar tareas que no estén definidas dentro de los parámetros iniciales del sistema.". La inteligencia es ".la capacidad de desenvolverse dentro del entorno sin asistencia humana y resolver los problemas a los que se enfrenta el robot.". Por último tenemos la acción, que simplemente es ".la capacidad de recorrer una distancia e ir de un punto A a un punto B sin la ayuda humana y sin quedar atascado.".

• Sensores

En los robots autónomos, una de las partes más importantes es el arreglo o conjunto de sensores que proveen la entrada al sistema que rige al robot. Tanto la cantidad como la localización de cada uno de ellos hacen complejo el diseño de dichos robots, también se debe tomar en cuenta cuales son los sensores que ayudan de la forma más eficiente a la interacción del robot con su entorno. El robot debe tener la capacidad de detectar todos los obstáculos que se le presenten en todas las direcciones posibles, dado que dichos obstáculos pueden tener formas variables, y pueden estar en posiciones que crean confusión en el robot si no se detectan de forma correcta.

Según Aboshosha (2003), ".los sensores se pueden dividir en 2 clases: activos y pasivos. Los activos se conocen como sensores reactivos que envían y reciben señales moduladas, por ejemplo: Sonar, Láser, Radar y los Sensores Infrarrojos. Los pasivos miden y detectan cantidades físicas.", también este autor presenta que:

Las ventajas de los sonares sobre el láser lo hacen una de las mejores opciones para los robots autónomos. Los Sensores Sonares son relativamente más baratos comparados con los localizadores de láser. Los Sonares son más pequeños y ligeros, por lo tanto se pueden montar de forma flexible en el cuerpo del robot. En muchas aplicaciones se ha observado que la abertura del ángulo es un factor decisivo en la detección de obstáculos. Y los Sonares no consumen mucha energía, por lo tanto no son una carga para las baterías del robot.

Se puede decir entonces que los Sonares son una de las mejores opciones para implementar la navegación autónoma por su precio, facilidad de instalación y alcance, pero también tienen varias desventajas que los hacen inadecuados para ciertas ocasiones.

En Aboshosha (2003) se presentan varias desventajas para los Sonares:

Como es una onda mecánica que se mueve por el aire, es absorbida y pierde velocidad, esto lleva a un incremento en la distancia estimada y no en el valor actual. Idealmente, el Sonar reflejaría la onda directamente desde el obstáculo hacia el receptor, pero en el mundo real las ondas se reflejan en múltiples obstáculos antes de retornar al receptor, la distancia estimada es mayor que la real. Normalmente, el robot tiene múltiples sensores, entonces varios sonares envían ondas de sonido idénticas, generando un problema de comunicación cruzada, esto se puede evitar dándole a cada sonar una identificación de onda diferente. Los Sonares tienen un rango de medida limitado (~0.30:6.5m) y una dirección angular (~9:39°), fuera de estos rangos la información es incierta. Los cambios en temperatura, humedad y presión influyen en la velocidad de la onda, por lo tanto la distancia al objeto puede ser errónea. Perdida de datos puede ocurrir si la onda reflejada es muy débil para ser detectada por el receptor o si la onda es reflejada fuera del rango de detección. Comparado con el láser, el Sonar es más lento, esto se obtiene por la diferencia de velocidad entre la luz y el sonido.

Para situaciones donde el robot no está expuesto a muchos cambios ambientales el uso de Sonares puede resolver el problema, por ejemplo para robots que se encuentran en cuartos cerrados o en oficinas.

Otro tipo de Sensor es el láser (Light Amplification by Stimulated Emisión of Radiation, que significa Amplificación de Luz por Emisión Estimulada de Radiación). Para Aboshosha (2003) las ventajas del láser son:

El láser es rápido, su precisión es mayor dado que tiene una desviación estándar, para la última generación de láser, de 10 mm y de la resolución angular de 0.25°. La resolución angular es mucho mejor con el láser que con el sonar. La información obtenida por el láser puede ser interpretada directamente desde la distancia al obstáculo en cualquier dirección.

En la navegación de robots se necesita que la respuesta de los sensores sea lo mejor posible, en este caso es mejor el láser que el sonar, pero el láser tiene varias desventajas, que según Aboshosha (2003) son:

El láser provee información limitada a un plano cartesiano, para resolver este problema se pueden montar en plataformas giratorias que le dan un poco de ventaja. El láser consume una cantidad considerable de energía comparado con los otros sensores. Es más costoso que los otros sensores por su complejidad. Algunos obstáculos pueden no ser detectados por el láser, pro ejemplo el cristal no produce reflejo.

En los casos donde los materiales puedan generar interferencia con el láser, como los cristales, se utilizan combinados con otros sensores, como por ejemplo el sonar, dado que el láser presenta una respuesta mayor ante los obstáculos y mayor precisión, pero puede fallar con estos materiales que no reflejan la luz hacia el receptor.

"Los sensores más utilizados en robots miniaturas son los infrarrojos, dado que su alcance es de 10 a 80 cm, también son utilizados como sensores secundarios en sistemas más complejos", según Aboshosha (2003). Además de esto, los sensores infrarrojos son baratos y se pueden montar fácilmente en cualquier tipo de robot. "Estos sensores son insensibles a la luz del ambiente y al tipo de superficie por que dependen de señales infrarrojas moduladas", para Aboshosha (2003) esta es una gran ventaja para los robots que utilizan este tipo de sensores.

Es posible tener otra subdivisión para los sensores según Aboshosha (2003), ".sensores inspirados por la biología y los no inspirados por la naturaleza o sintéticos.". Dentro de esta nueva clasificación se encuentras los siguientes:

Dentro de los sensores de posicionamiento, utilizados para posicionar al robot con respecto a su entorno, se pueden encontrar los sensores reactivos como el sonar, láser, etc., brújulas digitales, visión geométrica, sistemas de posicionamiento global, etc. También se encuentran los sensores de detección de movimiento, utilizados para detectar parámetros de movimiento, dentro de estos se encuentran los sensores de rotación y translación, velocidad rotacional y longitudinal, aceleración, vibración, etc. Los sensores de visión también se pueden encontrar dentro de esta clasificación, utilizados para la vigilancia y el reconocimiento del entorno por parte del robot, dentro de estos sensores se pueden resaltar las cámaras, láser 3D, cámaras infrarrojas, etc. Los sensores inspirados por la biología pueden ser imitaciones de órganos sensoriales, por ejemplo: narices electrónicas para imitar el sentido del olfato, piel artificial o sensores de tacto para reconocer superficies, analizadores de sonido para el reconocimiento de voz, sensores para imitar la visión humana para reconocer el ambiente que rodea al robot. Por ultimo están los sensores ambientales, que se utilizan para reconocer el entorno que rodea al robot y detectar fenómenos físicos por ejemplo: Temperatura, presión atmosférica, radiación, humedad, velocidad y dirección del viento, ondas electromagnéticas, detectar metales, campos magnéticos, etc.

Uno de los modelos estudiados por Tsourveloudis et al (2005) utiliza 12 sensores sonares que se agrupan así: 10 sensores en 2 grupos de 5 responsables de la detección de obstáculos para el frente y la parte trasera, y 6 sensores en 2 grupos de 3 para la entrada de los otros 2 controles difusa que se encargan de la detección de obstáculos a ambos lados del robot.

En el modelo propuesto por Yang et al (2006a), se tiene un robot circular que se divide en 2 áreas simétricas, por lo que desarrollando una de ellas se puede duplicar para la otra. Cada semicírculo se divide en 4 áreas de igual tamaño, colocan en el centro de cada área un sensor, lo que da un total de 4 sensores por cada semicírculo, en total 8 para el robot. Cada uno tiene una función especial en la obtención de datos que utiliza el sistema difuso que utiliza el robot.

En el modelo de Yang et al (2006b) se utiliza un robot Koala manufacturado por K-team equipado con 6 ruedas diferenciales, un motor de corriente directa y velocidad incremental, un microprocesador de 16 MHz Motorota 68331 y un anillo de 16 sensores infrarrojos de proximidad y ambiente. Los sensores infrarrojos proveen un rango de medida de la distancia hacia el objeto de 5 a 20 cm.

En Na et al (2003) se utilizan 8 sensores ultrasónicos agrupados en subconjuntos de 5 sensores y el promedio de las lecturas es la entrada que obtiene la red neuronal que se encarga de la navegación del robot. Las características de estos sensores son: Frecuencia de Operación = 43KHz a 48KHz, Frecuencia de Resonancia = 45KHz, Rango de pulso = 25Hz, Sensitividad = 6 pulgadas a 35 pies y el Angulo de acción = -15 a 15 grados.

El robot que se describe en Surmann (1995), llamado "MORIA", tiene 2 motores de velocidad variable y 8 sensores sonares que se localizan 3 en frente, 3 atrás y 2 a los lados del robot, estos sensores le proporcionan los datos al sistema basado en lógica difusa.

En Yang et al (2006a) se propone un sistema que depende por completo de los sensores localizados en 8 lugares específicos del robot. Los sensores están localizados en lugares estratégicos para darle una mejor percepción al robot, se tienen 2 sensores para revisar el frente, 2 para revisar entre el frente y el lado, 2 para revisar atrás y al lado y 2 para atrás, cada uno de estos se toma en cuenta en cada momento, y haciendo uso de la función NEAR, se decide cual conducta se va a ejecutar.

Se pudo determinar que los mejores sensores que se pueden utilizar, por su facilidad de manejo, precio y funcionamiento, son los sensores ultrasónicos o sonares. Por estas razones se utilizan para la navegación de robots, además los sonares encajan bien donde otros pueden fallar, por esto se escogieron para el modelo que se presenta en este documento.

• Robótica Basada en Conductas

Según Mitchell (1997), ".hay 2 tipos de aprendizaje para robots: aprendizaje inductivo y analítico.", dentro del aprendizaje inductivo se pueden tomar en cuenta las redes neuronales y los árboles de decisión. Dentro del aprendizaje analítico se encuentra el Prolog-EBG, que funciona con definiciones previas que se van verificando a medida que el robot interactúa con el entorno. Igualmente en Mitchell (1997), ".los métodos de aprendizaje analíticos puros ofrecen la ventaja de generalizar con mayor precisión y menos datos usando el conocimiento previo para el aprendizaje, pero pueden fallar si se les da poca información o información errónea.". Para Mitchell (1997), "Los animales utilizan el aprendizaje por experiencia, experimentan situaciones y aprenden sin necesidad de información previa.", por lo tanto los animales utilizan una forma de aprendizaje inductiva donde las situaciones a las que se enfrentan les permiten aprender los resultados de sus acciones.

Para Nolfi (2005), ".una conducta es un proceso dinámico que resulta de la interacción no lineal entre un agente (natural o artificial), su cuerpo y el ambiente externo (incluyendo el ambiente social).", lo que quiere decir es que cada acción resultante de la influencia del entorno hacia el agente es lo que se puede considerar como una conducta. ".por lo tanto estos sistemas son extremadamente difíciles de diseñar desde la perspectiva de un observador externo, y pueden ser desarrollados eficientemente por medio de métodos de autoorganización (por ejemplo métodos evolutivos).", esto según lo observado por Nolfi (2005).

En Tunstel (2001), ".se utiliza la etología (la etología es la ciencia que analiza los comportamientos animales y desarrolla modelos y explicaciones basada en observaciones externas) como medio para generar sistemas basados en conductas, tomando como referencia las conductas que presentan los animales al ser enfrentados a diferentes actividades que no están acostumbrados a hacer.". Esto permite obtener diferentes conductas para diferentes actividades, por ejemplo evitar obstáculos.

Varios métodos se utilizan para resolver los problemas que se presentan en el arbitraje de conductas, se mencionan 2 modelos en Tunstel (2001), "el primero se basa en prioridades y donde solamente una conducta puede estar activa en un momento dado". "En el segundo modelo, se utiliza la activación concurrente de múltiples conductas, lo que se asemeja a lo observado en varias investigaciones hechas basadas en la etología.".

Una propuesta diferente se describe en Na et al (2003), ".se presenta una arquitectura hibrida que combina el uso de navegación reactiva basada en conductas y la clasificación del entorno basada en modelos, también se utiliza coordinación competitiva y cooperativa para el control de las conductas.".

Para la coordinación competitiva se utiliza el resultado de la clasificación de la red neuronal y determinar cual es la acción a tomar. En el método cooperativo se puede utilizar más de una salida de más de una conducta, pero este método es vulnerable a situaciones como son los Deadlocks, por la cancelación de fuerzas opuestas mientras que el método competitivo tiende a evitar esta situación dado que selecciona una sola conducta para generar la salida.

En el caso anterior se utilizan redes neuronales que se encargan de hacer la clasificación del entorno del robot que se basa en 16 prototipos de mapas topológicos que se utilizan para la navegación del sistema, estos son algunos: Pasillos, puertas, intersecciones, etc. Luego se utiliza un controlador de conductas que se basa en redes neuronales y se entrena para que aprenda los diferentes comandos de la navegación humana para cada uno de los 16 prototipos anteriores, estos comandos son: Continuar recto, girar a la izquierda y girar a la derecha.

Para el arbitraje de las conductas se utiliza un método llamado campo potencial modificado (MPF, Modified Potential Field) donde hay un vector de espacio libre y que en conjunto con la red neuronal entrenada con los comando de navegación se utiliza para seleccionar la conducta a utilizar en ese momento.

Finalmente, se combinan los tres métodos anteriores para generar el sistema hibrido que permite al robot reconocer diferentes tipos de espacios y reaccionar activando una de las conductas para ejecutar el comando correcto. Los 2 sensores del centro se utilizan para detección de casos de emergencia. La conducta de emergencia simplemente agrega una corrección de dirección a la red neuronal para corregir el comando de salida.

• Lógica Difusa

El termino Lógica Difusa nació de la teoría difusa de conjuntos desarrollada por Lotfi Zadeh en 1965. Según Jantzen (1998), Lofti Zadeh afirma que: "Los conjuntos que vemos en el mundo que nos rodea son definidos por límites que no son distintos.", esto quiere decir que todos los conjuntos que nos rodean tienen un rango de membresía o pertenencia de sus elementos igual para todos, este rango es [0,1].

• Introducción a la Lógica Difusa

Jantzen (1998) muestra el contraste entre la lógica booleana y la difusa:

La lógica booleana basada únicamente en los valores "Verdadero" y "Falso" es inadecuada, en muchos casos, para describir sucesos como el razonamiento humano, que son imprecisos y que no tienen un valor definido. La lógica difusa utiliza todo el intervalo completo entre 0 ("Falso") y 1 ("Verdadero") para describir estos sucesos.

Según Martín del Brío et al (2002), ".la teoría de conjuntos difusos parte de la teoría clásica de conjuntos, añadiendo una función de pertenencia al conjunto, definida ésta como un número entre 0 y 1".

Como se puede observar, la lógica difusa permite representar valores que no se pueden representar con la lógica clásica o Booleana. Esta característica es muy importante al momento de resolver un problema y obtener diferentes soluciones para resolverlo, pues permite la representación de datos inciertos.

También en Jantzen (1998) se muestra la diferencia entre los conjuntos de la lógica clásica y los conjuntos de la teoría difusa:

Un conjunto, en su definición clásica, es una colección de elementos y puede ser tratado como una entidad dentro de un universo tal que los elementos del universo pueden o no ser miembros de ese conjunto. En la teoría difusa un elemento no solamente tiene el criterio "Verdadero" o "Falso", sino que tiene un nivel de membresía o pertenencia en el conjunto de la teoría difusa, el nivel de pertenencia de todos los miembros del conjunto es lo que describe al conjunto.

Funciones de Membresía

Para el universo X y una función de membresía el conjunto difuso A se define como:

La función de membresía µA(x) cuantifica el grado de membresía de los elementos x pertenecientes a X. El valor 0 significa que el elemento no esta incluido en el conjunto, 1 significa que el elemento esta completamente incluido. Los valores entre 0 y 1 son los miembros de la lógica difusa del conjunto.

Hay varios tipos de funciones de membresía que se utilizan comúnmente para diseñar sistemas basados en lógica difusa, algunas de estas son:

Figura 1: Función de membresía Triangular Figura 2: Función de membresía Trapezoidal

Figura 3: Función de membresía Gaussiana Figura 4: Función de membresía Sigma

Por ejemplo, si se toma en cuenta la temperatura podemos decir que 0° es frío y que 40° es caliente, pero que sucede con las temperaturas intermedias? Y las que son menores que 0° y mayores que 40°? Para estos casos es que se utiliza el grado de membresía o pertenencia de la teoría difusa, para que el cambio de un elemento de ser miembro a no serlo sea menos abrupto.

• Operaciones Difusas

En Hellman (2001), se muestra un ejemplo de las operaciones en la lógica difusa:

Figura 5: Ejemplo de Conjuntos difusos.

Figura 6: Ejemplo del operador AND Figura 7: Ejemplo del operador OR

Figura 8: Ejemplo del operador NOT

En el ejemplo anterior se muestran 2 conjuntos de lógica difusa y se presentan las operaciones AND, OR y NOT, que son los equivalentes de la unión, la intersección y la negación de la lógica booleana y trabajan de la misma forma, por ejemplo en la Intersección se toman los elementos que pertenecen a ambos conjuntos, en la Unión se toman los elementos que pertenecen a cualquiera de los 2 conjuntos y en la negación se obtienen los elementos que no pertenecen al conjunto.

• Inferencia Difusa

Al igual que en la lógica Booleana, en la lógica difusa existe un método de inferencia que permite obtener las reglas de difusas que describen el comportamiento de los sistemas basados en lógica difusa. Todas las reglas de inferencia son de la forma:

Si A1 (y/o A2 y/o A3.) entonces B1 (y B2 y B3.)

Donde A1, A2, A3. son funciones de membresía que proveen la entrada al sistema basado en lógica difusa y B1, B2, B3. son las funciones de membresía que equivalen a las combinaciones u operaciones de las funciones de entrada.

También se puede definir la inferencia difusa como el proceso de mapear desde una entrada hacia una salida usando la lógica difusa. El mapeo provee una base desde la cual se pueden tomar decisiones o encontrar patrones. Hay 2 tipos de inferencia difusa: Mamdani y Sugeno. La diferencia más importante entre estos dos tipos de inferencia se encuentra en la forma como se determinan las salidas del sistema.

2.4.4.1. Método de inferencia Mamdani

El método de inferencia Mamdani es el más comúnmente utilizado visto en la metodología difusa. Este método fue uno de los primeros sistemas de control que utilizaba la teoría de conjuntos difusos. Fue propuesto por Ebrahim Mamdani en 1975 en un intento por controlar un sistema combinado de un motor de vapor y un tanque.

En este tipo de inferencia se espera que la función de membresía de salida sea un conjunto difuso. Después del proceso de agregación, hay un conjunto difuso para cada una de las variables de salida que necesita ser defusificada. Es posible, y en muchos casos más eficiente, utilizar una función de membresía con una sola cresta que un conjunto difuso distribuido. Este tipo de funciones de membresía son conocidas como Singletons y pueden ser vistos como conjuntos difusos defusificados.

2.4.4.2. Método de inferencia Sugeno

El método Sugeno, o método Takagi-Sugeno-Kang, fue introducido en 1985 y es similar al método Mamdani por que las primeras 2 fases, proceso de fusificación de las entradas y la aplicación del operador difuso, de ambos procesos son iguales. La diferencia entre estos dos métodos es que las funciones de membresía de salidas del método Mamdani pueden ser lineales o constantes, pero para el método Sugeno, si las entradas son "x" y "y", la salida es z=ax + by + c. La salida final del sistema es el promedio de los valores de las reglas de salida que se calcula de la siguiente manera:

• Reglas Difusas

En Martín del Brío, B. et al (2002), "Las Reglas Difusas combinan uno o más conjuntos difusos de entrada, llamados antecedentes o premisas, y le asocian un con junto borroso de salida, llamado consecuente o consecuencia". De la misma forma "Las reglas difusas permiten expresar el conocimiento que se dispone sobre la relación entre antecedentes y consecuentes". Por lo tanto, las reglas difusas son un conjunto de relaciones entre los elementos de entrada o antecedentes y los de salida o consecuentes.

En Yang et al (2006b) se estudian 2 problemas comunes de los sistemas autónomos basados en la lógica difusa:

El problema GUWLO (Goal-Unreachable with Large Obstacles) ocurre cuando el valor absoluto del ángulo de la meta es grande y la dirección hacia la izquierda o derecha esta completamente bloqueada. Para resolver este problema se utiliza un ángulo temporal considerando la superficie del obstáculo en frente del robot. El problema GUWNO (Goal-Unreachable with Nearby Obstacles) surge cuando los obstáculos están cerca de la meta. Este problema se resuelve incluyendo un eliminador e en el sistema de navegación, tomando en cuenta la distancia relativa entre el robot y la posición de la meta.

En el sistema anterior se calcula d, que es la distancia entre el robot y un obstáculo. En la función NEAR se utilizan los datos obtenidos por los sensores individualmente y estos afectan la velocidad de cada uno de los motores. En el siguiente ejemplo se muestra como afecta cada sensor la velocidad del motor 1, en este caso V1 es el cambio de la velocidad del motor. Para V1 se utiliza el conjunto de la lógica difusa formado por los elementos: NVB (Negativo Muy Grande), NB (Negativo Grande), NS (Negativo Pequeño) y PS (Positivo Pequeño), por lo tanto las reglas de la lógica difusa para el cambio de velocidad son:

– Si d detectada por Sensor-Frontal es NEAR, entonces 1V es NVB.

– Si d detectada por Sensor-Frente-Lado es NEAR, entonces 1V es NB.

– Si d detectada por Sensor-Atrás-Lado es NEAR, entonces 1V es NS.

En Saffiotti(1995) se muestra un conjunto diferente de reglas de lógica difusa para manejar la dirección del robot:

– Si Obstáculo-Enfrente Lejos entonces Seguir-Adelante.

– Si Obstáculo-Derecha Cerca entonces Mover-Izquierda.

– Si Obstáculo-Derecha Lejos entonces Mover-Derecha.

En el caso anterior, las funciones Lejos y Cerca se manejan con las entradas de los diferentes sensores y con las reglas fuzzy se define hacia donde va a seguir moviéndose el robot.

• Fusificador

Según Martín del Brío, B. et al (2002), "El Fusificador establece una relación entre puntos de entrada no difusos a un sistema y sus correspondientes conjuntos difusos". Esto quiere decir que cada punto de entrada del sistema no difuso tiene un valor dentro de los conjuntos difusos según las funciones de membresía.

• Fusificador Singleton

"Es el método más utilizado, principalmente en sistemas de control.", según Martín del Brío, B. et al (2002), ".consiste en considerar los propios valores discretos como conjunto difuso". Por lo tanto, cada valor discreto pertenece a un conjunto difuso donde tiene un valor 1 y los demás tienen valor 0.

• Fusificador no Singleton

Según Martín del Brío, B. et al (2002), "En el caso de los fusificadores no Singleton, se utiliza una función exponencial con forma de campana centrada en un valor x de entrada, de anchura igual a la desviación estándar y amplitud a".

• Defusificador

Según Martín del Brío, B. et al (2002), "El defusificador es la función que transforma un conjunto difuso en un valor no difuso".

• Defusificador por máximo

Definido como:

Donde y es el punto de V en que alcanza su valor máximo y se define como:

• Defusificador por media de centros

Definido como:

Donde y-l representa el centro del conjunto difuso Gl definido como el punto de V en el que alcanza su valor máximo y se define como los M conjuntos difusos Bl con l=1,2,.,M y donde cada uno de los cuales es el resultado de aplicar la entrada A" a cada una de las M reglas de la base de reglas difusas que conforman el conjunto de reglas del sistema.

• Defusificador por centro de área

Definido como:

Donde Ml es el momento en torno al eje y del universo de discurso de la salida V de la función de inclusión del conjunto difuso Gl, Al es el área y se define igualmente que en el Defusificador por media de centros.

• Sistemas Difusos

En el sistema descrito por Surmann et al (1995), utilizan 3 funciones de membresía por cada sensor, lo que hacen un total de 27 reglas difusas. El control basado en la lógica difusa implementado es de unas 180 reglas difusas con 30 entradas y 11 salidas.

Para Tsourveloudis et al (2005), ".el uso de lógica difusa es muy importante en la creación de robots autónomos, sobre todo en los sistemas de navegación para estos por su extensa aplicabilidad y la representación de nociones inherentemente imprecisas.". En el sistema propuesto por estos autores se toma en cuenta un controlador difuso de 2 capas donde la primera capa se encarga de evaluar las lecturas de los sensores e interpreta el entorno del robot y la segunda capa se encarga de controlar el movimiento del robot por medio de la información obtenida de la capa anterior, también se encarga de la posición, velocidad, rumbo, etc.

Para el modelo presentado en Tunstel (2001) se utiliza la lógica difusa, dado que para obtener una inferencia robusta por parte del sistema y razonamiento aproximado bajo la incertidumbre es mejor el uso de una colección de conductas primitivas que se codifican como reglas difusas que son gobernadas por la inferencia difusa.

En Yang et al (2006a) se propone un sistema basado en la lógica difusa que tiene como característica principal una función de membresía llamada NEAR que interpreta la cercanía de los objetos en el entorno del robot y los ángulos a los que se encuentran, luego de hacer uso de las reglas de la lógica difusa determina que tan cerca o lejos está de un obstáculo. En este proyecto se implementa una función NEAR con una estructura diferente a la expuesta en Yang et al (2006a), la diferencia radica en la cantidad de variables de entada y salida.

• Algoritmos Genéticos

En Amar et al (2000) se definen como:

Los Algoritmos Genéticos son una de las más conocidas y originales técnicas de resolución de problemas dentro de lo que se ha definido como "Computación Evolutiva" (o "Algoritmos Evolutivos"), término que agrupa a los Algoritmos Genéticos, las Estrategias Evolutivas y la Programación Evolutiva. En realidad todas estas técnicas son muy parecidas y comparten muchos aspectos. Un Algoritmo Evolutivo es una técnica de resolución de problemas inspirada en la evolución de los seres vivos.

Por lo tanto, los algoritmos genéticos son una herramienta importante al momento de resolver problemas donde se deben tener en cuenta muchas variables, las cuales se deben ir tomando en cuenta para alcanzar el nivel óptimo en cuanto al resultado que se desea obtener.

Según Wahde (2004):

Los algoritmos genéticos toman ejemplo de la naturaleza en muchos aspectos, pero en realidad son una simplificación de esta, dado que en la naturaleza no se utiliza toda la información almacenada en los cromosomas y parte de esta queda en un estado "Dormido" que se puede ver reflejado en generaciones posteriores. Además, en la naturaleza los cromosomas vienen en pares, por lo que al momento de combinarse hay cromosomas que pueden ser recesivos o dominantes, caso que no se utiliza en los algoritmos genéticos donde un cromosoma contiene la información necesaria a cerca del problema que se desea solucionar.

En efecto, la información que se utiliza para crear los genes en un algoritmo genético es la necesaria para resolver el problema, y cada vez que se hace un cruce entre 2 genes se obtiene los mejores resultados de cada característica para darle la ventaja al gen resultante sobre los otros miembros de la población. Por eso no se necesitan datos que sean recesivos, por que serían obsoletos al momento de hacer el cruce y se perdería esta información. Lo contrario sucede en la naturaleza, donde la información recesiva puede activarse en cualquier momento.

Según Haupt (2004), ".un cromosoma es un arreglo de valores variables que pueden ser optimizados.", también se toma en cuenta que: ".una función de costo toma como entrada un cromosoma y por medio de un proceso matemático o un juego modifica la entrada y la convierte en una salida deseada aproximando los valores de entrada.".

La estructura que deben tener estos algoritmos según Amar et al (2000) es la siguiente:

En un Algoritmo Evolutivo se define una estructura de datos que admita todas las posibles soluciones a un problema. Cada uno de los posibles conjuntos de datos admitidos por esa estructura será una solución al problema. Unas soluciones serán mejores, otras peores. Solucionar el problema consistirá en encontrar la solución óptima, y por tanto, los Algoritmos Evolutivos son en realidad un método de búsqueda.

Ejemplo de un algoritmo genético estándar según Haupt (2004):

• Definir la función de costo o fitness function, los costos, las variables y la estructura del cromosoma.

• Crear la población inicial.

• Decodificar cromosomas.

• Buscar costo para cada cromosoma.

• Seleccionar las parejas.

• Aparear.

• Mutar.

• Verificar convergencia, repetir desde el paso 3 hasta que se encuentre el cromosoma óptimo.

En Wahde (2004) se utiliza la siguiente estructura de algoritmo genético:

• Seleccionar la población inicial.

• Codificar de forma binaria los genes de cada individuo de la población.

• Seleccionar la función de costo.

• Proceso de selección por medio de ruleta rusa.

• Cruce de un punto (One-point Crossover), donde se selecciona de forma aleatoria un punto de cruce.

• Calcular las variables de probabilidad de cruce y de mutación.

• Utilizar elitismo, se copia la estructura del mejor individuo de cada generación y se hace una transferencia hacia la siguiente generación.

• Reemplazar la generación con la nueva.

En Haupt (2004) se estudian 4 tipos de selección:

Selección desde arriba hacia abajo, lo que se hace es comenzar en el tope de la lista e ir seleccionando en pares hasta que se hayan seleccionado los mejores para luego aparearlos, este método no se apega mucho a la naturaleza, pero es el más fácil de implementar. Selección aleatoria, en este caso se generan números aleatorios que representan las filas donde se encuentran los cromosomas a aparear. Selección aleatoria con peso, para este caso se utiliza la probabilidad asignada al cromosoma e inversamente proporcional al costo, lo que significa que mientras el costo sea mayor, menor la probabilidad de aparear ese cromosoma, para este método hay 2 formas de obtener el costo: por rango, que utiliza el rango que tiene el cromosoma dentro de la población, y por costo, que utiliza el costo del cromosoma en vez del rango. Y el método de selección por competencia, en este caso se toma un subconjunto desde la población y de estos se seleccionan los que están en mejor condición para ser apareados.

Para Wahde (2004), ". Cuando un algoritmo genético se utiliza para resolver problemas de optimización, las variables del problema se codifican en estructuras llamadas Cromosomas. Cada Cromosoma consiste de un número de elementos llamados Genes .", además ". la estructura de los Cromosomas puede cambiar de problema en problema, dependiendo del problema que se desea resolver .".

Según Haupt (2004), ". la optimización es el proceso de hacer algo mejor.". La optimización consiste en hacer variaciones a un concepto inicial y usar la información obtenida para mejorar esa idea. Los algoritmos genéticos han demostrado ser eficientes en cuanto a la optimización de problemas complejos en muchas áreas de las ciencias, en especial en las ciencias de la computación, por que permiten manejar información especifica del problema y obtener los datos óptimos con los que se pueden trabajar. También se define cruce (crossover) como: ".la combinación de genes para producir otros con rasgos (traits) combinados y seleccionar los genes con los mejores rasgos o características.", esto se hace para que los genes o individuos de una población asignados para ser padres, sean los genes que tengan los valores óptimos para que el cruce sea positivo para la generación siguiente. Pero existe otra forma de propagar valores dentro de la población, esta se llama mutación, ".una mutación ocurre cuando los cruces no producen cambios significativos en la población, por lo tanto se pueden incrementar las variables de forma elitista dentro de la población con cierta probabilidad.".

Para Wahde (2004), ". la evolución, dada su naturaleza estocástica, puede encontrar diferentes soluciones para un problema dado .". También se puede observar que para Wahde (2004): ". los usos para los algoritmos genéticos son infinitos, dada la variedad de problemas que se pueden representar en la forma de genes. Además, la cantidad de problemas de optimización es grande y muchos de estos problemas se pueden resolver de forma sencilla por medio de algoritmos genéticos .".

En Haupt (2004) se muestran los diferentes usos de los algoritmos genéticos aplicados a varias áreas de la ciencia, las optimizaciones pueden ser:

1. Optimización de Prueba y Error se refiere al proceso de ajustar las variables que afectan la salida sin conocer mucho sobre el proceso que produce esa salida.

2. Si existe únicamente una variable, la optimización es unidimensional. Un problema que tiene más de una variable, requiere una optimización multidimensional. Las optimizaciones se vuelven más difíciles a medida que se incrementa el número de dimensiones.

3. Optimización dinámica significa que la salida es una función del tiempo, mientras que la estática significa que la salida es independiente del tiempo.

4. Las variables discretas tienen un número finito de valores posibles, mientras que las continuas tienen un número infinito.

5. La optimización controlada incorpora igualdades y desigualdades variables a la función de costo. Las no controladas permiten a las variables tomar cualquier valor.

6. Algunos algoritmos tratan de optimizar el costo iniciando desde un conjunto inicial de valores variables. Estos algoritmos se concentran en los mínimos, pero por lo normal son rápidos.

En este documento se utilizan los algoritmos genéticos para optimizar el sistema basado en la lógica difusa desarrollado para describir las conductas del robot, por lo tanto el gen final debe tener todas las características del sistema con los valores óptimos para el manejo del robot.

Para el modelo propuesto en Mahmoudi et al (2004), se tiene como base los algoritmos genéticos y la planeación de ruta, la función para determinar el mejor robot se basa en 2 parámetros: El primero es el tiempo en que toma el robot en llegar al objetivo, si el robot toma mucho tiempo en llegar al objetivo obtiene más puntos y menos probabilidad de ser elegido como el mejor; el segundo parámetro es penalizar a los robots que choquen con los obstáculos que se encuentran en el entorno, cada vez que un robot choca se le agrega un valor constante a la función del robot, mientras menos valor tenga la función al final del camino mejor es el robot.

En el sistema propuesto por Chronis et al (1999) es un agente controlado por un conjunto dinámico de reglas difusas, donde el conjunto de reglas es aprendido por medio de algoritmos genéticos. Las reglas se van ajustando por medio de sesiones de entrenamiento y se prueban cuando se observa que la conducta obtenida es satisfactoria. Con este método se pueden aprender diferentes esquemas de navegación dependiendo en la conducta requerida por el robot, sin necesidad de hacer muchos cambios al sistema, sino en las funciones que se evalúan.

CAPITULO 3

Sistema propuesto

• Estructura del Robot

En este proyecto se hace una síntesis de los diferentes casos presentados anteriormente para obtener las conductas que debe tener el robot: Ir a meta, evitar obstáculo, seguir pared, visitar próximo, seguir adelante, girar y comer. Cada una tiene una función especial y está regida por varias reglas difusas que van a ser optimizadas por medio de algoritmos genéticos para desarrollar un sistema autónomo, en forma de un cromosoma, que puede ser implementado en un robot real y funcionar de acuerdo a las especificaciones del robot que se describe en la sección anterior.

El robot propuesto consta de dos motores de velocidad variable los cuales tendrán asociada una función difusa que maneja la velocidad de cada motor dependiendo de la entrada que los sensores envían a las funciones. Se propone un robot con un arreglo de seis sensores ultrasónicos situados en la parte frontal del robot, esto para simplificar el sistema donde el robot podrá girar sobre su propio eje, por lo tanto no se necesitan sensores en la parte de atrás. Las siguientes figuras muestran la posición de los motores y los sensores en el robot físico:

Cada uno de los sensores presenta datos de los obstáculos cercanos al robot, al igual que las metas y submetas, los 2 de enfrente permiten al robot detectar obstáculos en su camino, los 2 de los lados permiten la detección de obstáculos para dar vuelta hacia la izquierda o la derecha, y el resto de los sensores permiten detectar otros obstáculos que puedan interferir en el camino del robot. Cada uno de los sensores está a 30° del anterior, por lo que cada uno envía la información del ángulo al que se encuentra el obstáculo. En el caso de la navegación, los sensores deben ser infrarrojos o ultrasónicos, para el reconocimiento de las metas (los obstáculos que el robot debe buscar) se utilizan cámaras digitales.

• Estructura del Cerebro

Lo que se pretende es crear un sistema de dos capas de reglas difusas para la navegación del robot. La primera capa toma los datos de los sensores y se obtienen tres valores, éstos representan los obstáculos que hay a la izquierda, derecha y enfrente del robot. Estos valores se obtienen tomando el promedio de la entrada de los sensores. La segunda capa se encarga en sí de la navegación tomando en cuenta la salida de la primera capa, es capaz de determinar donde están los obstáculos y cual es la acción a tomar, o sea seguir adelante o evitar obstáculo.

• Estructura de las Conductas

Obstáculo enfrente: Cuando el grupo de dos sensores frontales se activa, entonces hay un obstáculo enfrente.

Obstáculo al lado derecho: Para determinar si hay un obstáculo a la derecha se toma el promedio de las distancias obtenidas del conjunto de los tres sensores en la parte derecha del robot.

Obstáculo al lado izquierdo: Al igual que la anterior, se toma el promedio de los datos de los tres sensores de la izquierda y se determina si hay un obstáculo en la parte izquierda del robot.

Para determinar si hay obstáculos a los lados o enfrente del robot, se deben leer los sensores y se determina si han detectado un objeto en el camino del robot, esto se logra con la primera capa de funciones difusas, una vez determinado donde están los obstáculos, entran en vigencia las conductas de la segunda capa, esta capa debe ser capaz de orientar al robot de forma que no haya colisión y que pueda llegar a la meta.

Seguir Adelante: En esta conducta lo que se pretende es hacer que el robot continúe hacia adelante mientras no hayan obstáculos en frente. Por lo tanto la información de la primera capa debe ser procesada antes para saber donde están los obstáculos, si no hay obstáculos enfrente, el robot debe seguir adelante.

Girar: Con esta conducta se gira el robot un delta del ángulo hacia donde el robot debe ir, esta corrección puede ser desde 0.1° hasta 180°, dependiendo de la corrección hecha por la primera capa de funciones difusas.

Ir a Meta: Esta función es una combinación de varias características. Ir a meta utiliza el Evitar obstáculo cuando sea necesario, al igual que seguir pared, visitar próximo y seguir adelante. Esta conducta se evoluciona contabilizando el tiempo que tarda el robot en llegar a la meta pasando por los puntos designados, pero como dentro de esta conducta hay otras involucradas, se deben evolucionar todas satisfactoriamente.

Evitar Obstáculo: Con esta conducta el robot puede evitar múltiples obstáculos dado que la primera capa del sistema basado en la lógica difusa le dice a la segunda capa donde están los obstáculos, una vez esta información es procesada, la segunda capa se encarga de hacer las correcciones necesarias al robot para que pueda esquivar el obstáculo o los obstáculos.

Seguir Pared: Una de las características que debe tener un robot autónomo es seguir paredes, puede ayudar en algún momento a resolver problemas donde los obstáculos son muy grandes para determinar donde está la meta, también se evoluciona con el algoritmo genético.

Visitar Próximo: Se utiliza para hacer que el robot vaya hacia el punto más cercano donde puede comer, esto es para la evolución del robot, pero sirve al momento de tener múltiples metas.

Comer: Se utiliza simplemente para el algoritmo genético con el cual se van a evolucionar los robots, el robot que más come es el más fuerte.

• Estructura de la Evolución

El algoritmo genético utilizado en este proyecto para evolucionar los individuos consta de cinco partes: Un cromosoma con la estructura interna del individuo y de las características a evolucionar, el método de selección de los individuos más aptos, la función de selección, el método para cruzar los individuos que tengan permitido cruzarse y el método para mutar los individuos de cada generación.

3.4.1. Cromosoma

El cromosoma que se debe generar tiene siete características, las mismas características mencionadas anteriormente. Estas se deben evolucionar a medida que las generaciones vayan aumentando para obtener el cromosoma con las mejores características. La función que se utiliza para seleccionar el mejor robot está relacionada con la capacidad de alimentarse, dado que para alimentarse el robot debe esquivar obstáculos estáticos y dinámicos, como son otros robots, ir a un punto especifico donde está la comida y realizar diferentes actividades que le van a dar puntos para ser seleccionado como el mejor robot. En el caso de las colisiones, el robot no obtiene puntos si se choca, pero por el contrario obtiene todos los puntos si no se choca, por lo tanto cada característica se ve de forma diferente y se evoluciona de forma diferente.

El cromosoma utilizado se puede definir como un arreglo donde están almacenadas las variables de entrada y de salida de las conductas y las reglas difusas, cada uno de los conjuntos difusos para las funciones de membresía se encuentra representado en el arreglo y puede ser evolucionado, a continuación se muestra la estructura del cromosoma:

Figura 11: Cromosoma utilizado en el algoritmo genético.

Dentro de esta misma estructura, se debe codificar de la misma manera todas las conductas del robot. Por lo tanto, el arreglo tiene una estructura de 1×66, donde cada variable tiene asignados once valores críticos de las funciones de membresía, veintisiete reglas para el movimiento autónomo y seis del sistema difuso que maneja las metas cercanas y que se evolucionan igual que los otros valores.

• Selección

En este caso se utiliza la selección por competencia, en este tipo de selección, todos los individuos se pueden cruzar de una u otra forma y compiten para ver quien es el más apto. En el caso de los dos individuos con mejor calificación, se cruzan entre sí para tratar de generar un individuo con las mejores características posibles hasta el momento.

• Función de selección

La función utilizada para obtener la calificación del individuo es la siguiente:

• 1. 40% de la calificación se obtiene si el robot recorre de forma eficiente el mapa asignado, en este caso se utiliza la formula: (distancia recorrida/iteraciones)x40.

• 2. 40% de la calificación se obtiene al visitar las metas, la formula utilizada para calcular el porcentaje es: (metas visitadas/total de metas)x40.

• 3. 20% se obtiene si no hay choques, si el robot se choca, obtiene 0% y además termina la simulación.

En este caso, un robot perfecto obtiene 100%, pero el tiempo que se tarda el algoritmo en obtener un individuo con una calificación perfecta depende de los datos iniciales que se introduzcan al sistema y de la cantidad de individuos y generaciones.

• Cruce

Para el cruce de la población, se toman los 2 individuos con la mejor calificación y se cruzan de forma que las mejores características quedan entre los individuos resultantes de este cruce, el resto de los individuos se cruzan de forma aleatoria dependiendo del porcentaje especificado por el usuario al inicio de la evolución.

3.4.5. Mutación

En este caso se utiliza un método de mutación donde los datos cambian con una distribución normal o Gaussiana. La distribución normal se utiliza para obtener un valor dentro del rango deseado de evolución, El valor actual se utiliza como media para la función normal y se utiliza una varianza especificada al inicio de la simulación.

• Estructura del Cerebro Robótico

El cerebro robótico tiene la misma estructura del cromosoma que se propone anteriormente, donde los valores que se manejan dentro de éste son los valores significativos de las funciones de membresía del sistema difuso y los valores de las reglas difusas. La estructura del cerebro se puede representar de la siguiente forma:

Variables de entrada de la función NEAR:

Variable Derecha

Figura 12: Función NEAR para la primera variable de entrada del Sistema Difuso, Derecha.

Near: [0.01971 0.04382 0.04471 0.1369]

Médium: [0.06959 0.2314 0.3705]

Far: [0.1256 0.3087 2 2]

Variable Centro

Figura 13: Función NEAR para la segunda variable de entrada del Sistema Difuso, Centro.

Near: [0.056 0.06561 0.1633 0.4771]

Médium: [0.3527 0.5882 0.7266]

Far: [0.6444 0.7446 2 2]

Variable Izquierda

Figura 14: Función NEAR para la segunda variable de entrada del Sistema Difuso, Izquierda.

Near: [0.02224 0.0485 0.1216 0.3533]

Médium: [0.2071 0.5689 0.6072]

Far: [0.4514 0.6288 2 2]

Variable de Salida de la función NEAR:

Figura 15: Función de membresía para la variable de salida del Sistema Difuso, Dirección.

Front: [0 0.5 1]

Left: [1 1.5 2]

Right: [2 2.5 3]

Back: [3 3.5 4]

En este caso se utiliza un cerebro evolucionado hasta obtener 100% de calificación, el mapa utilizado es el tres y la cantidad de iteraciones es de 200. Por medio de una heurística donde se hacen las combinaciones de los valores que pueden obtenerse de los diferentes sensores se construye la tabla de reglas difusas, ver Tabla 2 en la página 38.

Una vez construida la tabla, el cromosoma nos permite obtener todos los valores resultantes de las combinaciones de las variables de entrada y las funciones de membresía. En este caso, los valores obtenidos ya se encuentran evolucionados hasta llegar al valor máximo que se puede obtener en el mapa tres, se puede observar que la variable de salida o dirección tiene 4 valores, que se pueden ver en la gráfica anterior, y es la dirección que el robot debe tomar en caso de cumplirse una de las combinaciones de la tabla.

Por lo tanto, el diagrama del cerebro robótico se puede representar según se muestra en el anexo 4 de la página 39, un sistema difuso con tres entradas y una salida que permite al robot moverse libremente sin necesidad de la intervención humana.

CAPITULO 4

Implementación

4.1. IMPLEMENTACIÓN EN MATLAB

El software utilizado para desarrollar la simulación es Matlab. Se utiliza Matlab por que incluye varios módulos que permiten crear sistemas difusos y al mismo tiempo se puede programar y llamar estos sistemas dentro del código. El sistema difuso se genera utilizando el módulo fuzzy de Matlab de la siguiente manera:

• 1. Se define el tipo de inferencia, las entradas y las salidas.

En este caso se utiliza el tipo Mamdani para la inferencia y el sistema tiene tres variables de entrada y una de salida, las tres variables de entrada representan los datos de los sensores frontales y laterales, la salida es el ángulo de la trayectoria del robot. El método de defusificación que se utiliza es el método por centro de área, para la operación "and" se utiliza el mínimo y para el "or" se utiliza el máximo.

Figura 16: Ejemplo de Sistema Difuso en MATLAB.

2. Se definen las funciones de membresía de las variables de entrada y de salida.

Para esto se utiliza un módulo de Matlab donde se pueden especificar los diferentes tipos de funciones de membresía que trae definidas, entre ellas se encuentras: Triangulares, trapezoidales, Gauss y tipo Sigma. Los parámetros se definen manualmente, pero estos valores se van a ir evolucionando con los algoritmos genéticos hasta obtener los valores más efectivos para que el robot se pueda desenvolver de forma eficiente en el ambiente. En el caso de la salida, el ángulo de giro varía entre 0° y 180° dependiendo de las entradas de los diferentes sensores del robot.

Figura 17: Definición de la función NEAR.

3. Se definen las reglas difusas que van a regir los comportamientos o conductas del robot.

Las reglas difusas pueden definirse de una forma automática con los algoritmos genéticos, pero en este caso se definen con una heurística inicial y a medida que se va realizando la simulación el sistema va cambiando los valores de forma aleatoria para ver cual configuración cumple con el objetivo de la simulación. Se pueden observar las entradas y las salidas con los diferentes valores difusos. Los valores de entrada utilizados para la función de membresía son: Near, Medium y Far, los que significa que los valores Near son valores que se encuentran cerca del robot, Medium los que están un poco lejos del robot y los valores Far se encuentran lejos del alcance del robot.

Figura 18: Editor de Reglas Difusas de MATLAB.

4. Una vez terminado el sistema difuso, seguimos con la creación del algoritmo genético.

El algoritmo utilizado en la simulación consta de cinco pasos:

• a. Inicializar la población, este proceso se realiza de forma aleatoria, el archivo donde se encuentra el código de esta función es initpop.m, además existe la posibilidad de tomar un robot ya evolucionado y seleccionarlo para evolucionarlo nuevamente.

• b. Evaluar cada uno de los individuos, el archivo evolucionar.m se encarga de tomar todos los individuos generados en el paso anterior y evaluar cada uno, evaluate_individual.m devuelve el sistema evolucionado y la calificación del individuo, dentro de esta función se ejecuta la función simrobot.m que es la encargada de correr los individuos dentro del mapa seleccionado, pero también se encarga de mostrar la simulación.

• c. Seleccionar los mejores y cruzar los individuos según el criterio de competencia, el archivo donde se identifican los individuos aptos para ser cruzados es tournament_select.m, en este caso se seleccionan los individuos con mayor porcentaje de calificación y se cruzan, el porcentaje de individuos restante que se especifique al inicio del programa se cruzan de manera aleatoria.

• d. Mutar los individuos de acuerdo al porcentaje definido de mutaciones, se utiliza una función llamada mutate.m y dentro de ella se utiliza una función interna de Matlab llamada normrnd, genera valores aleatorios en una distribución normal y recibe como parámetros el valor que se quiere mutar y la desviación estándar.

• e. Se repite hasta que se llegue a la condición de finalización, o sea que se llegue a la última generación.

Se pueden cambiar varios aspectos de la simulación como son: Porcentaje de cruce, porcentaje de mutación, porcentaje de población que participa en el torneo, la cantidad de individuos que se desean tener por cada generación o población y la cantidad de generaciones que se desean analizar. También se puede cambiar la cantidad de iteraciones de la simulación, esto con el fin de analizar entornos más complejos o para prolongar el proceso de evolución. A medida que se aumenten las iteraciones, más tiempo tardará la evolución, pero mayor es la probabilidad de obtener robots mejores, dado que a mayor tiempo de evolución, mayor es la probabilidad de hacer más movimientos y visit

En el programa de simulación se pueden distinguir dos procesos: Evolución del robot y Simulación del mismo. En la evolución del robot se utilizan los datos de la pantalla principal para aplicarlos al algoritmo genético, una vez terminada la evolución, se muestra la gráfica y se obtiene la calificación máxima y los datos del robot.

Una vez terminada la evolución de los datos, se pueden simular los resultados, también se puede aumentar la cantidad de iteraciones para correr la simulación por más tiempo. Del mismo modo se puede cambiar el escenario para probar la simulación en diferentes ambientes y ver como se desenvuelve el robot, aunque el robot sea únicamente evolucionado para correr en un ambiente en específico, pero puede suceder que un robot se desenvuelva de manera eficiente en ambientes diferentes.

Figura 19: Pantalla principal del Simulador.

Figura 20: Simulación en diferentes ambientes.

4.2. IMPLEMENTACIÓN EN EL ROBOT FÍSICO

Este proyecto se realizó con el objetivo de crear un cerebro robótico para ser implementado en un robot físico. Aunque no sea uno de los objetivos implementar el cerebro en el robot, se presentan dos formas de migrar. Se utilizó MATLAB por que es una herramienta que permite de forma fácil y rápida la migración de código hacia otros lenguajes como C++ y Java, al igual que existen varios módulos implementados en muchos lenguajes que permiten trabajar con sistemas difusos y algoritmos genéticos.

El primero de los métodos que se sugiere es traducir el código del simulador directamente a C++ o Java para correrlo dentro del sistema operativo que se utilice para manejar los dispositivos del robot. Una vez hecho esto, se traducen los movimientos del robot real hacia los movimientos dentro del simulador. De esta forma, cuando el simulador haga un movimiento, el robot se debe mover del mismo modo. Para finalizar, los cerebros generados por el programa que resulta de esta investigación, se podrán correr directamente ya que tienen la misma estructura que necesita el simulador.

El segundo método consiste en conseguir librerías de lógica difusa, ya sean de C++, Java u otro lenguaje, con las cuales se puedan implementar los cerebros evolucionados ya que su estructura representa las entradas y las salidas del sistema difuso. En este caso también se puede implementar el algoritmo genético y hacer que a medida que el robot vaya caminando, se vaya evolucionando.

Resultados

En esta sección, se presentan dos escenarios para navegación de robots. En el primer escenario no hay obstáculos en el ambiente, esto se hace para probar la conducta del robot de ir a meta. En el caso de no haber obstáculos en el camino del robot, este recorre el ambiente en el que se encuentra buscando las metas que se más cercanas a él, una vez que todas se han encontrado el robot obtiene todos los puntos y por lo tanto se convierte en el mejor adaptado para ir a todos los puntos designados. Se muestran dos gráficas, la primera muestra el mejor robot en una población de 10 individuos en 10 generaciones, el mejor obtuvo una calificación de 94%, en el segundo caso, el mejor robot obtuvo la misma calificación, pero se puede ver que la población se manipula durante 100 generaciones, en este caso el mejor robot se obtiene en la generación 20, es posible que mientras más generaciones haya es posible que tarde más tiempo en obtenerse el mejor individuo.

En el segundo escenario se considera un ambiente con varios obstáculos para observar como se comporta el robot. En este caso, el mejor individuo obtuvo 100% en la generación 55, por lo que se puede decir que a medida que aumenta el número de generaciones se puede llegar a un mejor resultado que el valor obtenido en una simulación con menor número.

–

Figura 21: Evoluciones de robots en ambientes sin obstáculos.

–

Figura 22: Evoluciones de Robots en ambientes con obstáculos.

En la primera evolución se utiliza el mapa número 3, que es uno de los más simples, se utiliza un porcentaje de cruce de 0.8, lo que significa que un 80% de la población tiene la oportunidad de ser cruzado. El porcentaje de mutación es de 0.3, o sea que el 30% de la población es afectada por las mutaciones aleatorias. Como se había explicado antes, el proceso de mutación utiliza una varianza que puede ser de 0.01 a 0.1. El porcentaje de torneo es de 0.75, lo que significa que el 75% de la población se selecciona para ser cruzado. La población es de 10 individuos y el número de generaciones es de 10. La cantidad de movimientos o iteraciones es de 200, lo que significa que para obtener una mejor calificación el robot debe recorrer la mayor parte de su entorno con el número de iteraciones dado. En este caso se obtuvo un 80% de calificación final para el cerebro.

En el segundo caso, se utilizan los mismos parámetros que en el caso anterior, únicamente se cambian el número de generaciones, en este caso 100, y el mapa. En este caso se obtuvo una calificación final de 94%, se puede observar que con un número mayor de generaciones es posible obtener un mejor resultado. Para mayor información referente a las pruebas que se hicieron, ver tabla 1 página 38.

Conclusiones

Se creó un sistema capaz de generar cerebros robóticos para diferentes ambientes que pueden o no tener obstáculos y metas que permitan simular ambientes reales donde se desea que el robot se desenvuelva.

Como se ha dicho en este documento, las conductas en los sistemas autónomos son de gran complejidad por que dependen de las propiedades de los ambientes a los que se enfrentan dichos sistemas. En el caso de los robots, mientras más complejo o mientras más obstáculos y metas tenga el ambiente, es más difícil elegir entre las diferentes conductas que se pueden ir descubriendo, por lo tanto se hace más difícil la evolución del robot. Por otro lado, mientras más tiempo pase un robot dentro de un ambiente, es más probable que desarrolle mejor sus conductas y por lo tanto va a tener mejor desempeño.

Tomando en cuenta los dos casos presentados en este documento donde un robot se evolucionó en un entorno simple, sin obstáculos, donde únicamente debía seguir las metas hasta recorrerlas todas y el otro caso donde habían varios obstáculos que le impedían en cierta forma interactuar fácilmente con el entorno, se puede observar que en el ambiente simple puede tomar menos tiempo en conseguirse un individuo que tenga una calificación perfecta, al contrario del otro tipo de ambiente.

Por el otro lado, la evolución del robot se consigue por medio de un algoritmo genético con ciertas características descritas en secciones anteriores de este documento. Se puede observar que mientras mayor es el número de individuos de la población es posible obtener resultados de forma más rápida que cuando no se tienen muchos individuos. Por el contrario, si se toma una población con pocos individuos y se analizan los datos durante un rango grande de generaciones, es posible que al final no se obtenga un individuo que sea el más apto.

Discusión

En este proyecto se utilizó la lógica difusa para desarrollar un sistema autónomo con diferentes características y ser implementado en un robot real. Éste debe desempeñarse de forma eficiente en un ambiente desconocido. A su vez se utilizó un algoritmo genético para buscar los mejores resultados para cada uno de los escenarios propuestos. Como se había dicho antes, la lógica difusa se utiliza en muchos de los sistemas autónomos en proyectos realizados por otros investigadores, es el caso de Saffiotti (1995), Surmann et al (1995), Chronis et al (1999), Mahmoudi et al (2004), Tsourveloudis et al (2005) y Yang et al (2006a y b). Pero en cada uno de ellos se ven diferentes enfoques de evolución, en el modelo de Saffiotti (1995) se utilizan mapas de reconocimiento, sin ningún método de evolución, dado que los mapas se generan desde el principio y el robot se guía por medio de ellos. En el modelo de Surmann et al (1995) se utilizan variables de estado difuso donde se van guardando las conductas que cambian el comportamiento del robot. En Chronis et al (1999) se describe un sistema muy parecido al presentado en este proyecto, un sistema difuso evolucionado por algoritmos genéticos, pero difiere en las variables lingüísticas de entrada y salida, y la estructura del cromosoma. En el enfoque de Mahmoudi et al (2004) se puede observar que utilizan los algoritmos genéticos para la planeación de la ruta de movimiento y evitar los obstáculos. En el caso de Tsourveloudis et al (2005) se utiliza un sistema de dos capas de lógica difusa donde cada capa actúa independientemente, pero ambas ayudan a decidir cual es la conducta que el robot debe utilizar en un momento dado. En Yang et al (2006a) se utilizan mapas de reconocimiento, al igual que en Saffiotti (1995), la diferencia es que Yang et al (2006a) utilizan una función NEAR para asegurar que el robot no choque con los obstáculos, y por último en Yang et al (2006b) se estudian dos problemas de los sistemas difusos y proponen soluciones para ambos problemas, pero siempre utilizando la lógica difusa como método principal para manejar las conductas.

Por lo tanto, la estructura utilizada en este proyecto es un sistema difuso con tres variables de entrada, que son los valores obtenidos por los sensores de las tres direcciones: Frente, Izquierda y Derecha. Luego se obtiene la salida a través del proceso de fusificación donde se obtiene el ángulo de dirección del robot. Estos valores se evolucionan por medio del algoritmo genético, al igual que las funciones de membresía y los valores de las reglas difusas.

En muchos casos, los robots evolucionados presentan problemas de movimiento. La razón de esto es que el sistema difuso desarrollado para el proyecto es muy simple y no cuenta con un árbitro para administrar las conductas. Pero puede ocurrir que al obtener un individuo cuya evolución no sea la adecuada para el ambiente se obtenga el mismo resultado. También se puede observar que hay casos donde el individuo no visita ninguna meta, pero aún así obtiene una calificación alta, esto se da por la forma como se calcula el grado de aptitud, es posible que mejorando la forma de calificación o la función de aptitud se mejore el proceso de selección de los individuos.

Trabajos futuros

Sobre este mismo tema, se pueden destacar varios trabajos relacionados:

• Implementar los diferentes cerebros robóticos evolucionados por el sistema propuesto en robots reales.

• Navegación de robots utilizando Lógica Difusa y Redes Neuronales con mapas de Cohoren.

• Aprendizaje automático de reglas difusas por medio de Algoritmos Genéticos.

• Aplicar algoritmos de aprendizaje Fuzzy-Q para robots.

• Navegación de robots por medio de reconocimiento de imágenes capturadas por cámaras digitales.

Anexos

• 1. Tabla de evoluciones.

2. Tabla de Reglas Difusas.

3. Mapas para evolucionar los robots.

4. Diagrama del cerebro robótico.

Variables de Entrada

Referencias bibliográficas

• 1. Aboshosha, A. (2003), An Introduction to Robot Distributed Sensors Part I. Dept. of Computer Science, University of Tübingen. Alemania.

• 2. Amar, E. y Berlandez, I. (2000). Cátedra sobre Algoritmos Genéticos. Consultado en Octubre, 2006 en: http://www.frro.utn.edu.ar/isi/algoritmosgeneticos/html_data/3intro.

• 3. Chronis, G., Keller, J. y Skubic, M. (1999), Learning Fuzzy Rules by Evolution for Mobile Agent Control. Dept. of Computer Engineering and Computer Science, University of Missouri, Columbia, U.S.A.

• 4. Haupt, R. y Haupt, S. (2004), Practical Genetic Algorithms: Second Edition. U.S.A: John Wiley & sons, inc.

• 5. Hellman, M. (2001), Fuzzy Logic Introduction.

• 6. Jantzen, J. (1998), Tutorial On Fuzzy Logic. Department of Automation, Technical University of Denmark, Lyngby, Dinamarca.

• 7. Mahmoudi, S., Bitanhsir, A., Forouzandeh, B. y Marandi A. (2004), A new genetic method for mobile robot navigation. Electrical and Computer Engineering Dep. University of Tehran, Iran.

• 8. Martín del Brío, B., Sans Molina, A. (2002), Redes Neuronales y Sistemas Difusos 2da edición. Mexico. Alfaomega.

• 9. Matlab 7 (2004), Copyright 1984-2004, The mathworks, inc.

• 10. Mitchell, T. (1997), Machine Learning. McGraw-Hill Science/Engineering/Math.

• 11. Na, Y. y Ho, S. (2003), Hybrid Control for Autonomous Mobile Robot Navigation Using Neural Network Based Behavior Modules and Environment Classification. Department of Electrical Engineering, Pohang University of Science and Technology. Pohang, South Korea.

• 12. Nolfi, S. (2005), Behaviour as a Complex Adaptive System: On the role of Self-Organization in the Development of Individual and Collective Behaviour. Institute of Cognitive Sciences and Technologies, Roma, Italia.

• 13. Saffiotti, A. (1995), Fuzzy Logic in Autonomus Robot Navigation. Universidad de Bruselas, Bruselas, Bélgica.

• 14. Surmann, H., Huser, J. y Peters, L. (1995), A Fuzzy System for Indoor Mobile Robot Navigation. German National Research Center for Computer Science, St. Augustin, Alemania.

• 15. Tsourveloudis, N. C., Doitsidis, L., y Valavanis, K. P. (2005), Autonomous Navigation of Unmanned Vehicles: A Fuzzy Logic Perspective.

• 16. Tunstel, E. (2001), Ethology as an Inspiration for Adaptive Behavior Synthesis in Autonomous Planetary Rovers. Robotic Vehicles Group, Jet Propulsion Laboratory, Pasadena, CA. U.S.A.

• 17. Wahde, M. (2004), Biological Basis for Evolutionary Algorithms. Course in Artifitial Intelligence: Biological Methods.

• 18. Yang, X., Patel, R. V., y Moallem, M. (2006a), A Fuzzy–Braitenberg Navigation Strategy for Differential Drive Mobile Robots. Department of Electrical & Computer Engineering, University of Western Ontario, London, ON, Canadá.

• 19. Yang, X., Patel, R. V., y Moallem, M. (2006b). A Sensor Based Navigation Algorithm for a Mobile Robot Using Fuzzy Logic. International Journal of Robotics and Automation, Vol. 21, No. 2.

A Dios por darme la vida y permitirme terminar esta fase de mi vida.

A mis padres, Guillermo y Cecilia por su amor y su apoyo incondicional.

Y a mi esposa Elena por su amor y por permanecer a mi lado en cada paso que he dado.

AGRADECIMIENTOS

El autor expresa sus agradecimientos a:

• Ingeniero Jorge García, Asesor del presente trabajo, por su apoyo durante la realización de este proyecto y por todas sus enseñanzas.

• A los maestros de UNITEC, por enseñarme todo lo que sé.

Autor:

David Botero Rojas

Asesor: Jorge García Bolaños

UNIVERSIDAD TECNOLÓGICA CENTROAMERICANA

CAMPUS SAN PEDRO SULA

INGENIERÍA EN SISTEMAS COMPUTACIONALES

SAN PEDRO SULA

2007