A Universal Approach to Feature Representation in Dynamic Task Assignment Problems

📄 arXiv: 2507.03579v1 📥 PDF

作者: Riccardo Lo Bianco, Remco Dijkman, Wim Nuijten, Willem van Jaarsveld

分类: cs.AI

发布日期: 2025-07-04

💡 一句话要点

提出基于图的动态任务分配通用特征表示方法，提升DRL策略学习效果

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 动态任务分配 深度强化学习 特征表示 分配图 近端策略优化

📋 核心要点

  1. 现有DRL方法在动态任务分配中面临状态和动作空间无限时的特征表示难题。
  2. 论文提出基于图的特征表示方法，将任务分配问题转化为分配图，实现通用表示。
  3. 实验证明该方法能有效学习接近最优的任务分配策略，不受状态和动作空间维度限制。

📝 摘要（中文）

动态任务分配旨在业务流程中将资源最优地分配给任务。近年来，深度强化学习(DRL)已被认为是解决分配问题的最先进方法。DRL方法通常采用神经网络(NN)作为策略函数的近似器，该网络接收流程的状态并输出可能分配的估值。然而，如何表示状态和可能的分配，使其能够作为策略NN的输入和输出，仍然是一个公开的挑战，特别是当任务或资源具有无限数量的可能值的特征时。为了解决这个问题，本文提出了一种表示和解决具有无限状态和动作空间的分配问题的方法。为此，它提供了三个贡献：(I)一种基于图的分配问题特征表示，我们称之为分配图；(II)从标记的彩色Petri网到分配图的映射；(III)近端策略优化算法的改进，该算法可以学习解决通过分配图表示的分配问题。为了评估所提出的表示方法，我们对三种典型的分配问题进行了建模，这些问题的状态和动作空间维度从有限到无限。实验表明，该方法适用于表示和学习接近最优的任务分配策略，而与状态和动作空间的维度无关。

🔬 方法详解

问题定义：论文旨在解决动态任务分配问题中，当任务或资源具有无限数量的特征值时，如何有效地表示状态和动作空间，以便深度强化学习（DRL）策略网络能够学习最优分配策略。现有方法难以处理无限状态和动作空间，导致DRL在复杂任务分配场景中性能受限。

核心思路：论文的核心思路是将任务分配问题转化为图结构，即“分配图”。通过图结构，可以灵活地表示任务和资源的各种特征，包括连续值和离散值，从而统一处理有限和无限状态/动作空间的问题。这种表示方法旨在提供一种通用的、可扩展的特征表示，适用于各种类型的任务分配问题。

技术框架：整体框架包括三个主要步骤：1) 将任务分配问题建模为标记的彩色Petri网；2) 将Petri网映射到分配图；3) 使用改进的近端策略优化（PPO）算法在分配图上学习任务分配策略。分配图作为DRL算法的输入，PPO算法负责学习最优的资源分配策略。

关键创新：最重要的技术创新在于提出了“分配图”这一概念，它是一种通用的、基于图的特征表示方法，能够统一表示具有有限或无限状态/动作空间的任务分配问题。与传统的向量化或矩阵化表示方法相比，分配图能够更好地捕捉任务和资源之间的复杂关系，并支持各种类型的特征。

关键设计：论文对PPO算法进行了适配，使其能够处理分配图表示的任务分配问题。具体的适配细节可能包括：如何将分配图作为神经网络的输入，如何设计神经网络的结构以处理图结构数据，以及如何定义奖励函数以鼓励DRL算法学习最优的分配策略。此外，Petri网到分配图的映射规则也是一个关键设计，它决定了如何将任务分配问题的语义信息编码到图结构中。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的基于分配图的特征表示方法能够有效地学习接近最优的任务分配策略，无论状态和动作空间的维度是有限还是无限。论文在三种典型的任务分配问题上进行了实验，验证了该方法的通用性和有效性。具体的性能数据和对比基线（如果论文中提供了）可以进一步说明该方法的优势。

🎯 应用场景

该研究成果可应用于各种动态任务分配场景，例如：云计算资源调度、物流配送优化、生产调度、医疗资源分配等。通过学习接近最优的任务分配策略，可以提高资源利用率、降低成本、提升服务质量，并为企业带来显著的经济效益。未来，该方法有望扩展到更复杂的任务分配问题，例如多目标优化、不确定性环境下的任务分配等。

📄 摘要（原文）

Dynamic task assignment concerns the optimal assignment of resources to tasks in a business process. Recently, Deep Reinforcement Learning (DRL) has been proposed as the state of the art for solving assignment problems. DRL methods usually employ a neural network (NN) as an approximator for the policy function, which ingests the state of the process and outputs a valuation of the possible assignments. However, representing the state and the possible assignments so that they can serve as inputs and outputs for a policy NN remains an open challenge, especially when tasks or resources have features with an infinite number of possible values. To solve this problem, this paper proposes a method for representing and solving assignment problems with infinite state and action spaces. In doing so, it provides three contributions: (I) A graph-based feature representation of assignment problems, which we call assignment graph; (II) A mapping from marked Colored Petri Nets to assignment graphs; (III) An adaptation of the Proximal Policy Optimization algorithm that can learn to solve assignment problems represented through assignment graphs. To evaluate the proposed representation method, we model three archetypal assignment problems ranging from finite to infinite state and action space dimensionalities. The experiments show that the method is suitable for representing and learning close-to-optimal task assignment policies regardless of the state and action space dimensionalities.