Sistema de reparto de tareas distribuido para misiones multi-robot basado en teoría de juegos

Abstract

El presente proyecto explora la aplicación de Teoría de Juegos a la resolución del problema de asignación de tareas en misiones multi-robot (MRTA de sus siglas en inglés Mult-Robot Task Allocation). Este problema tiene como objetivo la maximización de la utilidad U asociada a la asignación de T tareas a R robots. Para el problema planteado a lo largo de este trabajo, se han disen˜ado dos algoritmos de asignación, considerados por la autora completamente originales al ser de disen˜o propio y al no encontrar ningún algoritmo semejante en la literatura tras una extensiva búsqueda. Aunque ambos se basan en la Teoría de Juegos, cada uno se formula según distintos postulados de la disciplina: el competitivo se deriva del disen˜o de juegos según su forma normal y la búsqueda del equilibrio de Nash y el colaborativo se basa en sistemas de votación colectivos entre los jugadores. En el problema que se busca resolver a través de estos algoritmos una flota de R robots debe realizar un conjunto del mismo número de tareas T conocidas por los distintos miembros de la misión. La flota es homogénea y se compone de un alto número de robots relativamente simples en cuanto a sus capacidades y funcionamiento, siendo incapaces de realizar más de una tarea simultáneamente. Las tareas a completar también son homogéneas y necesitan de un sólo robot para su realización. El éxito de una misión será función de la cantidad de tareas realizadas y el desplazamiento de cada miembro de la flota. El planteamiento descrito refleja distintas situaciones reales, de gran interés por su aplicación humanitaria y comercial. La misión planteada, por ejemplo, podría modelar una de de búsqueda y rescate, en el que un alto número de robots deben inspeccionar un área, visitando ciertos puntos de interés, que conforman las tareas que los robots deben realizar, con el fin de encontrar a las posibles víctimas de un catástrofe. Otra posible misión sería la de un estudio orográfico para el desarrollo de una aplicación comercial, en la que fuera necesario obtener una imagen meticulosa de la zona en cuestión a través de varias fotografías a lo largo de una superficie extensa.