[제어] Dynamic programming - Richard Bellman

이 글은 Richard Bellman(professor of mathematics, electrical engineering, medicine, University of Southern California)의 Dynamic programming(Science에 게재)을 정리한 글입니다. 다소 저의 이해가 부족해 내용을 왜곡했을 수도 있으니 원문을 찾아보시는 걸 권합니다.

 

---

 

문제 해결을 위한 planning과 programming의 다양성은 많은 수학 이론을 탄생시켰고, dynamic programming은 그 중 하나이다. 일련의 결정 과정이 필요한 문제에서 가장 중요한 것 중 하나는 system을 control하는 문제이다. 이 문제들은 한 번에 해결되는 것이 아니라 상호작용하는 관찰과 행동을 통해 해결된다.

 

시스템을 그 시스템의 필요와 의무의 관점에서 살펴보았을 때 그것을 충족시키는 일련의 행동들은 무수히 많다. 그 중 하나를 택하고 그 결정의 결과와 다음 결정을 위한 관찰이 이어져야 한다.

 

즉, 관찰 - 해석 - 결정, 이 일련의 과정이 반복된다.

 

dynamic programming은 어떤 정보가 필요하고 그것을 어떻게 활용할 것인지에 대한 systematic technique를 제공한다.

 

 

feedback control

 

space vehicle을 guidance하는 문제를 생각해보자. 최소한의 시간, 연료로 달에 착륙하기 위한 path를 계산해낼수 있다. vehicle의 속도와 위치를 지속적으로 모니터링하면서 약간의 disturbance에 대해 feedback control을 하면 우리가 원하는 대로 움직일 수 있을 것이다.

 

guidance of the spacecraft는 일련의 관찰과 결정의 과정으로 이루어져있다. 그러나 현실적으로 봤을 때 이 문제에는 어려움이 존재한다.

 

우리가 원하는 path로 가기 위해 spacecraft를 조정하다보면 큰 disturbance가 존재할 때, path를 유지하려고 하다보면 지그재그로 움직이게 되고(원래 계산된 path로 조정하는 과정 때문) 결국 많은 시간과 연료를 낭비하게 된다. 그런데 생각해보면 우리의 목적은 최소한의 시간으로 달에 도착하는 것이지, 우리가 계산한 trajectory로 움직이는 것이 목적이 아니다. 따라서 우리는 예상치 못한 path에 대하여 새로운 path를 계산하는 것이 낫다.

 

또한 결함으로 인해 새로운 path로 가는 것에서 멀어진다면 마찬가지로 다시 path를 계산하는 과정을 거쳐야 한다. 즉, 우리는 현재의 위치를 파악하고 새로 course를 계산함으로써 문제를 해결할 수 있다. 즉 이 문제는 multistage decision making이 필요하다. 현재 위치를 파악하고, 그것을 해석하여 새로운 경로를 결정하는 방식이 반복되기 때문이다.

 

이 policy는 경험을 통해 learning한다는 개념이 포함되어 있다. 시간이나 비용 등을 최소화하는 가장 효율적인 policy를 optimal policy라고 하는데 이 optimal policy는 처음의 상태와 결정에 관계 없이 현재의 상태를 고려하여 최적의 방법을 결정한다.

 

Application

 

앞서 말한 policy는 매우 flexible하지만 상상할 수 있는 모든 상태에 대한 최적의 결정을 내리기 위한 규칙이다. 복잡한 시스템의 경우 매우 많은 경우의 수를 가지고 있는데 이 때 digital computer의 성능이 문제가 된다.

최근에는 digital computer 성능이 좋아지고 있으므로 classical thoery는 대부분 복잡한 계산을 피하기 위해 존재했으나 이제는 자취를 감출 것이다.

 

multistage decision making

 

이제 multistage decision making에서 발생할 수 있는 어려움을 생각해보자. 우리는 지금까지

1) system의 상태를 모두 정확하게 알 수 있고,

2) control이 적용될 시기와 control로 인한 결과를 모두 알고 있다는 이상적인 가정을 하고 있었다.

 

그러나 우리는 결정에 대한 결과를 예측하지 못할 수 있고, 이 경우에 optimal policy를 만드는 것이 불가능해진다. 따라서 우리는 확률 이론을 도입함으로써 이 문제를 다루게 된다. (저자는 이것이 주사위 놀이와 다를 바 없어보인다 해서 너무 실망하지 말라고 다독인다.)

 

flexible policy는 여러 단계의 결정 과정에서 사건의 발생 가능성까지 고려한다. principle of optimality는 확률적, 결정론적 결정 과정까지 다루는 수학적 도구를 제공한다. stochastic이라는 단어 역시 확률에 의한 사건을 표현할 때 사용된다고 한다.

 

Adaptive control

 

또한 우리는 system에 필요한 변수를 모두 알고 있고, 모든 결정에 대해 잘 알고 있으며, 결정론적이든 확률적이든 그 원인과 결과에 대해 알고 있고, 이 결정의 목적이 명확하다는 가정을 가지고 있다.

 

즉 우리는 system에 대한 기본 동작을 모두 알고 있다는 전제를 하는 것이다.

 

그러나 실제로는 시스템에 대해서 아주 잘 알고 있는 경우는 거의 없다. 따라서 우리는 행동하는 동시에 학습을 해야하고, 그 학습을 통해 policy를 수정할 필요가 있음을 알게 된다. 우리는 시스템에서의 상태(state) 뿐 아니라 시스템에 대한 information(그리고 이를 통해 learning)을 고려하여 control을 해야하고 이를 adaptive control이라고 한다.

Not only do we have to decide upon the allocation of time and other resources to the control activity; we also must decide how much time and effort to devote to studying the intrinsic nature of the system.

 

Hierarchy of Decision Making

 

위의 과정은 learning이자 곧 thinking을 의미한다. 기계는 생각을 한다고 생각할수 있을까? 우리는 기계가 일련의 decision process를 할 수 있다고 생각할 뿐이다. 창조의 영역까지 간다면 대단하겠지만 일단은 여러 level의 decision making process를 만듦으로써 몇 가지 일들을 수행할 수 있을 것이다. 이를 hierarchy of decision making이라고 한다.

 

conclusion

 

인간과 거의 유사하게 digital computer(machine)가 이행할 수 있을까? 우리가 인간의 mind가 어떻게 작동하는지 이해할 수 있을까? 인간의 마음이 어떻게 작동하는지 이해하고 그것을 재생산해낼 수 있는 수준까지는 아직 시간이 걸릴 것이다.

 

수학자들은 그의 심장을 흔드는 수많은 어려운 문제들과 마주한다. 그가 절데 풀 수 없는 것들도 존재하겠지만 그는 결코 지루하지 않을 것이다. 그에게 뭘 더 바라겠는가?