提出图结构表示法，解决无限状态任务分配的神经网络输入难题。
A Universal Approach to Feature Representation in Dynamic Task Assignment Problems
- 用图结构抽象任务与资源关系，统一处理有限与无限状态空间。
- 实验表明该方法在各类任务分配问题中均能学习接近最优策略。
- 适合研究动态资源调度、复杂流程优化的工程师和研究人员。
动态任务分配关注在业务流程中将资源最优分配给任务。近年来，深度强化学习（DRL）已成为解决分配问题的前沿方法。通常，DRL使用神经网络（NN）作为策略函数的近似器，接收流程状态并输出各分配方案的评估值。然而，如何表示状态与可能的分配方案，使其能作为策略神经网络的输入和输出，仍是开放挑战，尤其当任务或资源具有无限取值特征时。本文提出一种针对无限状态与动作空间的分配问题表示与求解方法，包含三项贡献：(I) 提出基于图的分配问题特征表示方法，称为分配图；(II) 建立标记彩色佩特里网到分配图的映射；(III) 改造近端策略优化算法（PPO），使其能通过分配图学习任务分配策略。为评估该表示方法，我们构建了三类典型分配问题，涵盖从有限到无限状态与动作空间的情形。实验结果表明，该方法在不同维度的分配问题中均能有效表示并学习接近最优的分配策略。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。