Petri Net Heuristics and Intelligent Scheduling

Robot workshop scheduling, when expanded to include AGV path planning, becomes a complex combinatorial optimization problem. Graph search methods, particularly the A* algorithm, provide a foundational framework for identifying optimal schedules. This study introduces an artificial potential field (APF) method to guide the spontaneous movement of tokens in the Petri Net, allowing for a rapid approach to the target state. The team models the robotic workshop using a timed Petri Net, incorporating both path and task subnetworks. Based on the Petri Net topology, a task network potential field is designed, alongside a maximum potential difference heuristic function, for which admissibility is proven. To optimize AGV path planning, a path network potential field is further developed, culminating in a comprehensive potential difference heuristic function.

Experimental results demonstrate that the maximum potential difference heuristic function enhances the efficiency of the A* algorithm, though its performance declines with increased task and AGV numbers. The overall potential difference heuristic function, however, proves advantageous for large-scale tasks, improving search efficiency by one to two orders of magnitude. Specifically, when handling hundreds of parts, it significantly reduces completion times and achieves more optimal scheduling outcomes compared to genetic algorithms.