# 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  
A timed Colored Petri net (TCPN) is a pair \((N,\mathbf{\theta})\)[44], where:  
* \(N=(P,T,Co,\mathbf{Pre},\mathbf{Post})\) is a CPN,
* \(\mathbf{\theta}(t_{j})\) is a non-negative multiset over \(Co(t_{j})\). The mapping \(\mathbf{\theta}(t_{j}):Co(t_{j})\to\mathbb{N}\) associates to each occurrence color of transition \(t_{j}\) a non-negative integer fixed firing duration. We denote by \(\mathbf{\theta}=[\mathbf{\theta}(t_{1}),\ldots,\mathbf{\theta}(t_{m})]\) the _firing delay vector_, where \(\mathbf{\theta}(t_{j})=[\mathbf{\theta}(t_{j})(1),\ldots,\mathbf{\theta}(t_{j})(v_{j})]\). We denote by \(G=\langle N,\mathbf{\theta},\mathbf{M}_{0}\rangle\) a _TCPN system_, where \(\mathbf{M}_{0}\) is an initial marking. In the following, it is assumed that the _moving environment_\(R=\{r_{1},r_{2},\ldots,r_{n}\}\) of an MTRS is divided into a set of \(n\) triangular regions that connect to each other via several predefined line segments [47]. Each type of robot can move freely inside any triangular region except the forbidden one. We model the MTRS and its working environment by a TCPN according to Algorithm 1. To illustrate the construction of a TCPN better, a simple MTRS is discussed in the following example. **Example 1**. : _Let us consider the MTRS in Figure 1. Its moving environment is divided into ten triangular regions, i.e., \(R=\{r_{1},\ldots,r_{10}\}\). Two robots with different functions are initially deployed in regions \(r_{3}\) (represented by blue circle \(\mathsf{C}_{1}\)) and \(r_{5}\) (represented by red circle \(\mathsf{C}_{2}\)), respectively, i.e., \(K=2\)._  
The TCPN system of the MTRS is shown in Figure 2. It consists of 10 places, \(P=\{p_{1},\ldots,p_{10}\}\), each of which represents a region, and 26 transitions, \(T=\{t_{1},\ldots,t_{26}\}\), each of which represents the movement of a robot from one region to an adjacent one. The description of transitions and places is presented in Table 1.  
Figure 1: A simple MTRS for examples 1 and 2. ```
0: The working environment with \(K\) robots and \(n\) regions \(R=\{r_{1},r_{2},\ldots,r_{n}\}\)
0: A TCPN system \(G=\langle N,\mathbf{\theta},\mathbf{M}_{0}\rangle\) and a distance vector \(\mathbf{w}\)
1: Let \(P=\{p_{1},\ldots,p_{n}\}\), \(T=\phi,\mathbf{Pre}=\mathbf{0},\mathbf{Post}=\mathbf{0},\mathbf{\theta}=\mathbf{0},\mathbf{M}_{0}=\mathbf{0}, \mathbf{w}=\mathbf{0},m=0\)
2: Associate each region \(r_{i}\) with a place \(p_{i}\) in the place set \(P\), i.e., each place \(p_{i}\in P\) represents a region \(r_{i}\in R\);
3:for each \(p_{i}\in P\)do
4:for each \(p_{j}\in P,j\
eq i\)do
5:if\(p_{i}\) and \(p_{j}\) are adjacent, i.e., region \(r_{i}\) and region \(r_{j}\) are adjacent then
6:\(m=m+1\);
7:\(T=T\cup\{t_{m}\}\); %transition \(t_{m}\) represents the movement from \(r_{i}\) to \(r_{j}\)
8:\(\theta(t_{m})(k)\) equals the average time for a \(C_{k}\) type of robot moving from region \(r_{i}\) to region \(r_{j}\), \(k=1,\ldots,K\);
9:\(w(t_{m})(k)\) equals the average distance for a \(C_{k}\) type of robot moving from region \(r_{i}\) to region \(r_{j}\), \(k=1,\ldots,K\);
10:\(\mathbf{Pre}(p_{i},t_{m})=\mathbf{I}_{K},\mathbf{Post}(p_{j},t_{m})=\mathbf{I}_{K}\), where \(\mathbf{I}_{k}\) denotes a \(K\times K\) identity matrix;
11:endif
12:endfor
13:endfor
14:for\(p_{i}\in P\)do
15:\(M_{0}(p_{i})(h)=\) The number of robots with color \(a_{j,h}\) initially located in region \(r_{i}\);
16:endfor
```  
**Algorithm 1**Construct the TCPN model for the multi-type robot system