11institutetext: 1 Eindhoven University of Technology, Netherlands
11email<EMAIL_ADDRESS>
2 Eindhoven Artificial Intelligence Systems Institute, Netherlands

# Action-Evolution Petri Nets: a Framework for Modeling and Solving Dynamic
Task Assignment Problems

Riccardo Lo Bianco 11 Remco Dijkman 11 Wim Nuijten 11 2 2 Willem van Jaarsveld
11

###### Abstract

Dynamic task assignment involves assigning arriving tasks to a limited number
of resources in order to minimize the overall cost of the assignments. To
achieve optimal task assignment, it is necessary to model the assignment
problem first. While there exist separate formalisms, specifically Markov
Decision Processes and (Colored) Petri Nets, to model, execute, and solve
different aspects of the problem, there is no integrated modeling technique.
To address this gap, this paper proposes Action-Evolution Petri Nets (A-E PN)
as a framework for modeling and solving dynamic task assignment problems. A-E
PN provides a unified modeling technique that can represent all elements of
dynamic task assignment problems. Moreover, A-E PN models are executable,
which means they can be used to learn close-to-optimal assignment policies
through Reinforcement Learning (RL) without additional modeling effort. To
evaluate the framework, we define a taxonomy of archetypical assignment
problems. We show for three cases that A-E PN can be used to learn close-to-
optimal assignment policies. Our results suggest that A-E PN can be used to
model and solve a broad range of dynamic task assignment problems.

###### Keywords:

Petri Nets, Dynamic Assignment Problem, Business Process Optimization, Markov
Decision Processes, Reinforcement Learning

##  1 Introduction

During the execution of a business process, tasks become executable and
resources become available to execute these tasks. As resources are assigned
to tasks, they become unavailable to execute other tasks. Consequently,
continuously assigning the right task to the right resource is essential to
run a process efficiently. This problem is known as dynamic task assignment.
The dynamic task assignment problem can be seen as a particular case of the
dynamic assignment problem, which, according to [1], is the problem of
assigning a fixed number of individuals to a sequence of tasks, such as to
minimize the total cost of the allocations, which may include setup costs,
travel costs, or other time-varying costs. This problem has been extensively
studied in business process optimization [2] as well as related areas, such as
manufacturing [3]. For the sake of brevity, we will employ the term
“assignment problem” to indicate the general dynamic (task) assignment
problem.

To solve an assignment problem, it must first be modeled mathematically.
Markov Decision Processes (MDPs) are a common technique for modeling
assignment problems [4], and they are the standard interface for Reinforcement
Learning (RL) algorithms [5]. The basic definition of MDP involves a single
agent interacting with an environment to maximize a cumulative reward, which
is a global signal of the goodness of the actions chosen by the agent during a
(possibly infinite) sequence of system states. In the context of business
process optimization, the environment is the business process that must be
executed, and the agent decides which task to assign to which resource. The
reward is calculated based on what we want to optimize in the process, such as
the total time resources spend working, the total cost of employing the
resources, or the time customers spend waiting. While MDPs provide a good
formalism for modeling the agent’s behavior, they consider the environment, in
our case the business process, as a black box that provides rewards for the
decisions taken by the agent without exposing its internal behavior. Moreover,
they do not have an agreed-upon syntax and lack any type of graphical
representation. On the other hand, (Colored) Petri Nets [6] are a well-known
formalism for modeling a business process but have no inherent mechanisms for
modeling and calculating the best decision in a given situation. Also,
frameworks exist for many mathematical optimization techniques, such as linear
programming and constraint programming, where problems can be modeled and
solved without additional effort. However, no such framework exists for
dynamic task assignment problems.

To fill this gap, this paper presents a unified and executable framework for
modeling assignment problems. We use the term “unified” to refer to the
capability of expressing both the agent and the environment of the assignment
problem in a single standardized notation, thus simplifying the modeling of
new problems. We use the term “executable” to refer to the possibility of
using the models to train and test decision-making algorithms (specifically RL
algorithms) without additional effort. To this end, we propose a new artifact
in the form of a modeling language with a solid mathematical foundation,
namely A-E Petri Net (A-E PN), which draws from the well-known Petri Net (PN)
formalism to model assignment problems in a readable and executable manner.
This paper pays particular attention to embedding the A-E PN formalism in the
RL cycle, such that RL algorithms can be trained and used to solve assignment
problems without additional effort.

The proposed artifact is evaluated by modeling and solving a set of
archetypical assignment problems. A taxonomy of assignment problem variants is
proposed, and an example for each of the three main variants is modeled
through A-E PN. An RL algorithm is trained on each instance, achieving close-
to-optimal results. Apart from modeling each assignment problem as an A-E PN,
no additional effort is required to achieve these results, empirically
demonstrating that A-E PN constitutes a unified and executable framework for
modeling and solving assignment problems.

Against this background, the remainder of this paper is structured as follows.
Section 2 is dedicated to a review of relevant literature. Section 3
introduces Timed-Arc Colored Petri Nets (T-A CPN). Section 4 is devoted to the
formal definition of Action-Evolution Petri Net and the description of the
integration of A-E PN in the classic RL loop. In section 5, an essential
taxonomy of assignment problem variants is presented. A problem instance for
each variant is modeled through A-E PN, and a RL algorithm is trained on each
instance, obtaining close-to-optimal results. Section 6 discusses the proposed
method’s benefits and limitations and delineates the next research steps.

##  2 Related work

To the best of our knowledge, this paper presents the first attempt at
defining a unified and executable framework for assignment problems. In
contrast, the relation between (generalized stochastic) Petri Nets and Markov
Chains is well studied [7], but Markov Chains cannot be used to model and
optimize (task assignment) decisions. Since Markov Decision Processes can be
seen as an extension to Markov Chains, the idea of extending Petri Nets to
model Markov Decision Processes follows naturally. Several attempts at this
exist in the literature, but none focus on the assignment problem. An overview
of existing frameworks for modeling and solving dynamic optimization problems
is presented in Table 1, listing, for each framework, the Petri Net variant
employed, the scope of applicability, and whether the framework is unified and
executable. The current work is presented in the last line.

Table 1: Comparison of existing frameworks for dynamic optimization.

Reference | PN | Scope | Unified | Executable
---|---|---|---|---
[8] | FPN | Problems expressible as finite MDPs | Yes | Yes*
[9] | DPN | Problems expressible as finite MDPs | No | Yes
[10] | GSPN | A single power management problem | Yes | No
[11] | TCPN | A single manufacturing scheduling problem | Yes | No
[12] | TCPN | Manufacturing scheduling problems | Yes | No
This paper | A-E PN | Assignment problems | Yes | Yes

* No executable example is provided.

In [8], the authors define a CPN variant: Factored Petri Net (FPN). In FPNs,
the transition probabilities are defined explicitly, and a reward is attached
to each network state. A limitation of [8] is that actions must be input marks
from a single source transition (a transition without input arcs), while our
framework allows actions to be defined anywhere in the Petri net, thus
allowing for more modeling flexiblity.

In [9], the authors propose the Decision Petri Net (DPN) formalism. In DPN,
the network is partitioned into a probabilistic network, in which transition
probabilities are determined on arcs, and a non-deterministic network,
corresponding to the actions that can be taken at a given moment by the
decision maker. In our framework, we remove the need for two separate subnets
and model the agents as tokens in the network, obtaining a unified
representation. Both [8], and [9] require the number of states in the system
to be finite, whereas our approach does not rely on states enumeration.

In [10], the authors propose a model for a power-managed distributed computing
system that is based on the Generalized Stochastic Petri Net (GSPN) formalism
and provide a translation to the equivalent continuous-time MDP. The work
demonstrates the expressive power of PN variants, but the resulting model is
not executable. Also, the paper presents a single case study, while our
approach is demonstrated to be generally applicable to modeling and solving
problems with different characteristics.

In [11], a manufacturing scheduling problem is modeled using Timed Colored
Petri Nets (TCPN). The search for an optimal policy is implemented using
Q-learning, where each action corresponds to a complete schedule, which is a
path from the initial marking to a final marking of the TCPN representing the
system, whereas in our case, an action corresponds to a single assignment,
which allows for more flexible modeling of decisions. Moreover, [11] only
covers a single case study, relying heavily on problem-specific heuristics.

In [12], the authors provide an example usage of TCPN in the context of
manufacturing systems, focusing on reinforcement learning as solving approach.
While [12] highlights the relationship between TCPN and RL, TCPNs are used
only to describe the environment and not to train or test solving algorithms.
In contrast, our work provides a unified and executable framework.

##  3 Preliminaries

This section provides the formal definition of Colored Petri Net (CPN) and
Timed-Arc Colored Petri Net (T-A CPN), which will be used to define the new
formalism.

Colored Petri Net (CPN) [6] is an extension of Petri Nets (PN) in which tokens
have different characteristics called colors. In the remainder of this
section, we rely on the CPN definition provided in [13].

######  Definition 1 (Colored Petri Net)

A CPN is defined as a tuple $CPN=(\mathcal{E},P,T,F,C,G,E,I)$, such that:

  * •

$\mathcal{E}$ is a finite set of types called color sets. Each color set must
be finite and non-empty.

  * •

$P$ is a finite set of places.

  * •

$T$ is a finite set of transitions, such that $P\cap T=\emptyset$

  * •

$F\subseteq P\times T\cup T\times P$ is a finite set of arcs.

  * •

$C:P\to\mathcal{E}$ is a color function that maps each place $p$ into a set of
possible token colors. Each token on $p$ must have a color that belongs to the
type $C(p)$, which is called the place’s color set.

  * •

$G$ is a guard function. It is defined from $T$ into expressions such that for
each $t\in T$, $G(t)$ is a Boolean expression and
$Type(Var(G(t)))\subseteq\mathcal{E}$, where $Type(x)$ denotes the type of $x$
and $Var(f)$ denotes the set of free variables in the function $f$.

  * •

$E$ is an arc expression function. It is defined from $F$ into expressions
such that for each $f\in F$, $Type(E(f))=C(P(f))_{MS}$ and
$Type(Var(E(f)))\subseteq\mathcal{E}$ where $P(f)$ is the place of $f$. This
means that each evaluation of the arc expression must yield a multi-set
(indicated by the $MS$ subscript) over the color set attached to the
corresponding place.

  * •

$I$ is an initialization function. It is defined from $P$ into expressions
such that $\forall p\in P:Type(I(p))=C(p)_{MS}$. The initialization function
determines the network’s initial marking.

######  Definition 2 (Marking)

A marking of a CPN is a function $M$, such that for each place $p\in P$, it
defines a multi-set of colors $C(p)\rightarrow\mathbb{N}$, which maps each
possible color of the place to the number of times it occurs.

For a place $p$ with colors $C(p)=\\{c_{1},c_{2}\\}$, we also write
$M(p)=c_{1}^{n}c_{2}^{m}$ to denote that $p$ has $n)$ token with color $c_{1}$
and $m$ tokens with color $c_{2}$. Since a marking is a multi-set, multi-set
operations, such as $\geq$, $+$, and $-$, are available on markings.

######  Definition 3 (Binding)

For a transition $t$, the variables $Var(t)=Var(G(t))\cup\\{Var(E(f))|f\in
F,T(f)=t\\}$ represent the set of variables from the guard function and the
expressions on its arcs, where $T(f)$ is the transition of arc $f$.

A binding of a transition $t\in T$ is a function $Y$ that maps each $v\in
Var(t)$ to a color, such that $\forall v\in Var(v):Y(v)\in Type(v)$ and
$G(t)\langle Y\rangle$ evaluates to true, where $f\langle Y\rangle$ denotes
the evaluation of a function $f$ with its free variables bound as $Y$.

For a transition $t$ with variables $Var(t)=\\{v_{1},v_{2}\\}$, we also write
$Y(t)=\langle v_{1}=c_{1},v_{2}=c_{2}\rangle$ to denote that the binding $Y$
assigns color $c_{1}$ to variable $v_{1}$ and color $c_{2}$ to variable
$v_{2}$.

We now define the behavior of a CPN through its firing rules.

######  Definition 4 (CPN Firing Rules)

  1. 1.

A transition $t$ is enabled in marking $M$ for binding $Y$ if and only if
$\forall(p,t)\in F:M(p)\geq E((p,t))\langle Y\rangle$.

  2. 2.

An enabled transition can fire, changing the Marking $M$ into a marking
$M^{\prime}$, such that $\forall p\in P:M^{\prime}(p)=M(p)-E((p,t))\langle
Y\rangle+E((t,p))\langle Y\rangle$.

The standard CPN definition assumes that the effect of a firing is always
instantaneous. To account for time, we will refer to a modified version of the
Timed-Arc Petri Net (T-A PN) formulation [14]. Our version defines a global
clock, updated according to a next-event time progression. This is also the
time management paradigm implemented in CPN Tools [15], a widely adopted
software for Petri Nets modeling.

######  Definition 5 (Timed-Arc Colored Petri Net)

A T-A CPN is defined by a tuple $TACPN=(\mathcal{E},P,T,F,C,G,E,I)$, where
$P,T,F,C,G,I$ are as in Definition 1, and $\mathcal{E}$ and $E$ are adapted as
follows:

  * •

$\mathcal{E}$ is a finite set of timed types called timed color sets. A color
of a timed color set has both a value $v$ and a time $\tau$, we also denote
this as $v@\tau$.

  * •

$E$ is an arc expression function. It is defined from $F$ into tuples of two
elements. For a given $f\in F$, $E(f)_{0}$ is defined the same as $E$ in
Definition 1 and $E(f)_{1}$ is a scalar increment, thus $\forall f\in
F:Type(E(f)_{1})=\mathbb{N}$, that indicates the generated tokens’ time with
reference to the global clock. The second tuple element is ignored for arcs
outgoing from places and incoming to transitions since the scalar increment is
only used when producing new tokens.

Note that each color now has a time and consequently, each color in a marking
and in a binding has time. For example, we can refer to the marking of a place
$p$ with $M(p)=c_{1}@2^{1}c_{1}@3^{5}$ as the marking that has one token with
color $c_{1}$ at time 2 and five tokens with color $c_{1}$ at time 3. With
some abuse of notation, we will allow arc expression functions $E(f)_{0}$, to
ignore the time element of colors and leave it unaffected, and we will denote
with $c@e$ that an expression $e$ only changes the time element of a timed
color.

We also extend the concept of marking to account for the presence of a global
clock, which we need further on in the paper to define the transition rules
for A-E PN.

######  Definition 6 (Timed Marking)

A timed marking is defined as the tuple $TM=(M,\tau)$, where $M$ is a marking
and $\tau$ is the current value of the global clock.

The T-A CPN firing rule can then be expressed as follows:

######  Definition 7 (T-A CPN Firing Rules)

  1. 1.

Let $t$ be a transition that is enabled in marking $M$ for binding $Y=\langle
v1=c_{1}@\tau_{1},v2=c_{2}@\tau_{2},\ldots,v_{n}=c_{n}@\tau_{n}\rangle$ as in
Definition 4 (using only $E_{0}$ for $E$). The enabling time of the
transition, denoted $\tau_{E}$, is $max(\tau_{1},\tau_{2},\ldots,\tau_{n})$.

  2. 2.

An enabled transition $t$ is time-enabled in timed marking $(M,\tau)$, if its
enabling time $\tau_{E}$ is less than or equal to $\tau$, and there exists no
transition $t^{\prime}$ that is enabled in marking $M$ for some binding
$Y^{\prime}$ with enabling time $\tau^{\prime}_{E}\leq\tau_{E}$.

  3. 3.

A transition $t$ that is time-enabled in timed marking $(M,\tau)$ for binding
$Y$ with enabling time $\tau_{E}$ can fire, changing the timed marking to
$(M^{\prime},\tau_{E})$, where $M^{\prime}$ is constructed, such that $\forall
p\in P:M^{\prime}(p)=M(p)-E((p,t))_{0}\langle Y\rangle+E((t,p))_{0}\langle
Y\rangle@\tau_{E}+E((t,p))_{1}$.

  4. 4.

When there exists no $t$ in timed marking $(M,\tau)$, for which there is a
binding $Y$, such that $t$ is time-enabled, the global clock $\tau$ is
increased until there is.

In practice, point 4 can be performed by evaluating bindings that are enabling
but not time-enabling. The binding that leads to the lowest enabling time
reveals the minimal increase of the global clock, making it possible to update
the global clock using a next-event time progression.

##  4 Action-Evolution Petri Nets

This section extends the definition of T-A CPN to provide a model that can
automatically learn close-to-optimal task assignment policies. This extension
is called Action-Evolution Petri Nets (A-E PN). The new elements are first
described informally, then a formal definition is provided. Finally, the
definition is incorporated into the RL cycle, allowing for automated learning
of close-to-optimal task assignment policies.

###  4.1 Tags and Rewards

The overall objective of A-E PN is to mimic the behavior of an agent that
observes changes in the environment and acts upon those changes when possible.
We will thus extend the CPN definition provided in the background section to
distinguish two separate types of transitions:

  * •

Actions: transitions that represent actions taken by the agent. In the context
of assignment problems, the firing of an action transition represents a single
assignment.

  * •

Evolutions: transitions that represent events happening in the system
independently of the actions taken by the agent. The firing of an evolution
transition represents a single event in the environment, for example, the
arrival of a new order.

This distinction is expressed by associating every transition with a
transition tag, that can be either $A$ (action) or $E$ (evolution), through a
transition tag function $L$. We also extend the concept of marking to embed a
network tag $l$, which can assume a single value in $\\{A,E\\}$: only
transitions associated with a tag of the same type as the one in the network
tag are allowed to fire. The network tag $l$ must be updated every time no
transitions with the same tag are available for firing. The tag update
function $S$ performs the update by changing the network’s tag from $A$ to $E$
or vice versa: $S(l)=A\text{, if }l=E;S(l)=E\text{, if }l=A$. We use the term
tag time frame to refer to the period between changes in the network tag.

The objective of the RL cycle is the maximization of a cumulative reward over
a (possibly infinite) horizon. To track rewards in A-E PN, we introduce a
transitions reward function $\mathcal{R}$ that associates a reward to the
firing of any transition, and we embed the total reward accumulated by firing
transitions, which we call network reward $\rho$, in the network’s marking. In
general, a reward can be produced by any change in the environment, regardless
of whether an action or an evolution produced such change. For this reason, a
reward is produced due to the firing of any transition, regardless if the
transition is tagged as an action or an evolution. To comply with the classic
RL cycle, rewards associated with evolutions are accumulated and awarded to
the last action taken, eventually after a normalization operation (see
subsection 4.3).

To further clarify the basic mechanisms of A-E PN, the example in Fig. 1
provides an overview of a sequence of firings.

Figure 1: A sequence of firings in a simple task assignment problem.

The network shows the evolution of a system with two types of tasks, $a$ and
$b$, and two employees, one that can undertake only task $a$ and one that can
undertake only task $b$. A task of each type arrives at every clock tick, and
an employee is assigned to a task of the same type. Assignments take one clock
tick to complete, and a reward of $1$ is produced every time an assignment is
completed. The parentheses on the top right corner contain the components of
the tagged marking that are not directly represented as network elements.
Guard functions and reward functions are associated with single transitions.
Timed tokens and arcs follow the notation introduced in Definition 5. The
initial marking is presented in the dotted square a, in which only $E$
transitions are enabled. After two firings of transition Arrive, consuming
both tokens in the Arrival place (in any order), no evolution transitions are
available, so the tag is updated, and the system transitions to state b.
Notice that the transition from e to a does not produce a clock update, since
actions are available to be taken at time $0$. In b, transition Start is
enabled. In this case, the RL agent would have two available actions: pairing
task $a$ with resource $a$, or pairing task $b$ with resource $b$. In this
case, both actions will be taken sequentially, in any order, leading to tagged
marking c, while in the general case, choices would have to be made by a
decision algorithm on which assignments to make. In c, the network tag is
again $E$, and two transitions are associated with time-enabled steps: Arrive
and Complete. The firing of Arrive produces two new tokens at time $1$ in the
Waiting place, while the firing of Complete places two tokens back in the
Resources place at time $1$ and generates a network reward increment of $2$
units in state d.

###  4.2 Formal Definition of Action-Evolution Petri Net

To provide a formal definition of A-E PN, we must adapt three definitions from
T-A CPN: the net itself, the marking, and the firing rules.

######  Definition 8 (Action-Evolution Petri Net)

Let $\mathcal{T}=\\{A,E\\}$ be a finite set of tags representing actions and
evolutions, and $S:\mathcal{T}\to\mathcal{T}$ a network tag update function.
An Action-Evolution Petri Net (A-E PN) is as a tuple
$AEPN=(\mathcal{E},P,T,F,C,G,E,I,L,l_{o},\mathcal{R},\rho_{0})$, where
$\mathcal{E},P,T,F,C,G,E,I$ follow Definition 5, and:

  * •

$L:T\to\mathcal{T}$ is a transition tag function that maps each transition $t$
to a single tag. Only transitions associated with the same tag as the network
can fire.

  * •

$l_{0}\in\mathcal{T}$ is a singleton containing the network’s initial tag,
usually equal to $E$.

  * •

$\mathcal{R}:T\to(f:\mathbb{R})$ associates every transition with a reward
function. The function can take timing properties or numbers of tokens
(representing completed cases) as parameters, thus allowing for flexbility in
modeling reward.

  * •

$\rho_{0}\in\mathbb{R}$ is the initial network reward, usually equal to $0$.

######  Definition 9 (Tagged Marking)

A tagged marking is a tuple $TM=(M,l,\tau,\rho)$, where the tuple $(M,\tau)$
is a timed marking, as in Definition 6, $l\in\mathcal{T}$ is the network tag
at the current time $\tau$, and $\rho\in\mathbb{R}$ is the total reward
accumulated until the current time $\tau$.

######  Definition 10 (A-E PN Firing Rule)

  1. 1.

A transition $t$ is tag-enabled in a tagged marking $(M,l,\tau,\rho)$ for
binding $Y$ if and only if $t$ is enabled in $M$ according to Definition 1,
and $L(t)=l$.

  2. 2.

Let $t$ be a transition that is tag-enabled in tagged marking
$(M,l,\tau,\rho)$ for binding $Y=\langle
v1=c_{1}@\tau_{1},v2=c_{2}@\tau_{2},\ldots,v_{n}=c_{n}@\tau_{n}\rangle$ . The
enabling time of the transition, denoted $\tau_{E}$, is
$max(\tau_{1},\tau_{2},\ldots,\tau_{n})$.

  3. 3.

An enabled transition $t$ is tag-time-enabled in tagged marking
$TTM=(M,l,\tau,\rho)$, if its enabling time $\tau_{E}$ is less than or equal
to $\tau$, and there exists no transition $t^{\prime}$ that is enabled in
tagged marking $TTM$ for some binding $Y^{\prime}$ with enabling time
$\tau^{\prime}_{E}\leq\tau_{E}$.

  4. 4.

A transition $t$ that is tag-time-enabled in tagged marking $(M,l,\tau,\rho)$
for binding $Y$ with enabling time $\tau_{E}$ can fire, changing the tagged
marking to $(M^{\prime},l,\tau_{E},\rho^{\prime})$, where $M^{\prime}$ is
constructed, such that $\forall p\in P:M^{\prime}(p)=M(p)-E((p,t))_{0}\langle
Y\rangle+E((t,p))_{0}\langle Y\rangle@\tau_{E}+E((t,p))_{1}$ and
$\rho^{\prime}=\rho+\mathcal{R}(t)$.

  5. 5.

When there exists no $t$ in tagged marking $TTM=(M,l,\tau,\rho)$, for which
there is a binding $Y$, such that $t$ is time-enabled, the set of all
transitions is partitioned in two disjoint sets: $T_{\text{current}}=\\{t\in
T|L(t)=l\\}$ and $T_{\text{next}}=\\{t\in T|L(t)\neq l\\}$. Let
$\tau_{current}$ be the minimum value for which a transition in
$T_{\text{current}}$ is time-enabled (according to Definition 7), and let
$\tau_{next}$ be the minimum value for which a transition in $T_{\text{next}}$
is time-enabled. Note that $\tau_{current}$ and $\tau_{next}$ can be
undefined.

     * •

If $\tau_{current}$ is defined, and $\tau_{current}\leq\tau_{next}$ or
$\tau_{next}$ is undefined, only the global clock is updated, leading to a new
tagged marking $TTM^{\prime}=(M,l,\tau_{current},\rho)$.

     * •

If $\tau_{next}$ is defined, and $\tau_{current}>\tau_{next}$ or
$\tau_{current}$ is undefined, both the global clock and the network tag are
updated, leading to a new tagged marking
$TTM^{\prime}=(M,S(l),\tau_{next},\rho)$.

###  4.3 Extending the Reinforcement Learning Loop

Having completely defined the characteristics of the A-P PN formalism, we can
clarify how it can be used to learn optimal task assignment policies (i.e.
mapping from observations to assignments) by applying it in a Reinforcement
Learning (RL) cycle. Figure 2 shows the RL cycle. In every step in the cycle,
the agent receives an observation (a representation of the environment’s
state), then it produces a single action that it considers the best action for
this observation. The action leads to a change in the environment’s state. The
environment is responsible for providing a reward for the chosen action along
with a new observation. Then the cycle repeats, and a new decision step takes
place. The MDP formulation is the standard framework for training an agent to
take actions that lead to the highest cumulative reward.

Figure 2: A common representation of the RL training cycle [5].

In recent years, the embedding of neural networks in RL algorithms gave birth
to the field of Deep Reinforcement Learning (DRL), achieving breakthroughs in
settings such as playing board games [16] and robotic manipulation [17], as
well as successful applications in domains like industrial process control
[18], and healthcare [19]. With the proliferation of robust DRL algorithms,
the main hurdle in modeling new problems is the definition of the environment,
which is usually represented as a black box, as in Fig. 2, thus leaving the
implementation of the system’s dynamics entirely to the modeler. The lack of a
standardized interface makes the creation of new environments time-consuming
and dependent on the modeler’s coding skills. Moreover, even introducing small
changes potentially requires substantial effort once the environment has been
modeled. These observations motivate the effort to provide a unified and
executable framework. In Fig. 3, the classic RL cycle is extended to account
for the presence of A-E PN. The main element is the A-E PN, which acts as a
simulator for the whole process.

Figure 3: The reinforcement learning cycle with A-E PN

The A-E PN communicates with the agent through two sub-components: observation
manager and action manager. The observation manager is invoked every time the
tagged marking changes, regardless if due to a firing or not. The new reward
is stored, and the network tag is evaluated: if the tag is $E$, no action is
required, and the control is given back to the A-E PN, which can fire a new
$E$ transition. If the tag is $A$, the accumulated rewards are added up, and
the result is divided by $1+(\tau_{t+1}-\tau_{t})$. The resulting value is
returned to the agent as $r_{t+1}$. The reward value takes into account the
possible misalignment between clock ticks ($\tau$) and RL steps ($t$), given
by the fact that multiple actions can happen at the same $\tau$. The
observation manager also returns to the agent the new observation $o_{t+1}$.
For the set of experiments presented in the next section, the observation is
built as a vector containing, for each place, the number of tokens of each
color in the place’s color set. The action manager is invoked every time the
agent chooses an action $a_{t}$, which it transforms into the corresponding
binding $B_{t}$ (associated with an action transition) to be fired.

##  5 Evaluation

This section aims to show that A-E PN constitutes a unified and executable
framework for expressing dynamic task assignment problems with different
characteristics: in fact, all the examples were modeled using a single
notation (except for color-specific functions on arcs, guards, and rewards)
and a RL algorithm was trained on each problem, without any additional
development effort.

We provide a (non-exhaustive) taxonomy of assignment problem variants based on
[20]. We distinguish three archetypes of assignment problems.

  * •

Assignment Problem with Compatibilities: resources are assigned to tasks
according to a measure of compatibility. Two problem subclasses can be
formulated:

    * –

Assignment Problem with Hard Compatibilities: resources can only be assigned
to tasks if they are compatible. The dynamic task assignment problem in
subsection 5.1 falls into this subclass.

    * –

Assignment Problem with Soft Compatibilities: resources can always be assigned
to tasks, but different assignments result in different system behaviors. An
example of such a problem is if multiple resources can perform a task, but
some will be faster at it than others.

  * •

Assignment Problem with Multiple Assignments: the same resource can be
assigned to multiple tasks, or the same task can be assigned to multiple
resources. Two problem subclasses can be formulated:

    * –

Assignment Problem with Resource Capacity: resources have a maximum capacity
of tasks that they can undertake before being considered full. In the simple
case each resource can only be busy with a single task at a time. The dynamic
bin packing problem in subsection 5.2 provides a more elaborate example.

    * –

Assignment Problem with Task Capacity: tasks have a minimum capacity of
resources to be assigned to them before processing. In the simple case each
tasks needs exactly one resource.

  * •

Assignment Problem with Dynamic Resources’ Behavior: resources have dynamic
behavior. Two problem subclasses can be formulated:

    * –

Assignment Problem with Action-Dependent Dynamic Resources’ Behavior:
resources change their attribute values as the consequence of taking actions.
The dynamic order-picking problem in subsection 5.3 falls into this category.

    * –

Assignment Problem with Action-Independent Dynamic Resources’ Behavior:
resources change their attribute values as the consequence of evolutions in
the environment. For example, resources may take breaks or go on holidays.

In the following sections, one example is detailed for each archetype. An
example for each subclass is implemented in the provided Python package.

###  5.1 Dynamic Task Assignment Problem with Hard Compatibilities

Let us consider a system that solves a task assignment problem, similar to the
one presented in Fig. 1. At every clock tick, two tasks arrive: one has type
$r1$ and the other $r2$. Two resources are available for the assignment: one
can only undertake tasks of type $r1$, while the other can undertake tasks of
type $r1$ or $r2$. Once a task is assigned to a resource, completion always
takes one clock tick, after which the resource becomes available for a new
assignment. A resource cannot work on multiple tasks at the same time. A
network reward of $1$ is returned every time a task is assigned to a resource
and every time an assignment completes, leading to a theoretical maximum
reward of $200$ over $100$ clock ticks. The problem can be fully expressed in
terms of A-E PN, as reported in Fig. 4.

Figure 4: A-E PN initial marking for the dynamic task assignment problem

###  5.2 Dynamic Bin Packing Problem

In this scenario, we model a dynamic version of the bin packing problem where
items (the problem tasks, characterized by their weight) arrive sequentially
and they must be allocated to two bins (the problem resources, characterized
by the total weight of objects in the bin curr and the bin’s total capacity
tot) that are emptied at every clock tick (except for the first, which is used
to generate the objects to be put in the bins). The fullness of the bins
before being emptied gives the measure of goodness of the object’s allocation,
quantified as the weight of objects in the bin divided by the total bin
capacity. This problem showcases how tokens’ colors can be used to model non-
trivial reward functions. In the example reported, three objects arrive in the
system at every clock tick, one of weight $1$ and two of weight $2$. Two
initially empty bins are available, one with capacity $2$ and one with
capacity $3$. The optimal allocation would give a reward of $2$, leading to a
theoretical maximum reward of $200$ over a $100$ clock ticks horizon. The A-E
CPN formalization of the problem is reported in Fig. 5.

Figure 5: A-E PN initial marking for the dynamic bin packing problem

###  5.3 Dynamic Order-Picking Problem

In this section, we present an example of action-dependent resource behavior
(i.e. the agent taking decisions on the actions that it performs). The example
is a simple order-picking problem in which a single agent (the resource) moves
on a squared grid of size $2$, trying to pick orders (the tasks). The agent’s
and the orders’ colors are characterized by two parameters representing the
coordinates on the grid (infinite capacity is assumed). The agent starts in
position $(0,0)$ and can move left, right, up, or down, but not over a
diagonal. If an order is in the same position as the agent, the latter can use
an action to pick the order. A single order arrives at every clock tick,
always in position $1,1$, and the order stays on the grid for exactly one
clock tick, according to a time-to-live (TTL) parameter. The agent’s objective
is to pick as many orders as possible, so it gets a reward of $1$ every time
an order is picked, leading to a theoretical maximum reward of $98$ over a
$100$ clock ticks horizon (at least two orders will be lost due to the agent
moving to position $(1,1)$. The problem is formulated in terms of A-E PN in
Fig. 6.

Figure 6: A-E PN initial marking for the dynamic order-picking problem

###  5.4 Experimental Results

All experiments were implemented in a proof-of-concept package111The code is
publicly available in https://github.com/bpogroup/aepn-project., relying on
the Python programming language and the widely adopted RL library Gymnasium
[21]. Proximal Policy Optimization (PPO) [22] with masking was used as the
training algorithm. Specifically, the PPO implementation of the Stable
Baselines package [23] is used. Note, however, that the mapping from each A-E
PN to PPO was automated and requires no further effort from the modeler. The
PPO algorithm was trained on each example for ($10^{6}$ steps with $100$ clock
ticks per episode, completed in less than $2300$ seconds on a mid-range
laptop, without GPUs), always using the default hyperparameters. The
experimental results were computed on (network) rewards obtained by the
trained agent and following a random policy over $1000$ trajectories, each of
duration $100$ clock ticks. In Table 2, the average and standard deviations of
rewards obtained by the trained PPO are compared to those of a random policy
on each of the three presented problem instances, with reference to the
maximum attainable reward. In all cases, PPO shows to be able to learn a
close-to-optimal assignment policy.

Table 2: The results for the three presented problem instances. Instance | Random | PPO | Optimal
---|---|---|---
Task Assignment | $186.894\pm 2.084$ | $199.852\pm 0.398$ | $200$
Bin Packing | $186.746\pm 1.941$ | $199.963\pm 0.186$ | $200$
Order Picking | $6.046\pm 2.585$ | $96.776\pm 2.019$ | $98$

##  6 Conclusions and Future Work

This paper presented a framework for modeling and solving dynamic task
assignment problems. To this end, it introduced a new variant of Petri Nets,
namely Action-Evolution Petri Nets (A-E PN), to provide a mathematically sound
modeling tool. This formalism was integrated with the Reinforcement Learning
(RL) cycle and consequently with existing algorithms that can solve RL
problems. To evaluate the general applicability of the framework for modeling
and solving task assignment problems, a taxonomy of archetypical problems was
introduced, and working examples were provided. A DRL algorithm was trained on
each implementation, obtaining close-to-optimal policies for each example.
This result shows the suitability of A-E PN as a unified and executable
framework for modeling and solving assignment problems.

While the applicability of the framework was shown, its possibilities and
limitations are yet to be fully explored. This will be done in future research
by expanding the provided taxonomy of assignment problems and considering
different problem classes.

## Acknowledgement

The research that led to this publication was partly funded by the European
Supply Chain Forum (ESCF) and the Eindhoven Artificial Intelligence Systems
Institute (EAISI) under the AI Planners of the Future program.

## References

  * [1] H. W. Kuhn.  The Hungarian method for the assignment problem.  Naval Research Logistics Quarterly, 2(1-2):83–97, March 1955.
  * [2] N. Gülpınar, E. Çanakoğlu, and J. Branke.  Heuristics for the stochastic dynamic task-resource allocation problem with retry opportunities.  European Journal of Operational Research, 266(1):291–303, April 2018.
  * [3] L. Hu, Z. Liu, W. Hu, Y. Wang, and J. Tan.  Petri-net-based dynamic scheduling of flexible manufacturing system via deep reinforcement learning with graph convolutional network.  Journal of Manufacturing Systems, 55:1–14, April 2020.
  * [4] M. Z. Spivey and W. B. Powell.  The Dynamic Assignment Problem.  Transportation Science, 38(4):399–419, November 2004.
  * [5] R. Sutton and A. Barto.  Reinforcement Learning: An Introduction.  page 352.
  * [6] K. Jensen.  A brief introduction to coloured Petri Nets.  In Tools and Algorithms for the Construction and Analysis of Systems, volume 1217, pages 203–208. 1997.
  * [7] F. Bause and P. Kritzinger.  Stochastic Petri Nets: An Introduction to the Theory.  ACM SIGMETRICS Performance Evaluation Review, 26(2):2–3, August 1998.
  * [8] M. Eboli and F. Cozman.  Markov Decision Processes from Colored Petri Nets.  In Advances in Artificial Intelligence – SBIA 2010, volume 6404, pages 72–81. 2010.  Series Title: Lecture Notes in Computer Science.
  * [9] M. Beccuti, G. Franceschinis, and S. Haddad.  Markov Decision Petri Net and Markov Decision Well-Formed Net Formalisms.  In Petri Nets and Other Models of Concurrency – ICATPN 2007, volume 4546, pages 43–62. 2007.
  * [10] Q. Qiu, Q. Wu, and M. Pedram.  Dynamic power management of complex systems using generalized stochastic Petri nets.  In Proceedings of the 37th conference on Design automation - DAC ’00, pages 352–356. ACM Press, 2000.
  * [11] M. Drakaki and P. Tzionas.  Manufacturing Scheduling Using Colored Petri Nets and Reinforcement Learning.  Applied Sciences, 7(2):136, February 2017.
  * [12] S. Riedmann, J. Harb, and S. Hoher.  Timed Coloured Petri Net Simulation Model for Reinforcement Learning in the Context of Production Systems.  In Bernd-Arno Behrens, Alexander Brosius, Welf-Guntram Drossel, Wolfgang Hintze, Steffen Ihlenfeldt, and Peter Nyhuis, editors, Production at the Leading Edge of Technology, pages 457–465, Cham, 2022\. Springer International Publishing.
  * [13] K. Jensen and G. Rozenberg.  High-level Petri nets: theory and application.  Springer-Verlag, 1991.
  * [14] L. Jacobsen, M. Jacobsen, M. H. Møller, and J. Srba.  Verification of timed-arc petri nets.  In SOFSEM 2011: Theory and Practice of Computer Science, pages 46–72, 2011.
  * [15] CPN Tools.  https://cpntools.org/.
  * [16] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap, F. Hui, L. Sifre, G. van den Driessche, T. Graepel, and D. Hassabis.  Mastering the game of Go without human knowledge.  Nature, 550(7676):354–359, October 2017.
  * [17] D. Kalashnikov, A. Irpan, P. Pastor, J. Ibarz, A. Herzog, E. Jang, D. Quillen, E. Holly, M. Kalakrishnan, V. Vanhoucke, and S. Levine.  QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation, November 2018.
  * [18] R. Nian, J. Liu, and B. Huang.  A review on reinforcement learning: Introduction and applications in industrial process control.  Computers & Chemical Engineering, 139:106886, August 2020.
  * [19] C. Yu, J. Liu, and S. Nemati.  Reinforcement Learning in Healthcare: A Survey, April 2020.  arXiv:1908.08796 [cs].
  * [20] David W. Pentico.  Assignment problems: A golden anniversary survey.  European Journal of Operational Research, 176(2):774–793, January 2007.
  * [21] Gymnasium.  https://gymnasium.farama.org/.
  * [22] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov.  Proximal Policy Optimization Algorithms, August 2017.  arXiv:1707.06347 [cs].
  * [23] Sb3-contr.  https://github.com/Stable-Baselines-Team/stable-baselines3-contrib.


(0.1863, 0.15) | (1.5,7.4) | 50 | 100 | (0.656, 0.812) | (0.769, 0.809) | 95.8 | 8.3 | 96.1
|  |  | 500 |  | (0.786, 0.809) | 95.3 | 5.3 | 95.6
|  | 100 | 100 | (0.708, 0.816) | (0.776, 0.807) | 95.9 | 7.0 | 96.3
|  |  | 500 |  | (0.789, 0.806) | 95.7 | 4.6 | 95.9
(0.0438, 0.17) | (0.7, 8) | 50 | 100 | (0.500, 0.809) | (0.500, 0.808) | 95.9 | 7.4 | 95.5
|  |  | 500 |  | (0.500, 0.808) | 95.4 | 5.5 | 95.7
|  | 100 | 100 | (0.500, 0.810) | (0.773, 0.808) | 94.1 | 6.0 | 94.9
|  |  | 500 |  | (0.500, 0.807) | 94.4 | 4.5 | 95.6
(0.1, 0.2133) | (0, 6.5) | 50 | 100 | (0.688, 0.819) | (0.786, 0.818) | 94.9 | 9.7 | 96.0
|  |  | 500 |  | (0.790, 0.815) | 95.2 | 7.2 | 95.8
|  | 100 | 100 | (0.727, 0.818) | (0.791, 0.814) | 94.7 | 7.4 | 95.0
|  |  | 500 |  | (0.793, 0.813) | 95.0 | 5.4 | 95.4
(0.1062, 0.16) | (1.2, 7.9) | 50 | 100 | (0.550, 0.814) | (0.766, 0.812) | 96.1 | 7.4 | 96.2
|  |  | 500 |  | (0.777, 0.810) | 95.3 | 5.0 | 96.2
|  | 100 | 100 | (0.713, 0.812) | (0.780, 0.810) | 95.3 | 5.9 | 95.8
|  |  | 500 |  | (0.789, 0.808) | 95.4 | 4.1 | 95.9
Scenario 2a ($J_{1}=6,J_{2}=12$) |  |  |  |  |
(0.1863, 0.15) | (1.5,7.4) | 50 | 200 | (0.509, 0.814) | (0.735, 0.821) | 94.8 | 11.5 | 95.8
(0.0438, 0.17) | (0.7, 8) | 50 | 200 | (0.500, 0.807) | (0.500, 0.809) | 94.9 | 11.1 | 96.3
(0.1, 0.2133) | (0, 6.5) | 50 | 200 | (0.515, 0.823) | (0.775, 0.820) | 95.9 | 14.7 | 95.8
(0.1062, 0.16) | (1.2, 7.9) | 50 | 200 | (0.500, 0.812) | (0.500, 0.813) | 94.8 | 10.7 | 96.2
Scenario 2b ($J_{1}=10,J_{2}=20$) |  |  |  |  |
(0.1863, 0.15) | (1.5,7.4) | 50 | 200 | (0.556, 0.815) | (0.771, 0.814) | 96.2 | 8.3 | 95.7
(0.0438, 0.17) | (0.7, 8) | 50 | 200 | (0.500, 0.808) | (0.500, 0.808) | 95.3 | 8.2 | 95.9
(0.1, 0.2133) | (0, 6.5) | 50 | 200 | (0.535, 0.820) | (0.782, 0.816) | 95.7 | 10.9 | 96.0
(0.1062, 0.16) | (1.2, 7.9) | 50 | 200 | (0.500, 0.813) | (0.500, 0.813) | 95.7 | 7.7 | 96.3

$n_{j}^{(1)}$: number of patients in center $j$ at stage 1, $n_{j}^{(2)}$:
number of patients in center $j$ at stage 2.
True Mean under $\hat{x}^{opt,(2,n^{(1)})}$: true mean outcome under the stage
2 recommended intervention.
True Mean under $\hat{x}^{opt}$: true mean outcome under the final estimated
optimal intervention.
$Q$2.5 and $Q$97.5: 2.5$\%$ and 97.5$\%$ quantiles.
SetCP95$\%$: empirical coverage percentage of confidence set for the optimal
intervention.
SetPerc$\%$: mean percentage of the size of the confidence set as a percent of
the total sample space.
BandsCP95$\%$: empirical coverage of 95$\%$ confidence band.