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

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

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

مکانیک حرکت:

$\mathbf {x} _{i+1}=\mathbf {f} (\mathbf {x} _{i},\mathbf {u} _{i})$

(1)

این فرمول تغییرات $\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$ از معادله Eq. 1 بدست می آید. راه حل مسئله کنترل بهینه، مینیمم کردن دنباله کنترلی $\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، مینیمم سازی را به جای انجام آن در کل دنباله کنترل¬ها به دنباله¬ای از مینیمم سازی ها روی تنها یک کنترل محدود می کند، که روند پیشرفت آن نسبت به زمان، روبه عقب است:

$V(\mathbf {x} ,i)=\min _{\mathbf {u} }[\ell (\mathbf {x} ,\mathbf {u} )+V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)].$

(2)

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

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

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

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

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

${\begin{aligned}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{aligned}}$

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

$\approx {\frac {1}{2}}{\begin{bmatrix}1\\\delta \mathbf {x} \\\delta \mathbf {u} \end{bmatrix}}^{\mathsf {T}}{\begin{bmatrix}0&Q_{\mathbf {x} }^{\mathsf {T}}&Q_{\mathbf {u} }^{\mathsf {T}}\\Q_{\mathbf {x} }&Q_{\mathbf {x} \mathbf {x} }&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}}$

(3)

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

${\begin{alignedat}{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{alignedat}}$

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

${\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} ),$

(4)

با دادن جمله حلقه باز $\mathbf {k} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }$ و جمله بازخورد $\mathbf {K} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }$ و قرار دادن نتیجه در (3) اکنون ما مدل درجه دوم ارزش در زمان $i$ را داریم:

${\begin{alignedat}{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{alignedat}}$

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

${\begin{aligned}{\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{aligned}}$

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

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

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

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

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

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

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