Click here to load reader
Upload
luis-alfredo-moctezuma
View
113
Download
0
Embed Size (px)
Citation preview
Navegación con robots móviles
FCC BUAP
4/16/2016 1Planeación de rutas
Introducción,I
• La navegación, es la metodología que permite guiar el curso de un robot movil a través de un ambiente con obstáculos
4/16/2016 Planeación de rutas 2
Trayectoria
• Secuencia de configuraciones de un robot desde una configuración inicial a una final
• Es continua• Algunos valores de costo se aplican en la ruta
para cambiar la configuración• Por lo general, se prefiere un camino libre de
colisiones con el minimo costo• Problema de obtimizacion y busqueda
4/16/2016 Planeación de rutas 3
Configuración espacial
• Es el conjunto de todas las configuraciones posibles del robot
• Es el número mínimo de parametros necesarios para especificar completamente la configuración del objeto
4/16/2016 Planeación de rutas 4
Algoritmos tipo bug
• Eficaces en navegación basada en sensores– Bug 1 <-- Exhaustivo– Bug 2 <-- Heuristica
• Algunos algoritmos de planificación asumen el conocimiento global del medio ambiente– Los algoritmos bug, asumen sólo el conocimiento
local del medio ambiente y un objetivo global
4/16/2016 Planeación de rutas 5
Bug 1,I
1. Apuntar a su objetivo y dirigirse a él
2. Si encuentra un obstáculo, circunnavegar recordando el punto mas cercano que estaba del objetivo
3. Retornar al punto más cercano recordado y continuar apuntando al objetivo
4/16/2016 Planeación de rutas 6
Bug 1,II
InicioMeta
4/16/2016 Planeación de rutas 7
Bug 1,IIIrepetir
navegar de r siguiendo gr= localización actual del robot
hasta que r==g o se encuentre un obstáculo
si r==g terminar, ya se llego a la meta
sea p=r // contacto con el obstáculosea m=r // punto guardado de lo cerca que estaba del objetivo
repetir //Seguir en direccion al objetivo r= localización actual del robotsi la distancia de g a r es menor que la distancia de m a g , actualizar el nuevo punto mas cercano al objetivo: m=r
hasta que r==g o r==Psi r==g
terminar, ya se llego a la metanavegar a m a largo de del obstáculo
si se encuentra un obstáculo al seguir a m en direccion a g // terminar, meta no alcanzable
4/16/2016 Planeación de rutas 8
Bug 1,IV
4/16/2016 Planeación de rutas 9
Bug 2,I
• Apuntar al objetivo y dibujar una linea imaginaria, dirigirse hacia el objetivo
• Si hay un obstáculo en el camino, circunnavegar hasta encontrar la linea imaginaria de nuevo
• Dejar el obstáculo y continuar hacia el objetivo siguiendo la linea imaginaria
4/16/2016 Planeación de rutas 10
Bug 2,II
InicioMeta
4/16/2016 Planeación de rutas 11
Bug 2,IIISea L la linea de r a grepetir
navegar de r en direccion a gr= localizacion actual del robot
hasta que r==g o se encuentre un obstáculo si r==g
terminar, ya se llego a la metasea p=r el contacto con el obstáculorepetir
seguir hasta el limite del obstáculor= localizacion actual del robotsea m la intersección de r y L
hasta que m != null y (la distancia de m a g sea menor que la distancia de p a g) o r= p si r==g
terminar, ya se llego a la metasi r==p
terminar, meta no alcanzable
4/16/2016 Planeación de rutas 12
Bug 2,IV
4/16/2016 Planeación de rutas 13
Comparación• E s u n a l g o r i t m o d e
búsqueda exhaustiva– Examina todas las
opc iones an tes de comprometerse
• B u g 1 t i e n e u n rendimiento global más predecible
• Es un algoritmo voraz– Toma la primera cosa que
ve mejor
• En muchos casos, Bug 2 supera a Bug 1
4/16/2016 Planeación de rutas 14
Otros tipos de algoritmos
• Métodos Wavefront• Planes de trabajo– Descomposición de celdas– Gráficos de visibilidad– etc..
4/16/2016 Planeación de rutas 15
Referencias
• Dr. Carlotta A. Berry,Introduction to Mobile Robotics
4/16/2016 Planeación de rutas 16