動的計画法の簡単な応用例 / A Simple Application of DP
(1) 問題設定 / Problem description
Fig.1の回路で，充電時の内部抵抗でのエネルギー損失が最小になるよう充電電流を決めたい。 The charging current in Fig.1 is determined so as to minimize the energy loss in the internal resistance. https://scrapbox.io/files/66c29f1d00a8df001c8e2764.png
Fig 1: コンデンサ充電回路 / Capacitor charging circuit.
(2) 問題の定式化 / Mathematical formulation of the problem
$ W=\int_{0}^{T}R i(t)^{2}dt \rightarrow \min: エネルギー損失 / Energy loss
$ \frac{d}{dt}v(t)=\frac{1}{C}i(t) \quad \left (\because v(t)=\frac{Q}{C}=\frac{1}{C}\int_{0}^{t}i(\tau)d\tau \right): 状態方程式 / State equation
$ i(t) \in \{ i_{a}, i_{b}, i_{c}, \cdots \}
$ v(0)=0,\ v(T)=V
(3) 離散化 / Discretization
$ t=n \Delta T \quad \left(0\leq n \leq N: N=\frac{T}{\Delta T} \right)
離散化された問題 / Discretized problem $ W=\sum_{k=0}^{N} R i_{k}^{2} \Delta T = R \Delta T\sum_{k=0}^{N}i_{k}^{2} \rightarrow \min
Subject to:
$ v_{n+1}=v_{n}+\frac{\Delta T}{C}i_{n} \quad i_{n} \in \{ i_{a}, i_{b}, i_{c}, \cdots \} \quad v_{0}=0,\ v_{N}=V
区間 $ n, N での部分エネルギー損失$ W_{n}を定義 / Defining the partial energy loss$ W_{n}in $ n, N.
$ W_{n}=\sum_{k=n}^{N} R i_{k}^{2} \Delta T \ \rightarrow \ W_{n}=W_{n+1}+R i_{n}^{2}
状態変数も離散化を行い，Fig.2のように$ v-t平面での格子状のノードを考える。 / The state variable is also discretized; the nodes in the$ v-t plane are latticed as Fig.2.
各ノードにおいて，$ W_{n}が最も小さくなるような$ i_{n}を選択。 / $ i_{n} is determined so as to minimize $ W_{n} in each node.
https://scrapbox.io/files/66c2a1302730a2001d464dca.png
Fig.2: 離散化された平面での最適軌道 / Optimal trajectory in discretized plane.
(4) 数値例 / Numerical example
$ R = 1 \Omega, \ C = 1000 \mu\mathrm{F}, \ \Delta T = 1 \mathrm{ms}, \ T = 5 \mathrm{ms}, \ V = 5 \mathrm{V}, \ i_{n} \in \{0, 1, 2\}
$ v_{n+1}=v_{n}+i_{n}, \quad W_{n}=W_{n+1}+i_{n}^{2}
(5) 結果 / Result
(5.1) 逆方向探索 / Backward Search
探索方法はFig.3の通り。ただし，(c)に示すように，最適な軌道が複数ある場合，ここでは最も電流が大きいものを選択するものとする。
The method to find the optimal current is shown in Fig.3. As shown in (c), if there are several optimal trajectories, the largest current value is selected in this case.
https://scrapbox.io/files/66c2a29c7a4e8b001cf39352.png
Fig.3: 各ノードの最適電流の探索方法 / Method to find the optimal current.
ラベリングを$ n=N-1\ \rightarrow 0まで繰り返すとFig.4のようになり，後ろ向き探索が完了する。
If the labeling is processed $ n=N-1\ \rightarrow 0, the backward search is completed as Fig.4.
https://scrapbox.io/files/66c2a38679228d001c2ddfde.png
Fig.4: 後ろ向き探索の完了 / Completed backward search.
(5.2) 順方向探索 / Forward search
逆方向探索が終わったら，Fig.5のようにSTARTから各ノードのラベルをもとに最適軌道を辿り，GOALに至ればよい。その結果，$ i_{n} =1 \mathrm{A}一定に保つのが最適で，$ W =5 \mathrm{J}である。この事実は本手法を適用するまでもなく理論的に明らかである。
After the backward search, one can find the optimal trajectory by following the labels from START to GOAL like Fig.5. The optimal result is $ i_{n} =1 \mathrm{A} as constant and $ W =5 \mathrm{J}. This fact is consistent with theoretical consideration.
https://scrapbox.io/files/66c2a36e3c7407001dac9304.png
Fig.5: 前向き探索 / Forward search.
(5.3) ロバスト性 / Robustness
https://scrapbox.io/files/66c2a3dac09276001da89731.png
Fig.6: 最初のステップで充電できなかった時の軌道再構成 / Trajectory reconfiguration when capacitor cannot be charged at the first step.
この手法では，本質的に任意のノードからGOALまでの最適軌道が分かる。従って，Fig.5のように，最初のステップで充電に失敗した場合でも，即座にノードXからの最適軌道を順方向探索だけで再構成でき，外乱に対するロバスト性（頑健性）を有する。 This method with DP inherently enables us to find the optimal trajectory from any node to GOAL. Therefore, for example, Fig.6 shows how to reconfigure the optimal trajectory from the node X immediately only by the forward search when the charging is failed at the first step. This is because the method has robustness against disturbances. この資料は，大学院科目「電気エネルギー管理と制御」用に作成したものをScrapboxに転記したものである。