University of Illinois Urbana-Champaign

On the convexity of right-closed sets and its application to liveness enforcement in Petri Nets

Salimi, Ehsan

Content Files
SALIMI-DISSERTATION-2015.pdf

Permalink

https://hdl.handle.net/2142/88056

Description

Title
On the convexity of right-closed sets and its application to liveness enforcement in Petri Nets
Author(s)
Salimi, Ehsan
Issue Date
2015-07-16
Director of Research (if dissertation) or Advisor (if thesis)
Sreenivas, Ramavarapu S.
Doctoral Committee Chair(s)
Sreenivas, Ramavarapu S.
Committee Member(s)
  • Basar, Tamer
  • Nagi, Rakesh
  • Beck, Carolyn L.
  • Kiyavash, Negar
Department of Study
Industrial&Enterprise Sys Eng
Discipline
Industrial Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2015-09-29T20:38:30Z
Keyword(s)
  • Right-closed set
  • convexity
  • integer convexity
  • polyhedral theory
  • Petri Nets
  • Liveness
Abstract
A set of n-dimensional integral vectors, Nn, is said to be right-closed if for any x 2 , any vector y x also belongs to it. An integral-set Nn is convex if and only if there is a convex set C Rn such that = Int(C), where Int( ) denotes the integral points in the set argument. In this dissertation, we show that the problem of verifying convexity of a right-closed set is decidable. Following this, we present a polynomial time, LP-based algorithm, for verifying the convexity of a right-closed set of integral vectors, when the dimension n is xed. This result is to be viewed against the backdrop of the fact that checking the convexity of a real-valued, geometric set can only be accomplished in an approximate sense; and, the fact that most algorithms involving sets of real-valued vectors do not apply directly to their integral counterparts. Also, we discuss a grid-search based algorithm for verifying the convexity of such a set, although not a polynomial time procedure, it is a method that veri es the convexity of right-closed sets in a reasonable time complexity. On the application side, right-closed sets feature in the synthesis of Liveness Enforcing Supervisory Policies (LESPs) for a large family of Petri Nets (PNs). For any PN structure N from this family, the set of initial markings, (N), for which there is a LESP, is right-closed. A LESP determines the transitions of a PN that are to be permitted to re at any marking in such a manner that, irrespective of the past, every transition can be red at some marking in the future. A system that is modeled by a live PN does not experience livelocks, which serves as the motivation for investigating implementation paradigms for LESPs in practice. If a transition is prevented from ring at a marking by a LESP, and all LESPs, irrespective of the implementation-paradigm that is chosen, prescribe the same control for the marking, then it is a minimally restrictive LESP. It is possible to synthesize the minimally restrictive LESP for any instance N of the aforementioned family that uses the right-closed set of markings (N). The literature also contains an implementation paradigm called invariant-based monitors for liveness enforcement in PNs. This paradigm is popular due to the fact that the resulting supervisor can be directly incorporated into the semantics of the PN model of the controlled system. In this work, we show that there is an invariant-based monitor that is equivalent to the minimally restrictive LESP that uses the right-closed set (N) if and only if (N) is convex. This result serves as the motivation behind exploring the convexity of right-closed sets.
Graduation Semester
2015-8
Type of Resource
text
Permalink
http://hdl.handle.net/2142/88056
Copyright and License Information
Copyright 2015 Ehsan Salimi

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Industrial and Enterprise Systems Engineering