396.50 페트리넷(Petri Net) 기반 임무 모델링

1. 페트리넷의 개요

**페트리넷(Petri Net)**은 1962년 Carl Adam Petri에 의해 제안된 수학적 모델링 도구로서, 이산 사건 시스템(Discrete Event System)에서의 동시성(concurrency), 동기화(synchronization), **자원 경합(resource contention)**을 자연스럽게 표현할 수 있다. 유한 상태 머신(FSM)이 단일 제어 흐름의 순차적 행동만을 모델링할 수 있는 반면, 페트리넷은 다수의 **토큰(token)**이 동시에 흐르는 병렬 프로세스를 형식적으로 기술할 수 있다. 이러한 특성은 다중 로봇 시스템의 임무 조율, 공유 자원 관리, 병렬 과업 실행 등 복잡한 임무 관리 문제에 페트리넷을 특히 적합한 도구로 만든다.

2. 페트리넷의 형식적 정의

2.1 기본 페트리넷 구조

페트리넷 $\mathcal{N}$ 은 5-튜플(5-tuple)로 정의된다:

$\mathcal{N} = (P, T, F, W, M_0)$

여기서 각 요소는 다음과 같다:

기호	정의
$P$	유한 장소(place) 집합
$T$	유한 전이(transition) 집합, $P \cap T = \emptyset$
$F \subseteq (P \times T) \cup (T \times P)$	유향 간선(arc) 집합
$W: F \rightarrow \mathbb{N}^+$	간선 가중치(weight) 함수
$M_0: P \rightarrow \mathbb{N}_0$	초기 마킹(initial marking)

장소(place)는 원(○)으로, 전이(transition)는 직사각형(□) 또는 막대(|)로 도식화된다. 장소에는 토큰(token, ●)이 배치되며, 마킹(marking) $M: P \rightarrow \mathbb{N}_0$ 은 각 장소에 있는 토큰의 수를 나타내는 함수로서 페트리넷의 **상태(state)**를 정의한다.

2.2 전이의 활성화(Enabling)와 발화(Firing)

전이 $t \in T$ 가 마킹 $M$ 에서 **활성화(enabled)**되려면, 모든 입력 장소에 충분한 토큰이 존재해야 한다:

$t \text{ is enabled at } M \iff \forall p \in {}^{\bullet}t, \; M(p) \geq W(p, t)$

여기서 ${}^{\bullet}t = \{p \in P : (p, t) \in F\}$ 는 전이 $t$ 의 입력 장소(pre-set) 집합이다. 활성화된 전이 $t$ 가 **발화(fire)**하면, 마킹은 다음과 같이 갱신된다:

$M'(p) = M(p) - W(p, t) + W(t, p), \quad \forall p \in P$

여기서 $W(p, t)$ 는 장소 $p$ 에서 전이 $t$ 로의 간선 가중치이고, $W(t, p)$ 는 전이 $t$ 에서 장소 $p$ 로의 간선 가중치이다. 간선이 존재하지 않는 경우 가중치는 0으로 간주한다.

3. 임무 모델링에서의 페트리넷 기본 패턴

3.1 순차 실행(Sequential Execution)

임무 과업 $a_1$ 과 $a_2$ 의 순차 실행은 다음과 같이 모델링된다:

$p_{\text{ready}} \xrightarrow{t_{a_1}} p_{\text{mid}} \xrightarrow{t_{a_2}} p_{\text{done}}$

초기 마킹 $M_0(p_{\text{ready}}) = 1$ 에서 $t_{a_1}$ 이 발화하면 $p_{\text{mid}}$ 에 토큰이 이동하고, 이후 $t_{a_2}$ 가 발화하여 $p_{\text{done}}$ 에 토큰이 도착한다. 이 구조는 임무 과업 간의 선후 관계(precedence)를 자연스럽게 표현한다.

3.2 병렬 실행(Concurrent Execution)

다수의 과업을 동시에 실행하는 병렬 구조는 **포크(fork)**와 조인(join) 패턴으로 모델링된다:

포크(Fork): 하나의 전이 $t_{\text{fork}}$ 가 발화하면 다수의 출력 장소에 동시에 토큰이 생성된다:

$t_{\text{fork}}: \{p_{\text{start}}\} \rightarrow \{p_1, p_2, \ldots, p_k\}$

조인(Join): 다수의 입력 장소에 모두 토큰이 존재할 때만 전이 $t_{\text{join}}$ 이 활성화된다:

$t_{\text{join}}: \{p_1, p_2, \ldots, p_k\} \rightarrow \{p_{\text{end}}\}$

조인 전이의 활성화 조건은 $\forall i, \; M(p_i) \geq 1$ 이며, 이는 모든 병렬 과업이 완료된 후에만 다음 단계로 진행하는 동기화(synchronization) 메커니즘을 형식적으로 구현한다.

3.3 선택(Choice)과 충돌(Conflict)

동일한 입력 장소를 공유하는 다수의 전이는 충돌(conflict) 관계에 있으며, 이는 배타적 선택(exclusive choice)을 모델링한다:

${}^{\bullet}t_1 \cap {}^{\bullet}t_2 \neq \emptyset \implies t_1, t_2 \text{ are in conflict}$

충돌 관계에 있는 전이 중 하나만 발화할 수 있으므로, 이 구조는 로봇이 여러 가능한 행동 중 하나를 선택하는 **의사결정 지점(decision point)**을 나타낸다.

3.4 자원 공유(Resource Sharing)

공유 자원은 해당 자원의 가용 수량에 해당하는 토큰을 보유하는 장소로 모델링된다. 자원을 사용하는 전이는 자원 장소로부터 토큰을 소비하고, 사용 완료 후 반환한다:

$M_0(p_{\text{resource}}) = k \quad (\text{자원 수량 } k)$

전이 $t$ 가 자원을 사용하려면 $M(p_{\text{resource}}) \geq 1$ 이어야 하며, 발화 시 자원 토큰을 소비한다. 이 구조는 배터리, 통신 채널, 작업 도구 등 유한 자원의 경합 상황을 형식적으로 모델링한다.

4. 확장 페트리넷 모델

4.1 색상 페트리넷(Colored Petri Net, CPN)

**색상 페트리넷(Colored Petri Net, CPN)**은 Jensen (1987)에 의해 제안된 고수준 페트리넷으로, 토큰에 색상(color) 또는 **데이터 값(data value)**을 부여한다. CPN은 다음과 같이 정의된다:

$\mathcal{CPN} = (\Sigma_C, P, T, A, N, C, G, E, I)$

여기서 $\Sigma_C$ 는 색상 집합(color set)의 유한 집합, $C: P \rightarrow \Sigma_C$ 는 각 장소에 배정된 색상 유형, $G$ 는 각 전이의 보호 조건(guard), $E$ 는 각 간선의 표현식이다.

임무 관리에서 CPN의 이점은 다음과 같다:

특성	기본 페트리넷	CPN
토큰 구분	동질적(homogeneous)	데이터 담지(data-carrying)
로봇 식별	장소 복제 필요	토큰 색상으로 구분
매개변수화	구조 변경 필요	보호 조건으로 처리
모델 크기	인스턴스별 확장	접힌(folded) 표현

다중 로봇 임무 관리에서 각 로봇을 구분된 색상의 토큰으로 표현하면, 단일 CPN 모델로 다수의 로봇 인스턴스를 효율적으로 관리할 수 있다.

4.2 시간 페트리넷(Timed Petri Net)

**시간 페트리넷(Timed Petri Net)**은 전이 또는 장소에 시간 제약을 부여하여, 시간 의존적 임무 동작을 모델링한다. 전이 $t$ 에 시간 구간 $[a_t, b_t]$ 가 배정되면, $t$ 는 활성화된 후 최소 $a_t$ 시간이 경과해야 발화할 수 있으며, 최대 $b_t$ 시간 이내에 발화해야 한다:

$\text{FireTime}(t) \in [a_t, b_t]$

이 확장은 임무의 시간 제약 조건을 페트리넷 구조 내에 직접 인코딩하며, 데드라인(deadline) 준수 여부의 형식적 분석을 가능하게 한다.

4.3 확률적 페트리넷(Stochastic Petri Net, SPN)

**확률적 페트리넷(Stochastic Petri Net, SPN)**은 전이의 발화 시간을 확률 분포로 모델링한다. 전이 $t$ 의 발화율(firing rate) $\lambda_t$ 가 지수 분포를 따를 때:

$P(\text{FireTime}(t) \leq \tau) = 1 - e^{-\lambda_t \tau}$

SPN은 불확실한 환경에서 임무 수행 시간의 통계적 분석, 시스템 처리량(throughput) 추정, 병목 지점 식별 등에 활용된다. 다수의 로봇이 비결정적 시간에 과업을 완료하는 시나리오를 확률적으로 분석할 수 있다.

5. 페트리넷의 분석 기법

5.1 도달 가능성(Reachability) 분석

도달 가능성 분석은 초기 마킹 $M_0$ 에서 출발하여 특정 마킹 $M_f$ 에 도달할 수 있는지를 판정한다:

$M_f \in \mathcal{R}(M_0) \iff \exists \sigma = t_1 t_2 \cdots t_n : M_0 \xrightarrow{t_1} M_1 \xrightarrow{t_2} \cdots \xrightarrow{t_n} M_f$

여기서 $\mathcal{R}(M_0)$ 는 $M_0$ 에서 도달 가능한 모든 마킹의 집합이다. 임무 관리에서 이는 임무 완료 가능성, 교착 상태(deadlock) 부재, 위험 상태 미도달 등의 속성을 검증하는 데 활용된다.

5.2 불변량(Invariant) 분석

페트리넷의 구조적 속성은 발화 카운트 벡터(firing count vector) $\mathbf{x}$ 와 관입 행렬(incidence matrix) $\mathbf{A}$ 를 통해 분석된다. 관입 행렬은 다음과 같이 정의된다:

$\mathbf{A}[p, t] = W(t, p) - W(p, t)$

장소 불변량(P-invariant): 벡터 $\mathbf{y} \geq \mathbf{0}$ 가 $\mathbf{y}^{\top} \mathbf{A} = \mathbf{0}$ 을 만족하면, 대응하는 장소의 토큰 가중합은 모든 도달 가능 마킹에서 보존된다:

$\mathbf{y}^{\top} M = \mathbf{y}^{\top} M_0, \quad \forall M \in \mathcal{R}(M_0)$

이 속성은 자원 보존 법칙(예: 전체 로봇 수의 일정, 공유 자원의 총량 보존)을 형식적으로 검증하는 데 핵심적으로 활용된다.

전이 불변량(T-invariant): 벡터 $\mathbf{x} \geq \mathbf{0}$ 가 $\mathbf{A} \mathbf{x} = \mathbf{0}$ 을 만족하면, 대응하는 전이 시퀀스의 실행이 마킹을 원래 상태로 복원한다. 이는 임무의 반복적 실행 가능성(주기적 순찰 임무 등)을 분석하는 데 활용된다.

5.3 활동성(Liveness)과 유계성(Boundedness)

활동성(Liveness): 전이 $t$ 가 활동적(live)이면, 어떤 도달 가능 마킹에서도 $t$ 를 재활성화할 수 있는 발화 시퀀스가 존재한다:

$\forall M \in \mathcal{R}(M_0), \; \exists M' \in \mathcal{R}(M) : t \text{ is enabled at } M'$

모든 전이가 활동적이면 시스템에 교착 상태(deadlock)가 존재하지 않는다.

유계성(Boundedness): 장소 $p$ 가 $k$ -유계이면, 모든 도달 가능 마킹에서 $p$ 의 토큰 수가 $k$ 를 초과하지 않는다:

$\forall M \in \mathcal{R}(M_0), \; M(p) \leq k$

유계성은 시스템 자원의 유한성 보장과 버퍼 오버플로(overflow) 방지를 증명하는 데 필수적이다.

6. 로봇 임무 관리에서의 페트리넷 적용

6.1 다중 로봇 과업 조율

페트리넷은 다수의 로봇이 협력하여 임무를 수행하는 시나리오에서 동기화 제약과 자원 경합을 자연스럽게 표현한다. 예를 들어, 두 로봇 $R_1$ 과 $R_2$ 가 협력하여 물체를 운반하는 임무는 다음과 같이 모델링된다:

장소 $p_{R_1\text{ready}}$ , $p_{R_2\text{ready}}$ : 각 로봇의 준비 상태
전이 $t_{\text{lift}}$ : 두 장소 모두에 토큰이 있을 때 활성화 (동기화)
장소 $p_{\text{carrying}}$ : 협력 운반 상태

조인 전이의 활성화 조건이 자연스럽게 두 로봇의 동기화를 보장하며, 추가적인 동기화 프로토콜 없이 형식 구조 자체로 협력 행동이 보장된다.

6.2 워크플로우 기반 임무 관리

산업용 로봇의 제조 임무는 **워크플로우 넷(Workflow Net)**으로 모델링된다. 워크플로우 넷은 단일 시작 장소 $p_{\text{start}}$ 와 단일 종료 장소 $p_{\text{end}}$ 를 갖는 특수한 페트리넷으로, van der Aalst (1998)가 제안한 건전성(soundness) 속성을 검증하여 임무의 정상적 완료를 보장한다:

완료 가능성: $p_{\text{start}}$ 에 토큰을 배치하면 항상 $p_{\text{end}}$ 에 도달할 수 있다.
적정 종료: $p_{\text{end}}$ 에 토큰이 도착하면 다른 모든 장소에 토큰이 없다.
교착 부재: 어떤 전이도 영구적으로 활성화 불가능한 상태가 되지 않는다.

7. 페트리넷의 임무 관리에서의 장단점

7.1 장점

장점	설명
동시성 표현	병렬 프로세스와 동기화를 자연스럽게 모델링
자원 모델링	유한 자원의 경합과 공유를 토큰으로 직관적 표현
형식 분석	도달 가능성, 활동성, 유계성 등의 형식적 검증 가능
시각적 표현	직관적인 그래프 표현으로 시스템 동작의 시각화 지원
수학적 기반	선형 대수 기반의 구조적 분석 기법 제공

7.2 한계

상태 공간 폭발: 토큰 수와 장소 수가 증가하면 도달 가능 마킹의 수가 지수적으로 증가한다.
계층적 구조화의 어려움: 기본 페트리넷은 계층적 분해를 직접 지원하지 않으며, 계층적 페트리넷(Hierarchical Petri Net) 등 확장이 필요하다.
반응성 제한: 전이의 발화가 이산 사건에 기반하므로, 연속적 환경 변화에 대한 실시간 반응 모델링이 제한적이다.
학습 곡선: 형식적 분석 기법의 활용에 오토마타 이론과 선형 대수에 대한 이해가 요구된다.

8. 참고 문헌

Petri, C. A. (1962). Kommunikation mit Automaten. Doctoral Dissertation, Universität Hamburg.
Murata, T. (1989). “Petri Nets: Properties, Analysis and Applications.” Proceedings of the IEEE, 77(4), 541–580.
Jensen, K. (1987). “Coloured Petri Nets.” Petri Nets: Central Models and Their Properties, Lecture Notes in Computer Science, Vol. 254, Springer, 248–299.
van der Aalst, W. M. P. (1998). “The Application of Petri Nets to Workflow Management.” Journal of Circuits, Systems, and Computers, 8(1), 21–66.
Ziparo, V. A., Iocchi, L., Lima, P. U., Nardi, D., and Palamara, P. F. (2011). “Petri Net Plans: A Framework for Collaboration and Coordination in Multi-Robot Systems.” Autonomous Agents and Multi-Agent Systems, 23(3), 344–383.

본 절은 로봇공학 서적 Volume 9, Part 53, Chapter 396의 일부로 작성되었다. v1.0