Market-based distributed task allocation methodologies applied to multi-robot exploration

Abstract

A medida que los robots se van integrando en la vida diaria de las personas, se les pide que realicen tareas cada vez mas complejas. Muchas de estas tareas se podrian ejecutar mas eficientemente por un grupo de robots, en vez de por uno solo. Trabajando conjuntamente, el equipo de robots puede completar tareas de forma mas rapida, incrementando la robustez del sistema e incluso llevando a cabo tareas que son imposibles por un unico robot. Sin embargo, coordinar un equipo de robot aun requiere superar importantes retos a nivel cientifico. Dentro del campo de estudio de los sistemas multirobot, esta tesis se enfoca en el problema de la asignacion de tareas. Este problema intenta responder a la pregunta: ?que robot deberia ejecutar cada una de las tareas? Este problema tiene una gran importancia en misiones de exploracion que hacen uso de varios robots. Por ejemplo, en futuras misiones cientificas, se quiere mandar distintos robots instrumentados a lugares de interes cientifico, que nos permita ampliar nuestro conocimiento sobre el origen de la vida. A la hora de establecer las configuraciones de estos robots, hay que determinar como asignar las posiciones de estos para que finalmente se obtenga la topologia deseada. Este mismo objetivo tambien se trata cuando se estudia el problema de la asignacion de tareas con multiples robots. Esta tesis presenta recientes contribuciones en el campo de la cooperacion entre multiples robots. En particular, la investigacion llevada a cabo se centra en algoritmos distribuidos de asignacion de tareas basados en reglas de mercado. Con mayor detalle, las aportaciones de la tesis se pueden resumir en cuatro puntos fundamentales. En primer lugar, se ha desarrollado un nuevo concepto denominado servicios, que permite asignar tareas de las que se desconoce el numero de robots necesarios para ser ejecutadas. El numero final de robots necesario es decidido durante un proceso de negociacion y depende de las capacidades de los robots. Con respecto a los algoritmos MRMT (Multiple Robots Multiple Tasks), esta tesis presenta un nuevo algoritmo distribuido de asignacion de tareas que combina la reasignacion y combinacion de pujas, que posee tanto una alta eficiencia como tolerancia a fallos. Por otra parte, se han desarrollado mejoras de los algoritmos MRST (Multiple Robots Single Task) ya existentes. La principal diferencia es que se aumenta la informacion compartida, de manera que los robots eligen tareas que, no solo son mejores para ellos, sino para el grupo en general. Finalmente, esta tesis desarrolla un marco de trabajo probabilistico para calcular medidas de eficiencia en algoritmos MRST. El analisis consiste en el calculo del valor esperado de la funcion objetivo, que es usado mas tarde como metrica para comparar diferentes algoritmos. Como el valor esperado de una variable aleatoria indica su valor en media, este supone una medida mas informativa que las utilizadas usualmente en la literatura para medir la eficiencia del algoritmo, como por ejemplo el peor caso posible con respecto a la solucion optima. Por otra parte, la tesis esta organizada de la siguiente manera. El primer capitulo introduce y motiva el problema a tratar. A continuacion, el Capitulo 2 aborda el problema de la asignacion de tareas que necesitan un numero desconocido de robots para ser ejecutadas. El numero de robots depende de sus capacidades y se calcula durante un proceso de negociacion. El concepto de servicio, es definido en este punto. Un servicio se genera a partir de una tarea con la que esta relacionado, y este puede generar otro servicio creandose una relacion jerarquica entre las tareas y los servicios. En este capitulo tambien se estudia el impacto sobre la ejecucion de las tareas que dicha relacion provoca. En el caso en el que la eficiencia de la asignacion sea de interes, esta se puede aumentar, como se muestra en el Capitulo 3, mediante la combinacion de los conceptos de reasignacion con el de pujas combinatorias. L