برنامه‌نویسی پویای دیفرانسیلی

**برنامه‌نویسی پویای دیفرانسیلی** (DDP)، یک الگوریتم کنترلی بهینه از رده بهینه سازی مسیر است. این الگوریتم در سال (۱۹۹۶) توسط ماینی Mayne معرفی شد و بعدها در کتاب جاکوبسون (Jacobson )و ماینی مورد تحلیل قرارگرفت. این الگوریتم از مدل‌های با مرتبه دوی توابع هزینه و حرکت بهره می برد و همگرایی از نوع درجه دومquadratic convergence را به نمایش می گذارد. این رویکرد خیلی نزدیک به روش نیوتون(Newton) قدم به قدم که متعلق به پانتوجا(Pantoja) هست می‌باشد .
## مسائل زمان گسسته با کران محدود
مکانیک حرکت:
  
این فرمول تغییرات  \textstyle\mathbf{x}را به صورت تابعی از متغیرکنترلی \mathbf{u}از زمان iتا i+1 نشان می‌دهد. *هزینه کل* J_0 یعنی   مجموع هزینه‌های اجرا  \textstyle\ellو هزینه نهایی \ell_fاست که وقتی محقق می‌شود که با شروع از وضعیت \mathbf{x}و اعمال دنباله کنترلی  \mathbf{U} \equiv \{\mathbf{u}_0,\mathbf{u}_1\dots,\mathbf{u}_{N-1}\}  به کران مورد نظر برسیم:
:J_0(\mathbf{x},\mathbf{U})=\sum_{i=0}^{N-1}\ell(\mathbf{x}_i,\mathbf{u}_i) + \ell_f(\mathbf{x}_N),
 
در اینجا \mathbf{x}_0\equiv\mathbf{x}است و\mathbf{x}_i برای i>0 از معادله  بدست می آید. راه حل مسئله کنترل بهینه، مینیمم کردن دنباله کنترلی  \mathbf{U}^*(\mathbf{x})\equiv \operatorname{argmin}_{\mathbf{U}} J_0(\mathbf{x},\mathbf{U}). است. *بهینه سازی مسیر* یعنی پیدا کردن\mathbf{U}^*(\mathbf{x})برای یک \mathbf{x}خاص به جای تمامی وضعیت‌های اولیهٔ ممکن.

## برنامه نویسی پویا
فرض کنید که\mathbf{U}_iیک دنباله کنترل جزئی\mathbf{U}_i \equiv \{\mathbf{u}_i,\mathbf{u}_{i+1}\dots,\mathbf{u}_{N-1}\} باشد :   و *هزینه رفتن* به   J_iبه صورت مجموع جزئی هزینه هاازi به Nتعریف شود:
:J_i(\mathbf{x},\mathbf{U}_i)=\sum_{j=i}^{N-1}\ell(\mathbf{x}_j,\mathbf{u}_j) + \ell_f(\mathbf{x}_N).
 
هزینه بهینهٔ رفتن یا *تابع ارزش *در زمان i، هزینه رفتنی است که دنباله کنترلی مینیمم را می‌دهد:

:V(\mathbf{x},i)\equiv \min_{\mathbf{U}_i}J_i(\mathbf{x},\mathbf{U}_i). با قراردادن V(\mathbf{x},N)\equiv \ell_f(\mathbf{x}_N)، اصل برنامه نویسی پویاdynamic programming principle، مینیمم سازی را به جای انجام آن در کل دنباله کنترل¬ها به دنباله¬ای از مینیمم سازی ها روی تنها یک کنترل محدود می کند، که روند پیشرفت آن نسبت به زمان، روبه عقب است:

[\ell(\mathbf{x},\mathbf{u}) + V(\mathbf{f}(\mathbf{x},\mathbf{u}),i+1)].|}}

این معادله بلمن(Bellman) معادله بلمناست.

## برنامه نویسی پویای دیفرانسیلی
DDP، از طریق انجام تکراری یک پاس روبه عقب روی مسیری جزئی انجام می‌شود تا دنباله کنترلی جدید تولید کند و سپس یک پاس رو به جلو برای محاسبه و ارزیابی یک مسیر جزئی جدید انجام می‌شود. ما با پاس رو به عقب شروع می کنیم. اگر

:\ell(\mathbf{x},\mathbf{u}) + V(\mathbf{f}(\mathbf{x},\mathbf{u}),i+1)

آرگومانی از عملگر \min[] در معادله باشد، Qرا تغییرات این کمیت درمحدوده iامین جفت (\mathbf{x},\mathbf{u}) در نظر می گیریم:

:\begin{align}Q(\delta\mathbf{x},\delta\mathbf{u})\equiv &\ell(\mathbf{x}+\delta\mathbf{x},\mathbf{u}+\delta\mathbf{u})&&{}+V(\mathbf{f}(\mathbf{x}+\delta\mathbf{x},\mathbf{u}+\delta\mathbf{u}),i+1)
\\
-&\ell(\mathbf{x},\mathbf{u})&&{}-V(\mathbf{f}(\mathbf{x},\mathbf{u}),i+1)
\end{align}


و آن را به مرتبه 2 بسط می دهیم.

 & Q_{\mathbf{x}\mathbf{u}}\\
Q_\mathbf{u} & Q_{\mathbf{u}\mathbf{x}} & Q_{\mathbf{u}\mathbf{u}}
\end{bmatrix}
\begin{bmatrix}
1\\
\delta\mathbf{x}\\
\delta\mathbf{u}
\end{bmatrix}
|}}

زیرنویس Q در اینجا نوع دیگر از زیرنویسی موریموتو(Morimoto) است که زیرنویس‌ها تفاوت در چیدمان مشتق را نشان می دهند.
 با رها کردن اندیس i جهت خوانایی، علامت پرایم گام زمانی بعدی را نشان می‌دهد V'\equiv V(i+1) ، ضرایب بسط داده شده به صورت زیر هستند:
 
:
\begin{alignat}{2}
Q_\mathbf{x} &= \ell_\mathbf{x}+ \mathbf{f}_\mathbf{x}^\mathsf{T} V'_\mathbf{x} \\
Q_\mathbf{u} &= \ell_\mathbf{u}+ \mathbf{f}_\mathbf{u}^\mathsf{T} V'_\mathbf{x} \\
Q_{\mathbf{x}\mathbf{x}} &= \ell_{\mathbf{x}\mathbf{x}} + \mathbf{f}_\mathbf{x}^\mathsf{T} V'_{\mathbf{x}\mathbf{x}}\mathbf{f}_\mathbf{x}+V_\mathbf{x}'\cdot\mathbf{f}_{\mathbf{x}\mathbf{x}}\\
Q_{\mathbf{u}\mathbf{u}} &= \ell_{\mathbf{u}\mathbf{u}} + \mathbf{f}_\mathbf{u}^\mathsf{T} V'_{\mathbf{x}\mathbf{x}}\mathbf{f}_\mathbf{u}+{V'_\mathbf{x}} \cdot\mathbf{f}_{\mathbf{u} \mathbf{u}}\\
Q_{\mathbf{u}\mathbf{x}} &= \ell_{\mathbf{u}\mathbf{x}} + \mathbf{f}_\mathbf{u}^\mathsf{T} V'_{\mathbf{x}\mathbf{x}}\mathbf{f}_\mathbf{x} + {V'_\mathbf{x}} \cdot \mathbf{f}_{\mathbf{u} \mathbf{x}}.
\end{alignat}


جملات آخر در سه معادله آخر ادغانم یک بردار را با یک تانسور نشان می دهند. با کمینه کردن تخمین درجه دوم  برحسب    \delta\mathbf{u}داریم:

^* = \operatorname{argmin}\limits_{\delta \mathbf{u}}Q(\delta \mathbf{x},\delta
\mathbf{u})=-Q_{\mathbf{u}\mathbf{u}}^{-1}(Q_\mathbf{u}+Q_{\mathbf{u}\mathbf{x}}\delta \mathbf{x}),
|}}
 	 	 
با دادن جمله حلقه باز \mathbf{k}=-Q_{\mathbf{u}\mathbf{u}}^{-1}Q_\mathbf{u} و  جمله بازخورد \mathbf{K}=-Q_{\mathbf{u}\mathbf{u}}^{-1}Q_{\mathbf{u}\mathbf{x}}  و قرار دادن نتیجه در  اکنون ما مدل درجه دوم ارزش در زمان  i را داریم:

:
\begin{alignat}{2}
\Delta V(i) &= &{} -\tfrac{1}{2}Q_\mathbf{u} Q_{\mathbf{u}\mathbf{u}}^{-1}Q_\mathbf{u}\\
V_\mathbf{x}(i) &= Q_\mathbf{x} & {}- Q_\mathbf{u} Q_{\mathbf{u}\mathbf{u}}^{-1}Q_{\mathbf{u}\mathbf{x}}\\
V_{\mathbf{x}\mathbf{x}}(i) &= Q_{\mathbf{x}\mathbf{x}} &{} - Q_{\mathbf{x}\mathbf{u}}Q_{\mathbf{u}\mathbf{u}}^{-1}Q_{\mathbf{u}\mathbf{x}}.
\end{alignat}


با محاسبه بازگشتی مدل‌های درجه دوم محلی از V(i)و اصلاحات کنترلی \{\mathbf{k}(i),\mathbf{K}(i)\} ، از i=N-1تا i=1 گذر رو به عقب را تشکیل می‌شود. همانند بالا، ارزش با  V(\mathbf{x},N)\equiv \ell_f(\mathbf{x}_N) مقداردهی اولیه می‌شود. هر وقت گذر روبه عقب کامل شد، گذر روبه جلو یک مسیر جدیدی را محاسبه می نماید:

:
\begin{align}
\hat{\mathbf{x}}(1)&=\mathbf{x}(1)\\
\hat{\mathbf{u}}(i)&=\mathbf{u}(i) + \mathbf{k}(i) +\mathbf{K}(i)(\hat{\mathbf{x}}(i) - \mathbf{x}(i))\\
\hat{\mathbf{x}}(i+1)&=\mathbf{f}(\hat{\mathbf{x}}(i),\hat{\mathbf{u}}(i))
\end{align}


پاس‌های روبه عقب و جلو آنقدر تکرار می‌شوند تا در نهایت همگرا شوند.

## قاعده سازی و جستجوی خطی
برنامه‌نویسی پویای دیفرانسیلی الگویتم مرتبه دویی شبیه به روش نیوتون است. بنابراین این روش از گام‌های بزرگی در راستای مینیم کردن بهره می برد و اغلب نیاز به قاعده سازیregularization و/یا جستجوی خطی line-search برای رسیدن همگرایی دارد.

. قاعده سازی در زمینه DDP،  یعنی اطمینان پیدا کردن از اینکه ماتریس   Q_{\mathbf{u}\mathbf{u}}در معادله   همیشه مثبت positive definite است. جستجوی خطی در DDP یعنی تغییر مقیاس دادن کنترل حلقه باز \mathbf{k}از طریق ضریب آلفا که به نحوی که  0 برقرار باشد.

## جستارهای وابسته

* کنترل بهینهکنترل بهینه

## منابع

## پیوند به بیرون

* A Python implementation of DDP
* A MATLAB implementation of DDP

رده:برنامه‌نویسی پویا