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

برنامه نویسی پویای دیفرانسیلی (DDP)، یک الگوریتم کنترلی بهینه از رده بهینه سازی مسیر است. این الگوریتم در سال ۱۹۹۶ توسط ماینی Mayne معرفی شد و بعدها در کتاب جاکوبسون (Jacobson )و ماینی مورد تحلیل قرارگرفت . این الگوریتم از مدل‌های با مرتبه دوی توابع هزینه و حرکت بهره می‌برد و همگرایی از نوع درجه دومquadratic convergence را به نمایش می‌گذارد. این رویکرد خیلی نزدیک به روش نیوتون(Newton) قدم به قدم که متعلق به پانتوجا(Pantoja) هست می‌باشد .
مسائل زمان گسسته با کران محدود
مکانیک حرکت:
این فرمول تغییرات را به صورت تابعی از متغیرکنترلی از زمان تا نشان می‌دهد. هزینه کل یعنی مجموع هزینه‌های اجرا و هزینه نهایی است که وقتی محقق می‌شود که با شروع از وضعیت و اعمال دنباله کنترلی به کران مورد نظر برسیم:
در اینجا است و برای از معادله بدست می‌آید. راه حل مسئله کنترل بهینه، مینیمم کردن دنباله کنترلی است. بهینه سازی مسیر یعنی پیدا کردن برای یک خاص به جای تمامی وضعیت‌های اولیه‌ی ممکن.
برنامه نویسی پویا
فرض کنید که یک دنباله کنترل جزئی باشد : و هزینه رفتن به به صورت مجموع جزئی هزینه هااز به تعریف شود:
هزینه بهینه‌ی رفتن یا تابع ارزش در زمان ، هزینه رفتنی است که دنباله کنترلی مینیمم را می‌دهد:
با قراردادن ، اصل برنامه نویسی پویاdynamic programming principle، مینیمم سازی را به جای انجام آن در کل دنباله کنترل‌ها به دنباله‌ای از مینیمم سازی‌ها روی تنها یک کنترل محدود می‌کند، که روند پیشرفت آن نسبت به زمان، روبه عقب است:
این معادله بلمن(Bellman) معادله بلمناست.
برنامه نویسی پویای دیفرانسیلی
DDP، ازطریق انجام تکراری یک پاس روبه عقب روی مسیری جزئی انجام می‌شود تا دنباله کنترلی جدید تولید کند و سپس یک پاس رو به جلو برای محاسبه و ارزیابی یک مسیر جزئی جدید انجام می‌شود. ما با پاس رو به عقب شروع می‌کنیم. اگر
آرگومانی از عملگر در معادله باشد، را تغییرات این کمیت درمحدوده امین جفت در نظر می‌گیریم:
\begin{alignQ(\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 بسط می‌دهیم.
زیرنویس در اینجا نوع دیگر از زیرنویسی موریموتو(Morimoto) است که زیرنویس‌ها تفاوت در چیدمان مشتق را نشان می‌دهند.
با رها کردن اندیس جهت خوانایی، علامت پرایم گام زمانی بعدی را نشان می‌دهد ، ضرایب بسط داده شده به صورت زیر هستند:
\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
جملات آخر در سه معادله آخر ادغانم یک بردار را با یک تانسور نشان می‌دهند. با کمینه کردن تخمین درجه دوم برحسب داریم:
با دادن جمله حلقه باز و جمله بازخورد و قرار دادن نتیجه در اکنون ما مدل درجه دوم ارزش در زمان را داریم:
\begin{alignat{2
\Delta V(i) -= -{ -\tfrac{1{2Q_\mathbf{u Q_{\mathbf{u\mathbf{u^{-1Q_\mathbf{u\\
V_\mathbf{x(i) -= Q_\mathbf{x - {- Q_\mathbf{u Q_{\mathbf{u\mathbf{u^{-1Q_{\mathbf{u\mathbf{x\\
V_{\mathbf{x\mathbf{x(i) -= Q_{\mathbf{x\mathbf{x -{ - Q_{\mathbf{x\mathbf{uQ_{\mathbf{u\mathbf{u^{-1Q_{\mathbf{u\mathbf{x.
\end{alignat
با محاسبه بازگشتی مدل‌های درجه دوم محلی از و اصلاحات کنترلی ، از تا گذر رو به عقب را تشکیل می‌شود. همانند بالا، ارزش با مقداردهی اولیه می‌شود. هر وقت گذر روبه عقب کامل شد، گذر روبه جلو یک مسیر جدیدی را محاسبه می‌نماید:
\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، یعنی اطمینان پیدا کردن از اینکه ماتریس در معادله همیشه مثبت positive definite است. جستجوی خطی در DDP یعنی تغییر مقیاس دادن کنترل حلقه باز از طریق ضریب آلفا که به نحوی که برقرار باشد.
کنترل بهینهکنترل بهینه