Explicación del algoritmo de búsqueda de trayectorias para múltiples drones.

Al intentar resolver un algoritmo de búsqueda de rutas para múltiples drones.

¿Alguna vez ha observado el funcionamiento de un robot en la realidad?
¿Ha considerado cómo se desplaza un objeto, que por definición es inanimado, en el espacio?
¿Cómo se logra que sus dedos se muevan y cómo se les hace avanzar?
¿Cómo se permite que los drones vuelen, por ejemplo?

Este trabajo no es sencillo, ya que cada paso y cada movimiento deben ser planificados y codificados desde una perspectiva global y a largo plazo.

¿Qué es un «algoritmo de navegación autónoma»?

Se trata de un conjunto de técnicas y métodos empleados por robots o vehículos para desplazarse y realizar tareas sin la necesidad de intervención humana.
Este algoritmo les permite observar, orientarse, tomar decisiones y actuar en su entorno.
Estos algoritmos están diseñados para asegurar la seguridad y la eficacia en la ejecución de las tareas que se les asignan.

Adentrándonos un poco más en el tema.
Todo lo relacionado con el espacio es relativamente sencillo; es más simple, por ejemplo, que el aprendizaje automático, ya que se basa únicamente en cálculos geométricos, cálculos de grafos o cálculos trigonométricos.
Estos cálculos son considerablemente más precisos y facilitan la obtención de una solución completa a un problema específico. Esto no tiene relación con el intento de replicar el cerebro humano, su forma de pensar y su inteligencia.
Esta es la creencia que se ha formado a partir de una de mis experiencias, la cual consistió en intentar desarrollar un algoritmo para la búsqueda de trayectorias de drones.

Este algoritmo de búsqueda de trayectoria fue solicitado para un espectáculo de luces.
El objetivo consistía en determinar una ruta que permitiera a todos los drones operar en un mismo espacio sin que se produjeran colisiones entre ellos.
El algoritmo debía facilitar el desplazamiento de los drones de un lugar a otro, generando así el espectáculo de luces.

El algoritmo permite que múltiples drones se desplacen dentro de un mismo espacio desde un punto A hasta un punto B sin colisionar entre sí.

Considerando que ya existe un algoritmo de búsqueda de trayectorias para drones, pensé que podría ser relevante utilizarlo.

La idea original consistía en desarrollar una matriz en tres dimensiones. De este modo, se segmenta el espacio en cuadrados, y cada cuadrado abarca tanto las dimensiones del dron como la zona de seguridad.

A continuación, se desplaza el dron gradualmente, cada vez en una dimensión, y se coloca una bandera en la matriz para indicar que el lugar está ocupado. De este modo, se informa a los demás drones que no deben moverse hacia ese espacio.

Se puede llevar a cabo este cálculo gráfico de manera sencilla: x + 1, o y + 1, o z + 1.

Los algoritmos de navegación empleados en la actualidad para el vuelo de drones se centran en determinar la trayectoria en el espacio que permite desplazarse del punto A al punto B, utilizando un algoritmo que identifica el camino más corto.

Para ello, se segmenta el espacio en cubos. Cada cubo representa un nodo, y cada nodo está vinculado a todos los demás nodos que se encuentran físicamente cercanos a él. En un grafo, por ejemplo, x está conectado a x + 1, y así sucesivamente.

Se intenta posteriormente identificar la ruta más corta entre el nodo A y el nodo B.
El algoritmo de Dijkstra se utiliza para determinar el camino más corto entre un nodo específico, conocido como "nodo fuente", y otros nodos dentro de un grafo. Este algoritmo se basa en los pesos de las aristas para identificar la ruta que minimiza la distancia total (peso) entre el nodo fuente y los demás nodos.

Este algoritmo no ha proporcionado la solución al problema planteado.

Aquí el algoritmo es distinto. No es necesario emplear el algoritmo de trayectoria para un dron específico, sino que se requiere encontrar un algoritmo que permita sincronizar todos los drones en conjunto.
Además, en el espacio físico, no es necesario emplear el algoritmo de nodos, sino que es más adecuado utilizar funciones de grafos. De esta manera, se puede calcular la línea entre dos puntos del grafo y determinar fácilmente el siguiente punto. Para trasladarse de un punto A a un punto B dentro de un grafo, se puede realizar utilizando una dimensión a la vez: x+y, y+1, z+1.

Se puede encontrar el camino desplazándose en tres dimensiones y utilizando el cálculo de la distancia D en un grafo tridimensional. De este modo, en cada etapa, se puede determinar el siguiente punto aplicando la fórmula D.
Este enfoque permite que el trayecto sea más corto, ya que en lugar de moverse una dimensión a la vez, es decir, x + 1, y + 1, z + 1, que implica desplazamientos hacia arriba, abajo, a la derecha, a la izquierda, adelante o atrás, se avanza directamente hacia el objetivo. Para ello, es necesario calcular el siguiente punto mediante el cálculo de la distancia y la longitud del paso.
Aunque esta solución no ha sido implementada en el algoritmo, representa una idea de mejora que ha sido parcialmente desarrollada, por lo que podría afirmar que su éxito es posible sin enfrentar otros problemas.

No es necesario intentar encontrar el camino más corto examinando todas las opciones, ya que, por lo general, un dron tendrá que esperar o moverse, o bien otro deberá desviarse, por lo que no importa de qué dron se trate.
El camino más directo consiste en avanzar recto hacia el destino y, posteriormente, abordar el problema de la colisión.
En términos generales, para todos los drones, se considerará la ruta más corta, y se podrá desarrollar un algoritmo de manera ágil, sin necesidad de recurrir a la fuerza bruta (probar todas las opciones mediante recursión) o a un método similar.

La solución en este caso consiste en desarrollar un algoritmo que permita la sincronización de todos los drones de manera conjunta. Para lograrlo, utilizaremos funciones gráficas.

Además, no es necesario examinar todos los nodos para determinar cuál es el camino más corto, ya que si se desplaza cada dron en el grafo directamente del punto A al punto B, se obtiene el camino más corto. En este caso, solo necesitamos abordar el problema de las colisiones y responder a la siguiente pregunta: ¿cómo gestionar el uso de un punto de la matriz por parte de otro dron y cómo evitarlo?

Tenemos, por lo tanto, una gran cantidad de opciones y una variedad considerable de algoritmos diferentes.
He desarrollado varios algoritmos más complejos que no siempre resultaron ser eficaces. Al final, he identificado dos que realmente funcionan y que son sencillos de implementar.

Como ejemplo, procederé a exponer un problema junto con su solución.
Si se produce una colisión con un dron que ya ha llegado a su destino, ¿cuáles son las acciones que se deben tomar?
No podemos esperar a que se marche, ya que habiendo llegado a su destino, no se moverá más.
También es cierto que se puede mover alrededor de él, pero hemos encontrado una solución mejor, más fácil de implementar: simplemente hay que desplazar el dron fijo de su posición para permitir el paso del dron móvil, y luego devolver el dron fijo a su lugar original.

Si en este ejemplo no se tratara de un dron, sino de un árbol, entonces, por supuesto, no sería posible mover el árbol, sino únicamente desplazarse a su alrededor.
Por esta razón, al desarrollar un algoritmo, es fundamental buscar la solución a un problema particular, en lugar de limitarse a replicar otro algoritmo diseñado para abordar un problema diferente.

A veces, la verdadera genialidad radica en identificar la solución más sencilla y efectiva al problema, en lugar de optar por la más complicada.

Es igualmente una regla fundamental: no compliquen las cosas si pueden simplificarlas.


Un problema que se encuentra en el espacio físico puede ser resuelto mediante el uso de un grafo, la geometría o la trigonometría. Siempre es necesario realizar un cálculo para mover un objeto en el espacio.
No intente resolver un problema en el espacio utilizando simples algoritmos de nodos; en su lugar, opte por una solución geométrica si es factible, ya que esto debería proporcionar una solución más rápida y eficiente.

Cuando se trata, por ejemplo, de sortear un obstáculo, ¿por qué no emplear las funciones parabólicas? Al buscar un punto en una parábola, estoy convencida de que las matemáticas proporcionan respuestas a numerosos problemas en el espacio. Solo es necesario conocer todas las fórmulas. De todos modos, es posible hallar soluciones de maneras muy sencillas.

He desarrollado numerosas soluciones para este algoritmo, pero solo he finalizado dos.
No entraré en los detalles de los dos algoritmos, lo cual probablemente haré en uno de los próximos artículos.
La intención de este artículo es explicarle cómo abordar un problema similar.
En resumen:

1. No intente copiar un algoritmo existente si no se ajusta perfectamente a sus necesidades. En su lugar, busque una solución para una situación particular.
2. No intente utilizar la fuerza bruta (es decir, probar todas las posibilidades) en su primer intento, especialmente en situaciones como esta, donde se puede encontrar la solución de manera rápida simplemente avanzando en línea recta, como en un grafo.
Un problema de algoritmo no se limita únicamente a la codificación.
Esto también implica descubrir la manera de solucionar problemas.
Sea creativo y trate de encontrar soluciones como si estuviera en una situación real. Olvídese un poco del código y considere todo esto como un juego.
Intente plasmar todo esto de manera tangible en un papel o en la vida real. Así es como podrá encontrar una solución efectiva para cada problema, como el de mover el dron fijo en lugar de intentar sortearlo.
Primero, trate la cuestión como si fuera un problema de la vida real y, solo después, considere cómo puede programarlo.

En este artículo, presento un ejemplo de algoritmo; sin embargo, mi principal objetivo es detallar los diversos aspectos que se deben considerar al construir un robot.

Si se espera que realice una acción en el espacio (como desplazarse o manipular objetos), es necesario contar con habilidades avanzadas en grafos, geometría y trigonometría, para poder guiarlo en la manipulación de elementos en el entorno tridimensional.

En el ámbito de la robótica, no tenemos la intención de reinventar los cálculos espaciales, ya que todo lo necesario ya ha sido expuesto hace tiempo. Es suficiente con aprender matemáticas y comprender cómo aplicarlas en la programación.

A continuación se presentan algunos ejemplos de la aplicación de los cálculos en el espacio.

1. Movimientos en el espacio de un robot o un dron.
Si tuviera que desarrollar una herramienta como un robot cortacésped, el trabajo probablemente incluiría cálculos gráficos, geometría, cálculos espaciales, entre otros.

¿Por qué no emplear fórmulas más complejas para los robots? No solo considerar la distancia en un grafo o algo similar, sino, por ejemplo, utilizar fórmulas parabólicas para maniobrar alrededor de los objetos.

¿Y en el caso de un vehículo autónomo?
En los sitios de construcción, los vehículos autónomos requieren algoritmos que les permitan crear un grafo de navegación. Estos algoritmos son fundamentales para identificar las rutas más cortas y sin colisiones en entornos dinámicos. Una de las metodologías empleadas es el "Grafo de Visibilidad", que se encarga de calcular el grafo completo y posteriormente busca activamente rutas utilizando algoritmos como A* o Dijkstra.

Es posible utilizar este algoritmo cada vez que se necesite sincronizar múltiples elementos entre sí. Por ejemplo, se puede aplicar en un estudio si se desea que toda la iluminación se desplace por la habitación. También puede ser útil en una escena de espectáculo, donde se busca que todos los elementos se muevan en el escenario.
Esto podría incluso facilitar una coreografía, permitiendo a los diferentes bailarines trasladarse de un lugar a otro... el algoritmo puede mapear la danza en el escenario.

Este algoritmo ha sido diseñado específicamente para sincronizar drones en el contexto de un espectáculo de luces.
Este recurso podría ser empleado en el contexto de cualquier proyecto que requiera el desplazamiento de diversos elementos dentro de un espacio determinado.

Ejemplos de casos de uso con múltiples drones:

. Zona de seguridad

Se deben evaluar los sistemas anti-drones que resguardan aeropuertos, instalaciones industriales y otras infraestructuras críticas mediante el envío simultáneo de drones desde diversas direcciones hacia la zona a proteger.

. Agricultura.

Aplicar tratamientos a diversas cultivos de manera simultánea utilizando varios drones en paralelo.

. Cartografía.

Realizar la cartografía de amplias áreas mediante el uso simultáneo de varios drones.

Compañía de construcción.

La incorporación de drones en el sector de la construcción ha dado inicio a una nueva etapa en términos de eficiencia, precisión y seguridad a lo largo de las diversas etapas de los proyectos constructivos.

Proyectos de topografía.

Mapeo del terreno.

Seguridad y monitoreo.

Uso conjunto de múltiples drones para fines de inspección.

1. Evaluación de propiedades.

Los drones tienen la capacidad de realizar inspecciones visuales detalladas de diversos bienes, con el fin de identificar de manera rápida defectos como: grietas, problemas estructurales, filtraciones, tejas dañadas, corrosión, entre otros.

1. Inspección de techos.

Este sistema aéreo es especialmente idóneo para la inspección de techos. Los drones tienen la capacidad de acceder a lugares que son inaccesibles para las personas. Esto disminuye e incluso elimina el riesgo de lesiones, además de suponer un ahorro de tiempo significativo.

1. Planta de energía, transmisión y distribución.

La tecnología de los drones facilita la verificación del correcto funcionamiento de las líneas de transmisión. Los operadores tienen la capacidad de evaluar un fallo desde el suelo antes de proceder a su reparación. De este modo, los drones mejoran tanto la eficiencia como la rapidez en las labores de mantenimiento.

. Inspección de torres de telecomunicaciones y de radio.

La inspección de torres mediante drones facilita la obtención de imágenes de alta resolución que permiten evaluar las condiciones operativas, lo que a su vez permite a las empresas analizar los resultados y tomar decisiones informadas.

. Sectores del petróleo y el gas.

Los drones tienen la capacidad de inspeccionar las instalaciones de petróleo y gas, lo que facilita la obtención de datos consolidados de manera más rápida, mejorando así la durabilidad de las instalaciones. Además, esto contribuye a disminuir los riesgos y los tiempos de inactividad.

. Manejo de residuos.

Los drones, empleados en la gestión de residuos, pueden facilitar diversas operaciones, incluyendo la recolección de basura y la supervisión de vertederos. Además, tienen la capacidad de limpiar contenedores y detectar y recoger desechos que deben ser eliminados.

. Seguridad vial.

La utilización de drones en el ámbito de la seguridad vial abarca la evaluación de riesgos, la realización de investigaciones exhaustivas sobre accidentes y la supervisión integral de la red de carreteras.

. Monitoreo y control del tráfico.

Los drones se emplean para la vigilancia y el monitoreo del tráfico. Se extraen parámetros de tráfico, tanto en línea como fuera de línea, a partir de los datos de video proporcionados por los drones, con el objetivo de optimizar los mecanismos de seguimiento y gestión del tráfico.

. Administración de las infraestructuras viales.

La tecnología de los drones se emplea para la supervisión y gestión de las infraestructuras viales. Más significativamente, se utiliza para la inspección de puentes y la identificación de deterioros en la calzada.

. Agricultura.

Los drones empleados en el ámbito agrícola facilitan a los agricultores, investigadores y proveedores de servicios la supervisión rápida y eficaz de sus cultivos, el seguimiento del crecimiento de las plantas, la identificación de estrés, la elaboración de planes de tratamiento, entre otras funciones.

. Entorno

La tecnología de los drones constituye el método más ágil, seguro y económico para la cartografía y el monitoreo de extensas áreas en el contexto del estudio, la conservación y la gestión del medio ambiente. Esto resulta especialmente relevante en regiones peligrosas y de difícil acceso para las personas y los vehículos.

. Peligros naturales y desastres naturales.

Los drones permiten una intervención ágil en el terreno ante desastres naturales, de manera notablemente más rápida que los procesos de detección, análisis y respuesta manuales. Su utilización disminuye considerablemente el tiempo de reacción ante emergencias, lo que a su vez reduce la magnitud de los daños potenciales. Equipados con sensores como el infrarrojo, los drones son capaces de localizar con precisión e identificar visualmente a personas en situaciones de peligro, y posteriormente brindarles asistencia mediante la entrega de material médico, medicamentos, equipos y alimentos, así como realizar labores de rescate.

. Administración de bosques

Los drones se emplean para la cartografía de bosques tanto naturales como artificiales, ofreciendo datos precisos y relevantes para el análisis de la salud de los árboles, su conteo, la estimación de la biomasa, el cálculo del índice de dosel y la gestión de las plantaciones.

• El potencial de la cinematografía con drones en la industria del cine y el entretenimiento.

En los últimos años, la industria cinematográfica y del entretenimiento ha experimentado un notable incremento en la utilización de drones para la producción audiovisual. La capacidad de obtener impresionantes tomas aéreas desde una perspectiva elevada ha transformado la forma en que se graban películas y programas de televisión.