學術產出-Books & Chapters in Books
Article View/Open
Publication Export
-
題名 A New Approach to Petri Net Synthesis:The Knitting Technique 作者 趙玉
D.Y. Chao
CHAO, YUH貢獻者 資訊管理學系 關鍵詞 Petri Net Synthesis
The Knitting Technique日期 2010-04 上傳時間 30-Apr-2010 12:02:42 (UTC+8) 摘要 The advantages of distributed systems are many: resource sharing, cost reduction, improved accessibility and availability, and improved performance. The distributed nature allows concurrency or parallelism, and separate components of a system can work asynchronously. Concurrency increases the computation power, but different components have to cooperate with each other to allow resource sharing. Due to the distributed nature, it is generally a very intricate problem to design a distributed system correctly and efficiently. The first step to a correct design lies in choosing the most appropriate model. The choice of which method to use for modeling concurrent systems is influenced by (1) ease of use and understanding, (2) modeling and analysis power, (3) generality, and (4) support of automation. There are various models at hand: shared variables, exchange functions, communicating sequential processes, actors, data flow, and Petri nets. Petri nets is preferred to others due to the following reasons: (1)The ability to show a precise and graphical representation, (2)The availability of machine readable descriptions, (3)The existence of analysis techniques for control aspects. (4)The capability of employing top-down design methodology, and (5)The possibility of design and analysis automation. Thus, PNs have been used for modeling and analyzing concurrent systems. The net behavior depends not only on the graphical structure, but also on the initial marking of the net. Therefore they cannot be determined by static analysis such as dependency analysis; rather, they can be obtained with reachability analysis. The size of reachability graph depends not only by the structure of the net, but also by the initial marking. In general, the larger the initial marking (i.e., more tokens are involved), the larger the reachability graph. It has been shown that the complexity of the reachability analysis of the PNs is exponential. Though such analysis methods as reachability graph, reduction and linear algebra based methods are available, they are of limited use due to their limited capacity. Another disadvantageous fact is that modification and re-analysis may have to be conducted if the analysis methods have detected some undesired properties. Therefore, it is desired to have a synthesis approach which can build up a PN systematically such that the net has following desired logical properties: boundedness, liveness, and reversibility. These properties are critical for a system to operate in a stable, deadlock-free and cyclic way. Since the PN synthesis research started in late 70`s, significant results have been developed for special classes of PNs such as marked Graphs, free-choice PNs, and safe and live PNs. Two dominant synthesis approaches for general classes of PNs are bottom-up and top-down. Bottom-up approaches start with decomposition of systems into subsystems, construct sub-PNs for subsystems, and merge these subnets to reach a final PN by sharing places, transitions, and/or elementary paths or by linking subnets. Top-down approaches begin with a first-level PN and refine the net to satisfy system specification until a certain level is reached such as refinement of transitions and places by general modules with boundedness and liveness or well-defined modules. This approach has the advantage of reducing the scope of analysis from global to local. However, the existing bottom-up approaches suffer from the difficulty to analyze the global system properties although such useful information as invariants of the global PN can be derived from those of its subnets. In the top-down approaches, there is no easy way to validate all general modules and their design is still a problem given the system specification. the other hand, many reduction rules are very much powerful in reducing PNs. Nevertheless, they are often difficult to be applied to synthesis directly. All these difficulties and problems motivate us to devise some simple but effective rules which can guide the synthesis of PNs with desired properties. The Knitting Technique (KT) is a rule-based interactive approach. It tackles the synthesis problem from a different perspective. It aims to find the fundamental constructions to build any PN. There are two advantages of KT: (1) reduction of the complexity of synthesis as an interactive tool, and (2) providing knowledge of which construction building which class of nets. It therefore opens a novel avenue to the PN analysis. Rather than refining transitions, KT generates new paths upon a PN, to produce a larger PN`. The new generations are performed in such a fashion that all reachable markings in PN remain unaffected in PN`; hence all transitions and places in PN stay live and bounded respectively. PN` is live and bounded by making the subnet of the new paths live and bounded. This notion is novel compared with other approaches and could synthesize more general PN than others. Using KT, designers start with a basic process which is modeled by a set of closed-loop sequentially-connected places and transitions with a so-called home- place marked with a certain number of tokens. The tokens may represent the num- ber of raw materials which can be present in a system each time. Then parallel,alternative, and exclusive processes or operations are added according to the sys- tem pecification. Closed loops for the operations are added according to the resources required by the operations involved. Since expansions are conducted among nodes (either transitions or places) in a global way, the knitting technique is so called. This approach is easy to use due to the simple rules, and leads to a final net which is bounded, live, conservative, consistent, and reversible. The other advantage is that the approach is easily adapted to computer implementation to perform the synthesis of PNs in a user-friendly fashion. The knitting technique is unconventional but powerful, specially practical in the field of manufacturing and robotics because it can be used to synthesize large and complex Petri nets. It may very well be the best and/or the unique method for synthesizing large and complex Petri nets. Chapter 2 presents the basic knitting rules: TT and PP rules. Based on which, new paths are from transitions to transitions or from places to places maintaining good properties. he correctness of the rules are proved by finding the invariants of the synthesized net. It is simple, yet it creates more classes of nets than most other synthesis techniques using rules. Paths generations from transitions to places or vice versa are prohibited because the straight forward application of which renders the resulting net unbounded or deadlocked. This restriction is removed in Chapter 3 a second order generation where any generation from a transition to a place must be followed by a generation from a place to a transition and vice versa. This allows more complicated classes of nets to be created, further proving the superiority of our approach. Chapter 4 presents the reduction algorithm based on the same set of synthesis rules. The algorithm takes polynomial time complexity and is very powerful in the sense that it can reduce nets where traditional methods, usually with no algorithms, could not do it. Chapter 5 further enhances the knitting technique to the synthesis of structures of sequential mutual exclusion which is essential for maintaining the fairness in resource sharing such as in flexible manufacturing systems and other distributed systems. It removes the previous restriction of disallowing IT generations among transitions exclusive to each other. Chapter 6 extends the knitting technique to general Petri nets where any arc can carry multiple weights. Chapter 7 presents the algorithm for finding the structural matrix which records the temporal relationship of processes in a Petri net. It further applies the structure matrix to derive deadlock-free conditions. Chapter 8 applies our knitting technique to a automated manufacturing system which frequently can suffer from an ill-design. 關聯 第壹版 資料類型 book/chapter dc.contributor 資訊管理學系 en dc.creator (作者) 趙玉 zh_TW dc.creator (作者) D.Y. Chao en dc.creator (作者) CHAO, YUH en dc.date (日期) 2010-04 - dc.date.accessioned 30-Apr-2010 12:02:42 (UTC+8) - dc.date.available 30-Apr-2010 12:02:42 (UTC+8) - dc.date.issued (上傳時間) 30-Apr-2010 12:02:42 (UTC+8) - dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/39225 - dc.description.abstract (摘要) The advantages of distributed systems are many: resource sharing, cost reduction, improved accessibility and availability, and improved performance. The distributed nature allows concurrency or parallelism, and separate components of a system can work asynchronously. Concurrency increases the computation power, but different components have to cooperate with each other to allow resource sharing. Due to the distributed nature, it is generally a very intricate problem to design a distributed system correctly and efficiently. The first step to a correct design lies in choosing the most appropriate model. The choice of which method to use for modeling concurrent systems is influenced by (1) ease of use and understanding, (2) modeling and analysis power, (3) generality, and (4) support of automation. There are various models at hand: shared variables, exchange functions, communicating sequential processes, actors, data flow, and Petri nets. Petri nets is preferred to others due to the following reasons: (1)The ability to show a precise and graphical representation, (2)The availability of machine readable descriptions, (3)The existence of analysis techniques for control aspects. (4)The capability of employing top-down design methodology, and (5)The possibility of design and analysis automation. Thus, PNs have been used for modeling and analyzing concurrent systems. The net behavior depends not only on the graphical structure, but also on the initial marking of the net. Therefore they cannot be determined by static analysis such as dependency analysis; rather, they can be obtained with reachability analysis. The size of reachability graph depends not only by the structure of the net, but also by the initial marking. In general, the larger the initial marking (i.e., more tokens are involved), the larger the reachability graph. It has been shown that the complexity of the reachability analysis of the PNs is exponential. Though such analysis methods as reachability graph, reduction and linear algebra based methods are available, they are of limited use due to their limited capacity. Another disadvantageous fact is that modification and re-analysis may have to be conducted if the analysis methods have detected some undesired properties. Therefore, it is desired to have a synthesis approach which can build up a PN systematically such that the net has following desired logical properties: boundedness, liveness, and reversibility. These properties are critical for a system to operate in a stable, deadlock-free and cyclic way. Since the PN synthesis research started in late 70`s, significant results have been developed for special classes of PNs such as marked Graphs, free-choice PNs, and safe and live PNs. Two dominant synthesis approaches for general classes of PNs are bottom-up and top-down. Bottom-up approaches start with decomposition of systems into subsystems, construct sub-PNs for subsystems, and merge these subnets to reach a final PN by sharing places, transitions, and/or elementary paths or by linking subnets. Top-down approaches begin with a first-level PN and refine the net to satisfy system specification until a certain level is reached such as refinement of transitions and places by general modules with boundedness and liveness or well-defined modules. This approach has the advantage of reducing the scope of analysis from global to local. However, the existing bottom-up approaches suffer from the difficulty to analyze the global system properties although such useful information as invariants of the global PN can be derived from those of its subnets. In the top-down approaches, there is no easy way to validate all general modules and their design is still a problem given the system specification. the other hand, many reduction rules are very much powerful in reducing PNs. Nevertheless, they are often difficult to be applied to synthesis directly. All these difficulties and problems motivate us to devise some simple but effective rules which can guide the synthesis of PNs with desired properties. The Knitting Technique (KT) is a rule-based interactive approach. It tackles the synthesis problem from a different perspective. It aims to find the fundamental constructions to build any PN. There are two advantages of KT: (1) reduction of the complexity of synthesis as an interactive tool, and (2) providing knowledge of which construction building which class of nets. It therefore opens a novel avenue to the PN analysis. Rather than refining transitions, KT generates new paths upon a PN, to produce a larger PN`. The new generations are performed in such a fashion that all reachable markings in PN remain unaffected in PN`; hence all transitions and places in PN stay live and bounded respectively. PN` is live and bounded by making the subnet of the new paths live and bounded. This notion is novel compared with other approaches and could synthesize more general PN than others. Using KT, designers start with a basic process which is modeled by a set of closed-loop sequentially-connected places and transitions with a so-called home- place marked with a certain number of tokens. The tokens may represent the num- ber of raw materials which can be present in a system each time. Then parallel,alternative, and exclusive processes or operations are added according to the sys- tem pecification. Closed loops for the operations are added according to the resources required by the operations involved. Since expansions are conducted among nodes (either transitions or places) in a global way, the knitting technique is so called. This approach is easy to use due to the simple rules, and leads to a final net which is bounded, live, conservative, consistent, and reversible. The other advantage is that the approach is easily adapted to computer implementation to perform the synthesis of PNs in a user-friendly fashion. The knitting technique is unconventional but powerful, specially practical in the field of manufacturing and robotics because it can be used to synthesize large and complex Petri nets. It may very well be the best and/or the unique method for synthesizing large and complex Petri nets. Chapter 2 presents the basic knitting rules: TT and PP rules. Based on which, new paths are from transitions to transitions or from places to places maintaining good properties. he correctness of the rules are proved by finding the invariants of the synthesized net. It is simple, yet it creates more classes of nets than most other synthesis techniques using rules. Paths generations from transitions to places or vice versa are prohibited because the straight forward application of which renders the resulting net unbounded or deadlocked. This restriction is removed in Chapter 3 a second order generation where any generation from a transition to a place must be followed by a generation from a place to a transition and vice versa. This allows more complicated classes of nets to be created, further proving the superiority of our approach. Chapter 4 presents the reduction algorithm based on the same set of synthesis rules. The algorithm takes polynomial time complexity and is very powerful in the sense that it can reduce nets where traditional methods, usually with no algorithms, could not do it. Chapter 5 further enhances the knitting technique to the synthesis of structures of sequential mutual exclusion which is essential for maintaining the fairness in resource sharing such as in flexible manufacturing systems and other distributed systems. It removes the previous restriction of disallowing IT generations among transitions exclusive to each other. Chapter 6 extends the knitting technique to general Petri nets where any arc can carry multiple weights. Chapter 7 presents the algorithm for finding the structural matrix which records the temporal relationship of processes in a Petri net. It further applies the structure matrix to derive deadlock-free conditions. Chapter 8 applies our knitting technique to a automated manufacturing system which frequently can suffer from an ill-design. en dc.format.extent 426534 bytes - dc.format.mimetype application/pdf - dc.language zh_TW en dc.language.iso en_US - dc.relation (關聯) 第壹版 en dc.subject (關鍵詞) Petri Net Synthesis en_US dc.subject (關鍵詞) The Knitting Technique en_US dc.title (題名) A New Approach to Petri Net Synthesis:The Knitting Technique en dc.type (資料類型) book/chapter en
