397.90 임무 계획의 계산 복잡도 감소 전략과 발전 과제

1. 개요

임무 계획 문제는 본질적으로 높은 계산 복잡도(Computational Complexity)를 수반한다. 고전적 계획 문제는 일반적으로 PSPACE-완전(PSPACE-Complete)이며, 최적 계획은 NP-난해(NP-Hard)에 해당한다(Bylander, 1994). 다중 로봇 작업 할당, 시간적 제약 계획, 확률적 계획 등의 확장된 문제는 더욱 높은 복잡도를 보인다. 실제 자율 로봇 시스템에서 임무 계획의 실시간 운용을 가능하게 하려면, 이러한 계산 복잡도를 효과적으로 감소시키는 전략이 필수적이다.

이 절에서는 임무 계획의 계산 복잡도를 감소시키기 위한 주요 전략을 분석하고, 이 분야의 미해결 과제와 향후 발전 방향을 고찰한다.

2. 계산 복잡도의 원천

2.1 문제 유형별 복잡도

임무 계획의 계산 복잡도는 문제의 유형과 표현력에 따라 달라진다:

2.2 복잡도 증가 요인

임무 계획의 계산 복잡도를 증가시키는 주요 요인은 다음과 같다:

상태 공간의 지수적 증가: n개의 이진 상태 변수에 대해 상태 공간의 크기는 2^n이다. 로봇 수, 작업 수, 환경 변수가 증가할수록 상태 공간이 조합적으로 폭발(Combinatorial Explosion)한다.

시간적 제약의 부과: 듀레이티브 액션과 시간 제약이 도입되면, 이산 시간 인덱싱으로 인해 상태 공간이 추가적으로 확장된다.

불확실성의 도입: 확률적 전이와 부분 관측이 도입되면, 신뢰 상태(Belief State) 공간의 연속성으로 인해 이산 상태 기반 기법의 직접 적용이 불가능해진다.

다중 목적의 고려: 다목적 최적화에서는 하나의 최적 해 대신 파레토 최적 해 집합(Pareto Front)을 탐색해야 하므로 계산 비용이 증가한다.

3. 문제 분해 기반 전략

3.1 계층적 분해(Hierarchical Decomposition)

계층적 분해는 대규모 임무 계획 문제를 관리 가능한 크기의 하위 문제(Sub-problem)로 분할하는 전략이다. 계층적 작업 네트워크(HTN)는 이 전략의 대표적 구현이다.

원래 문제의 상태 공간 크기가 |S|이고, 이를 k개의 계층으로 분해하며 각 계층의 평균 상태 공간 크기가 |S|^{1/k}이면, 총 계산 비용은 O(k \cdot |S|^{1/k})로 감소한다. 이는 원래의 O(|S|)에 비해 지수적 감소를 달성한다.

계층적 분해의 효과는 하위 문제 간의 상호 의존성(Interdependency)이 낮을수록 크다. 하위 문제 간의 강한 결합(Tight Coupling)이 존재하면 분해의 이점이 감소하며, 극단적인 경우 분해 자체가 불가능할 수 있다.

3.2 공간적 분해(Spatial Decomposition)

광역 임무 영역을 공간적으로 분할하여, 각 부분 영역에 대한 임무 계획을 독립적으로 수행하는 전략이다. 보로노이 분할, 격자 분할, 또는 자연 경계(도로, 하천 등) 기반 분할이 활용된다.

공간적 분해의 효과는 부분 영역 간의 교차 작업(Cross-Region Task)이 적을수록 크다. 교차 작업이 빈번한 경우, 분할 경계에서의 조율 비용이 증가하여 전체 효율이 저하될 수 있다.

3.3 시간적 분해(Temporal Decomposition)

장기 수평(Long Horizon) 계획을 시간 구간별로 분할하여, 각 구간의 계획을 순차적으로 수립하는 전략이다. 이 전략은 롤링 수평(Rolling Horizon) 계획으로도 알려져 있으며, 현재 시간 창(Time Window) 내의 계획만을 상세히 수립하고, 미래 구간에 대해서는 추상적 수준의 계획을 유지한다.

시간적 분해의 장점은 미래 불확실성이 큰 환경에서 불필요하게 상세한 장기 계획의 수립을 회피하고, 변화하는 상황에 대한 적응성을 향상시키는 것이다. 단, 현재 구간의 결정이 미래 구간에 부정적 영향을 미칠 수 있으므로, 미래 상태에 대한 적절한 추정(Lookahead)이 필요하다.

4. 추상화 기반 전략

4.1 상태 추상화(State Abstraction)

상태 공간의 세부 사항을 생략하여 추상화된 상태 공간에서 계획을 수립하고, 이를 구체적 상태 공간에서 정제(Refinement)하는 전략이다.

술어 추상화(Predicate Abstraction): 상태를 구성하는 일부 술어만을 고려하여 추상 상태 공간을 구성한다. 임무 수행에 직접적으로 관련된 술어만을 선택하고, 보조적 술어를 생략함으로써 상태 공간을 축소한다.

패턴 데이터베이스(Pattern Database): 상태 변수의 부분 집합(패턴)에 대한 최적 비용을 사전 계산하여 데이터베이스에 저장하고, 이를 탐색의 허용적 휴리스틱(Admissible Heuristic)으로 활용한다. 이는 A* 알고리즘의 탐색 효율을 크게 향상시킨다.

4.2 행동 추상화(Action Abstraction)

기본 행동(Primitive Action)의 시퀀스를 상위 수준의 매크로 행동(Macro-Action)으로 추상화하여, 계획 수립 시의 탐색 깊이를 감소시킨다. 빈번하게 사용되는 행동 시퀀스를 자동으로 식별하여 매크로 행동으로 정의하는 학습 기반 접근법이 연구되고 있다.

매크로 행동의 길이를 l이라 하면, 매크로 행동을 사용한 계획의 최대 탐색 깊이는 원래 깊이 d에서 d/l로 감소한다. 그러나 매크로 행동의 도입은 분기 인수(Branching Factor)를 증가시킬 수 있으므로, 매크로 행동의 선택에는 신중한 분석이 필요하다.

5. 근사 및 휴리스틱 전략

5.1 제한 시간 계획(Anytime Planning)

제한 시간 계획은 허용된 시간 내에서 가능한 한 최선의 계획을 생성하는 전략이다. 초기에 빠르게 실행 가능한 해를 생성하고, 잔여 시간 동안 해의 품질을 점진적으로 개선한다.

대표적인 제한 시간 알고리즘으로는 ARA*(Anytime Repairing A*)(Likhachev et al., 2004)가 있다. ARA는 초기에 팽창 계수(Inflation Factor) \epsilon이 큰 가중 A 탐색으로 빠르게 해를 생성하고, \epsilon을 점차 감소시키면서 해를 정제한다. \epsilon = 1에 도달하면 최적 해가 보장된다.

해의 품질 보증(Quality Guarantee)은 다음과 같이 제공된다:

\text{cost}(\pi_{\text{current}}) \leq \epsilon \cdot \text{cost}(\pi^*)

여기서 \pi_{\text{current}}는 현재까지 찾은 최선의 계획, \pi^*는 최적 계획이다.

지역 탐색(Local Search)

지역 탐색은 현재 해의 이웃(Neighborhood)을 탐색하여 개선된 해를 발견하는 반복적 최적화 기법이다. 임무 계획에서의 지역 탐색은 초기 실행 가능 해에서 출발하여, 작업 할당 변경, 순서 교환, 경로 구간 재배치 등의 이웃 연산을 적용한다.

지역 탐색의 일반적 변형은 다음과 같다:

• 시뮬레이티드 어닐링(Simulated Annealing, SA): 온도 파라미터를 통해 열화 해(Worse Solution)의 수용 확률을 제어하여, 지역 최적(Local Optimum)에서의 탈출을 가능하게 한다.
• 타부 탐색(Tabu Search): 최근 방문한 해를 타부 리스트에 등록하여 재방문을 금지함으로써 순환 탐색을 방지한다.
• 대규모 이웃 탐색(Large Neighborhood Search, LNS): 현재 해의 일부를 파괴(Destroy)하고 재구성(Repair)하는 대규모 이웃 연산을 수행하여, 탐색 범위를 확장한다.

유전 알고리즘 기반 접근

유전 알고리즘(Genetic Algorithm, GA)은 인구 기반(Population-Based) 메타 휴리스틱으로, 복수의 후보 해를 동시에 유지하고 진화시킨다. 임무 계획에서의 유전 알고리즘 적용은 작업 순서(순열 표현), 작업-로봇 할당(정수 표현), 또는 양자의 결합 표현에 대해 교차(Crossover)와 변이(Mutation) 연산자를 적용한다.

병렬 및 분산 계산 전략

병렬 계획 알고리즘

계획 알고리즘의 병렬화를 통해 계산 시간을 단축하는 전략이다:

병렬 A*: 상태 공간 탐색의 OPEN 리스트를 분할하여 복수의 프로세서에서 동시에 탐색을 수행한다. Hash Distributed A*(HDA*)는 해시 함수를 사용하여 상태를 프로세서에 할당하며, 메모리와 탐색 작업의 균형 있는 분산을 달성한다.

병렬 메타휴리스틱: 유전 알고리즘이나 입자 군집 최적화(Particle Swarm Optimization) 등의 인구 기반 알고리즘은 본質적으로 병렬화에 적합하다. 개체(Individual)별 적합도 평가를 병렬로 수행하거나, 섬 모델(Island Model)을 통해 복수의 독립 진화를 병렬로 수행한다.

GPU 가속

GPU(Graphics Processing Unit)의 대규모 병렬 처리 능력을 활용하여 계획 알고리즘을 가속하는 연구가 진행되고 있다. 특히, 몬테카를로 트리 탐색(MCTS)의 롤아웃(Rollout) 병렬화와 신경망 기반 계획의 추론 가속에서 GPU 활용이 효과적이다.

온라인 계획 전략

재계획 효율화

환경 변화에 따른 재계획(Replanning)의 계산 비용을 감소시키기 위한 전략이다:

증분 계획(Incremental Planning): 이전 계획의 결과를 재활용하여, 변경된 부분만을 재계획한다. D* Lite(Koenig & Likhachev, 2005) 알고리즘은 환경 변화가 감지되면 영향 받는 노드만을 재계산하여, 전체 재계획에 비해 크게 단축된 시간에 갱신된 계획을 생성한다.

계획 수리(Plan Repair): 현재 계획에서 실패한 부분만을 국소적으로 수정하는 전략이다. 전체 재계획보다 빠르지만, 수리된 계획의 전역적 최적성이 보장되지 않을 수 있다.

조건부 계획(Contingency Planning): 예상 가능한 환경 변화에 대한 대안 계획을 사전에 수립하여, 변화 발생 시 즉시 대안 계획으로 전환한다. 사전 계획 비용이 증가하지만, 온라인 재계획 시간을 크게 단축한다.

미해결 과제

이론적 과제

• 계획 복잡도의 하한(Lower Bound): 다양한 계획 문제에 대한 엄밀한 복잡도 하한의 확립이 아직 불완전하다. 특히, 실용적 제한 조건 하에서의 문제 복잡도 분류가 필요하다.
• 근사 해의 품질 보증: 근사 알고리즘의 근사 비율(Approximation Ratio)에 대한 엄밀한 이론적 보장이 많은 문제에서 아직 확립되지 않았다.
• 혼합 연속-이산 문제: 연속적 운동 계획과 이산적 작업 계획의 통합 문제에 대한 효율적 해법이 제한적이다.

실무적 과제

• 실시간성 보장: 시간 제한이 엄격한 환경에서, 제한 시간 내에 최소 품질의 해를 보장하는 메커니즘이 필요하다.
• 확장성: 로봇 수, 작업 수, 환경 복잡도가 동시에 증가하는 실제 시나리오에서의 확장성이 보장되어야 한다.
• 강건성: 모델 불확실성, 센서 오류, 통신 두절 등의 실무적 조건 하에서의 계획 품질 유지가 필요하다.
• 통합 벤치마크: 다양한 임무 계획 알고리즘의 공정한 비교를 위한 표준 벤치마크와 평가 프레임워크의 확립이 요구된다.

학제적 과제

• 인간-AI 협업 계획: 인간 전문가의 직관적 판단과 AI 계획기의 체계적 최적화를 효과적으로 결합하는 인터페이스와 프로토콜의 설계
• 윤리적 제약의 형식화: 안전성, 공정성, 프라이버시 등의 윤리적 요구사항을 형식적 제약으로 변환하여 임무 계획에 통합하는 방법론
• 설명 가능성과 효율성의 균형: 설명 가능한 임무 계획의 구현이 계산 효율에 미치는 영향을 최소화하는 기법

향후 발전 방향

임무 계획의 계산 복잡도 감소 연구는 다음의 방향으로 발전이 기대된다:

1. 학습 기반 휴리스틱 자동 설계: 문제 인스턴스의 특성을 분석하여 최적의 휴리스틱 함수를 자동으로 학습하는 기법
2. 적응적 추상화 수준 조절: 계획 진행 상황과 잔여 시간에 따라 추상화 수준을 동적으로 조절하는 기법
3. 양자 컴퓨팅의 활용: 양자 어닐링(Quantum Annealing)이나 변분 양자 고유값 해석기(Variational Quantum Eigensolver)를 활용한 조합 최적화의 가속
4. 연합 계획(Federated Planning): 개인정보나 군사 보안을 유지하면서 분산된 계획 정보를 활용하는 연합 학습 기반 계획 기법
5. 기초 모델 기반 계획 가속: 대규모 사전 훈련 모델을 활용하여 계획 탐색의 초기 추정치를 제공하고, 형식적 기법으로 정제하는 하이브리드 전략

참고 문헌

• Bylander, T. (1994). “The Computational Complexity of Propositional STRIPS Planning.” Artificial Intelligence, 69(1-2), 165-204.
• Likhachev, M., Gordon, G., & Thrun, S. (2004). “ARA*: Anytime A* with Provable Bounds on Sub-Optimality.” Advances in Neural Information Processing Systems (NeurIPS), 16.
• Koenig, S., & Likhachev, M. (2005). “Fast Replanning for Navigation in Unknown Terrain.” IEEE Transactions on Robotics, 21(3), 354-363.
• Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191-246.
• Ghallab, M., Nau, D., & Traverso, P. (2016). “Automated Planning and Acting.” Cambridge University Press.
• Stern, R., Sturtevant, N. R., Felner, A., Koenig, S., Ma, H., Walker, T. T., … & Boyarski, E. (2019). “Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks.” Symposium on Combinatorial Search (SoCS).