# Path Planning of Multi-Type Robot Systems with Time Windows Based on Timed Colored Petri Nets
## 5 Path Planning for MTRSs Based on TCPNs
### Transformation of Logic Constraints and Time Windows for Exclusive Tasks and Collaborative Tasks  
In the rest of the paper, we denote the total number of tasks to be completed by \(|task|\). Each marking \(\mathbf{M}\) of the TCPN represents the intermediate positions of all robots. According to Algorithm 1, each task can be represented by a reachable marking of the TCPN. In another word, completing the tasks of the MTRSs corresponds to some specific markings of the TCPN. Therefore, there are at most \(|task|\) intermediate markings for the TCPN to finish all tasks, i.e. :  
\[\mathbf{M}_{j}=\mathbf{M}_{j-1}+\mathbf{C}\cdot\mathbf{\sigma}_{j},\ j=1,\ldots,|task| \tag{4}\]  
where \(\mathbf{\sigma}_{j}=[\mathbf{\sigma}_{j}(t_{1}),\mathbf{\sigma}_{j}(t_{2}),\ldots,\mathbf{ \sigma}_{j}(t_{m})]^{T}\) is the firing count vector from \(\mathbf{M}_{j-1}\) to \(\mathbf{M}_{j}\). In other words, vector \(\mathbf{\sigma}_{j}\) represents all the movements of the MTRS from state \(\mathbf{M}_{j-1}\) to state \(\mathbf{M}_{j}\). The _exclusive tasks_ refer to those that can only be completed by a specific type of robot in exclusive regions. Only a \(C_{k}\) robot can visit an exclusive task region \(r_{q}\in R_{k}^{E}\). To fulfill this logic requirement, the following constraint should be satisfied:  
\[\left\{ \begin{array}{l}z_{q,k,j}-1\leq M_{j}(p_{q})(k)\cdot H\\ 1-z_{q,k,j}\leq M_{j}(p_{q})(k)\cdot H\\ \sum\limits_{j=1}^{|task|}z_{q,k,j}\leq|task|-1\\ z_{q,k,j}\in\{0,1\}\\ j=1,\ldots,|task|\end{array} \right.\quad(a) \tag{5}\]  
where \(H\in\mathbb{R}_{\geq 0}\) is a large enough number. Proof. : If \(z_{q,k,j}=1\) holds, then constraint \((5a)\) can be simplified as follows:  
\[0\leq M_{j}(p_{q})(k)\cdot H \tag{6}\]  
Since \(H\) is a large enough number and \(M_{j}(p_{q})(k)\) is a non-negative integer, constraint \((6)\) becomes redundant. On the other hand, when \(z_{q,k,j}=0\) holds, constraint \((5a)\) can be simplified as follows:  
\[1\leq M_{j}(p_{q})(k)\cdot H \tag{7}\]  
which is equivalent to \(M_{j}(p_{q})(k)\geq 1\). This condition indicates that the exclusive task region \(r_{q}\in R_{k}^{E}\) is visited by a \(C_{k}\) robot at marking \(M_{j}\). Since \(z_{q,k,j}\in\{0,1\}\) is a binary variable, constraint \((5b)\) guarantees that at least one variable \(z_{q,k,j}\) (\(j=1,\ldots,|task|\)) is equal to zero. As a consequence, the exclusive task region \(r_{q}\) will be visited by a \(C_{k}\) robot at marking \(M_{j}\) at least once. For the time window \([e_{q},l_{q}]\) imposed on an exclusive task region \(r_{q}\in R_{k}^{E}\), it can be converted into a linear constraint as follows:  
\[\left\{ \begin{array}{l}z_{q,k,j}-1\leq M_{j}(p_{q})(k)\cdot H\\ 1-z_{q,k,j}\leq M_{j}(p_{q})(k)\cdot H\\ \sum\limits_{j=1}^{|task|}z_{q,k,j}\leq|task|-1\\ z_{q,k,j}\in\{0,1\}\\ \tau_{k,j}=\tau_{k,j-1}+\mathbf{\theta}\cdot\mathbf{\sigma}_{j}\\ \tau_{k,0}=0\\ e_{q}-\tau_{k,j}\leq[1-M_{j}(p_{q})(k)+z_{q,k,j}]\cdot H\\ \tau_{k,j}-l_{q}\leq[1-M_{j}(p_{q})(k)+z_{q,k,j}]\cdot H\\ j=1,\ldots,|task|\end{array} \right\}\quad(a) \tag{8}\]  
where \(\mathbf{\theta}=[\mathbf{\theta}(t_{1}),\ldots,\mathbf{\theta}(t_{m})]\) denotes the firing delay vector, and \(\mathbf{\sigma}_{j}=[\mathbf{\sigma}_{j}(t_{1}),\ldots,\mathbf{\sigma}_{j}(t_{m})]^{T}\) denotes the firing count vector of all types of robots from \(M_{j-1}\) to \(M_{j}\). Parameter \(\tau_{k,j}\in\mathbb{R}_{\geq 0}\) represents the time instant when a \(C_{k}\) robot arrives at marking \(M_{j}\). Proof. : According to Equation (5), condition \((8a)\) ensures the logic requirement for the exclusive tasks. If a \(C_{k}\) robot visits the exclusive task region \(r_{q}\) at any marking \(M_{j}\) (\(j=1,\ldots,|task|\)), i.e., \(z_{q,k,j}=0\) and \(M_{j}(p_{q})(k)=1\), the third and fourth constraints of \((8b)\) can be simplified as follows:  
\[\left\{ \begin{array}{l}e_{q}-\tau_{k,j}\leq 0\\ \tau_{k,j}-l_{q}\leq 0\end{array}