Abstract
Task allocation is a key combinatorial optimization problem, crucial formodern applications such as multi-robot cooperation and resource scheduling.Decision makers must allocate entities to tasks reasonably across differentscenarios. However, traditional methods assume static attributes and numbers oftasks and entities, often relying on dynamic programming and heuristicalgorithms for solutions. In reality, task allocation resembles Markov decisionprocesses, with dynamically changing task and entity attributes. Thus,algorithms must dynamically allocate tasks based on their states. To addressthis issue, we propose a two-stage task allocation algorithm based onsimilarity, utilizing reinforcement learning to learn allocation strategies.The proposed pre-assign strategy allows entities to preselect appropriatetasks, effectively avoiding local optima and thereby better finding the optimalallocation. We also introduce an attention mechanism and a hyperparameternetwork structure to adapt to the changing number and attributes of entitiesand tasks, enabling our network structure to generalize to new tasks.Experimental results across multiple environments demonstrate that ouralgorithm effectively addresses the challenges of dynamic task allocation inpractical applications. Compared to heuristic algorithms like geneticalgorithms, our reinforcement learning approach better solves dynamicallocation problems and achieves zero-shot generalization to new tasks withgood performance. The code is available athttps://github.com/yk7333/TaskAllocation.