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

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

مسائل زمان گسسته با کران محدود
مکانیک حرکت:
  
این فرمول تغییرات  را به صورت تابعی از متغیرکنترلی از زمان تا  نشان می‌دهد. هزینه کل  یعنی   مجموع هزینه‌های اجرا  و هزینه نهایی است که وقتی محقق می‌شود که با شروع از وضعیت و اعمال دنباله کنترلی    به کران مورد نظر برسیم:

 
در اینجا است و برای  از معادله  بدست می آید. راه حل مسئله کنترل بهینه، مینیمم کردن دنباله کنترلی   است. بهینه سازی مسیر یعنی پیدا کردنبرای یک خاص به جای تمامی وضعیت‌های اولیهٔ ممکن.

برنامه نویسی پویا
فرض کنید کهیک دنباله کنترل جزئی باشد :   و هزینه رفتن به   به صورت مجموع جزئی هزینه هااز به تعریف شود:

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

 با قراردادن ، اصل برنامه نویسی پویاdynamic programming principle، مینیمم سازی را به جای انجام آن در کل دنباله کنترل¬ها به دنباله¬ای از مینیمم سازی ها روی تنها یک کنترل محدود می کند، که روند پیشرفت آن نسبت به زمان، روبه عقب است:

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

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

آرگومانی از عملگر  در معادله باشد، را تغییرات این کمیت درمحدوده امین جفت  در نظر می گیریم:

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

زیرنویس  در اینجا نوع دیگر از زیرنویسی موریموتو(Morimoto) است که زیرنویس‌ها تفاوت در چیدمان مشتق را نشان می دهند.
 با رها کردن اندیس  جهت خوانایی، علامت پرایم گام زمانی بعدی را نشان می‌دهد  ، ضرایب بسط داده شده به صورت زیر هستند:
 

جملات آخر در سه معادله آخر ادغانم یک بردار را با یک تانسور نشان می دهند. با کمینه کردن تخمین درجه دوم  برحسب    داریم:

 	 	 
با دادن جمله حلقه باز  و  جمله بازخورد   و قرار دادن نتیجه در  اکنون ما مدل درجه دوم ارزش در زمان   را داریم:

با محاسبه بازگشتی مدل‌های درجه دوم محلی از و اصلاحات کنترلی  ، از تا  گذر رو به عقب را تشکیل می‌شود. همانند بالا، ارزش با   مقداردهی اولیه می‌شود. هر وقت گذر روبه عقب کامل شد، گذر روبه جلو یک مسیر جدیدی را محاسبه می نماید:

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

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

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

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

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

منابع

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

 A Python implementation of DDP
 A MATLAB implementation of DDP

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