Cross-Entropy Method (CEM)

다른 이름: CEM
카테고리: Planning & manipulation › Trajectory optimisation
태그: optimization, sampling-based-planning, model-predictive-control, model-based-rl, trajectory-optimization

후보 해를 반복적으로 샘플링하고, 점수가 가장 좋은 일부를 남겨 샘플링 분포를 그것에 다시 맞추는 샘플링 기반 최적화기로, 모델 기반 제어에서 행동 시퀀스 최적화에 널리 쓰인다.

정의

교차 엔트로피 방법(cross-entropy method, CEM)은 단순한 무도함수 최적화 알고리즘이다. 후보 해에 대한 확률 분포, 보통 평균과 대각 분산을 갖는 가우시안을 유지한다. 매 반복마다 샘플 묶음을 뽑아 각각의 비용을 평가하고, 점수가 가장 좋은 일부(엘리트(elites))를 골라, 분포의 평균과 분산을 그 엘리트에 다시 맞추며, 이때 흔히 이전 값 쪽으로 약간의 평활화를 적용한다. 반복이 진행되면서 분포는 좋은 해 주변으로 좁아진다. 이 방법은 1990년대 후반 Reuven Rubinstein이 처음에는 희귀 사건 확률 추정을 위해, 이어서 최적화를 위해 개발했다. 이름은 재적합 단계가 샘플링 분포와 점수가 높은 샘플에 집중된 분포 사이의 교차 엔트로피, 즉 KL 발산을 최소화한다는 사실에서 왔다.

로봇공학에서 CEM은 샘플링 기반 모델 예측 제어(sampling-based model predictive control) 안의 궤적 최적화기로 가장 잘 알려져 있다. 결정 변수는 계획 구간에 걸친 행동 시퀀스이다. 샘플링된 각 시퀀스는 물리 시뮬레이터나 학습된 모델인 동역학 모델을 통해 롤아웃되고, 합산된 비용이나 예측된 보상으로 점수가 매겨진다. CEM을 몇 번 반복한 뒤 로봇은 평균 시퀀스나 최고 시퀀스의 첫 번째 행동을 실행하고, 다음 단계에서 다시 계획하며, 보통 이전 해를 시간상 앞으로 밀어 웜 스타트한다. PETS와 PlaNet 같은 모델 기반 강화 학습 방법이 학습된 모델과 함께 이런 방식으로 CEM을 사용하며, 변형들은 시간적으로 상관된 노이즈를 추가하거나, 단계 사이에 엘리트를 재사용하거나, 샘플을 제안하는 학습된 정책과 CEM을 결합한다.

CEM의 매력은 경사가 필요 없고, 매끄럽지 않거나 불연속인 비용을 다룰 수 있으며, GPU에서 병렬로 실행하기 쉽다는 점이다. 약점은 구간 길이와 행동 차원 수에 따라 빠르게 커지는 샘플 비용, 그리고 분산이 너무 일찍 국소 최적점으로 붕괴하는 경향이다. 모든 샘플에 비용의 지수 함수로 가중치를 주는 MPPI와 달리, CEM은 엄격한 절단 기준을 쓰고 엘리트를 동등하게 취급한다. iLQR이나 DDP 같은 경사 기반 궤적 최적화기와 달리 모델의 도함수를 활용하지 않으므로, 매끄러운 문제에서는 대개 샘플 효율이 낮지만 학습된 모델이나 블랙박스 모델에는 더 관대하다.

중요한 이유

CEM은 동역학 모델을 제어기로 바꾸는 가장 단순한 방법 중 하나이며, 많은 모델 기반 학습 논문에서 기본 계획기로 등장한다. 그런 결과를 재현하거나, 경사 기반 계획기나 MPPI 방식 계획기가 문제에 더 맞는지 판단하려면 엘리트 선택, 구간, 샘플 수 사이의 절충을 이해해야 한다.

주요 응용

학습된 동역학 모델을 이용한 샘플링 기반 모델 예측 제어
시각 제어를 위한 잠재 월드 모델 안에서의 계획
후보를 샘플링하고 점수를 매기는 방식의 파지 및 행동 선택
경사 없는 정책 탐색과 파라미터 조정
연속 행동 공간을 갖는 Q-learning에서의 행동 최적화

실제 사례

밀기 작업에 학습된 동역학 모델을 사용하는 한 팀은 제어 단계마다 CEM 기반 MPC를 실행한다. 짧은 구간에 걸친 행동 시퀀스 수백 개를 가우시안에서 샘플링하고, 각각을 GPU에서 학습된 모델로 롤아웃한 뒤, 예측 비용 기준 상위 10분의 1을 남겨 평균과 분산을 다시 맞추고, 이를 몇 번 반복한 뒤 첫 번째 행동을 실행한다. 계획기가 단계 사이에서 떨리듯 오락가락하면, 이전 평균을 밀어서 재사용하는 웜 스타트를 하고 탐색이 붕괴하지 않도록 최소 분산을 추가한다. CEM은 비현실적으로 낮은 비용을 예측하는 모델 오차를 악용하므로, 팀은 모델의 학습 데이터에서 멀리 벗어나는 행동 시퀀스에 대한 페널티도 추가한다.

흔한 오해

CEM은 강화 학습 알고리즘이다 — CEM은 범용 최적화기이다. 모델 기반 RL에서 CEM은 모델로 계획하며, 학습은 모델이나 가치 함수에서 일어난다
CEM 반복은 많을수록 언제나 도움이 된다 — 분산이 성급하게 나쁜 국소 최적점으로 붕괴할 수 있고, 학습된 모델에서는 추가 최적화가 모델 오차를 악용할 수 있다
CEM과 MPPI는 같다 — 둘 다 행동 시퀀스를 샘플링하지만, CEM은 엄격하게 선택한 엘리트 집합에 다시 맞추고 MPPI는 모든 샘플에 지수화한 비용으로 가중치를 준다

알아야 할 사람

모델 기반 강화 학습 연구자
샘플링 기반 MPC를 사용하는 제어 엔지니어
학습된 모델이나 시뮬레이션 모델로 계획하는 조작 엔지니어
궤적 최적화 방법을 비교하는 학생

Open Source Robotics

Cross-Entropy Method (CEM)

정의

중요한 이유

주요 응용

실제 사례

흔한 오해

알아야 할 사람

관련 기술

관련 용어

관련 프로젝트