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

برنامه‌نویسی پویای دیفرانسیلی (DDP)، یک الگوریتم کنترلی بهینه از رده بهینه سازی مسیر است. این الگوریتم در سال (۱۹۹۶) توسط ماینی Mayne معرفی شد و بعدها در کتاب جاکوبسون (Jacobson )و ماینی مورد تحلیل قرارگرفت. این الگوریتم از مدل‌های با مرتبه دوی توابع هزینه و حرکت بهره می برد و همگرایی از نوع درجه دومquadratic convergence را به نمایش می گذارد. این رویکرد خیلی نزدیک به روش نیوتون(Newton) قدم به قدم که متعلق به پانتوجا(Pantoja) هست می‌باشد .

مسائل زمان گسسته با کران محدود

مکانیک حرکت:

 الگو:NumBlk

این فرمول تغییرات $𝐱$را به صورت تابعی از متغیرکنترلی $𝐮$از زمان $i$تا $i+1$ نشان می‌دهد. هزینه کل $J_0$ یعنی مجموع هزینه‌های اجرا $\ell$و هزینه نهایی ${\ell }_f$است که وقتی محقق می‌شود که با شروع از وضعیت $𝐱$و اعمال دنباله کنترلی $𝐔\equiv \{{𝐮}_0,{𝐮}_1\dots ,{𝐮}_{N-1}\}$ به کران مورد نظر برسیم:

$J_0(𝐱,𝐔)=\sum _{i=0}^{N-1}\ell ({𝐱}_i,{𝐮}_i)+{\ell }_f({𝐱}_N),$

در اینجا ${𝐱}_0\equiv 𝐱$است و${𝐱}_i$ برای $i>0$ از معادله الگو:EquationNote بدست می آید. راه حل مسئله کنترل بهینه، مینیمم کردن دنباله کنترلی ${𝐔}^{*}(𝐱)\equiv {\mathrm{argmin}}_{𝐔}{J}_0(𝐱,𝐔).$ است. بهینه سازی مسیر یعنی پیدا کردن${𝐔}^{*}(𝐱)$برای یک $𝐱$خاص به جای تمامی وضعیت‌های اولیهٔ ممکن.

برنامه نویسی پویا

فرض کنید که${𝐔}_i$یک دنباله کنترل جزئی${𝐔}_i\equiv \{{𝐮}_i,{𝐮}_{i+1}\dots ,{𝐮}_{N-1}\}$ باشد : و هزینه رفتن به $J_i$به صورت مجموع جزئی هزینه هااز$i$ به $N$تعریف شود:

$J_i(𝐱,{𝐔}_i)=\sum _{j=i}^{N-1}\ell ({𝐱}_j,{𝐮}_j)+{\ell }_f({𝐱}_N).$

هزینه بهینهٔ رفتن یا تابع ارزش در زمان $i$، هزینه رفتنی است که دنباله کنترلی مینیمم را می‌دهد:

$V(𝐱,i)\equiv \underset{{𝐔}_i}{\min }{J}_i(𝐱,{𝐔}_i).$ با قراردادن $V(𝐱,N)\equiv {\ell }_f({𝐱}_N)$، اصل برنامه نویسی پویاdynamic programming principle، مینیمم سازی را به جای انجام آن در کل دنباله کنترل¬ها به دنباله¬ای از مینیمم سازی ها روی تنها یک کنترل محدود می کند، که روند پیشرفت آن نسبت به زمان، روبه عقب است:

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

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

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

$\ell (𝐱,𝐮)+V(𝐟(𝐱,𝐮),i+1)$

آرگومانی از عملگر $\min []$ در معادله الگو:EquationNoteباشد، $Q$را تغییرات این کمیت درمحدوده $i$امین جفت $(𝐱,𝐮)$ در نظر می گیریم:

$\begin{array}{cccc}Q(\delta 𝐱,\delta 𝐮)\equiv & \ell (𝐱+\delta 𝐱,𝐮+\delta 𝐮)& & +V(𝐟(𝐱+\delta 𝐱,𝐮+\delta 𝐮),i+1)\\ -& \ell (𝐱,𝐮)& & -V(𝐟(𝐱,𝐮),i+1)\end{array}$

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

زیرنویس $Q$ در اینجا نوع دیگر از زیرنویسی موریموتو(Morimoto) است که زیرنویس‌ها تفاوت در چیدمان مشتق را نشان می دهند. با رها کردن اندیس $i$ جهت خوانایی، علامت پرایم گام زمانی بعدی را نشان می‌دهد $V^{\prime }\equiv V(i+1)$ ، ضرایب بسط داده شده به صورت زیر هستند:

$\begin{array}{cc}{Q}_{𝐱}& ={\ell }_{𝐱}+{𝐟}_{𝐱}^{𝖳}V{\text{'}}_{𝐱}\\ Q_{𝐮}& ={\ell }_{𝐮}+{𝐟}_{𝐮}^{𝖳}V{\text{'}}_{𝐱}\\ Q_{𝐱𝐱}& ={\ell }_{𝐱𝐱}+{𝐟}_{𝐱}^{𝖳}V{\text{'}}_{𝐱𝐱}{𝐟}_{𝐱}+{V_{𝐱}}^{\prime }\cdot {𝐟}_{𝐱𝐱}\\ Q_{𝐮𝐮}& ={\ell }_{𝐮𝐮}+{𝐟}_{𝐮}^{𝖳}V{\text{'}}_{𝐱𝐱}{𝐟}_{𝐮}+V{\text{'}}_{𝐱}\cdot {𝐟}_{𝐮𝐮}\\ Q_{𝐮𝐱}& ={\ell }_{𝐮𝐱}+{𝐟}_{𝐮}^{𝖳}V{\text{'}}_{𝐱𝐱}{𝐟}_{𝐱}+V{\text{'}}_{𝐱}\cdot {𝐟}_{𝐮𝐱}.\end{array}$

جملات آخر در سه معادله آخر ادغانم یک بردار را با یک تانسور نشان می دهند. با کمینه کردن تخمین درجه دوم الگو:EquationNote برحسب $\delta 𝐮$داریم:

با دادن جمله حلقه باز $𝐤=-Q_{𝐮𝐮}^{-1}{Q}_{𝐮}$ و جمله بازخورد $𝐊=-Q_{𝐮𝐮}^{-1}{Q}_{𝐮𝐱}$ و قرار دادن نتیجه در الگو:EquationNote اکنون ما مدل درجه دوم ارزش در زمان $i$ را داریم:

$\begin{array}{ccc}\mathrm{\Delta }V(i)& =& -\frac{1}{2}{Q}_{𝐮}{Q}_{𝐮𝐮}^{-1}{Q}_{𝐮}\\ V_{𝐱}(i)& =Q_{𝐱}& -Q_{𝐮}{Q}_{𝐮𝐮}^{-1}{Q}_{𝐮𝐱}\\ V_{𝐱𝐱}(i)& =Q_{𝐱𝐱}& -Q_{𝐱𝐮}{Q}_{𝐮𝐮}^{-1}{Q}_{𝐮𝐱}.\end{array}$

با محاسبه بازگشتی مدل‌های درجه دوم محلی از $V(i)$و اصلاحات کنترلی $\{𝐤(i),𝐊(i)\}$ ، از $i=N-1$تا $i=1$ گذر رو به عقب را تشکیل می‌شود. همانند بالا، ارزش با $V(𝐱,N)\equiv {\ell }_f({𝐱}_N)$ مقداردهی اولیه می‌شود. هر وقت گذر روبه عقب کامل شد، گذر روبه جلو یک مسیر جدیدی را محاسبه می نماید:

$\begin{array}{cc}\widehat{𝐱}(1)& =𝐱(1)\\ \widehat{𝐮}(i)& =𝐮(i)+𝐤(i)+𝐊(i)(\widehat{𝐱}(i)-𝐱(i))\\ \widehat{𝐱}(i+1)& =𝐟(\widehat{𝐱}(i),\widehat{𝐮}(i))\end{array}$

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

قاعده سازی و جستجوی خطی

برنامه‌نویسی پویای دیفرانسیلی الگویتم مرتبه دویی شبیه به روش نیوتون است. بنابراین این روش از گام‌های بزرگی در راستای مینیم کردن بهره می برد و اغلب نیاز به قاعده سازیregularization و/یا جستجوی خطی line-search برای رسیدن همگرایی دارد. . قاعده سازی در زمینه DDP، یعنی اطمینان پیدا کردن از اینکه ماتریس $Q_{𝐮𝐮}$در معادله الگو:EquationNote همیشه مثبت positive definite است. جستجوی خطی در DDP یعنی تغییر مقیاس دادن کنترل حلقه باز $𝐤$از طریق ضریب آلفا که به نحوی که $0<\alpha <1$ برقرار باشد.

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

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

پیوندهای خارجی

• A Python implementation of DDP
• A MATLAB implementation of DDP