1291.24 다중 로봇 시스템에서 상태 머신의 한계 사례

1. 다중 로봇 시스템의 행동 제어와 상태 머신의 구조적 부적합성

다중 로봇 시스템(Multi-Robot System, MRS)은 둘 이상의 로봇 에이전트가 공유 환경에서 독립적 또는 협력적으로 임무를 수행하는 체계이다. MRS의 행동 제어는 개별 로봇의 국소적 행동 관리에 더하여, 로봇 간 조정(coordination), 임무 할당(task allocation), 충돌 회피(collision avoidance), 형성 제어(formation control), 합의(consensus) 등 시스템 수준의 복합적 행동 관리를 필수적으로 요구한다.

유한 상태 머신(Finite State Machine, FSM)은 단일 에이전트의 순차적 행동 제어에는 적합하나, MRS가 본질적으로 내포하는 다차원적 병행성, 동적 구성 변경, 이종 에이전트 간 협업, 비동기적 통신 등의 특성에 대하여 구조적 한계를 노출한다. 이러한 한계는 로봇의 수가 증가함에 따라 비선형적으로 심화되며, 실용적 규모의 MRS에서 FSM 기반 설계를 사실상 불가능하게 만드는 근본 원인이 된다.

2. 상태 공간의 조합적 폭증

2.1 중앙 집중식 FSM의 상태 공간 분석

MRS 전체를 단일 FSM으로 모델링하는 중앙 집중식(centralized) 접근에서, N대의 로봇이 각각 s개의 개별 상태를 보유하면, 시스템 전체의 상태 공간 크기는 직곱(Cartesian product)에 의하여 s^N으로 결정된다. 이는 로봇 수 N에 대하여 지수적(exponential)으로 증가하므로, 소규모 시스템에서조차 비실용적 규모의 상태 수를 생성한다.

위 표에서 확인되듯, 로봇당 상태 수 s = 10인 비교적 단순한 모델에서도 로봇 수 N = 10이면 시스템 상태 수는 10^{10}에 달한다. 이는 상태 전이 함수의 명시적 정의가 물리적으로 불가능한 규모이다.

2.2 로봇 간 조정 상태에 의한 추가 차원

로봇 간 조정이 요구되는 경우, 조정 관계의 상태가 시스템 상태 공간에 추가 차원으로 작용한다. N대의 로봇이 형성하는 로봇 쌍(pair)의 수는 \binom{N}{2} = \frac{N(N-1)}{2}이며, 각 쌍이 c개의 조정 상태(예: 독립 수행, 협업 중, 충돌 회피 중, 상호 대기)를 보유하면, 조정 상태 공간의 크기는 c^{\binom{N}{2}}이다.

N = 5, c = 3일 때, 조정 상태 수는 3^{10} = 59{,}049이다. 이 수치가 개별 로봇 상태의 직곱 s^N에 곱해지므로, 전체 시스템 상태 공간의 크기는 다음과 같다:

\lvert S_{\text{total}} \rvert = s^N \cdot c^{\binom{N}{2}}

N = 5, s = 10, c = 3의 조건에서 \lvert S_{\text{total}} \rvert = 100{,}000 \times 59{,}049 = 5{,}904{,}900{,}000이 됨에 따라, 상태 전이 테이블의 완전한 명세는 현실적으로 불가능하다.

3. 사례 1: 협업 탐색 임무에서의 상태 머신 한계

3.1 임무 시나리오 정의

3대의 자율 이동 로봇이 미지의 실내 환경을 분할 탐색(area partitioning exploration)하는 임무를 수행한다. 각 로봇은 독립적으로 SLAM(Simultaneous Localization and Mapping)을 수행하되, 탐색한 지도 정보를 타 로봇과 공유하고, 미탐색 영역의 중복 방문을 최소화하기 위하여 탐색 전방(frontier)의 동적 재할당을 실행한다.

3.2 FSM에 의한 설계의 구조적 한계

탐색 전방 할당의 상태 표현 문제. 환경 내 미탐색 전방의 수를 F라 하면, 3대의 로봇에 대한 전방 할당 조합의 수는 3^F이다. 전방의 수가 임무 진행에 따라 동적으로 변화하므로, 할당 상태를 FSM의 이산 상태로 정적 정의하는 것 자체가 불가능하다. 새로운 전방이 발견될 때마다 FSM의 상태 집합과 전이 함수를 재정의하여야 하며, 이는 FSM의 정적 구조와 근본적으로 상충한다.

지도 정보 공유에 따른 교차 전이. 로봇 R_A가 새로운 영역을 탐색하여 지도를 갱신하면, 이 정보가 로봇 R_B와 R_C의 탐색 전략에 영향을 미치므로, R_A의 상태 변화가 R_B와 R_C의 상태 전이를 유발하는 교차 전이(cross-transition)가 필요하다. 3대의 경우 교차 전이 경로는 3 \times 2 = 6개이나, N대로 일반화하면 N(N-1)개로 증가하며, 각 경로에서 전달 정보의 유형별로 별도의 전이 규칙이 요구된다.

통신 장애 대응의 상태 분기. 무선 통신 환경에서 로봇 간 통신 링크는 가용 또는 불가용의 이진 상태를 가진다. 3대 로봇 간 통신 링크는 \binom{3}{2} = 3개이므로, 통신 연결 상태의 조합은 2^3 = 8가지이다. 각 통신 조합에 따라 로봇의 행동 전략이 달라져야 하므로(예: 통신 불가 시 독립 탐색으로 전환, 부분 통신 시 가용 로봇과의 협업 유지), 이 8가지 조합 각각에 대하여 별도의 상태와 전이를 정의하여야 한다.

4. 사례 2: 형성 제어 기반 협동 운반 임무에서의 상태 머신 한계

4.1 임무 시나리오 정의

4대의 전방향 이동 로봇(omnidirectional mobile robot)이 사각 형성(square formation)을 유지하며 대형 물체를 협동으로 운반한다. 임무 수행 중 형성의 유지, 장애물 회피에 의한 형성 변형, 개별 로봇 고장에 대한 대응, 좁은 통로 통과를 위한 형성의 동적 전환(사각 형성에서 종대 형성으로 전환)이 요구된다.

4.2 FSM에 의한 설계의 구조적 한계

형성 유형과 역할 할당의 조합적 증가. 가용 형성 유형이 K종류(사각, 종대, 횡대, 삼각 등)이고, 각 형성에서 로봇별 역할(리더, 좌측 팔로워, 우측 팔로워, 후방 팔로워 등)의 배정이 순열(permutation)로 결정되면, 형성 상태의 수는 K \times N!이다. K = 4, N = 4일 때 4 \times 24 = 96개의 형성 상태가 존재하며, 형성 간 전환의 중간 단계(transitional phase)를 포함하면 상태 수는 더욱 증가한다. 형성 전환은 출발 형성과 도착 형성의 쌍에 대하여 정의되므로, 전환 경로의 수는 K(K-1)이며 각 경로에서 로봇별 이동 궤적이 상이하다.

리더-팔로워 동적 전환. 리더 로봇의 고장 시, 잔여 로봇 중 하나가 리더 역할을 인계(takeover)하여야 한다. N대 중 임의의 1대가 고장 가능하므로, N가지 고장 시나리오 각각에 대하여 잔여 N-1대의 리더 후보가 존재한다. 이를 FSM으로 모델링하면 N \times (N-1)개의 전환 상태가 필요하며, 리더 교체 합의 프로토콜의 중간 상태까지 포함하면 상태 수는 추가로 증가한다.

부분 형성 재구성. 로봇 1대가 고장 시, 잔여 3대로 삼각 형성(triangular formation)을 재구성하여야 한다. 고장 로봇의 위치에 따라 재구성 전략이 달라지며, N대 중 k대 고장 시 잔여 (N-k)대의 가능한 형성 재구성 조합을 모두 FSM 상태로 명시하여야 한다. 이는 고장 로봇 조합 \binom{N}{k}와 가용 형성 유형의 곱으로 증가한다.

5. 사례 3: 이종 다중 로봇 협업에서의 상태 머신 한계

5.1 임무 시나리오 정의

재해 현장 수색 구조(Search and Rescue, SAR) 임무에서, 소형 회전익 무인기(quadrotor UAV) 2대와 지상 이동 로봇(UGV) 2대가 이종(heterogeneous) 협업 체계를 구성한다. UAV는 공중 정찰을 통하여 피해 지역의 전체 상황을 파악하고, UGV는 UAV가 식별한 관심 지점(Point of Interest, POI)에 접근하여 정밀 탐색 및 물자 전달을 수행한다.

5.2 FSM에 의한 설계의 구조적 한계

이종 상태 공간의 직곱. UAV와 UGV의 행동 모델은 본질적으로 상이하다. UAV의 상태 집합 S_{\text{UAV}} = \{\text{이륙}, \text{순항}, \text{정찰 촬영}, \text{선회 대기}, \text{복귀}, \text{착륙}, \text{충전}\}과 UGV의 상태 집합 S_{\text{UGV}} = \{\text{대기}, \text{이동}, \text{탐색}, \text{구조 작업}, \text{물자 전달}, \text{장애물 우회}, \text{복귀}\}를 단일 FSM으로 통합하면, 시스템 상태 공간은 \lvert S_{\text{UAV}} \rvert^2 \times \lvert S_{\text{UGV}} \rvert^2 = 7^2 \times 7^2 = 2{,}401이 되며, 이에 UAV-UGV 간 협업 상태(지시 전달 중, 확인 대기 중, POI 재할당 중 등)가 곱해져 상태 수가 급증한다.

이종 실패 모드의 교차. UAV와 UGV는 상이한 실패 모드를 가진다. UAV는 배터리 소진, GPS 신호 손실, 강풍에 의한 비행 불안정 등이 발생 가능하며, UGV는 주행 장치 고장, 노면 통행 불가, 센서 오염 등이 발생 가능하다. 이종 실패 모드의 조합에 대하여 각 로봇의 복구 전략이 상호 영향을 미치며(예: UAV 고장 시 UGV의 정찰 임무 자체 수행 전환), 이를 FSM으로 표현하면 실패 모드 조합 수에 비례하는 예외 처리 상태가 필요하다.

비대칭적 통신 구조. UAV-UGV 간 통신과 UAV-UAV 간 통신, UGV-UGV 간 통신은 상이한 대역폭, 지연 시간, 신뢰도를 가진다. 통신 채널별 상태(정상, 지연, 단절)의 조합이 로봇 행동에 영향을 미치며, 이를 FSM의 이산 상태로 모델링하면 통신 상태 조합 수만큼 추가 상태가 발생한다.

6. 사례 4: 다중 로봇 임무 할당에서의 상태 머신 한계

6.1 임무 시나리오 정의

물류 창고에서 N대의 자율 이동 로봇(AMR)이 M개의 물품 운반 주문을 처리한다. 주문은 동적으로 도착하며, 각 로봇은 현재 포지션, 배터리 잔량, 적재 용량에 따라 최적의 주문을 할당받아야 한다. 주문 우선순위의 변동, 로봇의 경로 충돌 방지, 충전 스케줄 관리가 동시에 요구된다.

6.2 FSM에 의한 설계의 구조적 한계

동적 임무 풀(pool)의 상태 표현. 임무 할당은 N대의 로봇과 M개의 임무 간의 매핑 문제이며, 가능한 할당 조합의 수는 \frac{(M+N-1)!}{(N-1)! \cdot M!} 이상이다. 임무가 동적으로 추가·삭제되므로, FSM의 상태 집합을 정적으로 고정할 수 없다.

충전 스케줄과 임무 수행의 상호 의존. 로봇의 배터리 잔량이 임무 할당 결정에 영향을 미치며, 충전 스테이션의 가용 슬롯이 제한되면 충전 대기열 관리가 추가 상태를 요구한다. N대의 로봇과 P개의 충전 슬롯 간 경쟁을 FSM으로 표현하면, 자원 경합 상태만으로 \binom{N}{P}개의 상태 조합이 발생한다.

7. 분산 FSM 접근의 근본적 한계

상태 공간 폭증을 완화하기 위하여 각 로봇에 독립적 FSM을 할당하는 분산(distributed) 접근이 시도될 수 있으나, 이 방식은 다음의 근본적 한계를 내포한다.

시스템 수준 속성의 비보장. 개별 로봇의 FSM이 단독으로 올바르게 동작하더라도, 로봇 간 상호작용에 의하여 시스템 수준의 교착(deadlock), 활성 잠금(livelock), 자원 충돌(resource conflict)이 발생할 수 있다. 예를 들어, 두 로봇이 동시에 동일 충전 스테이션을 점유하려 시도하면 교착이 발생하며, 이를 방지하기 위한 상호 배제(mutual exclusion) 프로토콜이 각 로봇의 FSM에 부가적 상태와 전이로 내재화되어야 한다.

조정 프로토콜의 FSM 내 인코딩 복잡성. 로봇 간 합의, 경매(auction), 계약망(contract net) 등 조정 프로토콜의 단계적 절차를 FSM의 이산 상태로 표현하면, 프로토콜의 메시지 교환 단계마다 별도의 상태가 필요하다. N대 로봇이 참여하는 k단계 합의 프로토콜은 각 로봇의 FSM에 최소 k개의 추가 상태를 요구하며, 타임아웃, 재전송, 프로토콜 실패 등의 예외 사항은 추가적인 상태 분기를 발생시킨다.

전역적 일관성 보장의 어려움. 분산 환경에서 모든 로봇이 시스템 상태에 대하여 동일한 인식(consistent view)을 유지하는 것은 합의 문제(consensus problem)에 해당한다. Fischer, Lynch, Paterson(1985)이 증명한 바와 같이, 비동기 분산 시스템에서 1대의 프로세스 고장만으로도 결정론적 합의가 불가능하며(FLP impossibility), 이는 분산 FSM 기반 MRS에서 전역 상태 일관성 보장의 이론적 한계를 시사한다.

8. 행동 트리에 의한 다중 로봇 행동 제어의 우위

행동 트리(Behavior Tree, BT)는 전술한 FSM의 구조적 한계에 대하여 다음과 같은 설계적 이점을 제공한다.

계층적 분해에 의한 복잡도 관리. 시스템 수준 BT의 루트에서 개별 로봇 수준의 서브트리로 계층적으로 분해함으로써, 로봇 간 조정 논리와 개별 로봇 행동 논리를 구조적으로 분리한다. 서브트리는 독립적으로 설계·검증·재사용 가능하므로, 로봇 수 증가 시에도 선형적 복잡도 증가에 가까운 확장성을 확보할 수 있다.

블랙보드 메커니즘에 의한 정보 공유. 로봇 간 공유 블랙보드(shared blackboard)를 통하여 지도 정보, 임무 할당 상태, 형성 파라미터, 시스템 상태 등을 중앙 저장소에 유지하며, 각 서브트리의 조건 노드(condition node)가 블랙보드의 정보를 평가하여 행동을 조정한다. 이 방식은 FSM의 교차 전이를 대체하며, 로봇 수 증가 시에도 블랙보드 항목의 선형적 추가만으로 확장 가능하다.

동적 서브트리 할당에 의한 런타임 재구성. 임무 할당기(task allocator)의 출력에 따라 각 로봇에 적절한 행동 서브트리를 런타임에 동적으로 교체 할당할 수 있으며, 이는 FSM에서 상태 집합과 전이 함수의 런타임 재정의에 해당하는 기능을 구조적으로 지원한다.

병렬 노드에 의한 동시성 표현. BT의 Parallel 제어 노드는 복수의 자식 노드를 동시에 실행하여, 다중 로봇의 병행 행동을 자연스럽게 표현한다. FSM에서 병행 행동의 표현을 위하여 직교 영역(orthogonal region)을 도입할 때 수반되는 동기화 복잡도가 BT에서는 Parallel 노드의 성공·실패 정책(success/failure policy)으로 간결하게 처리된다.

9. 참고 문헌

• Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Parker, L. E. (2008). “Multiple Mobile Robot Systems.” Springer Handbook of Robotics, 921–941.
• Rizk, Y., Awad, M., & Tunstel, E. W. (2019). “Cooperative Heterogeneous Multi-Robot Systems: A Survey.” ACM Computing Surveys, 52(2), 1–31.
• Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). “Impossibility of Distributed Consensus with One Faulty Process.” Journal of the ACM, 32(2), 374–382.
• Gerkey, B. P., & Matarić, M. J. (2004). “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems.” The International Journal of Robotics Research, 23(9), 939–954.
• Korsah, G. A., Stentz, A., & Dias, M. B. (2013). “A Comprehensive Taxonomy for Multi-Robot Task Allocation.” The International Journal of Robotics Research, 32(12), 1495–1512.

v0.2.0