Desarrollo de un algoritmo planificador de

rutas con capacidad de implementación en

diversas aplicaciones de la robótica móvil.

Edward Andrés González Ríos

Proyecto de grado para optar al título de
Ingeniero Electrónico

Universidad Tecnológica de Pereira

Facultad de Ingenierías
Ingeniería Electrónica
Pereira, Colombia
Octubre 2015
Desarrollo de un algoritmo planificador de
rutas con capacidad de implementación en
diversas aplicaciones de la robótica móvil.

Por:
Edward Andrés González Ríos
Cód: 1088301352

Proyecto de grado para optar al título de

Ingeniero Electrónico

Director:
M.Sc. José Andrés Chaves Osorio
Profesor del Programa Ingeniería Electrónica
Ingeniero Electricista

Universidad Tecnológica de Pereira

Facultad de Ingenierías
Ingeniería Electrónica
Pereira, Colombia
Octubre de 2015
 Nota de aceptación:

___________________________________

___________________________________

___________________________________

___________________________________

Director:

___________________________________

Jurado:

___________________________________

Octubre de 2015
 Dedicatoria

Que la dedicatoria de este trabajo de grado sea un pequeño reconocimiento y agradecimiento

a las dos personas que han sido mi apoyo, inspiración y motor de mi vida. Mis padres: Magda
Cely Ríos Pineda y Guillermo González Rodríguez.

Edward Andrés González Ríos.

 Agradecimientos

Gracias a Dios por todo lo bueno de mi vida, por mi familia y amigos...

Son muchas las personas a las que debo agradecer por su ayuda y colaboración durante la ejecución de
este proyecto y de toda mi carrera.

Para empezar un especial agradecimiento al M.Sc. José Andrés Chaves Osorio quien ha sido el director
de este proyecto, porque a pesar de sus múltiples ocupaciones siempre ha tenido tiempo y disposición para
guiar en todo momento el desarrollo y evolución del mismo; al M Sc. Mauricio Fernando Jaramillo Morales
por su respaldo y especialmente por el apoyo en la generación del entorno; al Ph.D Juan Bernardo Gómez
Mendoza por sus aportes y comentarios; al M.Sc. Edwin Andrés Quintero Salazar director del programa de
ingeniería electrónica por su acompañamiento durante toda la carrera.

A mi familia que me ha respaldado en todo momento durante el desarrollo de éste pregrado, mis her-
manas, tíos, tías, primas y especialmente a mis padres quienes siempre han estado presentes sin importar
la dificultad o complejidad de la situación en la que me encuentre; a mi novia por su paciencia, apoyo y
palabras de motivación cuando las he necesitado; a los miembros del grupo de investigación robótica aplicada
que con sus aportes grandes o pequeños han contribuido en el mejoramiento del presente proyecto y a todas
las personas que han aportado para alcanzar los objetivos de éste pregrado.

Por último a mis amigos y compañeros que de una u otra manera han aportado en mi crecimiento personal
y académico .

Edward Andrés González Ríos

Índice general

1. DESCRIPCIÓN DEL PROYECTO 10

1.1. DEFINICIÓN DEL PROBLEMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2. JUSTIFICACIÓN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3. OBJETIVOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1. OBJETIVO GENERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2. OBJETIVOS ESPECÍFICOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2. MARCO REFERENCIAL 13
2.1. MARCO CONCEPTUAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1. Búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.2. Inteligencia Artificial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.3. Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.4. Algoritmos para planificación de rutas . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.5. Agente inteligente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.6. Función heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2. MARCO TEÓRICO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1. Búsqueda a ciegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1.1. Búsqueda en Amplitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1.2. Búsqueda en Profundidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1.3. Búsqueda en Profundidad Progresiva . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1.4. Búsqueda Bidireccional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2. Búsqueda informada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2.1. Búsqueda Incremental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2.2. Búsqueda Heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2.3. Búsqueda Incremental Heurística . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3. MARCO HISTÓRICO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1. Algoritmo BFS (Breadth First Search) . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.2. Algoritmo DFS (Depth First Search) . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.3. Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.4. Algoritmo A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.5. Algoritmo LPA* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.6. Algoritmo D* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7. Algoritmo D* Lite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3. DESARROLLO DEL PROYECTO 23

3.1. SELECCIÓN DEL AMBIENTE DE DESARROLLO . . . . . . . . . . . . . . . . . . . . . . . 23
3.2. CREACIÓN DEL ENTORNO DE EXPLORACIÓN . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1. Delimitación del entorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2. Generación de entorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3. EL AGENTE INTELIGENTE O EXPLORADOR . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.1. Sensores virtuales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.2. Aprendizaje del agente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

vi
ÍNDICE GENERAL ÍNDICE GENERAL

3.4. DESARROLLO DEL ALGORITMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.4.1. Algoritmo Best-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.1.1. Ejecución del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4.2. Algoritmo A*(A-star) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5. DISEÑO DE UN AGENTE DE ROBÓTICO . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5.1. Diseño mecánico del agente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5.1.1. La base del agente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5.1.2. Las ruedas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5.2. Diseño electrónico del agente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5.2.1. Alimentación del sistema y circuito controlador de los motores . . . . . . . . 41
3.5.2.2. Sistema microcontrolado del agente . . . . . . . . . . . . . . . . . . . . . . . 41
3.5.3. Ensamble del sistema y construcción física . . . . . . . . . . . . . . . . . . . . . . . . . 43

4. PRUEBAS Y RESULTADOS 45

5. CONCLUSIONES Y FUTUROS TRABAJOS 56

5.1. CONCLUSIONES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.2. FUTUROS TRABAJOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Bibliografía 58

6. ANEXOS 62
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.1.1. Best-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.1.2. A* Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.1.3. Generación del entorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

vii
Índice de figuras

2.1. Tipos de grafos clasificados según sus aristas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2. Clasificación tipos de búsqueda. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3. Diagrama de estados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4. Diagrama de estados explorado por Amplitud. . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5. Diagrama de estados explorado por Profundidad. . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6. Rejilla simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7. Juego del 8 Puzzle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1. Entorno de exploración. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2. Matriz del entorno de exploración. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3. Función para la generación del entorno. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4. Ejemplo generación del entorno. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.5. Modelo de un agente que interactuá con el entorno. . . . . . . . . . . . . . . . . . . . . . . . . 26
3.6. Dirección de los sensores del agente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.7. Modelo de un agente que interactuá y aprende del entorno. . . . . . . . . . . . . . . . . . . . 27
3.8. Clase en MATLAB para definir los agentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.9. Atributos de un agente en medio de una búsqueda. . . . . . . . . . . . . . . . . . . . . . . . . 28
3.10. Atributo “vecinos” en el agente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.11. Primera capa del atributo Mexplorados en medio de una búsqueda. . . . . . . . . . . . . . . . 30
3.12. Segunda capa del atributo Mexplorados en medio de una búsqueda. . . . . . . . . . . . . . . 30
3.13. Función principal para el algoritmo Best-First Search. . . . . . . . . . . . . . . . . . . . . . . 32
3.14. Función Main para el algoritmo Best-First Search. . . . . . . . . . . . . . . . . . . . . . . . . 33
3.15. Entorno de ejemplo para el ejemplo del algoritmo Best-First Search . . . . . . . . . . . . . . . 33
3.16. Representación matricial del entorno antes del primer movimiento. . . . . . . . . . . . . . . . 34
3.17. Ejemplo para el algoritmo A*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.18. Primera exploración del agente con el algoritmo A*. . . . . . . . . . . . . . . . . . . . . . . . 36
3.19. Segunda exploración del agente con el algoritmo A*. . . . . . . . . . . . . . . . . . . . . . . . 37
3.20. Tercera exploración del agente con el algoritmo A*. . . . . . . . . . . . . . . . . . . . . . . . . 37
3.21. Ruta encontrada por el agente utilizando el algoritmo A*. . . . . . . . . . . . . . . . . . . . . 38
3.22. Ruta optimizada después de la exploración y planificación. . . . . . . . . . . . . . . . . . . . . 38
3.23. Diseño mecánico del agente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.24. Motor 37Dx54L con encoder de Pololu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.25. Base del agente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.26. Ruedas de neopreno. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.27. Circuito controlador para los motores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.28. Arduino Mega 2560. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.29. Sensores ultrasonicos para la percepción del entorno. . . . . . . . . . . . . . . . . . . . . . . . 42
3.30. Modulo de comunicación inalambrica ESP8266. . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.31. PCB principal para el agente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.32. Base del agente robótico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.33. Agente inteligente robótico construido. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.1. Escenario 1 prueba 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

viii
ÍNDICE DE FIGURAS ÍNDICE DE FIGURAS

4.2. Escenario 1 prueba 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.3. Escenario 2 prueba 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.4. Escenario 2 prueba 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5. Escenario 3 prueba 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.6. Escenario 3 prueba 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.7. Escenario 4 prueba 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.8. Escenario 4 prueba 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.9. Escenario 5 prueba 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.10. Escenario 5 prueba 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

ix
Capítulo 1

DESCRIPCIÓN DEL PROYECTO

1.1 DEFINICIÓN DEL PROBLEMA

Son muchas las situaciones durante la vida de un ser vivo en las cuales debe realizar tareas de exploración
y planificación de un camino, estas situaciones se presentan de manera cotidiana y se pueden apreciar por
ejemplo en la forma en que un enjambre de abejas se desplaza de un lugar a otro y reajusta su ruta al en-
contrarse con algún obstáculo, o en hecho de que una persona planee un recorrido que le permita desplazarse
de la casa a la oficina y ejecute lo planeado haciendo uso de una ruta dentro de la ciudad para llegar mas
rápido o recorrer la menor distancia. En la vida diaria de un ser humano es muy común realizar tareas de
exploración y planificación de rutas, actividad que puede realizar muchas veces en un día, incluso de manera
inconsciente.

Sin embargo explorar y planificar un ruta se puede convertir en una tarea de vida o muerte cuando el
terreno donde se debe realizar esta tarea es total o parcialmente desconocido e implica un riesgo vital, éste
es el caso de las personas que pertenecen a organismos de búsqueda y rescate quienes deben encontrar la
manera de desplazarse entre dos puntos y que se pueden encontrar en medio de condiciones de alto riesgo
para la vida de los rescatistas, como cuando se exploran estructuras colapsadas en busca de sobrevivientes;
ya que en éste caso una mala decisión puede acarrear con la pérdida de una o muchas vidas.

Otra situación es la que viven los miembros de las fuerzas armadas de Colombia, especialmente los en-
cargados de inspeccionar terrenos que se sospechan pueden estar minados, donde la tarea de exploración y
planificación de la ruta para atravesar este tipo de terrenos puede suponer la pérdida de extremidades o
incluso la vida. Las personas que realizan esta tarea comúnmente llevan un uniforme especial que trata de
proteger parcialmente su integridad física en caso de una detonación accidental y algún dispositivo detector
el cual no puede garantizar que se detecten el 100 % de las minas enterradas en la zona; también existen otros
sistemas de exploración como es el caso de los sistemas teleoperados, en los cuales un operario entrenado ma-
nipula una plataforma robótica [1](a media o corta distancia) dotada con algún sensor que le permita detectar
los artefactos explosivos, aún así sigue siendo posible que en caso de una detonación accidental las perso-
nas que estén manipulando la plataforma al encontrarse en la zona de la explosión sufran daños físicos graves.

Existen también otros problemas similares como el caso de planificar una evacuación [2], encontrar el
camino en una hora de alta congestión vial a una clínica u hospital cercano y otra serie de problemas de
planificación de rutas.

10
1.2. JUSTIFICACIÓN CAPÍTULO 1. DESCRIPCIÓN DEL PROYECTO

1.2 JUSTIFICACIÓN
La posibilidad de implementar un algoritmo capaz de dotar de inteligencia a un sistema robótico que
pueda desplazarse y percibir su entorno (que de ahora en adelante se conocerá como un agente inteligente),
se convierte en un recurso valioso para la robótica móvil y la sociedad al aplicarse para realizar tareas de
manera autónoma, algunas de las cuales pueden ser demasiado complejas o peligrosas para ser desarrolladas
por un ser vivo.

En el área de la inteligencia artificial1 aplicada a la planificación de rutas y especialmente cuando se

hace uso de funciones heurísticas, encontrar una ruta que una dos puntos conocidos como inicio y destino
no garantiza directamente que se encuentre la mejor ruta; sin embargo el hecho de encontrar un camino
que permita conectar dos puntos se vuelve una solución valiosa dependiendo la situación donde se realice la
planificación.

Otro aspecto relevante a ser considerado, es cuando se realizan actividades que generan situaciones de
alto estrés para los involucrados como es el caso de explorar un estructura colapsada, donde se pierde parte
de la capacidad de razonar de manera rápida y coherente lo que genera nuevos riesgos, al utilizar un sistema
robótico dotado con IA se elimina el error humano causado por el estrés y otros factores emocionales debido a
que no cuentan con emociones ni sentimientos, lo que limita la toma de decisiones únicamente a las variables
físicas que se puedan percibir en el terreno de acuerdo a cada situación, aún cuando el escenario cambie
constantemente .

1 Inteligencia artificial o IA (ver Sección 2.1.2)

11
1.3. OBJETIVOS CAPÍTULO 1. DESCRIPCIÓN DEL PROYECTO

1.3 OBJETIVOS
1.3.1. OBJETIVO GENERAL
Desarrollar un algoritmo para la planificación de rutas con capacidad de implementación en diversas
aplicaciones de la robótica móvil.

1.3.2. OBJETIVOS ESPECÍFICOS

Estudiar el estado del arte de los algoritmos para la planificación de rutas utilizados para resolver
diferentes problemas en entornos reales, virtuales, estáticos y dinámicos.
Desarrollar un escenario de prueba en el cual se puedan ajustar las características y condiciones (tamaño,
dinámica y forma de los obstáculos ) del entorno que permita la implementación de agentes inteligentes
programados para la exploración y planificación de rutas.

Desarrollar un agente inteligente en el cual se puedan implementar diferentes algoritmos de búsqueda

heurística sensorialmente capaz de determinar las condiciones del escenario donde se realiza la explo-
ración y planificación de la ruta.
Proveer las bases para que el algoritmo desarrollado pueda llegar a ser implementado en una plataforma
móvil para resolver tareas como la de explorar de un campo minado y planificar una ruta libre (si existe).

12
Capítulo 2

MARCO REFERENCIAL

2.1 MARCO CONCEPTUAL

Para este proyecto es importante definir algunos conceptos que se consideran claves para el desarrollo del
mismo, como son: Búsqueda, Inteligencia Artificial, Grafos, Algoritmos para planificación de rutas, Agente
inteligente y Función heurística.

2.1.1. Búsqueda
Según el diccionario de la Real Academia de la Lengua Española [3]:
1. Hacer algo para hallar a alguien o algo.
2. Hacer lo necesario para conseguir algo.
3. Ir por alguien o recogerlo para llevarlo o acompañarlo a alguna parte.

2.1.2. Inteligencia Artificial

La inteligencia artificial o “IA” por sus siglas en Español, es una parte de la ciencia de la computación
que trata de darle a una máquina un conjunto de características propias de un ser humano [4], como son:
la capacidad de entender un lenguaje, aprender, resolver problemas, entre otras [5] (por tal razón el autor
considera que este es el concepto más importante en el desarrollo del presente trabajo). La principal motivación
para dotar una máquina con este tipo de características típicas de los humanos parte de la necesidad de hacer
más fácil o desarrollar con mayor rapidez tareas que pueden ser repetitivas o peligrosas como [6]:
Resolver algunos problemas difíciles en química, biología, arqueología, ingeniería, medicina entre otras
áreas del conocimiento al nivel de un humano experto.
Manipular dispositivos robóticos para realizar tareas que puedan ser peligrosas para un ser humano
como la exploración de zonas minadas o estructuras colapsadas.
Realizar tareas de censado y toma de decisiones que puedan ser repetitivas en el tiempo.

2.1.3. Grafos
Los grafos son una herramienta usada para modelar fenómenos discretos y son fundamentales para la
comprensión y resolución de problemas como también para el análisis de algoritmos; en matemáticas, inge-
nierías y ciencias de la computacion, los grafos son colecciones de objetos llamados vértices (estados o nodos)
conectados por líneas llamas aristas que son el camino establecido para pasar de un vértice a otro [7].

Utilizando grafos se pueden modelar:

13
2.1. MARCO CONCEPTUAL CAPÍTULO 2. MARCO REFERENCIAL

Las conexiones de una red de computadoras.

Rutas entre ciudades.
Recorridos turísticos.
Problemas lógicos.

Dependiendo el tipo de problema que se desee modelar se encuentran diferentes tipos de grafos, a continuación
en la Figura 2.1, se presentan 3 tipos de grafos clasificados según sus aristas.

(a) Grafo dirigido. (b) Grafo bidireccional. (c) Grafo ponderado.

Figura 2.1: Tipos de grafos clasificados según sus aristas.

A continuación se describe cada uno de los grafos mostrados anteriormente:

Grafo dirigido: Para este tipo de grafo cada arista incluye una flecha que indica el sentido en que se
puede dar el cambio de un estado a otro, en la Figura 2.1a, se puede observar este tipo de grafo.

Grafo bidireccional: En los grafos bidireccionales las aristas que unen los vértices no poseen ninguna
flecha tal como se observa en la Figura 2.1b, el hecho de que la arista no tenga ningún indicador de
sentido, quiere decir que el desplazamiento de un estado a otro se puede realizar en ambos sentidos.
Grafos ponderados: En esta clase de grafo las aristas tienen un valor o una condición, como por ejemplo
las que se muestran en la Figura 2.1c, las cuales se deben satisfacer para que sea posible realizar un
desplazamiento entre estados.

2.1.4. Algoritmos para planificación de rutas

Los algoritmos para la planificación de rutas tienen como finalidad explorar un espacio del cual se tiene
poca o ninguna información con el fin de encontrar una ruta que pueda conectar dos puntos coordenados;
para el desarrollo del proyecto se considerarán espacios bidimensionales ubicados sobre el plano X, Y con
el fin de simplificar las tareas de búsqueda. Se utilizará [Xs , Ys ] y [Xg , Yg ], definiéndose el primer par de
coordenadas como el punto de inicio y el otro par como el punto final, donde:
X y Y denotan la abscisa y la ordenada de un par de puntos coordenados en el plano bidimensional.

El subíndice s viene de start, empezar en Inglés, e indica el punto inicial.

El subíndice g viene de goal, meta en Inglés, e indica el punto final o punto a alcanzar.

2.1.5. Agente inteligente.

Un agente inteligente se puede definir como una entidad capaz de percibir el espacio donde se encuentra
y en consecuencia tomar decisiones, las cuales se pueden suponer como respuestas racionales generadas por
la percepción de las condiciones del entorno donde se encuentra dicho agente. En computación, esta entidad
puede ser un sistema electrónico, un sistema lógico o un ser humano [8].

14
2.2. MARCO TEÓRICO CAPÍTULO 2. MARCO REFERENCIAL

2.1.6. Función heurística

Una función heurística, es una función lógica o matemática que al ser alimentada por un conjunto de
variables produce una salida que puede ser la solución a un problema dado; para el caso de la planificación
de rutas, la función heurística es la encargada de decidir cual es el mejor paso o cuales son los siguientes
mejores pasos (de acuerdo a la función que se halla programado); sin embargo es importante tener en cuenta
que el uso de una función heurística no garantiza que se encuentre una solución o que la solución dada sea la
mejor, esto dependerá del nivel de complejidad con el que sea desarrollada.

2.2 MARCO TEÓRICO

Dentro de la literatura se encuentran diferentes tipos de algoritmos de búsqueda, los cuales se pueden
clasificar como se muestra en la Figura 2.2. Es importante aclarar que para el desarrollo del proyecto se
trabajará sobre búsqueda heurística, sin embargo en esta sección también se explicará en que consisten los
otros tipos de búsqueda.

Figura 2.2: Clasificación tipos de búsqueda.

2.2.1. Búsqueda a ciegas

La estrategia de búsqueda a ciegas también conocida como búsqueda exhaustiva, se implementa cuando
no se tiene ninguna información del entorno que se esta explorando, solo se conoce si la posición actual es el
estado deseado y cuantos posibles sucesores se pueden explorar partiendo del estado actual. Si se encuentra
la meta, la búsqueda termina pero de lo contrario el algoritmo seguirá buscando en todos los posibles estados
no explorados; para resolver los problemas en los que se necesita de la búsqueda a ciegas se utilizan diferentes
tipos de búsqueda como los que se presentan a continuación:

2.2.1.1. Búsqueda en Amplitud

También conocida como búsqueda en anchura, consiste en visitar todos los estados sucesores del estado
inicial, si ninguno de los estados visitados es el estado deseado, se exploran todos los descendientes de estos
últimos y así sucesivamente hasta encontrar el deseado (si existe), o hasta encontrar que no quedan mas
nodos por recorrer (es decir se recorrieron todos los nodos)[9]. Este tipo de búsqueda en algunos casos es
llamada búsqueda por niveles y por lo general cada nivel se explora de izquierda a derecha1 . En la Figura
2.3, se muestra un diagrama de estados, donde cada estado esta representado por letras mayúsculas y se
considera el estado A (marcado con verde) como el estado inicial y el estado U (marcado con rojo) como el
estado final o deseado.
1 Explorar de izquierda a derecha es una convención tomada comúnmente por diferentes autores, sin embargo no es una camisa

de fuerza, el sentido de la exploración también se puede realizar de derecha a izquierda.

15
2.2. MARCO TEÓRICO CAPÍTULO 2. MARCO REFERENCIAL

Figura 2.3: Diagrama de estados.

Al realizar la búsqueda en amplitud en el diagrama de estados presentado anteriormente, se puede observar

una secuencia de exploración como la que se presenta en la Figura 2.4, donde los estados con contorno negro
son estados explorados mientras que los marcados en gris solo han sido vistos pero no visitados, se puede
observar que antes de encontrar el estado deseado se exploraran una gran cantidad de estados.

Figura 2.4: Diagrama de estados explorado por Amplitud.

16
2.2. MARCO TEÓRICO CAPÍTULO 2. MARCO REFERENCIAL

2.2.1.2. Búsqueda en Profundidad

La búsqueda en profundidad es muy parecida a la búsqueda en amplitud, ya que es posible que se deban
explorar muchos estados antes de encontrar el deseado. En este tipo de búsqueda se explora uno de los
estados, si este no es el estado deseado, se explora uno de sus sucesores y así sucesivamente hasta encontrar el
estado deseado, si no se alcanza la solución y se llega a un callejón sin salida, el sistema genera un retroceso
estado previo 2 , si en este estado no quedan nuevos sucesores para explorar se sigue retrocediendo hasta
encontrar nuevos estados sucesores para explorar o hasta encontrar el estado deseado (si existe)[8]. Partiendo
del diagrama de estados presentado en la Figura 2.3, ahora realizando la búsqueda por profundidad, se obtiene
el resultado que se muestra en la Figura 2.5 donde los estados con contorno negro han sido visitados, los
marcados en gris han sido vistos pero no visitados y los estados totalmente negros son aquellos desde los
cuales se ha generado un retroceso y no se consideran útiles, se puede observar que al igual que en la búsqueda
por profundidad se han explorado una gran cantidad de estados antes de encontrar el estado deseado.

Figura 2.5: Diagrama de estados explorado por Profundidad.

Si se comparan las Figuras 2.4 y 2.5, se puede observar que han sufrido ligeros cambios con respecto a
la Figura 2.3 , esto se debe a que algunos estados no han sido explorados y por esto no aparecen en los
diagramas de estados resultantes después de la exploración, se puede apreciar que los estados no explorados
son pocos, lo que hace a este tipo de búsqueda muy pesada computacionalmente.
2 Este retroceso se conoce comúnmente como Backtracking en Inglés y consiste en un retroceso cronológico ya que el agente

inteligente o explorador vuelve al nivel inmediatamente anterior.

17
2.2. MARCO TEÓRICO CAPÍTULO 2. MARCO REFERENCIAL

2.2.1.3. Búsqueda en Profundidad Progresiva

La búsqueda en profundidad progresiva, define un limite de profundidad (lp) para la exploración , la
búsqueda inicia como un búsqueda en profundidad pero cada vez que se explora un estado se suma una
unidad a un contador, si este contador alcanza el valor establecido en el limite de profundidad antes de
encontrar el nodo deseado o un callejón sin salida, se empieza a devolver y empieza a inspeccionar una nueva
rama de estados, si después de realizar la exploración de todos los estados con el limite de profundidad
definido no se encuentra el deseado, se incrementa el valor del limite de profundidad y vuelve a comenzar la
búsqueda.

2.2.1.4. Búsqueda Bidireccional

Para aplicar este tipo de búsqueda es necesario que se pueda realizar la exploración de estados en dos
sentidos simultáneamente, uno de los sentidos es del origen hacia el estado deseado y el otro en sentido
contrario; es decir desde el estado deseado hacia el estado de origen [10]. La condición para que esta búsqueda
funcione es que en uno de los sentidos la búsqueda se realice por amplitud y en el otro sentido se realice por
profundidad y así poder encontrarse en un punto.

2.2.2. Búsqueda informada

Se conoce como búsqueda informada al proceso de búsqueda que cuenta con poca o mucha información
del entorno a explorar antes de iniciar el proceso, en este tipo de búsqueda el explorador o agente inteligente
hace uso de la información para tomar decisiones mas rápidas y certeras sobre el camino a escoger en cada
paso. El problema de las búsquedas informadas es que no se puede garantizar que siempre se encuentre el
estado deseado debido a que este tipo de búsqueda deja estados sin explorar basando en la información con
la que cuente y es posible que en estos estados ignorados se encuentre el estado deseado.

2.2.2.1. Búsqueda Incremental

La búsqueda incremental reutiliza información de búsquedas anteriores para hallar una solución a nuevos
problemas similares de una manera potencialmente mas rápida que cuando se parte de cero [11]. El uso de
este tipo de búsqueda es importante para la IA ya que muchas veces el escenario de búsqueda es dinámico y
puede cambiar constantemente lo que provoca que los planes deban ser adaptados con la misma frecuencia
que cambia el escenario, tarea que se realiza fácil y rápidamente haciendo uso de la información adquirida en
búsquedas previas. Sin embargo a pesar de que este tipo de búsqueda parece ser optima presenta problemas
cuando el entorno cambia demasiado y no se tiene suficiente información para realizar una adaptación al plan,
en estos casos es necesario utilizar alguna estrategia de búsqueda a ciegas hasta que se encuentre el estado
deseado o se llegue a un estado conocido desde donde se pueda planificar de nuevo utilizando información
adquirida previamente.

2.2.2.2. Búsqueda Heurística

El nombre de búsqueda heurística procede del hecho de que se utilizan funciones heurísticas (ver sección
2.1.6) para calcular el siguiente mejor paso, basándose en información como la distancia de un estado al
estado deseado, el costo de moverse entre estados, el tiempo de ir de un estado a otro, entre otras. En la
Figura 2.6, se muestra un entorno, representado como una rejilla, donde cada celda que compone la rejilla
es un estado que posee a su alrededor varios posibles sucesores (es decir las celdas que se encuentran a su
alrededor) que pueden ser o no explorados por un agente inteligente, el cual tomará la decisión de que camino
escoger basado en una función heurística programada.

18
2.3. MARCO HISTÓRICO CAPÍTULO 2. MARCO REFERENCIAL

Figura 2.6: Rejilla simple

Este tipo de búsqueda es muy utilizado ya que permite la exploración de zonas donde los escenarios
cambian constantemente, puede llegar a ser más lento que la búsqueda incremental pero será mas rápido y
eficiente que la búsqueda a ciegas, la ventaja que presenta este tipo de búsqueda con respecto a la incremental,
es que esta se puede implementar desde cero en un entorno totalmente desconocido.
La eficiencia de la búsqueda dependerá principalmente del diseño de la función heurística utilizada en la
solución del problema de búsqueda. Desde luego una “mejor función” permitirá obtener “mejores resultados”;
resultados que podrán ser medidos en términos de conceptos como carga computacional, tiempo de ejecución,
consumo energético; entre otros.

2.2.2.3. Búsqueda Incremental Heurística

La búsqueda Incremental Heurística aparece como solución al problema mencionado anteriormente en
la búsqueda incremental, la cual tiene que hacer uso de algún tipo de búsqueda a ciegas cuando el agente
inteligente no cuenta con suficiente información de búsquedas pasadas para resolver el problema. Con este
nuevo tipo de búsqueda el problema se resuelve utilizando una función Heurística en los momentos en que
la búsqueda incremental no tiene suficiente información, esta función se aplica hasta que se encuentre un
estado o conjunto de estados conocidos que permitan planificar de nuevo utilizando búsqueda puramente
incremental o hasta que se encuentre el estado deseado.
El problema de este tipo de búsqueda se encuentra en la implementación dado que puede llegar a ser
bastante robusta , ya que se requiere implementar dos estrategias de búsqueda que puedan interactuar y
alternarse mutuamente y de manera automática.

2.3 MARCO HISTÓRICO

Con el paso del tiempo y la constante evolución de la IA y especialmente para el caso del presente proyecto
en los algoritmos de búsqueda, se han desarrollado diferentes algoritmos para la planificación de rutas. A
continuación se presentan algunos de los algoritmos mas utilizados y algunas de sus aplicaciones.

2.3.1. Algoritmo BFS (Breadth First Search)

BFS es el algoritmo básico utilizado para la búsqueda en amplitud o anchura, su implementación se realiza
de manera iterativa ya que en cada estado se ejecuta una evaluación de los posibles estados vecinos e hijos

19
2.3. MARCO HISTÓRICO CAPÍTULO 2. MARCO REFERENCIAL

dándole prioridad en la exploración, primero a los estados vecinos (ver sección 2.2.1.1). Este algoritmo es
comúnmente utilizado para realizar búsqueda en grafos.

2.3.2. Algoritmo DFS (Depth First Search)

DFS [12] es el algoritmo básico utilizado para la búsqueda en profundidad, su implementación es muy
parecida a la del BFS ya que también se implementa de manera iterativa con la diferencia de que prioriza la
búsqueda en los estados hijos y no en los vecinos, también es comúnmente utilizado para realizar búsqueda
en grafos.

2.3.3. Algoritmo de Dijkstra

El algoritmo de Dijkstra fue desarrollado por el científico holandés Edsger Dijkstra en 1959 como un
algoritmo de búsqueda de caminos mínimos. Este algoritmo consiste en generar un árbol de estados donde
el inicio es la raíz de árbol, punto a partir del cual se exploran todos los estados sucesores (todos los estados
conectados a la raiz), cada vez que es explorado un estado se almacena el costo de moverse del estado actual
a cada uno de sus sucesores, este proceso se repite para todos los estados[13].

Al finalizar de explorar todos los estados, el algoritmo calcula entre todas las posibles rutas generadas
durante la exploración la ruta mas corta o de mínimo costo. Es importante tener en cuenta que si en el arbol
de estados cambia el origen o cambia el destino, se hace necesario volver a realizar la tarea de exploración y
planificación de la ruta óptima. Debido a lo anterior el algoritmo resulta muy costoso computacionalmente
porque siempre requiere del calculo y determinación de todos los caminos posibles entre un estado y otro, lo
que genera grandes cantidades de información [14].

La idea de determinar todos los caminos posibles y pagar el costo que ello implica puede no ser lo mejor
cuando solo se desea encontrar un “camino” entre dos estados o cuando el escenario “cambia constantemente”
por lo que en tal caso, el uso del algoritmo de Dijkstra puedo no ser la mejor alternativa a implementar.

El algoritmo de Dijkstra fue utilizado en vídeo juegos para planificar la ruta mas corta en diferentes
escenarios, pero fue reemplazado por algoritmos de búsqueda heurística debido a la alta carga computacional
que generaba a medida que los entornos de los juegos se volvían más extensos y dinámicos. Un vídeo juego
donde se utilizó el algoritmo fue en el famoso juego de Pacman, donde los fantasmas cuando estaban en modo
persecución utilizaban el algoritmo de Dijkstra para hallar el camino más corto hasta el personaje principal
del juego: “Pacman” [15].

2.3.4. Algoritmo A*
El algoritmo A* (pronunciado como A-start o A-asterisco), es un algoritmo de búsqueda heurística el cual
trata de hallar el camino más corto entre dos puntos. Fue descrito en 1968 por Peter E. Hart, Nils J. Nilsson
y Bertram Raphael [16].

En 1964 Nils J. Nilsson [17] desarrolló una función heurística la cual buscaba mejorar la velocidad del
algoritmo de Dijkstra, a la implementación de esta función se le llamó como algoritmo A1; en 1967 Bertram
realizó mejoras sobre el algoritmo A1, llamando a este nuevo algoritmo como A2, sin embargo Bertram no
pudo demostrar cuan óptimo era este nuevo algoritmo; en 1968 Hart demostró que el algoritmo A2 era óptimo
siempre y cuando se cumplieran algunas condiciones determinadas. Debido a que los algoritmos anteriores
(A1 y A2) empezaban con la letra A y teniendo en cuenta que todas las mejoras partían del anterior, se
decidió llamar al algoritmo final como A*, manteniendo así la inicial A y significando con el * que incluía a
todas las versiones anteriores.

El algoritmo A* utiliza una función heurística la cual tiene en cuenta dos distancias que se representan
como:

20
2.3. MARCO HISTÓRICO CAPÍTULO 2. MARCO REFERENCIAL

h(x) la cual es una estimación de la distancia desde el estado actual del explorador o agente inteligente
hasta el estado deseado, esta estimación se hace comúnmente utilizando el concepto de distancia eucli-
diana y distancia de manhattan, dependiendo de la aplicación donde se valla a implementar el algoritmo
A*.
g(x) indica el costo del camino recorrido hasta el estado actual donde se encuentre el agente inteligente.

Quedando así la función heurística representada como:

f (x) = h(x) + g(x)

Esta función heurística es aplicada a cada uno de los estados sucesores del estado actual y se escoge como
siguiente mejor paso al que contenga el menor valor de f (x).
Una de las situaciones donde se ha aplicado el algoritmo A*, ha sido la de resolver el juegos del 8 Puzzle
[10](en termino general el N puzzle). En la Figura 2.7. Se muestra la apariencia clásica de un juego de 8
Puzzle sin resolver.

Figura 2.7: Juego del 8 Puzzle.

El juego del 8 Puzzle consiste consiste en organizar las casillas en orden según su numero del 1 al 8 de
arriba abajo y de izquierda a derecha, realizando la menor cantidad de movimientos posibles, teniendo en
cuenta que solo se puede mover una ficha a la vez; en este caso se utiliza la distancia de manhattan para
calcular el siguiente mejor estado para la casilla que queda vacía.

Debido a la importancia que ha tenido el algoritmo A* dentro de los algoritmos de búsqueda heurística,
se han introducido nuevos tipos de búsqueda como la búsqueda centrada en el agente o Agent-Centered
Search [18] en ingles; aunque este nuevo tipo de búsqueda no ha sido completamente aceptado dentro de la
comunidad, se han desarrollado algunos algoritmos como el algoritmo RTA* [19] y el algoritmo LRTA*[20],
los cuales presentan variaciones en el tiempo de ejecución y planificación de la ruta así como también en la
manera en que se almacenan y procesan los datos de los espacios explorados por parte de un agente inteligente;
existen más variaciones del algoritmo A*, sin embargo no se abordaran en el presente documento.

2.3.5. Algoritmo LPA*

El algoritmo LPA* (Lifelong Planning A*)[21], fue desarrollado por Sven Koenig, Maxim Likhachev y
David Furcy, aunque fue publicado oficialmente en el año 2004 se encuentran evidencia en algunos textos del
mismo autor que se desarrollo años atrás [22, 23].

El algoritmo LPA* se presenta como un algoritmo de búsqueda Incremental Heurística (ver sección 2.2.2.3)
el cual busca encontrar el camino mas corto entre un estado inicial y un estado final en el menor tiempo
posible cuando el espacio a explorar es muy grande o cuando se presenta que el espacio cambia continuamente.

21
2.3. MARCO HISTÓRICO CAPÍTULO 2. MARCO REFERENCIAL

Cuando un agente inteligente programado con el algoritmo LPA* inicial el proceso de búsqueda, primero
utiliza la función heurística presentada en el algoritmo A*, con la información que acaba de adquirir descarta
los estados sucesores de menor importancia y calcula el siguiente mejor paso entre los posibles estados
que no fueron descartados haciendo uso de la información que tenga almacenada de búsquedas anteriores
como lo hace la búsqueda incremental; si no se tiene información de búsquedas pasadas, se sigue haciendo
uso únicamente de la función heurística pero se almacena toda la información del recorrido realizado para
utilizarla posteriormente si el entorno llega a cambiar; haciendo así que en un entorno dinámico no se requiera
hacer una exploración total o parcialmente grande cuando existen muchos cambios constantes en el escenario,
para este caso solo seria necesario explorar de nuevo lo estados que hallan cambiando solo si estos influyen
directamente en la ruta.

2.3.6. Algoritmo D*
El algoritmo D* [24] recibe su nombre debido a que este se asemeja al algoritmo A* [16], con la diferencia
de que este se presenta como dinámico en el uso de la función heurística, ya que dependiendo del entorno a
explorar puede calcular de manera diferente las variables h(x) y g(x) presentadas en el algoritmo A*, este
algoritmo también permite que estados ya explorados y con un valor de f (x) definido durante el proceso de
búsqueda, se les asigne un nuevo valor dependiendo de la situación actual en la que se encuentre el agente
inteligente.

El algoritmo D* fue desarrollado por Anthony Stentz en el año de 1993 y publicado en el artículo llamado
Optimal and Efficient Path Planning for Unknown and Dynamic Environments; se realizó con la idea de
que se pudiera implementar en sistemas de robótica móvil, los cuales tendrían la capacidad de ajustar sus
sensores y funciones heurísticas para hallar el mejor camino dependiendo del entorno a explorar. La idea
de utilizar una función heurísticas que pueda cambiar o ser ajustada según las necesidades que presente el
agente inteligente en cada estado, permite que este algoritmo genere trayectorias óptimas en la mayoría de
los casos haciendo uso únicamente de la función heurística.

2.3.7. Algoritmo D* Lite

A pesar de que el algoritmo D* parece ser una solución óptima para resolver los problemas de planifica-
ción de rutas, este aún presenta algunos problemas al hacer uso de una función heurística, como se mencionó
anteriormente, al usar una función heurística no se puede garantizar que siempre se encuentre la mejor ruta
entre dos puntos ni que se haga en el menor tiempo.

Como mejora al algoritmo D* se desarrolló el algoritmo D* Lite en el año 2002 por parte de Sven Koenig
y Maxim Likhachev [25], este se presenta como un algoritmo de búsqueda incremental heurística igual que el
algoritmo LPA*, con la diferencia de que utiliza una función heurística dinámica como lo hace el algoritmo D*.

Así el algoritmo D* Lite se establece como un algoritmo para la planificación de rutas eficiente, el cual es
capaz de encontrar la mejor ruta entre dos estados en un tiempo de ejecución mínimo, pero debido a que es un
algoritmo de búsqueda incremental heurística sigue teniendo un costo computacional alto (ver sección 2.2.2.3).

En el año 2011 se implementó el algoritmo en una plataforma móvil con sistema de tracción diferencial y
un juego de 7 sensores infrarrojos, esta plataforma móvil se llamó Khepera II [26], el objetivo era probar el
funcionamiento del algoritmo en un entorno real al planificar una ruta entre dos estados fijos en condiciones
controladas.

22
Capítulo 3

DESARROLLO DEL PROYECTO

3.1 SELECCIÓN DEL AMBIENTE DE DESARROLLO

Un aspecto importante para la ejecución del proyecto fue seleccionar un ambiente de desarrollo adecuado,
se tuvieron en cuenta dos ambientes con sus respectivos lenguajes de programación los cuales se mencionan
a continuación:
Visual Studio utilizando C# como lenguaje de programación.
MATLAB el cual utiliza un lenguaje propio.

La principal característica que se tuvo en cuenta fue la facilidad en la creación de matrices de M x N , su

posterior manipulación y las posibilidades de graficar los valores almacenados en dichos arreglos de datos;
Teniendo en cuenta lo anterior se decidió utilizar MATLAB como ambiente de desarrollo, el cual utiliza un
lenguaje de alto nivel especializado en el manejo de unidades y arreglos de datos matemáticos.

3.2 CREACIÓN DEL ENTORNO DE EXPLORACIÓN

3.2.1. Delimitación del entorno
Para el proyecto se considera un entorno o ambiente de exploración limitado a dos (2) dimensiones el cual
siempre será cuadrado, se podrá ajustar el tamaño y considerando que el entorno debe ser discreto se podrá
ajustar la cantidad de nodos (resolución) en los que se dividirá .

El hecho de que el entorno se presente como un ambiente discretizado en una cantidad de nodos finitos,
permite que su implementación física sea alcanzable ya que cualquier espacio puede ser segmentado en un
conjunto de nodos con un numero igualmente finito de nodos vecinos o adyacentes [27].

En cuanto a los obstáculos, solo se podrán agregar tres (3) objetos con formas geométricas sencillas de
las cuales dos (2) serán cuadrados o rectángulos y el tercer obstáculo será un círculo o elipse, a todos los
objetos se les podrá modificar el tamaño cambiando el valor de sus dimensiones en X y Y respectivamente;
del mismo modo se podrá cambiar la posición y rotación del objeto dentro del entorno.

Es importante tener en cuenta que siempre primero deberá ser generado el entorno y posterior a éste se
podrá iniciar la exploración, esto se debe a que el entorno debe de ser independiente del agente inteligente o
explorador ya que se parte del hecho de que el entorno es totalmente desconocido y ajeno al explorador, el
agente inteligente solo conocerá el tamaño del entorno a explorar, su posición, la posición del nodo destino y
la cantidad de nodos en la que se encuentra segmentado el entorno, garantizando así que la planificación de
la ruta se podrá aplicar a cualquier entorno.

23
3.2. CREACIÓN DEL ENTORNO DE EXPLORACIÓN
CAPÍTULO 3. DESARROLLO DEL PROYECTO

3.2.2. Generación de entorno

Los escenarios o entornos construidos pueden ser arbitrarios y están limitados solamente por las condicio-
nes de diseño especificadas anteriormente, en la Figura 3.1, se puede observar un escenario con dimensiones
100 x 100 y una resolución de 20 puntos; es decir con separación de 5 unidades entre nodos, los obstáculos
serán representados con la misma resolución que se presenta el escenario.

Figura 3.1: Entorno de exploración.

Los nodos de color azul representan nodos por donde el explorador se podrá mover libremente mientras
que los rojos representan posiciones ocupadas por donde el agente no podrá transitar o no podrá atravesar,
además se puede observar que por fuera del contorno de la figura geométrica que representa el obstáculo se
generan nodos ocupados, esto corresponde a un valor de offset que se agrega teniendo en cuenta el tamaño
del explorador[28], en el presente proyecto se considera que el explorador solo ocupa un nodo y se comporta
como una partícula que se mueve en el entorno, si se llegara a pensar en un agente mas grande (es decir que
ocupe mas de un nodo), seria necesario modificar el valor de offset de cada obstáculo con el fin de evitar
colisiones al momento que trate de transitar por espacios muy reducidos.

El entorno presentado anteriormente, corresponde a una matriz binaria como la que se muestra en la
Figura 3.2, donde los valores en 0 representan nodos libres y los valores en 1 los nodos ocupados.

Figura 3.2: Matriz del entorno de exploración.

La matriz presentada, será la que realmente recorra el explorador y la cual irá censando durante todo

24
3.2. CREACIÓN DEL ENTORNO DE EXPLORACIÓN
CAPÍTULO 3. DESARROLLO DEL PROYECTO

el proceso de planificación y búsqueda de la ruta. Para crear tanto la matriz como la interfaz gráfica de la
misma, se diseñó en MATLAB una función la cual se encarga de generar el espacio vacío y luego posicionar
los obstáculos.

A continuación en la Figura 3.3, se muestra la función que permite generar el entorno y la matriz de
exploración de la misma.

Figura 3.3: Función para la generación del entorno.

Donde:
N1 es la matriz binaria que representa el conjunto de nodos libres y ocupados.
E1 es un vector que contiene las dimensiones en X y Y del primer rectángulo.
U1 es un vector que contiene la ubicación en X y Y del primer rectángulo.
R1 es la rotación del primer rectángulo en radianes.
E2, U2 y R2 son los vectores para la generación del segundo rectángulo el cual se forma igual que el
primer rectángulo.
E3 es un vector que contiene el valor del radio en X y Y del círculo.
U3 es la ubicación del círculo donde sus valores en X y Y corresponden al centro.
A es un escalar que representa el tamaño máximo del entorno a generar.
D es la cantidad de nodos en los que se dividirá el entorno.
Un ejemplo de la generación del entorno se presenta en la Figura 3.4, que se puede observar a continuación.

Figura 3.4: Ejemplo generación del entorno.

Para crear el entorno completo tal como se ha mostrado hasta el momento, primero se crea un entorno
vació y posteriormente se crean cada uno de los elementos. Todo el escenario y los objetos se genera utilizando
la función linspace() de MATLAB, la cual permite generar vectores lineales con separación uniforme lo que
hace fácil la tarea de construir cuadrados y rectángulos, para el círculo se utiliza la relación de las funciones
trigonométricas seno y coseno.

25
3.3. EL AGENTE INTELIGENTE O EXPLORADOR CAPÍTULO 3. DESARROLLO DEL PROYECTO

3.3 EL AGENTE INTELIGENTE O EXPLORADOR

Un agente es cualquier entidad capaz de ver o percibir el ambiente por medio de sensores y actuar sobre el
entorno a través de actuadores. En un modelo simplificado, un agente se puede representar como se muestra
en la Figura 3.5. Un agente humano tiene ojos, oídos y otros órganos que funcionan como sensores y tiene
manos, piernas, cuerdas vocales, entre otros actuadores. Un agente robótico puede tener cámaras, sensores
infrarrojos y ultrasonicos de distancia para detectar objetos, así como varios motores y otros actuadores.
Un agente de software censará pulsaciones de teclado, el contenido de algún archivo o variable y actuará
mostrando mensajes o imágenes en una pantalla, modificando o creando archivos y enviando información a
otros sistemas.

Figura 3.5: Modelo de un agente que interactuá con el entorno.

3.3.1. Sensores virtuales

El agente inteligente que para este caso es un agente de software, inicia el proceso de búsqueda de la
ruta entre dos puntos desconociendo totalmente el entorno, por lo cual se pensó en dotar al agente con un
conjunto de 8 sensores virtuales direccionales (S1, S2, ..., S8) ubicados a 45º entre si tal como se muestra
en la Figura 3.6. La posición de los sensores permite que el agente pueda percibir el entorno; sin embargo
existirán zonas ciegas comprendidas entre dos sensores (nodos no detectados), los cuales no afectarán en gran
medida la toma de decisiones, ya que los 8 vecinos o nodos mas cercanos se encuentran en el rango de vista
de los sensores y los demás los ira descubriendo a medida que avance en el proceso de búsqueda de la ruta.

Figura 3.6: Dirección de los sensores del agente.

Teniendo en cuenta que es un agente de software, lo que percibirán los sensores es el estado de cada nodo
que hace parte de la matriz que conforma el entorno y que se encuentra dentro del alcance de los sensores,
como se mencionó anteriormente los dos estados posibles son 0 y 1 representando si el nodo se encuentra
libre para ser un posible siguiente paso o se encuentra ocupado, lo cual implica que es un obstáculo. Si
se pensara en un sensor real, este devolvería un valor análogo o digital según sea el tipo de sensor que

26
3.3. EL AGENTE INTELIGENTE O EXPLORADOR CAPÍTULO 3. DESARROLLO DEL PROYECTO

correspondería a indicar si el siguiente espacio se encuentra libre u ocupado por un obstáculo, lo cual hace
que la implementación física del sistema de sensores sea viable.

3.3.2. Aprendizaje del agente

Hasta el momento en secciones anteriores se ha descrito el entorno, se presentó un modelo básico del agente
y como el agente percibe el entorno, sin embargo esto no es suficiente para que el agente tome decisiones
sobre la ruta, es necesario que el agente aprenda del entorno y utilice algún algoritmo para la planificación
de rutas en el que aplique lo que ha aprendido y lo que esta viendo actualmente para tomar una decisión de
cual es el siguiente mejor paso, dicho algoritmo se presentará en secciones posteriores.

Figura 3.7: Modelo de un agente que interactuá y aprende del entorno.

En la Figura 3.7, se presenta un modelo mas completo para un agente, el cual además de poder percibir el
entorno e interactuar con el mismo debe tener la capacidad de aprender sobre lo que ha recorrido y percibido
del entorno hasta el momento.
Para la creación del agente se desarrollo en MATLAB una clase, la cual sirve como base para crear
cualquier agente o explorador, en la Figura 3.8, se observa la clase llamada planificador la cual contiene un
serie de atributos que servirán como la memoria del agente.

1 classdef planificador<handle
2 %UNTITLED3 Summary of this class goes here
3 % Detailed explanation goes here
4
5 properties
6 ini=[]; %vector de inicio
7 fin=[]; %vecto de fin
8 pos=[]; %vector de posicion actual
9 ruta=[]; %ruta recorrida
10 vecinos=[]; %vecinos actuales; con relacion a pos
11 d=[]; %distancia de posicion actual a la meta
12 Mexplorados=[]; %matriz del espacio explorado
13 gx=[] %sumatorio de costos de moverse entre puntos
14 Nopen=[] %lista de nodos abiertos
15 Nclose=[] %lista de nodos cerrados
16
17 end
18
19
20 end

Figura 3.8: Clase en MATLAB para definir los agentes.

27
3.3. EL AGENTE INTELIGENTE O EXPLORADOR CAPÍTULO 3. DESARROLLO DEL PROYECTO

El agente debe conocer en todo momento la posición donde inicio el recorrido, este dato se almacenará
como un vector el cual contendrá las coordenadas en X y Y de la posición donde el agente inicio la exploración
y se almacenará en el atributo llamado “ini”, el agente también debe recordar cuales son las coordenadas
de el nodo destino las cuales serán almacenadas en “fin”, el atributo “pos” almacenará las coordenadas de
la posición actual del móvil sobre el entorno. Por ejemplo en la Figura 3.9, se muestran los atributos de un
agente llamado “S1” el cual se ha creado partiendo de la clase “planificador” y esta realizando la búsqueda
de una ruta entre dos puntos.

Figura 3.9: Atributos de un agente en medio de una búsqueda.

Se puede observar que el agente tiene almacenado como posición inicial ini = [5, 60] que se encuentra
representado en color verde, f in = [85, 10] que se encuentra representado en rojo y la posición actual en
pos = [15, 50] y se encuentra representado por un circulo rojo que demarca la posición actual del agente.

EL atributo “ruta” es un arreglo de tamaño variable, que cambia (aumenta su tamaño) cada ciclo y va
almacenando en orden las coordenadas de los nodos por donde se va desplazando el agente, este atributo
tendrá la siguiente forma:  
Xi X1 X2 ... Xn
ruta =
Yi Y1 Y2 ... Yn
Donde el conjunto Xi y Yi corresponden a la abscisa y la ordenada del punto donde inició el agente; Xn
y Yn corresponde a las coordenadas cartesianas del nodo final o nodo objetivo que debe ser el ultimo nodo
visitado; los demás pares ordenados corresponden a todos los nodos visitados por el agente antes de encontrar
el nodo objetivo.

El atributo “vecinos” se muestra en la Figura 3.10, este atributo cambia cada vez que el agente cambia
de posición, aquí es donde se almacena las coordenadas cartesianas y el estado (ocupado o libre) de los nodos
percibidos por los sensores virtuales, esta información que acaba de adquirir el agente se compara con lo
que conoce el agente hasta el momento; si las coordenadas de un nodo se encuentran ya registradas en la
memoria del agente, el atributo “vecinos” se completa con la información que se tiene almacenada de dicho
nodo, si no se encuentra registrado; es decir es la primera vez que el nodo aparece en el proceso de búsqueda
y planificación, se calculan los valores relacionados con la función heurística y se asigna un estado al nodo
según el algoritmo para la planificación de rutas utilizado, con esta información se toma la decisión de cual
es el siguiente nodo donde deberá desplazarse el agente.

28
3.3. EL AGENTE INTELIGENTE O EXPLORADOR CAPÍTULO 3. DESARROLLO DEL PROYECTO

Figura 3.10: Atributo “vecinos” en el agente.

El orden de conformación de este arreglo depende del sentido de exploración de los sensores virtuales,
la exploración del entorno por parte de los sensores se lleva a cabo empezando por el sensor S1 y continua
en sentido horario hasta llegar a S81 (ver Figura 3.6). Los valores asignados en las columnas H(x), G(x) y
estado del nodo se justificaran en secciones posteriores cuando se explique el algoritmo para la búsqueda y
planificación de la ruta.

La información de cada nodo que ha sido explorado o solamente visto durante el proceso de búsqueda
se almacena en el atributo “Mexplorados” el cual es un arreglo de dimensiones N xN x2 donde el valor de
N corresponde a la cantidad de nodos en los que está dividido el entorno a explorar. Este atributo es la
reconstrucción del entorno visto por el agente y es la memoria principal del mismo, cada nodo del entorno
tiene un equivalente en éste atributo; al momento de iniciar el proceso de búsqueda y planificación de la
ruta este arreglo contiene todos los valores en cero ya que el entorno se considera totalmente desconocido,
a medida que el agente avanza por el entorno los valores en cero empiezan a cambiar. En la primera capa
del arreglo, se almacenan los valores calculados al aplicar la función heurística a cada nodo, los nodos que se
encuentren ocupados por un obstáculo no se les aplicara dicho cálculo y se les asignara un valor muy grande
que tienda a infinito2 ; en la segunda capa del arreglo se almacena el estado de cada nodo, los cuales se han
marcado de la siguiente manera:

0 representa que el nodo nunca ha sido visto ni explorado.

1 representa que el nodo ha sido visto pero nunca visitado y es un posible candidato a ser visitado.
2 representa que el nodo ha sido visitado y hace parte de la ruta.
1000 representa un nodo ocupado por un obstáculo.

A continuación en la Figura 3.11, se muestra la primera capa del atributo “Mexplorados”, se pueden observar
los valores asignados por la función heurística para cada nodo y cuales nodos se han descubierto como parte
de un obstáculo, en la Figura 3.12, se muestra la segunda capa del atributo para la misma búsqueda, si se
observan los nodos con valor 2 se puede deducir cual es la ruta que se ha encontrado hasta el momento,
cuantos nodos han sido vistos y cuales hacen parte de los obstáculos del entorno.
1 Es posible dependiendo de la ubicacion del agente, que se cuente con menos de 8 vecinos por ejemplo cuando el agente se

encuentra sobre el borde del entorno.

2 Para el presente proyecto se escogio un valor de 1000, el cual es un valor muy grande en comparación con los valores arrojados

por la función heurisitca

29
3.3. EL AGENTE INTELIGENTE O EXPLORADOR CAPÍTULO 3. DESARROLLO DEL PROYECTO

Figura 3.11: Primera capa del atributo Mexplorados en medio de una búsqueda.

Figura 3.12: Segunda capa del atributo Mexplorados en medio de una búsqueda.

Los atributos “d” y “g(x)” son escalares que cambian cada vez que el agente se mueve, el primero alma-
cena el valor de la distancia euclidiana desde el nodo actual (donde se encuentra el agente) hasta el nodo
objetivo y sirve como condición de parada para el algoritmo de búsqueda, si “d” llega a valer 0 se considera
que el agente ha encontrado el nodo objetivo; el segundo es el costo acumulado del camino recorrido desde el
punto de inicio del agente hasta la posición actual, su valor se calcula utilizando la sumatoria de la distancia
euclidiana entre los nodos que forman parte de la ruta, también hace parte de la función Heurística de algunos
algoritmo para la búsqueda y planificación de rutas.

El Atributo“Nopen” es donde se almacenan las coordenadas de todos los nodos que han sido vistos pero
no visitados, es decir que no hacen parte de la ruta pero son vecinos de algún nodo que sí hace parte y
pueden llegar a ser visitados en algún momento; en el instante que un nodo que se encuentra en el atributo
“Nopen” es visitado por el agente, es eliminado de éste atributo y pasa automáticamente al atributo “Nclose”
que es dónde se almacenan las coordenadas de los nodos que hacen parte de la ruta y las coordenadas del
nodo que fue el predecesor de este último. Todos los nodos antes de pasar atributo “Nclose” deben haber
existido en “Nopen” ya que antes de ser visitados fueros nodos vecinos sin visitar. La información de estos
dos atributos es utilizada para realizar optimización de la ruta encontrada, sin embargado la optimización
excede los ámbitos del presente proyecto por lo cual no fue estudiada.

30
3.4. DESARROLLO DEL ALGORITMO CAPÍTULO 3. DESARROLLO DEL PROYECTO

Nota: Dependiendo del algoritmo de búsqueda utilizado un agente puede requerir menos
atributos de los presentados anteriormente.

3.4 DESARROLLO DEL ALGORITMO

Para el desarrollo del presente proyecto se tuvieron en cuenta dos tipos de algoritmos de búsqueda:
Algoritmos de búsqueda a ciegas o no informados
Algoritmos de búsqueda informada
Los primeros fueron descartados rápidamente, ya que estos algoritmos a pesar de requerir una carga compu-
tacional muy baja son muy demorados al no tener ningún tipo de información sobre la cual basar las decisiones
sobre la ruta a escoger.

Después de escoger los algoritmos de búsqueda informada fue necesario decidir entre los algoritmos de bús-
queda incremental o los algoritmos de búsqueda heurística. Los algoritmo de búsqueda incremental prometen
encontrar la ruta mas corta [29] en el menor tiempo posible para resolver una serie de problemas similares,
lo cual implica tener un conocimiento casi total del entorno [30]. Por otro lado, los algoritmos de búsqueda
heurística tratan de encontrar una ruta en un entorno desconocido de manera mas rápida que los algoritmos
de búsqueda a ciegas haciendo uso de una función heurística para tomar decisiones sobre la ruta [31, 32].
Teniendo en cuenta que la idea principal del proyecto es dotar en un futuro cercano a un sistema robótico
con los algoritmos acá desarrollados y que son varias las aplicaciones en las que un sistema robótico tiene que
interactuar con un entorno desconocido, se escogieron para el desarrollo del proyecto las búsquedas heurísticas.

Las búsquedas heurísticas también conocidas como búsquedas basadas en el agente, tratan de estimar
la distancia entre la posición actual del agente y la meta o nodo objetivo[33] haciendo uso de funciones
matemáticas conocidas como por ejemplo:
Distancia de Manhattan

Distancia de Mahalanobis
Distancia Euclidiana, entre otras.
Para conformar sus funciones heurísticas, que generalmente se denota como f (x), se pueden utilizar una o
varias de estas funciones matemáticas dependiendo del algoritmo, el entorno donde se apliquen y el tipo de
agente[34].

3.4.1. Algoritmo Best-First Search

El algoritmo Best-first Search3 expande todos los nodos vecinos del nodo actual donde se encuentra el
agente, buscando el siguiente nodo que tenga la distancia mas corta hasta el nodo objetivo. Cada nodo vecino
que es expandido se evaluá con la función heurística, la cual esta definida como:

f (n) = h(n) (3.1)

donde h(n) se encuentra definida como la distancia euclidiana, la cual en un espacio bidimensional entre
dos nodos P 1 y P2 con coordenadas cartesianas (X1 , Y1 ) y (X2 , Y2 )respectivamente, es:
q
2 2
dE (P1 , P2 ) = (X2 − X1 ) + (Y2 − Y1 ) (3.2)
Entonces, aplicando la ecuación (3.2) en (3.1) se tiene:
3 También es conocido como greedy search, ha sido llamado de muchas formas por diferentes autores y aun no se encuentra

establecido un nombre estar para referirse a este algoritmo[35].

31
3.4. DESARROLLO DEL ALGORITMO CAPÍTULO 3. DESARROLLO DEL PROYECTO

q
2
2
h (n) = dE (n’, ng ) = (ngx − n0x ) + ngy − n0y (3.3)
donde:
n0 es un nodo vecino del nodo actual con coordenadas cartesianas n0x , n0y el cual no se encuentra

ocupado por un obstáculo y se considera como un siguiente posible nodo en la ruta.

ng es el nodo objetivo o nodo meta y tiene coordenadas cartesianas (ngx , ngy ).
Ahora conociendo el valor de f (n) para cada nodo vecino del nodo actual donde se encuentra el agente, se
busca el que tenga menor valor y este se convierte en el siguiente nodo a visitar dentro de la ruta; todos los
f (n) calculados se almacenan en la memoria del agente, si un nodo es visto mas de una vez no se calcula de
nuevo el valor de la función heurística sino que se utiliza el valor que se tiene almacenado ya que siempre
sera el mismo, esto ayuda a reducir la carga computacional.

3.4.1.1. Ejecución del algoritmo

Para que el agente4 puede realizar la búsqueda, se desarrollo en MATLAB una función la cual es la
encargada de poner en funcionamiento el algoritmo y utiliza una serie de funciones más pequeñas para
realizar las tareas especificas del mismo. En la Figura 3.13, se muestra la función llamada Main, la cual es la
función principal.

1 function [S1,t] = Main(D,N,in,fin,Mocu)

2 close all
3 tic;
4 %Main(10, 10, [5 4], [9 9],J) ejemplo
5 %D=dimensión, N= cantidad de puntos
6 %%in=vector con las coordenadas de inicio,
7 %fin=vector con las coordenadas de la meta.
8 %Mocu=matriz de ocupados
9 %%inicializacion de entorno y explorador
10 div=D/N; %escala de separacion entre nodos
11 S1=planificador; %creción del objeto explorador S1
12 S1.ini=in; %carga del punto de inicio.
13 S1.fin=fin; %carga del punto final
14 S1.pos=[S1.ini]; %carga de la posición actual del objeto.
15 S1.Mexplorados=zeros(N+1); %matriz que almacena el valor H(x)
16 %% Inicio del loop
17 % S1.d = distancia entre el punto actual y la meta
18 % S1.vecinos = vecinos de la posicion actual
19 % S1.pos= Posicion actual del movil
20 while 1
21 S1.ruta=[S1.ruta,S1.pos']; %se carga la posicion actual a la ruta
22 D=Entorno(D,N,S1);
23 S1.d=distanp(S1.pos,S1.fin);
24 if S1.d==0
25 break
26 end
27 S1.vecinos = sucesores(S1.pos,D,div);
28 [S1.vecinos, S1.Mexplorados]=...
29 Explorar(S1.vecinos,S1.Mexplorados,S1.fin,S1.pos,Mocu,div);
30 [S1]=heuristica(S1,div);
31 %pause(0.1)
32 end
33 t=toc;
34 end

Figura 3.13: Función principal para el algoritmo Best-First Search.

4 El funcionamiento y componentes del agente se explicaron anteriormente en la sección 3.3

32
3.4. DESARROLLO DEL ALGORITMO CAPÍTULO 3. DESARROLLO DEL PROYECTO

Un ejemplo de la ejecución de la función Main se presenta continuación en la Figura 3.14.

Figura 3.14: Función Main para el algoritmo Best-First Search.

En secciones anteriores se mencionó que el agente requiere conocer el tamaño del entorno y la resolución,
es decir en cuantos nodos se dividió el entorno, las coordenadas de inicio que debe ser un nodo libre, las
coordenadas del nodo objetivo y por ultimo la matriz sobre la que el agente va a realizar la búsqueda; si la
búsqueda se realizará en un entorno real, la matriz N1 no sería necesaria. El algoritmo realiza los siguientes
pasos:
1. Crea el agente utilizando la clase planificador.

2. Se cargan con sus respectivos valores los atributos ini, fin y pos que hacen parte de la memoria del
agente.
3. Inicializa el atributo Mexplorados, esto lo hace creando una matriz llena de ceros y de dimensiones
iguales a la cantidad de nodos en los que fue segmentado el entorno.

4. Se actualiza el entorno y se calcula el valor de f (n) para el nodo actual que tiene las coordenadas del
nodo de inicio, a continuación en la Figura 3.15, se muestra un entorno de ejemplo donde el agente
inicia en un nodo con coordenadas cartesianas (10,5) (marca cuadrada de color verde) y tiene como
objetivo el nodo marcado con coordenadas (85,10) (marca cuadrada de color rojo).

Figura 3.15: Entorno de ejemplo para el ejemplo del algoritmo Best-First Search

33
3.4. DESARROLLO DEL ALGORITMO CAPÍTULO 3. DESARROLLO DEL PROYECTO

5. El agente censa el entorno y descubre cuales son los nodos vecinos.

6. Para cada nodo vecino descubierto por los sensores que se encuentre libre se realiza el calculo de su
f (n), por ejemplo en la Figura 3.16, se muestra en la esquina inferior izquierda los valores de f (n) para
lo nodos vecinos, en verde se marca el nodo de inicio y en rojo el nodo final.

Figura 3.16: Representación matricial del entorno antes del primer movimiento.

7. Se escoge el nodo con menor valor f (n) como el siguiente paso para el agente; para el presente ejemplo
el siguiente nodo sera aquel que tiene f (n) = 70 y corresponde al nodo con coordenadas (15,10).

El anterior proceso se repite desde el paso 4 hasta el 7, el ciclo termina cuando el valor de f (n) sea igual a
cero; es decir cuando la posición actual del agente sea el nodo objetivo, si el agente explora todos los nodos
libres disponibles y no encuentra el nodo objetivo, se detiene la búsqueda y se concluye que el nodo objetivo
no puede ser alcanzado por el agente.

3.4.2. Algoritmo A*(A-star)

El algoritmo de búsqueda A* (conocido comúnmente como A-star Search), parte del mismo principio
del algoritmo Best-First Search; sin embargo su función heurística agrega un nuevo termino, g(n) como
complemento y mejora para escoger una ruta de menor costo. Siendo así la función heurística para el algoritmo
de búsqueda A* se define como:

f (n) = h(n) + g(n)

g(n) estima el costo de desplazarse desde el nodo inicial hasta cualquier otro nodo, tratando que el
camino encontrado tenga el menor costo en desplazamiento
h(n)estima el costo mínimo desde un nodo n hasta el nodo objetivo.

Por lo tanto, si se trata de hallar una ruta con el menor costo posible, es razonable tratar de encontrar
primero el nodo con el g(n)+h(n)[36]. Este algoritmo resulta ser muy valioso dentro de los algoritmos de
búsqueda, ademas siempre y cuando se satisfagan ciertas condiciones la ruta encontrada se puede considerar
casi optima en términos de la menor distancia recorrida.

Como se menciono anteriormente el algoritmo A* comparte el mismo principio que el algoritmo Best-First
Search en cuanto al calculo de la función h(n), por lo que queda definida como:
q
2
2
h (n) = dE (n’, ng ) = (ngx − n0x ) + ngy − n0y
Ahora el nuevo termino g(n) se define como:
(
C(ni , n0 ) P ara i = 1
g(n) =
g(n) + C(ni , n ) ∀ i > 1
0

34
3.4. DESARROLLO DEL ALGORITMO CAPÍTULO 3. DESARROLLO DEL PROYECTO

Donde ni con i = 1 representa que la búsqueda acaba de empezar, es decir el agente se encuentra en el
nodo inicial y ∀ i > 1 representa cualquier otro nodo que hace parte de la ruta; C(n, n0 ) es la función de costo
de desplazar el agente de un nodo actual n a un nodo n0 adyacente.

La función C(ni , n0 ) se puede asignar como un valor constante o como el resultado de una función ma-
temática, para el presente proyecto y considerando que el entorno es un espacio bidimensional se utilizo la
función distancia euclidiana definida para un par de nodos ni = (nx , ny ) y n0 = (n0x , n0y ), entonces:
q
2
2
C (ni , n0 ) = dE (ni , n0 ) = (n0x − nx ) + n0y − ny
La ejecución del algoritmo A* se puede explicar con el siguiente conjunto de pasos5 :
1. Se inicializan en la memoria del agente ini, fin, pos, Nopen, Nclose.

2. Se agregan las coordenadas de el nodo inicial a Nopen.

Comienzo de un ciclo (Loop).
3. Se quitan las coordenadas del nodo actual de Nopen.

4. Se agregan las coordenadas del nodo actual a Nclose junto con las coordenadas de su predecesor .
5. Si el nodo actual es el nodo objetivo, se sale del Loop y se da por terminada la búsqueda, de lo contrario
continua el ciclo.
6. Se obtienen las coordenadas de cada nodo vecino del nodo actual donde se encuentre el agente.

7. Para cada nodo vecino del nodo actual se realiza lo siguiente:

a) Si es un nodo ocupado por un obstáculo o un nodo que se encuentre en Nclose, se ignora y se

continua con el siguiente nodo vecino.
b) Si es un nodo nuevo (nunca antes visto), se agrega a Nopen.
c) Para todos los nodos vecinos del nodo actual que se encuentren en Nopen, se calcula el valor de
f (n).

8. Se escoge el nodo con f (n) mas bajo como el siguiente nodo a visitar.
9. Se realiza el movimiento del agente, se actualiza pos con las coordenadas del nuevo nodo.

10. Se vuelve al comienzo del ciclo (Paso 3).

Para facilitar la comprensión sobre el funcionamiento del algoritmo A*, se presenta un ejemplo; en la Figura
3.17, se observa un entorno conformado por una cuadricula, cada casilla corresponde a un nodo y está
representado con su respectivas coordenadas cartesianas, la casilla marcada en verde representa el nodo
donde iniciará el agente, las casillas en negro son nodos ocupados y la casilla marcada en rojo es el nodo
objetivo.
5 Todos los atributos y variables que se mencionan a continuación y que hacen parte de la memoria del agente, se explicaron

en la sección 3.3

35
3.4. DESARROLLO DEL ALGORITMO CAPÍTULO 3. DESARROLLO DEL PROYECTO

Figura 3.17: Ejemplo para el algoritmo A*.

Una vez iniciado el proceso de búsqueda, el agente pasa el nodo actual de la lista Nopen a Nclose, y calcula
el valor de f (n) para cada nodo vecino. En la Figura 3.18, se pueden observar los valores de f (n) calculados
para cada uno de los nodos vecinos del nodo actual donde se encuentra el agente, también se observa una
lista con los nodos abiertos y resaltado en azul el nodo con menor valor calculado el cual sera escogido como
siguiente nodo donde el agente se desplazará.

Figura 3.18: Primera exploración del agente con el algoritmo A*.

Una vez el agente se desplaza al siguiente nodo, si éste no es el nodo objetivo, se vuelve a iniciar el proceso;
como en este caso no se ha alcanzado el nodo objetivo por parte del agente, se vuelven a realizar un censado
de los nodos vecinos y a calcular sus valores f (n), en la Figura 3.19, se observan los nuevos valores calculados
por el agente.

36
3.4. DESARROLLO DEL ALGORITMO CAPÍTULO 3. DESARROLLO DEL PROYECTO

Figura 3.19: Segunda exploración del agente con el algoritmo A*.

Se puede observar comparando las Figuras 3.18 y 3.19, el cambio en los valores f (n) calculados para todos
los nodos que se encuentran en la lista Nopen, los nodos que hasta el momento se encuentran en la lista Nclose
se ignoran, esto previene que el agente genere un retroceso innecesario, también se puede apreciar la aparición
de nuevos nodos en la lista Nopen. Es importante tener en cuenta que la componente h(n) permanece igual
, sin embargo g(n) cambia y hace que el valor de la función heurística f (n) cambie.

Figura 3.20: Tercera exploración del agente con el algoritmo A*.

En la Figura 3.20, se puede apreciar que el agente aun no ha encontrado el nodo objetivo por lo que sigue
el proceso de búsqueda, se ha encontrado con un obstáculo el cual trata de rodear, esto lo hace marcando
los nodos ocupados con valores muy altos lo cual hace que el agente no trate de atravesar los obstáculos. El
agente sigue buscando un camino para solucionar el problema, en la Figura 3.21, se observa la ruta encontrada
por el agente después de ejecutar varias veces el algoritmo; cuando el agente se encuentra en el nodo objetivo
el proceso de búsqueda termina.

37
3.5. DISEÑO DE UN AGENTE DE ROBÓTICO CAPÍTULO 3. DESARROLLO DEL PROYECTO

Figura 3.21: Ruta encontrada por el agente utilizando el algoritmo A*.

A pesar de que la optimización excede los ámbitos del presente proyecto, es importante recordar el uso
de la relación entre la lista Nopen y Nclose, esta servirá para optimizar en términos de la distancia recorrida
el algoritmo. Después de finalizar la búsqueda se genera un retroceso a través de todos los nodos vistos y
recorridos, es decir a través de todos los nodos que aparecen en las listas Nopen y Nclose; como en este
momento parte del entorno ya es conocido, se puede calcular una mejor ruta con la información almacenada.
En la Figura 3.22, se puede observar una posible optimización de la ruta encontrada, la linea negra marca la
ruta optima.

Figura 3.22: Ruta optimizada después de la exploración y planificación.

Para el desarrollo del algoritmo A* se utilizo la misma estructura en MATLAB que la utilizada en el
algoritmo Best-First Search, solo se cambio la sub-funcion llamada heurística.m. En el capitulo 6 ANEXOS,
se encuentran todos los códigos implementados en MATLAB con el fin de que puedan ser validados y utilizados
en futuras investigaciones.

3.5 DISEÑO DE UN AGENTE DE ROBÓTICO

Inicialmente dentro de los objetivos del presente proyecto solo se plantea desarrollar un agente inteligente
de software sensorialmente capaz de percibir el entorno; sin embargo todo se ha desarrollado con la intención
de poder implementar los algoritmos de búsqueda desarrollados a un agente inteligente robótico el cual pueda
percibir un entorno real y actuar sobre este.

38
3.5. DISEÑO DE UN AGENTE DE ROBÓTICO CAPÍTULO 3. DESARROLLO DEL PROYECTO

En esta sección se presenta el diseño y algunas consideraciones para la construcción de un prototipo de

agente inteligente robótico el cual sera sensorialmente capaz de percibir el ambiente y actuar desplazándose
en un entorno en busca de una ruta que una dos puntos coordenados.

3.5.1. Diseño mecánico del agente

Para el diseño mecánico del agente robótico se deben tener en cuenta varias condiciones como tamaño
y forma entre otras que se irán mencionando mas adelante. A continuación en la Figura 3.23, se presenta
una propuesta de diseño desarrollada en el programa solidworks para el agente el cual contara con tracción
diferencial.

(a) Diseño agente inteligente robótico (b) Vista explosionada del agente

Figura 3.23: Diseño mecánico del agente.

Los materiales seleccionados para la fabricación del agente fueron acrílico y aluminio, esto con el fin de
que sea resistente y liviano.

3.5.1.1. La base del agente

Para la base del agente se tuvieron en cuenta tres aspectos importantes: la forma, el tamaño y la la
ubicación del dentro de masa.

El tamaño del agente fue seleccionado teniendo en cuenta que debía ser menor al tamaño promedio de
algunas baldosas el cual oscila alrededor de 30 cm de longitud, esto con el fin de poder realizar pruebas en
entornos controlados sin tener que realizar adecuaciones difíciles o costosas, también se considero el tamaño
de los motores con caja reductora y encoder que se encontraban actualmente en el mercado, para el presente
proyecto se escogió el motor 37Dx54L con encoder de Pololu el cual se muestra a continuación en la Figura
3.24. El cual tiene aproximadamente 8 cm de longitud desde el encoder hasta la salida de la caja reductora.
Teniendo en cuenta lo anterior se estableció una medida de 24 cm de diámetro para el móvil.

Figura 3.24: Motor 37Dx54L con encoder de Pololu.

39
3.5. DISEÑO DE UN AGENTE DE ROBÓTICO CAPÍTULO 3. DESARROLLO DEL PROYECTO

La forma del móvil y la ubicación de los elementos en el la misma se selecciono pensando en la forma en
la que deberían ir ubicados los sensores (aunque los sensores se encuentran ubicados en la tapa y no en la
base, estas dos partes deben guardar relación) y en la ubicación del centro de masa del móvil.

Rueda loca o
Rueda de apoyo
Centro de masa
Centro geométrico

Figura 3.25: Base del agente.

En la Figura 3.25, se puede apreciar la forma y la ubicación de los motores en la base del móvil, se
decidió que tuviera una forma circular con cortes laterales para las llantas, también se agregaron dos ruedas
de apoyo, una en la parte frontal y la otra en la parte trasera del móvil; el objetivo principal de agregar los
elementos a la base con la distribución anteriormente mostrada es el de garantizar que el centro de masa se
ubique exactamente con el centro geométrico del móvil, lo cual al tener un sistema de tracción diferencial
facilita el control del mismo, especialmente cuando este tenga que rotar ya que siempre rotara sobre su centro
geométrico y no generara ningún tipo de desplazamiento; solo rotación.

3.5.1.2. Las ruedas

Teniendo el cuenta que el desplazamiento debe de darse de la manera mas suave posible y sin que hallan
perdidas de tracción por falta de fricción sobre la superficie en donde se encuentre el móvil, se escogieron
ruedas de neopreno de 7.7 cm de diámetro como las que se presentan a continuación en la Figura 3.26.

Figura 3.26: Ruedas de neopreno.

Estas ruedas al ser de un material poroso garantizan un buen agarre en la mayoría de las superficies lo
que evita las perdidas de tracción, ademas al ser de un material suave estas se deformen un poco al pasar
por superficies que no sean totalmente lisas sin que el móvil sufra grandes perturbaciones6 .
6 Con el fin de evitar la deformación excesiva por el peso del móvil, las ruedas de apoyo se deben tener el tamaño minimo al

que puede estar la base del movil de la superficie.

40
3.5. DISEÑO DE UN AGENTE DE ROBÓTICO CAPÍTULO 3. DESARROLLO DEL PROYECTO

3.5.2. Diseño electrónico del agente

En la sección anterior se mencionaron las características mecánicas mas relevantes para la construcción
del agente, en esta sección se presentan algunos de los elementos escogidos y consideraciones para el diseño
para la parte electrónica de control, comunicaciones y de manejo de los motores.

3.5.2.1. Alimentación del sistema y circuito controlador de los motores

Uno de los puntos críticos en el diseño y construcción de dispositivos robóticos es la selección de la fuente
de alimentación de los mismo, ya que de esta depende en gran parte el correcto funcionamiento y autonomía
del móvil. Es bien conocido que el mayor consumo de carga de las baterías se encuentra dado por los moto-
res, algunos autores consideran que los motores consumen aproximadamente el 80 % [37] de la carga total de
las baterías. Por la anterior se sugiere escoger las baterías teniendo en cuenta especialmente el consumo de
los motores; para el presente proyecto y considerando el consumo de corriente de los motores mencionados
anteriormente (ver sección 3.5.1.1) para los cuales se determino de manera experimental que la corriente
máxima demandada en rotor bloqueado se encuentra alrededor de 1.5A/h y puede trabajar con tensiones
entre 6 y 12V se selecciono una batería de litio ion de 11.1V y 1500mA/h con la cual se puede garantizar
aproximadamente 1 hora de autonomía cuando este se encuentre atascado, es decir cuando sus motores de
encuentren en rotor bloqueado. Ademas se selecciona una batería extra que alimentara toda la parte de lógica
de control ya que esta parte es de bajo consumo se selecciona un batería de 7V y 500mA/h.

Otro aspecto importante a tener en cuenta es la correcta selección o construcción de un circuito que
permita controlar la velocidad y cambio de giro de los motores, en la Figura 3.27a. Se muestra la tarjeta
controladora para motores MC33926, la cual permite el control de dos motores de manera independiente y
requiere conexiones mínimas con un sistema microcontrolado como se observa en la Figura 3.27b.

(a) Tarjeta MC33926. (b) Diagrama de conexión con un sistema microcontrolado.

Figura 3.27: Circuito controlador para los motores.

3.5.2.2. Sistema microcontrolado del agente

Para que el agente pueda funcionar de manera autónoma es necesario que este cuente con un sistema que
ejerza control sobre el, en este proyecto se utilizaron dos tarjetas de desarrollo basadas en microcontroladores
Atmel, como “cerebro” o sistema de control principal del agente se utilizo un Arduino Mega 2560 como el que
se observa en la Figura 3.28. Este Arduino cumple con las mismas funciones de memoria que las explicadas en
las sección 3.3.2, es decir es el encargado de almacenar la posición actual del agente, posición inicial, posición
final y lo que a aprendido del entorno.

41
3.5. DISEÑO DE UN AGENTE DE ROBÓTICO CAPÍTULO 3. DESARROLLO DEL PROYECTO

Figura 3.28: Arduino Mega 2560.

También es el encargado de controlar y realizar la tarea de censado y percepción del entorno por parte
del agente, para la tarea de censado se decidió trabajar con sensores ultrasonicos de referencia HC-SR04,
los cuales son de bajo costo, tienen un rango de operación de 2 cm a 400 cm lo que los hace ideales para
la aplicación y ademas tienen un angulo de apertura de 30 grados; en la Figura 3.29a, se presenta el sensor
ultrasonico mencionado. Si se toma en cuenta las consideraciones de poner en sensor cada 45 grados se
obtendría una distribución de sensores tal como se muestra en la Figura 3.29b, la cual es ideal ya que permite
detectar los 8 puntos mas cercanos al agente y deja pocas zonas ciegas.

(a) Sensor ultrasonico HC-SR04. (b) Distribución de sensores y area de sensado.

Figura 3.29: Sensores ultrasonicos para la percepción del entorno.

Por otro lado es importante tener en cuenta que este sistema microcontrolado tiene memoria finita y muy
limitada por tal motivo se piensa en dotar al agente con un sistema de comunicación inalámbrico basado
en el protocolo 802.11b haciendo uso del modulo ESP8266 como el que se muestra en la Figura 3.30. Este
modulo tiene comunicación serial para comunicarse con el Arduino de forma bidireccional y permitirá al
móvil comunicarse con un computador con alta capacidad de memoria para realizar una copia de toda la
información percibida del entorno por parte del agente, también en el computador se realizara toda la tarea de
procesamiento y ejecución del algoritmo de planificación de rutas y se le enviara solo al móvil la información
de cual es el siguiente mejor paso. Utilizar un computador externo hacer que el sistema microcontrolado
funcione mejor y de manera mas eficiente al no tener que utilizar el procesador hasta el limite.

42
3.5. DISEÑO DE UN AGENTE DE ROBÓTICO CAPÍTULO 3. DESARROLLO DEL PROYECTO

Figura 3.30: Modulo de comunicación inalambrica ESP8266.

Es necesario utilizar un segundo sistema microcontrolado dedicado exclusivamente a controlar los motores,
esto se debe a que la tarea de desplazarse requiere que se dedique un elemento exclusivamente a realizar el
conteo de pulsos emitidos por el encoder del motor para garantizar el menor error posible en desplazamiento
y posicionamiento del móvil; para esta tarea se escogió un Arduino Nano, el cual es de bajo costo y se puede
comunicar por medio de un puerto serial como el sistema principal (Arduino Mega).

3.5.3. Ensamble del sistema y construcción física

Teniendo en cuenta todo la anterior se inicio el proceso de diseño de una tarjeta electrónica la cual
permitirá agrupar y conectar todos los elementos anteriormente mencionados como se observa en la Figura
3.31.

Figura 3.31: PCB principal para el agente.

En la Figura 3.32, se observa la base con los motores.

43
3.5. DISEÑO DE UN AGENTE DE ROBÓTICO CAPÍTULO 3. DESARROLLO DEL PROYECTO

Figura 3.32: Base del agente robótico.

Finalmente en la Figura 3.33, se observa finalmente el agente completamente ensamblado siguiendo todas
las condiciones mencionadas durante esta sección.

Figura 3.33: Agente inteligente robótico construido.

Nota: Las pruebas realizadas con el agente robótico no se incluyen en el capítulo de pruebas y resultados
debido a que este se encuentra aún en la fase de puesta a punto. Esta sección esta orientada principalmente
al diseño.

44
Capítulo 4

PRUEBAS Y RESULTADOS

En este capitulo se presentan los resultados de las pruebas realizadas sobre cinco (5) entornos diferentes,
los cuales son totalmente desconocidos para el agente que realiza la búsqueda y planificación de la ruta;
para cada entorno se aplicaron dos (2) pruebas, en donde se cambiaron para cada caso las coordenadas del
nodo de inicio y nodo objetivo o destino. En todos los casos se realizaron las pruebas con los dos algoritmos
desarrollados en el presente proyecto, Best-First Search y A* Search.

Con el fin de poder comparar los resultados arrojados por los algoritmos en cada caso, ademas de la
comparación gráfica, se midieron 3 parámetros:

Tiempo de ejecución: El tiempo de ejecución de cada algoritmo desde el inicio del mismo hasta que
finaliza se midió utilizando las funciones tic y toc de MATLAB. Al inicio de la función principal Main.m
empieza el conteo de tiempo con la función tic; al final del algoritmo se ejecuta la función toc, la cual
devuelve el tiempo en segundos que a pasado desde la ultima ejecución de la función tic. Este valor en
segundos se considera como el tiempo de ejecución de cada algoritmo.

Nodos recorridos: Es la cantidad de nodos en unidades que el agente recorrió desde el nodo de inicio
hasta el nodo objetivo, es decir todos los nodos que el agente visitó durante el proceso de búsqueda y
planificación de la ruta.
Distancia recorrida: Es la suma acumulada de la distancia euclidiana entre los nodos que visitó el agente
durante la búsqueda y planificación de la ruta. Este parámetro hace parte del algoritmo A* Search como
parte de su función heurística para tratar de encontrar el camino mas corto; sin embargo el algoritmo
Best-First Search no cuenta con este parámetro.
Con el fin de poder realizar la comparación de la distancia recorrida por el agente con cada algoritmo, se
desarrollo un función para medir la distancia recorrida cuando se utiliza el algoritmo Best-First Search;
es importante aclarar que esta función se ejecuta de manera externa al algoritmo principal una vez que
termina la búsqueda, esto con el fin de evitar que se afecte el tiempo de ejecución del algoritmo por
una función que no es propia de mismo.

45
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(a) Best-First Search

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(b) A* Search

Figura 4.1: Escenario 1 prueba 1

A* Search Best-First Search

Tiempo de ejecución(s) 0.7386 0.7133
Nodos recorridos(unid) 18 18
Distancia recorrida (unid) 85 85
Nodo inicial (5,50)
Nodo final (90,50)

Cuadro 4.1: Cuadro de resultados escenario 1 prueba 1

46
A* Search Best-First Search
Tiempo de ejecución(s) 0,7124 0,7399
Nodos recorridos(unid) 17 17
Distancia recorrida (unid) 104.8528 104.8528
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(a) Best-First Search

100

90

80

70

60

50

40

30

20
A* Search Best-First Search
Tiempo de ejecución(s) 0,7386 0.7133
10
Nodos recorridos(unid) 18 18
Distancia
0 recorrida (unid) 85 85
0 20 40 60 80 100
Nodo inicial (5,50)
Nodo final (b) A* Search. (90,50)
Figura 4.2: Escenario 1 prueba 2

A* Search Best-First Search

Tiempo de ejecución(s) 0.7124 0.7399
Nodos recorridos(unid) 17 17
Distancia recorrida (unid) 104.8528 104.8528
Nodo inicial (5,15)
Nodo final (85,75)

Cuadro 4.2: Cuadro de resultados escenario 1 prueba 2

47
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(a) Best-First Search

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(b) A* Search

Figura 4.3: Escenario 2 prueba 1

A* Search Best-First Search

Tiempo de ejecución(s) 0.6512 0.6237
Nodos recorridos(unid) 19 19
Distancia recorrida (unid) 112.7817 112.7817
Nodo inicial (35,5)
Nodo final (80,85)

Cuadro 4.3: Cuadro de resultados escenario 2 prueba 1

A* Search Best-First Search
Tiempo de ejecución(s) 481.6953 1.3134
Nodos recorridos(unid) 56 42
Distancia recorrida (unid) 326.77 256
Nodo inicial (5,95)
Nodo final (55,1)
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(a) Best-First Search

100

90

80

70

60

50

40

30

20

10
A* Search Best-First Search
Tiempo de ejecución(s) 0,6512 0.6237
0
Nodos recorridos(unid) 19 60 19 100
0 20 40 80
Distancia recorrida (unid) 112.7817 112.7817
(b) A* Search
Nodo inicial (35,5)
Nodo final Figura 4.4: Escenario 2 prueba 2
(80,85)

A* Search Best-First Search

Tiempo de ejecución(s) 1.6953 1.3134
Nodos recorridos(unid) 56 42
Distancia recorrida (unid) 326.77 256
Nodo inicial (5,95)
Nodo final (55,10)

Cuadro 4.4: Cuadro de resultados escenario 2 prueba 2

49
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(a) Best-First Search

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(b) A* Search

Figura 4.5: Escenario 3 prueba 1

A* Search Best-First Search

Tiempo de ejecución(s) 0.3598 0.5013
Nodos recorridos(unid) 9 21
Distancia recorrida (unid) 92.4264 237.2792
Nodo inicial (0,90)
Nodo final (30,10)

Cuadro 4.5: Cuadro de resultados escenario 3 prueba 1

A* Search Best-First Search
Tiempo de ejecución(s) 50 0,3467 0,3538
Nodos recorridos(unid) 11 13
Distancia recorrida (unid) 132.4264 140.7107
Nodo inicial (30,30)
Nodo final (50,80)
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(a) Best-First Search

100

90

80

70

60

50

40

30

20
A* Search Best-First Search
10
Tiempo de ejecución(s) 0,3598 0.5013
Nodos
0 recorridos(unid) 9 21
0 20 40 60 80 100
Distancia recorrida (unid) 92.4264 237.2792
(b) A* Search
Nodo inicial (0,90)
Nodo final (30,10)
Figura 4.6: Escenario 3 prueba 2

A* Search Best-First Search

Tiempo de ejecución(s) 0.3467 0.3538
Nodos recorridos(unid) 11 13
Distancia recorrida (unid) 132.4264 140.7107
Nodo inicial (30,30)
Nodo final (50,80)

Cuadro 4.6: Cuadro de resultados escenario 3 prueba 2

51
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(a) Best-First Search

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(b) A* Search

Figura 4.7: Escenario 4 prueba 1

A* Search Best-First Search

Tiempo de ejecución(s) 0.6442 1.4475
Nodos recorridos(unid) 16 46
Distancia recorrida (unid) 79.1421 253.994
Nodo inicial (10,5)
Nodo final (80,10)

Cuadro 4.7: Cuadro de resultados escenario 4 prueba 1

A* Search Best-First Search
Tiempo de ejecución(s) 520,8781 0.6901
Nodos recorridos(unid) 24 21
Distancia recorrida (unid) 131.5685 122.7817
Nodo inicial (90,95)
Nodo final (30,0)
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100
(a) Best-First Search

100

90

80

70

60

50

40

30

20

10 A* Search Best-First Search

Tiempo de ejecución(s) 0,6442 1.4475
0
Nodos recorridos(unid)
0 20 40 1660 80 46 100
Distancia recorrida (unid) 79.1421 253.994
(b) A* Search
Nodo inicial (10,5)
Nodo final (80,10)
Figura 4.8: Escenario 4 prueba 2

A* Search Best-First Search

Tiempo de ejecución(s) 0.8781 0.6901
Nodos recorridos(unid) 24 21
Distancia recorrida (unid) 131.5685 122.7817
Nodo inicial (90,95)
Nodo final (30,0)

Cuadro 4.8: Cuadro de resultados escenario 4 prueba 2

53
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100
(a) Best-First Search

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(b) A* Search

Figura 4.9: Escenario 5 prueba 1

A* Search Best-First Search

Tiempo de ejecución(s) 1.5084 1.6591
Nodos recorridos(unid) 47 50
Distancia recorrida (unid) 246.5685 280.2082
Nodo inicial (5,85)
Nodo final (60,80)

Cuadro 4.9: Cuadro de resultados escenario 5 prueba 1

A* Search Best-First Search
Tiempo de ejecución(s) 12.3847
54 2.3955
Nodos recorridos(unid) 409 78
Distancia recorrida (unid) 2238.8225 445.0610
Nodo inicial (80,90)
Nodo final (15,5)
 CAPÍTULO 4. PRUEBAS Y RESULTADOS

100

90

80

70

60

50

40

30

20

10

0
0 20 40 60 80 100

(a) Best-First Search

100

90

80

70

60

50

40

30

20

10 A* Search Best-First Search

Tiempo de ejecución(s) 1.5084 1.6591
0
Nodos recorridos(unid)
0 20 40 47 60 80 50 100
Distancia recorrida (unid) 246.5685 280.2082
(b) A* Search
Nodo inicial (5,85)
Nodo final Figura 4.10: Escenario 5 prueba
(60,80)2

A* Search Best-First Search

Tiempo de ejecución(s) 12.3847 2.3955
Nodos recorridos(unid) 409 78
Distancia recorrida (unid) 2238.8225 445.0610
Nodo inicial (80,90)
Nodo final (15,5)

Cuadro 4.10: Cuadro de resultados escenario 5 prueba 2

55
Capítulo 5

CONCLUSIONES Y FUTUROS
TRABAJOS

5.1 CONCLUSIONES
En este trabajo de grado se han estudiado los conceptos de búsqueda y planificación de rutas, en este
sentido se han manejado muchos algoritmos que facilitan el proceso de búsqueda y planificación realizados
por un agente inteligente; particularmente se ha orientado el presente trabajo a estudiar e implementar dos
algoritmos, uno de ellos el Best-First Search y el otro el A* Search.

Al comparar los dos algoritmos y los resultados después de un proceso de experimentación, se sabe:

Por el estudio del estado del arte el algoritmo Best-First Search aparece entre los primeros algoritmos de
búsqueda heurística y sirve de base al algoritmo A* Search, en ese sentido se podría pensar que éste último
es un algoritmo más evolucionado y debería garantizar siempre mejores resultados que su predecesor; sin
embargo en los experimentos realizados se observa que esto no es así, una de las razones se encuentra relacio-
nada con el tiempo de ejecución de cada uno de los algoritmos. Se puede observar que el algoritmo Best-First
Search es mas rápido en tiempo de ejecución cuando el entorno es simple y se pueda identificar fácilmente
la ruta que una dos nodos, mientras que el A* Search en un entorno simple puede llegar a ser considerado lento.

Por otro lado, una de las ventajas del algoritmo A* Search es que después de realizar un primera búsqueda
se puede realizar una optimización de la ruta encontrada; esto se puede realizar utilizando la información
extra que almacena el algoritmo sobre lo que el agente halla conocido durante el recorrido, ya que se tiene la
capacidad de almacenar en memoria la ruta recorrida y los nodos vecinos de la ruta recorrida.

También es importante tener en cuenta que encontrar la ruta mas corta en términos de distancia recorrida
puede no ser la mejor opción cuando se realiza la implementación de un algoritmo como el A* Search en
un sistemas físico real. Un ejemplo de esto se puede observar en la Figura 4.2b, donde en la búsqueda de
un camino mas corto se realizan varios cambios de dirección, lo que desde el punto de vista de la energía se
puede considerar como un desgaste para el sistema, ya que para realizar los cambios de dirección se requiere
generar un conjunto de aceleraciones y desaceleraciones que en un sistema robótico alimentado por baterías
puede suponer el agotamiento prematuro de la carga de las baterías.

Aunque las búsquedas heurísticas se caracterizan por el uso de información para realizar la búsqueda y la
planificación de la ruta y garantizan siempre encontrar una ruta (mientas exista), se observa que en algunas
ocasiones el agente se queda sin suficiente información o con información que puede ser confusa para tomar
una decisión certera; por ejemplo cuando dos o mas nodos vecinos tienen el mismo valor f (n), se puede pensar
en que existe un factor de aleatoriedad para definir cual de los nodos debe ser “el elegido”; en este caso la
selección del nodo siguiente se da generalmente por el orden en que se programa el uso de los sensores para

56
5.2. FUTUROS TRABAJOS CAPÍTULO 5. CONCLUSIONES Y FUTUROS TRABAJOS

percibir el entorno (esta situación puede generar que el agente se aleje del nodo objetivo).

5.2 FUTUROS TRABAJOS

Dentro de los futuros trabajos que se piensan realizar con base en lo desarrollado en el presente proyecto
se encuentra:

1. Incluir en el algoritmo A* Search la opción de optimización de la ruta.

2. Generar un algoritmo que permita suavizar las trayectorias encontradas.
3. Simular el recorrido de la ruta utilizando el modelo matemático de un sistema de tracción diferencial.

4. Desarrollar un agente robótico físico e implementar en éste alguno, o los dos algoritmos estudiados en
el proyecto.
5. Implementar el sistema de búsqueda en un entorno de tres dimensiones.
6. Construir un equipo conformado por dos o más agentes inteligentes que trabajen colaborativamente en
la solución de un problema de planificación.
7. Estudiar e implementar sistemas de optimización de variables como: distancia recorrida, esfuerzo de
control, tiempos de búsqueda y ejecución, consumo energético, entre otras.

57
58
Bibliografía

[1] Ángela Bedoya Hernández y Gustavo Guzmán Cadavid y José Chaves Osorio,
“Propuesta de desarrollo robótico para el desminado humanitario,” Scientia et
Technica, vol. 3, no. 49, pp. 239–244, 2011. 1.1
[2] A. KOTT, V. SAKS, and A. MERCER, “A new technique enables dynamic replanning
and rescheduling of aeromedical evacuation: Special articles on innovative
applications,” The AI magazine, vol. 20, no. 1, pp. 43–53, 1999. 1.1
[3] R. A. Española, Diccionario de la Real Academia de la Lengua Española, vol. 22. 2012.
2.1.1
[4] A. M. Turing, “Computing machinery and intelligence,” Mind, pp. 433–460, 1950. 2.1.2
[5] A. Barr, E. Feigenbaum, and C. Roads, The Handbook of Artificial Intelligence,
Volume 1, vol. 1. JSTOR, 1982. 2.1.2
[6] D. A. Waterman and A. Newell, “Protocol analysis as a task for artificial intelligence,”
Artificial Intelligence, vol. 2, no. 3, pp. 285–318, 1972. 2.1.2
[7] C. L. Liu, L. A. D. Torres, and G. T. Castillo, Elementos de matemáticas discretas.
McGraw-Hill, 1995. 2.1.3
[8] J. Roberto, “Inteligencia artificial: Introducción y tareas de búsqueda,” 2010. 2.1.5,
2.2.1.2
[9] J. M. Vargas, C. T. Pinzón, and C. R. Patiño, “Técnicas de inteligencia artificial para
la solución de laberintos de estructura desconocida.,” Scientia et Technica, vol. 2,
no. 39, 2008. 2.2.1.1
[10] A. González Ospina, C. Garzón, and H. Baldomiro, “Diseño, implementación y
aplicación de una estrategia de búsqueda preferente por amplitud, para uso
multidireccional sobre sistemas distribuidos o de procesamiento en paralelo, usando un
simulador de escenarios, construido para el trazado de rutas en robótica móvil,” 2011.
2.2.1.4, 2.3.4
[11] S. Koenig, M. Likhachev, Y. Liu, and D. Furcy, “Incremental heuristic search in ai,” AI
Magazine, vol. 25, no. 2, p. 99, 2004. 2.2.2.1
[12] R. E. Korf, “Depth-first iterative-deepening: An optimal admissible tree search,”
Artificial Intelligence, vol. 27, no. 1, pp. 97 – 109, 1985. 2.3.2
[13] E. Dijkstra, “A note on two problems in connexion with graphs,” Numerische
Mathematik, vol. 1, no. 1, pp. 269–271, 1959. 2.3.3

59
BIBLIOGRAFÍA BIBLIOGRAFÍA

[14] J. D. i Gavaldà and H. T. Navarro, Inteligencia artificial. UOC Universitat Oberta de

Catalunya, 2008. 2.3.3
[15] A. Espinose Marlasca, D. J. Moran Marquez, and F. J. Romero Paris, “Funciones que
ganan partidas,” Universidad de Alcala, 2013. 2.3.3
[16] P. Hart, N. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of
minimum cost paths,” Systems Science and Cybernetics, IEEE Transactions on, vol. 4,
pp. 100–107, July 1968. 2.3.4, 2.3.6
[17] “Ai’s hall of fame,” Intelligent Systems, IEEE, vol. 26, pp. 5–15, July 2011. 2.3.4
[18] S. Koenig, “Agent-centered search,” AI Magazine, vol. 22, no. 4, p. 109, 2001. 2.3.4
[19] R. E. Korf, “Real-time heuristic search,” Artificial Intelligence, vol. 42, no. 23, pp. 189
– 211, 1990. 2.3.4
[20] M. Shimbo and T. Ishida, “Controlling the learning process of real-time heuristic
search,” Artificial Intelligence, vol. 146, no. 1, pp. 1 – 41, 2003. 2.3.4
[21] S. Koenig, M. Likhachev, and D. Furcy, “Lifelong planning a*,” Artificial Intelligence,
vol. 155, no. 12, pp. 93 – 146, 2004. 2.3.5
[22] S. Koenig, D. Furcy, and C. Bauer, “Heuristic search-based replanning.,” in AIPS,
pp. 294–301, 2002. 2.3.5
[23] M. Likhachev and S. Koenig, “Incremental replanning for mapping,” in Intelligent
Robots and Systems, 2002. IEEE/RSJ International Conference on, vol. 1, pp. 667–672
vol.1, 2002. 2.3.5
[24] A. Stentz and I. C. Mellon, “Optimal and efficient path planning for unknown and
dynamic environments,” International Journal of Robotics and Automation, vol. 10,
pp. 89–100, 1993. 2.3.6
[25] S. Koenig and M. Likhachev, “D* lite,” in Eighteenth national conference on Artificial
intelligence, pp. 476–483, American Association for Artificial Intelligence, 2002. 2.3.7
[26] P. Kumar Das, S. Patro, C. Panda, and B. Balabantaray, “D* lite algorithm based
path planning of mobile robot in static environment,” Int. J. Comput. Commun.
Technol.(IJCCT), vol. 2, pp. 32–36, 2011. 2.3.7
[27] J. A. M. Pérez, “Heurísticas de búsqueda para problemas discretos de
localización-asignación,” in Lecturas en teoría de localización, pp. 107–134,
Secretariado de Publicaciones, 1996. 3.2.1
[28] J. Goyal and K. Nagla, “A new approach of path planning for mobile robots,” in
Advances in Computing, Communications and Informatics (ICACCI, 2014
International Conference on, pp. 863–867, Sept 2014. 3.2.2
[29] A. Bhatia and E. Frazzoli, Incremental search methods for reachability analysis of
continuous and hybrid systems. Springer, 2004. 3.4
[30] A. J. Broder, “Strategies for efficient incremental nearest neighbor search,” Pattern
Recognition, vol. 23, no. 1, pp. 171–178, 1990. 3.4

60
BIBLIOGRAFÍA BIBLIOGRAFÍA

[31] B. Bonet and H. Geffner, “Planning as heuristic search,” Artificial Intelligence,

vol. 129, no. 1, pp. 5–33, 2001. 3.4
[32] B. Bonet and H. Geffner, “Planning with incomplete information as heuristic search in
belief space,” 2000. 3.4
[33] B. Bonnet and H. Geffner, “Hsp: Heuristic search planner,” 1998. 3.4
[34] O. Wink, W. Niessen, and M. Viergever, “Minimum cost path determination using a
simple heuristic function,” in Pattern Recognition, 2000. Proceedings. 15th
International Conference on, vol. 3, pp. 998–1001 vol.3, 2000. 3.4
[35] J. Pearl, Heuristics: Intelligent search strategies for computer problem solving.
Addison-Wesley Pub. Co., Inc.,Reading, MA, Jan 1984. 3
[36] S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach. Prentice Hall
series in artificial intelligence, Prentice Hall, 2010. 3.4.2
[37] G. Paganelli, S. Delprat, T. Guerra, J. Rimaux, and J. Santin, “Equivalent
consumption minimization strategy for parallel hybrid powertrains,” in Vehicular
Technology Conference, 2002. VTC Spring 2002. IEEE 55th, vol. 4, pp. 2076–2081
vol.4, 2002. 3.5.2.1

61
Capítulo 6

ANEXOS

6.1 CÓDIGOS IMPLEMENTADOS EN MATLAB

6.1.1. Best-First Search
1. Función Main.m.

1 function [S1,t] = Main(D,N,in,fin,Mocu)

2 close all
3 tic;
4 %Main(10, 10, [5 4], [9 9],J) ejemplo
5 %D=dimensión, N= cantidad de puntos
6 %%in=vector con las coordenadas de inicio,
7 %fin=vector con las coordenadas de la meta.
8 %Mocu=matriz de ocupados
9 %%inicializacion de entorno y explorador
10 div=D/N; %escala de separacion entre nodos
11 S1=planificador; %creción del objeto explorador S1
12 S1.ini=in; %carga del punto de inicio.
13 S1.fin=fin; %carga del punto final
14 S1.pos=[S1.ini]; %carga de la posición actual del objeto.
15 S1.Mexplorados=zeros(N+1); %matriz que almacena el valor H(x)
16 %% Inicio del loop
17 % S1.d = distancia entre el punto actual y la meta
18 % S1.vecinos = vecinos de la posicion actual
19 % S1.pos= Posicion actual del movil
20 while 1
21 S1.ruta=[S1.ruta,S1.pos']; %se carga la posicion actual a la ruta
22 D=Entorno(D,N,S1);
23 S1.d=distanp(S1.pos,S1.fin);
24 if S1.d==0
25 break
26 end
27 S1.vecinos = sucesores(S1.pos,D,div);
28 [S1.vecinos, S1.Mexplorados]=...
29 Explorar(S1.vecinos,S1.Mexplorados,S1.fin,S1.pos,Mocu,div);
30 [S1]=heuristica(S1,div);
31 %pause(0.1)
32 end
33 t=toc;
34 end

62
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

2. Funcion Entorno.m

1 function [D] = Entorno(D,N,S1)

2 %D=dimensiones del entorno, la matris debe ser cuadrada.
3 %N=Cantidad de puntos en el espacio selecionado en D.
4 %S=Planificador
5 %Creacio del entorno.
6
7 Xn = zeros(N+1,N+1); Yn = zeros(N+1,N+1); %inicializacion de las variables
8
9 % Creacion de entorno
10 for i = 1:N+1
11 Xn(i,:) = linspace((i-1)*round(D/N),(i-1)*round(D/N),N+1);
12 Yn(i,:) = linspace(0,D,N+1);
13 end
14
15 clf
16 genentorno([10 50],[30 0],0,[20 30],[30 70],0,[10 10],[70,65],100,20);
17 hold on;
18 %grafica del nodo inicial del agente
19 plot(S1.ini(1),S1.ini(2),'gs','MarkerSize',10,'LineWidth',3)
20 %grafica del nodo final
21 plot(S1.fin(1),S1.fin(2),'rs','MarkerSize',10,'LineWidth',3)
22 %grafica de la posicion del agente
23 plot(S1.pos(1),S1.pos(2),'ro','MarkerSize',10,'LineWidth',2)
24 plot([S1.pos(1),S1.fin(1)],[S1.pos(2),S1.fin(2)],':k')
25 plot(S1.ruta(1,:),S1.ruta(2,:),'k','LineWidth',2);
26 end

3. Funcion distanp.m

1 function [D] = distanp( Ps,Pg )

2 D =((Pg(1)-Ps(1))^2+(Pg(2)-Ps(2))^2)^(1/2);
3 end

4. Funcion sucesores.m

1 function [ suce ] = sucesores(S,D,div)

2 A=div;
3 k=1;
4 if ( (S(2))+A <= D )
5 succ(k,1) = S(1);
6 succ(k,2) = S(2)+A;
7 k=k+1;
8 end
9
10 if ((S(1)+A <= D )&(S(2)+A <= D ))
11 succ(k,1) = S(1)+A;
12 succ(k,2) = S(2)+A;
13 k=k+1;
14 end
15
16 if ( (S(1))+A <= D )
17 succ(k,1) = S(1)+A;
18 succ(k,2) = S(2);
19 k=k+1;
20 end
21
22 if ((S(1)+A <= D )&(S(2)-A >= 0 ))
23 succ(k,1) = S(1)+A;
24 succ(k,2) = S(2)-A;
25 k=k+1;
26 end

63
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

27
28 if ( (S(2))-A >= 0 )
29 succ(k,1) = S(1);
30 succ(k,2) = S(2)-A;
31 k=k+1;
32 end
33
34 if ((S(1)-A >= 0 )&(S(2)-A >= 0 ))
35 succ(k,1) = S(1)-A;
36 succ(k,2) = S(2)-A;
37 k=k+1;
38 end
39
40 if ( (S(1))-A >= 0 )
41 succ(k,1) = S(1)-A;
42 succ(k,2) = S(2);
43 k=k+1;
44 end
45
46 if ((S(1)-A >= 0 )&(S(2)+A <= D ))
47 succ(k,1) = S(1)-A;
48 succ(k,2) = S(2)+A;
49 end
50 suce=succ;
51
52 end

5. Funcion Explorar.m

1 function [Svecinos,Sexplo] = Explorar(Svecinos,Sexplo,Sfin,Spos,Moc,div)

2 %EXPLORAR Summary of this function goes here
3 % Detailed explanation goes here
4 %S=Vecino del objto en la poscion actuat
5 %Moc=matriz de ocupados
6 %SMoc=tamaño de la matriz de ocupados
7 %Ssuce=cantidad de suscesores
8 %Sexplo = matriz de explorados
9 SMoc=size(Moc);
10 Ssuce=size(Svecinos);
11
12 for i=1:Ssuce(1)
13 %se exploran cuales nodos de la matriz estan libres y ocupados
14 Oc(i,1) = Moc(SMoc(2)-(Svecinos(i,2)/div) , (Svecinos(i,1)/div)+1);
15 if Oc(i,1)==1 %condicion para darle valor de 1000 a un nodo ocupado
16 Oc(i,1)=1000;
17 Sexplo(SMoc(2)-(Svecinos(i,2)/div) ,...
18 (Svecinos(i,1)/div)+1 , 1)=1000;
19 end
20 if (Oc(i,1)==0 && Sexplo(SMoc(2)-(Svecinos(i,2)/div) ,...
21 (Svecinos(i,1)/div)+1 , 1)==0)
22 Oc(i,1)= distanp(Svecinos(i,:),Sfin);
23 Sexplo(SMoc(2)-(Svecinos(i,2)/div) ,...
24 (Svecinos(i,1)/div)+1 , 1)=Oc(i,1);
25 end
26 end
27
28 Sexplo(SMoc(2)-Spos(1,2)/div , (Spos(1,1)/div)+1)=distanp(Spos,Sfin);
29
30
31 for i=1:Ssuce(1)
32 Oc(i,1)=Sexplo(SMoc(2)-(Svecinos(i,2)/div),(Svecinos(i,1)/div)+1 , 1);
33 end
34 Svecinos=[Svecinos,Oc];
35 end

64
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

6. Funcion heurística.m

1 function [ S1 ] = heuristica( S1,div )

2 %HEURISTICA Summary of this function goes here
3 % Detailed explanation goes here
4 [Val,Posval]=min(S1.vecinos(:,3));
5 S1.pos = S1.vecinos(Posval,1:2);
6 end

7. Clase planificador.m para el algoritmo Best-First Search

1 classdef planificador<handle
2 %UNTITLED3 Summary of this class goes here
3 % Detailed explanation goes here
4
5 properties
6 ini=[]; %vector de inicio
7 fin=[]; %vecto de fin
8 pos=[]; %vector de posicion actual
9 ruta=[]; %ruta recorrida
10 vecinos=[]; %vecinos actuales; con relacion a pos
11 d=[]; %distancia de posicion actual a la meta
12 Mexplorados=[]; %matriz del espacio explorado
13 end
14
15
16 end

65
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

6.1.2. A* Search
Teniendo en cuenta que solo se modificaron las funciones Main.m y heuristica.m con respecto a las
funciones presentadas anteriormente, en esta sección solo se presenta las funciones que han tenido cambios,
las demás se conservan igual por lo cual agregarlas seria redundante.
1. Funcion Main.m

1 function [S1,t] = Main(D,N,in,fin,Mocu)

2 close all
3 tic;
4 %Main(10, 10, [5 4], [9 9],J) ejemplo
5 %D=dimensión, N= cantidad de puntos,
6 %in=vector con las coordenadas de inicio,
7 %fin=vector con las coordenadas de la meta.
8 %Mocu=matriz de ocupados
9 %%inicializacion de entorno y explorador
10 div=D/N; %escala de separacion entre nodos
11 S1=planificador; %creción del objeto explorador S1
12 S1.ini=in; %carga del punto de inicio.
13 S1.fin=fin; %carga del punto final
14 S1.pos=[S1.ini]; %carga de la posición actual del objeto.
15 S1.Mexplorados=zeros(N+1); %matriz que almacena el valor H(x)
16 %% Inicio del loop
17 % S1.d = distancia entre el punto actual y la meta
18 % S1.vecinos = vecinos de la posicion actual
19 % S1.pos= Posicion actual del movil
20 while 1
21 S1.ruta=[S1.ruta,S1.pos']; %se carga la posicion actual a la ruta
22 D=Entorno(D,N,S1);
23 S1.d=distanp(S1.pos,S1.fin);
24 if S1.d==0
25 break
26 end
27 S1.vecinos = sucesores(S1.pos,D,div);
28 [S1.vecinos, S1.Mexplorados]=...
29 Explorar(S1.vecinos,S1.Mexplorados,S1.fin,S1.pos,Mocu,div);
30 [S1]=heuristica(S1,div);
31 % pause(0.2)
32 end
33
34 t=toc;
35 end

2. Funcion heurística.m

1 function [S1,t] = Main(D,N,in,fin,Mocu)

2 close all
3 tic;
4 %Main(10, 10, [5 4], [9 9],J) ejemplo
5 %D=dimensión, N= cantidad de puntos,
6 %in=vector con las coordenadas de inicio,
7 %fin=vector con las coordenadas de la meta.
8 %Mocu=matriz de ocupados
9 %%inicializacion de entorno y explorador
10 div=D/N; %escala de separacion entre nodos
11 S1=planificador; %creción del objeto explorador S1
12 S1.ini=in; %carga del punto de inicio.
13 S1.fin=fin; %carga del punto final
14 S1.pos=[S1.ini]; %carga de la posición actual del objeto.
15 S1.Mexplorados=zeros(N+1); %matriz que almacena el valor H(x)
16 %% Inicio del loop
17 % S1.d = distancia entre el punto actual y la meta
18 % S1.vecinos = vecinos de la posicion actual
19 % S1.pos= Posicion actual del movil

66
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

20 while 1
21 S1.ruta=[S1.ruta,S1.pos']; %se carga la posicion actual a la ruta
22 D=Entorno(D,N,S1);
23 S1.d=distanp(S1.pos,S1.fin);
24 if S1.d==0
25 break
26 end
27 S1.vecinos = sucesores(S1.pos,D,div);
28 [S1.vecinos, S1.Mexplorados]=...
29 Explorar(S1.vecinos,S1.Mexplorados,S1.fin,S1.pos,Mocu,div);
30 [S1]=heuristica(S1,div);
31 % pause(0.2)
32 end
33
34 t=toc;
35 end

3. Clase planificador.m para el algoritmo A* Search

1 classdef planificador<handle
2 %UNTITLED3 Summary of this class goes here
3 % Detailed explanation goes here
4
5 properties
6 ini=[]; %vector de inicio
7 fin=[]; %vecto de fin
8 pos=[]; %vector de posicion actual
9 ruta=[]; %ruta recorrida
10 vecinos=[]; %vecinos actuales; con relacion a pos
11 d=[]; %distancia de posicion actual a la meta
12 Mexplorados=[]; %matriz del espacio explorado
13 gx=[] %sumatorio de costos de moverse entre puntos
14 Nopen=[] %lista de nodos abiertos
15 Nclose=[] %lista de nodos cerrados
16
17 end
18
19
20 end

6.1.3. Generación del entorno

1. Funcion entorno.m

1
2 function [N1] = entorno(E1,U1,R1,E2,U2,R2,E3,U3,A,D)
3
4 %% % % FUNCION
% QUE ENTREGA LOS NODOS OCUPADOS EN FORMA DE MATRIZ BINARIA
5
6
7 %Primer elemento. Rectangulo.
8
9 %E1 = Vector de escalamiento en eje X, Y y Z respectivamente.
10 %U1 = Vector de ubicacion coordenado en el eje X y Y respectivamente.
11 %R1 = Rotacion en pi radianes.
12
13 %Segundo elemento. Rectángulo.
14
15 %E2 = Vector de escalamiento en eje X, Y y Z respectivamente.
16 %U2 = Vector de ubicacion coordenado en el eje X y Y respectivamente.
17 %R2 = Rotacion elemento 2 en pi radianes.
18
19 %Tercer elemento. Cilindro.

67
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

20 %E3 = Escalamiento en el eje X y Y

21 %EA3 = Escalamiento en el eje Y.
22 %U3 = ubicacion coordenado en el eje X y Y.
23
24 %M = ubicacion del movil en el entorno
25 %A = El area del entorno es cuadrado, A define el lado del cuadrado.
26 %D = Es la dimension de los nodos en el entorno, que seria en total DxD
27
28 %% % % % %Funcion que genera los elementos de la escena
29 [X1,Y1,X2,Y2,X3,Y3] = geo(E1,U1,R1,E2,U2,R2,E3,U3);
30
31 %% % %
Funcion que genera los nodos ocupados y no ocupados
32 [XNn,YNn,xs1,ys1,xs2,ys2,xs3,ys3] = NODOS2(E1,U1,R1,E2,U2,R2,E3,U3,A,D);
33
34 figure
35 plot(X1,Y1,X2,Y2,X3,Y3,0,100);grid on;axis equal;
36 hold on
37 plot(XNn,YNn,'b*',xs1,ys1,'R*',xs2,ys2,'r*',xs3,ys3,'r*')
38
39 %% % % %Los vectores que contienes las coordenadas de visualizacion de los
40 %% % % %nodos ocupados, son cambiados por una matriz binaria en donde 1
41 %% % % %corresponde al nodo ocupado
42 T1=size(xs1);
43
44 for j=1:T1(1)
45 for i=1:T1(2)
46
47 if xs1(j,T1(1)-(i-1)) > 0 || ys1(j,T1(1)-(i-1)) > 0 || ...
48 xs2(j,T1(1)-(i-1)) >0 || ys2(j,T1(1)-(i-1)) > 0 ...
49 || xs3(j,T1(1)-(i-1)) > 0 || ys3(j,T1(1)-(i-1)) > 0
50 N1(i,j) = 1; %% % Matriz binaria de nodos ocupados
51 else
52 N1(i,j) = 0;
53 end
54 end
55 end
56
57 end

2. Funcion geo.m

1 function [XO3E,YO3E,XO1E,YO1E,XP1E,YP1E] = geo(E1,U1,R1,E2,U2,R2,E3,U3);

2
3 %% %XO3E,YO3E = Vector de graficacion del cilindro
4 %% %XO1E,YO1E = Vector de graficacion de primer rectángulo
5 %% %XP1E,YP1E = Vector de graficacion del segundo rectángulo
6
7 % %ELEMENTO 1 (RECTANGULO 1)
8 %
9 % %Generamos vectores de graficacion
10
11 XO11 = linspace(1,0,E1(1)*2)*E1(1); %Escalamiento lado 1 (Largo 1)
12 YO11 = linspace(0,0,E1(1)*2);
13 [XRL1 YRL1] = rotacion2(XO11,YO11,R1); %Rotacion lado 1
14
15 XO12 = linspace(0,1,E1(2)*2)*E1(2); %Escalamiento lado 2
16 YO12 = linspace(0,0,E1(2)*2);
17 [XRA1 YRA1] = rotacion2(XO12,YO12,R1+pi/2); %Rotacion lado 2 (Ancho 1)
18
19 %Se conforma el rectangulo, trasladando los lados.
20
21 XO21 = linspace(0,1,E1(1)*2)*E1(1); %Escalamiento lado 1 (Largo 1)
22 YO21 = linspace(0,0,E1(1)*2);
23 [XRL21 YRL21] = rotacion2(XO21,YO21,R1); %Rotacion lado 1
24 XRL2 = XRL21 + XRA1(length(XRA1)); %lado 3 (Largo 2) y traslado
25 YRL2 = YRL21 + YRA1(length(YRA1));

68
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

26
27 XO22 = linspace(1,0,E1(2)*2)*E1(2); %Escalamiento lado 2
28 YO22 = linspace(0,0,E1(2)*2);
29 [XRA22 YRA22] = rotacion2(XO22,YO22,R1+pi/2); %Rotacion lado 2 (Ancho 1)
30 XRA2 = XRA22 + XRL1(1); %Lado 4 (Ancho 2) y traslado
31 YRA2 = YRA22 + YRL1(1);
32
33
34
35 %Guardamos todos los puntos del rectangulo 1 en los vectores XO1 YO1
36
37 XO1=XRL1;
38 XO1(length(XO1)+1:length(XO1)+length(XRA1))=XRA1;
39 XO1(length(XO1)+1:length(XO1)+length(XRL2))=XRL2;
40 XO1(length(XO1)+1:length(XO1)+length(XRA2))=XRA2;
41
42 YO1=YRL1;
43 YO1(length(YO1)+1:length(YO1)+length(YRA1))=YRA1;
44 YO1(length(YO1)+1:length(YO1)+length(YRL2))=YRL2;
45 YO1(length(YO1)+1:length(YO1)+length(YRA2))=YRA2;
46
47
48 %% % % TRASLADO(
% hacia la ubicacion en el entorno)
49
50 XO1E=XO1+U1(1);
51 YO1E=YO1+U1(2);
52
53 %Inicializacion de matrices
54
55 XO1F = zeros(10,length(XO1));
56 YO1F = zeros(10,length(XO1));
57 ZO1F = zeros(10,length(XO1));
58
59 %ELEMENTO 2 (RECTANGULO 2)
60
61
62 %Generamos vectores de graficacion
63
64
65 XP11 = linspace(0,1,E2(1)*3)*E2(1); %Escalamiento lado 1 (Largo 1)
66 YP11 = linspace(0,0,E2(1)*3);
67 [XPL1 YPL1] = rotacion2(XP11,YP11,R2); %Rotacion lado 1
68
69 XP12 = linspace(0,1,E2(2)*3)*E2(2); %Escalamiento lado 2 (Ancho 1)
70 YP12 = linspace(0,0,E2(2)*3);
71 [XPA1 YPA1] = rotacion2(XP12,YP12,R2+pi/2); %rotacion lado 2
72
73 %Se conforma el rectangulo, trasladando los lados.
74
75 XPL2 = XPL1 + XPA1(length(XPA1)); %Lado 3 (Largo 2) y traslado
76 YPL2 = YPL1 + YPA1(length(YPA1));
77
78 XPA2 = XPA1 + XPL1(length(XPL1)); %Lado 4 (Ancho 2) y traslado
79 YPA2 = YPA1 + YPL1(length(YPL1));
80
81 %% %ESCALAMIENTO
82
83 %Guardamos puntos de rectangulo 2 en los vectores XO1 YO1
84
85 XP1=XPL1;
86 XP1(length(XP1)+1:length(XP1)+length(XPA1))=XPA1;
87 XP1(length(XP1)+1:length(XP1)+length(XPL2))=XPL2;
88 XP1(length(XP1)+1:length(XP1)+length(XPA2))=XPA2;
89
90 YP1=YPL1;
91 YP1(length(YP1)+1:length(YP1)+length(YPA1))=YPA1;
92 YP1(length(YP1)+1:length(YP1)+length(YPL2))=YPL2;
93 YP1(length(YP1)+1:length(YP1)+length(YPA2))=YPA2;

69
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

94
95
96 %% % % TRASLADO
% (Hacia la ubicacion en el entorno)
97
98 XP1E=XP1+U2(1);
99 YP1E=YP1+U2(2);
100
101 %Inicialiacion de matrices
102
103 XP1F = zeros(10,length(XP1));
104 YP1F = zeros(10,length(XP1));
105 ZP1F = zeros(10,length(XP1));
106
107 %ELEMENTO 3 (CILINDRO)
108 %se escala y se ubica en el entrono
109 teta = linspace(0,2*pi,E3(1)*8);
110
111 i=0;
112 for i=1:length(teta)
113 XO3E(i) = cos(teta(i));
114 YO3E(i) = sin(teta(i));
115 end
116
117 XO3E = XO3E*E3(1)+U3(1);
118 YO3E = YO3E*E3(2)+U3(2);
119 i=0;

3. Funcion angulo.m

1 %funcion para hallar en angulo positivo de 0 a 2*pi

2 %resultante del punto (x,y)
3 function[teta]=angulo(x,y)
4 %consideraciones
5 x=round(x*1000000)/1000000;
6 y=round(y*1000000)/1000000;
7
8
9 if y>=0
10 con1=1;
11 else
12 con1=0;
13 end
14 if x>=0
15 con2=2;
16 else
17 con2=0;
18 end
19
20 %hallamos el angulo
21 %dependiendo del cuadrante
22 %en donde se ubica el pareja coordenada
23
24 if con1+con2==2
25 teta=atan2(y,x)+2*pi;
26 elseif con1+con2==3
27 teta=atan(y/x);
28 else
29 teta=atan(y/x)+pi;
30 end
31 if x==0
32 con3=1;
33 else
34 con3=0;
35 end
36 if y==0
37 con4=1;

70
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

38 else
39 con4=0;
40 end
41 if con3+con4==2
42 teta=pi/2;
43 else
44 teta=teta;
45 end
46
47 if x==0 & y==0
48 teta=0;
49 else
50 teta=teta;
51 end

4. Funcion NODOS2.m

1 function[XNn,YNn,XS1,YS1,XS2,YS2,XS3,YS3] = ...
2 NODOS2(E1,U1,R1,E2,U2,R2,E3,U3,A,D)
3
4 %% % XNn YNn = nodos no ocupados.
5 %% % XS1 YS1 = nodos ocupados por el primer elemento.
6 %% % XS2 YS2 = nodos ocupados por el segundo elemento.
7 %% % XS3 YS3 = nodos ocupados por el tercer elemento.
8
9 %GENERACION DE LOS NODOS EN EL ENTORNO
10
11 %Inicializacion de matices
12 Xn = zeros(D+1,D+1); Yn = zeros(D+1,D+1); Zn = zeros(D+1,D+1);
13
14 for i = 1:D+1
15 Xn(i,:) = linspace((i-1)*round(A/D),(i-1)*round(A/D),D+1);
16 Yn(i,:) = linspace(0,A,D+1);
17 Zn(i,:) = linspace(0,0,D+1);
18 end
19
20 %% % % % % % % % % % % % % % % % % %SE
% % GUARDAN
%% NODOS EN VECTORES % % % % % % % % % % % % % % % % % % % %
21 Tam = size(Xn);
22 i=0;j=0; XNn = []; YNn = [];
23 for i=1:Tam(1)
24 for j=1:Tam(2)
25 XNn(length(XNn)+1) = Xn(i,j);
26 YNn(length(YNn)+1) = Yn(i,j);
27 end
28 end
29
30 %
31 % % % % % % % % %SE
% RETIRAN LOS NODOS DEL AREA DE LOS ELEMENTOS % % % % % % % % % % % % % %
32 %
33 % % % % % % % % % % % % % % % % %ELEMENTO
%%%% 1 Y ELEMENTO 2 % % % % % % % % % % % % % % % % % % % % % % % % %
34 %
35 off = 6; %Offset de seguridad
36 %
37 %% %Trasladamos y rotamos nodos segun ubicacion y rotacion de los elementos
38
39 Xnr1 = Xn-U1(1); Ynr1 = Yn-U1(2);
40 [XnR1 YnR1] = rotacion2(Xnr1,Ynr1,-R1);
41
42 Xnr2 = Xn-U2(1); Ynr2 = Yn-U2(2);
43 [XnR2 YnR2] = rotacion2(Xnr2,Ynr2,-R2);
44
45 T1 = size(XnR1);
46
47 %Inicializacon de matrices
48 XS1 = zeros(T1(1),T1(2));
49 XS2 = XS1;

71
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

50 YS1 = XS1; YS2 = XS1;

51 XS3 = XS1; YS3 = YS1;
52
53 %% % GENERAMOS NODOS OCUPADOS Y LOS RETIRAMOS DE LOS NODOS ORIGINALES
54 i=0; j=0;
55 for i=1:T1(1)
56 for j= 1:T1(2)
57 if XnR1(i,j) <= E1(1)+off && XnR1(i,j) >= -off && ...
58 YnR1(i,j) <= E1(2)+off && YnR1(i,j) >= -off
59 XS1(i,j) = Xn(i,j);
60 YS1(i,j) = Yn(i,j);
61 Xn(i,j) = 0;
62 Yn(i,j) = 0;
63 end
64 if XnR2(i,j) <= E2(1)+off && XnR2(i,j) >= -off && ...
65 YnR2(i,j) <= E2(2)+off && YnR2(i,j) >= -off
66 XS2(i,j) = Xn(i,j);
67 YS2(i,j) = Yn(i,j);
68 Xn(i,j) = 0;
69 Yn(i,j) = 0;
70 end
71 end
72 end
73
74
75
76
77 %% % % % % % % % % % % % % ELEMENTO
%%%% 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
78
79 X3of = Xn - U3(1); % Se quita offset de nodos.
80 Y3of = Yn - U3(2);
81
82 T3 = size(X3of);
83
84
85 %distancia euclidiana entre centro de circunferencia y nodos
86
87 dis3 = zeros(T3(1),T3(2));
88 i=0; j=0;
89 for i=1:T3(1)
90 for j= 1:T3(2)
91 dis3(i,j) = (X3of(i,j)^2+Y3of(i,j)^2)^(1/2);
92 if dis3(i,j) <= E3(2)+off;
93 XS3(i,j) = Xn(i,j);
94 YS3(i,j) = Yn(i,j);
95 Xn(i,j) = 0;
96 Yn(i,j) = 0;
97 end
98 end
99 end
100
101 %% % % % % % % % % % % % % % % % ORDENAMOS
%%%% LA MATRIZ DE LOS NODOS EN VECTORES % % % % % % %
102 k=1;
103 for i=1:T1(1)
104 for j=1:T1(2)
105 if Xn(i,j) > -1
106 XN(k)=Xn(i,j);
107 YN(k)=Yn(i,j);
108 k=k+1;
109 end
110 end
111 end
112
113 %% % % % % % % % % % % % % ORDENAMOS
%%% EN VECTORES LOS NODOS OCUPADOS % % % % % % % % % % % % % %
114 i=0; j=0;T=0; xs1 = []; ys1=[];
115 T=size(XS1);
116
117 for i=1:T(1)

72
6.1. CÓDIGOS IMPLEMENTADOS EN MATLAB CAPÍTULO 6. ANEXOS

118 for j = 1:T(2)

119 xs1(length(xs1)+1) = XS1(i,j);
120 ys1(length(ys1)+1) = YS1(i,j);
121 end
122 end
123
124
125 i=0; j=0;T=0; xs2 = []; ys2=[];
126 T=size(XS2);
127
128 for i=1:T(1)
129 for j = 1:T(2)
130 xs2(length(xs2)+1) = XS2(i,j);
131 ys2(length(ys2)+1) = YS2(i,j);
132 end
133 end
134
135 i=0; j=0;T=0; xs3 = []; ys3=[];
136 T=size(XS3);
137 for i=1:T(1)
138 for j = 1:T(2)
139 xs3(length(xs3)+1) = XS3(i,j);
140 ys3(length(ys3)+1) = YS3(i,j);
141 end
142 end

5. Funcion rotacion2.M

1 %Funcion que rota puntos (B1,B2 eje x eje y) un angulo Ang

2 %B1 y B2 son matrices
3 function[XX1,YY1,d1,A1]=rotacion2(B1,B2,Ang)
4 L=size(B1);
5 for i=1:L(1)
6 for j=1:L(2)
7 d1(i,j)=(B1(i,j)^2+B2(i,j)^2)^(1/2);
8 A1(i,j)=angulo(B1(i,j),B2(i,j));
9 XX1(i,j)=cos(Ang+A1(i,j))*d1(i,j);
10 YY1(i,j)=sin(Ang+A1(i,j))*d1(i,j);
11 end
12 end

73