동적 계획법과 LQR 기초 정리, 스탠퍼드 AA203 최적제어 강의로 이해하는 폐루프 정책

핵심 메시지

• 개루프 제어는 시간에 따른 입력 시퀀스를 미리 계산하지만, 폐루프 정책은 어떤 상태에 있든 그때 할 최선의 행동을 알려준다.
• 외란과 모델 오차가 있는 현실에서는 계획된 궤적을 벗어나는 순간 개루프 시퀀스가 무력해지므로 폐루프 정책이 더 견고하다.
• 최적성 원리는 최적 경로의 꼬리 구간이 그 지점에서 시작하는 문제의 최적해라는 성질이며, 비용이 각 단계의 합으로 정의될 때 성립한다.
• 동적 계획법은 이 성질을 이용해 끝에서부터 거꾸로 계산하며 이미 푼 부분 문제의 답을 재사용한다.
• 상태가 연속이면 격자로 나눠야 하고 계산량이 상태 차원에 대해 지수적으로 늘어나는데, 이것이 차원의 저주다.

쉽게 이해하기

마르코 파보네 교수는 이 강의에서 수업의 축을 옮긴다고 예고한다. 지금까지 다룬 간접법과 직접법은 최적 제어 문제를 개루프 형태로, 즉 시간에 따른 제어 입력의 시퀀스로 풀어 왔다. 이번에는 모든 가능한 상태에 대해 최적의 행동을 지정하는 폐루프 제어 정책을 구하는 쪽으로 넘어간다.

왜 굳이 정책이 필요한지에 대한 설명이 명확하다. 시스템이 계획된 공칭 궤적을 그대로 따라간다면 두 방식의 결과는 같다. 그러나 실제 배치되는 시스템의 동역학은 설계에 쓴 모델과 다르고 외란도 있다. 궤적에서 벗어나는 순간 개루프 시퀀스는 상황과 무관하게 미리 정한 입력을 그대로 밀어붙이지만, 정책은 지금 어디에 있든 무엇을 해야 할지 알려준다.

핵심 도구는 최적성 원리다. 출발점 A에서 B를 거쳐 E로 가는 경로가 최적이라면, B에서 E까지의 꼬리 구간은 B에서 시작하는 문제의 최적해여야 한다. 강의는 이를 귀류법으로 증명한다. 만약 B에서 C를 거쳐 E로 가는 더 싼 경로가 있다면 A에서 그 경로를 이어 붙여 더 나은 전체 경로를 만들 수 있고, 이는 처음 경로가 최적이라는 가정과 모순이기 때문이다. 이 성질은 비용이 단계별 항의 합으로 주어진다는 가정에서 나온다.

이 원리 덕분에 꼬리 문제를 다시 풀 필요가 없어진다. 강의는 A에서 H까지 가는 작은 그래프 예제로 역방향 계산을 직접 보여준다. 도착점의 비용을 0으로 두고 한 단계씩 뒤로 오면서 각 지점에서 '즉시 비용 + 이미 계산해 둔 잔여 비용'이 최소가 되는 선택만 기록한다. 마지막에 시작점에 도달하면 각 단계에서 저장해 둔 최소화 선택을 따라가며 최적 경로를 복원한다.

다만 대가도 분명하다. 재귀는 모든 시간 단계에 대해, 그리고 도달 가능한 모든 상태에 대해 수행돼야 한다. 상태가 연속이면 격자로 나눠야 하는데, 각 축을 열 칸으로 나눈다면 계산량은 상태 차원 D에 대해 10의 D제곱으로 늘어난다. 교수는 이 지수적 증가를 차원의 저주라고 부르고, 이를 완화하는 근사 동적 계획법이 뒤에 이어질 학습 기반 제어의 출발점이라고 예고한다.

강의 후반부는 선형 이차 조절기(LQR)를 예로 삼는다. 동역학이 선형이고 비용이 상태와 제어의 이차형식일 때, 마지막 단계부터 역방향으로 한 단계 최적화를 풀면 최적 제어가 상태의 선형 피드백으로 나오고 잔여 비용은 다시 상태의 이차형식이 된다. 구조가 그대로 반복되므로 매 단계 최적화를 푸는 대신 이득 행렬과 비용 행렬에 대한 재귀식만 계산하면 되며, 이 식들이 리카티 방정식이다.

주요 인사이트

• 교수는 동적 계획법의 어려움이 알고리즘 자체가 아니라 모델링에 있다고 강조한다. 형식만 갖추면 재귀는 파이썬으로 옮겨 적는 수준이지만, 겉보기에 전혀 다른 문제를 이 형식에 맞게 표현하는 데 설계자의 기량이 필요하다는 것이다.
• 정책을 구한다는 것은 곧 관심 있는 초기 조건 하나가 아니라 도달 가능한 모든 상태에 대해 문제를 푸는 일이다. 낭비처럼 보이지만 초기 조건이나 문제 데이터가 바뀌어도 해가 남아 있다는 이점이 있다.
• 제약 조건은 직접법 같은 비선형 최적화에서는 문제를 어렵게 만들지만, 동적 계획법에서는 고려할 행동의 수를 줄이므로 오히려 계산을 단순하게 만든다.
• 동적 계획법은 각 재귀 단계에서 전역 최소를 찾으므로 국소해에 갇히지 않는 해를 준다는 점이 강조된다.
• 교수는 오늘의 정책 학습과 비전-언어-행동 모델 같은 흐름도 이 방정식에 뿌리를 두고 있다고 말한다. 복잡한 자율주행 시스템에서도 궤적 추종 부분은 LQR 계열인 경우가 많다는 언급이 이어진다.

자주 묻는 질문

관련 AI 소식