PDF de programación - Capítulo 2. Análisis de técnicas y algoritmos existentes

Capítulo 2. Análisis de técnicas y algoritmos existentes


2.1 Introducción



Siendo la robótica un campo de estudio nacido años atrás, cuenta hoy en día con un

historial considerable en cuanto a trabajos de investigación, desarrollos y propuestas que en

gran medida sustentan las bases para pruebas de mayor alcance e inclusive nuevas

propuestas o líneas de investigación.

Para la realización del presente trabajo es necesario conocer antes distintos

algoritmos enfocados a tres principales problemas como lo son la planeación de trayectorias

enfocadas a la exploración de un ambiente, la correcta detección de obstáculos y técnicas

para evitar colisiones, así como la determinación de posición y orientación del robot en el

espacio. Para los tres diferentes casos de estudio, existe una variedad de algoritmos por lo

que el primer objetivo es conocer algunos de ellos para poder seleccionar los más

adecuados para el tipo de problema propuesto y entresacar ideas que sirvan a la

implementación del algoritmo para el trabajo presente.

Para hablar de una solución eficiente no debemos olvidar que ésta no solo depende

de la tarea de exploración sino que al mismo tiempo depende de las técnicas para la

adquisición de información y su procesamiento, el método para la identificación de los

objetos en el ambiente y finalmente la representación gráfica del espacio explorado. Por

ello es importante llevar a cabo una revisión de las diferentes técnicas y algoritmos

existentes para finalmente poder elaborar un algoritmo para la resolución del problema y

que mejor se pueda adaptar a las necesidades y características del equipo disponible, ya que

el acercamiento que cada trabajo tiene hacía un mismo problema varía de acuerdo a los

recursos disponibles haciendo que un algoritmo pueda ser mucho mas eficaz con un tipo de

dispositivos que otro.

Los algoritmos difieren uno de otro en aspectos tan simples como que para algunos

el cubrir varias veces un mismo lugar de la zona explorada representa un costo inútil en

tiempo, mientras que bajo otras circunstancias como un ambiente en continuo cambio, estas

repetidas revisiones de un mismo lugar representan una ventaja ya que mantienen

actualizada la información y con ello un conocimiento real del terreno.



20

Para un robot inmerso en un ambiente desconocido, los algoritmos para planeación

de trayectorias no resultan ser tan adecuados para la exploración, pues en general dan por

hecho el conocimiento de la zona sobre la que se va a mover el robot, es decir, los

algoritmos para planeación de trayectorias toman como entrada un mapa sobre el cual debe

navegar el robot y entregan como salida una secuencia de movimientos que se encadenan

como una trayectoria para el robot buscando generalmente llevarlo del punto actual a un

punto diferente definido como meta. Ahora bien, en la robótica muchas veces se trabaja

realizando solamente simulaciones con

los algoritmos propuestos ejecutándolos

exclusivamente en la computadora, sin embargo las cosas son muy diferentes cuando se

pasa de una simulación a un modelo real en el cual las consideraciones deben ampliarse y

se deben dejar de lado los casos ideales asumidos.

Un problema cuando se trabaja con un robot dentro de un espacio real es ocasionado

por los sensores cuando se desea hacer la generación y actualización del mapa de la zona

explorada ya que los sensores son dispositivos muy propensos a ruido y suelen entregar

datos imprecisos y, debido a que los sensores son nuestro medio para de alguna manera

percibir el ambiente en el cual actúa el robot, muchas veces los datos de los sensores

arrojan una apreciación errónea.

Los datos que el robot capta del ambiente a través de sus sensores sirven

obviamente para la navegación, sin embargo también las lecturas de los sensores son

empleadas para estimar la posición del robot en el ambiente, lo que implica entonces que la

determinación precisa de dicha posición sea también un problema implícito, y esto hace

surgir también diferentes técnicas de ubicación para el robot dentro del espacio.

Un primero paso para afrontar el problema de posicionamiento consiste en elegir o

desarrollar una correcta técnica de calibración para los sensores a utilizar en el trabajo ya

que de la precisión en las medidas entregadas dependerá la fiabilidad del mapa que se

construye del espacio explorado.

Desde un inicio se deben definir los parámetros bajo los cuales se va a trabajar, esto

es, si es de interés conocer irregularidades en la superficie del terreno o sencillamente

reconocer y ubicar espacialmente los objetos que se encuentran sobre él. De igual forma,

definir la extensión de la búsqueda o exploración también es importante así como decidir si

durante la exploración tienen mas importancia los detalles que la cantidad de territorio



21

explorado e inclusive es necesario definir el tipo de sensores con los que se cuenta ya que

ello nos da pauta a saber el tipo de información de la que se puede hacer uso.



2.2 Algoritmos para exploración



La definición de exploración varía de un autor a otro, sin embargo podemos tomar

la definición presentada por Zlot diciendo que es la adquisición de información relevante y

alcanzable de un ambiente desconocido o parcialmente conocido [7].

Así como las tareas de exploración pueden tomar diferentes enfoques o mejor dicho,

dentro de la exploración se añaden factores que las hacen diferentes aunque sea en una

mínima parte, también existen muy diferentes algoritmos propuestos para cada una de sus

variaciones a tratar.

Algunos algoritmos, por ejemplo están orientados a resolver el problema de obtener

un punto de encuentro para dos robots que se encuentran explorando un ambiente

totalmente desconocido y parten desde distintos lugares. Otros se basan en buscar que los

robots involucrados siempre puedan verse entre si mientras realizan la exploración, y

finalmente otros sencillamente proponen rutas aleatorias para los robots involucrados.



Por otro lado, una exploración no sería lo suficientemente útil si no se lleva un

registro de lo que se conoce y no se conoce del ambiente, por eso es que otro punto de

interés que va de la mano con los algoritmos de exploración es la generación de mapas.



De manera general, las técnicas que se utilizan para la construcción de mapas se

dividen en dos categorías que son: métricas y topológicas. El primer tipo se basa en una

representación del terreno con una gran cuadricula donde cada celda tiene asignado un

valor que representa su situación en el espacio físico, ya sea que esté ocupada, vacía o aún

esté sin explorar.



Un poco diferentes son los mapas topológicos, los cuales se generan tomando como

puntos de referencia un conjunto de marcas a lo largo y ancho del terreno explorado, donde

tanto la posición del robot como la conexión con las marcas es modelada de acuerdo a

distribuciones de probabilidad. Es evidente que para poder trabajar con esta técnica de

mapas topológicos el terreno debe ser preparado previamente para proveer al robot de las

marcas necesarias para su orientación durante su recorrido por el espacio.



22

El primer algoritmo al que se puede hacer referencia es el que trata el problema de

encontrar un punto de reunión para dos robots inmersos en un ambiente desconocido [8], en

el cual ninguno de los dos robots involucrados conoce la posición inicial del otro, sin

embargo, este método considera dos robots con una memoria propia en la cual cada uno va

guardando la trayectoria de exploración seguida y va creando una especie de mapa local.

Este algoritmo de exploración se interesa en emplear sensores tales como sonar o

dispositivos de visión, además cada robot tiene un comportamiento totalmente autónomo y

una vez que resuelven el problema de elegir un punto de encuentro en el terreno explorado

se sitúan en él para hacer un intercambio de información y fusionar los mapas parciales que

cada uno ha obtenido, de esta manera se espera que en un dado caso que alguno de los

robots no pueda regresar a la base, de cualquier manera se cuente con la mayor cantidad de

información posible, ya que la información obtenida por ese robot que no pudo regresar a la

base fue comunicada a otro robot durante la reunión en el punto establecido por ambos.

La estrategia seguida por este algoritmo se puede fragmentar en los siguientes

pasos: navegar a través del ambiente, encontrar buenas posiciones para un encuentro, elegir

la mejor de las posiciones para realizar la reunión en un tiempo predeterminado para tal

efecto y finalmente desplazarse hasta ese punto de reunión y compartir la información con

el o los otros robots.

Otra propuesta referente a la exploración considera un modelo de tipo "Maestro -

Multiesclavos" [9] en el cual existe un conjunto de pequeños robots cuyo comportamiento

esta inspirado por las colonias de hormigas; trabaja con la finalidad de explorar un

ambiente determinado y grabar los datos obtenidos durante el recorrido para luego regresar

a un control maestro y vaciar la información obtenida por cada uno; así los robots solo

recolectan información y al final el control maestro es el que se encarga de efectuar los

procesos necesarios