Polynomial analysis algorithms for free choice Probabilistic Workflow Nets
Polynomial analysis algorithms for free choice Probabilistic Workflow Nets
复制标题
DOI：
10.1016/j.peva.2017.09.006
复制
发表时间：
2017-12-01
影响因子：
2.2
通讯作者：
Saha, Ratul
中科院分区：
文献类型：
--
作者：
Esparza, Javier;Hoffmann, Philipp;Saha, Ratul
我们介绍了概率工作流网（PWNS），这是一种模型，该模型以概率扩展了无混淆的工作流petri网。我们就马尔可夫决策过程（MDP）给予PWNs语义，并引入奖励模型。我们表明，PWN的完整执行的预期奖励独立于用于解决MDP的非确定性的调度程序，该调度程序允许人们选择合适的调度程序进行计算。但是，此功能不会导致多项式算法，实际上，我们证明，确定预期奖励是否超过给定阈值是PSPACE-HARD。为了减轻这种高计算成本，我们扩展了先前有关保留非 - 降低非 - 的工作的工作。概率工作流网。我们介绍了PWN的简化规则，并证明它们保留了预期的奖励。规则允许我们在构建其MDP之前简化工作流程。然后，我们考虑自由选择PWN的子类，其非稳态对应物已被广泛研究。使用以前的结果，我们在Fase'16中发表了该类别的规则，我们得出了PWN大小的多项式时间算法，以计算预期奖励。相反，基于构造MDP的算法需要指数时间。我们报告了还原算法的示例实现及其在基准集合中的性能。在本文中，我们介绍了我们工作的两个扩展。首先，我们表明我们的还原规则也可以用来以参数来计算预期奖励，即作为与过渡的概率和奖励有关的参数的函数。其次，我们讨论了PWN的扩展到不是无混淆的工作流网，并表明我们的某些结果仍然存在。 （c）2017 Elsevier B.V.保留所有权利。
We introduce Probabilistic Workflow Nets (PWNs), a model extending confusion-free workflow Petri nets with probabilities. We give PWNs a semantics in terms of Markov Decision Processes (MDPs) and introduce a reward model. We show that the expected reward of a complete execution of a PWN is independent of the scheduler used to resolve the nondeterminism of the MDP, which allows one to choose a suitable scheduler for its computation. However, this feature does not lead to a polynomial algorithm, and in fact we prove that deciding whether the expected reward exceeds a given threshold is PSPACE-hard.To alleviate this high computational cost, we extend previous work on property preserving reductions of non-probabilistic workflow nets. We introduce reduction rules for PWNs, and prove that they preserve the expected reward. The rules allow us to simplify the workflow before constructing its MDP. We then consider the subclass of free-choice PWNs, whose non-probabilistic counterpart has been extensively studied. Using a previous result on the power of the rules for this class, published by us in FASE'16, we derive a polynomial-time algorithm in the size of the PWN for the computation of the expected reward. In contrast, algorithms based on constructing the MDP require exponential time. We report on a sample implementation of the reduction algorithm and on its performance on a collection of benchmarks.Finally, we present two extensions of our work. First, we show that our reduction rules can also be used to compute the expected reward parametrically, that is, as a function of parameters related to the probabilities and rewards of the transitions. Second, we discuss the extension of PWNs to workflow nets that are not confusion-free, and show that some of our results still hold. (c) 2017 Elsevier B.V. All rights reserved.