introducción a la navegación de robots en ambientes inteligentes
DESCRIPTION
ResumenTRANSCRIPT
Programa de Doctorado de Informática Industrial Departamento de Arquitectura y Tecnología de Computadores – Universidad de Sevilla
Trabajo de investigación
Curso 2010 / 2011
Introducción a la Navegación de Robots en
Entornos Inteligentes
Realizado por
Pablo Íñigo Blasco - Junio de 2011
Tutores
Fernando Díaz del Río y Saturnino Vicente Díaz
2
3
Resumen
Palabras Clave
Navegación de Robots, MultiSensor Data Fussion, Localización, Planificación de
Movimiento, Evitación de Obstáculos.
Este trabajo se centra en el estudio de los principios fundamentales de la navegación de robots móviles con ruedas (WMRs) en entornos inteligentes. Se abordan de manera transversal distintas áreas directamente implicadas en el problema: la localización, los modelos de movimiento, la percepción, la planificación de movimiento, la evitación de obstáculos y las arquitecturas distribuidas para sistemas robóticos. Diversas técnicas reconocidas son expuestas en cada una de estas áreas. Este trabajo define la base para el desarrollo de futuras investigaciones en el ámbito navegación de WMRs en entornos inteligentes.
4
5
I. CONTENIDO
I. Contenido ....................................................................................................................................................... 5
CAPÍTULO 1 Introducción ............................................................................................................................. 11
1.1. Motivación .......................................................................................................................................... 11
1.2. Contexto .............................................................................................................................................. 11
1.3. Objetivos ............................................................................................................................................. 12
1.4. Metodología ....................................................................................................................................... 12
1.5. Estructura del trabajo .................................................................................................................... 14
CAPÍTULO 2 Navegación de WMRs No-holónomos ........................................................................... 17
2.1. Introducción ...................................................................................................................................... 17
2.2. Historia ................................................................................................................................................ 17
2.3. Conceptos fundamentales en la Navegación de WMRs ................................................... 20
2.3.1. WMRs no-holónomos ........................................................................................................... 20
2.3.2. Cinemática ................................................................................................................................ 20
2.3.3. Dinámica .................................................................................................................................... 21
2.3.4. Espacio de Trabajo ( ) ...................................................................................................... 22
2.3.5. Espacio de Configuración ( ) ........................................................................................... 22
2.3.6. Espacio de Estados ( ) ....................................................................................................... 24
2.3.7. El Espacio de Acción ( ) .................................................................................................... 25
2.3.8. Evolucion Dinámica del sistema ...................................................................................... 26
2.4. Herramientas para gestionar mundos con obstáculos .................................................... 27
2.4.1. Función Clearance ................................................................................................................. 27
2.4.2. Chequeador de Colisiones (Collision Chequer) ......................................................... 28
2.4.3. El Planificador Local ............................................................................................................. 28
2.5. Complejidad, optimalidad y completitud .............................................................................. 30
CAPÍTULO 3 Modelos de movimiento en WMRs no-holónomos ................................................... 33
3.1. Introducción ...................................................................................................................................... 33
3.2. Robots Móviles con Ruedas (WMRs)....................................................................................... 33
3.3. Modelo Cinemático en WMRs No-holónomos ..................................................................... 35
6
3.3.1. Centro Instantáneo de rotación (ICR) ........................................................................... 35
3.3.2. Ecuaciones de movimiento ................................................................................................ 36
3.3.3. Modelo cinemático discreto .............................................................................................. 37
3.3.4. Modelo de movimiento Odométrico .............................................................................. 37
3.3.5. Aplicación del modelo .......................................................................................................... 39
3.4. Modelos de Movimiento Probabilísticos ................................................................................ 40
3.4.1. Modelo de Movimiento con Incertidumbre en la Configuración ....................... 42
3.4.2. Modelo de Movimiento con Incertidumbre en la Velocidad ................................ 43
3.4.3. Modelo de Movimiento Odométrico .............................................................................. 46
3.4.4. Modelo de Movimiento Basado en Mapas ................................................................... 48
3.5. Controlabilidad y Métodos de Direccionamiento (Steering Methods) ...................... 48
3.6. Conclusiones ...................................................................................................................................... 49
CAPÍTULO 4 Localización de Robots ........................................................................................................ 51
4.1. Introducción ...................................................................................................................................... 51
4.2. Fusión de Información .................................................................................................................. 51
4.3. Estimadores Recursivos y El Marco de Trabajo Bayesiano ........................................... 53
4.3.1. El Filtro de Bayes ................................................................................................................... 54
4.3.2. Filtro de Bayes aplicado a la localización de robots ................................................ 57
4.4. Estimadores Recursivos Gaussianos ....................................................................................... 58
4.4.1. Kalman Filter (KF) ................................................................................................................. 58
4.4.2. Extended Kalman Filter (EFK) ......................................................................................... 63
4.4.3. Unscented Kalman Filter (UKF) ....................................................................................... 66
4.4.4. Information Filter (IKF) y el Extended Information Filter (EIKF) .................... 69
4.5. Estimadores Recursivos No Paramétricos ............................................................................ 70
4.5.1. Filtro Histograma ................................................................................................................... 70
4.5.2. Filtros de Partículas .............................................................................................................. 72
4.6. Modelo de Percepción en Entornos Inteligentes con percepción ............................... 76
4.7. Conclusiones ...................................................................................................................................... 79
CAPÍTULO 5 Planificación de Movimiento ............................................................................................. 81
5.1. Introducción ...................................................................................................................................... 81
5.2. El Problema de la Planificación ................................................................................................. 82
5.2.1. Extensiones del problema .................................................................................................. 83
5.2.2. Complejidad ............................................................................................................................. 84
5.3. La Planificación de Caminos........................................................................................................ 85
5.4. Métodos Combinatorios para la Planificación de Caminos ........................................... 86
7
5.4.1. RoadMaps .................................................................................................................................. 87
5.4.2. Descomposición en Celdas ................................................................................................. 89
5.5. Métodos Basadas en Muestras para la Planificación de Caminos (Sampling-
Based) 90
5.5.1. Probabilistc Roadmaps(PRMs) ........................................................................................ 94
5.5.2. Obstacle Based PRM (OBPRM) ......................................................................................... 95
5.5.3. Rapidly-Exploring Random Tree (RRT) ...................................................................... 95
5.5.4. Expansive-Spaces Tree (EST) .......................................................................................... 97
5.5.5. Lazy Probabilistic Roadmap (LazyPRM) ...................................................................... 97
5.5.6. Single Query Bi-Directional Lazy collision checking PRM (SBL) ........................ 98
5.5.7. Sampling-Based Roadmap of Trees (SRT) .................................................................. 98
5.6. Campos de Potenciales y Funciones de Navegación ...................................................... 100
5.6.1. Campos de Potenciales ..................................................................................................... 101
5.6.2. Funciones de Navegación en Espacios Discretos................................................... 103
5.6.3. Otras Aproximaciones ....................................................................................................... 105
5.6.4. Función de navegación para WMRs no-holónomos ............................................. 107
5.7. Planificación de de Movimiento bajo Restricciones Diferenciales ........................... 107
5.7.1. El Problema Completo del Movimiento ..................................................................... 108
5.7.2. Tipos y Terminología ........................................................................................................ 109
5.8. Planificación de Movimiento en WMRs No-holónomos ............................................... 109
5.8.1. Generación de Trayectorias y el problema de la existencia .............................. 109
5.8.2. Construcción Incremental de con Programación Dinámica (BLM) .......... 110
5.8.3. El Método de la Aproximación (Approximation Approach) ............................. 111
5.8.4. Planificación Basados en Muestras para WMRs no-holónomos ...................... 112
5.8.5. Lattice-Noholonomic Search .......................................................................................... 112
5.9. Conclusiones y Trabajo futuro ................................................................................................ 114
CAPÍTULO 6 Evitación de Obstáculos y Colisiones .......................................................................... 117
6.1. Introducción ................................................................................................................................... 117
6.2. Contexto de la investigación .................................................................................................... 118
6.3. El Problema de la Evitación de Obstáculos ........................................................................ 118
6.3.1. Componentes en un Sistema de Evitación de Obstáculos .................................. 120
6.3.2. Limitaciones en la Evitación de Obstáculos ............................................................. 121
6.3.3. Evitación de Obstáculos Reactiva ................................................................................. 122
6.3.4. Evitación de Obstáculos Híbrida................................................................................... 125
6.4. Métodos Reactivos de Evitación de Obstáculos ............................................................... 127
8
6.4.1. Potential Field Approaches (PFM) ............................................................................... 127
6.4.2. Virtual Force Field (VFF) ................................................................................................. 128
6.4.3. Vector Field Histogram (VFH) ...................................................................................... 130
6.4.4. Extended Potential Field (EPF) ..................................................................................... 132
6.4.5. Dynamic Window Approach (DWA) ........................................................................... 133
6.4.6. Curvature Velocity Method (CVM)............................................................................... 135
6.4.7. Virtual Force Histogram+ (VFH+) ................................................................................ 136
6.4.8. Schelgel approach ............................................................................................................... 138
6.4.9. Trajectory Rollout Algorithm (TR) .............................................................................. 139
6.4.10. Virtual Damping Force (VDP) ........................................................................................ 141
6.4.11. Otras aproximaciones ....................................................................................................... 142
6.4.12. Tabla comparativa .............................................................................................................. 143
6.5. Métodos Híbridos de Evitación de Obstáculos ................................................................. 144
6.5.1. Global Window Approach (GDWA) ............................................................................. 144
6.5.2. Virtual Force Histogram* (VFH*) ................................................................................. 145
6.5.3. The Gradient Method ........................................................................................................ 147
6.5.4. Stachniss Approach ............................................................................................................ 148
6.5.5. Reduced dynamic window (rDWA)............................................................................. 151
6.5.6. Multi-Level Lattice .............................................................................................................. 152
6.5.7. Otras aproximaciones ....................................................................................................... 153
6.5.8. Path-following Window Motion Planning (PFWMP) ........................................... 154
6.6. Modelado y actualización del mundo ................................................................................... 156
6.6.1. Percepción y representaciones de ............................................................. 156
6.6.2. Point Clouds .......................................................................................................................... 157
6.6.3. Occupancy Grid y Certainty Grid .................................................................................. 157
6.6.4. Mapeo Incremental (Incremental Mapping) ........................................................... 158
6.6.5. Simultaneous Localization and Mapping (SLAM).................................................. 158
6.6.6. Enriquecimiento del modelo del mundo local ........................................................ 159
6.6.7. Obstáculos en Movimiento e Incertidumbre ........................................................... 159
6.7. Control compartido ..................................................................................................................... 161
6.8. Integración de Evitación de Obstáculos con Planificación y Control ...................... 164
6.8.1. Deformación de caminos - Elastic bands ................................................................. 165
6.9. Conclusiones y Trabajo Futuro ............................................................................................... 168
CAPÍTULO 7 Arquitecturas Software para Robótica Distribuida .............................................. 169
7.1. Introducción ................................................................................................................................... 169
9
7.2. Sistemas Multi-Agente en la Robótica .................................................................................. 171
7.2.1. Aplicaciones .......................................................................................................................... 172
7.3. Robotics Software Frameworks ............................................................................................. 172
7.4. Tecnologías ..................................................................................................................................... 174
7.4.1. Open-RDK ............................................................................................................................... 175
7.4.2. OpenTM (Open Robot Technology Middleware) ................................................... 175
7.4.3. ORCA ........................................................................................................................................ 176
7.4.4. OROCOS (Open Robot Control Software).................................................................. 177
7.4.5. ROS (Robotic Operative System) .................................................................................. 177
7.4.6. YARP (Yet Another Robotic Platform) ....................................................................... 178
7.5. Conclusiones ................................................................................................................................... 178
II. Conclusiones y Trabajo Futuro ......................................................................................................... 181
III. Bibliografía ........................................................................................................................................... 183
10
11
CAPÍTULO 1 INTRODUCCIÓN
1.1. MOTIVACIÓN
ste trabajo se centra en el estudio de los principios fundamentales de la navegación
de robots móviles con ruedas (WMRs) en entornos inteligentes. Se abordan de
manera transversal distintas áreas directamente implicadas en el problema: la
localización, los modelos de movimiento, la percepción, la planificación de movimiento, la
evitación de obstáculos y las arquitecturas distribuidas para sistemas robóticos. Diversas
técnicas reconocidas son expuestas en cada una de estas áreas. Este trabajo define la base
para el desarrollo de futuras investigaciones en el ámbito navegación de WMRs en
entornos inteligentes. El presente capítulo presenta el contexto, la motivación y los
objetivos de la investigación.
1.2. CONTEXTO
La navegación en WMRs ha evolucionado sorprendentemente en las últimas tres décadas.
La mayoría de los problemas planteados en los años 80 han sido superados. Algunos de
ellos son: la planificación de trayectorias en robots no-holónomos, el seguimiento de
trayectorias, la navegación con sistemas de percepción sujetos a errores y la evitación de
obstáculos en tiempo real. En la actualidad, el reto es la navegación en tiempo real en
entornos dinámicos y no modelados con obstáculos desconocidos en movimiento. El
avance ha sido espectacular especialmente en la investigación aplicada en el ámbito del
automóvil donde vehículos autónomos son capaces de recorrer largas distancias en
terrenos abruptos (Thrun, y otros, 2007), planificar en tiempo real operaciones complejas
multi-etapa como el aparcamiento (Lamiraux, Bonnafous, & Lefebvre, 2004), navegar en
entornos urbanos con presencia de otros vehículos autónomos (Urmson, y otros,
Autonomous driving in urban environments: Boss and the Urban Challenge, 2008).
Muchos de estos avances están ya disponibles en el mercado del automóvil y otros sin
duda lo estarán en el futuro.
Sin embargo, estos grandes avances son aplicables en otros ámbitos de aplicación donde la
navegación de WMRs sea necesaria. Algunos ejemplos son: navegación de WMRs en el
ámbito industrial, logística, la exploración planetaria, los servicios a personas en el hogar o
la asistencia a discapacitados y la rehabilitación. Este último es de especial interés para
nuestro grupo de investigación.
El concepto de inteligencia ambiental AmI aparece para solucionar nuevos retos que
surgen. Distintos WMRs en el mismo entorno de trabajo deben colaborar entre sí y con el
entorno para lograr una navegación más segura y eficiente. Esto es especialmente
interesante en el ámbito de la rehabilitación en entornos complejos, dinámicos y
E
12
desestructurados como hospitales donde los WMRs comparten el espacio de trabajo con
personas, otros WMRs y otros vehículos semi-autónomos. La percepción y procesamiento
distribuido es clave en la predicción de colisiones, evitar atascos y otras situaciones
conflictivas.
El Grupo de Robótica y Tecnología de Computadores Aplicada a la Rehabilitación de la
Universidad de Sevilla ha colaborado en distintos proyectos en el área de la asistencia en
la navegación en sillas de ruedas (Civit Balcells, Díaz del Río, Sevillano, & Jiménez, 1996),
(Sevillano, Civit, Díaz del Río, & Jiménez, 1997) y también en la navegación de sillas de
ruedas semi-operadas en entornos inteligentes (Sevillano, y otros, 2004) y (Abascal,
Bonail, Casas, Marco, Sevillano, & Cascado, 2009). Otros avances importantes en el ámbito
de la navegación de sillas de ruedas se encuentran en: (Díaz del Río, 1997), (Díaz, 2001) y
(Cagigas Muñiz, 2001). En ellos se aborda el problema del control, evitación de obstáculos
y planificación de movimiento en grandes edificios respectivamente. Todos ellos son
referencia fundamentales de este trabajo.
1.3. OBJETIVOS
El principal objetivo de este trabajo es realizar un estudio del arte en las distintas áreas
relativas a la navegación de WMRs: modelos de movimiento, localización, planificación de
movimiento, evitación de obstáculos y percepción distribuida. Estudiar como los distintos
métodos existentes se relacionan, y mostrar sus ventajas e inconvenientes. Esta
investigación define un marco de trabajo para el desarrollo de nuevas ideas en el ámbito
de la navegación de WMRs. Este marco de trabajo es útil para el desarrollo de técnicas en
la asistencia en la navegación de WMRs en ambientes inteligentes.
También es objetivo descubrir que avances en la tecnología y arquitectura de
computadores y la inteligencia artificial que usadas en combinación con las distintas
técnicas navegación de WMRs estudiadas: el hardware masivamente paralelo y las
arquitecturas distribuidas para robots, los sistemas multi-agente y los sistemas
bioinspirados pulsantes son de interés especial dentro de nuestro grupo de investigación.
El objetivo personal más importante es la adquisición del rigor y formalidad matemática
necesaria para expresar nuevas ideas de investigación de manera científica. También la
adquisición del vocabulario y los tecnicismos existentes en el área de investigación de la
robótica. Conocer las últimas investigaciones y entender el alcance y las carencias de los
enfoques propuestos. De esta forma, es más sencillo detectar potenciales ideas de
investigación. Por último, es importante profundizar en las investigaciones previas de
otros doctores del departamento en el ámbito de la navegación de robots. De este modo
que mejora la comunicación, la productividad y el trabajo en equipo en las tareas de
investigación. También es útil para agregar y unificar el trabajo realizado por el grupo
hasta ahora.
1.4. METODOLOGÍA
La metodología de investigación seguida tiene tres pilares fundamentales: adquisición de
conocimiento base, exploración y profundización, experimentación.
Conocimiento base
13
Para adquirir el conocimiento base necesario en el área de la navegación de WMRs se han
utilizado tres tesis doctorales y cinco libros que describen las técnicas existentes más
maduras aceptadas, y reconocidas en las distintas áreas de la navegación de WMRs. Las
tres tesis doctorales de referencia principales son:
- Análisis y evaluación del control de un robot móvil: aplicación a sillas de ruedas
eléctricas (Díaz del Río, 1997) - estudia en profundidad el control para el
seguimiento de caminos y trayectorias de sillas de ruedas.
- Una aportación al guiado de Sillas de Ruedas Eléctricas (Díaz, 2001) – estudia la
aplicación de las técnicas de campos de potenciales a la asistencia en la navegación
de sillas de ruedas.
- Un sistema eficiente de planificación de trayectorias en entornos cerrados grandes
para robots móviles y AGVs (Cagigas Muñiz, 2001) - abordan el problema de la
navegación en entornos grandes como hospitales utilizando mapas topológicos
jerárquicos.
Los cinco libros de referencia principales son:
- Springer Handbook of Robotics (Siciliano & Khatib, 2008) – Referencia general
donde se describen diversas temáticas de la robótica y donde multitud de
referencias pueden ser adquiridas. Diversos capítulos abordan problemas tratados
en este trabajo: Wheeled Mobile Robots, Motion Planning, Multi-Sensor Data Fusion,
Motion Control of Wheeled Mobile Robots, Motion Planning and Obstacle Avoidance y
World Modeling.
- Probabilistic Robotics (Thrun, Burgard, & Fox, 2005) – Se estudia el rol de la
estadística en la robótica centrándose en las áreas de localización, percepción y
SLAM.
- Introduction to Autonomous Mobile Robots (Siegwart & Nourbakhsh, 2004) – Se
centra en el estudio del movimiento y la navegación de WMRs. Destaca el estudio
realizado sobre la cinemática de los distintos de WMRs existentes. También trata
áreas como la localización, la planificación y evitación de obstáculos.
- Principles of Robot Motion (Choset, y otros, 2005) – Realiza un estudio general a la
navegación de WMRs, centrándose en el área de planificación. También trata áreas
como la localización, la cinemática y la dinámica en la robótica.
- Planning Algorithms (LaValle S. M., Planning Algorithms, 2006)- Muy completa y
extensa referencia sobre la planificación aplicada en la robótica.
Exploración y profundización
Partiendo del conocimiento base existente en las referencias mencionadas se ha realizado
una búsqueda de artículos científicos concretos que se centran y explican técnicas
específicas en las diversas áreas estudiadas en el trabajo: localización, modelos de
movimiento, evitación de obstáculos, planificación y percepción distribuida.
Importante destacar la utilizad de las herramientas online para búsqueda de información
científica: Google Scholar y IEEEXplore. Estas herramientas permiten no solo localizar
fácilmente artículos sino que suministran una métrica sobre el nivel de aceptación del
mismo por la comunidad científica basado en el número de citaciones de cada uno de ellos.
14
También destacar la utilidad de la herramienta Mendeley donde cientos de artículos
científicos pueden ser almacenados, categorizados y anotados. Esta herramienta permite
un uso manejable del desorbitado volumen de recursos científicos disponibles. Además
constituye una ayuda fundamental para la gestión de la bibliografía científica utilizada en
el trabajo.
Experimentación
La experimentación es la principal herramienta para la adquisición de conocimiento
científico. Sin ella, las ideas teóricas estudiadas no pueden ser asimiladas totalmente.
Diversos experimentos relacionados con la navegación de robots se han llevado a cabo
durante el desarrollo de este trabajo tanto en entornos de simulación como en robots
reales (robot Erratic). Caben destacar las pruebas de planificación de movimiento como:
Gradient Method, Elastic Bands, Probabilistic Roadmaps (PRM), Navigation Function1 y
otras. También experimentación con distintas técnicas de evitación de obstáculos como:
Virtual Force Field (VFF), Dynamic Window Approach (DWA), Virtual Force Histogra (VFH)
y Trayectory Rollout (TR). También técnicas de localización como: Localización de
Montecarlo basado en filtro de partículas (AMCL), y Filtro de Kalman extendido (EKF).
Técnicas de modelado y actualización del mundo como: Local Perceptual Space y técnicas
de SLAM como Gmapping.
Destacar que todo este trabajo ha podido ser realizado gracias a la existencia de diversas
herramientas de desarrollo OpenSoure para robots existentes. Cabe destacar la plataforma
ROS: Robot Operative System (Quigley, y otros, 2009), el proyecto Player/Stage (Collett,
MacDonald, & Gerkey, 2005), la librería OpenCV (Bradski & Kaehler, 2008) y la librería de
desarrollo Mobile Robot Programming Toolkit (MRPT) (Blanco J. L., 2009).
1.5. ESTRUCTURA DEL TRABAJO
El resto de la memoria está estructurada de la siguiente manera: En el Capítulo 2 -
Navegación de WMRs
No-holónomos se establecen los fundamentos básicos en la navegación de WMRs, se
describe el problema de la navegación y se definen conceptos que estarán presentes en
todo el trabajo como el Espacio de Configuración , el espacio de Acción , el espacio de
estados Cinemática, Dinámica y otros. El Capítulo 3 – “Modelos de movimiento en WMRs
no-holónomos” realiza una caracterización de la forma en la que los robots móviles con
ruedas se mueven. Esta caracterización es importante dado que los modelos expuestos
serán utilizados a lo largo del resto del trabajo. El Capítulo 4 – “Localización de Robots” se
centra en cómo solucionar este problema fundamental de la navegación de robots
mediante técnicas de fusión de información de los sistemas de percepción y en modelos
teóricos de movimiento. El Capítulo 5 – “Planificación de Movimiento” estudia diversas
técnicas reconocidas y acepadas para la planificación de movimiento desde el enfoque
global u offline. También se centra en las técnicas de planificación aplicables a WMRs no-
holónomos. El Capítulo 6 – “Evitación de Obstáculos y Colisiones” enfoca el problema de la
navegación desde un punto de vista más aplicado de forma que los WMRs puedan alcanzar
sus objetivos de navegación en tiempo real evitando obstáculos no modelados, realiza un
estudio profundo de las diversas técnicas reactivas e híbridas existentes más aceptadas. El
Capítulo 7 –“ Arquitecturas Software para Robótica Distribuida” se centra en un estudio
sobre las distintas herramientas de desarrollo para sistemas multi-agente aplicables a una
15
arquitectura de navegación distribuida. Finalmente se exponen un conjunto de
conclusiones y propuestas de trabajo futuro.
16
17
CAPÍTULO 2 NAVEGACIÓN DE WMRS
NO-HOLÓNOMOS
2.1. INTRODUCCIÓN
Este capítulo expone una introducción al problema de la navegación de WMRs no-
holónomos describiendo algunos de los conceptos básicos esenciales que serán utilizados a
lo largo del trabajo. Se realizará un breve resumen de los hitos más importantes en la
historia de la navegación de WMRs no-holónomos. Por último se expondrá una serie de
conceptos y definiciones que son necesarios de manera transversal en todas las áreas
estudiadas en el presente trabajo: Modelos de movimiento, Localización, Percepción
Distribuida, Planificación de Movimiento y Evitación de Obstáculos.
Estructura
Se comenzará realizando un breve resumen histórico sobre la navegación de WMRs no-
holónomos. En este análisis se referenciará muchos de los problemas abordados en este
trabajo (ver apartado 2.2 - Historia). Luego se expondrán una serie de conceptos
fundamentales esenciales en el problema de la navegación definiendo la nomenclatura y
vocabulario que se utilizará a lo largo del trabajo (ver apartado 2.3- Conceptos
fundamentales en la Navegación de WMRs). Luego se expondrán un conjunto de
herramientas conceptuales útiles para manejar problemas de navegación en entornos con
obstáculos, especialmente útil para las técnicas de evitación de obstáculos y planificación
de movimiento (ver apartado 2.4 - Herramientas para gestionar mundos con obstáculos).
Por último se definirá un conjunto de conceptos esenciales relacionados con la algorítmica
y la IA que serán utilizados también transversalmente a lo largo de todo el trabajo (ver
apartado 2.5- Complejidad, optimalidad y completitud).
2.2. HISTORIA
La navegación de robots autónomos tiene más de cuatro décadas de madurez. Los
primeros robots móviles aparecen a finales de los 60 y las primeras técnicas de
planificación de movimiento en WMRs comienzan a desarrollarse.
Años 70
Hasta mediados de los 70, la robótica clásica la navegación de robots se centraba en dos
ramas de investigación claramente diferenciadas: La Teoría del Control y la Planificación
de Movimiento. La segunda utilizaba técnicas clásicas de IA. Las primeras técnicas de
planificación se centraban en la construcción de un plan completo y óptimo basado en un
modelo del mundo offline (ver apartado 5.4 - Métodos Combinatorios para la Planificación
de Caminos ). Posteriormente un módulo ejecutivo (control) interpretaba el plan. El
modelo del mundo debía ser suficientemente preciso como para la construcción de un
correcto plan. Sin embargo, estas técnicas eran difícilmente aplicables en la práctica. Los
modelos eran creados a mano y no representaban entornos reales. La investigación se
18
centraba en la simulación. Este enfoque es conocido como el paradigma basado en modelos
(Thrun, Burgard, & Fox, 2005)
La arquitectura clásica de navegación expuesta tenía otros problemas graves: El nivel de
desconexión entre el módulo de planificación y el de ejecución (control). El plan se
realizaba previamente en un proceso deliberativo que podía tardar minutos. Luego,
durante la ejecución la incertidumbre en el estado del robot podía desbaratar la completa
ejecución de un plan. Esta incertidumbre entre el estado teórico y el estado real del robot
era inaceptable en la mayoría de los casos pero el uso de los sistemas probabilísticos de
estimación del estado no se extendería hasta los años 90.
Por otra parte, a finales de los 70 se populariza el concepto de espacio de configuración
para abordar los problemas de planificación en robots móviles y manipuladores. (Lozano-
Perez, 1983). Este enfoque permitía simplificar el problema de la planificación de
movimiento a la búsqueda de un camino en este espacio en el espacio de configuración,
que de forma implícita consideraba la forma del robot y los obstáculos. El principal reto
que surge en los comienzos es como construir de manera explícita este espacio de
configuración para poder ser resuelto por los métodos de planificación de caminos
clásicos. En (Reif J. , 1987) se formaliza el concepto de planificación de caminos y se
estudia en profundidad la complejidad computacional del problema.
Años 80
Durante los años 80 aparecen las primeras técnicas de evitación de obstáculos (ver
Capítulo 6 - Evitación de Obstáculos y Colisiones) inspirados en la técnica de Campos de
Potenciales (Khatib O. , 1986). Estas técnicas definían una ley de control con
realimentación que contemplaba la existencia de obstáculos y que dirigía la navegación del
robot.
A mediados de la década de los 80 se formaliza el concepto de evitación de obstáculos
reactiva (Reactive Paradigm o Sense/Act Paradigm) donde el movimiento del robot no
estaba basado en un modelo del mundo previo. La idea clave en este paradigma era crear
sistemas de comportamiento sencillo que se comportaran de manera reactiva ante la
información sensorial (ver apartado 6.4- Métodos Reactivos de Evitación de Obstáculos).
Múltiples reglas sencillas podían describir comportamiento complejo emergente en la
ejecución debido a la interacción el entorno. A pesar de sus limitaciones, este enfoque, este
enfoque presentó resultados más aplicables en la práctica que el paradigma basado en
modelos. Como desventaja, la ausencia de modelos reducían las capacidades del robot.
(Thrun, Burgard, & Fox, 2005).
El paradigma reactivo atenuó temporalmente la importancia del problema del dead-
reckoning un sistema de localización poderoso. La información más importante era
percibida por los sensores en el marco de referencia del robot. Los sistemas odométricos
eran utilizados para estimar la posición. Sin embargo, su utilidad era limitada debido a la
acumulación de error.
Aunque originalmente los Campos de Potenciales fueron ideados como un método de
control (siendo las primeras técnicas de Evitación de Obstáculos) su uso se extendió
rápidamente a la planificación de movimiento global offline. Aparece entonces el concepto
19
de Función de Navegación para evitar el problema del mínimo local en la planificación
global (ver apartado 5.6- Campos de Potenciales y Funciones de Navegación)
Durante estos años también se profundiza en el control de WMRs no-holónomos, y se
demostró para diversos modelos de WMRs no-holónomos que eran Small-Time Locally
Controlable. Esta propiedad asegura la existencia de una trayectoria admisible partiendo
de un camino previo no admisible. De esta forma, las técnicas de planificación de caminos
podían ser directamente aplicadas sobre en muchos WMRs no-holónomo. Además
aparecen las primeras técnicas de planificación que consideran las restricciones
cinemáticas de los WMRs no holónomos de manera directa (ver apartado 5.8 -
Planificación de Movimiento en WMRs No-holónomos)
Años 90
A principio de los años 80 nuevos métodos reactivos que contemplan las limitaciones
cinemáticas y dinámicas de los WMRs no-holónomos son desarrollados. Algunos ejemplos
son los métodos reactivos DWA y CVM (ver apartado 6.4 - Métodos Reactivos de Evitación
de Obstáculos). Nuevas técnicas probabilística de movimiento aparecen para abordar
problemas en espacios de configuración de alta dimensionalidad como manipuladores y
coordinación multi-robot. Estos métodos solucionan parcialmente el problema de la
complejidad computacional de los métodos clásicos (Sampling-Based Methods). Para
superar los problemas de complejidad utilizan mediante enfoques voraces, heurísticos y
probabilísticos. Técnicas como PRM y RRT se hacen muy populares (ver apartado 5.5-
Métodos Basadas en Muestras para la Planificación de Caminos (Sampling-Based)).
A mediados de los 90 se extendió el uso de técnicas híbridas de evitación de obstáculos
(ver apartado 6.5 - Métodos Híbridos de Evitación de Obstáculos). Este enfoque (también
conocido como paradigma Sense/Plan/Act) utiliza ideas del paradigma reactivo y e ideas
de las técnicas deliberativas de planificación global. Estos mostraron mejores resultados
dado que tenían una mayor capacidad para estimar y predecir el estado futuro del sistema.
Surge la necesidad de mejorar e implantar el uso de los sistemas de fusión de información.
A mediados de los 90’s aparecen los denominadnos métodos de estimación y predicción
probabilísticos que tratan de combinar la información proveniente de los sensores con la
información predicha por los modelos teóricos. Estos sistemas permiten, en mayor o
menor medida trabajar con modelos imprecisos y sensores imprecisos y ser capaz con esta
información de obtener la información más robusta y precisa posible. Los métodos de
estimación de estados probabilísticos paramétricos como el Filtro de Kalman y los no
paramétricos como el método de Localización de Montecarlo adquieren una gran
popularidad (ver Capítulo 4- Localización de Robots). También se estudian diversas
técnicas de Mapping para la construcción de mundos locales.
Siglo XXI
Las técnicas de evitación de obstáculos y planificación se encuentran en una etapa de
madurez elevada. No obstante, nuevas técnicas aparecen para WMRs no-holónomos
mejorando. Se aborda en mayor profundidad el problema de los entornos dinámicos y con
obstáculos en movimiento.
Los métodos de estimación y predicción probabilísticos se establecen como las
aproximaciones estándar para la fusión de información en la localización de robots.
20
(Durrant-Whyte & Henderson, 2008). El problema de la localización y mapeo simultáneo
es abordado y surgen distintas técnicas de SLAM que solucionan el problema de manera
satisfactoria. Durante estos años diversas tecnologías Software aparecen para construir
arquitecturas software Robóticas Complejas y Distribuidas. También durante estos años es
el boom de los vehículos inteligentes, donde WMRs son capaces de recorrer largas
distancias de manera autónoma y circular en entornos urbanos con otros vehículos en
movimiento.
A continuación se expone una serie de conceptos fundamentales en el problema de la
navegación de WMRs no-holónomos. Estos conceptos serán utilizados de manera
transversal durante todo el trabajo.
2.3. CONCEPTOS FUNDAMENTALES EN LA NAVEGACIÓN DE WMRS
En este apartado se expondrán y discutirá sobre una serie de conceptos fundamentales
imprescindibles para abordar el problema de la navegación de WMRs no-holónomos. El
uso de estos conceptos están extendidos en la comunidad científica y su uso es necesario
para una correcta comprensión de las distintas ideas expuestas. Algunos conceptos que se
tratarán son: El concepto de WMR no-holónomo, la cinemática, la dinámica, el Espacio de
Trabajo , el Espacio de Configuración y el Espacio de Estados .
2.3.1. WMRs no-holónomos
Los sistemas no-holónomos están caracterizados por estar sujetos a un conjunto de
restricciones diferenciales sobre las variables de configuración respecto el tiempo. Estas
ecuaciones no son integrables y surgen típicamente cuando hay menos variables de
control que variables de configuración (sistemas sub-actuados). Un ejemplo son los WMR
no-holónomos estudiados en este trabajo. Estos tienen dos variables actuadoras: la
velocidad lineal y la velocidad angular, sin embargo este se mueve en un espacio de
configuración 3-Dimensional. Como consecuencia, cualquier camino en el Espacio de
Configuración no corresponde de manera necesaria a un camino admisible para el sistema.
Algunos ejemplos de vehículos no-holónomos extendidos en la sociedad de vehículos no-
holónomos son Coches, sillas de ruedas, bicis y motos. Las restricciones cinemáticas
aparecen en diversas áreas de navegación de WMRs no-holónomos como la evitación de
obstáculos, la generación de trayectorias y la planificación de movimiento.
2.3.2. Cinemática
La cinemática es el estudio más básico del movimiento de sistemas mecánicos sin tener en
cuenta las fuerzas y torques que producen este movimiento y limitándose al estudio de las
trayectorias en función del tiempo. Conocer el comportamiento cinemático de un WMR no-
holónomo es un aspecto esencial en este trabajo.
Desde el punto de vista clásico de la teoría del control automático el cálculo cinemático
describe el efecto de de las variables de control en la configuración de un robot (Thrun,
Burgard, & Fox, 2005). Este comportamiento puede ser modelado matemáticamente como
la configuración del sistema q evoluciona en el tiempo respecto a la entrada del sistema .
Entonces, siendo la variación temporal de la configuración, u la entrada del sistema. El
comportamiento cinemático de un WMR no-holónomo queda descrito de forma compacta
mediante la siguiente ecuación de transición de estado:
33
CAPÍTULO 3 MODELOS DE MOVIMIENTO EN
WMRS NO-HOLÓNOMOS
3.1. INTRODUCCIÓN
os vehículos con ruedas están ampliamente extendidos en nuestra sociedad, son
utilizados para el transporte de personas y mercancías utilizando por lo general
superficies habilitadas para este propósito como carreteras, carriles, etc. Lograr que
estos vehículos se muevan de manera autónoma para realizar estas tareas es un reto de
investigación desde hace más de tres décadas. Este tipo de vehículo autónomo se
denomina en la literatura Wheeled Mobile Robots – WMRs. Comprender como los WMRs se
mueven es la principal motivación de este capítulo. Se trata de un aspecto importante si se
desea diseñar un entorno inteligente que asista en la navegación de WMRs. Los modelos de
movimiento de los WMRs son necesarios en diversas áreas de la navegación (en las que
este trabajo se centra) como: los métodos de localización (Capítulo 4 - Localización de
Robots), métodos evitación de obstáculos (Capítulo 6 - Evitación de Obstáculos y Colisiones)
y la planificación de movimiento para WMRs no-holónomos (ver apartado 5.7 -
Planificación de de Movimiento bajo Restricciones Diferenciales) .
Estructura del capítulo
El concepto de Robot Móvil con Ruedas (WMR) y algunas de sus propiedades
fundamentales como estructura, controlabilidad y direccionabilidad son discutidos en el
apartado 3.2 - Robots Móviles con Ruedas (WMRs). Posteriormente se expone un sencillo y
general modelo de movimiento que describe los aspectos cinemáticos en WMRs no-
holónomos (ver apartado 3.3 - Modelo Cinemático en WMRs No-holónomos). Este modelo
será utilizado a lo largo de todo el trabajo. Posteriormente se exponen otros modelos que
pueden ser útiles en el trabajo. Los modelos probabilísticos son una aproximación sencilla
y elegante que permiten describir como un WMR no-holónomo se mueve en presencia de
incertidumbre en los sensores (ver apartado 3.4 - Modelos de Movimiento Probabilísticos).
Luego se describe de manera breve algunos conceptos y cuestiones importantes sobre la
controlabilidad en WMRs no-holónomos que son muy importantes en la navegación
(apartado 3.5 - Controlabilidad y Métodos de Direccionamiento (Steering Methods)).
Finalmente se exponen algunas conclusiones generales sobre el contenido del capítulo
(ver apartado 3.6 - Conclusiones).
3.2. ROBOTS MÓVILES CON RUEDAS (WMRS)
Formalmente los WMRs, son vehículos con ruedas capaces de realizar navegación
autónoma (sin la asistencia de un conductor humano) donde su movimiento es planificado
y controlado por un computador a bordo. En este trabajo también nos referiremos a WMRs
a robots cuyo movimiento es asistido por un entorno inteligente. Los WMRs. son
relativamente sencillos de implementar y muy eficiente energéticamente respecto a otros
mecanismos de locomoción de robots como piernas, robots aéreos, deslizantes, etc.
L
34
Los parámetros esenciales que caracterizan las capacidades de movimiento cinemáticas de
un WMR son: el número de ruedas, el tipo y la distribución de mismas. Cada tipo de rueda -
Standard (o fixed), Steer, Castor, Omni, Swedish – impone restricciones en el movimiento de
un robot. Existen distintos tipos de WMRs según estos parámetros. Los tipos más
estudiados en la bibliografía son: car-like (Akerman), differential-drive, synchronous-drive,
omidireccional-drive. En cualquier caso cualquier tipo de WMR se puede incluir dentro de
una de las cinco clases genéricas de WMRs según su movilidad y direccionabilidad
(steereability). La Figura 5 presenta ejemplos cada uno de estas cinco clases en WMRs de
tres ruedas.
En la década de los 90, la comunidad robótica consiguió un profundo entendimiento del
movimiento de los robots móviles y manipuladores, tanto sus aspectos cinemáticos como
dinámicos. Este capítulo realizará un estudio básico de los modelos existentes para WMRs
no-holónomos, centrándose en dos tipos: modelos cinemáticos deterministas y modelos
de movimiento probabilísticos.
Estabilidad maniobrabilidad y control
Los WMRs son diseñados en términos de estabilidad, maniobrabilidad y control (Siegwart
& Nourbakhsh, 2004). Estos aspectos están correlacionados y mejorar uno de ellos puede
llevar al empeoramiento de otro. Por ejemplo un robot con alta maniobrabilidad suele
tener un control más complejo, es el caso de los WMRs omnidireccionales con ruedas
suecas. Se suele elegir una solución de compromiso que sea óptima en el ámbito de
aplicación específico. Por ejemplo un robot tipo coche (car-like) no permite un
movimiento omnidireccional y presenta una maniobrabilidad reducida donde las
trayectorias circulares no pueden superar una curvatura máxima. Sin embargo presenta
una alta estabilidad incluso en superficies no planas (haciendo uso de un sistema de
suspensión). Implementar el control de este tipo de vehículo es relativamente sencillo
respecto a otro tipo de configuraciones como los robots diferenciales o robots
omnidireccionales.
Movilidad, direccionabilidad y maniobrabilidad
Según el número, distribución y tipo de ruedas los WMRs presentan determinado grado de
movilidad (mobility) y grado de direccionabilidad (steereability). Estos parámetros
caracterizan las capacidades del WMR. Existen 5 clases fundamentales según
donde cualquier WMR puede englobarse. La Figura 5 presenta los 5 tipos básicos de WMRs
de tres ruedas.
Una consecuencia directa de es grado el de maniobrabilidad [1,3] que indica
la capacidad de localizar el centro de rotación en el plano. Por ejemplo, indica que
el centro de rotación del WMR puede ubicarse en cualquier punto del plano. Con el
centro de rotación estaría restringido a ser ubicado en una línea, y con indicaría
que el centro de rotación es fijo y el robot solo se puede mover realizando movimientos
circulares. Los conceptos de maniobrabilidad, movilidad y direccionabilidad han sido
ampliamente estudiados en la bibliografía en los que destacan (Siegwart & Nourbakhsh,
2004) y (Campion & Chung, 2008).
51
CAPÍTULO 4 LOCALIZACIÓN DE ROBOTS
4.1. INTRODUCCIÓN
La localización es una tarea esencial en muchas aplicaciones en la robótica y en especial en
la navegación de WMRs no-holónomos. Reconocidos estudios en la navegación de robots
como (Cox, 1990) y (Borenstein, Everett, & Feng, 1996) afirman que: “Utilizar información
sensorial para localizar el robot en su entorno es el problema más fundamental para
lograr capacidades autónomas en un robot móvil”.
La localización es necesara para la ejecución de trayectorias y también para alcanzar el
objetivo en sistemas de evitación de obstáculos. Los sensores odométricos que muchos
robots poseen no son suficientes para resolver el problema de la localización debido a la
acumulación del error. Este capitulo describe una serie de algoritmos para la localización
robots mobiles. Localización en un marco de referencia global y común es esencial para
lograr la coordinación entre múltiples robots y la asistencia en la navegación en ambientes
inteligentes. Durante el capítulo se centra especial atención en la aplicación de distintos
métodos en esta área de la investigación.
Estructura del capítulo
El capítulo comienza haciendo una breve introducción a los conceptos de la robótica
probabilística y la fusión de información (ver apartado 4.2 - Fusión de Información). En el
siguente apartado se expone un marco de trabajo probabilístico basado en el Teorema de
Bayes (ver apartado 4.3 - Estimadores Recursivos y El Marco de Trabajo Bayesiano).
Diversas técnicas se basan en este marco de trabajo. Estas se pueden categorizar en dos
grupos: Los Estimadores Recursivos Gaussianos (ver apartado 4.4 - Estimadores Recursivos
Gaussianos) y los Estimadores Recursivos no Paramétricos (ver apartado 4.5 - Estimadores
Recursivos No Paramétricos). Posteriormente exponen algunas consideraciones en la
aplicación de estos métodos en entornos inteligentes (ver apartado 4.6 - Modelo de
Percepción en Entornos ). Finalmente se exponen conclusiones sobre las distintas técnicas
estudiadas en el contexto de este trabajo (ver apartado 4.7 - Conclusiones).
4.2. FUSIÓN DE INFORMACIÓN
El problema de la localización está enmarcado dentro del paradigma de la Fusión de
Información. La fusión de información consiste en la combinación de las distintas fuentes
de información para estimar de una forma más exacta el estado desconocido del sistema
(Durrant-Whyte & Henderson, 2008). La información a fusionar proviene tanto de
sistemas de percepción como de modelos teóricos que definen el comportamiento
dinámico del sistema (ver Capítulo 3 - Modelos de movimiento en WMRs no-holónomos). El
objetivo de la fusión de información es tener una descripción mucho más robusta y exacta
del estado del robot. Distintas técnicas de fusión de información son utilizadas de manera
exahustiva en la robótica. Algunas areas de aplicación son: la localización, el
52
reconocimiento de objetos, construcción de mapas y localización. La fusión de
información.
Métodos probabilísticos
La fusión de información en la robótica en la actualidad se aborda mediante estadísticos.
La idea clave de los métodos probabilísticos respecto a otros métodos de estimación
clásicos es que no solo indican una hipótesis sobr el estado del robot, sino que indican
cuanto se cree en ella. Distintas hipótesis sobre el estado pueden ser consideradas de
manera simultánea. La Figura 14 presenta un caso típico sobre la creencia en un espacio
de estados continuo con dos variables..
Una vez conocidas las hipótesis más probables, un seguimiento del estado del sistema es
relativamente sencillo. La nueva información adquirida por los mecanismos de percepción
debe ser coherente con alguna de las hipótesis haciéndolas más probables. De esta forma
la información disponible sobre el estado de un robot es más robusta y coherente. Otra
ventaja del enfoque estadístico es que se puede estiamr el estado de ciertas variables que
son ocultas y no se pueden medir de manera directa mediante ningún sensor (Thrun,
Burgard, & Fox, 2005).
Figura 14. En la robótica probabilística el estado de un robot no es descrito como un conjunto de variables de
estado con valor único, sino como una función de distribución que describe la probabilidad de que el robot se
encuentre en cada estado. De esta forma se describe de manera más fideligna otros aspectos como múltiples
hipótesis de estado o la creencia de estar en el estado más proable.
Limitaciones
Por lo general el enfoque probabilístico presenta una mayor complejidad computacional.
Para controlar esta complejidad, la mayoría de los métodos propuestos son
aproximaciones o presentan unas estrictas restricciones en el problema que lo limitan a
un pequeño conjunto de problemas sencillos. Algunas de las simplificaciones típicas son: la
asunción de Markov, restricciones en el comportamiento del error, discretización del
espacio de estados, etc. Estos aspectos serán explicados más detenidamente en apartados
posteriores. (Thrun, Burgard, & Fox, 2005)
53
4.3. ESTIMADORES RECURSIVOS Y EL MARCO DE TRABAJO BAYESIANO
El reconocido libro “IA A Modern Approach” (Russell, Norvig, Canny, Malik, & Edwards,
1995) propone un marco de trabajo probabilístico para la fusión de información basado en
el Teorema de Bayes. Este marco de trabajo define un proceso recursivo denominado
“Filtro de Bayes” que realiza una estimación periodica del estado del robot. El estado es
descrito mediante una función de densidad (denominada creencia) que define la
probabilidad de que el sistema se encuentre en cualquier estado . El Filtro de Bayes
se ha utilizado en las dos últimas décadas de manera exhaustiva en el problema de la
localización de Robots.
Técnicas existentes
Existen diversos métodos de fusión de sensores para la localización de robots basados en
el Marco de trabajo Bayesiano (ver Figura 15). En este trabajo estudiarán las dos familias
de técnicas más aceptadas por la comunidad científica: Filtros recursivos Gaussianos ver
(0- Implementaciones
Existen diversas implementaciones OpenSource de los métodos estudiados. Tres
Frameworks de desarrollo para robots destacan en implementaciones de estos:
Player/Stage , ROS y MRPT .
Estimadores Recursivos Gaussianos) y Filtros recursivos no-parametrico (ver apartado 4.5 -
Estimadores Recursivos No Paramétricos).
Estimadores Recursivos
Bayesianos
Filtros Gaussianos Filtros No paramétricos
Kalman Filter
Extended
Kalman Filter
Unscented
Kalman FilterInformation Filter
Extended
Information Filter
Histogram Filter Particle Filter
Figura 15. Estimadores recursivos estudiados en este capítulo.
Teorema de Bayes
El Teorema de Bayes es la base define una regla fundamental estadística. El teorema de
Bayes la probabilidad condicional de un evento aleatorio x dado z en términos de la
distribución de probabilidad condicional del evento z dado x y la distribución de
probabilidad marginal de sólo z. Desde el punto de vista de la robótica, el Teorema de
Bayes define una vía para estimar la probabilidad de cualquier estado de un sistema
dada una observación (Durrant-Whyte & Henderson, 2008).
Sea x el estado exhaustivo del sistema y sea z una medida observación obtenida por los
sistemas de percepción. Se realizan las siguientes definiciones:
81
CAPÍTULO 5 PLANIFICACIÓN DE
MOVIMIENTO
5.1. INTRODUCCIÓN
A planificación de movimiento (Motion Planning) es una de las categorías
fundamentales dentro del problema de la Navegación en WMRs. Las técnicas de
planificación de movimiento definen la secuencia de movimientos necesaria para que
un WMR alcance una posición o configuración objetivo partiendo de una posición o
configuración inicial sin colisionar con ningún obstáculo del entorno. Las técnicas de
planificación de movimiento utilizan conceptos e ideas pertenecientes a las otras áreas de
la ciencia como: la geometría computacional, la estadística, la inteligencia artificial y la
teoría del control automático.
La planificación de movimiento tiene más de cuatro décadas de madurez. Los primeros
métodos aparecieron durante los años 70. Sin embargo, aún se trata de un problema
abierto con nuevas aportaciones cada año. La planificación de movimiento en entornos
inteligentes donde la ubicuidad y la percepción distribuida entran en juego plantea aún
muchos retos.
Este capítulo realiza un estudio del arte de las técnicas históricas y actuales más
relevantes, centrándose en la planificación de movimiento en WMRs en el plano y en
entornos estáticos (no existen obstáculos en movimiento) donde un modelo del mundo
está disponible. Referencias y comentarios a problemas más generales son realizadas a lo
largo de todo el capítulo.
Estructura del capítulo
A continuación se expondrá un resumen sobre los tipos de enfoques y extensiones
existentes para solucionar el problema de la planificación de movimiento (ver apartado
5.2 - El Problema de la Planificación). El siguiente apartado se centra en describir el
problema de la Planificación de Caminos que es una primera aproximación para resolver
problemas en la planificación de Movimiento (ver apartado 5.3 - La Planificación de
Caminos). En los dos siguientes apartados se exponen las dos familias fundamentales de
técnicas para la resolución del problema de la planificación de caminos (apartado 5.4 -
Métodos Combinatorios para la Planificación de Caminos ) y (apartado 5.5 - Métodos
Basadas en Muestras para la Planificación de Caminos (Sampling-Based)). El capítulo
siguiente expone el concepto d plan de navegación, una visión más general para la
resolución del problema de la planificación de movimiento (ver apartado 5.6 - Campos de
Potenciales y Funciones de Navegación). Finalmente se expone la planificación bajo
restricciones diferenciales que permite abordar la planificación de sistemas mucho más
realistas y complejos (ver apartados 5.7 y 5.8). Estos apartados se centran en la aplicación
de métodos de planificación en WMRs no-holónomos.
L
82
5.2. EL PROBLEMA DE LA PLANIFICACIÓN
Existen muchas categorías dentro de la planificación de movimiento (ver apartado 5.2.1 -
Extensiones del problema). El presente capítulo se centrará en tres las tres técnicas más
fundamentales: La Planificación de Caminos, las Funciones de Navegación y Campos de
Potenciales y la Planificación de Movimiento con Restricciones Diferenciales.
Planificación de caminos
La planificación de caminos parte de una especificación de la geometría del robot y los
obstáculos del entorno . Entonces, dadas la configuración inicial y objetivo
debe construirse un camino .
Aunque la planificación de caminos no representa por lo general una solución completa al
problema del movimiento, en algunos casos como los robots holónomos si puede serlo.
Muchas técnicas de planificación de caminos han sido diseñadas de manera desacoplada.
El camino representa un primer paso para obtener un plan completo al problema de la
planificación (ver apartado 5.8.4 - Planificación Basados en Muestras para WMRs no-
holónomos). En otros casos un camino puede ser una heurística para una técnica más
compleja. En última instancia el camino puede ser un plan incompleto y la capa inferior
(Control o Evitación de Obstáculos) debe ser capaz de interpretarla de la mejor forma
posible.
Dos subcategorías principales existen dentro de la planificación de caminos: las
aproximaciones combinatorias y la planificación de caminos basadas en muestras. La
planificación de caminos se estudiará con más profundidad en los apartados: 5.3- La
Planificación de Caminos, 5.4 - Métodos Combinatorios para la Planificación de Caminos y
5.5 - Métodos Basadas en Muestras para la Planificación de Caminos (Sampling-Based)
Planificación con Realimentación y Funciones de Navegación
Durante el proceso de deliberación no es posible saber qué ocurrirá durante la ejecución
del plan. En la práctica es habitual que el plan no pueda ser ejecutado correctamente. Una
pequeña desviación en la ejecución del plan implica una incoherencia entre la realidad y
lo planificado. Esto puede invalidar el plan completamente. Es decir, un plan de
movimiento definido por un camino o una secuencia de acciones puede ser poco robusto.
La incertidumbre en la ejecución es contemplada en las técnicas denominadas: Funciones
de Navegación y Campos de Potenciales. El plan es modelado como una ley o heurística de
control general que considera los obstáculos. Este plan puede ser ejecutado
independientemente del estado actual del robot por lo que es mucho más robusto ante
desviaciones. Por esto son también conocidas como planificación de movimiento con
realimentación (Feedback Motion Planning) (LaValle S. M., Planning Algorithms, 2006).
Estas técnicas son estudiadas en el apartado 5.6 - Campos de Potenciales y Funciones de
Navegación.
Planificación de Movimiento bajo Restricciones Diferenciales.
En la práctica existen multitud de restricciones que limitan el movimiento de un robot. En
este trabajo se aborda el problema de los WMRs no-holónomos que presentan
restricciones diferenciales en su movimiento. Por lo tanto estos robots no son capaces de
seguir cualquier tipo de camino o trayectoria y la planificación de caminos se convierte en
83
un enfoque incompleto. Estos aspectos pueden ser tenidos en cuenta en la fase de
planificación de movimiento y no ser delegados a la capa de control, enfrentando a esta a
situaciones comprometidas. Distintos tipos de problemas de planificación con
restricciones diferenciales existen, entre los que destacan: la planificación de robots no-
holónomas o la planificación con restricciones kinodinámicas. (LaValle S. M., Planning
Algorithms, 2006)
5.2.1. Extensiones del problema
Existen otras categorías y generalizaciones del problema. Entre ellas destacan: la
planificación con múltiples robots, la planificación en tiempo variante y la planificación
con incertidumbre.
Obstáculos en movimiento (Time-Varying Problems) – Los objetos del escenario se
mueven en trayectorias en función del tiempo. El enfoque utilizado para abordar este
problema es incrementar la dimensionalidad de en uno y obtener un camino
monotónicamente creciente en esta dimensión. Este problema es implícitamente una
planificación de trayectorias (no sólo de camino). Una limitación de estos enfoques es que
presuponen conocidas las trayectorias de los obstáculos por lo que en muchos casos no
son enfoques realistas. Debido a esto surge otras extensiones como la planificación de
movimiento con incertidumbre en la predicción, típicamente utilizado como técnica de
evitación de obstáculos (ver apartado 6.6.7- Obstáculos en Movimiento e Incertidumbre).
Figura 26. Esta figura muestra el problema de la planificación en tiempo variante. El tiempo es añadido como otra
dimensión del espacio de configuración. La posición objetivo pasa de ser un punto a una línea. El objetivo es
alcanzar esa línea con un camino monotónicamente creciente en la dimensión temporal. Fuente: (LaValle S. M.,
Planning Algorithms, 2006)
Múltiples robots – Distintos robots pueden colaborar de modo que un plan conjunto
puede ser necesario. Estos robots también pueden colisionar. Estos problemas puede ser
abordadas desde diversos enfoques: dos de los más conocidos son la planificación
centralizada y la planificación desacoplada. La planificación centralizada consiste
básicamente en considerar todos los robots como un único robot con más grados de
117
CAPÍTULO 6 EVITACIÓN DE OBSTÁCULOS Y
COLISIONES
6.1. INTRODUCCIÓN
En muchas de las aplicaciones prácticas los WMRs deben enfrentarse a una navegación en
entornos desconocidos, cambiantes y dinámicos. Entornos urbanos, áreas de servicio o
zonas industriales son algunos ejemplos. Las técnicas de planificación de movimiento
offline no presentan soluciones que puedan ser ejecutadas en tiempo real en entornos
dinámicos y desconocidos. Surge la necesidad de un sistema de evitación de obstáculos
(Obstacle Avoidance). Este debe tener la capacidad de predecir colisiones y modificar la
trayectoria para evitarla al mismo tiempo que intenta alcanzar la posición objetivo. Según
(Brooks, 1991) cualquier modelo del mundo offline es incompleto y está sujeto a errores.
Entonces, el mejor modelo existente es la realidad percibida por los sensores del WMR.
La idea clave en los métodos de evitación de obstáculos es introducir información rica del
entorno tiempo-real en bucle de control de navegación (Khatib O. , 1986). A diferencia de
los métodos de planificación global, no necesitan un modelo del mundo offline. Entonces,
en lugar de un modelo del mundo offline, los obstáculos son representados por un modelo
del mundo local online que se actualiza periódicamente en tiempo real haciendo
uso de los mecanismos de percepción del WMR.
Las técnicas de evitación de obstáculos es un área de investigación madura con más de dos
décadas de madurez. Las técnicas existentes actuales pueden ser aplicadas en robots
reales con buenos resultados. Sin embargo la investigación aún está abierta. La
investigación actual se centra en la evitación de obstáculos en entornos dinámicos
(obstáculos en movimiento) e incertidumbre en la predicción de estados futuros. Estas
investigaciones son directamente aplicable a situaciones muy complejas como navegación
en entornos Urbanos (Urmson, y otros, 2008). Este trabajo se centra en los métodos de
evitación de obstáculos en el plano y entornos estáticos, sin embargo algunas
consideraciones y referencias a entornos dinámicos son realizadas.
Interesantes estudios que repasan muchas de las técnicas de evitación de obstáculos
existentes, entre ellos destacan (Siegwart & Nourbakhsh, 2004) y (Minguez, Lamiraux, &
Laumond, 2008)
Estructura del capítulo
El presente capítulo describe las características, tipos y limitaciones de los métodos de
evitación de obstáculos. A continuación se realizará un resumen de las características más
importantes de los métodos de evitación de obstáculos. Posteriormente se analizarán los
enfoques existentes: métodos reactivos (apartado 6.3.3 - Evitación de Obstáculos Reactiva)
y los métodos híbridos (apartado 6.3.4 - Evitación de Obstáculos Híbrida). Se exponen
distintas técnicas notables diseñadas en las tres últimas décadas. Algunas consideraciones
118
importantes sobre la construcción del mundo local son expuestas (apartado 6.6 - Modelado
y actualización del mundo). Luego se exponen un conjunto de técnicas de evitación
reactivas (apartado 6.4 - Métodos Reactivos de Evitación de Obstáculos) y un conjunto de
técnicas híbridas (apartado 6.5 - Métodos Híbridos de Evitación de Obstáculos). La relación
entre la evitación de obstáculos, el control y la planificación y como estas pueden ser
integradas en una arquitectura de navegación es estudiado en el (apartado 6.8 Integración
de Evitación de Obstáculos con Planificación y Control).
6.2. CONTEXTO DE LA INVESTIGACIÓN
Las tecnologías robóticas aplicadas a la rehabilitación es una de las principales áreas de
investigación de nuestro departamento (Díaz del Río, 1997), (Cagigas Muñiz, 2001) y
(Díaz, 2001). Este trabajo se centra en el problema de la asistencia a la navegación de
WMRs en entornos inteligentes (Sevillano, y otros, 2004). Sin embargo, para abordar los
problemas de la navegación desde un enfoque distribuido es esencial un conocimiento
previo y profundo de técnicas de evitación de obstáculos más aceptadas en las últimas
décadas.
Es fundamental descubrir qué ideas pueden ser aplicadas o extrapoladas a un sistema de
navegación y percepción dirigido por un entorno inteligente. La principal aplicación es el
control compartido (Shared Control) entre un operador humano del WMR (por ejemplo
silla de ruedas). Un entorno inteligente mejoraría la capacidad de percepción y estrategia
de navegación global del vehículo. Además dispondría disponer de otras ventajas posibles
en un entorno inteligente: colaboración con otros vehículos, mayor potencia de cálculo,
etc. De este de modo que se espera conseguir una navegación más fluida, cómoda, sencilla.
Es por lo tanto necesario estudiar el nivel de integración posible entre los sistema de
evitación de obstáculos existentes. Esta temática se estudiará más detenidamente en el
presente capítulo (ver apartado 6.7 Control compartido).
6.3. EL PROBLEMA DE LA EVITACIÓN DE OBSTÁCULOS
La evitación de obstáculos surge en los años 80 por algunas limitaciones que presentaba el
enfoque de navegación clásico: planificación & control. La planificación de movimiento se
fundamenta en la existencia de un modelo del mundo offline exacto y preciso10. El
planificador genera una trayectoria o camino libre de obstáculos tras un proceso
deliberativo previo. Este plan es enviado un módulo ejecutivo (executive) que implementa
técnicas clásicas de path-following o trajectory-following. Posiciones consigna son
generadas y son utilizadas como referencia en un sistema de control de posición o pose
(Díaz del Río, 1997) (Morin & Samson, 2008). La ejecución se realiza confiando la ausencia
colisiones.
Los métodos clásicos de control de posición o configuración (pose o postura) son ciegos en
el sentido de que no son capaces de detectar obstáculos. El único feedback utilizado en
estos sistemas es la posición o configuración actual del robot (haciendo uso de sensores
básicos como odometría, IMU, GPS, etc.). El enfoque puede ser pragmático y eficiente en un
entorno de trabajo controlado y si se dispone de un sistema de localización muy preciso.
Sin embargo, esto no es asumible en muchas aplicaciones reales. La incertidumbre en la
10 Este enfoque es también conocido como paradigma basado en modelos (Thrun, Burgard, & Fox, Probabilistic robotics, 2005).
119
localización es un asunto especialmente problemático en la navegación de los WMRs. Una
localización inexacta puede provocar una incorrecta ejecución del camino y
eventualmente una colisión no esperada. En entornos dinámicos y desconocidos esta
arquitectura es incompleta dado que es necesario utilizar los mecanismos de percepción
disponibles. En este contexto dinámico, los primeros robots manipuladores realizaban
movimientos cortos y por etapas. En cada etapa tenían que parar la ejecución y realizar
una adquisición de datos, reconstruir y posteriormente realizar una replanificación.
Esta replanificación podía tardar minutos.
Los sistemas de evitación de obstáculos pretenden superar estas limitaciones. La idea
clave que identifica a los métodos de evitación de obstáculos es el uso de información
sensorial rica en el bucle de control del sistema de navegación. Esta información rica le
permite detectar y modificar el rumbo de la navegación en tiempo real. Por lo tanto, un
sistema de evitación de obstáculos puede verse como una caja negra que acepta como
entrada una configuración objetivo (o de forma relajada una posición en el Entorno
de trabajo) y sumistra como salida una directiva de navegación (steering command)
a una capa de control elemental de velocidad. Sin embargo, los métodos de evitación de
obstáculos también presentan limitaciones y no surgen para sustituir a los métodos de
planificación global o control sino como una forma de mejorar o complementar las
arquitecturas existentes (Tilove, 1990), (Khatib O. , 1986). Por eso la integración con
técnicas de planificación global sigue siendo importante y es motivo de estudio en este
capítulo (apartado 6.8 - Integración de Evitación de Obstáculos con Planificación y Control).
Planificador global
Planificador de trayectorias
Generador de trayectorias
Controlador externo
Controlador Interno
Sistema y Mundo
Trayectoria global
Rectas, arcos, etc.
Posición consigna (X,Y,Ф)
Velocidades de referencia (v,ω)
CO
NTRO
L
(visión, odometría, Laser,etc)
(odometría)
Figura 45. Arquitectura con módulo de control de posición del de SIRIUS en “modo automático” (Díaz del Río,
1997). Presenta una primera aproximación a la evitación de obstáculos en tiempo real introduciendo información
rica de sensores en el bucle de control. Sin embargo este sistema sigue siendo muy sensible a la incertidumbre en
la localización.
Definición
Sea la configuración objetivo, y sea en el instante que se encuentra en la
configuración . Entonces el robot ubicado en la configuración ocupa una región del
espacio de trabajo , y tiene una percepción del parcial mundo y
sujeta a errores propios del sistema de percepción del robot. A partir de se puede
120
inferir una descripción de los obstáculos (modelo del mundo local ). El
objetivo es computar la acción de control de modo que la trayectoria generada
sea libre de colisiones con los obstáculos y que haga al
objetivo progresar11 a la posición objetivo:
.
6.3.1. Componentes en un Sistema de Evitación de Obstáculos
Un sistema de evitación de obstáculos está compuesto de dos módulos principales: El
módulo de evitación de obstáculos y el módulo de actualización del mundo. El primero
obtiene las medidas de los sensores para crear un modelo de mundo local, el segundo
utiliza esta información para enviar las directivas de navegación al controlador (ver Figura
46). Esta arquitectura desacoplada permite estudiar y combinar por separado distintas
técnicas. Sin embargo, no se debe olvidar que la construcción y actualización de es
una parte esencial en la evitación de obstáculos. Aunque la mayoría de los métodos se
desacoplan de este problema y asumen que está disponible y actualizado con la
representación conveniente. Distintos del mundo pueden ser construidos con distintos
costes computacionales. Por ejemplo una representación geométrica de requiere
un tratamiento de la información original del sensor. Por el contrario una representación
Point Cloud puede obtenerse de manera directa de algunos sensores (lasers, escáneres 3D,
etc.). La representación utilizada para influye de manera directa en la calidad de los
resultados del método de evitación de obstáculos. El apartado 6.6 -Modelado y
actualización del mundo trata con mayor profundidad este asunto.
Evitación de Obstáculos
Modelo del mundo local
Controlador
Sistema y Mundo
Actualizador del mundo
Sensores
Nivel Deliverativo
Nivel Reactivo
Evitación de Obstáculos
Figura 46. Arquitectura típica de un sistema de evitación de obstáculos. El módulo de construcción del
mundo es habitualmente ignorado en la mayoría de los métodos. Muchos métodos de evitación de
obstáculos presentan una clara distinción entre los niveles deliberativos y reactivos (híbridos). Otros carecen
del nivel deliberativo (reactivos). En Por lo general la salida del sistema es un comando de navegación
dirigido al módulo de control.
11 El concepto de distancia en esta definición puede ser interpretado en términos relajados ya que puede significar distancia espacial o distancia temporal teniendo en cuenta las capacidades cinemáticas del WMR, el comportamiento dinámico del mundo, etc.
121
6.3.2. Limitaciones en la Evitación de Obstáculos
La incompletitud y la suboptimalidad son dos características inherentes a todos los
métodos de evitación de obstáculos inherente dado que la percepción local del mundo no
es completa y está sujeta a errores, es decir a su visión local y limitada del mundo. Esto es
conocido como el problema de los mínimos locales o situaciones de bloqueo (Trap
Situations). Teniendo claro esta incompletitud y suboptimalidad inherente, distintos
grados de completitud definiciones más relajadas son posibles bajo. Algunos métodos
deliberativos se presentan como completos y óptimos. En cualquier caso, esta dicotomía
entre completitud e ineficiencia (planificación global) y la incompletitud, suboptimalidad y
eficiencia en la evitación de obstáculos sugiere la integración de ambos enfoques. Algunos
ejemplos se encuentran en (Brock O. , 2000) y (Kelly A. , 1994). Se trata más en
profundidad este asunto en (apartado 6.8 Integración de Evitación de Obstáculos con
Planificación y Control)
En cualquier caso, cada método de evitación de obstáculos tiene sus propias limitaciones.
No existe un método perfecto. No obstante, en general las ideas exitosas (como el concepto
de ventana dinámica en DWA) de técnicas previas son reutilizadas en técnicas posteriores.
La calidad de la trayectoria generada también varía según el método. Los métodos
reactivos presentan por lo general peores resultados que los deliberativos. Algunos
efectos presentados por estos son: movimientos oscilatorios, problemas para atravesar
pasillos, giros bruscos en cruces, etc. Por otra parte, los métodos deliberativos son más
complejos y requieren más recursos computacionales.
Los métodos de evitación de obstáculos son también sensibles a la incertidumbre a la
localización (Igual que las técnicas de control de posición o pose) dado que pierden la
referencia del objetivo. Sin embargo son capaces de cumplir su cometido incluso en
condiciones de incertidumbre. Los resultados pueden ser muy buenos reaccionar de
manera robusta incluso con incertidumbre en la localización.
Terminología
El término “evitación de colisiones” (Collision Avoidance) se utiliza indistintamente de
“evitación de obstáculos” Obstacle Avoidance). Otro termino típico es “planificación local”
(Local Planning). En este trabajo evitaremos utilizar este término12 porque la planificación
terminológicamente hablando supone un proceso deliberativo, mientras que algunos
métodos de evitación de obstáculos son reactivos.
Algunas referencias se refieren a los métodos reactivos como “puerly local approaches”
evitando la palabra “Planning” (Ulrich & Borenstein, 2000), (Brock & Khatib, 1999), (Chou
& Lian, 2009), (Likhachev & Ferguson, 2009). Los métodos de evitación de obstáculos
reactivos son también referidos en la bibliografía como “SENSE /ACT methods” por
ejemplo en (Thrun, Burgard, & Fox, 2005) y (Maja & Michaud, 2008).
Términos como “Sensor-Based Motion Planning” “Local Planning” o “Real-time Motion
Planning” suelen ser aplicados a “Técnicas de Evitación de Obstáculos Híbridas” este será el
12 Además se trata de una sobrecarga del térmno ya que en la jerga de la planificación de
movimiento basado en muestras, el planificador local es un compoenente que chequea la
conectividad entre dos configuraciones en los métodos basados en muestras.
122
término que se utilizará para hacer referencia sea ellos siguiendo la terminología definida
en (Arkin R. , 1989). Otro termino bastante utilizado es “Tactical Planning Systems”
(Minguez, Lamiraux, & Laumond, 2008), (Kelly A. , 1994). Toda esta terminología se
justifica por las claras influencias de técnicas de planificación. En el presente trabajo. El
término híbrido es utilizado en mucha parte de la bibliografía (Konolige K. , 2000) y (Maja
& Michaud, 2008). También son conocidos como técnicas SENSE/PLAN/ACT Concurrently
(Arkin R. C., 1998), (Thrun, Burgard, & Fox, 2005) y (Maja & Michaud, 2008). También en
ocasiones es habitual denominar a los métodos de evitación de obstáculos como goal-
driven methods.
6.3.3. Evitación de Obstáculos Reactiva
Son los métodos de evitación de obstáculos más rápidos. Se trata de una metáfora
importada de la biología de forma que el control del robot se caracterizada por una
relación estímulo sensorial-respuesta inmediata (Arkin R. , 1990). El sistema reacciona a la
información sensorial recibida y descrita a bajo nivel recibida en tiempo real sin realizar
ningún razonamiento deliberativo complejo. Implementaciones tempranas en los años 80
se conseguían ya velocidades superiores a 10Hz. Esta marca ha quedado como referencia
hasta la actualidad y todos los métodos de evitación de obstáculos deben estar
aproximados o mejorarla13. La información sensorial puede ser tratada de forma sencilla
modelando rapidamente14. Deben ser extremadamente rápidos por lo que no
analizan las posibles consecuencias de las respuestas que se van a realizar (no son
métodos deliberativos). Habitualmente los métodos presentan un diseño sencillo y fácil de
implementar, sin embargo, se espera de ellos un comportamiento emergente complejo que
solución el problema de la navegación (Brooks, 1991).
Varias técnicas notables son estudiadas en el (apartado 6.4 - Métodos Reactivos de
Evitación de Obstáculos)
Más de una decena de métodos han sido estudiados entre ellos muy populares técnicas
como PFM, VHF, DWA, VM, ND y TR. A continuación se describen algunos de los aspectos
que caracterizan a cada método y posteriormente se realizará una descripción más
detallada de cada uno de ellos.
Métodos reactivos para robots holónomos
Los primeros métodos reactivos se centraban en robots manipuladores en espacios de
configuración . Estos métodos podían ser fácilmente extendidos al espacio de
configuración de los robots moviles de los robots móviles holónomos o
directamente al espacio de trabajo de tipo . Ejemplos de estos métodos reactivos
son, VFF, VHF. A pesar de que los métodos sucesivos se centraron en solucionar el
problema de la dinámica (DWA, CVM, LCM, Schlegel) nuevos métodos para robots
holónomos han aparecido en la última década como ND y ORM gracias a la aparición del
concepto EK-Space.
13 Para robots que se mueven a la velocidad del ser humano. Aplicaciones más avanzadas como vehículos muy rápidos o con una dinámica compleja requieren velocidades superiores. 14 Ver mas en el apartado 6.6 Modelado y actualización del mundo.
123
Métodos reactivos para WMRs - Trabajando en el espacio de curvatura
Varios métodos reactivos (CVM, Schlegel, EK-Space) en la función curvatura. Esta función
define dada una configuración una distancia al obstáculo mas
cercano para cada curvatura. Esta distancia considera el modelo cinematico que describe
trayectorias circulares típico en los WMRs no-holónomos (ver Capítulo 3 - Modelos de
movimiento en WMRs no-holónomos). Entonces, estos métodos construyen de una forma
más o menos explícita un histograma de curvaturas donde para cada curvatura se define
una distancia hasta el obstáculo más cercano. El método EK-Space propone una forma
desacoplada de considerar la cinemática de WMRs no-holónomos mediante la
transformación de de modo que el problema puede ser resuelto por mecanismos de
evitación de obstáculos holónomos como VFF o VHF. Todos estos métodos tienen principal
ventaja que calculan de manera analítica la distancia al obstáculo más cercano para
cualquier comando de navegación u. Su principal limitación es que el modelo del mundo
generado ignora posibles trayectorias no circulares para distancias no diferenciales
(recordemos que la trayectoria circular era un modelo adecuado para trayectorias en un
tiempo diferencial).
Métodos reactivos para WMRs - Discretizando el espacio de acción
Una de las técnicas más utilizadas para considerar la cinemática en los métodos de
evitación de obstáculos es realizar una búsqueda en el espacio de acción discretizado .
Cada comando es evaluado según ciertos criterios y la opción más favorable es
elegida. El método DWA fue pionero en esta técnica y diferentes técnicas reactivas (CVM,
LCM, VHF+, TR) y cognitivas (GDWA, VHF*, Stachniss, rDWA, ASL, DWA*) lo han importado.
Forma del robot
La mayoría de métodos considera que el robot es de tipo puntual. Este enfoque es en
ocasiones limitado. Por ejemplo en VFF y VHF. Métodos posteriores consideran una
aproximación en la que el robot presente forma circular (CVM, LCM, VHF+). Estos métodos
calculan las intersecciones entre el robot y los obstáculos por lo que realizan asunciones
sobre la representación de . Otros métodos como DWA se desacoplan de este
problema mediante el uso de la función CLEARANCE. No haciendo ningún tipo de asunción
sobre el tipo de representación de o la forma del robot y haciendo uso de
herramientas indirectas para la gestión de obstáculos (ver apartado 2.4- Herramientas
para gestionar mundos con obstáculos).
Una interesante alternativa permite a técnicas que solo consideran robots puntuales
considerar la forma del robot. Se trata del inflado de obstáculos con el radio máximo del
robot. Esta técnica puede ser aplicable para representaciones sencillas de como:
nube de puntos (Point Cloud) o grid de ocupación (Ocupanccy Grid).
Algunos métodos como Schelgel o rDWA especifican de manera explícita el método de
chequeo de colisiones (en lugar de desacoplarse) teniendo en cuenta de manera explícita
la forma del robot a la hora de estimar posibles colisiones. Ambas estrategias asumen que
se representa mediante una nube de puntos (Point Cloud). Este enfoque les permite
construir trayectorias circulares y realizar intersecciones con cada segmento que describe
la forma del robot.
124
Limitaciones
La navegación reactiva puede ser vista como una forma restrictiva de navegación muy
especializada para una tarea específica concreta pero carece de la capacidad de adaptación
para proveer una navegación verdaderamente general y versátil dado que los análisis
deliberativos no son contemplados. (Arkin R. , 1990)
Al ser métodos puramente reactivos, tienen como ventaja de estos enfoques es la
eficiencia aplicable a tiempo real, pero son subóptimas y mínimos locales (Stachniss &
Burgard, 2002). La suboptimalidad es una norma general en todos los métodos de
evitación de obstáculos pero es especialmente problemática y recurrente en los métodos
reactivos. La falta de un análisis deliberativo sobre las consecuencias de las acciones
realizadas (look-ahead) desemboca de forma frecuente en estas situaciones indeseadas.
Por otra parte, la calidad de la trayectoria generada no es siempre la más adecuada y
efectos no deseados como oscilaciones y cambios brucos de dirección pueden producirse.
Los primeros métodos reactivos sufrían más de este tipo de efectos y aunque posteriores
métodos han atenuado estos efectos siguen estando presentes en muchas situaciones. Un
ejemplo destacado es el giro en un cruce con pasillos estrechos o puertas accediendo
desde una dirección tangencial a alta velocidad. Casi todos los métodos reactivos
reaccionan realizando un giro violento al localizarse en las cercanías del pasillo (ver
Figura 47). Otra limitación importante es la incapacidad de realizar tareas complejas que
requieran múltiples movimientos correlacionados como el aparcamiento de un coche
(Likhachev & Ferguson, 2009). Los métodos híbridos surgen como mejora de los métodos
reactivos para superar estas situaciones.
Figura 47. Stachniss vs DWA. Decelerar lentamente es importante especialmente al girar en cruces estrechos. La
mayoría de métodos reactivos presentan un comportamiento mejorable en este ejemplo. (Stachniss & Burgard,
2002)
Por lo tanto, a pesar de sus aportaciones no son soluciones completas al problema en la
mayoría de las aplicaciones prácticas y el uso de los métodos reactivos puros de forma
aislada está en desuso. Las técnicas híbridas (estudiadas a continuación) consiguen
mejores resultados gracias a la realización de procesos deliberativos avanzados. En
cualquier caso todos los enfoques híbridos tienen un nivel reactivo en el cual importan
ideas de estos métodos o utilizan uno de ellos de manera directa de forma desacoplada
(PMP, Gradient Method). Por lo tanto el estudio de las técnicas reactivas es de un alto
interés.
169
CAPÍTULO 7 ARQUITECTURAS SOFTWARE
PARA ROBÓTICA DISTRIBUIDA
7.1. INTRODUCCIÓN
La asistencia en la navegación de WMRs en entornos inteligentes es un area en la cual el
paradigma de Sistemas Multi-Agente (MAS) puede resultar muy útil. Los sistemas multi-
agente son aplicables en distintas áreas de la robótica: Robots colaborativos en equipo,
redes de sensores basadas en robot móviles y robots en ambientes inteligentes son solo
algunos ejemplos. Sin embargo, el desarrollo de Multi-Agent Robotics System (MARS)
sigue presentando hoy en día retos importantes. En la última década han aparecido un
elevado número de Robotics Software Frameworks (RSF) proponiendo algunas soluciones
a los problemas más recurrentes de la robótica. Algunos de ellos como ROS, YARP, OROCOS,
ORCA, Open-RTM y Open-RDK poseen ciertas características y ofrecen la infraestructura
básica necesaria para el desarrollo de MARS.
Historia
Los sistemas robóticos industriales de finales del siglo pasado estaban orientados a la
producción en serie de productos en fábricas, donde robots de alta precisión estaban
destinados al trabajo individual repetitivo en entornos controlados. Sin embargo, la
tendencia actual apunta a sistemas robóticos que deben ser capaces de resolver
problemas en entornos más complejos y menos controlados. Para ello se necesitan
sistemas robóticos más autónomos e inteligentes.
Algunos de estos sistemas son robots móviles en equipo donde un conjunto de robots
trabajan en grupo para lograr un objetivo común (Merino, Caballero, Martíneznez de Dios,
Ferruz, & Ollero, 2006). Estos sistemas requieren robots sociales, colaborativos; se
mueven en entornos complejos, dinámicos. Entonces la capacidad de entender e
interpretar el mundo que les rodea es su principal reto28. Como consecuencia, la
complejidad de la arquitectura software aumenta y las necesidades computacionales se
disparan. En estas arquitecturas software, la escalabilidad, la reusabilidad y la tolerancia a
errores toman una importancia fundamental.
Arquitectura software en la robótica distribuida
La arquitectura software del sistema debe ser diseñada de forma distribuida y modular.
No obstante estos sistemas deben seguir teniendo en cuenta problemas clásicos de la
28 A lo largo de este trabajo nos referiremos a ellos como sistemas robóticos complejos.
170
robótica industrial como las restricciones tiempo real en sus niveles inferiores, más
cercanos a sensores y actuadores. A continuación se enumeran las características
principales que debe cumplir la arquitectura software (y sus componentes) de un sistema
robótico complejo (Orebäck & Christensen, 2003), (Fitzpatrick, Metta, & Natale, 2008),
(Farinelli, Grisetti, & Iocchi, 2006)
Arquitectura concurrente y distribuida. Es necesario poder aprovechar todas
las unidades de procesamiento disponibles de manera concurrentes
(procesadores, multi-procesadores y microcontroladores) para cubrir todas las
necesidades computacionales que presenta un sistema robótico complejo. Dada la
la complejidad del sistema se necesita un mecanismo de inspección remota. Este
trabajo se centra en WMRs en entornos inteligentes, y en este caso el
procesamiento es totalmente distribuido.
Modularidad. La arquitectura software está formada por distintos componentes
altamente cohesionados y con bajo acoplamiento. Los componentes interactúan
entre ellos, sin embargo, las dependencias deben ser minimizadas para obtener
una arquitectura mantenible, flexible, reusable y con capacidad de adaptarse a
cambios y mejoras.
Tolerancia a errores. La disfunción de un componente no debe bloquear el
sistema por completo. Por el contrario, el resto del sistema debe ser capaz de
seguir funcionando en la medida de lo posible con los recursos que dispone
siempre y cuando se acerque a la consecusión de los objetivos. Para ello, el resto de
componentes (aún en correcto funcionamiento) deben ser capaces de actuar con
iniciativa propia tomando autónomamente decisiones para superar estas
situaciones. Estas decisiones pueden haber sido tomadas basándose en
colaboración con otros agentes del sistema o en la información local que poseen.
Tiempo Real. La mayoría de sistemas robóticos tienen algún tipo de restricciones
en tiempo real habitualmente relacionado con control de tareas. Estas
restricciones son problemáticas en arquitecturas software distribuidas. Por lo
tanto el diseño de la arquitectura debe considerar el uso de software, hardware y
protocolos de comunicaciones que garanticen el cumplimiento de estas
restricciones.
Sistemas multi-agente
En el contexto de los MAS, un agente es un componente software proactivo y social
(Bellifemine, Caire, & Greenwood, 2007). Los agentes son autónomos, poseen su propio
flujo de ejecución y son independientes de otros procesos. Los agentes pueden ser
reactivos pero también son proactivos. Además de responder a otros mensajes o eventos
externos, los agentes pueden tomar la iniciativa eventualmente y cambiar su
comportamiento para alcanzar sus objetivos. Por lo tanto, dada las características antes
mencionadas, una solución basada en el paradigma MAS es muy adecuada para el diseño
de un sistema robótico complejo. La arquitectura software del sistema robótico estaría
entonces formada por nodos distribuidos (Agents) que se comunican y colaboran para
lograr los objetivos globales. Es por ello que los sistemas robóticos multi-agente (MARS)
han sido ampliamente estudiados durante los últimos años y existen eventos relacionados
como competiciones como RoboCup y workshops como ICINCO-MARS.
171
En este capítulo se enumerarán y analizarán algunas tecnologías que facilitan el desarrollo
de arquitecturas software de MARS. Se explicarán las características comunes más
importantes prestando especial atención a aquellas que debe incluir a robotics framework
para que se adapte al paradigma MAS. En este capítulo también se presentará un estudio
comparativo que puede servir de referencia para la elección de alguna de estas tecnologías
en un proyecto real. Finalmente se expondrán algunas interpretaciones sobre las
características más importantes y las carencias de estas tecnologías.
La estructura del capítulo
En el primer apartado se expone los campos de aplicación de los sistemas multi-agentes en
la robótica (MARS). En el tercer apartado se define qué es un Robotics Software
Framework (RSF) y algunas de sus características. Posteriormente se describe de forma
breve cada framework, prestando especial atención a los criterios de comparación. Por
último se realizará la interpretación de la comparativa repasando los puntos en común y
las carencias de los frameworks expuestos.
7.2. SISTEMAS MULTI-AGENTE EN LA ROBÓTICA
Los MAS están compuestos de múltiples agentes distribuidos en distintas agencias de una
red. Son sociales, es decir, necesitan interactuar entre ellos para lograr un objetivo global
del sistema. Forman arquitecturas peer to peer y se comunican mediante mensajes. Son
adecuados para desarrollar sistemas distribuidos complejos y heterogéneos donde los
agentes requieren a low coupling level. Son útiles en contextos donde diseñar una solución
del problema por un único agente es complejo. Los MAS una aproximación divide y
vencerás donde la solución de un problema complejo puede lograrse a través de la
solución de problemas más sencillos.
Una arquitectura software para sistemas robóticos está compuesta por componentes de
distinta granularidad, estos componentes pueden ser considerados como agentes en
ciertas circunstancias.
Componentes de granularidad fina
Los components de grano-fino suelen tener una tarea y comportamiento muy definido por
lo que son muy cohesivos. Son habitualmente modelados mediante herramientas
matemáticas como: funciones, reglas o tablas de verdad. Estos componentes típicamente
no cumplen la definición de agente. Un ejemplo puede ser un algoritmo localizado en un
microcontrolador y que controle el servomotor de un brazo robótico, o un componente
que realice un procesado específico a una imagen que viene de una cámara.
Componentes de granularidad media
Por otra parte los componentes de granularidad media están compuestos de varios
subcomponentes y pueden presentar un comportamiento más complejo y en ocasiones no
se puede modelar. Este componente de granularidad media puede cumplir la definición de
agente cuando implementan algún grado de autonomía, sociabilidad e inteligencia.
Componentes de granularidad gruesa
Los componentes de grano-grueso en un sistema robótico complejo suele cumplir la
definición de agente. Un ejemplo claro es un robot móvil autónomo que puede ser
considerado un agente. A su vez, este robot puede estar formado de múltiples agentes de
granularidad media que colaboran creando un pequeño MARS y forman en conjunto la
172
personalidad del robot. También múltiples robots autónomos pueden colaborar creando
un MARS a un nivel de abstracción superior. A continuación se describen algunas áreas y
ejemplos en la robótica donde los MARS son aplicados:
7.2.1. Aplicaciones
A continuación se exponen algunas de las áreas de aplicación donde un sistema robótico se
considera que está dentro del paradigma Multi-Agente.
Sistemas Heterogéneos de Robots en Equipos
Un equipo de robots móviles con diferentes capacidades colaboran para solucionar un
problema. Los miembros del equipo intercambian información y evalúan las decisiones a
tomar. Se han realizado diversas investigaciones al respecto, por ejemplo un equipo de
robots aéreos anti-incendio donde cada uno de ellos posee distintas capacidades
sensoriales y locomotoras complementarias. Los robots colaboran para detectar incendios
en bosques. Cuando uno de ellos localiza un indicio de incendio avisa al resto y deciden
mediante percepción cooperativa si se trata finalmente de un incendio o de una falsa
alarma.
Robots trabajando en ambientes inteligentes
Robots móviles se comunican con elementos de inteligencia ambiental para obtener una
información más detallada de su entorno y poder tomar decisiones basadas en la
información contrastada. Por ejemplo existen proyectos donde robots colaboran con el
ambiente para solucionar problemas cotidianos en las tareas del hogar. También en la
asistencia para discapacitados, assistive or shared control wheelchairs pueden colaborar
con un edificio inteligente y decidir la ruta óptima para llegar a algún lugar de interés.
Enjambres de Robots
Gran número de robots homogéneos colaboran, para que de forma emergente se logren
objetivos comunes más complejos. No es necesario que los robots estén identificados dado
que no poseen características especiales. Los robots colaboran con otros robots cercanos y
actúan basándose primordialmente en la información local de que disponen y la de los
individuos que les rodean. Son sistemas escalables y redundantes; un único robot es
prescindible y completamente intercambiable. Estos sistemas pueden ser capaces de
resolver problemas relacionados con la exploración, vigilancia, path planning, creación de
Adhoc wireless networks de alta cobertura, etc.
Redes de Sensores móviles
Un conjunto de robots móviles con sensores permiten crear una red de sensores de
estructura flexible. Como consecuencia permiten relocalizar los sensores para aumentar la
cobertura de sensado u otra característica, focalizar la atención en un área, o apoyar a otro
individuo que presente un comportamiento defectuoso
7.3. ROBOTICS SOFTWARE FRAMEWORKS
En el año 2009 solo en SourceForge exístian más de 500 proyectos de software libre
relacionadas con. Algunos ejemplos de estos proyectos implementan: Drivers para
dispositivos y sensores robóticos, middleware de comunicaciones, simuladores y
herramientas de modelado de sistemas dinámicos. Algunos de ellos intentan proveer de
una solución integral a través de un conjunto genérico de herramientas y librerías off-the-
181
II. CONCLUSIONES Y TRABAJO FUTURO
En este trabajo se ha realizado un estudio transversal de las distintas áreas implicadas en
la navegación de WMRs no-holónomos: los modelos de movimiento, la localización de
robots, la planificación de movimiento y la evitación de obstáculos. Diferentes
aportaciones e ideas se han expuesto en el ámbito de la navegación de WMRs no-
holónomos en entornos inteligentes con cámaras, entre ellas: guías sobre como
implementar un sistema de localización, la construcción del modelo de percepción o la
construcción de un mapa del mundo distribuido en dos niveles: topológico y métrico.
La navegación de WMRs tiene más de 40 años de historia y se encuentra en un estado de
madurez elevado. Diversos WMRs comerciales empiezan a aparecer: Un ejemplo son los
vehículos con capacidad de aparcamiento lateral automático. En el ámbito de la
investigación actual, el reto es la introducción de WMRs no-holónomos en entornos
urbanos dinámicos y densamente poblados. Otros vehículos en movimiento y obstáculos
desconocidos añaden incertidumbre al problema y ciertas partes del problema deben ser
reformuladas.
Por otro lado, aunque existen investigaciones sobre cómo abordar el problema de la
asistencia en la navegación de WMRs no-holónomos en entornos inteligente la mayoría de
ellas tratan ideas conceptuales. Existen pocas técnicas específicas que puedan ser
fácilmente reproducibles o que estudien aspectos concretos basados en resultados
experimentales. Por esto se propone como trabajo futuro desarrollar y estudiar en
profundidad distintas técnicas de control compartido en ambientes inteligentes que
tengan en cuenta aspectos como: la latencia en las comunicaciones, la fusión de
información de múltiples cámaras, el procesamiento distribuido, el modelo del mundo
distribuido. Etc. Se han señalado aquellas técnicas específicas que pueden ser de especial
utilidad como base en la asistencia en la navegación en entornos inteligentes:
Técnicas de planificación de movimiento como SRT o PRM que utilizan el concepto de
roadmap presenta interesantes características para ser utilizado en entornos inteligentes.
En el ámbito de la localización, técnicas como los filtros de partículas pueden ser
adaptados de manera sencilla para estimar el estado de un robot desde un entorno
inteligente. Es interesante el estudio de cómo diversas cámaras con distintas estimaciones
en la medida pueden ser integradas para lograr una localización más robusta. Sistemas
con múltiples cámaras pueden ser extremadamente robustos haciendo uso de técnicas de
aprendizaje en el modelo de percepción.
Los modelos de movimiento probabilísticos son de especial interés en entornos
inteligentes con cámaras donde la latencia en las comunicaciones puede implicar una
degradación en la estimación del estado del robot. Es necesario llevar un seguimiento de la
certeza que se tiene en el estado del robot, no solo cual es el estado más probable.
182
Por otra parte, las técnicas de evitación de obstáculos reactivas pueden ser utilizadas para
construir técnicas de control compartido en modo semi-operado en ambientes
inteligentes. Es importante estudiar el efecto de las latencias en la efectividad del control
compartido. Los métodos híbridos presentan alternativas muy interesantes para
implementar mecanismos de control compartido de un mayor nivel de abstracción donde
la posición objetivo esté disponible.
183
III. BIBLIOGRAFÍA
Abascal, J., Bonail, B., Casas, R., Marco, \., Sevillano, J., & Cascado, D. (2009). Towards an
intelligent and supportive environment for people with physical or cognitive restrictions.
(págs. 1-8). ACM.
Abascal, J., Sevillano, J. L., Civit, A., Jiménez, G., & Falcó, J. (s.f.). Integration of
heterogeneous networks to support the application of Ambient Intelligence in assistive
environments. Science And Technology .
Amato, N., Bayazit, O., Dale, L., Jones, C., & Vallejo, D. (1998). OBPRM: An obstacle-based
PRM for 3D workspaces. : 1998 Workshop on .
Ando, N., Suehiro, T., & Kotoku, T. (2008). Software Platform for Component Based RT-
System Development: OpenRTM-Aist. Software Platform for Component Based RT-System
Development: OpenRTM-Aist , 87-98.
Arkin, R. C. (1998). Behavior-Based Robotics (Intelligent Robotics and Autonomous Agents).
The MIT Press.
Arkin, R. (1990). Integrating behavioral, perceptual, and world knowledge in reactive
navigation. Robotics and autonomous systems , 6, 105-122.
Arkin, R. (1989). Towards the unification of navigational planning and reactive control.
Arras, K., Persson, J., Tomatis, N., & Siegwart, R. (2002). Real-time obstacle avoidance for
polygonal robots with a reduced dynamic window. Proceedings 2002 IEEE International
Conference on Robotics and Automation (Cat. No.02CH37292) , 3050-3055.
Barraquand, J., & Latombe, J. C. (1993). Nonholonomic multibody mobile robots:
Controllability and motion planning in the presence of obstacles. Algorithmica , 10, 121-
155.
Barraquand, J., & Latombe, J.-C. (1989). On nonholonomic mobile robots and optimal
maneuvering. Proceedings. IEEE International Symposium on Intelligent Control 1989 , 340-
347.
Barraquand, J., Kavraki, L., Latombe, J.-C., Motwani, R., Li, T.-Y., & Raghavan, P. (1997). A
Random Sampling Scheme for Path Planning. The International Journal of Robotics
Research , 16, 759-774.
Barraquand, J., Langlois, B., & Latombe, J. (1992). Numerical potential field techniques for
robot path planning. Systems, Man and Cybernetics, IEEE Transactions on , 22, 224-241.
Bellifemine, F. L., Caire, G., & Greenwood, D. (2007). Developing multi-agent systems with
JADE. John Wiley and Sons.
184
Bellifemine, F., Caire, G., Greenwood, D., & Others. (2001). Developing multi-agent systems
with JADE (Vol. 978). Springer.
Bellifemine, F., Caire, G., Poggi, a., & Rimassa, G. (2008). JADE: A software framework for
developing multi-agent applications. Lessons learned. Information and Software
Technology , 50, 10-21.
Bessiere, P., Ahuactzin, J.-M., Talbi, E.-G., & Mazer, E. (1993). The "ariadne's clew"
algorithm: global planning with local methods. Proceedings of 1993 IEEE/RSJ International
Conference on Intelligent Robots and Systems (IROS '93) , 1373-1380.
Blanco, J. L. (2009). Contributions to Localization, Mapping and Navigation in Mobile
Robotics. Robotics .
Blanco, J. (2010). The Mobile Robot Programming Toolkit. Obtenido de
http://www.mrpt.org/
Blanco, J.-l., Gonzalez, J., & Fernandez-Madrigal, J.-a. (2006). The Trajectory Parameter
Space (TP-Space): A New Space Representation for Non-Holonomic Mobile Robot Reactive
Navigation. (págs. 1195-1200). Ieee.
Bohlin, R., & Kavraki, L. (2000). Path planning using lazy PRM. 1, págs. 521-528. IEEE;
1999.
Borenstein, J., & Koren, Y. (1988). High-speed obstacle avoidance for mobile robots. (págs.
382-384). IEEE.
Borenstein, J., & Koren, Y. (1989). Real-time obstacle avoidance for fast mobile robots.
IEEE Transactions on Systems, Man, and Cybernetics , 19, 1179-1187.
Borenstein, J., & Koren, Y. (1990). Real-time obstacle avoidance for fast mobile robots in
cluttered environments. Proceedings., IEEE International Conference on Robotics and
Automation , 572-577.
Borenstein, J., Everett, H., & Feng, L. (1996). Where am I? Sensors and methods for mobile
robot positioning. University of Michigan , 119, 120.
Borenstein, J., Koren, Y., & Arbor, A. (1991). The vector field histogram - fast obstacle
avoidance for mobile robots. IEEE Journal of Robotics and Automation , 7, 278-288.
Bradski, G., & Kaehler, A. (2008). Learning OpenCV (Vol. 16). (M. Loukides, Ed.) O'Reilly.
Brock, O. (2000). Generating robot motion: the integration of planning and execution.
Stanford University Stanford, CA, USA.
Brock, O., & Khatib, O. (1999). High-speed navigation using the global dynamic window
approach. Proceedings 1999 IEEE International Conference on Robotics and Automation
(Cat. No.99CH36288C) , 341-346.
Brock, O., & Khatib, O. (1999). High-speed navigation using the global dynamic window
approach. Proceedings 1999 IEEE International Conference on Robotics and Automation
(Cat. No.99CH36288C) , 341-346.
185
Brock, O., & Khatib, O. (1999). Real-time obstacle avoidance and motion coordination in a
multi-robot workcell. (págs. 274-279). IEEE.
Broggi, A., Zelinsky, A., Parent, M., & Thorpe, C. E. (2008). Intelligent Vehicles. En B.
Siciliano, & O. Khatib (Edits.), Springer Handbook of Robotics (págs. 1175-1198). Springer
Berlin Heidelberg.
Brooks, R. A. (1991). Intelligence without representation.
Bruemmer, D., Few, D., Boring, R., Marble, J., Walton, M., & Nielsen, C. (2005). Shared
Understanding for Collaborative Control. IEEE Transactions on Systems, Man, and
Cybernetics - Part A: Systems and Humans , 35, 494-504.
Bruyninckx H. & ‘‘. 00 . Open robot control software: The OROCOS project. ’’ in Proc.
IEEE Int. Conf. Robotics and Automation, Seoul, Korea, May , 3pp2523--2528.
Burgard, W., Derr, A., Fox, D., & Cremers, A. (1998). Integrating global position estimation
and position tracking for mobile robots: the Dynamic Markov Localization approach. 2,
págs. 730-735. IEEE.
Burgard, W., Derr, A., Fox, D., & Cremers, A. (1998). Integrating global position estimation
and position tracking for mobile robots: the Dynamic Markov Localization approach. 2,
págs. 730-735. IEEE.
Burgard, W., Fox, D., Hennig, D., & Schmidt, T. (1996). Estimating the Absolute Position of a
Mobile Robot Using Position Probability Grids. Artificial Intelligence .
Cagigas Muñiz, D. (2001). Un sistema eficiente de planificación de trayectorias en entornos
cerrados grandes para robots movieles y sistemas agvs (automated guided vehicles).
Universidad del País Vasco.
Calisi, D., Censi, A., Iocchi, L., & Nardi, D. (2008). OpenRDK: a modular framework for
robotic software development., (págs. 1872-1877).
Campion, G., & Chung, W. (2008). Wheeled Robots. En B. Siciliano, & O. Khatib (Edits.),
Springer Handbook of Robotics (págs. 391-410). Springer Berlin Heidelberg.
Cañas, J., Gómez, V., Barrera, P., & Matellán, V. (2007). Jdec: arquitectura basada en
esquemas para aplicaciones robóticas. gsyc.es .
Canny, J. (1988). The complexity of robot motion planning. MIT Press.
Canny, J., & Reif, J. (1987). New lower bound techniques for robot motion planning
problems. 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) , 49-60.
Cassandra, a., Kaelbling, L., & Kurien, J. (1996). Acting under uncertainty: discrete Bayesian
models for mobile-robot navigation. Proceedings of IEEE/RSJ International Conference on
Intelligent Robots and Systems. IROS '96 , 963-972.
Censi, A. (2008). An ICP variant using a point-to-line metric. 2008 IEEE International
Conference on Robotics and Automation , 19-25.
186
Choset, H. M., Lynch, K. M., Hutchinson, S., Cantor, G., Burgard, W., Kavraki, L. E., y otros.
(2005). Principles of robot motion: theory, algorithms, and implementation. MIT Press.
Chou, C., & Lian, F. (2009). Velocity space approach with region analysis and look-ahead
verification for robot navigation. (págs. 5971-5976). IEEE.
Civit Balcells, A., Díaz del Río, F., Sevillano, J., & Jiménez, G. (1996). SIRIUS: A Low Cost High
Performance Computerized Wheelchair. Proc. of the Int. Workshop on Medical Robots, Pág.
23-30. Vienna. October 1996 , 9.
Collett, T., MacDonald, B., & Gerkey, B. (2005). Player 2.0: Toward a practical robot
programming framework. Citeseer.
Conner, D., Rizzi, a., & Choset, H. (2003). Composition of local potential functions for global
robot control and navigation. Proceedings 2003 IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS 2003) (Cat. No.03CH37453) , 3546-3551.
Cooper, R. (1995). Intelligent control of power wheelchairs. Engineering in Medicine and
Biology Magazine, .
Cox, I. J. (1990). Autonomous Robot Vehicles (Vol. 84(8)). (I. J. Cox, & G. T. Wilfong, Edits.)
Springer.
del, F. {., Jimenez, G., Sevillano, J., Vicente, S., & Balcells}, a. {. (1999). A generalization of
path following for mobile robots. Proceedings 1999 IEEE International Conference on
Robotics and Automation (Cat. No.99CH36288C) , 7-12.
Dellaert, F., Fox, D., Burgard, W., & Thrun, S. (2001). Robust Monte Carlo localization for
mobile robots. Proceedings 1999 IEEE International Conference on Robotics and
Automation (Cat. No.99CH36288C) , 1322-1328.
Dial, R. (1969). Algorithm 360: Shortest-path forest with topological ordering [H].
Communications of the ACM , 12, 632-633.
Diankov, R., Openrave, J. K., & A. (2008). planning architecture for autonomous robotics.
Technical report, Robotics Institute, Carnegie Mellon University, July , --34.
Díaz del Río, F. (1997). Análisis y evaluación del control de un robot móvil: aplicación a sillas
de ruedas eléctricas.
Díaz, S. V. (2001). Una Aportación al Guiado de Sillas de Ruedas Eléctricas en Entornos
Estructurados.
Donald, B. R. (1988). A geometric approach to error detection and recovery for robot
motion planning with uncertainty. Artificial Intelligence , 37, 223-271.
Donald, B., Xavier, P., Canny, J., & Reif, J. (1993). Kinodynamic motion planning. Journal of
the ACM , 40, 1048-1066.
Durrant-Whyte, H. F., & Henderson, T. C. (2008). Multi-Sensor Data Fussion. En Springer
Handbook of Robotics (págs. 585-610).
187
Elfes, A. (1989). Using occupancy grids for mobile robot perception and navigation.
Computer , 22, 46-57.
Enderle, S., Utz, H., Sablatn, S., Simon, S., & Kraetzschmar, G. (s.f.). MIRO: Middleware for
autonomous mobile robots.
Farinelli, A., Grisetti, G., & Iocchi, L. (2006). Design and implementation of modular
software for programming mobile robots. International Journal of Advanced Robotic , 3, 37-
42.
Feiten, W., Bauer, R., & Lawitzky, G. (1994). Robust obstacle avoidance in unknown and
cramped environments. Proceedings of the 1994 IEEE International Conference on Robotics
and Automation , 2412-2417.
Ferguson D. & Stentz A. 007 . Field D•: An interpolation-based path planner and
replanner. Robotics Research , 239-253.
Ferguson, D., Darms, M., Urmson, C., & Kolski, S. (2008). Detection, prediction, and
avoidance of dynamic obstacles in urban environments. 2008 IEEE Intelligent Vehicles
Symposium , 1149-1154.
Ferguson, D., Howard, T. M., & Likhachev, M. (2008). Motion planning in urban
environments. Journal of Field Robotics , 25, 939-960.
Ferguson, M., & Webb, N. (2011). An intelligent low-cost scanning range finder. (págs. 168-
172). IEEE.
Fernández, I., Mazo, M., Lázaro, J. L., Pizarro, D., Santiso, E., Martín, P., y otros. (2007).
Guidance of a mobile robot using an array of static cameras located in the environment.
Autonomous Robots , 23, 305-324.
Fiorini, P., & Shiller, Z. (1998). Motion planning in dynamic environments using velocity
obstacles. The International Journal of Robotics Research , 17, 760.
Fitzpatrick, P., Metta, G., & Natale, L. (2008). Towards long-lived robot genes. Robotics and
Autonomous Systems , 56, 29-45.
Fong, T. (1999). Collaborative Control: A Robot-Centric Model for Vehicle Teleoperation .
Symposium: Agents with Adjustable Autonomy .
Fong, T. (1999). Collaborative Control: A Robot-Centric Model for Vehicle Teleoperation .
Symposium: Agents with Adjustable Autonomy .
Fong, T., Thorpe, C., & Baur, C. (2002). Robot as partner: Vehicle teleoperation with
collaborative control. Multi-Robot Systems: From Swarms to Intelligent Automata , 1, 423-
431.
Fox, D., Burgard, W., & Thrun, S. (1997). The dynamic window approach to collision
avoidance. Robotics \& Automation Magazine, IEEE , 4, 23-33.
Fox, D., Burgard, W., Dellaert, F., & Thrun, S. (1999). Monte Carlo Localization: Efficient
Position Estimation for Mobile Robots Dieter Fox, Wolfram Burgard. Artificial Intelligence .
188
Fox, D., Burgard, W., Kruppa, H., & Thrun, S. (1999). A Monte Carlo Algorithm for Multi-
Robot Localization.
Fox, D., Burgard, W., Thrun, S., & Cremers, a. (1998). A hybrid collision avoidance method
for mobile robots. Proceedings. 1998 IEEE International Conference on Robotics and
Automation (Cat. No.98CH36146) , 1238-1243.
Fox, D., Burgard, W., Thrun, S., & Cremers, A. B. (1996). Position Estimation for Mobile
Robots in Dynamic Environments. Artificial Intelligence .
Fox, D., Burgard, W., Thrun, S., & Cremers, A. B. (1996). Position Estimation for Mobile
Robots in Dynamic Environments. Artificial Intelligence .
Fraichard, T., & Asama, H. (2004). Inevitable collision states — a step towards safer
robots? Advanced Robotics , 18, 1001-1024.
Fraichard, T., & Scheuer, a. (1994). Car-like robots and moving obstacles. Proceedings of
the 1994 IEEE International Conference on Robotics and Automation , 64-69.
Fulgenzi, C., Spalanzani, A., & Laugier, C. (2007). Dynamic Obstacle Avoidance in uncertain
environment combining PVOs and Occupancy Grid. Proceedings 2007 IEEE International
Conference on Robotics and Automation , 1610-1616.
Fulgenzi, C., Tay, C., Spalanzani, A., & Laugier, C. (2008). Probabilistic navigation in
dynamic environment using Rapidly-exploring Random Trees and Gaussian processes.
2008 IEEE/RSJ International Conference on Intelligent Robots and Systems , 1056-1062.
Galluppi, F., Urdiales, C., Poncela, a., Sanchez-Tato, I., Sandoval, F., & Belardinelli, M. O.
(2008). A Study on Human Performance in a Cooperative Local Navigation Robotic System.
2008 IEEE 17th Workshop on Enabling Technologies: Infrastructure for Collaborative
Enterprises , 1, 48-53.
Ge, S., & Cui, Y. (2002). Dynamic motion planning for mobile robots using potential field
method. Autonomous Robots , 13, 207-222.
Gerkey, B., & Konolige, K. (2008). Planning and control in unstructured terrain.
Glasius, R. (1995). Neural Network Dynamics for Path Planning and Obstacle Avoidance.
Neural Networks , 8, 125-133.
Gonz\'{a}lez-Banos, H., Hsu, D., & Latombe, J. (2006). Motion planning: Recent
developments. Autonomous Mobile Robots: Sensing, Control, Decision-Making and
Applications , 1-50.
Gordon, N., Salmond, D., & Smith, A. (1993). Novel approach to nonlinear/non-Gaussian
Bayesian state estimation. 140, págs. 107-113. IET.
Hoffmann, F. (2001). Evolutionary algorithms for fuzzy control system design. Proceedings
of the IEEE , 89, 1318-1333.
Hollerbach, J. (1983). Dynamic scaling of manipulator trajectories. (págs. 752-756). IEEE.
189
Horswill, I. (1993). Polly: A Vision-Based Arti cial Agent. AAAI'93 Proceedings of the
eleventh national conference on Artificial intelligence .
Howard, T. M., & Kelly, a. (2007). Optimal Rough Terrain Trajectory Generation for
Wheeled Mobile Robots. The International Journal of Robotics Research , 26, 141-166.
Hsu, D., Kindel, R., Latombe, J.-C., & Rock, S. (2002). Randomized Kinodynamic Motion
Planning with Moving Obstacles. The International Journal of Robotics Research , 21, 233-
255.
Hsu, D., Latombe, J., & Motwani, R. (1999). Path planning in expansive configuration
spaces. International Journal of .
Isard, M. (1998). Condensation—conditional density propagation for visual tracking.
International journal of computer vision , 29, 5-28.
Jarvis, R. A. (1985). Collision-free trajectory planning using distance transforms.
Transactions of the Institution of Engineers, Australia. Mechanical engineering , 10, 187-191.
Jarvis, R. (2004). Distance Transform Based Visibility Measures for Covert Path Planning in
Known but Dynamic Environments. Autonomous Robots , 396-400.
Jiménez, P., Thomas, F., & Torras, C. (1998). Collision detection algorithms for motion
planning. Robot motion planning and control .
Kalman, R., & Others. (1960). A new approach to linear filtering and prediction problems.
Journal of basic Engineering , 82, 35-45.
Kavarki, L. E., Halperin, D., & Latombe, J.-C. (s.f.). Robotics.
Kavraki, L. E. (1994). Random Networks in Configuration Space for Fast Path Planning.
Kavraki, L., Svestka, P., Latombe, & Overmars, M. (1996). Probabilistic roadmaps for path
planning in high-dimensional configuration spaces. on Robotics and .
Kelly, A. (1994). An Intelligent Predictive Controller for Autonomous Vehicles. Engineering
.
Kelly, A. (1995). An intelligent, predictive control approach to the high-speed cross-country
autonomous navigation problem. Citeseer.
Kelly, a. (2006). Toward Reliable Off Road Autonomous Vehicles Operating in Challenging
Environments. The International Journal of Robotics Research , 25, 449-483.
Kelly, a., & Nagy, B. (2003). Reactive nonholonomic trajectory generation via parametric
optimal control. The International Journal of Robotics Research , 22, 583.
Khatib, M., & Chatila, R. (1995). An extended potential field approach for mobile robot
sensor-based motions.
190
Khatib, M., Jaouni, H., Chatila, R., & Laumond, J. (1997). Dynamic path modification for car-
like nonholonomic mobile robots. Proceedings of International Conference on Robotics and
Automation , 2920-2925.
Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The
international journal of robotics research , 5, 90.
Kim, J.-O., & Khosla, P. (1991). Real-time obstacle avoidance using harmonic potential
functions. Proceedings. 1991 IEEE International Conference on Robotics and Automation ,
790-796.
Kimmel, R., Kiryati, N., & Bruckstein, a. (1998). Multivalued distance maps for motion
planning on surfaces with moving obstacles. IEEE Transactions on Robotics and
Automation , 14, 427-436.
Kindel, R., Hsu, D., Latombe, J.-C., & Rock, S. (2000). Kinodynamic motion planning amidst
moving obstacles. Proceedings 2000 ICRA. Millennium Conference. IEEE International
Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) , 537-
543.
Kirkpatrick, S., Gelatt, C., & Vecchi, M. (1983). Optimization by simulated annealing. science
, 220, 671.
Kluge, B., & Prassler, E. (2004). Reflective navigation: individual behaviors and group
behaviors. IEEE International Conference on Robotics and Automation, 2004. Proceedings.
ICRA '04. 2004 , 4172--4177 Vol.4.
Knepper, R., & Kelly, A. (2006). High Performance State Lattice Planning Using Heuristic
Look-Up Tables. 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems ,
3375-3380.
Ko, N., & Simmons, R. (1998). The lane-curvature method for local obstacle avoidance.
Intelligent Robots and Systems, 1998. Proceedings., 1998 IEEE/RSJ International Conference
on , 3, 1615-1621.
Koditschek, D., & Rimon, E. (1990). Robot navigation functions on manifolds with
boundary• . Advances in Applied Mathematics , 11, 412-442.
Koenig, S., & Likhachev, M. (2002). Improved fast replanning for robot navigation in
unknown terrain. Proceedings 2002 IEEE International Conference on Robotics and
Automation (Cat. No.02CH37292) , 968-975.
Konolige, K. (2000). A gradient method for realtime robot control. Proceedings. 2000
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2000) (Cat.
No.00CH37113) , 639-646.
Konolige, K., Agrawal, M., Bolles, R. C., Cowan, C., Fischler, M., & Gerkey, B. (2008). Outdoor
Mapping and Navigation using Stereo Vision. Artificial Intelligence .
191
Koren, Y., & Borenstein, J. (1991). Potential field methods and their inherent limitations for
mobile robot navigation. Proceedings. 1991 IEEE International Conference on Robotics and
Automation , 1398-1404.
Krogh, B. (1984). A generalized potential field approach to obstacle avoidance control.
Krogh, B., & Thorpe. (1986). Integrated path planning and dynamic steering control for
autonomous vehicles. Robotics and Automation. Proceedings. , 1664-1669.
Kuffner, J., & LaValle, S. (2000). RRT-connect: An efficient approach to single-query path
planning. Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on
Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) , 995-1001.
Lamiraux, F., Bonnafous, D., & Lefebvre, O. (2004). Reactive Path Deformation for
Nonholonomic Mobile Robots. IEEE Transactions on Robotics , 20, 967-977.
Latombe, J. (1990). Robot motion planning. Springer Verlag.
Latombe, J.-C. (1991). A reactive architecture for planning and executing robot motions
with incomplete knowledge. Proceedings IROS '91:IEEE/RSJ International Workshop on
Intelligent Robots and Systems '91 , 24-29.
Laumond, J.-P. (1986). Feasible Trajectories for Mobile Robots with Kinematic and
Environment Constraints. 346-354.
Laumond, J.-P., Jacobs, P., Taix, M., & Murray, R. (1994). A motion planner for
nonholonomic mobile robots. IEEE Transactions on Robotics and Automation , 10, 577-593.
Laumond, J., Sekhavat, S., & Lamiraux, F. (1998). Guidelines in nonholonomic motion
planning for mobile robots. Robot motion planning and control , 1-53.
LaValle, S. M. (2001). Algorithms for Computing Numerical Optimal Feedback Motion
Strategies.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
LaValle, S. M., & Kavraky, L. E. (2009). Motion planning. Springer Handbook of Robotics .
LaValle, S. (1998). Rapidly-Exploring Random Trees: A New Tool for Path Planning.
LaValle, S., & Kuffner, J. (1999). Randomized kinodynamic planning. Proceedings 1999 IEEE
International Conference on Robotics and Automation (Cat. No.99CH36288C) , 473-479.
Levine, S. P., Bell, D. a., Jaros, L. a., Simpson, R. C., Koren, Y., & Borenstein, J. (1999). The
NavChair Assistive Wheelchair Navigation System. IEEE transactions on rehabilitation
engineering : a publication of the IEEE Engineering in Medicine and Biology Society , 7, 443-
51.
Likhachev, M., & Ferguson, D. (2009). Planning Long Dynamically Feasible Maneuvers for
Autonomous Vehicles. The International Journal of Robotics Research , 28, 933-945.
192
Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., & Thrun, S. (2005). Anytime Dynamic A*:
An Anytime, Replanning Algorithm. Proceedings of the International Conference on
Automated Planning and Scheduling (ICAPS) .
Likhachev, M., Gordon, G., & Thrun, S. (2004). ARA*: Anytime A* with Provable Bounds on
Sub-Optimality. Science .
Lindemann, S., & LaValle, S. (2005). Smoothly Blending Vector Fields for Global Robot
Navigation. Proceedings of the 44th IEEE Conference on Decision and Control , 3553-3559.
Lozano-Perez, T. (1983). Spatial planning: A configuration space approach. IEEE
transactions on computers , 100, 108-120.
Maja, J. M., & Michaud, F. (2008). Behavior-Based Systems. En Springer Handbook o
Robotics (pág. 891\~{}909).
Makarenko, A., Brooks, A., & Kaupp, T. (s.f.). Orca : Components for Robotics. 1-25.
McKay, N. (1985). Minimum-time control of robotic manipulators with geometric path
constraints. IEEE Transactions on Automatic Control , 30, 531-541.
Merino, L. (2007). Cooperative Perception Techniques for Multiple Unmanned Aerial
Vehicles: Applications to the Cooperative Detection, Localization and Monitoring of Forest
Fires. Education .
Merino, L., Caballero, F., Martíneznez de Dios, J., Ferruz, J., & Ollero, A. (2006). A
cooperative perception system for multiple UAVs: Application to automatic detection of
forest fires. Journal of Field Robotics , 23, 165-184.
Minguez, J., & Montano, L. (2008). Extending reactive collision avoidance methods to
consider any vehicle shape and the kinematics and dynamic constraints. IEEE Transactions
on Robotics , 1-13.
Minguez, J., & Montano, L. (2004). Nearness Diagram (ND) Navigation: Collision Avoidance
in Troublesome Scenarios. IEEE Transactions on Robotics and Automation , 20, 45-59.
Minguez, J., & Montano, L. (2000). Nearness diagram navigation (ND): a new real time
collision avoidance approach. 3, págs. 2094-2100. Ieee.
Minguez, J., & Montano, L. (2003). The ego-kinodynamic space: collision avoidance for any
shape mobile robots with kinematic and dynamic constraints. Proceedings 2003 IEEE/RSJ
International Conference on Intelligent Robots and Systems (IROS 2003) (Cat.
No.03CH37453) , 637-643.
Minguez, J., Lamiraux, F., & Laumond, J.-P. (2008). Motion Planning and Obstacle
Avoidance. En B. Siciliano, & O. Khatib (Edits.), Springer Handbook of Robotics (págs. 827-
852). Springer Berlin Heidelberg.
Minguez, J., Montano, L., & Santos-Victor, J. (2006). Abstracting Vehicle Shape and
Kinematic Constraints from Obstacle Avoidance Methods. Autonomous Robots , 20, 43-59.
193
Montemerlo, M., Roy, N., & Thrun, S. (s.f.). Perspectives on standardization in mobile robot
progranuning : the carnegie mellon navigation (carmen) toolkit. Proceedings 2003
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) (Cat.
No.03CH37453) , 2436-2441.
Montesano, L., Minguez, J., & Montano, L. (2006). Lessons learned in integration for sensor-
based robot navigation systems. International Journal of Advanced Robotic Systems , 3, 85-
91.
Montesano, L., Minguez, J., & Montano, L. (2008). Modeling dynamic scenarios for local
sensor-based motion planning. Autonomous Robots , 25, 231-251.
Moravec, H. A., & Elfes, A. (1985). The Robotics High resolution maps from wide angle
sonar.
Moravec, H. (1985). Certainty Grids for Mobile Robots.
Moreno-Noguer, F., Sanfeliu, A., & Samaras, D. (2008). Dependent multiple cue integration
for robust tracking. IEEE transactions on pattern analysis and machine intelligence , 30,
670-85.
Morin, P., & Samson, C. (2008). Motion Control of Wheeled Mobile Robots. En B. Siciliano,
& O. Khatib (Edits.), Springer Handbook of Robotics (págs. 799-826). Springer Berlin
Heidelberg.
Nilsson, N. J. (1969). A Mobile Automation: an Application of Artificial Intelligence
Techniques, Preliminary Draft Submitted to the International Joint Conference on Artificial
Intelligence, May 1969. Artificial Intelligence , 1969, 7-9.
Nistér, D., Naroditsky, O., & Bergen, J. (2006). Visual odometry for ground vehicle
applications. Journal of Field Robotics , 23, 3-20.
Nourbakhsh, I., Powers, R., & Birchfield, S. (1995). DERVISH An Office-Navigating Robot. AI
Magazine , 16, 53-60.
O'DÙNLAING, C., & YAP, C. K. (1982). A retraction method for planning the motion of a
disc. Journal of algorithms , 6, 104-111.
Ogren, P., & Leonard, N. (2005). A convergent dynamic window approach to obstacle
avoidance. IEEE Transactions on Robotics , 21, 188-195.
Orebäck, A., & Christensen, H. I. (2003). Evaluation of architectures for mobile robotics.
Autonomous Robots, Vol. , 14pp, 33-49.
Owen, E., & Montano, L. (2006). A Robocentric Motion Planner for Dynamic Environments
Using the Velocity Space. 2006 IEEE/RSJ International Conference on Intelligent Robots and
Systems , 4368-4374.
Petti, S., & Fraichard, T. (2005). Safe motion planning in dynamic environments. (págs.
2210-2215). IEEE.
194
Philippsen, R., & Siegwart, R. (2003). Smooth and efficient obstacle avoidance for a tour
guide robot. 2003 IEEE International Conference on Robotics and Automation (Cat.
No.03CH37422) , 446-451.
Pivtoraiko, M., & Kelly, A. (2006). Constrained motion planning in discrete state spaces.
(págs. 269-280). Springer.
Pivtoraiko, M., & Kelly, A. (2008). Differentially constrained motion replanning using state
lattices with graduated fidelity. 2008 IEEE/RSJ International Conference on Intelligent
Robots and Systems , 2611-2616.
Pivtoraiko, M., & Kelly, A. (2005). Generating near minimal spanning control sets for
constrained motion planning in discrete state spaces. (págs. 3231-3237). Ieee.
Pivtoraiko, M., Knepper, R., & Kelly, A. (2007). Optimal, smooth, nonholonomic mobile
robot motion planning in state lattices. Robotics Institute, Carnegie Mellon University,
Pittsburgh, PA, Tech. Rep. CMU-RI-TR-07-15 .
Plaku, E. (2009). Algorithms for Sensor-based Robotics.
Plaku, E., Bekris, K., Chen, B., Ladd, a., & Kavraki, L. (2005). Sampling-based roadmap of
trees for parallel motion planning. IEEE Transactions on Robotics , 21, 597-608.
Quigley, M., Gerkey, B., Conley, K., Faust, J., Foote, T., Leibs, J., y otros. (2009). ROS: an open-
source Robot Operating System.
Quinlan, S. (1994). Real-time modification of collision-free paths. Stanford University.
Quinlan, S., & Khatib, O. (1993). Elastic bands: connecting path planning and control.
[1993] Proceedings IEEE International Conference on Robotics and Automation , 802-807.
Rebai, K., Azouaoui, O., & Ouadah, N. (2009). Bi-steerable robot navigation using a
modified Dynamic Window Approach. (págs. 1-6). IEEE.
Reif, J. (1987). Complexity of the Mover';s Problem and Generalization, General
Techniques for Computing Topological Properties of Real Algebraic Manifolds.
Reif, J. H., & Wang, H. (2000). Nonuniform Discretization for Kinodynamic Motion Planning
and its Applications. SIAM Journal on Computing , 30, 161.
Rimon, E., & Koditschek, D. (1992). Exact robot navigation using artificial potential
functions. IEEE Transactions on Robotics and Automation , 8, 501-518.
Rosenfeld, A., & Pfaltz, J. (1966). Sequential operations in digital image processing. Journal
of the ACM , 13, 471-494.
Russell, S., Norvig, P., Canny, J., Malik, J., & Edwards, D. (1995). Artificial intelligence: a
modern approach (Vol. 74). Prentice hall Englewood Cliffs, NJ.
Rusu, R. B., Sucan, I. A., Gerkey, B., Chitta, S., Beetz, M., & Kavraki, L. E. (2009). Real-time
perception-guided motion planning for a personal robot. 2009 IEEE/RSJ International
Conference on Intelligent Robots and Systems , 4245-4252.
195
Saffiotti, a. (1997). The uses of fuzzy logic in autonomous robot navigation. Soft Computing
- A Fusion of Foundations, Methodologies and Applications , 1, 180-197.
Sánchez, G., & Latombe, J. (2003). A single-query bi-directional probabilistic roadmap
planner with lazy collision checking. Robotics Research .
Sanchez, G., & Latombe, J.-C. (2002). On Delaying Collision Checking in PRM Planning:
Application to Multi-Robot Coordination. The International Journal of Robotics Research ,
21, 5-26.
Sanfeliu, A., & Andrade-cetto, J. (s.f.). Ubiquitous Networking Robotics in Urban Settings.
International Journal .
Schlegel, C. (1998). Fast local obstacle avoidance under kinematic and dynamic constraints
for a mobile robot. Proceedings. 1998 IEEE/RSJ International Conference on Intelligent
Robots and Systems. Innovations in Theory, Practice and Applications (Cat. No.98CH36190) ,
594-599.
Schlegel, C. (2004). Navigation and execution for mobile robots in dynamic environments:
An integrated approach.
Schmidt, G., & Azarm, K. Mobile Robot Navigation In A Dynamic World Using An Unsteady
Diffusion Equation Strategy. IEEE.
Schwartz J. T. & Sharir M. 983 . On the “piano movers'” problem I. The case of a two-
dimensional rigid polygonal body moving amidst polygonal barriers. Communications on
Pure and Applied Mathematics , 36, 345-398.
Schwarzer, F., Saha, M., & Latombe, J.-C. (2005). Adaptive dynamic collision checking for
single and multiple articulated robots in complex environments. IEEE Transactions on
Robotics , 21, 338-353.
Seder, M., & Petrovic, I. (2007). Dynamic window based approach to mobile robot motion
control in the presence of moving obstacles. Proceedings 2007 IEEE International
Conference on Robotics and Automation , 1986-1991.
Sekhavat, S., Svestka, P., Laumond, J.-P., & Overmars, M. (1997). Multi-level path planning
for nonholonomic robots using semi-holonomic subsystems., 17, págs. 79-96.
Seraji, H., & Howard, a. (2002). Behavior-based robot navigation on challenging terrain: A
fuzzy logic approach. IEEE Transactions on Robotics and Automation , 18, 308-321.
Sevillano, J., Civit, A., Díaz del Río, F., & Jiménez, G. (1997). A Proposal For A Low Cost
Advanced Wheelchair Architecture. The 4th European Conference for the Advancement
Technology. AAATE Conference 1997. October 1997. Thessaloniki. Grecia.
Sevillano, J., Falc\'{o}, J., Abascal, J., Civit-Balcells, A., Jim\'{e}nez, G., Vicente, S., y otros.
(2004). On the design of ambient intelligent systems in the context of assistive
technologies. Computers Helping People with Special Needs , 625-625.
196
Shadden, S., Marsden, J., & Olfati-Saber, R. (2003). Collision avoidance for multiple agent
systems. 42nd IEEE International Conference on Decision and Control (IEEE Cat.
No.03CH37475) , 539-543.
Sharir, M. (1997). Algorithmic Motion Planning.
Shiller, Z., Large, F., & Sekhavat, S. (2001). Motion planning in dynamic environments:
obstacles moving along arbitrary trajectories. Proceedings 2001 ICRA. IEEE International
Conference on Robotics and Automation (Cat. No.01CH37164) , 3716-3721.
Shkel, a., & Lumelsky, V. (1997). Incorporating body dynamics into sensor-based motion
planning: the maximum turn strategy. IEEE Transactions on Robotics and Automation , 13,
873-880.
Siciliano, B., & Khatib, O. (2008). Springer Handbook of Robotics. (B. Siciliano, & O. Khatib,
Edits.) Springer.
Siegwart, R., & Nourbakhsh, I. R. (2004). Introduction to autonomous mobile robots. MIT
Press.
Simmons, R. (1996). The Curvature-Velocity Method for Local Obstacle Avoidance The
Curvature-Velocity Method. Work .
Simmons, R., & Koenig, S. (1995). Probabilistic robot navigation in partially observable
environments. 14, págs. 1080-1087. Citeseer.
Soetens, P. (2006). Orocos Open Robot Control Software. Technology .
Stachniss, C., & Burgard, W. (2002). An integrated approach to goal-directed obstacle
avoidance under dynamic constraints for dynamic environments. 1, págs. 508-513. Ieee.
Stentz, A. (1995). The Focussed D* Algorithm for Real-Time Replanning. Compare A
Journal Of Comparative Education .
Svestka, P. (1994). Motion planning for carlike robots using a probabilistic learning
approach. The International Journal of Robotics .
Thorpe, C. (1984). Path relaxation: Path planning for a mobile robot. (págs. 576-581).
IEEE.
Thrun, S., & Leonard, J. J. (2008). Simultaneous Localization And Mapping. En Springer
Handbook of Robotics (págs. 871-889).
Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic robotics. MIT Press.
Thrun, S., Montemerlo, M., Dahlkamp, H., Stavens, D., Aron, A., Diebel, J., y otros. (2007).
Stanley: The robot that won the DARPA Grand Challenge. The 2005 DARPA Grand Challenge
, 23, 1-43.
Tilove, R. (1990). Local obstacle avoidance for mobile robots based on the method of
artificial potentials. Proceedings., IEEE International Conference on Robotics and
Automation , 566-571.
197
Ulrich, I., & Borenstein, J. (2000). VFH*: local obstacle avoidance with look-ahead
verification. Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference
on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) , 2505-2511.
Ulrich, I., & Borenstein, J. (1998). VFH+: reliable obstacle avoidance for fast mobile robots.
Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat.
No.98CH36146) , 1572-1577.
Urmson, C., Anhalt, J., Bagnell, D., Baker, C., Bittner, R., Clark, M. N., y otros. (2008).
Autonomous driving in urban environments: Boss and the Urban Challenge. Journal of
Field Robotics , 25, 425-466.
Urmson, C., Anhalt, J., Bagnell, D., Baker, C., Bittner, R., Clark, M. N., y otros. (2008). General
Motors Research and Development Warren, Michigan 48090. Journal of Field Robotics , 25,
425-466.
Wang, M., & Liu, J. (2008). Fuzzy logic-based real-time robot navigation in unknown
environment with dead ends. Robotics and Autonomous Systems , 56, 625-643.
Yang, L., & Lavalle, S. (2004). The sampling-based neighborhood graph: An approach to
computing and executing feedback motion strategies. Robotics and Automation, IEEE
Transactions on , 20, 419-432.
Ye, C., Yung, N. C., & Wang, D. (2003). A fuzzy controller with supervised learning assisted
reinforcement learning algorithm for obstacle avoidance. IEEE transactions on systems,
man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and
Cybernetics Society , 33, 17-27.
Yen, J., & Pfluger, N. (1995). A fuzzy logic based extension to Payton and Rosenblatt's
command fusion method for mobile robot navigation. Systems, Man and Cybernetics, IEEE
Transactions on , 25, 971-978.
Yershova, A., & LaValle, S. M. (2007). Improving Motion-Planning Algorithms by Efficient
Nearest-Neighbor Searching. IEEE Transactions on Robotics , 23, 151-157.
Zhang, H., Dou, L., Fang, H., & Chen, J. (2009). Autonomous indoor exploration of mobile
robots based on door-guidance and improved dynamic window approach. 2009 IEEE
International Conference on Robotics and Biomimetics (ROBIO) , 408-413.
Zhou, R., & Hansen, E. A. (2002). Multiple Sequence Alignment Using Anytime A^*.
Proceedings of the National Conference on Artificial , 975-976.
197
Ulrich, I., & Borenstein, J. (2000). VFH*: local obstacle avoidance with look-ahead
verification. Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference
on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) , 2505-2511.
Ulrich, I., & Borenstein, J. (1998). VFH+: reliable obstacle avoidance for fast mobile robots.
Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat.
No.98CH36146) , 1572-1577.
Urmson, C., Anhalt, J., Bagnell, D., Baker, C., Bittner, R., Clark, M. N., y otros. (2008).
Autonomous driving in urban environments: Boss and the Urban Challenge. Journal of
Field Robotics , 25, 425-466.
Urmson, C., Anhalt, J., Bagnell, D., Baker, C., Bittner, R., Clark, M. N., y otros. (2008). General
Motors Research and Development Warren, Michigan 48090. Journal of Field Robotics , 25,
425-466.
Wang, M., & Liu, J. (2008). Fuzzy logic-based real-time robot navigation in unknown
environment with dead ends. Robotics and Autonomous Systems , 56, 625-643.
Yang, L., & Lavalle, S. (2004). The sampling-based neighborhood graph: An approach to
computing and executing feedback motion strategies. Robotics and Automation, IEEE
Transactions on , 20, 419-432.
Ye, C., Yung, N. C., & Wang, D. (2003). A fuzzy controller with supervised learning assisted
reinforcement learning algorithm for obstacle avoidance. IEEE transactions on systems,
man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and
Cybernetics Society , 33, 17-27.
Yen, J., & Pfluger, N. (1995). A fuzzy logic based extension to Payton and Rosenblatt's
command fusion method for mobile robot navigation. Systems, Man and Cybernetics, IEEE
Transactions on , 25, 971-978.
Yershova, A., & LaValle, S. M. (2007). Improving Motion-Planning Algorithms by Efficient
Nearest-Neighbor Searching. IEEE Transactions on Robotics , 23, 151-157.
Zhang, H., Dou, L., Fang, H., & Chen, J. (2009). Autonomous indoor exploration of mobile
robots based on door-guidance and improved dynamic window approach. 2009 IEEE
International Conference on Robotics and Biomimetics (ROBIO) , 408-413.
Zhou, R., & Hansen, E. A. (2002). Multiple Sequence Alignment Using Anytime A^*.
Proceedings of the National Conference on Artificial , 975-976.