# Path Planning of Multi-Type Robot Systems with Time Windows Based on Timed Colored Petri Nets
## 6 Illustrative Example  
In this following, the developed approach is illustrated using an example formed with the Robot Motion Tool RMTool [48]. The static environment of the system is partitioned [47] into 74 regions, as shown in Figure 3, i.e., \(R=\{r_{1},r_{2},\ldots,r_{74}\}\). There are three different types of robots (i.e., \(|K|=3\)) working in the environment whose initial locations are marked by different colored dots in Figure 3, i.e., \(\mathcal{C}_{1}\) robot in region \(r_{16}\) (blue dot); \(\mathcal{C}_{2}\) robot in region \(r_{36}\) (purple dot); and \(\mathcal{C}_{3}\) robot in region \(r_{49}\) (brown dot). The TCPN model of the MTRS is shown in Figure 4. It consists of 74 places and 218 transitions. We assumed that the distance and the moving time between adjacent regions were equal to one, i.e., \(\mathbf{w}=[\mathbf{w}(t_{1}),\mathbf{w}(t_{2}),\ldots,\mathbf{w}(t_{218})]=\mathbf{1}_{1\times 218}\) and \(\mathbf{\theta}=[\mathbf{\theta}(t_{1}),\mathbf{\theta}(t_{2}),\ldots,\mathbf{\theta}(t_{218})]\)\(=\mathbf{1}_{1\times 218}\). For the MTRS in Figure 3, we assumed that the set of interest regions are:  
* \(R^{E}_{1}=\{r_{65},r_{69}\}\), \(R^{E}_{2}=\{r_{3}\}\), \(R^{E}_{3}=\{r_{24},r_{45}\}\);
* \(R^{S}_{1}=\{r_{10}\}\)\(R^{S}_{2}=\{r_{21}\}\), \(R^{S}_{3}=\{r_{21},r_{10}\}\);  
Figure 3: An MTRS with three different types of robots. Figure 4: The TCPN system corresponding to the MTRS in Figure 3.  
For the temporal requirement, we assumed that the task regions \(r_{69}\), \(r_{3}\), \(r_{24}\), \(r_{45}\), \(r_{21}\), \(r_{10}\), and \(r_{11}\) should be visited in the time windows \([10,12]\), \([3,5]\), \([10,15]\), \([17,25]\), \([8,22]\), \([3,8]\), and \([15,20]\), respectively. Therefore, the task requirement \(\varphi\) for the MTRS can be represented as follows:  
\[\varphi=(r_{65},E^{1}),(r_{69},E^{1},[10,12]),(r_{3},E^{2},[3,5]), (r_{24},E^{3},[10,15]),(r_{45},E^{3},[17,25]),\] \[(r_{21},S^{2},[8,22]),(r_{21},S^{3},[8,22]),(r_{10},S^{1},[3,8]),( r_{10},S^{3},[3,8]),(r_{13},A),(r_{48},A),\] \[(r_{11},J,[15,20]),(r_{37},J),(r_{68},J),\]  
which requires that task region \(r_{65}\) be visited by a \(C_{1}\) robot; task region \(r_{69}\) be visited by a \(C_{1}\) robot in the time window \([10,12]\), task region \(r_{3}\) be visited by a \(C_{2}\) robot in the time window \([3,5]\); task region \(r_{24}\) be visited by a \(C_{3}\) robot in the time window \([10,15]\); task region \(r_{45}\) be visited by a \(C_{3}\) robot in the time window \([17,25]\); task region \(r_{21}\) be visited by \(C_{2}\) and \(C_{3}\) robots in the time window \([8,22]\); task region \(r_{10}\) be visited by \(C_{1}\) and \(C_{3}\) robots in the time window \([3,8]\); task region \(r_{11}\) be visited by any type of robot in the time window \([15,20]\); tasks regions \(r_{37}\) and \(r_{68}\) be visited by any type of robot; and all robots should avoid regions \(r_{13}\) and \(r_{48}\). Note that the task regions \(r_{65}\), \(r_{37}\) and \(r_{68}\) do not have time constraints. We implemented the proposed approach by MATLAB with toolbox YALMIP (YALMIP solver (2019) [Online]. Available online: yalmip.github.io/allsolvers/, accessed on 1 August 2021.) on a laptop equipped with a 1.8 GHZ Core i5 Processor. The highest computational effort of the proposed approach was spent in solving the MILPP (15). The paths of the robots were obtained by solving Algorithm 3 as follows:  
* \(\mathbf{path_{1}}\) (Blue): \(r_{16}\to r_{71}\to r_{19}\to r_{10}\to r_{60}\to r_{63}\to r_{68}\to r_{55} \to r_{65}\to r_{57}\to r_{67}\to r_{69}\);
* \(\mathbf{path_{2}}\) (Purple): \(r_{36}\to r_{1}\to r_{5}\to r_{30}\to r_{3}\to r_{30}\to r_{5}\to r_{1}\to r_{37} \to r_{21}\);
* \(\mathbf{path_{3}}\) (Brown): \(r_{49}\to r_{52}\to r_{56}\to r_{9}\to r_{62}\to r_{61}\to r_{60}\to r_{10} \to r_{19}\to r_{71}\to r_{73}\to r_{72}\to r_{24}\to r_{29}\to r_{2}\to r_{20} \to r_{39}\to r_{11}\to r_{6}\to r_{21}\to r_{45}\). The overall CPU time for the developed approach is 23 seconds.