Execution-driven dynamic Multi-Robot Task Allocation model easily applicable to real cases

Abstract

Molts magatzems i fàbriques modernes utilitzen robots mòbils autònoms per a les seves operacions logístiques internes. A causa del volum de treball que tenen aquestes instal·lacions, no és pràctic assignar manualment les tasques de transport als robots de la flota. Els canvis freqüents en les ordres planificades i els esdeveniments inesperats durant la seva execució com, per exemple, el mal funcionament del robot o els embussos de trànsit, augmenten la complexitat del problema d’assignació de tasques. Tenint tot això en compte, les cerques exhaustives de solucions s’han de limitar en temps de càlcul i els seus resultats esdevenen subòptims. Les solucions pràctiques utilitzen mecanismes d’assignació menys intensius en càlcul que potser no proporcionen resultats òptims però que s’adapten molt bé als entorns dinàmics com els que s’han descrit. Un d’aquests mecanismes consisteix en subhastar les tasques entre els robots de manera que els que facin la millor oferta acabin fent el transport assignat. En aquest treball es proposa un model d’un sistema multi-agent per fer les assignacions mitjançant subhastes que millora la qualitat de les solucions d’un sistema amb subhastes simples tot incorporant-hi mecanismes de repetició. A diferència d’altres aplicacions d’assignació de tasques, que fan servir estimacions per determinar la disponibilitat dels robots, la que s’ha desenvolupat fa servir un simulador físic, cosa que permet tenir en compte l’efecte del trànsit o d’altres fenòmens. Per fer-ho possible, a més dels models de la part deliberativa dels agents del sistema, també s’han creat els models de la part reactiva dels robots. Aquests models es descriuen formalment amb un tipus propi de màquina d’estat que, a més de garantir la predictibilitat i de facilitar la verificació i la implementació del sistema, permet arribar a expressar el comportament deliberatiu dels agents. El sistema que es proposa inclou un mecanisme de sincronització amb la part física de manera que fa les assignacions i controla els robots tot fent evolucionar el conjunt de màquines fins que requereix que passi temps, com, per exemple, per deixar que els robots es moguin. Els experiments que s’han fet mostren reduccions en el temps i la distància recorreguda pels robots quan s’ajusten els paràmetres de la subhasta i s’hi fan servir repeticions. Els resultats obtinguts suggereixen que les assignacions són properes a les òptimes. Atès que el sistema d’assignació de tasques que s’ha desenvolupat controla els robots simulats durant l’execució de les tasques, la integració amb una planta amb robots reals seria directa.

Muchos almacenes y fábricas modernas utilizan robots móviles autónomos para sus operaciones logísticas internas. Debido al volumen de trabajo que tienen estas instalaciones, no es práctico asignar manualmente las tareas de transporte a los robots de la flota. Los cambios frecuentes en las órdenes planificadas y los eventos inesperados durante su ejecución como, por ejemplo, el mal funcionamiento del robot o los atascos de tráfico, aumentan la complejidad del problema de asignación de tareas. Teniendo todo esto en cuenta, las búsquedas exhaustivas de soluciones deben limitarse en tiempo de cálculo y sus resultados acaban siendo subóptimos. Las soluciones prácticas utilizan mecanismos de asignación menos intensivos en cálculo que quizás no proporcionan resultados óptimos pero que se adaptan muy bien a los entornos dinámicos como los que se han descrito. Uno de estos mecanismos consiste en subastar las tareas entre los robots de forma que los que hagan la mejor oferta acaben realizando el transporte asignado. En este trabajo se propone un modelo de un sistema multi-agente para realizar las asignaciones mediante subastas que mejora la calidad de las soluciones de un sistema con subastas simples incorporando mecanismos de repetición. A diferencia de otras aplicaciones de asignación de tareas, que utilizan estimaciones para determinar la disponibilidad de los robots, la que se ha desarrollado utiliza un simulador físico, lo que permite tener en cuenta el efecto del tráfico o de otros fenómenos. Para ello, además de los modelos de la parte deliberativa de los agentes del sistema, también se han creado los modelos de la parte reactiva de los robots. Estos modelos se describen formalmente con un tipo propio de máquina de estado que, además de garantizar la predictibilidad y facilitar la verificación e implementación del sistema, permite llegar a expresar el comportamiento deliberativo de los agentes. El sistema que se propone incluye un mecanismo de sincronización con la parte física por lo que hace las asignaciones y controla los robots haciendo evolucionar el conjunto de máquinas hasta que requiere que pase tiempo, como, por ejemplo, para dejar que los robots se muevan. Los experimentos que se han realizado muestran reducciones en el tiempo y la distancia recorrida por los robots cuando se ajustan los parámetros de la subasta y se utilizan repeticiones. Los resultados obtenidos sugieren que las asignaciones son próximas a las óptimas. Dado que el sistema de asignación de tareas que se ha desarrollado controla a los robots simulados durante la ejecución de las tareas, la integración con una planta con robots reales sería directa.

Many modern warehouses and factories use autonomous mobile robots for their internal logistics operations. Due to the workload of these facilities, it is impractical to manually assign transport tasks to fleet robots. Frequent changes in planned orders and unexpected events during their execution, such as robot malfunctions or traffic jams, increase the complexity of the task assignment problem. Taking all this into account, exhaustive searches for solutions must be limited in computing time and their results become suboptimal. Practical solutions use less computationally intensive allocation mechanisms that may not provide optimal results but are well suited to dynamic environments such as those described. One of these mechanisms consists in auctioning the tasks between the robots so that those who make the best offer end up doing the assigned transport. This work proposes a model of a multi-agent system to make allocations through auctions that improves the quality of the solutions of a system with simple auctions while incorporating repetition mechanisms. Unlike other task assignment applications, which use estimates to determine robot availability, the one we developed uses a physical simulator, allowing the effect of traffic or other factors to be considered. To make this possible, in addition to the models of the deliberative part of the agents of the system, the models of the reactive part of the robots have also been created. These models are formally described with a specific type of state machine that, in addition to guaranteeing predictability and facilitating the verification and implementation of the system, makes it possible to express the deliberative behavior of the agents. The proposed system includes a synchronization mechanism with the physical part so that it makes the assignments and controls the robots while evolving the set of machines until it requires time to pass, such as to let the robots move. The experiments that have been done show reductions in the time and distance traveled by the robots when the auction parameters are adjusted, and repetitions are used. The results obtained suggest that the allocations are close to the optimal ones. Since the task assignment system that has been developed controls the simulated robots during the execution of tasks, the integration with a plant with real robots would be straightforward.