1

Navegación

Seminario de Modelo y MétodosCuantitativos

Teddy Alfaro O.

Que es navegación

• Ciencia o arte de conducir un robot móvil mientrasatraviesa en entorno de tierra, mar, aire, espacioexterior, par alcanzar un destino meta, sin chocarcon ningún obstáculo

• Metodología que permite guiar el curso de unmóvil a través de un entorno

• Arte o ciencia que permite guiar a un robot a suobjetivo, teniendo en cuenta el medio que lo rodea

2

Navegación en robot móviles

• La característica principal de los robot móviles es sumovimiento y su independencia del medio físico

• Tareas– Creación de Mapas– Planificación de Caminos– Conducción

• Percepción Sensorial• Fusión de sensores• Actualización de Mapas• Control de Movimientos• Esquivar Obstáculos

La Navegación de un RobotMóvil

• Un robot móvil requiere de unsistema de navegación– Holonomicidad, independencia del

medio, posición• Esquemas de navegación, se

basan en control– Reactivo– Deliberativo– Híbrido

• Necesidad de modelar el medioAmbiente

3

Esquema Reactivo• Colección de reglas: situaciones-acciones• No necesita representación del ambiente• Limitaciones

– Identificar situaciones en función de los sensores– Problema del arbitraje

Esquema Deliverativo• Esquema Deliberativo• Percibo�Planifico�Actúo• Planificación hacia delante• Se modelan como estados• Problemas

– Tiempo, espacio, información

4

Esquema Local-Global

• Planteado por AT&T, y rediseñado por Michalewicz

• Off-line: planificacióna base de informacióna priori, con ciertogrado de incertidumbre

• On-line: resolución deobstrucciones que sepresenten en el entornolocal. Información delos sensores

Etapas de la Navegación• El problema de la navegación se puede divide

en las siguientes etapas:– Percepción del Mundo: con el uso de los sensores se

crea el modelo de entorno de navegación– Planificación de Rutas: se crea una secuencia ordenada

de objetivos y submetas bajo estrategias– Generador de Caminos: proceso de búsqueda de un

camino válido. CSP, CSOP– Seguimiento de Camino: desplazamiento del vehículo,

según un camino con un adecuado Control

5

Problema de Modelar Ambiente

• El robot móvil debe conocer donde sedesenvuelve para funcionar correctamente

• Necesidad de una representación del espacio de configuraciones de un robot

• Modelo para: identificar espacios libre,obstáculos, reconocer regiones del ambiente, reconocer objetos del ambiente

• Modelo Gran Escala o Modelo Simplificado

Modelar el Medio Ambiente

• La navegación requiere de una adecuadapercepción del mundo

• Limitación Sensorial– Resolución, ruido, costo

• Limitación en los Actuadores– Deslizamiento de ruedas, roce, diferencia de

potencia en los motores• Construcción de un Modelo de Ambiente a

partir de datos incompletos (ambiente real)

6

Filosofías de Modelado deAmbiente

Modelos basados en Mapas• Mapas Geométricos: representan el espacio libre

(obstáculos) por medio de medidas espaciales• Mapas de Descomposición: representan el espacio

libre (obstáculos) por medio de una discretización enceldas

• Mapas Topológicos: el ambiente es una serie delugares y conexiones, se pueden considerar comografos métricos

• Mapas Semánticos: asociación geométrica otopológica a una semántica con el fin de crear unacomunicación más natural hombre-máquina

7

Mapas

Problema de Autolocalización

• Localización: que robot conozca en todomomento su posición y orientación

• Este problema no se presenta en simulaciones, ambientes virtuales, juegos

• En la práctica se debe considerar un robotcomo semi-ciego

• Es requisito esencial para desarrollar robotautónomos

8

Sistemas de Posicionamiento

• Se pueden clasificar en Sistemas dePosicionamiento Absolutos, los Sistemas dePosicionamiento Relativos

• Absolutos: Faros (infrarojos), Cámara modo satélite, GPS

• Relativos: sistemas odométricos, enconders

Posicionamiento Absoluto• Los más utilizados son los GPS, fácil localización• Información satelital para marcar posiciones• Aplicables ambientes abiertos

9

GPS• Sistema de posicionamiento global,

desarrollado en USA• Funciona por medio de 24 satélites que rodean

la tierra 2 veces al día• Se requiere se localizado por lo menos con 3

satélites (proceso de triangulación)• Gran precisión (m o cm)

Triangulación 2D

• Dado– Un lado del triángulo– Dos ángulos

• Se puede determinar– Los otros 2 lados– El angulo restante

10

Posicionamiento Absoluto

• Problemas– Ambientes indoor– Nanomundo o micromundo– Resolución espacial limitada (cobertura)– Nivel de actualización de la información limita

la capacidad de reacción inmediata del robot– Dependientes

Posicionamiento Relativo

• El principal son los Sistemas Odométricos– Odometría mide el desplazamiento usando

encoders incrementales asociados a las ruedasdel robot

– Un sistema odométrico es el mouse track-ball– Rápida obtención de información odométrica– Bajo costo– En general se trabajan con marcas (landmark)

11

Posicionamiento Relativo

• Problemas por Errores Odométricos– La principal desventaja son los

deslizamientos o movimientos inesperados que afectan a los encondersen el conteo (aumento-decremento)

– Requieren el punto de partida (referencia)– Imprecisión en la información entregada

por el sistema sensorial (ruido)– El error odométrico es acumulativo

Técnica PID• Correcciones de acuerdo a tres criterios:

– el Proporcional: basado en la magnitud del error observado– el Integral: para limitar el error acumulado– el Derivado: para controlar las variaciones del error.

∫ ∂∂++=

ttePdttePtePtc DIE)()()()(

)(te

DIE PPP ,,

Función de error

Factores de corrección

12

Odometría en un Móvil

( )

( )

Ltvtvt

ttvtvty

ttvtvtx

id

id

id

)()()(

)(sin2

)()()(

)(cos2

)()()(

−=

+=

+=

θ

θ

θ

&

&

&

Ltvtv

i

d

)()( Velocidad rueda derecha

Velocidad rueda izquierda

Largo del eje entre las ruedas

Modelo Odométrico simplifacdo• Trajectoria=arco de circunferencia

13

Elipse del error estimado

Tipos de Fuentes de ErroresErrores Sistemáticos• Diámetros desiguales en las

ruedas• Diferencia entre el promedio

real del diámetro con eldiámetro nominal

• Diferencia en el largo deleje nominal y el actual

• Deslineamiento en la ruedas• Problemas en la

configuración del enconder– Tasas de refresco– resolución

Errores no-sistemáticos• Pisos desnivelados• Objetos inesperados en el

recorrido• Deslizamiento de ruedas

– Pisos resbaladizos– Sobreacelaración– Patinaje en los giros– Fuerzas externas (interacción)– Fuerza internas (castor wheels)– No-contacto de la rueda con el

piso

14

Planificación de Caminos• Planificación de Rutas para un Robot móvil no holonómico• Dado un ambiente y un conjunto de obstáculos conformado

por objetos, un robot móvil debe navegar desde un punto de inicio a un punto final por medio de un camino libre de obstáculos.

• Planificación: Proceso de búsqueda de un camino válido, entrelos posibles, o de la ruta más corta (CSP o CSOP)

Odometría con Legos

TickdiametroD π*=

500mt, +-2cm

15

Métodos de Planificación

• Los métodos y técnicas se pueden clasificaren:– Planificación Basada en Mapas (centrado en los

obstáculos, 2 fases)– Planificación en Descomposición de Celda

(centrado en los espacios libres, 2 fases)– Metodología de Campos Potenciales

Artificiales

Resolución de 2 fases

• Se basan en las etapas de:– Mapeo (discretización)– Resolución

• La resolución, de acuerdo al “tamaño”, puedeabordada:– Con técnicas Completas (Djkistra,BFS, A-estrella)– Con metaheurísticas (SA, computación evolutiva,

otros)