COMPARACIÓN DE ESTRATEGIAS DE NAVEGACIÓN UTILIZANDO …
Transcript of COMPARACIÓN DE ESTRATEGIAS DE NAVEGACIÓN UTILIZANDO …
1
COMPARACIÓN DE ESTRATEGIAS DE NAVEGACIÓN UTILIZANDO TEORÍA DE
MULTIAGENTES PARA EL BARRIDO DE ZONAS POSIBLEMENTE MINADAS
CRISTIAN ALEJANDRO IBAGUÉ RAMOS
JORDAN STEVEN PARRA TORRES
UNIVERSIDAD SANTO TOMÁS
FACULTAD DE INGENIERÍA ELECTRÓNICA
BOGOTÁ D.C.
2017
2
COMPARACIÓN DE ESTRATEGIAS DE NAVEGACIÓN UTILIZANDO TEORÍA DE
MULTIAGENTES PARA EL BARRIDO DE ZONAS POSIBLEMENTE MINADAS
CRISTIAN ALEJANDRO IBAGUÉ RAMOS
JORDAN STEVEN PARRA TORRES
TRABAJO DE GRADO PRESENTADO COMO REQUISITO PARCIAL PARA
OPTAR AL TÍTULO DE: INGENIERO ELECTRÓNICO.
DIRECTOR:
(Ing. Electrónico) Carlos Saith Rodríguez Rojas
UNIVERSIDAD SANTO TOMÁS
FACULTAD DE INGENIERÍA ELECTRÓNICA
BOGOTÁ D.C.
2017
3
Dedicatoria y agradecimientos
Queremos agradecer la realización de este proyecto de grado primero que todo a
nuestros padres; Leonel Ibagué, Aleida Ramos, José Parra y Ana Elsy Torres. Que
han sido indispensables, brindándonos amor y un apoyo incondicional para poder
cumplir con nuestras metas. Queremos agradecer a nuestros amigos que han sido
parte fundamental para haber llegado hasta este punto, por último queremos
agradecer a todos los profesores que nos han brindado su sabiduría y su experiencia
para poder realizar este proyecto, en especial a los profesores Carlos Saith Rodríguez
Rojas y al profesor Carlos Andrés Quintero Peña quienes esclarecieron y dejaron al
descubierto su gran capacidad y acierto a la hora de ofrecer sus conocimientos en
pro de los estudiantes.
4
Contenido
Introducción................................................................................................................................ 6
1. Antecedentes ...................................................................................................................... 7
2. Justificación ...................................................................................................................... 11
3. Objetivos ........................................................................................................................... 12
3.1 Objetivo General: .......................................................................................................... 12
3.2 Objetivos Específicos: .................................................................................................. 12
4. Marco Teórico ................................................................................................................... 13
5. Diseño y Ejecución del proyecto ...................................................................................... 18
5.1. Etapa de revisión de estrategias de navegación basadas en Sistemas Multi-agentes
18
5.2. Etapa de Elección de estrategias ................................................................................. 26
5.3. Creación del Campo ..................................................................................................... 27
5.5. Creación del Sensor ..................................................................................................... 30
5.6. Implementación del Algoritmo PSO en Matlab ............................................................ 31
5.7. Implementación del algoritmo BFOA en Matlab........................................................... 33
6. Resultados del Proyecto .................................................................................................. 36
6.1. Elección de estrategias ................................................................................................. 36
6.2. Creación del campo ...................................................................................................... 36
6.3. Implementación de Algoritmos ..................................................................................... 37
6.4. Comparación de estrategias ......................................................................................... 37
7. Impacto Social .................................................................................................................. 40
8. Conclusiones .................................................................................................................... 41
9. Trabajo Futuro .................................................................................................................. 43
10. Bibliografía .................................................................................................................... 44
Anexos ..................................................................................................................................... 46
Anexo A. Simulaciones y resultados de las estrategias Tabla 1 ............................................ 46
Anexo B Simulaciones y resultados de las estrategias Tabla 2 ............................................. 47
Anexo C. Simulaciones y resultados de las estrategias Tabla 3 ............................................ 48
Anexo D. Simulaciones y resultados de las estrategias Tabla 4 ............................................ 49
Anexo E. Simulaciones y resultados de las estrategias Tabla 5 ............................................ 50
Anexo F. Simulaciones y resultados de las estrategias Tabla 6 ............................................ 51
Anexo G. Simulaciones y resultados de las estrategias Tabla 7 ............................................ 52
Anexo H. Simulaciones y resultados de las estrategias Tabla 8 ............................................ 53
Anexo I. Simulaciones y resultados de las estrategias Tabla 9 ............................................. 54
5
Anexo J. Simulaciones y resultados de las estrategias Tabla 10 ........................................... 55
Anexo K. Simulaciones y resultados de las estrategias Tabla 11 .......................................... 56
Anexo L. Simulaciones y resultados de las estrategias Tabla 12 .......................................... 57
Anexo M. Simulaciones y resultados de las estrategias Tabla 13 ......................................... 58
Anexo N. Simulaciones y resultados de las estrategias Tabla 14 .......................................... 59
Anexo O. Simulaciones y resultados de las estrategias Tabla 15 .......................................... 60
Anexo P. Simulaciones y resultados de las estrategias Tabla 16 .......................................... 61
6
Introducción
La navegación de zonas específicas ha sido ampliamente utilizado en la robótica
moderna para aplicaciones como vigilancia, rescate de personas exploración de
zonas de riesgo con técnicas como el path planning [1]. Sin embargo dicha técnica de
navegación ha presentado problemas o limitaciones como lo son el saber el punto de
inicio y el punto objetivo al que se quiere llegar, que trae como consecuencia, la
exploración incompleta de la zona ya que al tener un objetivo ya específico se crea
una ruta directa que se seguirá. Además la complejidad de estos procesos de
navegación usando un solo individuo tiene una complicación alta lo que supone un
tiempo de procesamiento elevado [2]. Dichos factores pueden llegar a ser
determinantes dependiendo de la aplicación que se le dé a esta navegación.
En el ambiente social, una potencial aplicación de la navegación de zonas específicas
es la detección de minas debido a que los dispositivos explosivos (especialmente
minas antipersonales) han provocado mutilaciones en las personas en sus miembros
superiores e inferiores [3].
Para abordar esta problemática depurando los problemas anteriormente
mencionados existen estrategias de navegación usando multi-agentes, debido a que
al usar múltiples entes para recorrer un área determinada se puede llegar a disminuir
el tiempo de ejecución de esta tarea, seccionando o dividiendo los procesos y así
minimizar la complejidad que puede representar el monitoreo del espacio
determinado. Es por eso que se quiere estudiar y comparar dos estrategias de
navegación en ambientes no estructurados a partir de la simulación de agentes
homogéneos, contrastando aspectos tales como tiempo de recorrido, área cubierta
por cada agente, posibles conflictos y tiempo de procesamiento.
7
1. Antecedentes
Las minas antipersonales en Colombia son un problema que se ha dado desde los
últimos 25 años y que han evolucionado a través del tiempo. Al pasar los años y con
el aumento de las problemáticas sociales estas minas han cambiado de materiales y
han aumentado exponencialmente [4]. Con lo anterior, existe la necesidad de crear
mejores estrategias de búsqueda, detección y desactivación de las minas
antipersonales en todas las regiones colombianas, además, de disminuir los posibles
riesgos de accidentes o posibles pérdidas humanas que pueden presentarse. Por lo
tanto, este proyecto busca exponer una solución para la navegación de múltiples
robots en la búsqueda de posibles minas antipersonales. A continuación, se
describirán algunos artículos relacionados con los métodos de navegación, búsqueda
e interacción de múltiples robots utilizando la teoría de los sistemas multi-agentes o
de enjambre, aplicadas a este problema.
Inicialmente, para la navegación de múltiples robots se describe la robótica de
enjambre el cual, es un enfoque reciente para el control y coordinación autónoma de
una colección de robots relativamente sencillos que interactúan localmente con la
toma de decisiones descentralizada y el empleo de algoritmos de comportamiento
inspirados en los principios de optimización practicados por los insectos sociales
como lo describe en Naval [5], entre las ventajas de cooperación de múltiples robots
se encuentran la ejecución simultánea de subtareas, robustez frente a fallos del
sistema, escalabilidad, flexibilidad en la adaptación en un ambiente, reconfiguración
y rentabilidad. En [6] se describe, el potencial del uso del color y la geometría
deducidos del escáner de la distancia y de los sensores de la visión para la
navegación de múltiples robots autónomos. Estos experimentos de simulación
mostraron la validez de varias técnicas desarrolladas para la navegación.
Además, en Marcolino y otros [7] se abordan los métodos de navegación y
coordinación que permiten a los enjambres de robots converger y extenderse a lo
largo de formas 2D complejas en entornos que contienen obstáculos desconocidos.
Las formas se modelan utilizando funciones implícitas y de descenso de gradiente
para controlar el enjambre. Además, que se describe el uso de mecanismos de
coordinación entre robots, los experimentos y las simulaciones reales demuestran la
viabilidad del enfoque propuesto.
Para la navegación de multi-agentes se deben analizar además los métodos de
planificación de trayectorias. Como Shirong y Mao [8] que exponen la planificación de
trayectos desacoplados basado en el algoritmo de la colonia de hormigas, junto a la
navegación distribuida, para la evasión de obstáculos y colisiones para sistemas
multi-robot. En donde proponen un algoritmo de colonia de hormigas mejorado para
8
planificar una trayectoria adoptando una estrategia de comportamiento que es el
"primero que llega tiene el primer servicio". Los resultados de la simulación muestran
que el método propuesto puede mejorar efectivamente el rendimiento de la trayectoria
planificada y que los robots individuales con colisiones pueden lograr alcanzar sus
ubicaciones de objetivos mediante simples estrategias de navegación local.
En Majumder [9] que describe una método de multi-agentes inspirado en abejas y
donde analizan la planificación de movimientos óptimos en un entorno simulado-
móvil. Además, presenta un enfoque nuevo para la planificación de trayectorias de
agentes móviles utilizando un algoritmo de optimización estocástico artificial de
colmenas de abejas (ABC) en medio de obstáculos dinámicos, destacando así un
análisis comparativo de los diferentes esquemas de computación bio-inspirados.
Además, exponen un esquema de planificación de trayectoria local con un algoritmo
de optimización para el uso de colonias de abejas. Los resultados experimentales
expuestos superan a los algoritmos predominantes de la literatura, con respecto a las
métricas estándares, como la desviación promedio total de la trayectoria y la distancia
objetivo.
Por otra parte, Xuzhi Chen [10] que expone la planificación de múltiples rutas para
vehículos aéreos no tripulados (UAV), estableciendo un algoritmo híbrido basado en
sistema multi-agente (MAS) y optimización de enjambre de partículas (PSO), llamado
MAPSO (Multi-Agent Particle Swarm Optimization). Todos los agentes viven en un
entorno en forma de panal y se ubican en su propia región evitando colisiones y
mejorando las comunicaciones optimizando la velocidad de la información que pasa
entre las partículas. Finalmente, se demuestra una manera eficaz de planificar
múltiples rutas que demuestran la viabilidad y la idoneidad del nuevo método para la
planificación de rutas múltiples.
Como artículo referente en los posibles métodos de navegación que se podrían
aplicar en este proyecto está Cassinis, entre otros [11] que presenta un enfoque para
la detección de minas terrestres antipersonal en donde utilizan equipos de robots
cooperativos. Siguiendo métodos que se originan tanto de la robótica clásica como
de la biología y pretenden definir un conjunto de estrategias de búsqueda adecuadas
para ser utilizadas en un espacio bidimensional, lleno de obstáculos. Además, este
artículo presenta las directrices de las estrategias de búsqueda que se desarrollaron
y la descripción de un simulador que fue diseñado e implementado Para probarlos.
Además, se incluyen breves reseñas de las técnicas disponibles, de las tecnologías
de sensores y de los usos actuales de los dispositivos robóticos en el desminado
humanitario.
9
En Kumar [12] describe una técnica que consiste en utilizar sistemas multi-agentes
para la detección de minas, en este caso, se utilizó la teoría de colonia de hormigas,
que es una técnica basada en la optimización de tiempo de búsqueda, puesto que
busca el camino más corto para encontrar la mina antipersona. Además, Sahin y otros
[13] realizan una optimización usando la teoría de enjambres, específicamente la
colonia de hormigas usando organismos multi-agentes los cuales detectan el número
de minas que se encuentran en una zona determinada, cada agente va directamente
al lugar donde se encuentran dichos artefactos lo que reduce drásticamente el tiempo
de búsqueda.
García Gutiérrez [14] en su artículo diseña e implementa un sistema de control y
posicionamiento para una plataforma física y presenta los resultados de los algoritmos
de posicionamiento y exploración de una pista de minas antipersonales, en dicho
trabajo se cuenta con sensores de detección de metal tipo VMH3CS y su enfoque es
la implementación de la plataforma y posicionamiento de la misma, no en la detección
de la mina propiamente dicha. Nazlibilek [15] identifica las minas y objetos metálicos
enterrados en una zona específica usando una red de sensores que detectan la
perturbación del campo magnético existente en la zona, este procedimiento de
detección de minas se basa en conocer las coordenadas del artefacto, con esto y con
el uso de dos tipos de sensores (AT: Anti tanque y AP: Minas antipersonales) se
determina la naturaleza del objeto encontrado.
Además, en F. De Rango y N. Palmieri [16] se utiliza la teoría de enjambres para la
búsqueda de minas en un ambiente desconocido, con esta técnica se busca optimizar
el tiempo de exploración al mínimo, puesto que al trabajar con un equipo de robots
coordinados y que se comuniquen entre ellos, hace que la detección y el desarme de
la mina sean más rápida. Por otra parte, Cobo Ortega y compañía [17] se apoyan de
la inteligencia de enjambres SWARM para poder categorizar de manera autónoma la
recopilación de información de diferentes fuentes, usando técnicas como PSO
(Particles Swarm Optimization) y ACO (Ant Colony Optimization) y agrupando los
datos con la máxima similitud y mínima distancia haciendo eficiente el problema de
recolección de datos. Sreeja [18] expone cómo usar agentes por jerarquías para saber
los atributos y características de los consumidores y de esta manera clasificarlos
según su lealtad o su frecuencia de compra; teniendo en cuenta las limitaciones de
los recursos poder sacar el máximo provecho de esta situación.
Inspirado en estos sistemas de colaboración y comunicación de los animales se
crearon métodos en los cuales, con la cooperación de robots o individuos, se pueden
resolver problemas complejos segmentando las tareas y asignándoles a cada ente
del sistema. Es así como se crea una red que lleva a cabo el problema de manera
eficiente. Dichos métodos inspirados son aplicados a diferentes situaciones, no sólo
a robótica o a la optimización de un proceso computacional, sino que también se
aplica a diferentes campos como a la economía o a las estrategias militares como la
organización naval o aérea.
10
Se puede observar con los anteriores artículos que para la detección de minas
antipersonales se requiere del estudio de varios aspectos para finalmente detectar
una mina, estos aspectos en múltiples estudios son: la morfología de la plataforma, el
ambiente de búsqueda, el desplazamiento, el barrido del área (Navegación), la
planeación de rutas, la comunicación y cooperación entre robots, finalmente la
detección y desactivación de las minas. Por lo tanto, en este proyecto se abordará los
posibles métodos de navegación para múltiples robots, su cooperación y
coordinación. Teniendo en cuenta como base de desarrollo la teoría de enjambres y
los sistemas multi-agentes; de esta manera se facilita cualquier tarea coordinando y
asignando pequeñas porciones del problema a cada individuo [19]. Además, se
Inspira en los sistemas de colaboración y comunicación de los animales como método
de cooperación de robots o individuos para resolver problemas complejos
segmentando las tareas y asignándoles a cada ente del sistema. Es así como se crea
una red que lleva a cabo el problema de manera eficiente.
11
2. Justificación
La implementación de la navegación como parte de la detección de humanos u
objetos es una herramienta que ha sido utilizada a lo largo de la evolución de la
robótica misma. Esta participación de la robótica en procesos de búsqueda no es
casual, sino que tiene detrás implicaciones y ventajas muy importantes frente a otras
alternativas de navegación controlada por seres vivos en general (ya sea intervención
humana o animal para realizar las monitorizaciones de zonas desconocidas).
Dependiendo de la aplicación que se le pueda dar a la navegación existen ventajas y
desventajas, sin embargo una ventaja notoria que se presenta frecuentemente es el
factor de seguridad, debido a que el uso de robots reduce a cero el riesgo de perder
vidas humanas. Otro factor muy relacionado al mencionado anteriormente es el
aspecto de la economía, debido a que es mucho más costoso perder una vida humana
a perder un robot por muy caro que monetariamente represente la estructura del
dispositivo [20], finalmente, otra ventaja a tener en cuenta es la posible navegación
en grandes áreas o regiones que lo requieran.
Específicamente hablando de una posible aplicación de navegación con multi-
agentes es la detección de minas, con lo cual, es importante conocer las ventajas que
tiene utilizar estrategias usando multi-agentes, debido a que esta aplicación conlleva
a factores de tiempo de recorrido y complejidad del algoritmo que pueden ser
determinantes al salvar vidas y al detectar minas de forma eficaz en grandes regiones
del país [21].
Por estos motivos se quiere realizar un estudio y comparación de dos estrategias de
navegación usando multi-agentes por medio de la simulación de un área específica
no estructurada, aplicando agentes robóticos homogéneos que interactúan y
recorrerán un espacio desconocido no estructurado realizando un barrido del área y
generando una cobertura total del área en estudio. Teniendo en cuenta que
potencialmente se puede aplicar este desarrollo de navegación a la detección de
objetos como minas antipersonales.
12
3. Objetivos
3.1 Objetivo General:
Comparar dos estrategias de navegación basadas en teoría de sistemas multi-
agentes.
3.2 Objetivos Específicos:
o Estudiar el estado del arte de las diferentes estrategias de navegación basadas
en teoría de sistemas multi-agentes.
o Seleccionar dos estrategias específicas de navegación basadas en teoría de
sistemas multi-agentes para su posterior comparación.
o Simular las estrategias de navegación específicas para poder compararlas
usando métricas como el tiempo de ejecución y el área cubierta por los
agentes.
13
4. Marco Teórico
Hoy en día el problema de localización y navegación de un ambiente desconocido y
cambiante es un tema de amplia investigación en la robótica actual. Algunas de estas
investigaciones han buscado una solución con la robótica móvil; intentando comunicar
y coordinar múltiples agentes que puedan recorrer dicho campo, dependiendo de su
exploración y el campo que deben recorrer.
En la actualidad, se ha comenzado a implementar numerosas estrategias que ayudan
a la resolución y optimización de dicho problema. En la robótica actual hay un tema
que está trascendiendo y está siendo el más utilizado. Este es llamado Sistemas multi-
agentes y en donde su principal objetivo es la coordinación y comunicación de robots
para resolver problemas complejos. Dentro de los sistemas multi-agentes existen
algunas técnicas que pueden ser utilizadas para la exploración de campos no
estructurados, estas técnicas son conocidas como “Sistemas Bioinspirados”.
Los sistemas bioinspirados son aquellos que basan su funcionamiento en el
comportamiento de los animales y bacterias como las hormigas, abejas, peces, aves,
entre otros. El ejemplo más común entre estos sistemas es el comportamiento de las
hormigas. Las hormigas, a la hora de buscar comida se dispersan, en un primer
instante, de una forma totalmente aleatoria. Cuando una hormiga o varias hormigas
alcanzan la comida, el resto de la colonia sigue su camino gracias al llamado “rastro
de feromonas”. El camino menos costoso hasta la comida seguido por las hormigas
es el que mayor rastro de feromonas obtenga. Este comportamiento también ha sido
usado en los barcos de pesca, turismo y otros, con el propósito de buscar el camino
más corto, con menos contratiempos de viaje, tormentas, fuertes oleajes y así llegar
con mayor seguridad a su destino.
En este trabajo se implementarán 2 algoritmos que se basan en el comportamiento
de los animales y las bacterias, el primero será el PSO y el segundo e.coli.
El PSO (Particle Swarm Optimization) es una técnica bioinspirada que fue creada por
los científicos James Kennedy y Russell Eberhart en el año 1995 con el objetivo de
inspirarse en el comportamiento de los enjambres de aves y peces para poder
optimizar una función encontrando un mínimo o un máximo según sea el caso. El
PSO está basada en el modelo GBEST el cual explica que cada partícula de un grupo
de estas posee una posición personal y se va buscando en una función de costo los
mínimos que están alrededor de cada partícula con el propósito de buscar el objetivo
que es el mínimo global de la función [22].
El algoritmo PSO generalmente está basado para solucionar problemas en 2
dimensiones, pues cada partícula tiene una posición que está determinada por un
14
vector (x,y) en el espacio de búsqueda y una velocidad que está determinado por el
vector (Vx,Vy), con la que se mueve a través del espacio. Además, como partículas
de un mundo real físico, tienen una cantidad de inercia, que los mantiene en la misma
dirección en la que se movían, así como una aceleración (cambio de velocidad), que
depende principalmente de dos características [22]:
1) Cada partícula es atraída hacia la mejor localización que ella, personalmente,
ha encontrado en su historia (mejor personal).
2) Cada partícula es atraída hacia la mejor localización que ha sido encontrada
por el conjunto de partículas en el espacio de búsqueda (mejor global)
Figura 1. Vectores de cada partícula para moverse en el espacio. [22]
Como se muestra en la figura 1, la fuerza con que las partículas son empujadas en
cada una de estas direcciones depende de dos parámetros que pueden ajustarse
(atracción-al-mejor-personal y atracción-al-mejor-global), de forma que a medida que
las partículas se alejan de estas localizaciones mejores, la fuerza de atracción es
mayor. También se suele incluir un factor aleatorio que influye en cómo las partículas
son empujadas hacia estas localizaciones [22].
Para entender el código de una manera mucho más fácil se implementó un diagrama
de bloques, explicando paso a paso la creación del algoritmo, que se mostrará a
continuación en la figura 2.
15
Figura 2 Diagrama de bloques Algoritmo PSO
16
Por otro lado, se tiene otro algoritmo bioinspirado el cual se trata de la bacteria e.coli,
el comportamiento de estas bacterias es recorrer un campo buscando los mínimos
más óptimos (nutrientes) y cada vez que una bacteria se encuentra mejor posicionada
esta se divide en 2 partes iguales para recorrer dicho campo. Las bacterias se mueven
por medio de flagelos, que son los encargados de escoger la dirección, puede ser por
medio de Swim o Tumble, como se muestra a continuación en la figura 3 [23].
Figura 3 Movimiento Swim & Tumble de bacteria e.coli. [23]
El algoritmo e.coli estima la función de costos después de cada paso iterativo en el
programa, con el objetivo de que las bacterias encuentren el punto más óptimo del
campo, generalmente para este tipo de algoritmos se inicializan 10 bacterias que van
dando pasos dependiendo del movimiento de los flagelos, sea Swim o sea Tumble.
Este algoritmo está conformado por 4 etapas: Quimio taxis, Enjambres, Reproducción
y Eliminación y Dispersión [23].
Quimio taxis: Es el proceso por el cual las bacterias simulan el proceso de posición
sea por Swim o por Tumble, es bueno decir que la posición de la bacteria puede
variar, en algunos tramos puede ser por Swim y en otros por Tumble. [23]
Enjambres: Un grupo de células e.coli se organizan en forma de un anillo de
desplazamiento, moviendo el gradiente de nutrientes y así colocarse en medio de una
matriz semisólida con un solo nutriente. Cuando las células se estimulan por un alto
nivel de Succinato, liberan un Aspartato atrayente, lo que ayuda agrupar las bacterias
y así crear un tipo de enjambre. [23]
Reproducción: Las bacterias e.coli tienen una forma de reproducción, si una bacteria
se encuentra en un valor de la función mejor posicionada que las otras, esa bacteria
se dividirá en 2 partes iguales y las que se encuentren en la peor posición de la función
morirán, con esto lograr que el enjambre tenga el mismo número de población y su
tamaño sea constante. [23]
17
Eliminación y Dispersión: Pueden producirse cambios graduales o repentinos en el
entorno local en el que vive una población de bacterias debido a diversas razones.
Un aumento local significativo de la temperatura puede matar a un grupo de bacterias
que actualmente se encuentran en una región con una alta concentración de
gradientes de nutrientes. Los eventos pueden ocurrir de tal manera que todas las
bacterias en una región mueren o un grupo se dispersa en una nueva ubicación. Para
simular este fenómeno en BFOA algunas bacterias se liquidan al azar con una
probabilidad muy pequeña, mientras que los nuevos reemplazos se inicializan al azar
en el espacio de búsqueda. [23]
El pseudocódigo utilizado para su implementación en Matlab está descrito a
continuación en la figura 4.
Figura 4 Diagrama de flujo algoritmo BFOA implementado
18
5. Diseño y Ejecución del proyecto
En esta parte del proyecto se describirán paso a paso las diferentes etapas que se
siguieron para la realización del mismo, verificando y cumpliendo los objetivos
específicos propuestos, detallando cómo se lograron los diferentes problemas que
hubo durante la realización y cómo se solucionan dichos problemas.
5.1. Etapa de revisión de estrategias de navegación basadas en Sistemas
Multi-agentes
En primera medida en la ejecución del proyecto, se dio paso a revisar las diferentes
estrategias que existen basados en Sistemas Multi-agentes que han sido usados o se
pueden usar para realizar la navegación de zonas no estructuradas. A continuación
se detallarán las estrategias encontradas y el por qué se escogieron dos de estas
para su simulación, adecuación y comparación en un campo no estructurado.
Dentro del área de la optimización de problemas computacionales existen diferentes
métodos de clasificación de técnicas que van desde algunas categorizaciones
sencillas hasta divisiones muy complejas y desordenadas las cuales son muchas
veces incomprensibles o que se pueden enredar y confundir unas con otras dejando
al lector con más dudas que aclaraciones, por lo que para efectos de comprensión se
empezará categorizando las técnicas de resolución de problemas de optimización en
tres grandes grupos: técnicas exactas, técnicas heurísticas y técnicas meta
heurísticas.
Mientras las técnicas exactas de optimización buscan de manera juiciosa la resolución
u optimización de problemas sin medir el tiempo ni los demás recursos que se
necesiten, las técnicas heurísticas y meta heurísticas son alternativas que buscan
soluciones buenas y aceptables que no necesariamente son las óptimas a los mismos
problemas de una manera sencilla y rápida en comparación con las exactas.
Los métodos heurísticos son “procedimientos simples, a menudo basados en el
sentido común, que se supone que ofrecerá una buena solución (aunque no
necesariamente la óptima) a problemas difíciles de un modo fácil y rápido” [24]
A diferencia de las anteriormente mencionadas, las técnicas meta heurísticas intentan
“huir” de óptimos locales que pueden arruinar por completo el fin con el que se aplica
el algoritmo orientando la búsqueda del proceso a optimizar dependiendo de la
evolución de búsqueda del algoritmo. [25]
19
Algunas características que se presentan en los algoritmos meta heurísticos están
relacionados con la inexactitud de las técnicas, por lo que permite movimientos
erróneos como paso intermedio para acceder a zonas inexploradas, lo que conlleva
a otra característica que supone que son técnicas ciegas, es decir, que no sabe si
llegará al óptimo global del problema por lo que se debe indicar la condición de
parada, además cabe destacar que dichas técnicas tienen en cuenta el historial o el
recorrido anterior de los agentes como principio de selección a movimientos futuros
lo que conlleva a que los agentes deben poseer memoria. [26]
Teniendo en cuenta lo anteriormente descrito, se hace enfoque en la técnica meta
heurísticas y los algoritmos que podrían catalogarse como parte de este tipo de
técnicas entre los cuales cabe destacar algunos como lo son:
Algoritmos genéticos: Los algoritmos genéticos se basan en la evolución que han
tenido las especies a lo largo de la historia y como ha sido este proceso para lograr
el objetivo de todo ser viviente, la supervivencia de su raza; es así como aspectos
tales como la herencia y la diversidad toman un valor preponderante tanto en el ámbito
práctico de la supervivencia de las especies como en los algoritmos genéticos. La
genética como estudio de los cambios presentes en las especies de generación en
generación como parte del proceso de selección natural también es un pilar
fundamental que se tiene en cuenta para el análisis de la evolución y su relación para
lograr adaptarlo a sistemas de optimización, por ende se llevan a cabo una
clasificación y especificación de aspectos importantes a tener en cuenta como lo son:
o El número de hijos tiende a ser mayor que el número de padres.
o El número de individuos de una especie permanece aproximadamente
constante.
o De las dos anteriores se concluye que existe una lucha por la supervivencia.
o Dentro de una misma especie, los individuos presentan diferencias, y la
mayoría de estas también está presente en los padres.
o Debe existir algún proceso de variación continuada responsable de la
introducción de las nuevas informaciones, contenidas en los genes de los
organismos.
o No existe un límite de sucesión de variaciones que pueden ocurrir.
o La selección natural es un mecanismo utilizado para la preservación de las
nuevas informaciones que permite una mejor adaptación al medio. [27]
Teniendo en cuenta lo anterior los algoritmos genéticos proponen un método para que
por medio de “selección natural” y basados en la experiencia de las anteriores
generaciones, los genes que los padres dejan a sus hijos “muten” mejorando cada
vez más las características de los individuos adaptándose al medio. Los algoritmos
genéticos en general se componen de tres partes: Selección, recombinación y
mutación, que suceden en un ciclo generacional.
En la selección, se escogen dos de todas las configuraciones que generan
descendientes en una población, es decir, se elige en una población que una
20
configuración de como resultado muchos descendientes por ejemplo mientras otra
configuración desaparece al tener cero descendientes.
En la etapa de recombinación se mezclan las dos configuraciones escogidas
generando dos nuevas configuraciones con características de las dos anteriores,
generando la “diversidad genética”. Uno de los ejemplos más claros de este proceso
es el fenómeno de meiosis en las células que se muestra en la figura 5.
Figura 5 Representación de la diversificación por recombinación presente en las
células. [28]
Por último, la mutación cambia un solo aspecto en las características, en la
codificación binaria (principal aplicación o enfoque que se le da a los algoritmos
genéticos) sería el cambio de valor de una variable de 0 a 1, lo cual cambia el gen y
encontrando las nuevas configuraciones de la nueva generación repitiéndose el ciclo
descrito hasta cumplir los criterios de parada especificados.
Algoritmo GRASP: Las siglas GRASP tienen su origen en inglés de la expresión
Greedy Ramdomized Adaptative Search Procedure, es un algoritmo metaheurístico
que busca soluciones aceptables para un problema en particular por lo que se
considera un método de optimización combinacional (construye un conjunto de
soluciones alternativas). Este algoritmo busca soluciones locales para luego construir
las posibles soluciones al problema por lo que se aplica a problemas de campo
discreto en los cuales se conocen algunas características del campo como lo puede
ser los obstáculos o algunos puntos del mismo.
En su forma elemental, el algoritmo GRASP cuenta con tres partes fundamentales de
funcionamiento: fase de pre-procesamiento, fase de construcción y fase de búsqueda.
La primera fase consta de identificar algunos atributos que hacen parte de la solución
óptima que ayudan a reducir el problema considerable, centrándose en los mejores
aspectos y descartando los peores.
21
A continuación en la fase de construcción se toma la propuesta encontrada en la fase
anterior y se adicionan atributos nuevos para completar la propuesta y tener así una
solución completa, este proceso está acompañado de un factor de sensibilidad que
ayuda a determinar los atributos a adicionar a la solución parcial. Es así como se da
paso a la fase de búsqueda, que consiste en una vez tenida una solución factible,
explorar la región vecina en busca de soluciones mejores, en dado caso de encontrar
una propuesta mejor, esta se almacena y continúa el proceso de búsqueda en otra
vecindad. Es así como termina un ciclo del algoritmo que vuelve a realizar todo el
proceso hasta que las iteraciones predefinidas terminan o encuentre un criterio de
parada.
Por último se puede efectuar un método de reencadenamiento de trayectorias a las
soluciones encontradas debido a que este algoritmo no posee una memoria interna
lo que le imposibilita realizar esta operación en su ejecución. [25]
Búsqueda Tabú: Este algoritmo está enmarcado en las técnicas metaheurísticas y
tiene como principal novedad a las ya vistas, la inclusión de memoria adaptativa que
le permite moverse por el espacio en búsqueda de un mínimo global evitando los
óptimos globales. Su metodología está encaminada en explotar una colección de
métodos inteligentes de aprendizaje para la resolución de problemas complejos. La
búsqueda tabú considera una solución como óptima si cumple dos criterios: la
memoria adaptativa y la búsqueda responsiva. La primera de ellas se subdivide en
memoria de corto plazo y memoria de largo plazo las cuales consisten en registros
recientes en el caso de la memoria a corto plazo y a datos de la frecuencia con que
ocurren ciertos eventos en el caso de la memoria a largo plazo, esta memoria basada
en frecuencia recolecta información del número de veces que ciertos atributos han
estado presentes en la búsqueda, o en soluciones que ya han sido visitadas, y
precisamente esto último nos lleva a pensar en las soluciones tabú, que son
denominadas prohibidas con el fin de no recaer en las mismas.
En el caso de la búsqueda responsiva esto se refiere a que parte de la suposición de
que una elección mala estratégicamente hablando proporciona mayor información del
entorno que una buena elección al azar ya que proporciona un campo de no solo las
mejores soluciones al problema sino que también proporciona un vistazo a soluciones
prometedoras inexploradas. [29]
Recocido simulado: Este algoritmo se basa en la termodinámica de los sólidos en
el cual se calienta un objeto para luego ser enfriado logrando después de varias
iteraciones un estado de cristal perfecto, en este caso la energía libre es la función
que se optimiza en el sólido mientras el enfriamiento es el proceso que lleva a
minimizar resultando un cristal imperfecto al caer en un óptimo local. El proceso de
optimización se realiza una ejecución similar siendo este un algoritmo combinacional
denominado “Simulated Annealing” (SA), es ampliamente usado en la resolución de
problemas de transmisión debido a que puede resolver situaciones de gran
complejidad, sin embargo, presenta una desventaja notoria que se basa en la alta
complejidad y coste computacional que conlleva su ejecución. [25]
22
Optimización por colonia de hormigas (ACO): Tanto las hormigas como otros
insectos se caracterizan por ser individuos simples que al juntarse y ejecutar las
tareas en conjunto pueden realizar labores realmente complejas, por lo cual se han
hecho algoritmos que simulan este comportamiento. En el caso específico de las
hormigas, dicho algoritmo recibe el nombre de ACO, por sus siglas en inglés que
corresponden a Ant Colony Optimization. Este algoritmo metaheurístico busca el
mínimo global de una función a partir del comportamiento de las hormigas para buscar
su alimento y llevarlo a la colonia. Es así como en la práctica las hormigas recorren
un camino aleatorio hacia una fuente de alimentos y dependiendo del resultado, lleva
una pequeña porción de dicho alimento a la colonia dejando tras de sí una sustancia
química que alerta y atrae a las demás compañeras de su hallazgo para que vayan
tras de sí y traigan el alimento.
Figura 6 modelo de recorrido de un grupo de hormigas [25]
Como se observa en la figura 6, hay que resaltar que el camino tomado por las
hormigas en un primer momento es un camino aleatorio, puede que coja el camino
más largo (ilustrado en la figura como camino l) o el más corto fruto del azar (denotado
como camino c), sin embargo, la hormiga que toma el camino más corto tiene la
posibilidad de volver con un rastro de feromona de una manera mucho más rápida
que la hormiga que tomó el camino largo, por lo que una segunda hormiga tomará el
camino corto en un tiempo mucho más reducido que el tiempo que lo hará una
hormiga en tomar el camino largo dejando así cada vez un rastro de feromona mucho
más denso. También cabe la posibilidad que en caminos muy largos la hormiga no
regrese por lo que el rastro de feromona será muy débil y tenderá a desaparecer por
la evaporación de la sustancia eliminando la solución errónea, de esta manera la
hormiga puede saber a partir de la experiencia de sus congéneres la opción más
viable tomada como el camino con la concentración de feromona más alto, es así
como en la figura 7 se puede observar la decisión de la hormiga teniendo varias
opciones.
Figura 7 la decisión de la hormiga está relacionado con la concentración de
feromona de cada camino. [30]
23
Sin embargo, cabe resaltar que la implementación de la técnica de optimización
basada en hormigas requiere un número finito de posibilidades donde el individuo se
puede mover, esto es, caminos finitos por donde la hormiga puede llegar a su objetivo,
por lo cual es necesario implementar un sistema de adecuación de los campos que
no es perfecto ya que las partículas están limitadas a ciertas rutas preestablecidas
pero se puede realizar mediante teoría de grafos. Como se muestra en la figura 8,
esta teoría a grandes rasgos, crea grafos a partir de puntos especificados de manera
que pueda iterar entre cada posibilidad y concluir cual es la más corta.
Figura 8 ejemplo de teoría de grafos donde las líneas se generan entre cada uno de
los vértices especificados [30].
No obstante para la evasión de obstáculos se hace necesario crear un espacio de
grafos que generen caminos libre de dichas limitaciones, por lo que aparece un
método llamado MAKLINK que muestra su estructura general en la figura 9, el cual
genera grafos con vértices ubicados en los obstáculos, los cuales para lograr la
creación de las líneas son hexágonos cuyos lados están interconectados ya sea con
otros obstáculos como con los bordes del campo.
Figura 9 campo generado con MAKLINK para la evasión de obstáculos. [31]
Particle Swarm Optimization (PSO): Esta técnica de optimización matemática se
inspira en el comportamiento social de los individuos, analizando las interrelaciones
existentes entre los individuos y los demás integrantes de un grupo. El
comportamiento base de este algoritmo es el comportamiento colectivo e individual
de las aves cuando vuelan en bandadas. Pues para los científicos era muy interesante
24
estudiar la estética de la coreografía de las bandadas de aves y de esta manera
descubrir las reglas subyacentes que permitan vuelos sincrónicos de grandes grupos
de aves, a menudo cambiando de dirección repentinamente, dispersándose y
reagrupándose. [32]
Este algoritmo es importante puesto que es regido por ciertas normas y leyes físicas
que se deben cumplir, una de las más importantes es evitar la colisión entre los
individuos, puesto que para el algoritmo debe ser imposible que 2 partículas ocupen
el mismo lugar en el espacio y para esto, mantienen una distancia optima entre un
individuo y sus vecinos más cercanos. Otra ventaja que ofrece el algoritmo y que
parece importante es que el movimiento de las aves que se desplazan en formación
se realiza en un espacio de tres dimensiones, y que las aves aprenden a temprana
edad a volar en grupo sin colisionar con las demás aves, una manera de observar la
formación entre aves es la que se muestra en la figura 10. [27]
Figura 10 Vuelo en formación de una bandada de aves [32]
En teoría, los miembros de un grupo de individuos pueden beneficiarse de los
descubrimientos y la experiencia previa de todos los demás miembros, durante la
búsqueda de recursos indispensables para la supervivencia. Esta ventaja resulta ser
decisiva y prevalece sobre las dificultades que surgen el proceso de intercambio de
información entre individuos del colectivo.
Es importante tener en cuenta que entre los grupos de individuos se crean jerarquías
y una característica muy común es que se haya un líder del grupo reconocido y
seguido por los demás miembros. Cada individuo del grupo se encuentra influenciado
por dos factores: El primero está relacionado con el conocimiento y las habilidades
propias de los individuos, el segundo factor está asociado a la influencia que ejerce
el líder sobre los demás individuos. El líder es un individuo que posee características
físicas o habilidades que le permitan mantener un control sobre los demás
integrantes. Los miembros del grupo confían en las cualidades del líder para dirigirlos,
pero sin embargo, el líder puede cambiar si surge un individuo con mejores
características que el líder actual. Las características que debe tener el líder del grupo
se pueden dividir en tres factores:
25
o Conocimiento sobre el entorno.
o Conocimiento histórico o de experiencias anteriores.
o Experiencias de los individuos situados en su vecindario.
El modelo del algoritmo PSO está basado en encontrar el mínimo global de un
espacio, de esta manera un grupo de aves es capaz de realizar una exploración
alrededor del campo buscando su optimo local, en este caso el mínimo global. Esta
característica resulta importante puesto que de esta manera el algoritmo es capaz de
evitar obstáculos y colisiones con otros objetos, este proceso se puede observar en
la figura 11.
Figura 11. Búsqueda de la solución óptima del PSO [27]
Bacterial Foraging Optimization Algorithm (e.coli): Las bacterías han sido de gran
interés para los investigadores en la inteligencia artificial, pues debido a su
reproducción y evolución han formado parte importante como un algoritmo
bioinspirado en la búsqueda y barrido de campos no estructurados, este algoritmo
está basado en el sistema de producción de la bacteria e.coli.
La biología de estos sistemas es de una manera extraordinaria y en los últimos años
ha sido usada para algoritmos de optimización que basan su comportamiento en
quimio taxis, enjambres y reproducción de bacterias. Su principal funcionamiento está
en reproducirse al buscar comida o nutrientes dentro de un campo, el cúmulo de
bacterias está diseñado para encontrar un líder que tenga la mejor posición dentro
del campo en la búsqueda de nutrientes, cada partícula que se encuentra en la mejor
posición es dividida en dos partes iguales que recorran el campo, mientras que las
partículas que estén en la peor posición en la búsqueda de nutrientes se mueren
debido a su biología. De esta manera es posible encontrar un número constante del
enjambre permitiendo avanzar hacia la mejor posición en búsqueda de nutrientes.
La posición de cada bacteria está dada por flagelos que dirigen el camino de cada
bacteria, puede que ser Swim y que la bacteria siga una dirección recta o puede que
sea Tumble y que la bacteria haga una rotación en sentido de las manecillas del reloj,
26
esta posición puede ir cambiando de acuerdo a cada iteración del programa buscando
la mejor posición.
Las bacterias se simulan en un campo potencial como en el algoritmo PSO, en donde
su objetivo es también encontrar el mínimo global en un campo de potenciales, y de
esta manera realizar un recorrido a través del campo en donde cada bacteria haga
una exploración que lo lleve al objetivo. [23]
Figura 12. Recorrido de bacterias en un campo potencial [23]
Como se muestra en la figura 12, se puede observar que las bacterias realizan una
exploración del campo evitando obstáculos y buscando el mínimo global, los
obstáculos en el campo son diseñados con funciones gaussianas con el objetivo de
simular máximos locales que las bacterias seguramente evadirán puesto que
marcharán en busca del mínimo global.
5.2. Etapa de Elección de estrategias
Los sistemas multi-agentes tienen como principal objetivo la interacción entre robots
para resolver problemas complejos que los humanos no pueden hacer con facilidad.
Como se vio anteriormente en la clasificación adoptada se determinó e hizo énfasis
en las técnicas meta heurísticas de las cuales se escogerán dos algoritmos a analizar.
En la formulación del proyecto se espera que los agentes se organicen y se
comuniquen con facilidad, que sigan un patrón y cumplan con una tarea compleja de
ordenamiento y navegación de un área. Para estas condiciones, se busca una técnica
que se capaz de realizar dichas tareas y según estudios previos, basándonos en
facilidad de comunicación, ordenamiento e implementación se escogieron los
algoritmos basados en sistemas bioinspirados.
Las técnicas bioinspiradas son las técnicas que se basan en el comportamiento de
los animales, siguiendo patrones de búsqueda y exploración. Es por esta razón que
27
se acomodan perfectamente para dar solución a la ejecución del proyecto. Dentro de
las técnicas bioinspiradas existen varias estrategias que son: Cardumen de peces,
colmena de abejas y colonia de hormigas, algoritmos genéticos y optimización basada
en bacterias. Para la ejecución del proyecto se procedió a trabajar con 2 estrategias
específicas, estas son: PSO (Particle Swarm Optimization) que es una estrategia
basada en las aves y la segunda es la estrategia E.coli que se inspira en el modelo
de una bacteria, teniendo en cuenta su reproducción y cómo trabajan con enjambres.
Estas 2 estrategias son también las seleccionadas debido al tipo de comparación que
se pueden hacer entre estas, la comparación resulta ser totalmente directa, debido al
concepto que usa cada técnica para poder realizar el recorrido de un área
determinada, el cual en ambos algoritmos se puede simular de manera continua
dando la posibilidad de explorar un espacio no estructurado en su totalidad a
diferencia de, por ejemplo, algoritmos que limitan su búsqueda a caminos
determinados como lo pueden llegar hacer optimización por hormigas y abejas, y de
esta manera tomar en cuenta los factores de tiempo que demora cada técnica en
realizar su tarea y el porcentaje de área recorrido que ocupó en el espacio.
5.3. Creación del Campo
En la etapa de la creación del campo se utilizó como base la definición de un campo
potencial en la que se crean campos de repulsión y de atracción para saber cuándo
hay un obstáculo y poder evadirlo de manera eficaz y cuando hay un mínimo local el
cual atrae a las partículas.
El campo es un escenario cuadrado no estructurado que posee forma cóncava, efecto
que da al implementar una función cuadrada cuyo centro es el punto a donde se
quiere llegar y que atrae a las partículas, posee obstáculos los cuales son modelados
al introducir funciones gaussianas, estas funciones tienen como características
principal que forman puntos máximos en el campo potencial demarcados en el
Software como puntos calientes de colores cálidos (tonalidades de rojo y amarillo) y
de esta manera poder distinguir el obstáculo de los demás puntos del campo.
Para modelar este campo es necesario implementar la función objetivo como una
fórmula cuadrática y multiplicarla por un factor de escalamiento 𝑤1 que en este caso
será de un valor muy pequeño de 0.001 así la función a optimizar queda de la
siguiente manera:
𝐽𝑔(𝑥, 𝑦) = 𝑤1[[𝑥, 𝑦]𝑇 − [𝑥𝑚𝑖𝑛 − 𝑦𝑚𝑖𝑛]𝑇]𝑇[[𝑥, 𝑦]𝑇 − [𝑥𝑚𝑖𝑛 − 𝑦𝑚𝑖𝑛]𝑇](1)
En el caso de los obstáculos, estos al ser funciones gaussianas, se rigen por la
expresión que las representa:
𝐽𝑜(𝑥, 𝑦) = 𝑤2𝑒−([𝑥+𝑥𝑜𝑏𝑠]2+[𝑦+𝑦𝑜𝑏𝑠]2
𝑠𝑖𝑔𝑚𝑎 (2)
28
Donde 𝑤2 = 2, 𝑥𝑜𝑏𝑠 y 𝑦𝑜𝑏𝑠 representan las coordenadas de la posición del obstáculo.
Es así como la función de costos completa está dada por la siguiente expresión:
𝐽𝑐(𝑥, 𝑦) = 𝐽𝑜(𝑥, 𝑦) + 𝐽𝑔(𝑥, 𝑦)(3)
Al implementarla en el software de simulación los resultados se pueden ver a
continuación:
Figura 13 campo potencial simulado en tres dimensiones
Como se puede evidenciar en la figura 13, al implementar la suma de las funciones
del campo y los obstáculos, se genera un especio cóncavo inclinado hacia el centro
de la función (en este caso, [5,5]) en donde sus puntos máximos son las funciones
gaussianas, y que en el campo representan obstáculos.
Figura 14. Estructura del campo potencial con obstáculos.
En la figura 14, se puede evidenciar el campo desde una vista superior, en donde se
observa su mínimo global y las funciones gaussianas que representan los obstáculos.
29
5.4. Discretización del campo
Mediante la implementación de los algoritmos, se generaron algunas inquietudes a la
hora de poder conocer el porcentaje del barrido de la zona, es así que se tuvo que
discretizar el campo para lograr tener una aproximación de cobertura finita, por lo que
se decidió realizar una cuadrícula de 100x100 a lo largo y ancho del campo de tal
forma que las partículas al moverse en todo momento se pueda saber en qué parte
del campo se encuentran. En la figura 15, se puede observar en color rojo la
cuadricula generada para la discretización del campo.
Figura 15. Campo discretizado - cuadrados 100*100
Al obtener el campo discretizado en cuadrados pequeños, se hallaron y registraron
las coordenadas que corresponden al punto medio de cada cuadrado con el objetivo
de conocer cuántos cuadros ha recorrido cada partícula y así poder hacer una relación
de porcentaje recorrido. El campo discretizado con las coordenadas se puede
observar de la siguiente manera en la figura 16 en donde los puntos azules
representan dicho punto medio mencionado anteriormente.
Figura 16. Campo discretizado con coordenadas de centros de la cuadrícula
30
5.5. Creación del Sensor
Como bien se sabe, los robots implementan diversos sensores que ayudan a la
recolección de datos y así poder cumplir los objetivos propuestos, de esta manera en
este proyecto se implementó la simulación de un sensor que pudiera reconocer
cuántos cuadros ha recorrido y así poder realizar exactamente la relación de
porcentaje que ha recorrido en el campo. Este sensor tiene un área de 0.5 metros y
tiene como centro la partícula y de esta manera realizar el recorrido del campo.
Figura 17. Creación de sensores en los agentes
Como se puede observar anteriormente en la figura 17, los círculos verdes que rodean
la partícula son los sensores creados para hacer el registro del campo recorrido por
cada partícula.
Por otro lado, un factor importante en la implementación de los sensores fue el poder
conocer qué partícula recorre un punto y de esta manera que no se repita o se tome
en cuenta para las otras partículas que recorren el campo y de esta manera, tener un
valor exacto del porcentaje recorrido del campo.
La implementación del sensor permitió conocer el área recorrido por una partícula.
Para esto se procedió a implementar un sistema en el cual cada una de las partículas
por medio de un sensor simulado tenía cierta visibilidad alrededor suyo para detectar
cierta área del campo en cada iteración. El área detectada está dada por el contacto
de los sensores al punto central de cada uno de los cuadrados, por lo que al
interactuar el sensor con el punto se da como recorrido el cuadrado al que pertenece.
Para modelar este sistema se siguió la siguiente fórmula matemática:
31
𝐶𝑜𝑣𝐴𝑎𝑔 = {(𝑥, 𝑦)|(𝑥 − 𝑥𝑎𝑔)2
+ (𝑦 − 𝑦𝑎𝑔)2
≤ 𝐶𝑜𝑣𝑅𝑎𝑔2 } (4)
La anterior expresión guarda en la variable 𝐶𝑜𝑣𝐴𝑎𝑔 un valor de 1 si se cumple la
condición que tiene la cual consiste en que si la distancia que existe entre las
coordenadas (𝑥, 𝑦) que corresponden a la posición de la partícula dentro del campo
y el centro que se quiere recorrer con coordenadas (𝑥𝑎𝑔, 𝑦𝑎𝑔) es menor al radio de
cobertura dado al sensor denotado con 𝐶𝑜𝑣𝑅𝑎𝑔, de manera contraria (la distancia es
mayor al radio) no cuenta como cuadro recorrido. De manera gráfica se puede denotar
en la figura 18, donde el punto 𝑋𝑎𝑔 , 𝑌𝑎𝑔 son las coordenadas a analizar, (x,y) es el
punto actual de la partícula y CovRag es el radio de cobertura
Figura 18. Representación sistema de cobertura implementado
5.6. Implementación del Algoritmo PSO en Matlab
En primera medida, se debe tomar en cuenta que el algoritmo PSO realiza un
procedimiento de búsqueda en el espacio solución que explora simultáneamente
varios sub espacios que se encuentran relativamente próximos entre sí. Las partículas
recorren un espacio en busca del mínimo global y cada partícula posee una posición
𝑋i(t) y una velocidad 𝑉𝑖(𝑡). De acuerdo a estos parámetros, cada partícula según su
posición tiene la mejor posición 𝑃𝑏𝑒𝑠𝑡 o la mejor posición del grupo de partículas 𝐺𝑏𝑒𝑠𝑡.
Conceptualmente 𝑃𝑏𝑒𝑠𝑡 representa la memoria autobiográfica, a través de la cual cada
individuo recuerda sus antiguas experiencias. 𝐺𝑏𝑒𝑠𝑡 Está asociada a la tendencia de
los grupos de regresar a donde obtuvieron las mayores satisfacciones en el pasado.
La posición actual de cada individuo es modificado estocásticamente en cada
iteración, tomando como referencia la posición actual y la velocidad.
Durante la implementación del algoritmo se deben tener en cuenta algunas
constantes y parámetros que son claves para la velocidad y la posición de cada
partícula. Partiendo de que la posición de cada partícula está regida por la siguiente
ecuación:
𝑋𝑖(𝑡 + 1) = 𝑋𝑖(𝑡) + 𝑉𝑖(𝑡 + 1) (5)
32
Es necesario implementar la fórmula de velocidad de cada partícula, la cual se
muestra a continuación:
𝑉𝑖(𝑡 + 1) = 𝑤 ∗ 𝑣𝑖(𝑡) + 𝐶1 ∗ 𝑟𝑎𝑛𝑑(𝑃𝑏𝑒𝑠𝑡 − 𝑥𝑖(𝑡)) + 𝐶2 ∗ 𝑟𝑎𝑛𝑑(𝐺𝑏𝑒𝑠𝑡 − 𝑥𝑖(𝑡))(6)
La ecuación anterior está compuesta por un término correspondiente a la experiencia
propia de la partícula y otro relacionado con la experiencia social. Los parámetros que
intervienen en la actualización de la velocidad se describen a continuación:
Factor de inercia (w): Es aquella que controla el grado de influencia que la velocidad
actual de la partícula 𝑉𝑖(𝑡) produce sobre la velocidad futura 𝑉𝑖(𝑡 + 1). Este factor
permite controlar el balance entre la diversificación y la intensificación de la búsqueda
en el subespacio que rodea a la partícula, y divide los individuos entre explorados o
colonizadores. Pero para la implementación del código, se desea que las partículas
sean primero exploradoras y después de cada iteración sean colonizadoras, para
lograr esto, se propuso iniciar el factor de inercia en un 𝑊𝑚𝑎𝑥 y a medida de cada
iteración que su valor vaya disminuyendo hacía un 𝑊𝑚𝑖𝑛. La fórmula que rige esta
condición es la siguiente:
𝑤 = [(𝑊𝑚𝑖𝑛−𝑊𝑚𝑎𝑥)
(𝑖𝑡𝑒𝑟𝑚𝑎𝑥−1)∗ (𝑖𝑡𝑒𝑟 − 1)] + 𝑊𝑚𝑎𝑥, 𝑝𝑎𝑟𝑎 𝑖𝑡𝑒𝑟 ≤ 𝑖𝑡𝑒𝑟𝑚𝑎𝑥 (7)
En esta ecuación hay que tener en cuenta que el valor iter es el contador de
iteraciones e itermax es el número máximo de iteraciones que se desea efectuar para
que termine el código. Para esta implementación los valores de 𝑊𝑚𝑎𝑥 𝑦 𝑊𝑚𝑖𝑛 fueron
0.9 y 0.1 respectivamente.
Constantes de aceleración (C1 y C2): Valores que direccionan las partículas hacia
la mejor ubicación local y global. C1 regula la influencia que tiene la mejor posición
alcanzada por la partícula, en la determinación de su nueva dirección. Mientras que
C2 regula la influencia del líder del cúmulo en la dirección de búsqueda de cada
partícula. Para escoger el valor de estos parámetros es necesario conocer los
siguientes parámetros:
o Si 𝐶1 > 0 𝑦 𝐶2 = 0, las partículas actúan independientemente y cada
partícula realiza una búsqueda local
o Si 𝐶1 = 0 𝑦 𝐶2 > 0, las partículas actúan colectivamente y cada
partícula realiza una búsqueda estocástica.
o Si 𝐶1 = 𝐶2 > 0, las partículas son atraídas por el valor promedio entre
el conocimiento individual y el conocimiento colectivo
o Si 𝐶1 > 𝐶2, las partículas privilegian la experiencia propia sobre la
experiencia del grupo.
o Si 𝐶2 > 𝐶1, la experiencia colectiva se privilegia sobre la individual.
33
o Si 𝐶1 𝑦 𝐶2 son pequeños producen trayectorias de desplazamiento
suaves.
o Si 𝐶1 𝑦 𝐶2 son grandes producen grandes aceleraciones y movimientos
abruptos.
Para escoger el valor apropiado de estas constantes fue necesario utilizar una fórmula
de la literatura especializada, en donde proponen:
𝐶1 =(𝐶1𝑚𝑖𝑛−𝐶1𝑚𝑎𝑥)
𝑖𝑡𝑒𝑟𝑚𝑎𝑥∗ 𝑖𝑡𝑒𝑟 + 𝐶1𝑚𝑎𝑥, 𝑝𝑎𝑟𝑎 𝑖𝑡𝑒𝑟 < 𝑖𝑡𝑒𝑟𝑚𝑎𝑥 (8)
𝐶2 =(𝐶2𝑚𝑎𝑥−𝐶2𝑚𝑖𝑛)
𝑖𝑡𝑒𝑟𝑚𝑎𝑥∗ 𝑖𝑡𝑒𝑟 + 𝐶2𝑚𝑖𝑛, 𝑝𝑎𝑟𝑎 𝑖𝑡𝑒𝑟 < 𝑖𝑡𝑒𝑟𝑚𝑎𝑥 (9)
Para la elección de las constantes C1min, C1max, C2min y C2max, se hicieron de la
siguiente manera 𝐶1𝑚𝑖𝑛 = 𝐶2 min = 0.5 𝑦 𝐶1 max = 𝐶2 max = 2.5, valores escogidos
de manera experimental.
Mejor ubicación Local (Pbest): Representa la memoria de cada individuo. En esta
variable se almacena la mejor posición que la partícula ha tenido durante su recorrido.
Mejor ubicación Global (Gbest): Representa la memoria del grupo. En esta variable
se almacena el valor de la mejor ubicación que ha tenido el líder del cúmulo durante
su recorrido.
De esta manera, al tener todas las variables y constantes, es mucho más fácil poder
implementar la posición actualizada de cada partícula. Sin embargo hay que tener en
cuenta que en algún momento la posición de cada partícula no exceda los límites, y
esto puede darse dependiendo de la velocidad de cada partícula.
Es así que se interviene la formula, restringiendo la velocidad a un valor máximo de
0.3, y así de esta manera evitar que las partículas excedan los límites y la posición no
se altere y se desborde.
5.7. Implementación del algoritmo BFOA en Matlab
Para la implementación del modelo de E.Coli basado en la optimización de búsqueda de
bacterias (BFOA) fue necesario tener en cuenta el modelamiento matemático que tiene el
comportamiento de las bacterias dentro de un entorno dado, comportamientos y actos tales
como el movimiento en busca de nutrientes, suceso que trae consigo dos posibilidades: que
34
la bacteria se mueva de manera recta a lo largo del campo (swim), o que la bacteria de una
vuelta para reposicionarse de mejor manera para encontrar los nutrientes que se buscan
(tumble) que en este caso es el mínimo al que se desea llegar, dicho movimiento es llamado
quimio taxis debido a que en la teoría la bacteria se mueve buscando nutrientes que le brindan
energía para crecer y seguir desplazándose por el espacio. Otros comportamientos que son
tenidos en cuenta para la implementación del algoritmo son: la reproducción de la bacteria
denotado con la letra k y la eliminación-dispersión del individuo denotado con la letra l.
Además de estos comportamientos, al ser un algoritmo de optimización es necesario tener
en cuenta por supuesto la función de costos o función a optimizar que en este caso es una
función igual a la implementada en el PSO que consta de un campo cóncavo con su centro
en el mínimo global a donde se quieren llevar las partículas representado por una expresión
cuadrada con unos máximos que representan los obstáculos que se deben evitar denotados
por la expresión de funciones gaussianas. En el ámbito teórico del algoritmo el mínimo
representa sustancias que son usadas como nutrientes para las bacterias mientras que los
máximos representan sustancias nocivas para los individuos que deben ser evitadas por los
mismos. Es así que para empezar se debe tener en cuenta que los pasos de la quimio taxis
están denotados con la letra j y el número de estos pasos por la constante 𝑁𝐶 , luego se tiene
la expresión de movimiento de la partícula la cual depende tanto de la quimio taxis de la
bacteria (j) como de la reproducción (k) y de la eliminación-dispersión (l) y está indicada por
la siguiente ecuación:
𝜃𝑖(𝑗 + 1, 𝑘, 𝑙) = 𝜃𝑖(𝑗, 𝑘, 𝑙) + 𝐶(𝑖)∆(𝑖)
√∆𝑇(𝑖)∆(𝑖) (10)
En donde i representa la iteración de la posición de cada una de las bacterias, 𝐶(𝑖)
representa el valor de la magnitud del paso en dirección aleatoria tomado al darse la
vuelta (tumble) y ∆(𝑖) representa un vector en dirección aleatoria con valores que
oscilan entre -1 y 1.
Antes de continuar con la reproducción de la bacteria y la dispersión hay que tener en
cuenta y modelar matemáticamente la comunicación e interacción que existe entre
cada una de las bacterias con sus congéneres dentro de la simulación. Para esto es
necesario tener en cuenta variables que en la teoría sirven a la bacteria a dar señal a
sus congéneres de su posición para poder mantenerse juntas, dichas variables son
secreciones tanto de atracción como de repulsión lanzadas por cada bacteria que
sirven para mantener distancia de los nutrientes que cada bacteria consume. Es así
como se tiene:
o 𝑑𝑎𝑡𝑡𝑟𝑎𝑐𝑡 Correspondiente a la cantidad de sustancia atrayente lanzado por cada
bacteria.
o 𝑤𝑎𝑡𝑡𝑟𝑎𝑐𝑡 Correspondiente al radio de difusión que tiene la sustancia lanzada.
o ℎ𝑟𝑒𝑝𝑒𝑙𝑙𝑒𝑛𝑡 Correspondiente a la cantidad de sustancia repelente lanzada por
cada bacteria.
o 𝑤𝑟𝑒𝑝𝑒𝑙𝑙𝑒𝑛𝑡 Correspondiente al radio de difusión de la sustancia repelente.
Teniendo en cuenta las anteriores consideraciones la ecuación que representa el
efecto de swarming en las bacterias está dada por:
35
𝐽𝐶𝐶(𝜃, 𝑃(𝑗, 𝑘, 𝑙)) = ∑ 𝐽𝐶𝐶𝑖
𝑆
𝑖=1
(𝜃, 𝜃𝑖(𝑗, 𝑘, 𝑙)) (11)
= ∑ [−𝑑𝑎𝑡𝑡𝑟𝑎𝑐𝑡exp (−𝑤𝑎𝑡𝑡𝑟𝑎𝑐𝑡 ∑ (𝜃𝑚 − 𝜃𝑚𝑖 )2
𝑝
𝑚=1
]
𝑆
𝑖=1
+ ∑ [ℎ𝑟𝑒𝑝𝑒𝑙𝑙𝑒𝑛𝑡exp (−𝑤𝑟𝑒𝑝𝑒𝑙𝑙𝑒𝑛𝑡 ∑ (𝜃𝑚 − 𝜃𝑚𝑖 )2
𝑝
𝑚=1
]
𝑆
𝑖=1
De la anterior fórmula cabe aclarar que la sumatoria de m=1 hasta p se refiere que
𝜃𝑚 se refiere a cada una de las dimensiones que se desea manejar en la optimización
que en este caso serán 2 para poder observar los resultados, además, 𝜃𝑚 quiere dar
a entender cada uno de los componentes de la posición dependiendo de las
dimensiones en este caso se refiere a la componente en el eje x y a la componente
en el eje y.
Posteriormente se tiene el comportamiento de la reproducción y además de
eliminación- dispersión de las bacterias que se explicarán de manera conjunta debido
a que el modelamiento es correlacionado. Es así como en primera medida y al igual
que en la quimio taxis se tiene un número de pasos en este caso un número de
reproducciones dado por la constante 𝑁𝑟𝑒, además se tiene el número de bacterias
aptas para poder reproducirse lo cual en realidad viene siendo la división de la
bacteria en dos con la expresión: 𝑆𝑟 = 𝑠
2. Es así como se debe ordenar la población
de bacterias por la función de costos acumulada, debido a que un valor alto en esta
variable quiere decir que no ha tenido los nutrientes necesarios a lo largo de la
búsqueda por lo que no ha sido una labor exitosa, lo que trae como consecuencia que
dicha bacteria debe morir mientras las bacterias con un valor bajo son las que han
tenido más nutrientes y son las que finalmente se dividen ocupando el lugar de la
bacteria que ya no existe.
Por último dentro de la realización del algoritmo se tiene en cuenta la constante 𝑁𝑒𝑑
que se refiere a la cantidad de eventos de eliminación y dispersión de la población y
que está sujeta a una probabilidad 𝑝𝑒𝑑. Esta medida se toma para simular de manera
mucho más realista el comportamiento de las bacterias debido que factores de
temperatura y variables externas del ambiente pueden llegar a eliminar o dispersar
los grupos de bacterias de manera repentina, sin embargo para efectos de
comparación el número de eventos se reduce a 1 y la probabilidad de que ocurran
pasados un número considerable de pasos de quimio taxis se deja en 0.25.
36
6. Resultados del Proyecto
En esta sección se muestran los resultados de las etapas descritas anteriormente en
la implementación de los algoritmos, creación del campo y demás factores que
intervinieron en la implementación del proyecto y que fueron expuestos en la sección
5 del diseño y ejecución del proyecto. Los algoritmos fueron diseñados en el software
de simulación MATLAB R2016a.
6.1. Elección de estrategias
La Elección de las estrategias a implementar fue basada en estrategias que pudieran
compararse de manera directa y que cumplieran con el objetivo de realizar un barrido
a través de un campo no estructura, como resultado a este ítem; las estrategias que
se implementaron fueron Particle Swarm Optimization “PSO” y Bacterial Foraging
Optimization Algorithm “e.coli”, que cumplían exactamente con los criterios de
comparación y de barrido de un campo no estructurado.
6.2. Creación del campo
La implementación del campo a recorrer fue una de las tareas claves que se realizó,
teniendo en cuenta que cumpliera con el objetivo de ser un campo no estructurado y
que presentara obstáculos aleatorios, de esta manera poder simular un campo real
en donde los robots se vieran enfrentados a este tipo de campos. El campo que se
implementó fue un campo potencial que cumpliera con el requisito de encontrar el
mínimo global, y para la simulación de obstáculos se implementaron funciones
gaussianas que representaban máximos locales en un campo potencial, de esta
manera en la figura 19 se muestra la implementación en Matlab.
Figura 19. Creación campo potencial y funciones gaussianas
37
6.3. Implementación de Algoritmos
Con la implementación del campo que se mencionó en la sección anterior fue posible
realizar la ejecución de los algoritmos, simulando estas estrategias en el software de
simulación MATLAB. Las etapas de implementación de los algoritmos están descritas
en la sección 5 del diseño y ejecución del proyecto, en donde se menciona paso a
paso la ejecución, pasos a seguir y problemas encontrados en la implementación.
6.4. Comparación de estrategias
Como objetivo de este proyecto, la comparación de estas estrategias está regida por
dos tipos de métricas: la primera por el porcentaje del área recorrido por cada
algoritmo y la segunda como el tiempo en la que se realiza dicha ejecución.
Los resultados de estas comparaciones se puede observar a continuación en las
siguientes tablas:
Comparación entre 1 cardumen
Y 1 obstáculo
Tiempo(s) Barrido Zona (%)
PSO 19,84 23,2
E.COLI 136,4 52,7
Comparación entre 1 cardumen
Y 7 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 28,6 36,7
E.COLI 154,9 61,3
Comparación entre 1 cardumen
Y 4 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 20,1 27,4
E.COLI 149,3 55,4
Comparación entre 1 cardumen
10 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 39,12 37,8
E.COLI 165,6 63,4
Tabla 1. Comparación entre algoritmos
Ver Anexo A Tabla 2. Comparación entre algoritmos
Ver Anexo B
Tabla 3. Comparación entre algoritmos
Ver Anexo C
Tabla 4. Comparación entre algoritmos
Ver Anexo D
38
Comparación entre 2 cardumen
Y 1 obstáculo
Tiempo(s) Barrido Zona (%)
PSO 29,7 55,6
E.COLI 182,4 74,4
Comparación entre 2 cardumen
Y 7 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 39,2 59
E.COLI 176,6 67,5
Comparación entre 3 cardumen
Y 1 obstáculo
Tiempo(s) Barrido Zona (%)
PSO 26,6 77,48
E.COLI 209,2 83,2
Comparación entre 3 cardumen
Y 7 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 37,1 56,5
E.COLI 206,3 81,3
Comparación entre 2 cardumen
Y 4 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 31,8 50,84
E.COLI 174,9 71,14
Comparación entre 2 cardumen
10 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 39,9 55,6
E.COLI 183,5 72,3
Comparación entre 3 cardumen
Y 4 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 24 72,2
E.COLI 213,6 74
Comparación entre 3 cardumen
10 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 27,6 75,4
E.COLI 238 81,1
Tabla 5. Comparación entre algoritmos
Ver Anexo E Tabla 6. Comparación entre algoritmos
Ver Anexo F
Tabla 7. Comparación entre algoritmos
Ver Anexo G
Tabla 8. Comparación entre algoritmos
Ver Anexo H
Tabla 9. Comparación entre algoritmos
Ver Anexo I Tabla 10. Comparación entre algoritmos
Ver Anexo J
Tabla 11. Comparación entre algoritmos
Ver Anexo K
Tabla 12. Comparación entre algoritmos
Ver Anexo L
39
Comparación entre 4 cardumen
Y 1 obstáculo
Tiempo(s) Barrido Zona (%)
PSO 32,2 75,1
E.COLI 220 95
Comparación entre 4 cardumen
Y 7 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 35,4 70,42
E.COLI 257,1 87,9
Teniendo en cuenta los resultados obtenidos se puede evidenciar en primera medida
una notable diferencia entre los dos algoritmos; mientras en el algoritmo del PSO el
tiempo oscila entre los 20 y 48 segundos dependiendo del número de cardúmenes
que se crean en el espacio, el algoritmo E.COLI varía entre los 135 y 264 segundos,
observando una notable diferencia entre el tiempo de recorrido de los dos algoritmos.
Por otro lado el porcentaje del barrido de zona en el algoritmo PSO está entre el 24 y
80 porciento, el E.COLI varía entre 56 y 96 porciento.
Los resultados de las simulaciones serán mostrados en la sección de anexos donde
se evidenciara el recorrido y exploración de cada técnica y además observar el
comportamiento que tiene cada una de ellas para recorrer el campo no estructurado.
Las simulaciones fueron hechas en un computador portátil con procesador Inter®
Core(TM) i7-4510 CPU @ 2.60GHz con tarjeta gráfica NVIDIA GEFORCE.
Comparación entre 4 cardumen
Y 4 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 28,3 78,4
E.COLI 248,7 96,04
Comparación entre 4 cardumen
10 obstáculos
Tiempo(s) Barrido Zona (%)
PSO 47,3 78,2
E.COLI 263,4 92,4
Tabla 13. Comparación entre algoritmos
Ver Anexo M Tabla 14. Comparación entre algoritmos
Ver Anexo N
Tabla 15. Comparación entre algoritmos
Ver Anexo O
Tabla 16. Comparación entre algoritmos
Ver Anexo P
40
7. Impacto Social
Este proyecto de grado es un acercamiento a la solución del problema de localización
y barrido de un campo no estructurado, es primordial tener en cuenta que este ha sido
un problema durante las últimas décadas, pues el reconocimiento de objetos en
campos que no pueden ser explorados por los humanos es sumamente importante
para la sociedad. La robótica e inteligencia artificial son los mecanismos apropiados
para buscar una solución eficiente y generar un gran impacto en esta área.
Este proyecto de grado ofrece una posible solución a la sociedad con el problema de
localización de minas en zonas minadas, donde es imposible para un humano hacer
un barrido completo del área debido a que podría poner en riesgo su vida lo que
genera un gran problema, es así que el trabajo con robots es sumamente importante,
pues evitará el riesgo que tengan los humanos al recorrer áreas minadas y
seguramente con la robótica el peligro podría llegar a ser nulo.
Otra posible solución que ofrece este proyecto es en la búsqueda de personas en
áreas de muy poco espacio, en donde la única alternativa es poder recorrer el área
con múltiples robots que indiquen la posición correcta en donde se encuentre algún
ser humano, este trabajo es elemental que se realice con robots, puesto que hará un
barrido completo de la zona en donde se cuente con la ayuda de sensores que
permitan una búsqueda más rápida y eficiente.
41
8. Conclusiones
o Los sistemas bio-inspirados presentados e implementados en este proyecto,
permiten ofrecer una solución a la localización y exploración de un área no
estructurada usando multiagentes que puedan comunicarse y coordinarse
entre ellos, para lograr un barrido del área y permitir recorrerlo en su totalidad.
Es por eso que es necesario tener en cuenta diversos factores o problemas
que puedan presentarse para la ejecución del proyecto.
o El proceso de la elección de las estrategias es sumamente importante, pues
se tiene que tener en cuenta factores claves como que los algoritmos se
puedan adaptar de una manera similar a la exploración de un campo, que
cumplan con los requisitos de comparación entre ellas y que tengan como idea
central la comunicación y coordinación entre distintos robots (swarming),
además, de su condición de inspiración en los mecanismos que se hallan en
la naturaleza, de esta manera y teniendo en cuenta estos factores, los
algoritmos PSO y E.coli fueron los seleccionados para la implementación y así
poder brindar una solución eficiente a la exploración de campos no
estructurados.
o Para tener una base de comparación exacta, fue necesario implementar los 2
algoritmos con un campo potencial y una serie de obstáculos aleatorios, que
cumplieran para los 2 escenarios las mismas condiciones, de esta manera
poder cumplir con el objetivo principal de una comparación de área recubierta
por cada algoritmo. Teniendo en cuenta este factor fue mucho más eficiente la
implementación de los 2 algoritmos para este proyecto de grado.
o Durante la implementación de los algoritmos, se observó que para la métrica
del barrido de zona, fue necesario discretizar el campo de manera que hubiese
un número finito de coordenadas en donde se pudiera conocer el área total del
campo. La solución planteada en el proyecto fue dividir el campo en cuadrados
de 100x100, cada cuadrado fue dividido en la mitad a lo largo y a lo ancho de
cada uno, de tal motivo que cada posición (x,y) sea la mitad del cuadrado y así
este pueda ser contado como una pequeña fracción del campo total.
o Como se sabe, un robot está compuesto por sensores que ayudan a realizar
las tareas de la manera más rápida y eficiente. Es por esto, que se vio la
necesidad de simular un sensor que se acercara a la realidad en cuanto a los
sistemas de búsqueda y visualización de los robots en un campo no
estructurado.
42
o Mediante la implementación de los algoritmos se encontró que había un
problema al encontrar la meta, pues estos algoritmos tienen como objetivo
encontrar el mínimo global de una función, en la ejecución de las pruebas se
logró observar que las partículas en ciertos momentos no llegaban al mínimo
global y se detenían en un mínimo local, lo que generaba que la simulación no
terminara y entrara en un bucle y debido a esto, que el área de barrido fuera
menor en comparación a las demás pruebas. Se plantea como trabajo futuro
la solución de este problema y así poder conseguir mejores resultados en los
dos algoritmos.
o Como resultado de la comparación de los dos algoritmos se evidenció que el
algoritmo E.coli realiza una mayor exploración debido a su reproducción y
quimio taxis que ofrece un movimiento aleatorio y la independencia de cada
una de las partículas. De esta manera fue posible observar en los resultados
que el algoritmo e.coli es mucho más eficiente en la exploración que el
algoritmo PSO en las mismas condiciones (cantidad de cardúmenes y
obstáculos), otra comparación que se observó en los resultados fue el tiempo
de ejecución de cada algoritmo para la realización de la búsqueda, en este
ítem el algoritmo PSO tuvo gran ventaja en comparación al e.coli y los
resultados, esto se puede observar en la sección de resultados, donde se
presentaron las tablas con los diferentes datos y también en la sección de
anexos, donde se muestra el recorrido de cada algoritmo.
43
9. Trabajo Futuro
En primera medida como trabajo futuro se quiere lograr que estas técnicas simuladas
sean implementadas en plataformas robóticas con el objetivo de poder tener datos
reales en la localización y pueda ser un proyecto que beneficie a la sociedad en los
problemas de búsqueda de objetos o personas y evasión de obstáculos para recorrer
un campo no estructurado. El estudio y simulaciones realizadas dan un primer atisbo
a que técnicas son las adecuadas para el barrido de zonas abiertas desconocidas,
descartando algunas que tienen limitaciones en cuanto a la complejidad de problemas
a tratar, el campo y los caminos que pueden recorrer y la viabilidad de implementación
por costes computacionales muy robustos que pueden generar problemas a la hora
de su ejecución.
Mediante la implementación de los algoritmos hechos, se observó un problema en el
algoritmo PSO el cual es que en algunos casos las partículas quedan atrapados en
mínimos locales y no encuentran el mínimo global. Como trabajo futuro se quiere
implementar una solución a este problema, evitando que las partículas se queden
atrapadas en estos mínimos locales y puedan llegar hasta el mínimo global sin ningún
problema y en el menor tiempo posible.
44
10. Bibliografía
[1] P. C. -Y. Sheu, «Intelligent robotic planning system,» World Scientific, 1993.
[2] A. P. Gonzales, «Exploración completa basada en comportamientos cooperativos para
un agente autónomo móvil,» Escuela Técnica Superior de ingeniería de
Telecomunicaciones, p. 358, 2008.
[3] D. A. C. Rincón, «Dispositivos para la detección y desactivación de artefactos
explosivos,» Superintendencia de Industria y Comercio, p. 81, 2004.
[4] D. c. m. P. d. l. República, «Dirección de desminado humanitario,» 2016.
[5] J. Prospero C. Naval, «Dispersal, Queueing and Navigation of Swarm Robots using
Color and Geometric Constraints,» IEEE, 2010.
[6] J. Prospero C. Naval, «Dispersal, Queueing and Navigation of Swarm Robots using
Color and Geometric Constraints,» IEEE, 2010.
[7] L. S. M. a. L. Chaimowicz, «No Robot Left Behind: Coordination to Overcome Local
Minima in Swarm Navigation,» IEEE International Conference on Robotics and
Automation, 2008.
[8] L. M. y. J. Y. Shirong Liu, «Path Planning Based on Ant Colony Algorithm and
Distributed Local Navigation for Multi-Robot Systems,» International Coference on
Mechatronics and Automation, pp. 1733-1738, 2006.
[9] L. R. K. y. D. N. Chiranjib Guha Majumder, «Bee Foraging Inspired Multi-Agent Optimal
Motion Planning Analysis in a simulated-mobile environment,» Indian Control
Conference (ICC) IEEE, pp. 39-46, 2016.
[10] W. H. Z. W. Xuzhi Chen, «Research of UAV’s Multiple Routes Planning based on Multi-
Agent Particle Swarm Optimization,» Fourth International Conference on INtelligent
Control and Information Processing (ICICIP) IEEE, pp. 765-769, 2013.
[11] G. B. A. C. P. R. R. Cassinis, «Strategies for navigation of robot swarms to be used in
landmines detection,» IEEE, pp. 211-218, 1999.
[12] D. F. S. Vignesh Kumar, «Foraging in Ant colonies applied to the Mine Detection
Problem,» RIT Schilar Works, p. 8, 2003.
[13] E. C. Sahin, «Ant Colony Optimization based Swarms: Implementation for the Mine
Detection Application,» IEEE, p. 6, 2004.
[14] G. G. L. Antonio, «Diseño y contrucción de un sistema robótico para la exploración de
campos sembrados con minas antipersona,» Umbral Científico, nº 13, p. 8, 2008.
[15] O. K. a. Y. E. S. Nazlibilek, «Mine Identification and Classification by Mobile,» IEEE,
vol. 3, nº 60, p. 9, 2011.
[16] N. Palmieri, «A Swarm-based Robot Team Coordination Protocol,» IEEE, p. 7, 2012.
[17] R. B. R. A. M. M. Cobo Ortega Angel, «Descubirmiento de Conocimiento,» Rect, vol.
10, p. 20, 2009.
[18] N. S. a. S. Annamalai, «A hierarchical heterogeneous ant colony optimization based
approach for efficient action rule mining,» ELSEIVER, vol. 29, p. 12, 2016.
45
[19] D. M. Gordon, «National Geographic,» 7 10 2016. [En línea]. Available:
http://www.nationalgeographic.com.es/mundo-ng/grandes-reportajes/teoria-de-los-
enjambres_1452.
[20] R. C. P. Lima, «Sistema de exploración de terrenos con robots móviles: Aplicación en
tareas de detección y localización de minas anipersonales,» Universidad Complutense
de Madrid, p. 4, 2011.
[21] A. O. Baturone, Robótica manipuladores y robots móviles, Marcombo, 2001.
[22] F. S. Caparrini, «PSO: Optimización por enjambres de partículas,» Sevilla, 2016.
[23] S. Das, «Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis,
and Applications,» Norwegian University of Science and Technology, Noruega, 2003.
[24] S. h. Z. y. J. r. Evans, «Heuristic Optimization: Why, when and how to use it,»
Interfaces, 1981.
[25] A. H. Sanchez, «Tecnicas metaheuristicas,» Universidad Politecnica de Madrid,
Madrid, España, 2001.
[26] H. Y. W. Sadig M Sait, «Iterative Computer Algorithms with Applications in Engineering:
Solving Combinatorial Optimization Problems,» Computer Society Press, 2000.
[27] A. E. Z. E. M. T. O. Ramón Alfonso Galego Rendón, «Técnicas Heurísticas y
Metaheurísticas de Optimización,» Universidad Tecnológica de Pereira, p. 280, 2003.
[28] S. D. S.N. Sivanandam, Introduction to Genetic Algorithms, India: Springer, 2008.
[29] F. G. Belén Melián Bautista, «Introducción a la búsqueda Tabu,» Escuela Técnica
Superior de Ingeniería Informática, p. 36, 2000.
[30] M. B. Marco Dorigo, «Ant Colony Optimization, artificial ants as Computacional
Intelligents Technique,» Université libre de Bruxelles , p. 14, 2006.
[31] H. H. S. A. TAN Guan-Zheng, «Ant Colony System Algorithm for Real-Time Globally,»
IEEE, vol. 33, nº 3, p. 7, 2007.
[32] R. A. G. Rendon, «Tecnicas Heurísticas y metaheurísticas de Optimización,» Pereira,
Risaralda, 2003, pp. 210-230.
46
Anexos Anexo A. Simulaciones y resultados de las estrategias Tabla 1
Simulación PSO Tabla 1
Figura 20. Simulación Algoritmo PSO Tabla 1
Simulación e.coli Tabla 1
Figura 21. Simulación Algoritmo e.coli Tabla 1
47
Anexo B Simulaciones y resultados de las estrategias Tabla 2
Simulación PSO Tabla 2
Figura 22. Algoritmo PSO Tabla 2
Simulación e.coli Tabla 2
Figura 23. Algoritmo e.coli Tabla 2
48
Anexo C. Simulaciones y resultados de las estrategias Tabla 3
Simulación PSO Tabla 3
Figura 24. Algoritmo PSO Tabla 3
Simulación e.coli Tabla 3
Figura 25 Algoritmo e.coli Tabla 3
49
Anexo D. Simulaciones y resultados de las estrategias Tabla 4
Simulación PSO Tabla 4
Figura 26. Simulación Algoritmo PSO Tabla 4
Simulación e.coli Tabla 4
Figura 27. Simulación Algoritmo e.coli Tabla 4
50
Anexo E. Simulaciones y resultados de las estrategias Tabla 5
Simulación PSO Tabla 5
Figura 28. Simulación Algoritmo PSO Tabla 5
Simulación e.coli Tabla 5
Figura 29. Simulación Algoritmo e.coli Tabla 5
51
Anexo F. Simulaciones y resultados de las estrategias Tabla 6
Simulación PSO Tabla 6
Figura 30 Simulación Algoritmo PSO Tabla 6
Simulación e.coli Tabla 6
Figura 31 Simulación Algoritmo e.coli Tabla 6
52
Anexo G. Simulaciones y resultados de las estrategias Tabla 7
Simulación PSO Tabla 7
Figura 32. Simulación Algoritmo PSO Tabla 7
Simulación e.coli Tabla 7
Figura 33. Simulación Algoritmo e.coli Tabla 7
53
Anexo H. Simulaciones y resultados de las estrategias Tabla 8
Simulación PSO Tabla 8
Figura 34. Simulación Algoritmo PSO Tabla 8
Simulación e.coli Tabla 8
Figura 35. Simulación Algoritmo e.coli Tabla 8
54
Anexo I. Simulaciones y resultados de las estrategias Tabla 9
Simulación PSO Tabla 9
Figura 36. Simulación Algoritmo PSO Tabla 9
Simulación e.coli Tabla 9
Figura 37. Simulación e.coli Tabla 9
55
Anexo J. Simulaciones y resultados de las estrategias Tabla 10
Simulación PSO Tabla 10
Figura 38. Simulación PSO Tabla 10
Simulación e.coli Tabla 10
Figura 39. Simulación Algoritmo e.coli Tabla 10
56
Anexo K. Simulaciones y resultados de las estrategias Tabla 11
Simulación PSO Tabla 11
Figura 40. Simulación Algoritmo PSO Tabla 11
Simulación e.coli Tabla 11
Figura 41. Simulación Algoritmo e.coli Tabla 11
57
Anexo L. Simulaciones y resultados de las estrategias Tabla 12
Simulación PSO Tabla 12
Figura 42. Simulación Algoritmo PSO Tabla 12
Simulación e.coli Tabla 12
Figura 43. Simulación Algoritmo e.coli Tabla 12
58
Anexo M. Simulaciones y resultados de las estrategias Tabla 13
Simulación PSO Tabla 13
Figura 44. Simulación Algoritmo PSO Tabla 13
Simulación e.coli Tabla 13
Figura 45. Simulación Algoritmo e.coli Tabla 13
59
Anexo N. Simulaciones y resultados de las estrategias Tabla 14
Simulación PSO Tabla 14
Figura 46. Simulación Algoritmo PSO Tabla 14
Simulación e.coli Tabla 14
Figura 47. Simulación Algoritmo e.coli Tabla 14
60
Anexo O. Simulaciones y resultados de las estrategias Tabla 15
Simulación PSO Tabla 15
Figura 48. Simulación Algoritmo PSO Tabla 15
Simulación e.coli Tabla 15
Figura 49. Simulación Algoritmo e.coli Tabla 15
61
Anexo P. Simulaciones y resultados de las estrategias Tabla 16
Simulación PSO Tabla 16
Figura 50. Simulación Algoritmo PSO Tabla 16
Simulación e.coli Tabla 16
Figura 51. Simulación Algoritmo e.coli Tabla 16