A polynomial-complexity approach to decide the existence of a maximally permissive Petri net supervisor using elementary siphons

Zhiwu Li; Mengchu Zhou

doi:10.1109/ICNSC.2009.4919347

A polynomial-complexity approach to decide the existence of a maximally permissive Petri net supervisor using elementary siphons

Zhiwu Li, Mengchu Zhou

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

Liveness is usually enforced by designing a supervisor that is supervisory in nature disabling events which otherwise would lead to the violation of the liveness specification. The supervisor is theoretically and practically expected to be maximally permissive such that it restricts the behavior of the plant (system under control) in a least restrictive manner while the liveness specification is not violated. However, the existence of a supervisory policy that enforces liveness in an arbitrary Petri net is undecidable. Based on elementary siphons of Petri nets, we develop a polynomial complexity approach to decide the existence of a maximally permissive monitorbased liveness-enforcing Petri net supervisor for a subclass of Petri nets, S³PR that can well model a large class of flexible manufacturing systems. The results obtained in this paper are based on the computation of the set of elementary siphons and siphon composition operations in an S³PR in our previous work, which has been shown to be of polynomial complexity with respect to the size of an S³PR.

Original language	English (US)
Title of host publication	Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009
Pages	608-613
Number of pages	6
DOIs	https://doi.org/10.1109/ICNSC.2009.4919347
State	Published - Sep 21 2009
Event	2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009 - Okayama, Japan Duration: Mar 26 2009 → Mar 29 2009

Other

Other	2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009
Country/Territory	Japan
City	Okayama
Period	3/26/09 → 3/29/09

All Science Journal Classification (ASJC) codes

Computer Networks and Communications
Electrical and Electronic Engineering

Access to Document

10.1109/ICNSC.2009.4919347

Cite this

@inproceedings{b1ab6039722944818f34f2961a6a2c4b,

title = "A polynomial-complexity approach to decide the existence of a maximally permissive Petri net supervisor using elementary siphons",

abstract = "Liveness is usually enforced by designing a supervisor that is supervisory in nature disabling events which otherwise would lead to the violation of the liveness specification. The supervisor is theoretically and practically expected to be maximally permissive such that it restricts the behavior of the plant (system under control) in a least restrictive manner while the liveness specification is not violated. However, the existence of a supervisory policy that enforces liveness in an arbitrary Petri net is undecidable. Based on elementary siphons of Petri nets, we develop a polynomial complexity approach to decide the existence of a maximally permissive monitorbased liveness-enforcing Petri net supervisor for a subclass of Petri nets, S3PR that can well model a large class of flexible manufacturing systems. The results obtained in this paper are based on the computation of the set of elementary siphons and siphon composition operations in an S3PR in our previous work, which has been shown to be of polynomial complexity with respect to the size of an S3PR.",

author = "Zhiwu Li and Mengchu Zhou",

year = "2009",

month = sep,

day = "21",

doi = "10.1109/ICNSC.2009.4919347",

language = "English (US)",

isbn = "9781424434923",

pages = "608--613",

booktitle = "Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009",

note = "2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009 ; Conference date: 26-03-2009 Through 29-03-2009",

}

Li, Z & Zhou, M 2009, A polynomial-complexity approach to decide the existence of a maximally permissive Petri net supervisor using elementary siphons. in Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009., 4919347, pp. 608-613, 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009, Okayama, Japan, 3/26/09. https://doi.org/10.1109/ICNSC.2009.4919347

A polynomial-complexity approach to decide the existence of a maximally permissive Petri net supervisor using elementary siphons. / Li, Zhiwu; Zhou, Mengchu.
Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009. 2009. p. 608-613 4919347.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A polynomial-complexity approach to decide the existence of a maximally permissive Petri net supervisor using elementary siphons

AU - Li, Zhiwu

AU - Zhou, Mengchu

PY - 2009/9/21

Y1 - 2009/9/21

N2 - Liveness is usually enforced by designing a supervisor that is supervisory in nature disabling events which otherwise would lead to the violation of the liveness specification. The supervisor is theoretically and practically expected to be maximally permissive such that it restricts the behavior of the plant (system under control) in a least restrictive manner while the liveness specification is not violated. However, the existence of a supervisory policy that enforces liveness in an arbitrary Petri net is undecidable. Based on elementary siphons of Petri nets, we develop a polynomial complexity approach to decide the existence of a maximally permissive monitorbased liveness-enforcing Petri net supervisor for a subclass of Petri nets, S3PR that can well model a large class of flexible manufacturing systems. The results obtained in this paper are based on the computation of the set of elementary siphons and siphon composition operations in an S3PR in our previous work, which has been shown to be of polynomial complexity with respect to the size of an S3PR.

AB - Liveness is usually enforced by designing a supervisor that is supervisory in nature disabling events which otherwise would lead to the violation of the liveness specification. The supervisor is theoretically and practically expected to be maximally permissive such that it restricts the behavior of the plant (system under control) in a least restrictive manner while the liveness specification is not violated. However, the existence of a supervisory policy that enforces liveness in an arbitrary Petri net is undecidable. Based on elementary siphons of Petri nets, we develop a polynomial complexity approach to decide the existence of a maximally permissive monitorbased liveness-enforcing Petri net supervisor for a subclass of Petri nets, S3PR that can well model a large class of flexible manufacturing systems. The results obtained in this paper are based on the computation of the set of elementary siphons and siphon composition operations in an S3PR in our previous work, which has been shown to be of polynomial complexity with respect to the size of an S3PR.

UR - http://www.scopus.com/inward/record.url?scp=70349140520&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349140520&partnerID=8YFLogxK

U2 - 10.1109/ICNSC.2009.4919347

DO - 10.1109/ICNSC.2009.4919347

M3 - Conference contribution

AN - SCOPUS:70349140520

SN - 9781424434923

SP - 608

EP - 613

BT - Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009

T2 - 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009

Y2 - 26 March 2009 through 29 March 2009

ER -

A polynomial-complexity approach to decide the existence of a maximally permissive Petri net supervisor using elementary siphons

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this