# Path Planning of Multi-Type Robot Systems with Time Windows Based on Timed Colored Petri Nets
## 1 Introduction  
With the increase in complexity and diversity of tasks, a single robot may not satisfy the task requirement in some industrial applications, which has led to the creation of multi-robot systems (MRSs) [1]. The main challenge for such systems is to coordinate the control and planning of multiple robots so that tasks are effectively finished. A large number of studies in the literature have been proposed to choose the optimum path trajectories for multiple robots to reach some task regions under certain requirements such as shortest travel distance, time windows, and obstacle avoidance [2; 3; 4; 5; 6; 7].  
The collaboration of multiple robots was a critical issue that has garnered much attention in recent decades. An improved particle swarm algorithm has been developed to deal with the collaborative navigation of MRSs [8]. To tackle the problem of collaborative coverage of multiple robots in complicated environments, a novel multi-robot persistent coverage strategy was proposed in [9] to take into account the environmental complexity and the differences in robot path lengths. If robots have different priorities and there are both static and dynamic obstacles in the workspace, a navigation strategy with priorities was presented [10]. To complete some collaborative tasks within time constraints, the distributed planning of robots was researched in [11; 12] to ensure that enough robots are present at the task destinations within the given time constraints. In [13], an integer linear programming method was proposed for optimizing the path trajectories of warehouse robots so that pickup and delivery points are reached within given time windows. The path planning of MRSs with complex tasks has also drawn a great deal of attention in theliterature [14; 15; 16; 17; 18; 19] in recent decades, where the tasks were expressed by Boolean formulae or linear temporal logic.  
In an MRS, the system's environment was divided into zones, and the movement of any robot from one zone to another was treated as a discrete event [20; 21; 22; 23]. Petri nets(PNs) are an efficient tool to model, analyze, and control discrete event systems [24; 25; 26; 27; 28; 29; 30; 31], such as robotics and intelligent transportation. PN can effectively avoid the state explosion problem as the number of robots increases. In [32], an MRS was modeled by a PN and an integer linear programming problem (ILPP) was provided to find the shortest path on the condition that the types of robots are identical (i.e., only one type). Owing to the restricted sensors and actuators, an optimal PN controller for MRS was devised [20] to minimize crashes when some events were indistinguishable and uncontrollable. The problem of path planning for MRSs with logic and time constraints was discussed using timed Petri nets [22], and an ILPP was established to determine the optimum paths of robots so that the task zones were visited by a robot within a given time window and the forbidden regions were always avoided.  
To finish some complex tasks cooperatively, multiple types of robots with different functions were required [33]. For instance, in many practical systems such as logistical and manufacturing systems, not all the tasks can be completed by all robots, i.e., some tasks may need specific types of robots to complete [34]. Moreover, the time factors of tasks are also crucial in real-word applications. A _multi-type robot system_ (MTRS) is a system that consists of _multi-types_ and _multi-quantities_ of robots. Therefore, path planning and task allocation are the key issues for multi-type robot systems that have received much attention in recent years. It requires to achieve a trade-off between the coordination of the robots to finish the tasks and the total cost of the system. This paper advances this research by developing an optimal path planning algorithm for multi-type robot systems with time windows.