최적제어 3강 - 벨만의 원리와 Dynamic Programming

 

 

최적성의 원리는 a+b가 최적이라면, b보다 나은 b'은 없다는 것을 전제로 함

 

 

최적의 경로란 앞서 구한 stage까지가 최적의 해라면, 다음 stage에서 최적의 경로를 구할 때 앞서 구한 최적의 해까지는 건드리지 않는 것이 Bellman's principle이고 이게 바로 dynamic 프로그래밍

 

stage 형태로 만들어서 변수를 두고, Starting 포인트에서 일정 Stage까지 경로를 구했으면, 다음 Stage에서는 이전 Stage에서 다음 Stage 사이까지만 고려하고 Starting 포인트 부터 고려하지 않는것이 핵심

 

 

위 예를 봤을때, Bellman의 원리를 이용하면 계산량이 줄어듦

 

 

functional이란 벡터를 어떠한 연산을 통해서 scalar로 만들어내는 작업을 말함

 

여기서는 g(x(t),u(t)를 적분을 해서 스칼라인 cost J로 만들어내는 것을 말함

 

최적에서는 J를 최소화 시키는 x와 u를 구하는 작업

 

 

cost-to-go는 k에서 N으로 가는 경로들을 말함

 

한 마디로는 J k,N (x(k)). 현재 x(k) 위치해있는데, k부터 N으로 가는 cost들을 J k,N (x(k))로 정의

 

여기서 state x는 state equation으로 구해짐 x(k+1) = f(x(k),u(k)))

 

 

만약 K+1부터 N 까지의 경로에 대해서 이미 최적 경로를 알고 있다면, k에서 k+1 까지의 경로에서만 최적의 경로를 찾으면 됨.

 

이 경우 위와 같이 수식을 만들 수 있는데, 결국 변수는 u(k)로, 어떻게 제어를 해서 최적을 할지 결정하는 문제라고 볼 수 있음

 

 

Real world에서는 저 사이에 값이 나올 수 있는데, 이 경우 interpolation을 활용

 

 

Cost J = h + g

 

h :  penalty term 같은 개념 (제어를 하긴 하지만 완벽히 할 수는 없어서 최종 원하는 state에 도달하기 위한 비용이 발생할 때 지불하기 위함)

g : 경로에 따른 cost

 

 

Dynamic 프로그래밍에서 쓰이는 표현을 정리

 

먼저 state 변화량 x'(t) = a(x(t),u(t))로 이루어지는데, discrete system을 반영하고, 간략화하면 결국

 

x(k+1) = a(x(k),u(k)) 로 표현됨.

 

 

Cost의 경우 J = H + G로 나타냈는데, 이 또한 decrete system으로 표현하면 아래와 같음

 

 

x(N-1) to X(N)으로 가는 최적화를 하려면 u(N-1)을 구하면 됨

 

근데 이걸 x(N-2) to x(N-1)... 등등으로 계속 이어나가면.. 아래와 같이 정리 가능

 

 

벨만의 원리에 의하면 (N-K)+1에서 N까지의 최적값이 이미 정해졌을 때, N-K에서 N-K+1로 가는 최적의 경로만 구하면 전체적인 최적이 보장됨

 

그래서 N-K에서 N-K+1로 가는 최적 경로를 구하기 위해서는 제어항인 u(N-K)를 변수로하여 문제를 풀면 됨

 

u(N-K)가 어떻게 결정되느냐에 따라 N-K+1의 여러 점에 도달할 수 있고, 그에 따라 cost도 바뀜.

 

 

결론저긍로, 벨만의 원리는 동적계획법의 핵심 개념이며,

 

동적계획법이란 큰 문제를 작은 문제로 쪼개서 해를 차례차례 구하고 이미 구한값을 재귀적으로 활용하여 계산적 효율을 추구하는 알고리즘임

 

 

그리고 동적계획법이 우리나라 사람들 입장에서는 직관적으로 받아들여지지는 않는데,

 

실제로 벨만은 긍정적인 인상을 주면서도 복잡해 보이는 이름을 찾아서 일부러 지은 것