Monte Carlo Tree Search
- 다른 이름: MCTS
- 카테고리: Planning & manipulation › Task-level
- 태그: planning, tree-search, decision-making, pomdp, sampling-based
모델로부터 많은 궤적을 시뮬레이션해 탐색 트리를 키우고, 그 수익을 이용해 가장 유망한 행동을 고르는 온라인 계획 알고리즘.
정의
몬테카를로 트리 탐색(Monte Carlo tree search, MCTS)은 시뮬레이션한 경험으로부터 탐색 트리를 점진적으로 만들어 다음에 무엇을 할지 정하는 계획 알고리즘 계열이다. 각 반복은 네 단계로 이루어진다. 선택(selection)은 현재 상태에서 트리를 따라 내려가며, 추정 가치가 높은 행동과 몇 번밖에 시도되지 않은 행동 사이의 균형을 맞추는 규칙으로 자식 노드를 고른다. 확장(expansion)은 새 노드를 하나 이상 추가한다. 시뮬레이션(simulation, 또는 롤아웃)은 새 노드의 가치를 추정하는데, 고전적으로는 무작위 정책이나 단순한 기본 정책으로 에피소드 끝까지 진행해 본다. 역전파(backpropagation)는 경로 위 모든 노드의 방문 횟수와 가치 추정치를 갱신한다. 시간 예산이나 반복 예산이 다 떨어지면 알고리즘은 가장 많이 방문되었거나 가치가 가장 높은 루트 행동을 확정하고, 다음 상태에서 이 과정을 반복한다. 이 용어는 2006년 Rémi Coulom이 도입했으며, 같은 해 Kocsis와 Szepesvári가 UCT(Upper Confidence bounds applied to Trees)를 발표했다. UCT는 선택 단계에 UCB1 밴딧 규칙을 사용하며 가장 널리 쓰이는 변형이다.
MCTS에 필요한 것은 생성 모델뿐이다. 즉 상태와 행동이 주어지면 샘플링된 다음 상태와 보상을 돌려주는 시뮬레이터다. 명시적인 전이 행렬, 미분 가능한 모델, 손으로 작성한 휴리스틱은 필요 없으며, MCTS는 애니타임(anytime) 알고리즘이어서 계산을 더 쓸수록 더 나은 결정을 내고 답이 필요할 때 언제든 탐색을 멈출 수 있다. 적절한 조건에서 UCT는 시뮬레이션 횟수가 늘어남에 따라 최적 행동으로 수렴하지만, 실제로 결정의 질은 예산, 롤아웃 정책, 그리고 탐색을 어떻게 유도하느냐에 크게 좌우된다. AlphaGo와 AlphaZero는 무작위 롤아웃을 학습된 가치 추정으로 바꾸고 학습된 정책으로 선택에 편향을 주면 탐색이 훨씬 효율적이 된다는 것을 보여 주었다.
로봇공학에서 MCTS는 결과가 불확실한 시간 지평에 걸친 결정에 쓰인다. POMCP와 그 변형인 POUCT는 행동과 관측의 이력 위에서 탐색함으로써 UCT를 부분 관측 문제로 확장하며, 이 때문에 물체 탐색, 능동 인식, 정보 수집을 POMDP로 정식화한 문제의 흔한 솔버가 되었다. 연속 상태와 연속 행동에는 추가적인 주의가 필요하다. 점진적 확장(progressive widening)은 노드의 방문 횟수가 늘어날 때에만 새 자식 행동이나 샘플링된 관측을 추가하며, 많은 로봇 시스템은 그 대신 매크로 행동이나 모션 프리미티브의 이산 집합 위에서 탐색하고 연속 운동은 하위 수준 플래너가 처리하게 한다.
중요한 이유
다음에 어디를 볼지, 어떤 물체를 먼저 옮길지 같은 많은 로봇 결정은 그 결과가 몇 단계 뒤에야 드러나고 불확실한 관측에 좌우된다. MCTS는 시뮬레이터 하나만으로 그런 시간 지평에 걸쳐 계획하는 실용적인 방법을 제공하며, 전체 MDP나 POMDP를 오프라인으로 푸는 것이 불가능한 문제까지 확장된다.
주요 응용
- POMDP로 정식화한 물체 탐색과 능동 인식
- 작업 및 동작 계획에서 기호적 행동의 순서 선택
- 교차로와 합류 구간에서의 자율주행 의사결정
- 다중 로봇 협조와 탐사
- AlphaZero 방식 시스템처럼 학습된 모델을 이용한 계획
실제 사례
모바일 매니퓰레이터가 어수선한 방에서 여러 물체를 찾아야 한다. 팀은 이 작업을 POMDP로 모델링하는데, 물체 위치에 대한 믿음(belief), 관측 지점으로 이동하는 매크로 행동과 검출 행동, 그리고 카메라의 관측 모델을 둔다. 결정할 때마다 POUCT는 고정된 시간 예산 안에서 현재 믿음으로부터 수천 번의 시뮬레이션을 실행하며, 생성 모델로 물체 위치와 검출 결과를 샘플링한다. 로봇은 가치가 가장 높은 루트 행동을 실행하고, 실제 검출 결과로 믿음을 갱신한 뒤 다시 계획한다. 엔지니어는 탐색 상수, 롤아웃 정책, 탐색 지평을 조정하고, 트리가 예산 안에서 깊게 자랄 수 있도록 매크로 행동 집합을 충분히 작게 유지한다.
흔한 오해
- MCTS는 학습 알고리즘이다 — MCTS는 모델이나 시뮬레이터가 필요한 계획 방법이다. 학습된 가치 네트워크 및 정책 네트워크와 자주 결합되지만, 탐색 자체가 정책을 학습하지는 않는다
- MCTS에는 에피소드 끝까지 가는 무작위 롤아웃이 필요하다 — 롤아웃 대신 휴리스틱 정책, 잘린 지평, 또는 학습된 가치 함수를 쓸 수 있다
- MCTS는 연속 행동에 바로 작동한다 — 표준 UCT는 유한한 행동 집합을 가정하므로, 연속 문제에는 점진적 확장, 샘플링, 또는 매크로 행동의 이산 집합이 필요하다
- MCTS는 최적 행동을 찾는다 — 시뮬레이션이 늘어남에 따라 최적 행동 쪽으로 수렴할 뿐이다. 실시간 예산에서는 결과가 근사적이며 탐색을 어떻게 유도하느냐에 좌우된다
알아야 할 사람
- 계획 및 의사결정 엔지니어
- POMDP와 능동 인식을 연구하는 연구자
- 작업 및 동작 계획 개발자
- 탐색과 학습을 결합하는 강화 학습 실무자
관련 기술
- UCT
- POMCP
- AlphaZero
- 점진적 확장(Progressive Widening)
- Upper Confidence Bound(UCB1)
관련 용어
- Markov Decision Process (MDP)
- Partially Observable Markov Decision Process (POMDP)
- Belief-Space Planning
- Task and Motion Planning
- Robotic information gathering
- Reinforcement Learning
관련 프로젝트
- BehaviorTree.CPP: C++ behavior tree library for robot task planning, powering Nav2 and ROS 2 systems
- OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
동영상
- Monte Carlo Tree Search: John Levine
- AI 101: Monte Carlo Tree Search: AI and Games