# 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
\[\mathbf{C}=\left[\begin{array}{cccccccc}\mathbf{Post}(p_{1},t_{1})&-\mathbf{Pre}(p_{1},t _{2})&-\mathbf{Pre}(p_{1},t_{1})&\mathbf{Post}(p_{1},t_{4})&\mathbf{0}_{2},\mathbf{0}_{1,2}&\bm {0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{Post}(p_{2},t_{2})\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}&\mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}&\mathbf{0}_{2,2}& \mathbf{0}_{2,2}\\ \mathbf{0}_{2,2}&\mathbf{0}_only a certain type of robot), and _collaborative_ (requires multi-types of robots to work cooperatively). We were interested in a variety of regions of the moving environment \(R^{I}\subseteq R\), particularly set \(R^{I}\), which contains four disjoint subsets \(R^{E}_{k}\), \(R^{S}_{k}\), \(R^{U}\), and \(R^{A}\) such that  
\[R^{I}=R^{E}_{k}\cup R^{S}_{k}\cup R^{U}\cup R^{A},\]  
where  
* \(R^{E}_{k}\): set of _exclusive task regions_ for \(C_{k}\) type of robot;
* \(R^{S}_{k}\): set of _collaborative task regions_ for \(C_{k}\) type of robot;
* \(R^{IL}\): set of _public task regions_ that can be visited by any type of robot;
* \(R^{A}\): set of _forbidden regions_ that all robots should always avoid. For every interest region \(r\in R^{I}\), a _state function_\(\Delta(r)\) is defined as follows:  
\[\Delta:R^{I}\rightarrow\{E^{k},S^{k},U,A\}, \tag{1}\]  
where  
* \(\Delta(r)=E^{k}\) means that the exclusive task in region \(r\) can only be performed by \(C_{k}\) type of robot;
* \(\Delta(r)=S^{k}\) means that the task in region \(r\) should be cooperatively performed by \(C_{k}\) type of robot and other types of robots, i.e., two or more robots are required to visit region \(r\);
* \(\Delta(r)=U\) means that the task in region \(r\) can be performed by any type of robot;
* \(\Delta(r)=A\) means that region \(r\) should be always avoided. Furthermore, we assumed that each task region \(r_{i}\) was associated with a time window \([e_{i},l_{i}]\) to indicate the earliest and the latest (global) time instant for visiting the task region \(r_{i}\).