Wittbold, Florian; Bernemann, Rebecca; Heckel, Reiko; Heindel, Tobias; König, Barbara:
Stochastic Decision Petri Nets
In: Application and Theory of Petri Nets and Concurrency : Proceedings / Gomes, Luis; Lorenz, Robert (Eds.). - 44th International Conference, PETRI NETS 2023; Lisbon, Portugal; 25–30 June 2023 - Cham: Springer Science and Business Media, 2023 - (Lecture Notes in Computer Science (LNCS) ; 13929), pp. 264 - 285
2023book article/chapter in ProceedingsOA Green
Computer ScienceFaculty of Engineering » Computer Science and Applied Cognitive Science » Computer Science » Theoretical Computer Science
Title in English:
Stochastic Decision Petri Nets
Author:
Wittbold, FlorianUDE
LSF ID
62659
ORCID
0000-0001-8307-503XORCID iD
Other
connected with university
corresponding author
;
Bernemann, RebeccaUDE
LSF ID
60566
ORCID
0000-0002-3240-0952ORCID iD
Other
connected with university
;
Heckel, Reiko
ORCID
0000-0003-4719-0772ORCID iD
;
Heindel, Tobias
ORCID
0000-0003-3371-8564ORCID iD
;
König, BarbaraUDE
GND
1050396502
LSF ID
15982
ORCID
0000-0002-4193-2889ORCID iD
Other
connected with university
Open Access?:
OA Green
arXiv.org ID
Scopus ID
Language of text:
English

Abstract in English:

We introduce stochastic decision Petri nets (SDPNs), which are a form of stochastic Petri nets equipped with rewards and a control mechanism via the deactivation of controllable transitions. Such nets can be translated into Markov decision processes (MDPs), potentially leading to a combinatorial explosion in the number of states due to concurrency. Hence we restrict ourselves to instances where nets are either safe, free-choice and acyclic nets (SAFC nets) or even occurrence nets and policies are defined by a constant deactivation pattern. We obtain complexity-theoretic results for such cases via a close connection to Bayesian networks, in particular we show that for SAFC nets the question whether there is a policy guaranteeing a reward above a certain threshold is -complete. We also introduce a partial-order procedure which uses an SMT solver to address this problem.