PDF de programación - Robots capaces de aprender y adaptarse al entorno a partir de sus propias experiencias

Robots capaces de aprender y

adaptarse al entorno a partir de sus

propias experiencias

Pablo Quintía Vidal

DEPARTAMENTO DE ELECTRÓNICA E COMPUTACIÓN

UNIVERSIDADE DE SANTIAGO DE COMPOSTELA

UNIVERSIDADE DE SANTIAGO DE COMPOSTELA

Departamento de Electrónica e Computación

Tesis doctoral

ROBOTS CAPACES DE APRENDER Y ADAPTARSE AL
ENTORNO A PARTIR DE SUS PROPIAS EXPERIENCIAS

Presentada por:

Pablo Quintía Vidal

Dirigida por:

Roberto Iglesias Rodríguez
Carlos Vázquez Regueiro

Mayo 2013

Roberto Iglesias Rodríguez, Profesor Titular de Universidad del Área de Ciencia de la Computación
e Inteligencia Artificial de la Universidade de Santiago de Compostela e investigador adscrito
al Centro Singular de Investigación en Tecnoloxías da Información (CITIUS)

Carlos Vázquez Regueiro, Profesor Titular de Universidad del Área de Arquitectura y Tecnología de

Computadores de la Universidade da Coruña

HACEN CONSTAR:

Que la memoria titulada ROBOTS CAPACES DE APRENDER Y ADAPTARSE AL ENTORNO A
PARTIR DE SUS PROPIAS EXPERIENCIAS ha sido realizada por D. Pablo Quintía Vidal bajo
nuestra dirección en el Departamento de Electrónica e Computación de la Universidade de Santiago de
Compostela, y constituye la Tesis que presenta para optar al título de Doctor.

Mayo 2013

Roberto Iglesias Rodríguez

Carlos Vázquez Regueiro

Pablo Quintía Vidal

Director de la tesis

Director de la tesis

Autor de la tesis

Agradecimentos

Esta tesis es el resultado del trabajo de muchas personas, a las cuales quiero agradecer su

ayuda y apoyo durante todo este tiempo:

En primer lugar a mis directores de tesis, Roberto Iglesias Rodríguez y Carlos Vázquez

Regueiro, por su ayuda, sus consejos y la confianza que depositaron en mí.

A Miguel Rodríguez por su inestimable ayuda y al que considero como un codirector más
de la tesis. También a Theocharis Kyriacou por la colaboración prestada y a Eva Cernadas por
sus consejos.

Al Departamento de Electrónica e Computación y al CITIUS de la Universidade de San-
tiago de Compostela, por proporcionar los recursos necesarios para la realización de esta tesis.
Al Departamento de Electrónica e Sistemas de la Universidade da Coruña, por darme la
oportunidad de iniciarme como docente y por todo el apoyo y ayuda que me ha proporcionado.
A todos los precarios de Coruña y Santiago con los que compartí las incertidumbres de un

estudiante de doctorado y gracias a los que los días en el laboratorio eran más agradables.

A la Xunta de Galicia, por proporcionar mediante su programa de becas predoctorales la

financiación con la que pude dedicarme a tiempo completo a este trabajo.

En el último y más importante lugar, gracias a mis padres, familia y amigos, por hacer-
me olvidar todo en los ratos libres (excepto cuando preguntaban ¿pero aún no acabaste?).
Especialmente a Carolina, por apoyarme todo este tiempo y el que queda.

Mayo 2013

Índice general

Introducción

.

.

.
.

.
.

.
.

.
.

.
.

.
.

1 Contexto y motivación
1.1. Tipos de robots .
.
1.2. Robótica de servicio .
1.3. Autonomía en los robots de servicio personal
1.4. Estrategias de aprendizaje .

. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
1.4.1. Aprendizaje por demostración . . . . . . . . . . . . . . . . . . . . .
1.4.2. Aprendizaje a partir de la experiencia . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .

1.5. Discusión .

.
.

.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2 Aprendizaje por refuerzo en robótica
.

.

.

.

.

.

.

.

.

.

.

.

.

2.1. Antecedentes
. . . . . . . . . . . . . . . . . . . . .
2.2. El problema de aprendizaje por refuerzo . . . . . . . . . . . . . . . . . . . .
2.2.1. Procesos de Decisión de Markov . . . . . . . . . . . . . . . . . . . .
2.2.2. Procesos de Decisión de Markov Parcialmente Observables
. . . . .
. . . . . . . . . . . . . . . . . . . . .
2.2.3. Política de control
.
2.2.4. Funciones de valor .
. . . . . . . . . . . . . . . . . . . . .
2.3. Algoritmos de aprendizaje por refuerzo . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
2.4. Continuidad del espacio de estados y acciones . . . . . . . . . . . . . . . . .
2.5. Otros algoritmos de aprendizaje por refuerzo . . . . . . . . . . . . . . . . .

2.3.1. Programación dinámica
.
2.3.2. Métodos de Monte Carlo .
2.3.3. Diferencias temporales .
.

.
.
.

.
.
.

.
.

.
.

.
.

.
.

.
.

1

7
7
12
13
20
21
25
26

29
29
31
32
33
34
35
37
38
41
42
48
49

VIII

Índice general

. . . . . . . . . . . . . . . . . . . . .
2.5.1. Algoritmos con exploración .
2.5.2. Algoritmos basados en mínimos cuadrados
. . . . . . . . . . . . . .
2.5.3. Algoritmos sobre espacios continuos . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .

2.6. Formulación del refuerzo .
.
2.7. Discusión .

.
.

.
.

.
.

.
.

.
.

.
.

.

.

.

.

.

.

.

3 Algoritmo I_Tbf

.

.

.

.

.

.

.

.

.
.
.

. . .

3.1. Prediciendo el tiempo antes del fallo .
3.2. Algoritmo I_Tbf
.
.
.
3.3. Dilema exploración-explotación .
3.4. Espacio de estados
.
.

. . . . . . . . . . . . . . . . . . . . .
. . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
3.4.1. Reducción dinámica del número de estados . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .

3.5. Aplicación experimental
3.5.1. Seguir pared .
3.5.2. Cruzar puerta .
.

3.6. Discusión .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.

.

.

.

.

.

.

.

.

.

.

.

.

49
51
54
57
60

65
66
69
70
72
73
75
76
80
83

4 Representación dinámica del entorno

.

.

.

.

.

.

.

.

.

. . .

. . .

4.1.1. Fuzzy ART .
4.1.2. Adaptación de Fuzzy ART para el aprendizaje en el robot real

85
86
4.1. Teoría de la resonancia adaptativa (ART) . . . . . . . . . . . . . . . . . . . .
88
. . . . . . . . . . . . . . .
91
. . . .
92
4.2. Aprendizaje simultáneo de percepción y acción . . . . . . . . . . . . . . . .
93
. . . . . . . . . . . . . .
94
Inserción dinámica de neuronas vinculada al aprendizaje . . . . . . .
96
. . . . . . . . . . . . . . . . . . . . .
4.3. Aplicación experimental
. . . . . . . . . . . . . . . . . . . . .
98
4.3.1. Seguir pared .
4.3.2. Cruzar puerta .
. . . . . . . . . . . . . . . . . . . . . 102
4.3.3. Modificación del espacio de estados vinculado al aprendizaje . . . . . 105
. . . . . . . . . . . . . . . . . . . . . 107

4.2.1. Red Fuzzy ART de vigilancia variable . . .
4.2.2.

4.4. Discusión .

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

5 Aprendizaje mediante comités
.
.

5.1. Dilema bias-varianza .
.
5.2. Creación de comités .
.
.
5.3. Comités de evaluadores de acción .

.
.

.
.

.
.

.
.

.
.

. . .

109
. . . . . . . . . . . . . . . . 110
. .
. . . . . . . . . . . . . . . . . . . . . 112
. .
. . . . . . . . . 114

. . . . . . .

. . .

.
.
.

Índice general

IX

.

.
5.4. Comité de evaluadores de políticas .

. . . . . . . . . . . . . . . . 116
5.3.1. Función de utilidad de cada aprendedor
5.3.2. Construcción de los intervalos de acciones
. . . . . . . . . . . . . . 118
5.3.3. Actualización de las funciones de valoración . . . . . . . . . . . . . 119
5.3.4. Aplicación experimental
. . . . . . . . . . . . . . . . . . . . . 121
. . . . . 124
. . .
. . . . . . . . . . . . . . . . . . . . 125
5.4.1. Actualización de los Q-valores .
Incorporando nuevo conocimiento . . . . . . . . . . . . . . . . . . . 127
5.4.2.
. . 129
5.4.3. Aprendizaje interactivo. Proporcionando realimentación al robot.
5.4.4. Aplicación experimental
. . . . . . . . . . . . . . . . . . . . . 133
5.4.5. Aprendizaje con usuarios no expertos . . . . . . . . . . . . . . . . . 135
. . . . . . . . . . . . . . . . . . . . . 140

5.5. Discusión .

. . . . .

. . . . .

. . .

.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

6 Selección de sensores significativos
.

6.1. Trabajo relacionado .
6.2.

143
. . . . . . . . . . . . . . . . . . . . . 144
Información mutua como medida de relevancia . . . . . . . . . . . . . . . . 147
6.2.1. Obteniendo los sensores más relevantes . . . . . . . . . . . . . . . . 148
6.2.2. Discretización en intervalos de las entradas sensoriales . . . . . . . . 149
6.2.3. Resultados experimentales .
. . . . . . . . . . . . . . . . . . . . 152
6.3. Selección de los sensores más relevantes y menos redundantes . . . . . . . . 156
6.3.1. Ordenando los sensores por mayor relevancia y menor redundancia . 157
6.3.2. Seleccionando el número de sensores significativos . . . . . . . . . . 158
. . . . . . . . . . . . . . . . . . . . . 159
6.4.1. Selección de los sensores para los procesos de aprendizaje . . . . . . 161
6.4.2. Aplicando los sensores más significativos al aprendizaje . . . . . . . 166
6.4.3. Generalización de lo aprendido . . . . . . . . . . . . . . . . . . . . 169
. . . . . . . . . . . . . . . . . . . . . 172

6.4. Resultados experimentales .

6.5. Discusión .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7 Conclusiones

7.1. Trabajo futuro .

.

.

.

.

.

.

.

.

.

.

.

.

175
. . . . . . . . . . . . . . . . . . . . . 179

Bibliografía

Índice de figuras

Índice de tablas

185

199

203

X

Índice de algoritmos

Índice general

205

Introducción

Objetivo de la tesis

Los intentos de dotar a los robots móviles con conocimiento y la capacidad de realizar
tareas de forma autónoma se vienen haciendo desde prácticamente el principio de la robótica
[35]. Inicialmente se asumía que se poseía suficiente información sobre el robot, la tarea y
el entorno, pero dicha asunción se demos