PDF de programación - Navegación robótica basada en aprendizaje evolutivo de acciones mediante lógica difusa

Universidad Técnica Federico Santa María

Departamento de Electrónica

Navegación robótica basada

en aprendizaje evolutivo

de acciones

mediante lógica difusa

Memoria presentada por : Fernando Ernesto Quirós Retamales

Ingeniero Civil Electrónico, mención Computadores y Control Automático

Como requisito parcial para optar al título de :

Profesor Guía : Tomás Arredondo Vidal

Profesor Correferente : Wolfgang Freund Grunewaldt

Valparaíso, 20 de octubre de 2006

Dedicado a mis padres

2

Índice general

1. Introducción

8

2. Marco teórico

10
2.1. Sensores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2. Redes neuronales artificiales . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1. Neuronas reales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2. Neuronas artificiales
. . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3. Redes neuronales artificiales . . . . . . . . . . . . . . . . . . . . . . 14
2.2.4. Requerimientos del robot . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3. Algoritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1. Evolución natural y algoritmos evolutivos . . . . . . . . . . . . . . . 17
2.3.2. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.3. Procedimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.4. Requerimientos del robot . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4. Lógica difusa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1.
Introducción a la lógica difusa . . . . . . . . . . . . . . . . . . . . . 25
2.4.2. Conceptos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.3. Control difuso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.4. Método Takagi-Sugeno . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.5. Requerimientos del robot . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5. Redes neuronales SOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5.1. Estructura de una red SOM . . . . . . . . . . . . . . . . . . . . . . 32
2.5.2. Entrenamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5.3. Funcionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.4. Requerimientos del robot . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6. Action based environmental modeling . . . . . . . . . . . . . . . . . . . . . 35
2.6.1. Funcionamiento de AEM . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6.2. Bloque AEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6.3. Requerimientos del robot . . . . . . . . . . . . . . . . . . . . . . . . 36
2.7. Chain coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3. Desarrollo

38
3.1. Procesos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
. . . . . . . . . . . . . . . . . . . . . . . . . 39

3.1.1. Red neuronal artificial

3

3.2. Datos

3.1.2. Algoritmo genético . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.3. Fitness difuso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.4. Bloque AEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.5. Driver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.6. Simulador de entornos
. . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.7. Chain coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.8. Reconocimiento de entornos mediante la red SOM . . . . . . . . . . 42
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.1. Peso 1, peso n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.2. Mapa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.3. Action sequence, environment vector
. . . . . . . . . . . . . . . . . 44
3.2.4. Homing, area, carga batería, entorno . . . . . . . . . . . . . . . . . 44
3.3. Salidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.1. Motores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4. Arquitectura de comportamientos . . . . . . . . . . . . . . . . . . . . . . . 45
3.5. Simulaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.6. Criterios para realizar las pruebas . . . . . . . . . . . . . . . . . . . . . . . 47
3.7. Entrenamiento del robot . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.8. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4. Conclusiones

54

5. Mejoras al comportamiento del robot

56
5.1. Mejorar el mapa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.2. Realizar el reconocimiento de entornos a partir del mapa . . . . . . . . . . 57
5.3. Reconocimiento de entornos en tiempo real . . . . . . . . . . . . . . . . . . 57
5.4. Más comportamientos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.5. Utilizar una red neuronal dinámica . . . . . . . . . . . . . . . . . . . . . . 58

6. Apéndice

61
6.1. SomPak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.1.
Instalación del programa . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.2. Comandos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2. Simulador YAKS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2.1. Requerimientos para compilar el programa . . . . . . . . . . . . . . 63
6.2.2. Makefile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2.3. Archivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.3. Configuración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.3.1. Opciones generales . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.3.2. Forma de hacer evolucionar la población . . . . . . . . . . . . . . . 69
6.3.3. Forma de correr una simulación gráfica, con una red neuronal ya

entrenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4

Índice de figuras

2.1. Foto del Robot Khepera. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2. Disposición física de los sensores.
. . . . . . . . . . . . . . . . . . . . . . . 11
2.3. Neurona biológica.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4. Conexión sináptica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5. Neurona artificial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6. Red neuronal artificial.
2.7. Estructura de un cromosoma.
. . . . . . . . . . . . . . . . . . . . . . . . . 18
2.8. Distribución de población inicial.
. . . . . . . . . . . . . . . . . . . . . . . 19
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.9. Función objetivo.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.10. Población inicial.
2.11. Selección mediante probabilidades.
. . . . . . . . . . . . . . . . . . . . . . 22
2.12. Gráfico de probabilidades tipo torta.
. . . . . . . . . . . . . . . . . . . . . 22
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.13. Ejemplo cruce n-puntos.
2.14. Ejemplo cruce uniforme.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.15. Ejemplo de mutación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.16. Algunas funciones de pertenencia. . . . . . . . . . . . . . . . . . . . . . . . 26
2.17. Mecanismo de inferencia aproximada. . . . . . . . . . . . . . . . . . . . . . 28
2.18. Ejemplo de control difuso.
. . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.19. Estructura de una red SOM. . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.20. Ejemplo del funcionamiento de una red SOM.
. . . . . . . . . . . . . . . . 34
2.21. Mapeo realizado por AEM. . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.22. Bloque AEM.
2.23. Ejemplo de vector de secuencia de acciones AS.
. . . . . . . . . . . . . . . 37

3.1. Arquitectura del sistema que estructura la inteligencia del robot . . . . . . 38
3.2. Estructura de la red neuronal del robot.
. . . . . . . . . . . . . . . . . . . 39
3.3. Entrenamiento de la red neuronal. . . . . . . . . . . . . . . . . . . . . . . . 40
3.4. Entrenamiento de la red SOM. . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5. Ejemplo de un mapa y su matriz asociada.
. . . . . . . . . . . . . . . . . . 44
3.6. Diagrama de comportamientos del robot. . . . . . . . . . . . . . . . . . . . 45
3.7. Entornos utilizados en los experimentos.
. . . . . . . . . . . . . . . . . . . 47
3.8. Screenshots para set de motivaciones 1, piezas 1 a 6 . . . . . . . . . . . . . 50
3.9. Screenshots para set de motivaciones 2, piezas 1 a 6 . . . . . . . . . . . . . 51
3.10. Screenshots para set de motivaciones 3, piezas 1 a 6 . . . . . . . . . . . . . 52

5

5.1. Red neuronal dinámica.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6

Índice de tablas

3.1. Parámetros del algoritmo genético y redes neuronales. . . . . . . . . . . . . 48
3.2. Estadísticas para el set de motivaciones 1 . . . . . . . . . . . . . . . . . . . 53
3.3. Estadísticas para el set de motivaciones 2 . . . . . . . . . . . . . . . . . . . 53
3.4. Estadísticas para el set de motivaciones 3 . . . . . . . . . . . . . . . . . . . 53
3.5. Estadísticas para el set de motivaciones 4 . . . . . . . . . . . . . . . . . . . 53

4.1. Promedios de las tablas de resultados . . . . . . . . . . . . . . . . . . . . . 54

7

Capítulo 1

Introducción

Hoy en día la robótica móvil es un tema en continuo desarrollo. Con el enorme poder
de cómputo que existe en la actualidad se puede dar cada vez más inteligencia a robots
móvi