A Two-stage Reinforcement Learning-based Approach for Multi-entity Task Allocation

任务分配是一个关键的组合优化问题，对于现代应用如多机器人协作和资源调度至关重要。决策者必须在不同的场景中合理地分配实体到任务中。然而，传统方法假设任务和实体的属性和数量是静态的，通常依靠动态规划和启发式算法来求解。实际上，任务分配类似于马尔可夫决策过程，具有动态变化的任务和实体属性。因此，算法必须根据它们的状态动态地分配任务。为了解决这个问题，我们提出了一种基于相似性的两阶段任务分配算法，利用强化学习来学习分配策略。所提出的预分配策略允许实体预先选择适当的任务，有效地避免局部最优，并因此更好地找到最优分配。我们还引入了注意机制和超参数网络结构，以适应实体和任务数量和属性的变化，使我们的网络结构能够推广到新的任务。多个环境中的实验结果表明，我们的算法有效地解决了实际应用中动态任务分配的挑战。与遗传算法等启发式算法相比，我们的强化学习方法更好地解决了动态分配问题，并在新任务的零-shot泛化方面表现良好。代码可在 https://github.com/yk7333/TaskAllocation 获得。

动态任务分配是一个关键的组合优化问题，在多机器人协作和资源调度等现代应用中至关重要。然而，传统方法假设任务和实体的属性和数量是静态的，通常依靠动态规划和启发式算法来解决问题。实际上，任务分配类似于马尔可夫决策过程，具有动态变化的任务和实体属性。因此，算法必须根据它们的状态动态分配任务。本文提出了一种基于相似性的两阶段任务分配算法，利用强化学习学习分配策略。所提出的预分配策略允许实体预先选择适当的任务，有效地避免局部最优解，从而更好地找到最优分配。我们还引入了注意机制和超参数网络结构，以适应实体和任务数量和属性的变化，使我们的网络结构能够推广到新任务。多个环境的实验结果表明，我们的算法有效地解决了实际应用中动态任务分配的挑战。与遗传算法等启发式算法相比，我们的强化学习方法更好地解决了动态分配问题，并在新任务的零-shot通用化方面表现良好。

本文提出了一种基于相似性的两阶段任务分配算法，利用强化学习学习分配策略，解决了动态任务分配的挑战。所提出的预分配策略允许实体预先选择适当的任务，有效地避免局部最优解，从而更好地找到最优分配。我们还引入了注意机制和超参数网络结构，以适应实体和任务数量和属性的变化，使我们的网络结构能够推广到新任务。

本文的亮点包括：1. 提出了一种基于相似性的两阶段任务分配算法，利用强化学习学习分配策略；2. 引入了预分配策略，允许实体预先选择适当的任务，有效地避免局部最优解；3. 引入了注意机制和超参数网络结构，使我们的网络结构能够推广到新任务；4. 实验结果表明，我们的算法有效地解决了实际应用中动态任务分配的挑战，并在新任务的零-shot通用化方面表现良好。代码已经开源。

在这个领域中，最近的相关研究包括：1. “Multi-Robot Task Allocation in Dynamic Environments Using Deep Reinforcement Learning”；2. “Distributed Task Allocation in Multi-Robot Systems Using Deep Reinforcement Learning”；3. “Dynamic Task Allocation for Multi-Robot Systems Based on Reinforcement Learning with a Priori Knowledge”等。