Modelling Unmanned Vehicles Mission Planning problems as Constraint Satisfaction Problems

Abstract

This Master Thesis provides a first analysis of mission planning for Unmanned Air Vehicles (UAVs), dealing with multiple UAVs that must perform one or more tasks in a set of waypoints and specific time windows. The solution plans obtained should fulfill all the constraints given by the different components and capabilities of the UAVs involved over the time periods given. Therefore a Temporal Constraint Satisfaction Problem (TCSP) representation is needed. In a first approach, a temporal constraint model is implemented and tested by performing Backtracking (BT) search in several missions. In this model, a set of resources and temporal constraints are designed to represent the main characteristics (task time, fuel consumption, ...) of this kind of aircrafts. On the other hand, BT algorithm is used to look through the whole solutions space to measure the scalability of the problem. In a second approach, we consider a Constraint Satisfaction Optimization Problem (CSOP) with an optimization function to minimize the fuel cost, the flight time and the number of UAVs needed; and Branch & Bound (B&B) search is employed for solving this CSOP model. Finally, some experiments will be carried out to validate both the quality of the solutions found and the runtime spent to found them.

El presente proyecto final de máster muestra un primer análisis sobre planificación de misiones para Vehículos Aéreos no tripulados (UAVs), donde se trata con múltiples UAVs que deben realizar una o más tareas en un conjunto de puntos o waypoints y en una ventana temporal específica. Los planes obtenidos como solución deben cumplir todas las restricciones dadas por los diferentes componentes y capacidades de los UAVs involucrados en un periodo de tiempo dado. Por tanto, se precisa de una representación del problema como un Problema de Satisfacción de Restricciones Temporales (TCSP). En una primera aproximación, se implementa un modelo de restricciones temporales y se testea ejecutando una búsqueda Backtracking (BT) cronológico en varias misiones. En este modelo, se diseñan un conjunto de restricciones temporales y de recursos para representar las principales características (tiempo de la tarea, consumo de combustible, ...) de este tipo de aviones. Por otro lado, el algoritmo BT es usado para examinar todo el espacio de soluciones para medir la escalabilidad del problema. En una segunda aproximación, consideramos un Problema de Optimización de Satisfacción de Restricciones (CSOP) con una función de optimización que minimice el coste de combustible, el tiempo de vuelo y el número de UAVs necesarios; y se utiliza Branch & Bound (B&B) para resolver este modelo de CSOP. Finalmente, se realizarán algunos experimentos para validar tanto la calidad de las soluciones encontradas como el tiempo de ejecución gastado en su búsqueda.