برنامه ریزی پویا — از صفر تا صد

در آموزش‌های قبلی مجله فرادرس، با کنترل بهینه آشنا شدیم. حل معادلاتی که در رگولاتورهای مرتبه دوم خطی به دست آوردیم، تحت شرایط غیر از حالت ماندگار کار دشواری است. در این موارد می‌توان از روش‌های عددی استفاده کرد. یکی از این روش‌ها، برنامه ریزی پویا (Dynamic Programming) است که می‌توان به راحتی آن را به مسئله گسسته رگولاتور مرتبه دوم خطی (LQR) اعمال کرد. برنامه‌ریزی پویا یک روش کارآمد برای حل انواع خاصی از مسائل بهینه‌سازی است و اولین بار، «ریچارد بلمن» (Richard Bellman) آن را ارائه کرد.

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

$$\large J ( x [ k ] ) = \underbrace { m i n } _ { u [ k ] } \left [ L ( x [ k ] , u [ k ] , x [ k + 1 ] ) + J ( x [ k + 1 ] ) \right ]$$

در بسیاری از موارد، عبارت بالا به صورت زیر اصلاح می‌شود:

 $$\large J ( x [ k ] ) = \underbrace { m i n } _ { u [ k ] } \left [ L ( x [ k ] , u [ k ] , x [ k + 1 ] ) + \gamma J ( x [ k + 1 ] ) \right ]$$

عامل $$\gamma$$ مقادیر آینده هزینه رو به جلو را کاهش می‌دهد. اگر $$\gamma = 0$$، آنگاه در الگوریتم، از مقدار هزینه رو به جلو کاملاً چشم‌پوشی می‌شود، در حالی که اگر $$\gamma$$ بزرگ باشد، مقادیر آینده مورد توجه بیشتری قرار می‌گیرند. وجود $$\gamma$$ در آن دسته از روش‌های عددی نیز مفید است که در آن‌ها مقدار هزینه رو به جلو را برای شروع نمی‌دانیم و آن را به صورت بازگشتی تخمین می‌زنیم. ضریب $$\gamma$$ اثرات مفروضات اشتباه اولیه را کاهش می‌دهد.

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

مثالی از برنامه ریزی پویا

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

در مثال بالا، محاسبه مسیر بهینه با شروع از شرایط اولیه دشوار است. کار ساده‌تر، محاسبه هزینه رو به جلو با شروع از یک هدف (GOAL) و بازگشت به عقب است. بعد از گام اول، خانه بالا و پایین هدف، هزینه رو به جلویی برابر با ۱ خواهد داشت.

می‌توانیم این گام را برای چهار چرخه بعدی انجام دهیم که در آن، هزینه رو به جلوی متناظر با هر خانه در شکل زیر مشخص شده است. توجه کنید که سلول‌های بالا و سمت راستِ خانه متناظر با ۵ امتیاز، هر دو امتیاز ۶ دارند.

نقشه هزینه رو به جلو برای موقعیت هدف مطابق شکل زیر است.

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

برنامه ریزی پویا برای کنترل رگولاتور خطی درجه دوم

در این بخش روند بالا برای محاسبه کنترل بهینه را برای یک سیستم خطی به فرم زیر بیان می‌کنیم:

$$\large X [ k ] = A X [ k - 1 ] + B u [ k - 1 ]$$

می‌خواهیم کنترل‌کننده‌ای برای تابع هزینه زیر طراحی کنیم:

$$\large J ( x [ k ] ) = \underbrace { m i n } _ { u [ k ] } \left [ \frac { 1 } { 2 } \left ( X [ k ] ^ T Q X [ k ] + u [ k ] ^ T R u [ k ] \right ) + J ( x [ k + 1 ] ) \right ]$$

که عبارتِ

$$\large J ( x [ N ] ) = \frac { 1 } { 2 } X [ N ] ^ T S _ N X [ N ] ,$$

هزینه در انتهای هر چرخه است. برنامه‌ریزی پویا را با گام برداشتن به عقب از $$N$$ شروع می‌کنیم:

$$\large J ( x [ N - 1 ] ) = \underbrace { m i n } _ { u [ N - 1 ] } \left [ \frac { 1 } { 2 } \left ( X [ N - 1 ] ^ T Q X [ N - 1 ] +u [ N - 1 ] ^ T R u [ N - 1 ] \right ) + J ( x [ N ] ) \right ]$$

از آنجایی که $$J ( x [ N ] ) = \frac { 1 } { 2 } X [ N ] ^ T S _ N X [ N ]$$، داریم:

$$\large J ( x [ N ] ) = \frac { 1 } { 2 } \left ( A X [ N - 1 ] + B u [ N - 1 ] \right ) ^ T S _ N ( A X [ N - 1 ] + B u [ N - 1 ] ) ,$$

بنابراین:

$$\large J ( x [ N - 1 ] ) = \underbrace { m i n } _ { u [ N - 1 ] } \left [ \frac { 1 } { 2 } \left ( X [ N - 1 ] ^ T Q X [ N - 1 ] + u [ N - 1 ] ^ T R u [ N - 1 ] \right ) \\ \large + \frac { 1 } { 2 } ( A X [ N - 1 ] + B u [ N - 1 ] ) ^ T S _ N ( A X [ N - 1 ] + B u [ N - 1 ] ) \right ]$$

توجه کنید که $$x[N-1]$$ به $$u[N-1]$$ وابسته نیست. بنابراین، هزینه رو به جلوی بهینه را می‌توان با استفاده از مشتقات ماتریسی و مشتق‌گیری نسبت به $$u[N-1]$$ محاسبه کرد:

$$\large \frac { \partial J ( x [ N - 1 ] ) } { \partial u [ N - 1 ] } = \left [ u [ N - 1 ] ^ T R + ( A X [ N - 1 ] + B u [ N - 1 ] ) ^ T S _ N B \right ] = 0$$

از آنجایی که $$R$$ و $$S _ N$$ متقارن هستند، می‌توان نوشت:

$$\large R u [ N - 1 ] + B ^ T S _ N ( A X [ N - 1 ] + B u [ N - 1 ] ) = 0$$

$$\large u [ N - 1 ] = - ( R + B ^ T S _ N B ) ^ { - 1 } B ^ T S _ N A X [ N - 1 ]$$

کنترل بالا را می‌توان به صورت $$u[N-1] = - K_{N-1} X[N-1]$$ نوشت که در آن:

$$\large K _ { N - 1 } = ( R + B ^ T S _ N B ) ^ { - 1 } B ^ T S _ N A X [ N - 1 ]$$

اکنون تابع هزینه $$J(x[N-1])$$ را می‌توان به صورت زیر نوشت:

$$\large J ( x [ N - 1 ] ) = \left [ \frac { 1 } { 2 } \left ( X [ N - 1 ] ^ T Q X [ N - 1 ] + u [ N - 1 ] ^ T R u [ N - 1 ] \right ) + J ( x [ N ] ) \right ]$$

$$\large J ( x [ N - 1 ] ) = \frac { 1 } { 2 } \left [ \left ( X [ N - 1 ] ^ T Q X [ N - 1 ] + X [ N - 1 ] ^ T K _ { N - 1 } ^ T R K _ { N - 1 } u [ N - 1 ] \right ) \\ \large + X [ N - 1 ] ^ T ( A - B K _ { N - 1 } ) ^ T S _ N ( A - B K _ { N - 1 } X [ N - 1 ] ) \right ]$$

اگر $$J(x[N-1] )$$ را به صورت $$\frac{1}{2} X[N-1]^T S_{N-1} X[N-1]$$ بنویسیم، آنگاه:

$$\large S _ { N - 1 } = Q + K _ { N - 1 } ^ T R K _ { N - 1 } + ( A - B K _ { N - 1 } ) ^ T S _ N ( A - B K _ { N - 1 } )$$

عبارت بالا همان معادله ریکاتی است که قبلاً‌ درباره آن صحبت کردیم و در آن $$S$$ به جای $$P$$ قرار گرفته است. اکنون عبارت هزینه رو به جلو بین $$( N-2)$$ و $$( N-1)$$ برابر است با:

$$\large J ( x [ N - 2 ] ) = \frac { 1 } { 2 } \underbrace { m i n } _ { u [ N - 2 ] } \left [ \left ( X [ N - 2 ] ^ T Q X [ N - 2 ] + u [ N - 2 ] ^ T R u [ N - 2 ] \right ) + J ( x [ N - 1 ] \right ]$$

که در آن:

$$\large J ( x [ N - 1 ] ) = \frac { 1 } { 2 } X [ N - 1 ] ^ T S _ { N - 1 } X [ N - 1 ] ,$$