HJB·HJI 방정식과 도달가능집합 — 스탠퍼드 AA203 최적·학습 기반 제어 10강 정리

핵심 메시지

• 무한 시간 문제에서 벨만 방정식은 고정점 형태가 되고, 이를 푸는 표준 방법이 가치 반복과 정책 반복이다.
• 상태와 제어의 가짓수가 유한하면 정책 반복은 유한한 횟수 안에 최적 정책에 도달한다.
• 시간을 연속 변수로 두면 벨만 방정식은 편미분방정식인 HJB 방정식으로 바뀐다.
• 외란을 '나를 방해하는 두 번째 플레이어'로 모형화하면 HJI 방정식이 되고, 이것이 안전 보장의 출발점이다.
• 도달가능집합은 자율주행차·항공기의 충돌 회피 정책을 설계할 때 쓰이는 대표적 응용이다.

쉽게 이해하기

강의는 지난 시간에 다루던 확률적 동적계획법의 무한 시간 확장을 마무리하는 것으로 시작한다. 무한 시간 문제에서는 비용 대신 보상 관점으로 서술하는 것이 관례라, 우리가 구하려는 대상은 최적 가치 함수가 된다. 이때 벨만 방정식은 '현재 보상 + 다음 상태에서의 최적 가치의 기댓값'이 자기 자신과 같아지는 고정점 방정식의 형태를 띤다.

특정 정책의 가치를 구하는 문제는 상태 수가 유한할 경우 선형 연립방정식을 푸는 일로 환원된다. 여기서 정책 반복이 나온다. 먼저 현재 정책의 가치를 계산하고(정책 평가), 그 가치를 대용품 삼아 벨만 방정식을 한 단계만 적용해 더 나은 행동을 고른다(정책 개선). 최적 가치 함수를 아직 모르니 최적 행동은 아니지만, 개선된 정책의 가치는 이전보다 반드시 같거나 커진다는 점이 핵심이다.

상태와 제어가 모두 유한하면 가능한 정책의 수도 유한하고, 매 단계 가치가 엄밀히 좋아지므로 정책 반복은 유한한 횟수 안에 끝난다. 다만 두 방법 모두 전이 확률과 보상 함수를 이미 안다는 전제 위에 서 있다. 이 전제를 놓았을 때 어떻게 되는지가 뒤이어 나올 학습 기반 제어의 주제다.

강의의 후반부는 시간을 이산 단계가 아니라 연속 변수로 다룬다. 동역학은 미분방정식으로, 비용은 합 대신 적분으로 쓰인다. 이 설정에서 동적계획법을 밀고 나가면 해밀턴-야코비-벨만(HJB) 방정식이 나오는데, 시간과 상태 양쪽으로 미분이 들어가는 편미분방정식이라 형태는 험하다. 강의자는 이 식을 '비용 함수가 시간에 따라 줄어드는 속도 = 현재 비용과 동역학을 따라 이동할 때의 비용 변화의 최솟값'으로 읽으면 이산시간 벨만 방정식과 같은 이야기임이 보인다고 설명한다.

여기에 나를 방해하려는 두 번째 플레이어(외란·상대 차량·돌풍)를 넣으면 미분 게임이 된다. 쟁점은 상대가 어떤 정보를 보고 반응하느냐다. 내 제어 계획 전체를 미리 공개하는 모형은 상대에게 지나친 이점을 줘 결과가 과도하게 보수적이 되고, 강의가 택한 모형은 상대가 '지금까지의 내 행동만' 보고 반응하는 비예측 전략이다. 이 설정에서 미니맥스를 풀면 해밀턴-야코비-아이작스(HJI) 방정식이 나온다.

마지막으로 이 도구가 향하는 곳이 후방 도달가능집합이다. 목표 집합에서 시간을 거꾸로 돌려, 그 집합에 도달하게 되는 초기 상태들의 모임을 구하는 문제다. 목표 집합을 '피해야 할 것'으로 두면 어떤 제어를 해도 상대의 최악의 수 때문에 충돌하게 되는 회피 집합이 되고, '가야 할 곳'으로 두면 상대가 무엇을 하든 도달할 수 있는 상태들의 집합이 된다. 실제 계산 절차는 다음 강의로 미뤄졌지만, 연속시간 LQR이 2차 형식 추측과 리카티 미분방정식으로 풀리고 최적 제어가 여전히 상태의 선형 피드백이라는 결과도 함께 정리된다.

주요 인사이트

• 정책 반복의 수렴 보장은 '매번 반드시 좋아진다 + 정책의 가짓수가 유한하다'는 두 사실의 조합에서 나온다. 알고리즘의 성질을 문제의 구조로 환원해 보는 전형적인 논법이다.
• HJB 방정식이 무섭게 보이는 이유는 편미분방정식이라서지, 담긴 생각이 새로워서가 아니다. 이산시간에서 '한 스텝 뒤와의 차이'였던 것이 연속시간에서 '시간에 대한 변화율'로 바뀐 것뿐이다.
• 안전을 다루려면 확률 모형만이 아니라 적대적 모형이라는 선택지가 있다. 돌풍이나 상대 차량을 '최악으로 움직이는 플레이어'로 두면 확률 분포를 몰라도 보장을 말할 수 있다.
• 상대에게 무엇을 보여줄 것인가라는 정보 구조의 선택이 답의 보수성을 결정한다. 내 계획 전체를 노출하는 모형은 풀기는 쉽지만 실제 상황보다 지나치게 비관적인 결과를 준다.
• 강의자는 미니맥스 순서를 바꾸는 대목만은 엄밀한 증명 대신 참고 문헌으로 넘긴다. 중요한 것은 문제 정식화와 최종 알고리즘을 이해하는 것이라는 태도다.

자주 묻는 질문

관련 AI 소식