# Petri Net Toolbox for Multi-Robot Planning under Uncertainty
## 2 Background  
Generalized stochastic Petri nets [22] extend Marked Ordinary Petri nets (MOPNs) by adding the capability of modeling events that take a stochastic time until completion. In [23] we introduced _GSPNs with rewards_ that extend GSPNs by adding place and transition rewards. A GSPNR for multi-robot systems is a tuple \(G^{\prime}=\langle P,T,W^{+},W^{-},F,m_{0},r_{P},r_{T}\rangle\) and is defined as follows:  
* \(P\) is a non-empty and finite set of places that models local robot states. These represent action execution or action selection states for subsets of the multi-robot system, denoted as action places and decision places, respectively;
* \(T=T_{I}\cup T_{T}\) is a finite set of transitions partitioned into the subset of all immediate transitions \(T_{I}\) and of all timed transitions \(T_{T}\). The firing delays of timed transitions are exponentially distributed and model the time uncertainty associated with these uncontrollable events, such as the time a robot takes to traverse the path between two locations. The immediate transitions represent the controllable actions that the team of robots has available;
* \(W^{-}:P\times T\rightarrow\mathbb{N}\) and \(W^{+}:T\times P\rightarrow\mathbb{N}\) are input and output arc weight functions, respectively. Input arcs assign which timed events can trigger or what are the available actions in a local state. Output arcs dictate the local state update resulting from such timed events or of the selected action;
* \(F:T\rightarrow\mathbb{R}_{\geq 0}\) is a function that associates a rate to each timed transition or a weight to each immediate transition, dictating the probability distribution of the uncontrollable events or of the control policy, respectively;
* \(m_{0}:P\rightarrow\mathbb{N}\) is the initial marking. A marking represents the number of robots executing each action or in each decision state;
* \(r_{P}:P\rightarrow\mathbb{R}_{\geq 0}\) is the place reward function and gives a reward \(r_{P}(p)\) per time unit in markings where there is at least one token in \(p\);
* \(r_{T}:T_{I}\rightarrow\mathbb{R}_{\geq 0}\) is the transition reward function and gives a reward every time the action, associated to \(t\in T_{I}\) is selected. In this representation each token corresponds to an individual robot. The marking \(m:P\rightarrow\mathbb{N}\) represents the global state of the system, where \(m(p)=k\) means that there are \(k\) robots in the local state represented by \(p\in P\). The dynamics of a GSPNR is defined by the firing rule, which determines how the robots move from the execution of one action to the next and how the action selection impacts the local states of the robots. The firing rule dictates that when one transition \(t\) is fired \(W^{-}(p_{i},t)\) tokens are consumed from all the places \(p_{i}\) that have input arcs to \(t\) and \(W^{+}(p_{j},t)\) tokens are produced in all the places \(p_{j}\) that have output arcs from \(t\). Transitioning from marking \(m\) to marking \(m^{\prime}\) due to the firing of \(t\) is denoted as \(m[t]m^{\prime}\). The set that contains all markings reachable from the initial marking \(m_{0}\), under the firing rule, is denoted as \(R(G^{\prime})\). The reachable state space of a conservative GSPNR has an upper bound given by the number of multisets of cardinality \(|P|\), with elements taken from a finite set of cardinality \(\sum m(p),\forall p\in P\). We shall refer to this as \(p\)_multichoose_\(r\), where \(p=|P|\) and \(r=\sum m(p),\forall p\in P\). We denote the set of input places of transition \(t\) as \(IN(t)=\{p\in P\mid W^{-}(p,t)>0\}\). A marking where at least one immediate transition is enabled is denoted as vanishing. A marking where there are no immediate transitions enabled and there is at least one timed transition enabled is denoted as tangible. The set of all vanishing markings and the set of all tangible markings are denoted as \(R_{V}(G^{\prime})\) and \(R_{T}(G^{\prime})\), respectively.