1316.45 자동 플래너 구성 기법

1316.45 자동 플래너 구성 기법

1. 자동 구성의 개요

자동 플래너 구성(automatic planner configuration)은 알고리즘 구성(algorithm configuration) 기법을 플래닝에 적용하여, 주어진 도메인이나 문제 분포에 최적화된 플래너 설정(휴리스틱, 탐색 전략, 매개변수)을 자동으로 탐색하는 기법이다(Seipp et al., 2015).

2. 구성 공간

현대 플래너(특히 Fast Downward)는 다수의 구성 가능 매개변수를 가진다:

  • 휴리스틱 선택: FF, LM-count, LM-cut, CG, merge-and-shrink, PDB 등
  • 탐색 알고리즘: A*, 가중 A*, GBFS, EHC 등
  • 큐 구성: 단일 큐, 이중 큐, 다중 큐, 부스팅 비율
  • 선호적 연산자: 사용 여부, 소스 선택
  • 가중치: 가중 A*의 w 값
  • 기타: 중복 검출 전략, 시간 제한, 메모리 제한

이러한 매개변수의 조합이 구성 공간(configuration space)을 형성하며, 가능한 조합의 수는 극히 크다.

3. 자동 구성 기법

3.1 SMAC (Sequential Model-based Algorithm Configuration)

Hutter et al.(2011)이 개발한 일반적 알고리즘 구성 도구로, 베이지안 최적화(Bayesian optimization)를 사용하여 구성 공간을 효율적으로 탐색한다:

  1. 대리 모델(Surrogate Model): 랜덤 포레스트로 구성-성능 관계를 학습
  2. 획득 함수(Acquisition Function): 기대 개선(Expected Improvement)으로 유망한 구성을 선택
  3. 반복적 평가: 선택된 구성을 벤치마크에서 실행하고 결과를 학습에 반영

3.2 ParamILS

반복적 지역 탐색(Iterated Local Search)을 사용하여 구성 공간을 탐색하는 기법이다.

3.3 GGA (Gender-based Genetic Algorithm)

유전 알고리즘 기반의 구성 탐색 기법이다.

4. Fast Downward에서의 자동 구성

Fast Downward의 플러그인 아키텍처를 활용한 자동 구성 예시:

구성 공간:
  heuristic ∈ {ff, lmcount, lmcut, cg, cea, merge_and_shrink}
  search ∈ {astar, eager_greedy, lazy_greedy}
  preferred_operators ∈ {true, false}
  boost_value ∈ {0, 1000, 2000, 5000}
  weight ∈ {1, 2, 3, 5, 10}

SMAC 최적화:
  입력: 훈련 벤치마크 집합
  출력: 최적 구성 (예: eager_greedy([ff], preferred=[ff], boost=2000))

5. 포트폴리오 자동 구성

개별 플래너 구성을 넘어, 여러 구성의 포트폴리오를 자동으로 생성하는 기법(Seipp et al., 2015):

  1. SMAC으로 다수의 유망한 구성을 생성
  2. 각 구성의 벤치마크 커버리지를 분석
  3. 상호 보완적인 구성들을 시간 분할 포트폴리오로 조합
  4. 시간 배분을 최적화

6. 도메인 특화 자동 구성

특정 로봇 도메인에 대해 자동 구성을 수행하면, 범용 설정보다 크게 향상된 성능을 달성할 수 있다:

1. 로봇 도메인의 다양한 문제 인스턴스 생성 (크기, 객체 수 변화)
2. SMAC으로 해당 도메인에 최적화된 플래너 구성 탐색
3. 최적 구성을 PlanSys2에 적용

7. 참고 문헌

  • Hutter, F., Hoos, H. H., & Leyton-Brown, K. (2011). “Sequential Model-Based Optimization for General Algorithm Configuration.” Proceedings of LION, 507–523.
  • Seipp, J., Sievers, S., Helmert, M., & Hutter, F. (2015). “Automatic Configuration of Sequential Planning Portfolios.” Proceedings of AAAI, 3364–3370.
  • Fawcett, C., Vallati, M., Hutter, F., Hoffmann, J., Hoos, H., & Leyton-Brown, K. (2014). “Moving AI Planning Forward with Heuristics and Search.” Proceedings of ECAI.