Monitoreo con drones en gráficas con viento dinámico

Abstract

Dada una gráfica completa no dirigida, se desea recorrer un subconjunto de sus aristas usando una flotilla de drones. Los drones tienen baterías limitadas que pueden recargarse al regresar a la base y, en principio, el tiempo para recorrer una arista está en función de la distancia entre sus vértices. Sin embargo, ante la presencia de viento el tiempo de recorrer una arista puede depender del sentido en el que se haga. La dificultad del problema aumenta si además la intensidad del viento puede variar de un instante a otro. En esta tesis se aborda el problema anteriormente descrito para el caso particular en el que los vértices son puntos en el plano, el impacto del viento en los tiempos de recorrido de las aristas está relativamente acotado y el subconjunto de las aristas a recorrer inducen un árbol que abarca todos los vértices excepto la base de los drones. Dado que los drones operan simultáneamente y pueden recorrer distintas partes de la gráfica de manera independiente, se desea minimizar el tiempo que emplea el dron con el recorrido más tardado. Esta tesis presenta un modelo matemático para resolver el problema de manera exacta, así como tres heurísticas diferentes para obtener buenas soluciones factibles. La primera de estas heurísticas transforma una solución sin viento y sin batería en una solución con viento y batería. La segunda heurística es un algoritmo glotón sin comunicación entre los drones y la última heurística también es un algoritmo glotón, pero con comunicación entre los drones. Aunque el problema abordado resulta ser lo suficientemente difícil como para que su resolución exacta sea inviable en la práctica, las heurísticas diseñadas son fáciles de implementar y obtuvieron resultados razonables en un tiempo corto de cómputo.