Retiro de una bomba mediante la colaboración de robots

Abstract

El contexto de nuestro problema es el siguiente: suponga que hay una bomba que se encuentra en una posición conocida y se requiere alejarla de dicha posición lo más posible, sin tomar en cuenta cuándo podría explotar. Para ello se cuenta con una cantidad fija de robots que tienen la capacidad de cargar la bomba, actúan uno a la vez, y disponen de una cantidad limitada de energía para desplazarse. Se considera un espacio de trabajo en dos dimensiones sobre la malla entera, donde cuesta una unidad de energía desplazarse entre vértices adyacentes. A este problema le llamamos "Retiro de la Bomba en la Malla (RBM)". Dadas las características del problema se sospecha que es NP-Duro, aunque hasta donde sabemos esto no se ha demostrado. El problema RBM se atacó con 5 técnicas diferentes: 1) modelo de programación entera y el software solucionador Gurobi; 2) una heurística ad hoc glotona; 3) una heurística ad hoc basada en grupos: 4) metaheurístico ascenso a la colina; y 5) metaheurístico recocido simulado. El desempeño de las técnicas se probó al evaluar un conjunto de instancias de distintos tamaños, las cuales diseñamos acorde a las características de RBM. ya que en la literatura no se encontró ninguna. El modelo de programación entera muestra un aumento excesivamente alto en los tiempos de ejecución conforme crece el tamaño de las instancias. Se resolvieron instancias de manera exacta de a lo más 14 robots (instancias de tamaño pequeño) en un tiempo límite de 8 horas. La heurística de grupos, ascenso a la colina y recocido simulado son técnicas donde se puede aplicar el método multiarranque, por lo que inicialmente se compararon con el mismo número de corridas. Los resultados obtenidos muestran que recocido simulado obtiene las mejores so- luciones (en las instancias pequeñas casi siempre llegó al valor óptimo), seguido por ascenso a la colina y las heurísticas glotona y de grupos, las cuales muestran soluciones similares, sin embargo, los tiempos de ejecución se mantienen el mismo orden, siendo el recocido simulado la técnica con los tiempos más altos (solo superados por los del modelo de programación entera) y la heurística glotona la técnica con los tiempos más bajos. Finalmente, se compara la heurística de grupos con el recocido simulado. Debido a que la heurística de grupos muestra una alta variación en sus respuestas y tiene tiempos de ejecución muy bajos, se realiza un número mayor de corridas para esta técnica. Los resultados muestran que al ejecutar la heurística de grupos cientos de veces, se puede obtener soluciones tan buenas o incluso mejores a las del recocido simulado, en tiempos de ejecución mucho menores.