  Task allocation is a key combinatorial optimization problem, crucial for
modern applications such as multi-robot cooperation and resource scheduling.
Decision makers must allocate entities to tasks reasonably across different
scenarios. However, traditional methods assume static attributes and numbers of
tasks and entities, often relying on dynamic programming and heuristic
algorithms for solutions. In reality, task allocation resembles Markov decision
processes, with dynamically changing task and entity attributes. Thus,
algorithms must dynamically allocate tasks based on their states. To address
this issue, we propose a two-stage task allocation algorithm based on
similarity, utilizing reinforcement learning to learn allocation strategies.
The proposed pre-assign strategy allows entities to preselect appropriate
tasks, effectively avoiding local optima and thereby better finding the optimal
allocation. We also introduce an attention mechanism and a hyperparameter
network structure to adapt to the changing number and attributes of entities
and tasks, enabling our network structure to generalize to new tasks.
Experimental results across multiple environments demonstrate that our
algorithm effectively addresses the challenges of dynamic task allocation in
practical applications. Compared to heuristic algorithms like genetic
algorithms, our reinforcement learning approach better solves dynamic
allocation problems and achieves zero-shot generalization to new tasks with
good performance. The code is available at
https://github.com/yk7333/TaskAllocation.
