Multi-robot task allocation for service robotics: from unlimited to limited communication range

摘要

Multiples robots autonomos trabajando en un mismo entorno requieren nuevas capacidades de decision para ser de maxima utilidad: cual es la mejor forma de abordar un problema (planificacion) y quien se encarga de cada parte del trabajo (asignacion de tareas). Esta ultima actividad, en la que se centra esta tesis, ha sido abordada con una gran diversidad de metodos: desde la coordinacion implicita en ausencia de comunicacion (cooperacion como resultado emergente de mecanismos predefinidos), pasando por metodos de inspiracion biologica (enjambres), hasta tecnicas similares a la cooperacion humana donde hay comunicacion explicita (contratos, subastas) o metodos fundamentalmente matematicos (modelos Markovianos). En soluciones donde existe comunicacion es habitual el uso de redes inalambricas por su conveniencia. Sin embargo, estas tienen un alcance limitado por razones bien economicas (no siempre es factible instalar puntos de acceso en todo el entorno de trabajo) o fisicas (la intervencion se realiza en un area no preparada, como un escenario de desastre natural), entre otras. Por lo tanto, el uso de comunicaciones en areas extensas requiere un tratamiento explicito de la conectividad en estas circunstancias. Dentro de este amplio abanico de posibilidades hay aspectos que han sido ya objeto de abundante investigacion. Sin embargo, su tratamiento es generalmente aislado y requiere por tanto una labor de investigacion adicional de cara a su integracion en soluciones completas. Adicionalmente, es el aspecto de limitaciones en la comunicacion el mas novedoso y el que esta recibiendo actualmente una atencion creciente dentro del contexto de la robotica de servicio. Por ello, la presente tesis aborda estos aspectos: * Metodos que no esten estrechamente ligados a un problema en particular, sino que sean aplicables con generalidad a tareas independientes o con pocas interdependencias, de cara a su uso en una variedad de tareas de servicio. En particular, se estudian distintas variaciones de metodos basados en subastas y se proponen mejoras para su uso en combinacion con sistemas de tareas jerarquicas y en ambitos de comunicaciones limitadas. * Metas de optimizacion y metricas de evaluacion precisas y contrastables dentro de la robotica de servicio, apropiadas para estos metodos de asignacion de tareas. Partiendo de un modelo clasico del problema, basado en el problema del viajante, se identifican varias metricas adecuadas, sus efectos en la optimizacion, y se proponen metodos de implementacion que permiten una rapida adaptabilidad de los algoritmos a las distintas metricas. * Soluciones para la integracion de todo lo anterior con las limitaciones de conectividad, ya sea tratandolas como una restriccion adicional para la optimizacion, o como un elemento fundamental y determinante de la metodologia de asignacion. * Demostraciones experimentales de los resultados obtenidos en simulacion. Estos experimentos respaldan dos puntos interrelacionados y de relevancia creciente en sistemas complejos como es un equipo multirrobot: por una parte, la validacion experimental es un paso necesario en una investigacion completa; por otra, al hacer publico el codigo fuente (la arquitectura \sancta) de nuestro equipo robotico (llamado \conan), se simplifica la tarea de verificacion y reproduccion de resultados por parte de otros investigadores, amen de posibilitar la reutilizacion del codigo con el consiguiente ahorro de esfuerzo para la comunidad robotica. * Implementacion e integracion, como responsables del paquete de trabajo dedicado a asignacion de tareas, de los algoritmos pertinentes dentro del contexto del proyecto europeo \acsu{URUS}. Este proyecto esta enfocado a la integracion de robots y sensores en ambientes urbanos para facilitar tareas tales como transporte de objetos y personas, seguimiento de usuarios, deteccion de situaciones anomalas y consiguiente intervencion robotica, por ejemplo. Conjuntamente, estos puntos contribuiran a la construcc