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 más complejas. Muchas de estas tareas se podrían ejecutar más eficientemente por un grupo de robots, en vez de por uno sólo. Trabajando conjuntamente, el equipo de robots puede completar tareas de forma más rápida, incrementando la robustez del sistema e incluso llevando a cabo tareas que son imposibles por un único robot. Sin embargo, coordinar un equipo de robot aún requiere superar importantes retos a nivel científico.

Dentro del campo de estudio de los sistemas multirobot, esta tesis se enfoca en el problema de la asignación de tareas. Este problema intenta responder a la pregunta: ¿qué robot debería ejecutar cada una de las tareas? Este problema tiene una gran importancia en misiones de exploración que hacen uso de varios robots. Por ejemplo, en futuras misiones científicas, se quiere mandar distintos robots instrumentados a lugares de interés científico, 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 cómo asignar las posiciones de éstos para que finalmente se obtenga la topología deseada. Este mismo objetivo también se trata cuando se estudia el problema de la asignación de tareas con múltiples robots.

Esta tesis presenta recientes contribuciones en el campo de la cooperación entre múltiples robots. En particular, la investigación llevada a cabo se centra en algoritmos distribuidos de asignación 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 número de robots necesarios para ser ejecutadas. El número final de robots necesario es decidido durante un proceso de negociación y depende de las capacidades de los robots. Con respecto a los algoritmos MRMT (Múltiple Robots Múltiple Tasks), esta tesis presenta un nuevo algoritmo distribuido de asignación de tareas que combina la reasignación y combinación de pujas, que posee tanto una alta eficiencia como tolerancia a fallos. Por otra parte, se han desarrollado mejoras de los algoritmos MRST (Múltiple Robots Single Task) ya existentes. La principal diferencia es que se aumenta la información compartida, de manera que los robots eligen tareas que, no sólo son mejores para ellos, sino para el grupo en general. Finalmente, esta tesis desarrolla un marco de trabajo probabilístico para calcular medidas de eficiencia en algoritmos MRST. El análisis consiste en el cálculo del valor esperado de la función objetivo, que es usado más tarde como métrica para comparar diferentes algoritmos. Como el valor esperado de una variable aleatoria indica su valor en media, 'este supone una medida más 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 solución óptima.

Por otra parte, la tesis está organizada de la siguiente manera. El primer capítulo introduce y motiva el problema a tratar. A continuación, el Capítulo 2 aborda el problema de la asignación de tareas que necesitan un número desconocido de robots para ser ejecutadas. El número de robots depende de sus capacidades y se calcula durante un proceso de negociación. El concepto de servicio, es definido en este punto. Un servicio se genera a partir de una tarea con la que está relacionado, y éste puede generar otro servicio creándose una relación jerárquica entre las tareas y los servicios. En este capítulo también se estudia el impacto sobre la ejecución de las tareas que dicha relación provoca.

En el caso en el que la eficiencia de la asignación sea de interés, ésta se puede aumentar, como se muestra en el Capítulo 3, mediante la combinación de los conceptos de reasignación con el de pujas combinatorias. Las tareas se agrupan y se asignan como si fueran una única, en lugar de asignar cada tarea por separado. La eficiencia de la asignación se ve aumentada puesto que los robots calculan sus costes con un horizonte de ejecución más largo y se benefician de las sinergias entre las tareas. Como contrapartida, se necesita un nivel de confianza más alto en los costes de las tareas.

La última parte del Capítulo 3 estudia problemas de sincronización para algoritmos de asignación de tareas basados en reglas de mercado.

En el Capítulo 4 se describen diferentes algoritmos MRST de asignación de tareas.

Este tipo de algoritmos no usan planes de ejecución locales, y por tanto, son apropiados para aplicaciones donde los costes pueden cambiar con el tiempo. En el mismo capítulo se discuten varias estrategias para la obtención de soluciones más eficientes que las usuales. Por otra parte, el Capítulo 5 desarrolla un marco de trabajo probabilístico que permite comparar diferentes algoritmos MRST de asignación de tareas. Dentro de este análisis probabilístico, el objetivo es calcular el valor esperado del la función objetivo, que proporciona una medida de la eficiencia del algoritmo. Los resultados teóricos obtenidos son validados mediante simulaciones y experimentos con robots reales. También en este capítulo, se desarrolla un estudio de la eficiencia de un algoritmo en comparación con el valor 'optimo. Este capítulo finaliza con una extensión de la metodología propuesta, mediante el cálculo de la distribución probabilística estimada de la función objetivo. Finalmente, las conclusiones y el futuro trabajo a desarrollar de esta tesis se exponen en el Capítulo 6.