SHORTEST PATH ALGORITHMS FOR PETRI NETS

Abstract

Petri net is a mathematical and graphical tool for modeling and analysing discrete event systems. This paper focuses on a driving Petri net system from a given initial state to a desired state via minimum number of operations, that is, through the shortest transition sequence which is called as the shortest path problem. Thereby, two algorithms are developed to obtain the shortest path for Petri nets. The first algorithm, namely Forward Algorithm, uses integer programming approach and makes the process start from the initial state towards the desired state. The second algorithm, namely Backward Algorithm, uses most promising state to generate the shortest path and makes the process start from the desired state back to the initial state. Proposed algorithms do not deal with the reachability tree or graph of the net under analysis and use memory only for  storing the obtained paths unlike the approaches based on the reachability tree. Moreover, the algorithms can be applied to general Petri nets without any restriction. Simulation results demonstrate that the proposed algorithms reduces the computational time and complexity significantly..    

Keywords

• Petri net, Shortest path, Algorithms

References

1. Desel, J., "Shortest paths in reachability graphs". Journal of Computer and System Sciences, 51:314–323,1995.
2. Desrochers, A. A. and Al-Jaar, R. Y. , "Applications of Petri nets in Manufacturing Systems", The Institute of Electrical Electrical and Electronics Engineers Inc., New York, 1995.
3. Kostin, A., "Reachability analysis in t-invariant- less Petri nets. IEEE Transactions on Automatic Control, 48, Issue: 6:10-19 1024, 2003.
4. Murata, T., "Petri nets: properties, analysis and applications" Proceedings of the IEEE, 77 No:4:541– 580, 1989.
5. Proth, J. and Xie, X. , "Petri Nets: A Tool for Design and Management of Manufacturing Systems. John Wiley & Sons, West Sussex, 1996.
6. Ru, Y. and C.N.Hadjicostis, "Reachability analysis for a class of petri nets , In Proceedings of IEEE Conference on Decision and Control, 2009, pp. 1261–1266, Shanghai.
7. S. Wang; M. Gan; M. Zhou; D. You, "A reduced reachability tree for a class of unbounded petri nets," in IEEE/CAA Journal of Automatica, 2, 4:345-352, 2015.
8. Y. Haoxiong and H. Yang, "Congested traffic based on ant colony algorithm for shortest path algorithm," in International Conference on Logistics, Informatics and Service Sciences (LISS),2015 , pp.1-3, July.

9. Y. Zheng; K. Hou; W. Liao and L.Yang., "The Shortest Path Algorithm Based on Petri Net," in 19th International Conference on Industrial Engineering and Engineering Management, 2013 , pp.221-229, April.
10. Apaydin-Özkan, H., “On Achieving Reachability Paths of Petri nets,” in 9th International Conference on Electrical and Electronics Engineering (ELECO), 2015, pp.724-728, November.
11. X. Ye, J. Z. and Song, X., “On reachability graphs of Petri nets”, Computers and Electrical Engineering, 29, 2:263-272, 2003.
12. M.Conforti, G.Cornuejols, G. Zambelli and Giacomo., "Integer Programming", Springer International Publishing, 2014.
13. E. Teruel, J. M. Colom, M. Silva, “Choice-free Petri nets: A model for deterministic concurrent systems with bulk services and arrivals”, IEEE Transactions on Systems, Man, and Cybernetics, 1(27): 73–83, 1997