[en] 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.

[es] 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.