[ca] 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&#184;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&#184;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.

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