algoritmo

CAPÍTULO 4

Algoritmo

La parte más importante de este proyecto es el algoritmo de búsqueda-exploración.
Este algoritmo será el que tome decisiones de los caminos a seguir para poder llegar a una
búsqueda exitosa. Por consiguiente el algoritmo debe estar diseñado de tal forma que
contemple la mayoría de los casos con los que se pueda encontrar para así encontrar la
mejor solución antetales situaciones.

Para este proyecto se necesita un algoritmo que cumpla con las siguientes características:

•

Planear una ruta que cubra de manera rápida la mayor parte del área a explorar.

•

Evitar redundancia en la exploración.

•

Ajustar la ruta planeada ante obstáculos encontrados.

•

Dar una respuesta en un tiempo razonable.

•

Mantener la eficiencia deexploración tanto en áreas pequeñas como en áreas grandes,

guardando la relación de tiempo.

34

Debemos tomar en cuenta que el algoritmo debe ser capaz de trabajar con o sin datos del
área a explorar, ya que en un principio no se tiene ninguna idea del área que se explorará y
se irá generando un mapa conforme se vaya avanzando. La base del algoritmo será la
misma para ambos casos, con pequeñasdiferencias a la hora de considerar la existencia de
obstáculos.

4.1 Planeación de rutas.

Para poder comenzar la búsqueda de un objetivo lo primero que se debe hacer es realizar
una exploración del área tratando de cubrir la mayor parte de la misma, dado que así
podríamos llegar a encontrar el objetivo o cuando menos se tendría una idea aproximada
del área que se está explorando paradespués replantear la ruta de búsqueda pero tomando
en cuenta los obstáculos encontrados.

Con esto tenemos en claro que será necesario crear una ruta de exploración inicial que nos
permita conocer el área de exploración sin detalles exactos pero con detalles suficientes
para, en caso de no poder abarcar toda el área en esta primera búsqueda-exploración inicial,
más adelante poder replantearla.35

Los pasos para llevar a cabo la búsqueda-exploración inicial serán los siguientes:

1)

Lo primero que se hará será dividir el área a explorar en regiones que sean del mismo
tamaño, tal que el robot pueda explorarlas en un tiempo lo suficientemente rápido.

2)

Luego se procederá a explorar cada región, es decir el robot pasará de región en región.
Se asegurará que por lo menoscada región se visite una vez. El paso entre regiones será por
la distancia más corta entre una región y otra tomando en cuenta los nodos intermedios.

3)

Si se encuentra un obstáculo para pasar de una región a otra, se buscará pasar por otro
lado replanteando la exploración y buscando los nodos más cercanos.

4)

Si no se puede pasar a ninguna otra región entonces se hará un“back-tracking” y se
realizará el paso (4) para la región a la que se ha llegado. Se repetirá esta operación hasta
que se exploren todas las regiones o se determine que no existen más regiones a las que sea
posible llegar.

A grandes rasgos ésta será la forma en la que se realizará la búsqueda principal, los detalles
se explicarán más adelante.

A continuación se ilustra la forma en que funcionará elalgoritmo al realizar la planeación
de la búsqueda inicial.

36

Fig. 4.1) División del área en regiones.

Fig. 4.2) Inicio de exploración.

Fig. 4.3) Al no poder seguir la ruta inicial, se busca la manera de continuar la ruta buscando un punto alterno.

37

Fig. 4.4) y 4.5) “Back-tracking” y continuación de la exploración.

4.2 Evitar redundancia.

Para evitar pérdida de tiempobuscando en lugares por los que ya se realizó una exploración
debemos identificar los lugares explorados. Esto se puede realizar gracias a que llevaremos
un mapa guardado de lo que se ha explorado y también se tendrá registrada la ruta que el
robot ha seguido, marcando los nodos que ya han sido visitados. Así mediante este mapa
podremos ver fácilmente que regiones están exploradas y que...