# Path Planning of Multi-Type Robot Systems with Time Windows Based on Timed Colored Petri Nets
## 3 Preliminary
### Timed Colored Petri Net for the Multi-Type Robot Systems
\begin{table}
\begin{tabular}{l l l l l l} \hline \hline
**Place** & **Description** & **Transition** & **Description** & **Transition** & **Description** \\ \hline \(p_{1}\) & Region \(r_{1}\) & \(t_{1}\) & Moving to \(r_{1}\) & from \(r_{3}\) & \(t_{14}\) & Moving to \(r_{8}\)  from \(r_{4}\) \\ \(p_{2}\) & Region \(r_{2}\) & \(t_{2}\) & Moving to \(r_{3}\)  from \(r_{1}\) & \(t_{15}\) & Moving to \(r_{5}\)  from \(r_{2}\) \\ \(p_{3}\) & Region \(r_{3}\) & \(t_{3}\) & Moving to \(r_{6}\)  from \(r_{1}\) & \(t_{16}\) & Moving to \(r_{2}\)  from \(r_{5}\) \\ \(p_{4}\) & Region \(r_{4}\) & \(t_{4}\) & Moving to \(r_{1}\)  from \(r_{6}\) & \(t_{17}\) & Moving to \(r_{4}\)  from \(r_{5}\) \\ \(p_{5}\) & Region \(r_{5}\) & \(t_{5}\) & Moving to \(r_{8}\)  from \(r_{6}\) & \(t_{18}\) & Moving to \(r_{5}\)  from \(r_{4}\) \\ \(p_{6}\) & Region \(r_{6}\) & \(t_{6}\) & Moving to \(r_{6}\)  from \(r_{8}\) & \(t_{19}\) & Moving to \(r_{10}\)  from \(r_{7}\) \\ \(p_{7}\) & Region \(r_{7}\) & \(t_{7}\) & Moving to \(r_{7}\)  from \(r_{8}\) & \(t_{20}\) & Moving to \(r_{7}\)  from \(r_{10}\) \\ \(p_{8}\) & Region \(r_{8}\) & \(t_{8}\) & Moving to \(r_{8}\)  from \(r_{7}\) & \(t_{21}\) & Moving to \(r_{9}\)  from \(r_{2}\) \\ \(p_{9}\) & Region \(r_{9}\) & \(t_{9}\) & Moving to \(r_{2}\)  from \(r_{3}\) & \(t_{22}\) & Moving to \(r_{2}\)  from \(r_{9}\) \\ \(p_{10}\) & Region \(r_{10}\) & \(t_{10}\) & Moving to \(r_{3}\)  from \(r_{2}\) & \(t_{23}\) & Moving to \(r_{10}\)  from \(r_{9}\) \\ \(p_{11}\) & Region \(r_{10}\) & \(t_{11}\) & Moving to \(r_{5}\) from \(r_{1}\) & \(t_{24}\) & Moving to \(r_{9}\)  from \(r_{10}\) \\ \(\hskip 14.226378 pt\) & & \(t_{12}\) & Moving to \(r_{1}\)  from \(r_{5}\) & \(t_{25}\) & Moving to \(r_{10}\)  from \(r_{4}\) \\ \(\hskip 14.226378 pt\) & & \(t_{13}\) & Moving to \(r_{4}\)  from \(r_{8}\) & \(t_{26}\) & Moving to \(r_{4}\)  from \(r_{10}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Description of places and transitions in Figure 2.  
Figure 2: The TCPN system corresponding to the MTRS in Figure 1.  
The possible color sets of each place \(p_{i}\in P\) (\(i=1,\ldots,10\)) and each transition \(t_{j}\in T\) (\(j=1,\ldots,26\)) are \(Co(p_{i})=\{C_{1},C_{2}\}\) and \(Co(t_{j})=\{C_{1},C_{2}\}\), respectively. The initial marking \(\mathbf{M}_{0}=[\mathbf{M}_{0}(p_{1}),\ldots,\mathbf{M}_{0}(p_{10})]^{T}\) of the TCPN system is a column vector that contains ten subvectors, where \(\mathbf{M}_{0}(p_{1})=[0\,0]^{T}\), \(\mathbf{M}_{0}(p_{2})=[0\,0]^{T}\), \(\mathbf{M}_{0}(p_{3})=[1\,0]^{T}\), \(\mathbf{M}_{0}(p_{4})=[0\,0]^{T}\), \(\mathbf{M}_{0}(p_{5})=[0\,1]^{T}\), \(\mathbf{M}_{0}(p_{6})=[0\,0]^{T}\), \(\mathbf{M}_{0}(p_{7})=[0\,0]^{T}\), \(\mathbf{M}_{0}(p_{8})=[0\,0]^{T}\), \(\mathbf{M}_{0}(p_{9})=[0\,0]^{T}\), and \(\mathbf{M}_{0}(p_{10})=[0\,0]^{T}\). Each element in subvector \(\mathbf{M}_{0}(p_{i})\) denotes the number of two different robots in region \(r_{i}\). The incidence matrix \(\mathbf{C}\) of the TCPN system is a \(10\times 26\) matrix, where \(\mathbf{C}(p_{i},t_{j})\) is a \(2\times 2\) matrix, for \(i=1,\ldots,10\) and \(j=1,\ldots,26\). For instance, the sixth row of \(\mathbf{C}\) indicates that the input (resp., output) transitions of place \(p_{6}\) are \(t_{3}\) and \(t_{6}\) (resp., \(t_{4}\) and \(t_{5}\)).