Petri-net 200924107 오상묵 Date- 2015. 06. 05 - Written by SangMook

Index Petri-net? Example Production cell Specification Requirement Date- 2015. 06. 05 - 1 -

Petri-net? 상호 작용하는 동시 발생 구성요소를 갖는 이산사건 시스템을 모델링하고 설계할 수 있는 시각적 도구 Carl Adam Petri 상호 작용하는 동시 발생 구성요소를 갖는 이산사건 시스템을 모델링하고 설계할 수 있는 시각적 도구 동시적, 비동기적, 분산적, 병렬적, 비화정적, 확률적인 현상을 갖는 작업공정 연구에 유익한 도구 이산사건시스템의 명확한 규정, 명확한 확인, 성능평가에 대한 통일된 환경을 제공 그래프 표현이므로 FMS(Flexible Manufacturing System) 등과 같은 실시간 제어의 구현에 사용될 수 있음 페트리네트는 PLC(programmable logic controller)와 같이 여러 요소 시스템을 순서대로 동작시키고 조정할수있다. 따라서 시스템에 대한 페트리네트 모델로 부터 시뮬레ㅐ이션을 할 수 있고, 이로부터 성능 평가를 할 수있다. Date- 2015. 06. 05 - 2 -

Definition Petri-net은 5개의 원소로 구성되어 있다. N={P, T, I, O, M0} P (Place : circle) : 조건, 자원의 사용가능성 또는 공정상태 P={P1, P2, …, Pm}은 유한한 place 집합 T (Transition : bar) : 사건(event) 또는 공정(Processing)의 시작과 끝 T={t1, t2, …, tn}은 유한한 transition의 집합 I (Input function) : place로부터 transition으로의 아크(arc / arrow) O (Output function) : transition으로부터 place로의 아크 M (Marking) : 각 place에 있는 토큰의 개수 (M0 : 초기 마킹) P1 P2 P3 t1 t2 .Transition은 Place로 부터 한 개 또는 그 이상의 input과 output을 가진다. .Transition에 대한 각각의 input Place안에 적어도 하나의 토큰이 존재하면 Transition은 ENABLE 됨. .ENABLE된 transition은 fire 할 수 있다. 여기서 fire는 input place에서 하나의 토큰이 제거되고 output place로 토큰이 넘어감을 의미함. - Place가 안전(safe)하다는 것은 place안에 토큰들이 개수가 0, 1이여야 한다. - Petri net이 안전(safe)하기 위해서는 각가의 place들 모두가 safe해야 한다. Date- 2015. 06. 05 - 3 -

Rule 활성화 규칙(enabling rule) : transition의 모든 입력 place에 토큰(token)이 있을 때, transition은 활성화 (enabled)되고 점화 (fire)할 수 있다. 점화 규칙(firing rule) : 활성화된 transition이 점화하면, 모든 입력 place에서 하나의 token이 제거되고, 모든 출력 place에 하나의 토큰이 더해진다. 입력 place가 없는 transition 생성(source) transition이라 하고, 출력 place가 없는 transition을 소멸 (sink) transition이라 한다. 그러므로 생성 transition은 무조건 활성화되어 있고, 소멸 transition을 점화하는 것은 net에서 token의 소멸을 가져온다. .Transition은 Place로 부터 한 개 또는 그 이상의 input과 output을 가진다. .Transition에 대한 각각의 input Place안에 적어도 하나의 토큰이 존재하면 Transition은 ENABLE 됨. .ENABLE된 transition은 fire 할 수 있다. 여기서 fire는 input place에서 하나의 토큰이 제거되고 output place로 토큰이 넘어감을 의미함. - Place가 안전(safe)하다는 것은 place안에 토큰들이 개수가 0, 1이여야 한다. - Petri net이 안전(safe)하기 위해서는 각가의 place들 모두가 safe해야 한다. Date- 2015. 06. 05 - 4 -

Type 상 페트리네트 (Ordinary PN) : 기본 기능만을 갖는 PN 시간 페트리네트 (Timed PN) : 시간적 개념이 들어간 PN - Timed Transition PN - Timed Place PN 일반화된 페트리네트 (Generalized PN) : 즉각 및 시간지연 혼합 PN - 즉각(Immediate) transition / place - 시간지연(Timed) transition 확률 페트리네트(Stochastic PN) : 점화시간(Firing time)이 확률변수인 경우 컬러 페트리네트(Colored PN) : 다수의 부품 흐름을 용이하게 표현 가능 확장 페트리네트(Extended PN) : Sub-net 등을 사용하여 표현력 보강 .Transition은 Place로 부터 한 개 또는 그 이상의 input과 output을 가진다. .Transition에 대한 각각의 input Place안에 적어도 하나의 토큰이 존재하면 Transition은 ENABLE 됨. .ENABLE된 transition은 fire 할 수 있다. 여기서 fire는 input place에서 하나의 토큰이 제거되고 output place로 토큰이 넘어감을 의미함. - Place가 안전(safe)하다는 것은 place안에 토큰들이 개수가 0, 1이여야 한다. - Petri net이 안전(safe)하기 위해서는 각가의 place들 모두가 safe해야 한다. Date- 2015. 06. 05 - 5 -

Modeling 선행관계 공정이 어떤 특정한 순서에 의하여 진행될 때, 제약 조건을 부가하게 된다. 분산되어 있는 여러 자원 사이의 관계를 나타내 주기도 한다. 상충 또는 경합 제한된 자원을 동시에 사용 요청하는 경우로, 모두 활성화되어 있으나, 어느 하나를 점화시키면 나머지 모두는 비활성화가 된다. 경합의 조정은 결정적인 방법과 확률적인 방법이 사용된다. 동시발생 또는 병렬처리 시스템 요소들의 상호 작용 가운데 가장 흔히 발생하는 상황이다. 선행관계 공정이 어떤 특정한 순서에 의하여 진행될 때, 제약 조건을 부가하게 된다. 분산되어 있는 여러 자원 사이의 관계를 나타내 주기도 한다. 상충 또는 경합 제한된 자원을 동시에 사용 요청하는 경우로, 모두 활성화되어 있으나, 어느 하나를 점화시키면 나머지 모두는 비활성화가 된다. 경합의 조정은 결정적인 방법과 확률적인 방법이 사용된다. 동시발생 또는 병렬처리 시스템 요소들의 상호 작용 가운데 가장 흔히 발생하는 상황이다. 동기 우연 생산 시스템에서 부품들을 특정한 자원을 사용하려고 기다리고 있고, 자원은 어떤 특정한 부품을 기다리는 경우가 있다. 이러한 상황은 동기화를 함으로써 묘사된다. 합병 여러 부품들이 같은 기계에서 서비스 받을 때, 예를 들어 조립과 같은 공정을 나타내기 위해 필요한 상황이다. 혼란 동시발생과 경합이 공존하는 상태이다. 우선순위 : 공정의 순서상, 또는 경합의 조정 등의 조작을 위하여 점화 순서를 임의로 조작하는 경우다. Date- 2015. 06. 05 - 6 -

Modeling 동기 우연 생산 시스템에서 부품들을 특정한 자원을 사용하려고 기다리고 있고, 자원은 어떤 특정한 부품을 기다리는 경우가 있다. 이러한 상황은 동기화를 함으로써 묘사된다. 합병 여러 부품들이 같은 기계에서 서비스 받을 때, 예를 들어 조립과 같은 공정을 나타내기 위해 필요한 상황이다. 혼란 동시발생과 경합이 공존하는 상태이다. 우선순위 공정의 순서상, 또는 경합의 조정 등의 조작을 위하여 점화 순서를 임의로 조작하는 경우다. 선행관계 공정이 어떤 특정한 순서에 의하여 진행될 때, 제약 조건을 부가하게 된다. 분산되어 있는 여러 자원 사이의 관계를 나타내 주기도 한다. 상충 또는 경합 제한된 자원을 동시에 사용 요청하는 경우로, 모두 활성화되어 있으나, 어느 하나를 점화시키면 나머지 모두는 비활성화가 된다. 경합의 조정은 결정적인 방법과 확률적인 방법이 사용된다. 동시발생 또는 병렬처리 시스템 요소들의 상호 작용 가운데 가장 흔히 발생하는 상황이다. 동기 우연 생산 시스템에서 부품들을 특정한 자원을 사용하려고 기다리고 있고, 자원은 어떤 특정한 부품을 기다리는 경우가 있다. 이러한 상황은 동기화를 함으로써 묘사된다. 합병 여러 부품들이 같은 기계에서 서비스 받을 때, 예를 들어 조립과 같은 공정을 나타내기 위해 필요한 상황이다. 혼란 동시발생과 경합이 공존하는 상태이다. 우선순위 : 공정의 순서상, 또는 경합의 조정 등의 조작을 위하여 점화 순서를 임의로 조작하는 경우다. Date- 2015. 06. 05 - 7 -

Example P={ p1, p2, p3 } T={ t1, t2 } I{ p1, t1 } = I{ p2, t1 } = I{ p3, t2 } =1 I{ p3, t1 } = I{ p1, t2 } = I{ p2, t2 } =0 I{ p1, t1 } I{ p1, t2 } 1 0 I(P, T) = I{ p2, t1 } I{ p2, t2 } = 1 0 I{ p3, t1 } I{ p3, t2 } 0 1 P1 P2 P3 t1 t2 .Transition은 Place로 부터 한 개 또는 그 이상의 input과 output을 가진다. .Transition에 대한 각각의 input Place안에 적어도 하나의 토큰이 존재하면 Transition은 ENABLE 됨. .ENABLE된 transition은 fire 할 수 있다. 여기서 fire는 input place에서 하나의 토큰이 제거되고 output place로 토큰이 넘어감을 의미함. - Place가 안전(safe)하다는 것은 place안에 토큰들이 개수가 0, 1이여야 한다. - Petri net이 안전(safe)하기 위해서는 각가의 place들 모두가 safe해야 한다. Date- 2015. 06. 05 - 8 -

Example P={ p1, p2, p3 } T={ t1, t2 } O{ p1, t2 } = O{ p2, t2 } = O{ p3, t1} =1 O{ p3, t2 } = O{ p1, t1 } = O{ p2, t1 } =0 O{ p1, t1 } O{ p1, t2 } 0 1 O(P, T) = O{ p2, t1 } O{ p2, t2 } = 0 1 O{ p3, t1 } O{ p3, t2 } 1 0 P1 P2 P3 t1 t2 .Transition은 Place로 부터 한 개 또는 그 이상의 input과 output을 가진다. .Transition에 대한 각각의 input Place안에 적어도 하나의 토큰이 존재하면 Transition은 ENABLE 됨. .ENABLE된 transition은 fire 할 수 있다. 여기서 fire는 input place에서 하나의 토큰이 제거되고 output place로 토큰이 넘어감을 의미함. - Place가 안전(safe)하다는 것은 place안에 토큰들이 개수가 0, 1이여야 한다. - Petri net이 안전(safe)하기 위해서는 각가의 place들 모두가 safe해야 한다. Date- 2015. 06. 05 - 9 -

Example P={ p1, p2, p3 } T={ t1, t2 } 1 M0 = 1 0 enabling rule M( P ) ≥ I( P, t1 ) 이므로 1 1 M0 = 1 ≥ 1 = I( p, t1 ) 점화 가능 0 0 1 0 M0 = 1 ≠ 0 = I( p, t2 ) 점화 불가능 0 1 P1 P2 P3 t1 t2 활성화 규칙(enabling rule) : transition의 모든 입력 place에 토큰(token)이 있을 때, transition은 활성화 (enabled)되고 점화 (fire)할 수 있다. Date- 2015. 06. 05 - 10 -

Example P={ p1, p2, p3 } T={ t1, t2 } t1에 대한 점화법칙을 사용하면 M1 = M0 + O( P, t1 ) – I( P, t1 ) 1 0 1 0 M1 = 1 + 0 - 1 = 0 0 1 0 1 0 0 M1 = 0 ≥ 0 = I( P, t2 ) t2는 활성화 가능 1 1 P1 P2 P3 t1 t2 점화 규칙(firing rule) : 활성화된 transition이 점화하면, 모든 입력 place에서 하나의 token이 제거되고, 모든 출력 place에 하나의 토큰이 더해진다. Date- 2015. 06. 05 - 11 -

Example P={ p1, p2, p3 } T={ t1, t2 } 다시 활성화 법칙을 사용하면 0 1 M1 = 0 ≠ 1 = I( P, t1 ) t1은 활성화되지 않음 1 0 t2에 대하여 점화법칙을 사용하면 0 1 0 1 M1 = 0 + 1 - 0 = 1 1 0 1 0 P1 P2 P3 t1 t2 활성화 규칙(enabling rule) : transition의 모든 입력 place에 토큰(token)이 있을 때, transition은 활성화 (enabled)되고 점화 (fire)할 수 있다. 점화 규칙(firing rule) : 활성화된 transition이 점화하면, 모든 입력 place에서 하나의 token이 제거되고, 모든 출력 place에 하나의 토큰이 더해진다. Date- 2015. 06. 05 - 12 -

Example 사건 발생 행렬(Incidence Matrix) 사건 발생 행렬은 token 분포에 대한 정보를 제공하는 역할을 한다. C = C( P, T ) = O( P, T ) – I( P, T ) Mk = Mk-1 + Cuk, k = 1, 2, 3, … k-1 번째 marking은 제어벡터 uk에 의하여 k번째 marking으로 상태전이 한다. Uk는 k-1번째 marking에서 k번째 marking으로 상태전이 함에 있어 점화한 transition에 해당하는 요소만이 1의 값을 갖고 나머지 요소들은 0이다. P1 P2 P3 t1 t2 Date- 2015. 06. 05 - 13 -

Example 도달 가능 tree에서 각 node를 나타내는 marking은 다음과 같은 회기 방정식으로 표현이 가능하다. M1 = M0 + Cu1 M2 = M1 + Cu2 = M0 + C( u1+ u2 ) ……… Md = M0 + Cfd, d = 1, 2, 3, … 제어 벡터의 확장 개념인 점화 횟수 벡터 fd는 각 요소가 해당 transition의 점화 횟수를 나타내고 있다. 𝒌=𝟏 𝒅 𝒖𝒌 = fd P1 P2 P3 t1 t2 Date- 2015. 06. 05 - 14 -

Example C( P, T ) = - = k=1 일 때 u1 = t1을 점화하면 M1 = + = + = 1 0 0 1 1 0 0 1 -1 1 1 -1 0 1 1 0 P1 P2 P3 t1 1 1 t2 1 1 -1 1 1 -1 1 -1 1 1 1 Date- 2015. 06. 05 - 15 -

Example C( P, T ) = - = k=2 일 때 u1 = t2를 점화하면 M2 = + = + = 1 0 0 1 1 0 0 1 -1 1 1 -1 0 1 1 0 P1 P2 P3 t1 1 t2 1 1 -1 1 1 -1 1 1 -1 1 1 Date- 2015. 06. 05 - 16 -

Example C( P, T ) = - = d=2, Md =M0 + Cf2, f2 = u1 + u2 = M2 = + = 1 0 1 0 0 1 -1 1 1 -1 0 1 1 0 P1 P2 P3 t1 1 1 -1 1 1 -1 1 t2 1 Date- 2015. 06. 05 - 17 -

Production Cell Date- 2015. 06. 05 - 18 -

Production Cell Deposit belt Arm 2 Traveling crane Robot Press Arm 1 Feed belt Elevating rotary table Date- 2015. 06. 05 - 19 -

Specification Feed belt I( p1, t1 ) = 1 I( p2, t1 ) = 0 I( P, T ) = = O( p1, t1 ) = 0 O( p2, t1 ) = 1 O( P, T ) = = P1 I( p1, t1) I( p2, t1) 1 O( p1, t1) O( p2, t1) 1 t1 P2 1 M0 = t1 점화가능 앞에서 말한 대로 식을 세우면 I는 저렇게 O는 저렇게 구성 T1에 점화법칙을 적용하면 결과가 저렇게 나옴. M1 = M0 + O( P, t1 ) – I( P, t1 ) 1 1 1 1 M1 = + – = Date- 2015. 06. 05 - 20 -

Specification Elevating rotary table I( p2, t2 ) = 1 I( p3, t2 ) = 0 O( p2, t2 ) = 0 O( p3, t2 ) = 1 O( P, T ) = = I( p2, t2) I( p3, t2) 1 O( p2, t2) O( p3, t2) 1 Elevating rotary table P2 1 t2 M0 = t2는 점화 가능 M1 = M0 + O( P, t2 ) – I( P, t2 ) 앞에서 말한 대로 식을 세우면 I는 저렇게 O는 저렇게 구성 T1에 점화법칙을 적용하면 결과가 저렇게 나옴. P3 1 1 1 1 M1 = + – = Date- 2015. 06. 05 - 21 -

Specification Robot I( p4, t2 ) = I( p3, t3 ) = I( p5, t3 ) = 1 Arm 2 P4 I( p3, t2 ) I( p3, t3 ) I( p4, t2 ) I( p4, t3 ) I( p5, t2 ) I( p5, t3 ) t2 I ( P, T ) = Elevating rotary table 0 1 1 0 P3 P5 Arm 1 = P2 t3 P6는 디포짓벨트인데 현재 포커스는 로봇으로써 값을 주는것에는 상관이 없기 때문에 계산에서 생략한다. P3, p5가 팔이고 P4는 프레스이다. P6 Date- 2015. 06. 05 - 22 -

Specification Robot O( p4, t2 ) = O( p3, t3 ) = O( p5, t3 ) = 0 Arm 2 O( p3, t2 ) O( p3, t3 ) O( p4, t2 ) O( p4, t3 ) O( p5, t2 ) O( p5, t3 ) 1 0 0 1 O( P, T ) = = 1 0` Arm 1 t2는 점화가능 t3는 점화불가능 P2 M0 = 점화규칙에 의거하여 Date- 2015. 06. 05 - 23 -

Specification Robot t3에 대하여 점화법칙을 사용하면 M1 = M0 + O( P, t2 ) – I( P, t2 ) Arm 2 0 1 1 0 I ( P, T ) = 1 0` 1 1` 1 0` 1 1` Arm 1 M1 = + - = = I( P, t2 ) t3는 활성화 P2 1 1` 1 0` 1 1` 1 0` t3는 활성화 t2은 비활성화 이다. 여기서 다시 t3에 대하여 점화법칙을 사용하면 다시 복귀함. M1 = + - = Date- 2015. 06. 05 - 24 -

Specification Press I( p4, t2 ) = 1 I( p5, t2 ) = 0 I( P, T ) = = O( p4, t2 ) = 0 O( p5, t2 ) = 1 O( P, T ) = = I( p4, t2) I( p5, t2) 1 O( p4, t2) O( p5, t2) 1 P4 1 M0 = t2 점화가능 t2 P2 M1 = M0 + O( P, t2 ) – I( P, t2 ) 1 1 1 1 M1 = + – = t3는 활성화 t2은 비활성화 이다. 여기서 다시 t3에 대하여 점화법칙을 사용하면 다시 복귀함. P5 Date- 2015. 06. 05 - 25 -

Specification Deposit belt I( p6, t4 ) = 1 I( p7, t4 ) = 0 O( p6, t4 ) = 0 O( p7, t4 ) = 1 O( P, T ) = = I( p6, t4) I( p7, t4) 1 O( p6, t4) O( p7, t4) 1 p6 t4 P2 1 M0 = t4 점화가능 t3는 활성화 t2은 비활성화 이다. 여기서 다시 t3에 대하여 점화법칙을 사용하면 다시 복귀함. p7 M1 = M0 + O( P, t4 ) – I( P, t4 ) 1 1 1 1 M1 = + – = Date- 2015. 06. 05 - 26 -

Specification Traveling crane I( p7, t5 ) = 1 I( p8, t5 ) = 0 O( p7, t5 ) = 0 O( p8, t5 ) = 1 O( P, T ) = = I( p7, t5) I( p8, t5) 1 O( p7, t5) O( p8, t5) 1 p7 1 M0 = t5 점화가능 t5 P2 M1 = M0 + O( P, t5 ) – I( P, t5 ) 1 1 1 1 M1 = + – = t3는 활성화 t2은 비활성화 이다. 여기서 다시 t3에 대하여 점화법칙을 사용하면 다시 복귀함. p8 Date- 2015. 06. 05 - 27 -

Specification 전체를 묶어서 표현해야 함. t6 P1 P4 t1 t2 P2 p8 P5 P3 P2 t2 t5 t3 전체를 묶어서 표현해야 함. P6 p7 Date- 2015. 06. 05 - 28 -

Requirements 로봇은 시계 방향으로는 회전이 불가하다. 로봇 팔의 길이는 유동적이다. Elevating rotary table은 시계방향으로 회전한다. Crane의 경우 중간에 방향을 변경할 수 없다. Arm1이 feed belt로부터 물건을 받을 때, Arm2는 동시에 press로부터 물건을 받는다. 요구사항 대충 단점이랑 보완사항 및 다른ppt참고 Date- 2015. 06. 05 - 29 -

Limit 토큰에 특색이 없고 너무 단순해서 복잡한 시스템을 명시하기에 어려움이 있음 token에 특성(색)을 부여하여 약간 해결 가능(Colored Petri Net) 일반적으로 비결정적인 특징에 의해 selection부분을 명시하기에 불가능 if then else 표현이 필요함. 이에 여러 개의 net으로 분리하여 고려할 수도 있음 Real-Time 시스템에서 타이밍 문제도 있음 이 한계점에 시간의 특성들을 부여한 timed petri net도 존재함 여기까지 Date- 2015. 06. 05 - 30 -

Thank you -END -