On Multi-step Look-ahead Deadlock Prediction Method Of Automated Manufacturing Systems Based On Petri Nets

Discrete Event Systems(DESs)can describe many phenomena and processes in industrial practice,and they are event-driven dynamic systems.Constraints can be set in a system design to ensure that the system enters the expected state and completes specific goals and tasks.Automated Manufacturing Systems(AMSs),the research object of this thesis,fall into DESs because of their event-driven characteristics.In production practice,AMSs are composed of multiple different subsystems or modules,which will compete for limited resources in the systems.Unreasonable resource allocation will easily lead to deadlocks,the occurrence of deadlocks may cause the system to fail to achieve the expected goals,and thus deadlock control is the first task of AMSs design.In this thesis,a graphical and mathematical tool Petri nets is selected to model AMSs.The deadlock analysis of the Petri net is used to obtain the system deadlock control policy.The deadlock analysis methods of Petri nets are mainly based on the structure or reachability graph of the model.These two deadlock analysis methods have their own advantages and disadvantages.This thesis combines reachability graph analysis and siphon theory,and adopts a multi-step look-ahead deadlock prediction method to obtain the optimal deadlock avoidance policy of system.The multi-step look-ahead deadlock prediction method is a dynamic method to detect the deadlock of the system.The system fires a certain length of transition sequence(length is the number of steps for deadlock prediction)to detect whether a deadlock occurs in the reachable state.Determining the number of steps for deadlock prediction requires the calculation of markings in the dead zone without strict minimal siphon being emptied.Existing multi-step look-ahead deadlock prediction methods need to calculate the complete reachability graph,and then divide the reachability graph into the dead zone and live zone.This type of marking is calculated from the dead zone.For large-scale models,it is difficult to calculate this type of marking using the calculation method.Aiming at the shortcomings of the existing multi-step look-ahead deadlock prediction methods,this thesis mainly proposes the following work:(1)When using the multi-step look-ahead deadlock prediction method to analyze the deadlock of Petri nets,model reduction rules are used to remove the structures that are not related to the deadlock.The multi-step look-ahead deadlock prediction method and model reduction rules are combined to obtain the most optimal deadlock avoidance policy.Reduction rules are used to simplify the structure that has nothing to do with the system deadlock.The number of steps required for deadlock prediction is calculated by the simplified model.The use of model reduction rule reduces the complexity of the structure,effectively reduces the number of reachable markings,and improves the efficiency of calculating the markings in dead zone without strict minimal siphon being emptied.(2)To avoid calculating a complete reachability graph for the multi-step look-ahead deadlock prediction method,this thesis proposes to use the branch and bound method and the integer linear programming method to obtain the dead markings of the model.Calculating the markings in the dead zone without strict minimal siphon being emptied only needs to calculate the dead zone markings.This calculation method avoids calculating the complete reachable graph,narrows the search range and improves the calculation efficiency.(3)Some non-shared resources in a Petri net model are not related to system deadlock.Removing these resources during Petri net deadlock analysis can simplify the analysis process.Although removing these resources does not affect the system deadlock,it changes the number of steps required for multi-step forward deadlock prediction.In this research,the synchronous machine method in automata theory is used to calculate the number of steps required for the deadlock prediction of the original model from the simplified model.The purpose of analyzing and calculating the simplified model to obtain the optimal deadlock avoidance policy of the original model is achieved.