# Path Planning of Multi-Type Robot Systems with Time Windows Based on Timed Colored Petri Nets
## 2 Related Works  
During the past few years, there have been numerous works focusing on the task allocation and path planning problem of MTRSs. Heuristic algorithms were applied to find near optimal solutions in real time [35; 36]. In [37], an improved particle swarm optimization algorithm was used to search for the combination of robots and tasks, and the greedy algorithm was used to sort the task execution order and calculate the cost of the task execution strategy. Taking the resources required for tasks into consideration, a novel coordinated task allocation approach based on cross-entropy was presented in [38]. A comparative study between optimization-based and market-based approaches for the task allocation problem of MTRSs was discussed in [39]. In [40], an optimal task allocation solution was developed based on the mixed integer linear programming techniques. In [33], a high-level PN model called _colored Petri net_ (CPN) [41; 42] was used to model the MTRSs, where each token was associated with a color that represents the type of the robot. Then, a mixed integer linear programming problem (MILPP) was proposed to obtain the optimal sequences and paths for operating the tasks. A Petri net toolbox for multi-robot planning under uncertainty was developed in [43] to deal with multi-robot coordination problems and obtain robust, efficient, and predictable strategies.  
In this paper, the path planning problem for MTRSs with time windows is discussed by using _timed colored Petri nets_ (TCPNs). Compared with general Petri nets, colored Petri nets allow a lot of folding techniques in order to reduce the complexity of the system model. This paper focuses on a scenario in which a group of different types of mobile robots performs in a known environment that contains several tasks. We assume that there are three types of tasks in the working environment: _common_ (performed by any type of robot), _exclusive_ (performed by only a certain type of robot), and _collaborative_ (requires multi-types of robots to work cooperatively). The problem consists in finding an optimal trajectory for each robot such that all task regions are reached by one or more specified robot types within a given time window and the forbidden regions are avoided.  
The main contributions of this paper are as follows:We extend the previous works on the path planning of MTRSs (i.e., multi-type and multi-quantity of robots) by introducing time windows. In addition, the tasks to be finished are divided into three different types: common, exclusive, and collaborative.
2. An analytical approach based on integer linear programming techniques is developed so that both the time windows and the logic requirements imposed on the tasks are satisfied.
3. Simulation results are developed to show the effectiveness of the developed methodology.  
The rest of the paper is structured as follows: The basic concepts of TCPNs and the modeling framework are given in Section 3. In Section 4, the path problem of MTRSs with time windows is formally formulated. In Section 5, we develop an MILPP to solve the path planning problem. Simulation studies for the developed approach are given in Section 6. Conclusions and future work are in Section 7.