# Path Planning of Multi-Type Robot Systems with Time Windows Based on Timed Colored Petri Nets
## 3 Preliminary
### Colored Petri Nets  
**Definition 1**. : _Let \(S\) be a set. A multiset [45]\(\mathbf{\alpha}\) over \(S\) is defined by a mapping \(\mathbf{\alpha}:S\to\mathbb{N}=\{0,1,2,\ldots\}\) and is represented as_  
\[\mathbf{\alpha}=\sum_{s\in S}\mathbf{\alpha}(s)\otimes s\]  
_where \(s\in S\) is an element of set \(S\) and \(\mathbf{\alpha}(s)\) denotes the number of occurrences of the element \(s\) in the set \(S\)._  
A _Colored Petri Net_ (CPN) is a quintuple \(N=(P,T,Co,\mathbf{Pre,Post})\), where \(P\) is a set of \(n\) places; \(T\) is the a of \(m\) transitions; \(Cl\) is a set of colors; \(Co:P\cup T\to Cl\) is a function that associates a set of colors from \(Cl\) to each element in \(P\cup T\). For each \(p_{i}\in P\), \(Co(p_{i})=\{a_{i,1},a_{i,2},\ldots,a_{i,u_{i,u_{i}}}\}\subseteq Cl\) is the set of possible token colors in \(p_{i}\), and \(u_{i}\) denotes the total number of possible token colors in \(p_{i}\). Analogously, for each \(t_{j}\in T\), \(Co(t_{j})=\{b_{j,1},b_{j,2},\ldots,b_{j,p_{j}}\}\subseteq Cl\) is the set of possible occurrence colors of \(t_{j}\), and \(v_{j}\) denotes the total number of possible occurrence colors of \(t_{j}\). Matrices \(\mathbf{Pre}\), \(\mathbf{Post}\in\mathbb{N}^{n\times m}\) are the _pre_- and _post-incidence matrix_. Each element \(\mathbf{Pre}(p_{i},t_{j})\) is mapped from the set of occurrence colors of \(t_{j}\) to a non-negative multiset over the set of colors of \(p_{i}\), i.e., \(\mathbf{Pre}(p_{i},t_{j}):Co(t_{j})\to\mathbb{N}(Co(p_{i}))\), for \(i=1,\ldots,n\) and \(j=1,\ldots,m\). We use \(\mathbf{Pre}(p_{i},t_{j})\) to represent a matrix of \(u_{i}\times v_{j}\) non-negative integers, where \(\mathbf{Pre}(p_{i},t_{j})(h,k)\) denotes the weight of the arc from place \(p_{i}\) with respect to color \(a_{i,h}\) to transition \(t_{j}\) with respect to color \(b_{j,k}\). The mapping for \(\mathbf{Post}(p_{i},t_{j})\) can be analogously defined. The _incidence matrix_\(\mathbf{C}\) is an \(n\times m\) matrix, where \(\mathbf{C}(p_{i},t_{j}):Co(t_{j})\to\mathbb{Z}(Co(p_{i}))\), \(i=1,\ldots,n\), \(j=1,\ldots,m\), and \(\mathbf{C}(p_{i},t_{j})=\mathbf{Post}(p_{i},t_{j})-\mathbf{Pre}(p_{i},t_{j})\). The _marking_\(\mathbf{M}(p_{i})\) of place \(p_{i}\in P\) is a _non-negative multiset_ over \(Co(p_{i})\). The mapping \(\mathbf{M}(p_{i}):Co(p_{i})\to\mathbb{N}\) is associated with each possible token color in \(p_{i}\), which is a non-negative integer representing the number of tokens of that color contained in place \(p_{i}\), and  
\[\mathbf{M}(p_{i})=\sum_{s\in Co(p_{i})}M(p_{i})(s)\otimes s.\]  
where marking \(\mathbf{M}(p_{i})\) is denoted as a column vector of \(u_{i}\) non-negative integers that has an \(h\)-th component \(M(p_{i})(h)\) equal to the number of color tokens \(a_{i,h}\) contained in place \(p_{i}\). The marking \(\mathbf{M}\) is defined as an \(n\)-dimensional column vector of multisets, where  
\[\mathbf{M}=[\mathbf{M}(p_{1}),\ldots,\mathbf{M}(p_{n})]^{T}.\]  
A _colored Petri net system_\(\langle N,\mathbf{M}\rangle\) is a colored Petri net \(N\) with a marking \(\mathbf{M}\). A transition \(t_{j}\in T\) is _enabled_ at a marking \(\mathbf{M}\) with respect to color \(b_{j,k}\) if for each \(p_{i}\in P\) it holds \(M(p_{i})(h)\geq Pre(p_{i},t_{j})(h,k)\) (\(h=1,\ldots,u_{i}\)), and an enabled transition \(t_{j}\) may fire yielding a new marking \(\mathbf{M}^{\prime}\), denoted by \(M[t_{j}(k)\mathbf{M}^{\prime}\), where \(M^{\prime}(p_{i})(h)=M(p_{i})(h)-Pre(p_{i},t_{j})(h,k)+Post(p_{i},t_{j})(h,k)\), \(\forall p_{i}\in P\).