행동 조합 폭발 문제 (Behavioral Combinatorial Explosion Problem)

1. 개요

행동 조합 폭발(behavioral combinatorial explosion)은 로봇이 수행할 수 있는 행동의 수와 환경 조건의 수가 증가함에 따라, 가능한 행동 시퀀스의 수가 기하급수적으로 증가하는 현상이다. 하드코딩 기반 행동 제어에서 이 문제는 개발자가 모든 상황-행동 조합을 명시적으로 정의하여야 하므로, 시스템의 확장성을 근본적으로 제한한다.

2. 조합 폭발의 수학적 분석

2.1 행동 시퀀스의 수

m개의 가능한 행동이 있고, 임무가 k개의 단계로 구성되는 경우, 가능한 행동 시퀀스의 수는 다음과 같다.

N_{\text{sequences}} = m^k

예를 들어, 10개의 가능 행동과 5단계 임무에서 가능한 시퀀스는 10^5 = 100{,}000개이다.

조건-행동 규칙의 수

n개의 이진 조건 변수가 있을 때, 가능한 상태 수는 2^n이다. 각 상태에 대해 행동을 정의하면 필요한 규칙 수는 2^n이다.

FSM의 전이 수

n개의 상태와 e개의 이벤트가 있는 FSM에서, 가능한 전이 수는 n \times e이다. 이를 모두 명시적으로 정의하여야 한다.

조합 폭발의 실제 영향

개발 비용 증가

규칙 수의 증가는 개발 시간에 직접적으로 반영된다. 규칙 간의 상호 작용을 검증하는 비용은 규칙 수의 제곱에 비례한다.

오류 확률 증가

규칙이 많아지면 규칙 간 충돌, 누락, 불일치의 확률이 증가한다. 테스트 커버리지를 100%로 달성하기가 어려워진다.

유지보수 비용 증가

새로운 행동이나 조건이 추가될 때, 기존의 모든 규칙과의 상호 작용을 재검토하여야 한다.

자율 계획에 의한 해소

자율 계획은 조합 폭발 문제를 다음과 같이 해소한다.

1. 상태 공간 탐색의 자동화: 개발자가 규칙을 일일이 정의하는 대신, 계획 알고리즘이 상태 공간을 자동으로 탐색한다.
2. 도메인 정의의 간결성: PDDL로 행동의 전제 조건과 효과만 정의하면, 계획기가 이를 조합하여 행동 시퀀스를 생성한다.
3. 규칙 수의 선형 증가: 자율 계획에서 개발자가 정의하는 규칙(행동 정의)의 수는 행동의 수에 비례하며, 상태 조합의 수에 비례하지 않는다.

참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach. Pearson.