397.42 병렬 임무 실행의 자원 충돌 해결

다중 로봇 시스템이나 단일 로봇의 병렬 행동 실행에서, 여러 과업이 동시에 제한된 자원에 접근하려 할 때 **자원 충돌(resource conflict)**이 발생한다. 자원 충돌의 적절한 해결은 임무의 안전성과 효율성을 보장하기 위한 핵심 과제이며, 이를 위한 형식적 모델링과 해결 기법은 로봇 임무 계획의 실용적 적용에서 불가결한 요소이다.

1. 자원의 분류와 모델링

1.1 자원의 유형

로봇 임무 계획에서 다루어야 하는 자원은 다음과 같이 분류된다.

비소모성 자원(Reusable/Non-consumable Resource): 사용 후 반환되어 재사용이 가능한 자원이다. 이 자원은 동시에 사용할 수 있는 에이전트 수에 제한이 있을 수 있다.

• 통로(corridor), 작업 공간(workspace), 충전 스테이션(charging station), 통신 채널(communication channel)

소모성 자원(Consumable Resource): 사용 시 감소하며 재생되지 않거나 제한적으로 재생되는 자원이다.

• 배터리 에너지, 연료, 소모품(예: 접착제, 페인트)

단위 용량 자원(Unary Resource): 한 번에 하나의 과업에만 할당될 수 있는 자원이다.

• 특정 로봇 팔(end-effector), 도킹 포트(docking port), 공구(tool)

다중 용량 자원(Multi-capacity Resource): 동시에 제한된 수의 과업에 할당될 수 있는 자원이다.

• 대역폭 채널(동시 k개 연결 허용), 다중 충전 포트(동시 m대 충전 가능)

1.2 자원의 형식적 모델링

자원 r은 다음과 같은 형식적 기술로 정의된다.

r = (\text{id},\ C_r,\ \text{type}_r)

여기서 \text{id}는 자원 식별자, C_r은 자원의 총 용량(capacity), \text{type}_r \in \{\text{reusable},\ \text{consumable}\}는 자원 유형이다.

각 행동(과업) a가 자원 r에 대해 요구하는 자원량은 다음과 같이 정의된다.

\text{req}(a, r) \in \mathbb{R}_{\geq 0}

시간 t에서 자원 r의 사용량은 해당 시점에 실행 중인 모든 행동의 자원 요구량의 합이다.

U(r, t) = \sum_{a \in \text{active}(t)} \text{req}(a, r)

자원 충돌 조건: 임의의 시점 t에서 자원 r에 대한 충돌은 다음 조건이 만족될 때 발생한다.

U(r, t) > C_r

2. 자원 충돌 탐지 기법

2.1 자원 프로파일(Resource Profile) 분석

자원 프로파일은 시간축 위에서 각 자원의 사용량을 추적하는 함수이다. 계획 \pi_t = \{(a_1, t_1), (a_2, t_2), \ldots\}에 대해 자원 r의 프로파일 P_r(t)는 다음과 같이 정의된다.

P_r(t) = \sum_{\{a_i \mid t_i \leq t < t_i + \text{dur}(a_i)\}} \text{req}(a_i, r)

자원 프로파일에서 P_r(t) > C_r인 시간 구간이 존재하면, 해당 구간에서 자원 충돌이 발생한다. 이 분석은 계획의 유효성 검증(validation)에서 1차적으로 수행된다.

2.2 상호 배타(Mutex) 기반 탐지

GraphPlan과 같은 계획 알고리즘에서는 동일한 자원을 사용하는 행동 쌍을 사전에 상호 배타(mutex) 관계로 표시하여 충돌을 방지한다. 두 행동 a_i와 a_j가 자원 충돌 머텍스에 해당하는 조건은 다음과 같다.

\text{mutex}_r(a_i, a_j) \iff \text{req}(a_i, r) + \text{req}(a_j, r) > C_r

3. 자원 충돌 해결 전략

3.1 순서 제약 삽입(Ordering Constraint Insertion)

가장 기본적인 충돌 해결 방법은 충돌하는 두 행동 사이에 **순서 제약(ordering constraint)**을 삽입하여 동시 실행을 방지하는 것이다. 행동 a_i와 a_j가 자원 r에 대해 충돌할 때, 다음 두 가지 순서 중 하나를 선택한다.

a_i \prec a_j \quad \text{또는} \quad a_j \prec a_i

이 결정은 전체 계획의 makespan을 최소화하는 방향으로 이루어지며, 이는 유향 이접 그래프(disjunctive graph) 기반의 스케줄링 문제로 형식화된다.

유향 이접 그래프 G = (V, E_c, E_d)에서:

• V: 행동(과업) 노드의 집합
• E_c: 선행 제약(conjunctive arc)의 집합 — 반드시 유지되어야 하는 순서
• E_d: 이접 아크(disjunctive arc)의 집합 — 자원 충돌로 인해 하나의 방향을 선택해야 하는 순서

모든 이접 아크에 대해 방향을 결정하여 순환(cycle)이 없는 그래프를 생성하는 것이 스케줄링의 목표이며, makespan 최소화는 NP-hard 문제에 해당한다.

3.2 시간 이동(Temporal Shifting)

시간축 기반 계획에서는 충돌하는 행동의 시작 시점을 이동시켜 자원 충돌을 해소할 수 있다. 행동 a_j의 시작 시점 t_j를 다음 조건을 만족하도록 조정한다.

t_j \geq t_i + \text{dur}(a_i) \quad \text{(}a_i\text{가 먼저 실행되는 경우)}

이를 통해 자원 프로파일에서 충돌 구간이 제거된다. 시간 이동의 최소화는 제약 만족 문제(Constraint Satisfaction Problem, CSP) 또는 **혼합 정수 선형 프로그래밍(Mixed Integer Linear Programming, MILP)**로 정식화할 수 있다.

\min \text{makespan} \quad \text{s.t.} \quad \forall t, \forall r: \sum_{\{a_i \mid t_i \leq t < t_i + \text{dur}(a_i)\}} \text{req}(a_i, r) \leq C_r

3.3 자원 할당 최적화(Resource Allocation Optimization)

다중 용량 자원이 여러 종류 존재할 때, 과업에 대한 자원 할당 방식을 최적화하여 충돌을 최소화할 수 있다. 예를 들어, 다수의 충전 스테이션 중 어느 스테이션에 어느 로봇을 할당할 것인지를 결정하는 문제이다.

이 문제는 **할당 문제(assignment problem)**의 변형으로 모델링되며, 총 대기 시간 또는 makespan을 최소화하는 할당을 탐색한다.

\min \sum_{i,j} c_{ij} x_{ij} \quad \text{s.t.} \quad \sum_j x_{ij} = 1\ \forall i, \quad \sum_i x_{ij} \text{req}(a_i, r_j) \leq C_{r_j}\ \forall j

여기서 x_{ij} \in \{0, 1\}은 과업 a_i가 자원 r_j에 할당될 때 1이고, c_{ij}는 해당 할당의 비용이다.

3.4 우선순위 기반 해결(Priority-Based Resolution)

각 과업에 우선순위를 부여하고, 자원 충돌 발생 시 높은 우선순위의 과업에 자원을 우선 할당하는 방법이다. 우선순위 결정 기준은 다음과 같이 다양하게 설정될 수 있다.

4. 공간 자원 충돌의 특수 처리

4.1 경로 충돌(Path Conflict)

다중 이동 로봇 시스템에서 가장 빈번하게 발생하는 자원 충돌은 **경로 충돌(path conflict)**이다. 두 로봇 r_i와 r_j의 경로가 동일한 위치 v를 동일한 시간에 점유하려 할 때 충돌이 발생한다.

\text{conflict}(r_i, r_j, v, t) \iff \text{pos}(r_i, t) = v \wedge \text{pos}(r_j, t) = v

4.2 CBS(Conflict-Based Search) 알고리즘

Sharon 등(2015)이 제안한 **CBS(Conflict-Based Search)**는 다중 에이전트 경로 계획에서의 충돌을 효율적으로 해결하는 대표적 알고리즘이다. CBS는 두 단계로 구성된다.

고수준 탐색(High-Level Search): 충돌 트리(conflict tree)를 구성하며, 각 노드는 에이전트별 경로의 집합과 충돌 해소를 위한 제약의 목록을 포함한다. 충돌이 발견되면 두 개의 자식 노드를 생성하여, 각각 충돌에 관여한 두 에이전트 중 하나에 해당 시점·위치를 금지하는 제약을 추가한다.

저수준 탐색(Low-Level Search): 각 에이전트에 대해 주어진 제약 하에서 최단 경로를 계산한다. 이는 시간-공간 A*(space-time A*) 알고리즘으로 수행된다.

CBS의 최적성은 보장되며, 충돌이 적은 경우에 매우 효율적으로 동작한다.

4.3 우선순위 기반 경로 계획

우선순위 기반 경로 계획에서는 로봇에 순위를 부여하고, 높은 순위의 로봇이 먼저 경로를 계획한다. 이후의 로봇은 선행 로봇의 경로를 장애물로 간주하여 자신의 경로를 계획한다.

\text{path}(r_k) = \text{A}^*_{\text{constrained}}(s_k, g_k, \{\text{path}(r_1), \ldots, \text{path}(r_{k-1})\})

이 방법은 계산 효율이 높지만, 순위 결정에 따라 해의 품질이 크게 변동하며, 최적성이 보장되지 않는다.

5. 통신 자원 충돌

다중 로봇 시스템에서 통신 채널은 제한된 대역폭을 지닌 공유 자원이다. 다수의 로봇이 동시에 데이터를 전송하면 통신 혼잡(congestion)이 발생하여 메시지 손실이나 지연이 초래된다.

통신 자원 충돌의 해결을 위해 다음 전략들이 활용된다.

TDMA(Time Division Multiple Access) 기반 스케줄링: 각 로봇에 고정된 시간 슬롯을 할당하여 충돌 없는 통신을 보장한다. 로봇 r_i는 시간 슬롯 [(i-1) \cdot \Delta t,\ i \cdot \Delta t)에서만 전송할 수 있다.

우선순위 기반 통신: 긴급 메시지(예: 충돌 경고, 비상 정지)에 높은 우선순위를 부여하여 일반 메시지보다 먼저 전송되도록 한다. ROS2의 DDS(Data Distribution Service) 기반 QoS(Quality of Service) 정책이 이를 지원한다.

6. 에너지 자원 충돌

충전 스테이션의 수가 제한된 환경에서 다수의 로봇이 동시에 충전을 요구하면 에너지 자원 충돌이 발생한다. 이 문제는 충전 스케줄링(charging scheduling) 문제로 모델링되며, 다음 최적화 문제로 정식화된다.

\min \max_i (T_{\text{complete},i} - T_{\text{request},i}) \quad \text{s.t.} \quad \sum_{i: t \in [T_{\text{start},i},\ T_{\text{end},i})} x_{ij} \leq C_j\ \forall j, t

여기서 T_{\text{complete},i}는 로봇 i의 충전 완료 시간, T_{\text{request},i}는 충전 요청 시간, x_{ij}는 로봇 i가 충전 스테이션 j에 할당되었는지를 나타내는 이진 변수, C_j는 스테이션 j의 동시 충전 용량이다.

7. 자원 충돌 해결의 계산 복잡도

자원 충돌 해결 문제의 계산 복잡도는 자원의 유형과 제약 조건에 따라 다음과 같이 분류된다.

8. 요약

병렬 임무 실행에서의 자원 충돌 해결은 자원의 형식적 모델링, 충돌 탐지, 그리고 해결 전략의 체계적 적용을 요구하는 핵심 과제이다. 순서 제약 삽입, 시간 이동, 자원 할당 최적화, 우선순위 기반 해결 등의 전략이 주요하게 활용되며, 공간 자원 충돌에 대해서는 CBS 알고리즘이 최적 해를 보장하는 대표적 기법이다. 통신 자원과 에너지 자원의 충돌 또한 각각 특화된 스케줄링 기법으로 관리된다. 자원 충돌 해결의 대부분은 NP-hard 복잡도를 지니므로, 실제 로봇 시스템에서는 근사 알고리즘과 발견적 방법의 조합이 필수적이다.

9. 참고 문헌

• Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015). “Conflict-based search for optimal multi-agent pathfinding.” Artificial Intelligence, 219, pp. 40–66.
• Brucker, P. (2007). Scheduling Algorithms (5th ed.). Springer.
• Fox, M., & Long, D. (2003). “PDDL2.1: An extension to PDDL for expressing temporal planning domains.” Journal of Artificial Intelligence Research, 20, pp. 61–124.
• Stern, R., Sturtevant, N. R., Felner, A., Koenig, S., Ma, H., Walker, T., Li, J., Atzmon, D., Cohen, L., Kumar, T. K. S., Boyarski, E., & Barták, R. (2019). “Multi-agent pathfinding: Definitions, variants, and benchmarks.” Proceedings of the Symposium on Combinatorial Search (SoCS), pp. 151–158.
• Coles, A. J., Coles, A. I., Fox, M., & Long, D. (2010). “Forward-chaining partial-order planning.” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp. 42–49.

v1.0 | 로봇공학 서적 – Volume 9, Part 53, Chapter 397, Section 42