Sistema de subhastes cooperatives per a l'assignació dinàmica de tasques a robots mòbils

Abstract

Grups de robots més o menys nombrosos s'encarreguen del transport intern dins dels magatzems automatitzats. Un dels grans reptes en la gestió d'aquests tipus de magatzem és l'assignació de tasques als robots a l'hora que es minimitza el cost global de les operacions. En entorns amb pocs punts de càrrega és possible fer una assignació òptima mitjan¸cant tècniques de programació lineal. Però, a mesura que el nombre de tasques i robots augmenta, i que les tasques entren al sistema al llarg del temps de forma dinàmica, ja no és possible fer l'assignació òptima mitjan¸cant la programació lineal en un temps raonable. Les solucions basades en subhastes solucionen el problema de l'assignació de tasques aproximant-se a la solució òptima i aportant robustesa i escalabilitat al sistema. El protocol d'assignació de tasques a robots que es fa servir és el denominat "contract-net", en què els agents que representen les tasques son les que inicien subhastes tancades en les què els robots fan les seves ofertes basades en el seu cost d'operació. A causa del dinamisme del sistema, l'aparició de noves tasques, possibles accidents i altres esdeveniments inesperats fan que les tasques llancin noves subhastes quan es produeix un d'aquests esdeveniments. Això fa que aquestes noves subhastes provoquin el canvi de robot assignat a la tasca. Tot i que aquest mecanisme de "resubhasta"ens acosta encara més a la solució òptima (fins un 15% pitjor que la solució de la programació lineal) les tasques no tenen en compte el fet que que els robots poden estar participant a la vegada en altres subhastes. Tenim doncs que les tasques tenen un comportament "egoista"(greedy) perquè s'assignen el robot que aporta el valor mínim a la seva subhasta sense considerar les altres. Per tant, les primeres subhastes que avaluen les ofertes s'associen els robots. En aquesta tesi es modifica el protocol de les subhastes de manera que els agents que representen les tasques prenen les decisions basant-se no només en les ofertes que els robots fan per a la seva subhasta sinó també en les ofertes que fan a les altres. A més d'aquest canvi en el protocol, en aquesta tesi també es proposa un algorisme d'assignació de tasques que es denomina Munkres*, que està basat en el mètode hongarès i que aprofita assignacions prèvies òptimes amb l'objectiu de minimitzar les comunicacions i d'evitar bucles en reassignacions. Amb aquesta solució, el cost d'execució de les tasques i el cost de transport es redueix, cosa que porta a millores dels costos globals d'operació que s'acosten fins a un 90% de l'òptim.

Dentro de los almacenes automatizados grupos de robots más o menos numerosos se encargan del transporte interno. Uno de los grandes retos en la gestión de este tipo de almacenes es la asignación de tareas a los robots a la vez que se minimiza el coste global de las operaciones. En entornos con pocos puntos de carga es posible realizar una asignación óptima mediante técnicas de programación lineal. Sin embargo, a medida que el número de tareas y robots aumenta, y que las tareas entran en el sistema a lo largo del tiempo de forma dinámica, ya no es posible realizar la asignación óptima mediante la programación lineal en un tiempo razonable. Las soluciones basadas en subastas solucionan el problema de la asignación de tareas aproximándose a la solución óptima y aportando robustez y escalabilidad al sistema. El protocolo de asignación de tareas a robots que se utiliza es el denominado "contract-net", donde los agentes que representan las tareas son los que inician subastas cerradas en las que los robots realizan sus ofertas basadas en su coste de operación. Debido al dinamismo del sistema, la aparición de nuevas tareas, posibles accidentes y otros acontecimientos inesperados hacen que las tareas lancen nuevas subastas cuando se produce uno de estos eventos. Esto provoca que estas nuevas subastas puedan provocar el cambio de robot asignado a la tarea. Aunque este mecanismo de "resubasta" nos acerca aún más a la solución óptima (hasta un 15% peor que la solución de la programación lineal) las tareas no tienen en cuenta el hecho de que los robots pueden estar participando a la vez en otras subastas. Tenemos pues que las tareas tienen un comportamiento "codicioso"("greedy") porque se asignan el robot que aporta el valor mínimo a su subasta sin considerar las demás subastas. Por tanto, las primeras subastas que evalúan las ofertas se asocian a los robots. En esta tesis se modifica el protocolo de las subastas por lo que los agentes que representan las tareas toman las decisiones basándose no sólo en las ofertas que los robots hacen para su subasta sino también en las ofertas que hacen a las demás. Además de este cambio en el protocolo, en esta tesis también se propone un algoritmo de asignación de tareas que se denomina Munkres*, basado en el método húngaro y que aprovecha asignaciones previas óptimas con el objetivo de minimizar las comunicaciones y de evitar bucles en reasignaciones. Con esta solución, el coste de ejecución de las tareas y el coste de transporte se reduce, lo que lleva a mejoras de los costes globales de operación que se avecinan hasta un 90% del óptimo.

Automated warehouses are populated with robots that take charge of the internal transportation. One of the main challenges of the management systems is to allocate tasks to robots while minimizing overall operation costs. For environments with a few loading spots, it is possible to make optimum assignments with linear programming techniques. As the number of tasks and robots increases, and as tasks arrive over time dynamically, it is no longer possible to make the optimal allocation using linear programming in a reasonable amount of time. Dynamic approaches based upon auctions solve the allocation problem with near-optimal solutions and give the systems robustness and scalability. We use the so-called "contract-net"protocol for assigning tasks to robots, in which the agents representing the tasks are the ones that initiate closed auctions, and the robots make their bids based on their cost of operation. Due to the dynamism of the system, the appearance of new tasks, potential crashes, and other unexpected events cause tasks to launch new auctions when one of these events occurs. This may cause the robot assigned to the task to change. Although this "re-auction" mechanism brings us even closer to the optimal solution (up to 15% worse than the linear programming solution) the tasks do not take into account the fact that robots may be participating at the same time in other auctions. We therefore have that the tasks have a "greedy"behavior because they are assigned the robot that contributes the minimum value to its auction without considering other auctions. Therefore, the first auctions that evaluate bids are assigned to robots. In this thesis the auction protocol is modified so that the agents representing the tasks make decisions based not only on the bids the robots make for their auction but also on the bids they make to the others. In addition to this change in the protocol, this thesis also proposes a task assignment algorithm called Munkres*, which is based on the Hungarian method and which takes advantage of optimal prior assignments with the aim of minimizing communications and to avoid loops in reassignments. With this solution, the task execution cost and transportation cost are reduced, leading to overall operating cost improvements approaching 90% of optimal.